具有隐私保护的分布式共轭对偶梯度算法

吕净阁，李德权

（安徽理工大学 数学与大数据学院，淮南 232000）

多个体系统是由大量自主个体或节点相互之间通过局部信息交流而构成的网络化系统［1］，其中每个个体或节点独立地进行计算和通信，并通过与邻居个体相互协调可有效处理复杂任务。正因为多个体系统的自主性、智能性和协同一致性等特点，近年来随着计算能力和网络技术的快速发展而备受研究者的关注，并在众多领域有着广泛的应用。作为多个体系统极为重要的一个应用领域，分布式优化问题研究的是系统中的n个个体如何协同地求解如下最小化问题：

其中，x∈R是所有个体所知的状态决策变量，fi:R→R是个体i的局部目标函数，个体间通过交流各自的本地局部目标函数和状态信息来求解问题（1）。解决问题（1）的典型分布式算法包括分布式（次）梯度算法（DG）［2，3］、对偶平均（DDA）［4，5］、交替方向乘子法（ADMM）以及变体［6-9］等方法。目前，这些分布式优化算法广泛应用于机器学习、无线传感器网络等领域。分布式（次）梯度算法主要通过计算每个局部目标函数的（次）梯度以及个体间的平均状态来寻求最优解；而对偶平均则针对凸但非平滑损失函数，通过对函数求一阶（次）梯度来解决分布式问题；ADMM算法则通过引入拉格朗日函数完成对原问题的转换而形成对偶问题，在对原始变量迭代的同时进行对偶变量的迭代来寻求最优解。

上述分布式优化算法通常要求系统中的个体在每一次迭代时将本地估计传递给邻居个体来寻求一致最优解。但当个体的状态包括隐私信息时，例如医院里的患者信息库有疾病种类或者年龄等隐私信息，这种信息的直接交换会因为隐私泄漏而导致安全隐患［10］。为了有效确保隐私，近年来隐私保护成为分布式优化研究的一个热点问题。最常见的隐私保护算法是差分隐私［11,12］，它通过在状态上添加精心设计的扰动来掩盖敏感信息以达到保护隐私的效果，然而添加的扰动会影响算法的收敛性；另外一种是信息加密［13-15］，但传统的加密方法在没有第三方协助的情况下难以直接应用于分布式优化问题。

本文主要研究基于共轭对偶梯度算法的隐私保护性，采用的同态加密［16］被证实能够对分布式计算环境下的用户隐私进行有效保护。同态加密可分为部分同态加密、浅同态加密和全同态加密。本文通过结合部分同态加密技术和共轭对偶梯度算法提出一种具有隐私保护的共轭对偶梯度算法2（PP-CDG），与基于差分隐私的分布式优化算法不同，算法2不仅能保证找到最优解，也能够确保多个体系统中个体的隐私信息不被窃取。

1 问题描述

图论中，将n个个体构成的网络拓扑结构用一个时变无向图Gk(V,Ek,Ak)来表示，其中k表示时刻，V=(1,2,...,n)是通信网络中的个体集，Ek⊂V×V代表个体之间的边集，Ak∈Rn×n为拓扑图对应的权重矩阵；(j,i)∈Ek表示在k时刻个体j和i之间有边相连，代表个体i的邻居集合，代表个体i的度，代表度矩阵；若每个个体之间都有一条路径，则称图为连通图；本文假设网络拓扑图是无向图，则其权重矩阵Ak是对称矩阵，元素满足：

考虑n个个体构成的无向时变系统，共轭对偶梯度将问题（1）转化为

其中，每个个体i有着局部的目标函数fi:R→R。

假设1［17］每个个体的局部目标函数fi,i∈V是1-强凸的，即∀x,y∈Κ和fi在x处的次梯度∂fi(x)有

假设2（1）最优解存在；（2）Κ,C是闭凸集

2 共轭对偶问题

共轭函数的定义是：di(w)=supx∈Κ(w⋅x-fi(x))，受文献［18，19］启发，通过添加如下正则项防止共轭函数震荡，且保证共轭函数的界更小，同时也便于有效地进行对偶转换：

相应地，可将优化问题（2）转化为如下对偶形式：

