具有隱私保護(hù)的分布式共軛對偶梯度算法

呂凈閣，李德權(quán)

（安徽理工大學(xué) 數(shù)學(xué)與大數(shù)據(jù)學(xué)院，淮南 232000）

多個體系統(tǒng)是由大量自主個體或節(jié)點(diǎn)相互之間通過局部信息交流而構(gòu)成的網(wǎng)絡(luò)化系統(tǒng)［1］，其中每個個體或節(jié)點(diǎn)獨(dú)立地進(jìn)行計(jì)算和通信，并通過與鄰居個體相互協(xié)調(diào)可有效處理復(fù)雜任務(wù)。正因?yàn)槎鄠€體系統(tǒng)的自主性、智能性和協(xié)同一致性等特點(diǎn)，近年來隨著計(jì)算能力和網(wǎng)絡(luò)技術(shù)的快速發(fā)展而備受研究者的關(guān)注，并在眾多領(lǐng)域有著廣泛的應(yīng)用。作為多個體系統(tǒng)極為重要的一個應(yīng)用領(lǐng)域，分布式優(yōu)化問題研究的是系統(tǒng)中的n個個體如何協(xié)同地求解如下最小化問題：

其中，x∈R是所有個體所知的狀態(tài)決策變量，fi:R→R是個體i的局部目標(biāo)函數(shù)，個體間通過交流各自的本地局部目標(biāo)函數(shù)和狀態(tài)信息來求解問題（1）。解決問題（1）的典型分布式算法包括分布式（次）梯度算法（DG）［2，3］、對偶平均（DDA）［4，5］、交替方向乘子法（ADMM）以及變體［6-9］等方法。目前，這些分布式優(yōu)化算法廣泛應(yīng)用于機(jī)器學(xué)習(xí)、無線傳感器網(wǎng)絡(luò)等領(lǐng)域。分布式（次）梯度算法主要通過計(jì)算每個局部目標(biāo)函數(shù)的（次）梯度以及個體間的平均狀態(tài)來尋求最優(yōu)解；而對偶平均則針對凸但非平滑損失函數(shù)，通過對函數(shù)求一階（次）梯度來解決分布式問題；ADMM算法則通過引入拉格朗日函數(shù)完成對原問題的轉(zhuǎn)換而形成對偶問題，在對原始變量迭代的同時進(jìn)行對偶變量的迭代來尋求最優(yōu)解。

上述分布式優(yōu)化算法通常要求系統(tǒng)中的個體在每一次迭代時將本地估計(jì)傳遞給鄰居個體來尋求一致最優(yōu)解。但當(dāng)個體的狀態(tài)包括隱私信息時，例如醫(yī)院里的患者信息庫有疾病種類或者年齡等隱私信息，這種信息的直接交換會因?yàn)殡[私泄漏而導(dǎo)致安全隱患［10］。為了有效確保隱私，近年來隱私保護(hù)成為分布式優(yōu)化研究的一個熱點(diǎn)問題。最常見的隱私保護(hù)算法是差分隱私［11,12］，它通過在狀態(tài)上添加精心設(shè)計(jì)的擾動來掩蓋敏感信息以達(dá)到保護(hù)隱私的效果，然而添加的擾動會影響算法的收斂性；另外一種是信息加密［13-15］，但傳統(tǒng)的加密方法在沒有第三方協(xié)助的情況下難以直接應(yīng)用于分布式優(yōu)化問題。

本文主要研究基于共軛對偶梯度算法的隱私保護(hù)性，采用的同態(tài)加密［16］被證實(shí)能夠?qū)Ψ植际接?jì)算環(huán)境下的用戶隱私進(jìn)行有效保護(hù)。同態(tài)加密可分為部分同態(tài)加密、淺同態(tài)加密和全同態(tài)加密。本文通過結(jié)合部分同態(tài)加密技術(shù)和共軛對偶梯度算法提出一種具有隱私保護(hù)的共軛對偶梯度算法2（PP-CDG），與基于差分隱私的分布式優(yōu)化算法不同，算法2不僅能保證找到最優(yōu)解，也能夠確保多個體系統(tǒng)中個體的隱私信息不被竊取。

1 問題描述

