一种用于分布式优化的加权梯度跟踪隐私保护方法

《Automatica》：A weighted gradient tracking privacy-preserving method for distributed optimization

　　

## 摘要

本文研究了保护隐私的分布式优化问题，旨在优化过程中保护智能体的私有信息免受潜在攻击者的窃取。梯度追踪是一种提高分布式优化收敛率的先进技术，近年来已被广泛应用于大多数一阶算法中。我们首先揭示了梯度追踪所固有的隐私泄漏风险。基于这一洞察，我们提出了一种加权梯度追踪分布式隐私保护算法，通过使用衰减权重因子消除了梯度追踪中的隐私泄漏风险。然后，我们在时变异构步长下刻画了所提算法的收敛性。我们证明了在温和假设条件下，所提算法能够精确收敛到最优解。最后，通过经典分布式估计问题和卷积神经网络的分布式训练，数值仿真验证了算法的有效性。

## 引言

随着网络系统的兴起，分布式优化受到了广泛关注，并被广泛应用于多智能体系统（Wang et al., 2024, Yi et al., 2023）、分布式学习（Liu, Chai et al., 2024）和电力系统（Cai et al., 2024, Liu, Xie et al., 2024）。然而，由于实际应用中涉及大量敏感信息，分布式优化中的隐私泄漏风险已成为其进一步发展和应用的主要障碍。在不妨碍其他性能（如精度或鲁棒性）的前提下开发隐私保护的分布式优化算法，是当前研究的关键挑战之一。现有的隐私保护算法大致可分为三类：基于差分隐私的方法、基于加密的方法以及基于相关随机性的方法（Wang, 2024），以下三段将分别进行简要回顾。

**基于差分隐私的方法**通过向智能体之间的交互信息中注入随机噪声来实现隐私保护。Ding et al.（2022）和Huang et al.（2015）分别基于分布式投影梯度下降算法和梯度追踪算法提出了差分私有的分布式优化算法。然而，由于注入的随机噪声导致优化精度损失，这两种算法无法收敛到最优解。此外，梯度追踪技术导致噪声的累积，这对精确收敛更加不利。受Pu（2020）中鲁棒性思想的启发，Xuan and Wang（2023）提出了一种基于鲁棒梯度追踪的差分私有的分布式优化算法，该算法避免了噪声累积并提高了优化精度。然而，Wang and Nedi?（2024b）已证明将差分隐私机制直接集成到现有方法中不可避免地会损害优化精度。为此，引入衰减因子来抑制噪声的影响，这可以保证差分隐私性并且几乎 surely 收敛到最优解。然而，这种方法收敛速度较慢。由于优化精度和收敛速度对算法的重要性，寻找隐私水平与这些性能之间的更好权衡至关重要。

**基于加密的方法**通过使用密码技术对智能体之间的交互信息进行加密来保护隐私。Paillier密码系统是广泛使用的加密技术。基于权重分解策略，Ruan et al.（2019）首次将Paillier密码系统以完全分布式的方式应用于平均一致性。受Ruan et al.（2019）的启发，Zhang et al.（2019）和Zhang and Wang（2019）分别通过将Paillier密码系统与分布式ADMM和分布式投影次梯度下降方法相结合，开发了基于加密的隐私保护算法。然而，这些方法仅限于无向图，并且计算和通信负担较重。Liu et al.（2025）通过使用高级加密标准（AES）提出了一种轻量级隐私保护算法，不仅显著降低了计算复杂度，还适用于时变有向图。尽管有这些改进，基于加密的方法仍然需要额外的计算和通信成本，这在处理大规模优化问题时将面临挑战。

**基于相关随机性的方法**通过向智能体之间的交互信息中引入空间上或时间上相关的随机性来实现隐私保护。Wang（2019）提出了一种状态分解策略，通过将智能体的状态分解为两个随机子状态来保护平均一致性中智能体的初始信息。在Wang（2019）的基础上，Cheng et al.（2024）提出了一种基于状态分解的分布式优化隐私保护算法。在Gade and Vaidya（2018）中，通过将结构化随机噪声注入智能体之间的交互信息来保护智能体的私有信息。Gao et al.（2023）利用系统动力学的鲁棒性，通过增加优化参数的随机性来实现隐私保护。Li et al.（2020）通过双变量将随机噪声注入非收敛子空间来保护智能体的私有信息。然而，上述基于相关随机性的隐私保护方法需要一个额外的拓扑假设：每个智能体必须至少有一个不参与攻击的合法邻居。从实现角度看，确保该假设成立是具有挑战性的。此外，这些方法容易受到能够访问通信网络内所有共享消息的攻击者的攻击。

为了克服上述局限性，在本文中，我们首先揭示了先进的分布式优化方法如何泄露智能体的私有信息，然后提出了一种新颖的隐私保护算法。总而言之，本文的主要贡献包括：（1）我们为有向图上的分布式优化提出了一种基于加权梯度追踪的隐私保护算法，通过引入衰减权重因子规避了梯度追踪中固有的隐私泄漏风险。（2）所提算法在不损害优化精度、不增加计算或通信负担、也不施加额外拓扑假设的情况下保护智能体的私有信息。这与以优化精度换取隐私的差分隐私方法、引入计算和通信开销的加密方法以及施加额外拓扑假设的相关随机性方法截然不同。（3）我们在目标函数强凸且光滑的一般假设下严格证明了所提算法的收敛性。衰减权重因子的引入减少了算法对状态空间的探索，从而带来了分析挑战，使得现有文献中的分析方法不再适用。通过我们的分析，我们推导出了确保算法收敛到最优解的衰减权重因子的充分条件，并刻画了算法在时变异构参数下的收敛行为。