式（3）表示的是一类典型的资源优化分配问题［20，21］，可以采用基于梯度下降法或加权梯度算法进行求解。进一步地，由共轭函数的可微性可得：

再由假设 1，∇di利普希茨连续［18］其常数为Γi=(θi+1)/θi=2。因此，∇D的利普希茨常数为Γ=(θmin+1)/θmin=2 。

假设3 （周期连通性）存在B∈[1,∞)，使得对任何k≥0，在一个周期B内，图是连通的。

优化问题（3）可以通过如下共轭对偶梯度算法来解决：选取对偶变量初始点w0且满足1T⋅w0=0,w0Tw0=0，进而迭代如下：

其中α＞0是固定步长。则（5）的矩阵形式为：

其中Pk=I-αLk是Perron矩阵，Lk是时变拉普拉斯矩阵，其定义为：

（6）式可以通过下述算法1来实现：

算法1共轭对偶梯度（CDG）

1：个体i选择初始值并令

2：fork=0,1,...do

3：通讯：个体i∈V将其状态传递给邻居

4：接收到邻居的状态后，个体i更新对偶变量：

6：对没有邻居的个体保留前一时刻的状态即

3 具有隐私保护的分布式共轭对偶梯度算法

和分布式优化算法［2-8］类似，算法1要求所有个体在每一次迭代时，将本地估计传递给邻居来达成共识，这易造成信息泄露［1］。为了避免信息在交流中被敌对个体窃取，已经提出了许多保护隐私的方法，如在文献［11，12］中提出的差分隐私，通过在状态上添加扰动来保护隐私，但添加的扰动会影响算法的收敛性；文献［13-15］中提出的加密（encryption），如全同态加密，在没有第三方协助时却难以直接应用于分布式优化。本文将Paillier Cryptosystem机制和算法1结合，进行隐私保护。

3.1 同态加密

文献［16］中介绍了public-key cryptographies密码系统，使用两种钥匙：可以被任何个体用来加密信息的公钥和用来解密的私钥。此密码系统有：RSA、EL-Gamal和 Paillier［7］。本文将采用的是Paillier Cryptosystem机制，与其他算法相比，该加密方法不仅适用于分布式系统、具有隐私保护性又能保证算法的收敛。具体算法如下：

（1）选择两个素数p,q令n=pq，g=n+1，λ=(p-1)(q-1)。

（2）令μ=ϕ(n)-1modn是ϕ(n)的模乘逆.

（3）公钥kp=(n,g)，私钥ks=(λ,μ)

加密(c=ε(m))

定义：其中gcd()是最大公约数.

这是一个思维难度较大、有多种结论的开放性问题，没想到竟然有学生提出想知道邓爷爷植树的愿望是什么？教学目标自然达成。我觉得这是一节高质量的课堂。

（4）选择一个随机数

（5）密文是c=gm⋅rnmodn2其中

解密(m=D(c))

（6）定义整数分解函数Τ(μ)=(μ-1)/n.

（7）明文是m=Τ(cλmodn2)⋅μmodn

3.2 具有隐私保护的共轭对偶梯度算法

本节将结合上述Paillier Cryptosystem机制与算法1，确保在解决分布式问题（2）时可以对多个体系统中个体的隐私进行保护。为此构造权重对：，其中仅为个体i所知［7］。该构造方法不仅可以防止两个交互个体在交流中推断彼此的状态信息从而进行了隐私保护，而且还能确保算法的收敛性。

算法2隐私保护的共轭对偶梯度算法（PP-CDG）

个体i选择初始值并令

输入：；输出：

（1）个体i用公钥kpi对加密得到

（2）个体i将和公钥kpi传递给邻居个体j∈Ni

（3）个体j∈Ni用公钥对加密得到，通过同态性得

（4）个体j∈Ni计算权重为的差异再将传递给个体i

（5）个体i用私钥ksi对进行解密再乘上得到

（6）计算

（7）通过计算得到

（8）令k=k+1

对算法2，有下面几点说明：

（1）的构造是保护隐私的关键；

（2）对负状态加密得到是因为该方法具有加法同态性；