圖論中，將n個個體構(gòu)成的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)用一個時變無向圖Gk(V,Ek,Ak)來表示，其中k表示時刻，V=(1,2,...,n)是通信網(wǎng)絡(luò)中的個體集，Ek?V×V代表個體之間的邊集，Ak∈Rn×n為拓?fù)鋱D對應(yīng)的權(quán)重矩陣；(j,i)∈Ek表示在k時刻個體j和i之間有邊相連，代表個體i的鄰居集合，代表個體i的度，代表度矩陣；若每個個體之間都有一條路徑，則稱圖為連通圖；本文假設(shè)網(wǎng)絡(luò)拓?fù)鋱D是無向圖，則其權(quán)重矩陣Ak是對稱矩陣，元素滿足：

考慮n個個體構(gòu)成的無向時變系統(tǒng)，共軛對偶梯度將問題（1）轉(zhuǎn)化為

其中，每個個體i有著局部的目標(biāo)函數(shù)fi:R→R。

假設(shè)1［17］每個個體的局部目標(biāo)函數(shù)fi,i∈V是1-強(qiáng)凸的，即?x,y∈Κ和fi在x處的次梯度?fi(x)有

假設(shè)2（1）最優(yōu)解存在；（2）Κ,C是閉凸集

2 共軛對偶問題

共軛函數(shù)的定義是：di(w)=supx∈Κ(w?x-fi(x))，受文獻(xiàn)［18，19］啟發(fā)，通過添加如下正則項(xiàng)防止共軛函數(shù)震蕩，且保證共軛函數(shù)的界更小，同時也便于有效地進(jìn)行對偶轉(zhuǎn)換：

相應(yīng)地，可將優(yōu)化問題（2）轉(zhuǎn)化為如下對偶形式：

式（3）表示的是一類典型的資源優(yōu)化分配問題［20，21］，可以采用基于梯度下降法或加權(quán)梯度算法進(jìn)行求解。進(jìn)一步地，由共軛函數(shù)的可微性可得：

再由假設(shè) 1，?di利普希茨連續(xù)［18］其常數(shù)為Γi=(θi+1)/θi=2。因此，?D的利普希茨常數(shù)為Γ=(θmin+1)/θmin=2 。

假設(shè)3 （周期連通性）存在B∈[1,∞)，使得對任何k≥0，在一個周期B內(nèi)，圖是連通的。

優(yōu)化問題（3）可以通過如下共軛對偶梯度算法來解決：選取對偶變量初始點(diǎn)w0且滿足1T?w0=0,w0Tw0=0，進(jìn)而迭代如下：

其中α＞0是固定步長。則（5）的矩陣形式為：

其中Pk=I-αLk是Perron矩陣，Lk是時變拉普拉斯矩陣，其定義為：

（6）式可以通過下述算法1來實(shí)現(xiàn)：

算法1共軛對偶梯度（CDG）

1：個體i選擇初始值并令

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

3：通訊：個體i∈V將其狀態(tài)傳遞給鄰居

4：接收到鄰居的狀態(tài)后，個體i更新對偶變量：

6：對沒有鄰居的個體保留前一時刻的狀態(tài)即

3 具有隱私保護(hù)的分布式共軛對偶梯度算法

和分布式優(yōu)化算法［2-8］類似，算法1要求所有個體在每一次迭代時，將本地估計(jì)傳遞給鄰居來達(dá)成共識，這易造成信息泄露［1］。為了避免信息在交流中被敵對個體竊取，已經(jīng)提出了許多保護(hù)隱私的方法，如在文獻(xiàn)［11，12］中提出的差分隱私，通過在狀態(tài)上添加擾動來保護(hù)隱私，但添加的擾動會影響算法的收斂性；文獻(xiàn)［13-15］中提出的加密（encryption），如全同態(tài)加密，在沒有第三方協(xié)助時卻難以直接應(yīng)用于分布式優(yōu)化。本文將Paillier Cryptosystem機(jī)制和算法1結(jié)合，進(jìn)行隱私保護(hù)。

3.1 同態(tài)加密

文獻(xiàn)［16］中介紹了public-key cryptographies密碼系統(tǒng)，使用兩種鑰匙：可以被任何個體用來加密信息的公鑰和用來解密的私鑰。此密碼系統(tǒng)有：RSA、EL-Gamal和 Paillier［7］。本文將采用的是Paillier Cryptosystem機(jī)制，與其他算法相比，該加密方法不僅適用于分布式系統(tǒng)、具有隱私保護(hù)性又能保證算法的收斂。具體算法如下：