本文的组织结构如下。第2节介绍了问题建模，揭示了梯度追踪中的隐私泄漏风险，并提出了加权梯度追踪隐私保护算法。第3节收敛性分析和第4节隐私分析分别证明了收敛性和隐私性。第5节验证了算法的有效性。最后，第6节总结全文。

## 符号说明

考虑有向图$G=([n], E)$，其中$[n] = \{1, 2, \ldots, n\}$是智能体集合，$E \subseteq [n] \times [n]$是智能体有序对的边集合。集合$N_i^{\text{out}} = \{j \mid (i,j) \in E\}$和$N_i^{\text{in}} = \{j \mid (j,i) \in E\}$分别表示智能体$i$的输出邻居和输入邻居。我们用$\mathbf{1}$和$\mathbf{0}$分别表示全1列向量和全0列向量，用$I$表示单位矩阵。它们的维度由上下文决定。对于任意向量$v$，$\|v\|_2$表示$v$的欧几里得范数，$v_i$表示$v$的第$i$个分量。如果$v$是时变的，时间$k$时的第$i$个分量记为$[v_k]_i$。对于任意两个维度适当的向量$v$和$u$，$\langle v, u \rangle$表示$v$和$u$的内积。除非特别说明，所有向量均视为列向量。对于任意矩阵$M$，$\|M\|_2$表示$M$的谱范数，$M^*$表示$M$的共轭转置，$M_{ij}$表示$M$的第$i$行第$j$列元素。如果$M$是时变的，时刻$k$时的第$i$行第$j$列元素记为$[M_k]_{ij}$。对于两个同维矩阵$M$和$N$，$M \leq N$表示对所有$i$和$j$都有$M_{ij} \leq N_{ij}$。对于方阵$M$，$\rho(M)$和$\det(M)$分别表示谱半径和行列式。给定矩阵序列$M_k$，如果$K_2 \geq K_1$，我们定义$\prod_{k=K_1}^{K_2} M_k = M_{K_2} \cdots M_{K_1}$；如果$K_2 < K_1$，则$\prod_{k=K_1}^{K_2} M_k = I$。

## 问题建模

我们考虑有向图$G$上的一个由$n$个智能体组成的系统。这些智能体的目标是通过本地计算和局部通信协作求解以下全局目标函数：

$$\min_{x \in \mathbb{R}^p} f(x) = \sum_{i=1}^n f_i(x)$$

其中$x \in \mathbb{R}^p$是所有智能体共享的决策变量，$f_i: \mathbb{R}^p \to \mathbb{R}$是智能体$i$的局部目标函数。

为后续分析，我们对目标函数和通信图做出以下标准假设：

**假设1** 每个局部目标函数$f_i$

## 收敛性分析

在本节中，我们首先给出一些基本定义和引理。然后，我们给出算法的收敛性结果。更新公式(8)可以写成紧凑形式：

$$\begin{aligned}
x_{k+1} &= A_k(x_k - \alpha y_k) \\
y_{k+1} &= B_k y_k + \lambda_{k+1} \nabla F(x_{k+1}) - \lambda_k \nabla F(x_k)
\end{aligned}$$

其中$\alpha \triangleq \text{diag}\{\alpha_1, \alpha_2, \ldots, \alpha_n\} \in \mathbb{R}^{n \times n}$是对角矩阵，$x_k, y_k, \nabla F(x_k)$分别定义为：

$$\begin{aligned}
x_k &\triangleq (x_1^k, x_2^k, \ldots, x_n^k)^T \in \mathbb{R}^{n \times p} \\
y_k &\triangleq (y_1^k, y_2^k, \ldots, y_n^k)^T \in \mathbb{R}^{n \times p} \\
\nabla F(x_k) &\triangleq (\nabla f_1(x_1^k), \nabla f_2(x_2^k), \ldots, \nabla f_n(x_n^k))^T \in \mathbb{R}^{n \times p}
\end{aligned}$$

由(12b)，由于$\mathbf{1}^T B_k = \mathbf{1}^T$，我们推导出：

$$\mathbf{1}^T y_{k+1} - \lambda_{k+1} \mathbf{1}^T \nabla F(x_{k+1}) = \mathbf{1}^T y_k - \lambda_k \mathbf{1}^T \nabla F(x_k) = \cdots = \mathbf{1}^T y_1 - \lambda_1 \mathbf{1}^T \nabla F(x_1)$$

## 隐私分析

在本节中，我们将详细分析所提算法的隐私保护性能。在问题设置中，可能存在一个诚实智能体的所有邻居都是诚实但好奇的攻击者的情况，这些攻击者可以与外部窃听者合谋推断该诚实智能体的私有信息。我们考虑一个等价的两智能体系统来简化分析，如图1所示。在该系统中，智能体$i$和$j$分别被指定为诚实智能体和……

## 数值仿真

在本节中，我们通过一个经典的传感器融合问题验证所提算法的收敛性，并在DLG推断攻击（Zhu et al., 2019）下评估其隐私性能。

## 结论

在本文中，我们提出了一种基于加权梯度追踪的分布式隐私保护算法，通过引入衰减权重因子消除了梯度追踪中的隐私泄漏风险。我们证明了所提算法能够保护智能体的私有信息，包括其中间状态和所有梯度，使其免受外部窃听者和诚实但好奇的攻击者的窃取。所提隐私保护算法既不产生额外的计算和……

Furan Xie 2021年于武汉科技大学获得自动化学士学位，2025年获得控制科学与工程博士学位。目前，他是中国浙江大学和湖州工业控制技术研究院的博士后研究员，同时隶属于国家重点实验室——工业控制技术国家重点实验室。他的研究方向包括分布式优化、隐私保护优化和电力系统。

**Furan Xie | Bing Liu | Li Chai**