（3）个体i的状态以及中间状态被加密得以保护。

4PP-CDG收敛性分析

算法收敛性分析与步长选择密切相关，本文选取固定步长

假设4 拉普拉斯矩阵Lk的特征值满足

假设4和（8）能够保证Perron矩阵Pk是正定可逆矩阵。

引理1 当假设1、2成立，wk是算法1生成的对偶序列，则对偶函数是有界函数，即存在一个正数M，使得对任意k≥0，序列wk成立

证明：由假设1知D(w)是可微的，故在闭区间C上是连续的，由闭区间上的连续函数一定是有界易知引理1成立。

定义，其中B是假设3中的周期，是正定可逆矩阵，为便于证明，令

其中 ΛΓ=diag(Γ1,Γ2,…,Γn)是对偶梯度的利普希茨常数组成的对角阵且是2I。

引理2 当假设1、2、3、4成立，wk是算法1生成的对偶序列且步长满足（8）、（9），则有：

证明：一方面由范数性质得

另一方面由三角不等式得：

由∇D的利普希茨连续性和三角不等式得：

则由上述三式易得

引理3如果假设1、2、3、4成立，wk是算法1生成的对偶序列且步长满足（8）、（9），则对偶函数满足周期性递减，即：

证明：由范数的性质得

再利用D(w)的可微性、假设4以及引理2即可得结论成立。

有了上面准备知识，下面证明本文对偶函数的收敛性。

定理1 如果假设1、2、3、4成立，wk是算法1生成的对偶序列且步长满足（8）、（9），并令D∗是对偶函数的最优解，则对偶函数收敛即limk→∞D(wk)=D∗。

证明：由引理1、2、3知对偶函数序列存在极限，即存在任意小的正数ε＞0，使得当时，由引理3知：

其中，则有

故对偶函数序列是平方收敛的。（11）式的第二个不等式主要依据下式得来的：

由假设3知，则：

从而有经过迭代和换算可以得到对偶函数周期性的误差为：

而可得

进一步地，下面定理2证明原函数以及迭代序列收敛到最优值。

定理2 如果假设1、2、3、4成立，设是算法1生成的原始序列且步长满足（8）、（9），则有：

证明：由假设1知问题（2）和（3）强对偶，则对偶函数收敛时原始函数序列亦收敛且最优值满足F∗=-D∗，由凸函数的性质，

由定理1和假设5知 limk→∞xk=x∗；由对偶函数的定义知

故原函数的误差：

因对偶序列是在闭区间生成的，故有界，即存在正数A，使得对任意k≥0均成立故原始函数序列收敛。

下面证明算法2能收敛到最优解。

定理3 如果随机从(0,1)中选择，则算法2能收敛到最优解。

证明：由于故选取步长

满足（8）式，则算法2能够收敛到最优解。

文章中个体状态包含的敏感信息是，算法2意味着当信息被加密之后，其他个体就不能推断出其敏感信息。下面定理4和定理5证明了敌对个体通过收集多步骤的中间信息但却不能获取邻居个体的状态和函数信息。

定理4 假设所有个体都按照算法2进行迭代，则敌对个体i不能推断出邻居个体j的状态信息，除非

证明：从算法2中的第五步可知敌对个体i在第k次迭代能够得到加权差异：

而中间变量由于被加密不为个体i所知。假若个体i通过收集K步的权重差异来推断个体j的状态信息：

这里已知，即2(K+1)个等式4(K+1)个未知量，方程组的解不唯一，故个体i不能推断出个体j的状态信息

定理5 假设系统中的个体都按照算法2进行迭代，则敌对个体i不能推断出邻居个体j的隐私函数fj(xj)。

证明：假设敌对个体i通过收集K步信息来推断邻居个体j的函数信息，由

可以得到

其中∂fi(xi)是函数fi在xi处的次梯度。敌对个体i可以建立K个等式：

在这K个等式中(k=1,...,K)是未知的，而通过算法2知当个体j只有唯一的邻居m时，

是已知的，否则是未知的。那么K个等式中有大于K个未知量，故个体i不能推断出邻居个体j的隐私函数fj(xj)。

5 结论