（1）選擇兩個素?cái)?shù)p,q令n=pq，g=n+1，λ=(p-1)(q-1)。

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

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

加密(c=ε(m))

定義：其中g(shù)cd()是最大公約數(shù).

這是一個思維難度較大、有多種結(jié)論的開放性問題，沒想到竟然有學(xué)生提出想知道鄧爺爺植樹的愿望是什么？教學(xué)目標(biāo)自然達(dá)成。我覺得這是一節(jié)高質(zhì)量的課堂。

（4）選擇一個隨機(jī)數(shù)

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

解密(m=D(c))

（6）定義整數(shù)分解函數(shù)Τ(μ)=(μ-1)/n.

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

3.2 具有隱私保護(hù)的共軛對偶梯度算法

本節(jié)將結(jié)合上述Paillier Cryptosystem機(jī)制與算法1，確保在解決分布式問題（2）時可以對多個體系統(tǒng)中個體的隱私進(jìn)行保護(hù)。為此構(gòu)造權(quán)重對：，其中僅為個體i所知［7］。該構(gòu)造方法不僅可以防止兩個交互個體在交流中推斷彼此的狀態(tài)信息從而進(jìn)行了隱私保護(hù)，而且還能確保算法的收斂性。

算法2隱私保護(hù)的共軛對偶梯度算法（PP-CDG）

個體i選擇初始值并令

輸入：；輸出：

（1）個體i用公鑰kpi對加密得到

（2）個體i將和公鑰kpi傳遞給鄰居個體j∈Ni

（3）個體j∈Ni用公鑰對加密得到，通過同態(tài)性得

（4）個體j∈Ni計(jì)算權(quán)重為的差異再將傳遞給個體i

（5）個體i用私鑰ksi對進(jìn)行解密再乘上得到

（6）計(jì)算

（7）通過計(jì)算得到

（8）令k=k+1

對算法2，有下面幾點(diǎn)說明：

（1）的構(gòu)造是保護(hù)隱私的關(guān)鍵；

（2）對負(fù)狀態(tài)加密得到是因?yàn)樵摲椒ň哂屑臃ㄍ瑧B(tài)性；

（3）個體i的狀態(tài)以及中間狀態(tài)被加密得以保護(hù)。

4PP-CDG收斂性分析

算法收斂性分析與步長選擇密切相關(guān)，本文選取固定步長

假設(shè)4 拉普拉斯矩陣Lk的特征值滿足

假設(shè)4和（8）能夠保證Perron矩陣Pk是正定可逆矩陣。

引理1 當(dāng)假設(shè)1、2成立，wk是算法1生成的對偶序列，則對偶函數(shù)是有界函數(shù)，即存在一個正數(shù)M，使得對任意k≥0，序列wk成立

證明：由假設(shè)1知D(w)是可微的，故在閉區(qū)間C上是連續(xù)的，由閉區(qū)間上的連續(xù)函數(shù)一定是有界易知引理1成立。

定義，其中B是假設(shè)3中的周期，是正定可逆矩陣，為便于證明，令

其中 ΛΓ=diag(Γ1,Γ2,…,Γn)是對偶梯度的利普希茨常數(shù)組成的對角陣且是2I。

引理2 當(dāng)假設(shè)1、2、3、4成立，wk是算法1生成的對偶序列且步長滿足（8）、（9），則有：

證明：一方面由范數(shù)性質(zhì)得

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

由?D的利普希茨連續(xù)性和三角不等式得：

則由上述三式易得

引理3如果假設(shè)1、2、3、4成立，wk是算法1生成的對偶序列且步長滿足（8）、（9），則對偶函數(shù)滿足周期性遞減，即：

證明：由范數(shù)的性質(zhì)得

再利用D(w)的可微性、假設(shè)4以及引理2即可得結(jié)論成立。

有了上面準(zhǔn)備知識，下面證明本文對偶函數(shù)的收斂性。

定理1 如果假設(shè)1、2、3、4成立，wk是算法1生成的對偶序列且步長滿足（8）、（9），并令D?是對偶函數(shù)的最優(yōu)解，則對偶函數(shù)收斂即limk→∞D(zhuǎn)(wk)=D?。

證明：由引理1、2、3知對偶函數(shù)序列存在極限，即存在任意小的正數(shù)ε＞0，使得當(dāng)時，由引理3知：

其中，則有

故對偶函數(shù)序列是平方收斂的。（11）式的第二個不等式主要依據(jù)下式得來的：