本文主要介绍了基于梯度下降法的分布式共轭对偶梯度算法（CDG）的隐私保护，解决了分布式优化中可能存在的隐私隐患，当目标函数强凸、对应的对偶函数可微时证明了所提算法的收敛性；最后证明了敌对个体即使收集多步骤的中间信息也不能推断出邻居个体的状态信息和局部目标函数。本文研究的是无向时变网络且目标函数是强凸，对有向非平衡网络下的PP-CGD算法进行研究将是下一步的主要工作。

［1］余智欣，黄天戍，杨乃扩，等.一种新型的分布式隐私保护计算模型及其应用［J］.西安交通大学学报，2007，41（08）：954-958.

［2］Nedic A，Ozdaglar A.Distributed subgradient methods for multiagent optimization［J］.IEEE Transactions on Automatic Control，2009，54（01）：48-61.

［3］Lobel I，Ozdaglar A.Distributed subgradient methods for convex optimization over random networks［J］.IEEE Transactions on Automatic Control，2011，56（06）：1291-1306.

［4］Agarwal A，Wainwright MJ，Duchi JC.Distributed dualaveraging in networks［C］.In Advancesin NeuralInformation Processing Systems，2010，23：550-558.

［5］Duchi JC，Agarwal A，Wainwright MJ.Dual averaging for distributed optimization：Convergence analysis and network scaling［J］.IEEE Transactions on Automatic control，2012，57（03）：592-606.

［6］Boyd S，Parikh N，Chu E，et al.Distributed optimization and statistical learning via the alternating direction method of multipliers［J］. Foundations &Trends in Machine Learning，2011，3（01）：1-122.

［7］Zhang C，Wang Y.Privacy-preserving Decentralized OptimizationBasedonADMM［J］.2017，arXiv：1707.04338.

［8］He BS，Xu HK，Yuan X.On the proximal jacobian decomposition of ALM for multiple-block separable convex minimization problemsand itsrelationship to ADMM［J］.Journal of Scientif i c Computing，2016，66（03）：1204-1217.

［9］许浩锋，凌青.分布式在线交替方向乘子法［J］.计算机应用，2015，35（06）：1595-1599.

［10］王杰，赵铭，于晓.云存储数据安全关键技术研究［J］.长春理工大学学报：自然科学版，2014（02）：147-150.

［11］Huang ZQ，Mitra S，Vaidya N.Differentially private distributed optimization［C］.In Proceedings of the 2015 InternationalConference on Distributed Computing and Networking.2015：1-10.

［12］Han S，Topcu U，Pappas GJ.Differentially private distributed constrained optimization［J］.IEEE Transactions on Automatic Control，2017，62（1）：50-64.

［13］LazzerettiR，Horn S，Braca P，etal.Secure multi-party consensus gossip algorithms［C］.IEEE International Conference on Acoustics，Speech and Signal Processing.IEEE，2014：7406-7410.

［14］Freris NM，Patrinos P.Distributed computing over encrypted data［C］.Communication，Control&Computing.IEEE，2017：1116-1122.

［15］Gentry，Craig.Fully homomorphic encryption using ideal lattices［C］.ACM Symposium on Theory of Computing，2009：169-178.

［16］巩林明，李顺东，郭奕旻.同态加密的发展及应用［J］.中兴通讯技术，2016，22（01）：26-29.

［17］Bertsekas D P.Convex optimization theory［M］.北京：清华大学出版社，2011.

［18］Wu X，Lu J.Fenchel Dual Gradient Methods for Distributed Convex Optimization over Time-varying Networks［C］.IEEE 56th Annual Conference on Decision and Control（CDC）.2017：2894-2899.

［19］Bach F.Duality between subgradient and conditional gradient methods［J］.SIAM Journal on Optimization，2015，25（01）：491-492.

［20］Xiao L，Boyd S.Optimalscaling ofa gradient method for distributed resource allocation［J］.Journal of Optimization Theory&Applications，2006，129（03）：469-488.

［21］Lakshmanan H，De Farias DP.Decentralized Resource Allocation in Dynamic Networks of Agents［J］.SIAM Journal on Optimization，2008，19（02）：911-940.