由假設(shè)3知，則：

從而有經(jīng)過迭代和換算可以得到對偶函數(shù)周期性的誤差為：

而可得

進(jìn)一步地，下面定理2證明原函數(shù)以及迭代序列收斂到最優(yōu)值。

定理2 如果假設(shè)1、2、3、4成立，設(shè)是算法1生成的原始序列且步長滿足（8）、（9），則有：

證明：由假設(shè)1知問題（2）和（3）強(qiáng)對偶，則對偶函數(shù)收斂時原始函數(shù)序列亦收斂且最優(yōu)值滿足F?=-D?，由凸函數(shù)的性質(zhì)，

由定理1和假設(shè)5知 limk→∞xk=x?；由對偶函數(shù)的定義知

故原函數(shù)的誤差：

因?qū)ε夹蛄惺窃陂]區(qū)間生成的，故有界，即存在正數(shù)A，使得對任意k≥0均成立故原始函數(shù)序列收斂。

下面證明算法2能收斂到最優(yōu)解。

定理3 如果隨機(jī)從(0,1)中選擇，則算法2能收斂到最優(yōu)解。

證明：由于故選取步長

滿足（8）式，則算法2能夠收斂到最優(yōu)解。

文章中個體狀態(tài)包含的敏感信息是，算法2意味著當(dāng)信息被加密之后，其他個體就不能推斷出其敏感信息。下面定理4和定理5證明了敵對個體通過收集多步驟的中間信息但卻不能獲取鄰居個體的狀態(tài)和函數(shù)信息。

定理4 假設(shè)所有個體都按照算法2進(jìn)行迭代，則敵對個體i不能推斷出鄰居個體j的狀態(tài)信息，除非

證明：從算法2中的第五步可知敵對個體i在第k次迭代能夠得到加權(quán)差異：

而中間變量由于被加密不為個體i所知。假若個體i通過收集K步的權(quán)重差異來推斷個體j的狀態(tài)信息：

這里已知，即2(K+1)個等式4(K+1)個未知量，方程組的解不唯一，故個體i不能推斷出個體j的狀態(tài)信息

定理5 假設(shè)系統(tǒng)中的個體都按照算法2進(jìn)行迭代，則敵對個體i不能推斷出鄰居個體j的隱私函數(shù)fj(xj)。

證明：假設(shè)敵對個體i通過收集K步信息來推斷鄰居個體j的函數(shù)信息，由

可以得到

其中?fi(xi)是函數(shù)fi在xi處的次梯度。敵對個體i可以建立K個等式：

在這K個等式中(k=1,...,K)是未知的，而通過算法2知當(dāng)個體j只有唯一的鄰居m時，

是已知的，否則是未知的。那么K個等式中有大于K個未知量，故個體i不能推斷出鄰居個體j的隱私函數(shù)fj(xj)。

5 結(jié)論

本文主要介紹了基于梯度下降法的分布式共軛對偶梯度算法（CDG）的隱私保護(hù)，解決了分布式優(yōu)化中可能存在的隱私隱患，當(dāng)目標(biāo)函數(shù)強(qiáng)凸、對應(yīng)的對偶函數(shù)可微時證明了所提算法的收斂性；最后證明了敵對個體即使收集多步驟的中間信息也不能推斷出鄰居個體的狀態(tài)信息和局部目標(biāo)函數(shù)。本文研究的是無向時變網(wǎng)絡(luò)且目標(biāo)函數(shù)是強(qiáng)凸，對有向非平衡網(wǎng)絡(luò)下的PP-CGD算法進(jìn)行研究將是下一步的主要工作。

［1］余智欣，黃天戍，楊乃擴(kuò)，等.一種新型的分布式隱私保護(hù)計(jì)算模型及其應(yīng)用［J］.西安交通大學(xué)學(xué)報，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］.計(jì)算機(jī)應(yīng)用，2015，35（06）：1595-1599.

［10］王杰，趙銘，于曉.云存儲數(shù)據(jù)安全關(guān)鍵技術(shù)研究［J］.長春理工大學(xué)學(xué)報：自然科學(xué)版，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］鞏林明，李順東，郭奕旻.同態(tài)加密的發(fā)展及應(yīng)用［J］.中興通訊技術(shù)，2016，22（01）：26-29.

［17］Bertsekas D P.Convex optimization theory［M］.北京：清華大學(xué)出版社，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.