陳凱麗 李蘇木

摘 要：本文研究了一個具有差分隱私性的無投影分布式在線條件梯度優(yōu)化問題。針對這一問題，提出了一種分布式在線條件梯度（D-OCG）算法作為期望的變體，該方法通過使用線性最小化步驟來避免投影操作。此問題的網(wǎng)絡模型是一個五個節(jié)點的平衡無向圖。我們在理論證明中知道，該算法對于一般凸局部代價函數(shù)的期望遺憾界是O（），其中T是時間范圍。我們的結(jié)果與最后的理論遺憾，可以實現(xiàn)最先進的算法。最后，通過仿真驗證了算法的有效性。

關鍵詞：分布式在線優(yōu)化;差分隱私;在線梯度;期望遺憾

中圖分類號：TP301.6? 文獻標識碼：A? 文章編號：1673-260X（2021）01-0004-05

1 引言

近年來，人們對多智能體網(wǎng)絡上的凸優(yōu)化算法越來越感興趣，由于其在信息控制[1]、機器學習[2]、智能電網(wǎng)[3]等方面的應用。這些應用需要設計分布式優(yōu)化算法，其中所有節(jié)點與它們的即時鄰居交換信息，共同達成一個最佳解決方案的共識，該方案將目標函數(shù)最小化為局部目標函數(shù)的總和[4-8]。

與目標函數(shù)隨時間變化的經(jīng)典分布式優(yōu)化算法相比，分布式在線優(yōu)化可適用于局部代價函數(shù)序列可能以不確定甚至敵對的方式變化的情況。此外，與集中式機器學習算法相比，分布式特性能夠完美地將一個大規(guī)模問題分解為一系列較小的問題，因此對通信故障和環(huán)境的不確定性具有固定的魯棒性，這使得分布式在線優(yōu)化算法特別適用于大規(guī)模網(wǎng)絡。多年來，人們提出了各種分布式在線優(yōu)化算法。例如，Akbari M，Gharesifard B及Linder L擴展了乘法器的交替方向法（ADMM）[9]，H. F. Xu，Q. Ling及A. Ribeiro提出了無向靜態(tài)網(wǎng)絡的分布式在線優(yōu)化算法[10]。然而，基于ADMM的算法需要在每次迭代時求解非線性次優(yōu)問題，這帶來了極高的計算量。因此，引入了用于分布式在線優(yōu)化問題的原對偶算法及其改進方法[11，12]。沿著這樣的思路，A. Koppel，S. Paternain和H. Pradhan，A. S. Bedi等人進一步開發(fā)了用于求解核希爾伯特空間的隨機優(yōu)化問題的分散在線算法[13，14]。最近，X. Yi，X. Li，L. Xie和K. H. Johansson將在線鏡像下降法[16]推廣到一個更具有挑戰(zhàn)性的案例中[15]，其中，針對時變耦合不等式約束網(wǎng)絡的分布式在線優(yōu)化問題，提出了一種原對偶動態(tài)鏡像下降算法。Xiong Y，Xu J和You K等人進一步探索一種對實際應用具有較強適應性的算法。利用拉普拉斯機制和重調(diào)次梯度技術，提出了一種在線算法，該算法既能解決帶行隨機矩陣有向圖上的分布式約束在線優(yōu)化問題，又能同時保持一定的差分私密性[17]。盡管這些算法取得了成功，但它們所要求的投影運算仍然限制了它們在許多實際利益的環(huán)境中的進一步適用性。為了避免這種代價高昂的操作，Wenpeng Zhang，Peilin Zhao，Wenwu Zhu，Steven C. H. Hoi和Tong Zhang提出了條件梯度的分布式在線變量[18]，并期望它能夠通過使用線性最小化步驟來避免投影操作。矩陣學習[19]，多類分類[20]和許多其他相關問題，其中凸域是所有具有有界核范數(shù)的矩陣的集合，投影運算相當于計算矩陣的全部的奇異值分解，過于復雜的操作，不能滿足分布式在線學習中局部計算的需要。在上述情況下，線性步驟相當于找到一個矩陣的最高奇異向量，這至少簡單了一個數(shù)量級。然而，如何設計和分析這種變體仍然是一個開放的問題。

為了填補這一空白，我們提出了分布式在線條件梯度（D-OCG）算法作為期望的變體。該算法是對以前的在線變體[21]的一種新的擴展，即每個本地節(jié)點將自己的對偶變量與鄰居進行交流，以實現(xiàn)相互協(xié)作。我們針對一個多類分類任務，評估D-OCG算法在真實數(shù)據(jù)集上的性能。實驗結(jié)果表明，D-OCG的運行速度明顯快于D-OGD和D-ODA。其每次迭代較低的計算成本及更少的迭代次數(shù)，使其成為一個更快的算法。對遺憾界算法的理論結(jié)果也得到了很好的驗證。

設計在平衡有向圖上的隱私保護算法，使所有節(jié)點以在線分布的方式，隨著時間的推移，令其遺憾度漸近為零。提出了分布式在線條件梯度（D-OCG）算法作為期望的變體，能夠通過使用線性最小化步驟來避免投影操作。

2 預備知識及問題描述

在本節(jié)中，簡要介紹代數(shù)圖論、隱私分布式在線條件梯度的一些初步內(nèi)容，并且對具有隱私保護的無投影分布在線算法進行闡述。

2.1 圖論

考慮一個由n個節(jié)點組成的網(wǎng)絡。節(jié)點之間的信息共享由有向圖G（V，E）來建模，其中V={1，…，n}表示節(jié)點的合集，E？哿V×V表示邊的合集，A=[aij]n×n ∈Rn×n為其對應的鄰接矩陣，所以當（j，i）∈E時，有aij=1，否則aij=0。邊（j，i）∈E表示節(jié)點i可以從節(jié)點j獲取信息，設Ni為具有路徑傳入到節(jié)點i的邊的鄰居的集合，Ni={j：（j，i）∈E}。對于無向圖，如果（j，i）∈E，則有aij=aji。

2.2 問題描述

現(xiàn)在，我們制定了差分隱私分布式在線優(yōu)化問題。在每個迭代t∈[T]，每個節(jié)點i∈V在約束集？奐Rm上做出一個決定xi，t，則局部代價函數(shù)fi，t：Rm→R關于節(jié)點i產(chǎn)生了一個成本函數(shù)fi，t（xi，t）。在這種情況下，在每個t時刻，網(wǎng)絡的目標是最小化以下代價函數(shù)：

fi（x）=fi，t（x），x∈ （1）

這里需要強調(diào)的是，每個節(jié)點只能訪問自己的局部代價函數(shù)，而全局函數(shù)ft不能被任何單個節(jié)點訪問。因此，每個節(jié)點都需要與其相鄰節(jié)點進行通信，協(xié)同解決優(yōu)化問題。此外，隨著時間的推移，本地成本函數(shù)逐漸顯現(xiàn)，每個節(jié)點i在做出決策前都無法訪問fi，t的信息。由于成本函數(shù)是時變的，我們需要設計一個算法，在有限的時間范圍T>0內(nèi)，使算法產(chǎn)生的總代價與最優(yōu)固定決策的代價之差最小。也就是說，如果在提前知道{fi，t}Ti=1所有函數(shù)的情況下，累積收益應該盡可能接近最佳固定決策。考慮到隱私問題，網(wǎng)絡中的節(jié)點通過隨機化機制只與相鄰節(jié)點共享自己的噪聲狀態(tài)，以保護自己的隱私信息。

3 具有隱私保護的無投影分布在線學習算法

在我們的算法中，每個節(jié)點i維護兩個變量xi，t ∈Rm和zi，t∈Rn，i其初始化分別為xi，0∈和zi，0=ei∈Rn。這里，ei是一個分量等于零的標準向量，除了它的第i個元素等于1。時間t∈[T]，每個節(jié)點i生成一個隨機噪聲向量？濁i，t，這個隨機噪聲向量？濁i，t來自由高斯分布N（？滓t），參數(shù)為？滓t。然后變量xi，t被？濁i，t擾動。具體來說，我們設

yi，t=xi，t+？濁i，t? ?（2）

之后，每個節(jié)點i與它的鄰居共享其噪聲狀態(tài)，然后將其狀態(tài)更新如下：

xi，t+1=bi，t-t? （3）

其中bi，t=∑aijyi，t，gi，t是fi，t在（xi，t）處的次梯度，gi，t=？塄fi，t（bi，t，？濁i，t），t為要設計的步長。zii，t是zi，t的第i個分量，用來平衡次梯度gi，t的輔助變量，輔助變量zi，t更新如下：

zi，t+1=aij（zj，t+？濁i，t）? （4）

我們在算法1中總結(jié)了以上內(nèi)容。

—————————————————————

算法1 隱私分布式在線條件梯度

—————————————————————

1：Input：設置約束;i∈V，隨機初始化xi，0∈并設置zi，0=ei;步長t，t∈[T]。

2：for t=0，1，2，…，T-1 do

3： for i=1，…，n do

4：? 高斯噪聲？濁i，t～N（0，j2）

5：? 變量xi，t被？濁i，t擾動并通過（2）得到y(tǒng)i，t

6：? 傳輸yi，t和zi，t給鄰居j∈Ni，t

7：? 通過（3）更新本地決策xi，t

8：? 通過（4）更新輔助變量zi，t

9： end for

10：end for

11：Output：{xi，T}ni=1

—————————————————————

作為本節(jié)的結(jié)尾，我們給出以下引理來揭示A和變量zii，t的一些重要性質(zhì)。

引理1 對于t≥0時，有：

1）對于i，j∈V，t≥0，存在0<？孜<1，C>0使得[At]ij-≤C？孜t，zii，t-≤C？孜t;

2）對于i∈V，t≥0，存在>0使得-1≤zii，t ≤1。

4 遺憾界分析

在這一節(jié)中，我們研究了一般凸目標函數(shù)的遺憾界。

為了得到期望的遺憾界，存在一個不可避免的挑戰(zhàn)。即隱私與優(yōu)化存在沖突，節(jié)點不傾向于與相鄰節(jié)點交換準確的信息以保護自己的隱私，而優(yōu)化要求節(jié)點自由地共享自己的信息來獲得準確的最優(yōu)解。因此，我們必須在隱私級別和優(yōu)化精度之間建立一個平衡。這個特性是我們的算法與現(xiàn)有的分布式優(yōu)化算法之間最重要的區(qū)別，同時也會給我們的性能分析帶來一些技術困難。

如果每個局部代價函數(shù)fi，t是一般凸函數(shù)，i≥V，t∈[T]，然后我們有下面的定理，揭示了E[Rj（T）/FT]，j≥V的上界在一般凸代價函數(shù)上擁有和O（）相同的數(shù)量級。此外，在步長選擇中使用了一種稱為加倍技巧方案[22]的邊界技術。

定理1[1] 設x*為對在線優(yōu)化問題的進行計算的最優(yōu)解，？濁i，t表示來自高斯分布N（0，j2），？滓t=？駐t/的噪聲，{xi，t}Tt=1為算法生成的決策序列。假設步長的選擇是通過加倍技巧方案，對于q=0，1，2，…，[log2T]，我們設步長為t=，每周期迭代2q次，t=2q，…，2q+1-1。那么，算法1的遺憾會有上界：

E[Rj（T）|FT]≤B? （5）

其中

B=2（+n）||xi，0||+nR+R2

+

+

+（8n+9）G2? （6）

即E[Rj（T）|FT]=O（）。

證明 我們首先考慮在一個固定的已知時間范圍內(nèi)的有固定步長的期望網(wǎng)絡遺憾T′，然后利用加倍技巧方案證明了該定理。

根據(jù)[1]中的（16），我們設t==，t∈[T′]，結(jié)合事實≥1，我們可以得到：

E[fi，t（xj，t）-fi，t（x*）]

≤（2（+n）||xi，0||+nR

+E[||xi，1-x*||2]+H1）? （7）

其中

H1=

+

++（8n+9）G2? （8）

根據(jù)加倍技巧方案，在以2q為迭代次數(shù)的周期中，t=2q，…，2q+1-1，q=0，1，2，…，[log2T]，即每一周期的初始值是前一周期的最終值。從（6）中很顯然可以看出，E[Rj（T′）]的邊界形式為E[Rj（T′）]≤Jq，其中Jq取決于對應周期q的初始條件。那么的直徑界限為R<∞，那么就可以得出結(jié)論，1/n∑E[||xi，t-x*]||2]≤R2，t≥0。從而可以直接消除相鄰周期的依賴關系，在沒一個周期q中，期望遺憾界為J，

J=（2（+n）||xi，0||+nR+R2+H1? （9）

因此，網(wǎng)絡的總期望遺憾數(shù)值可以界定為：

E[Rj（T′）|FT]≤J=J

≤J≤J? （10）

將H1代入到J中會得到（5）中所需的邊界。

5 仿真

我們考慮一個由五個節(jié)點組成的網(wǎng)絡，在權值平衡的無向圖上共同估計一個隨機向量。圖G的拓撲如圖1所示。

在每個時刻t∈[T]，每個傳感器i∈V權衡一個觀測向量zi，t∈R，由于觀測噪聲的存在，具有不確定性和時變特性。假設每個傳感器i具有形式為? hi（）=Hi的線性模型，其中Hi∈R表示觀測矩陣，hi（）=0當且僅當=0m。我們的目標是找到能使得函數(shù)F（）=fi，t（）最小化的的估計值，其中fi，t（）=||zi，t-Hi||，傳感器i在t時刻的觀測向量zi，t =Hi+i，t，其中i，t為觀測噪聲，我們將其假設為白噪聲。需要注意的是，由于建模錯誤和環(huán)境中的不確定性的存在，每個成本函數(shù)會隨著時間變化而變化，事后對時間范圍T內(nèi)的的最佳固定估計是這樣給出的：

=HTiHiHTizi，t? （11）

我們考慮m=1的情況。假設的實際值為=1，這對每個傳感器都不可用。傳感器i在t時刻的觀測值為zi，t=ki，t+i，t，其中隨機變量ki，t和i，t是分別在均勻分布[kmin，kmax]和[min，max]中抽取的。在整個仿真中，我們設置ki，t∈[0，2]，i，t∈[-1，1]，=[-5，5]。在平衡無向圖中設置步長為i，t=1/，i∈V，兩種情況：=0.05，=0.1。結(jié)果如圖2所示，這反映了我們的算法可以實現(xiàn)次線性遺憾，常數(shù)決定了隱私水平和優(yōu)化精度之間的權衡。

最后，我們在圖3中用=0.1平均超過100次獨立試驗來顯示每個傳感器決策變量的軌跡。它可以觀察到傳感器的估計方法的實際值=1的期望。

6 總結(jié)

本文研究了一個具有差分隱私的無投影分布式在線條件梯度優(yōu)化問題，該問題的網(wǎng)絡模型是具有五個節(jié)點的平衡無向圖。針對此問題，提出了一種差分隱私分布式在線條件梯度優(yōu)化算法。特別是采用高斯算法機制來保證個人敏感信息的差異性和私密性。此外，我們推導了一般凸局部代價函數(shù)的期望遺憾界，證明了我們的算法可以實現(xiàn)次線性遺憾作為最優(yōu)理論遺憾。最后，我們通過仿真證明了常數(shù)確定了隱私級別和優(yōu)化精度之間的權衡。

——————————

參考文獻：

〔1〕張玲玲.離散多智能體系統(tǒng)在獨立位移和速度拓撲結(jié)構下的一致性研究[D].2015.

〔2〕邵言劍，陶卿，姜紀遠，et al.一種求解強凸優(yōu)化問題的最優(yōu)隨機算法[J].軟件學報，2014，25（09）：2160-2171.

〔3〕張茸擎.網(wǎng)絡控制系統(tǒng)的時延與調(diào)度算法研究[D].上海交通大學，2007.

〔4〕K. You，R. Tempo，and P. Xie，“Distributed algorithms for robust convex optimization via the scenario approach，” IEEE Trans. Autom. Control，vol. 64，no. 3，pp. 880–895，2019.

〔5〕J. Zhang，K. You，and T. Bas， ar，“Distributed discrete-time optimization in multi-agent networks using only sign of relative state，” IEEE Trans. Autom. Control，2018.

〔6〕J. Xu，S. Zhu，Y. C. Soh，and L. Xie，“A Bregman Splitting Scheme for Distributed Optimization Over Networks，” IEEE Trans. Autom. Control，vol. 63，no. 11，pp. 3809–3824， 2018.

〔7〕J. Xu，S. Zhu，Y. C. Soh，and L. Xie，“Convergence of Asynchronous Distributed Gradient Methods Over Stochastic Networks，” IEEE Trans. Autom. Control，vol. 63，no. 2，pp. 434–448，2018.

〔8〕C. Liu，H. Li，and Y. Shi，“Distributed Subgradient Method for Convex Constrained Optimization： Non-ergodic Conve gence Guarantees，” arXiv preprint arXiv：1809. 06008， 2018.

〔9〕Akbari M，Gharesifard B，Linder L. Individual Regret Bounds for the Distributed Online Alternating Direction Method of Multipliers[J]. IEEE Transactions on Automatic Control，2019，PP（04）：1-1.

〔10〕H. F. Xu，Q. Ling，and A. Ribeiro，“Online learning over a decentralized network through ADMM，” J. Oper. Res. Soc. of China，vol. 3，no. 4，pp. 537–562，2015.

〔11〕D. Yuan，D. W. Ho，and G. P. Jiang，“An adaptive primal-dual subgradient algorithm for online distributed constrained optimization，”IEEE Trans. Cybern.，vol. 99，pp. 1–11， 2017.

〔12〕A. Koppel，F(xiàn). Y. Jakubiec，and A. Ribeiro，“A saddle point algorithm for networked online convex optimization，” IEEE Trans. Signal Proces.，vol. 63，no. 19，pp. 5149–5164，2015.

〔13〕A. Koppel，S. Paternain，C. Richard，and A. Ribeiro，“Decentralized online learning with kernels，” IEEE Trans. Signal Proces.，vol. 66，no.12，pp. 3240–3255，2018.

〔14〕H. Pradhan，A. S. Bedi，A. Koppel，and K. Rajawat，“Exact Nonparametric Decentralized Online Optimization，” In Proc. IEEE Global Conf. Signal and Inform. Proces. （GlobalSIP），pp. 643–647，2018.

〔15〕X. Yi，X. Li，L. Xie，and K. H. Johansson，“Distributed online convex optimization with time-varying coupled inequality constraints，” arXiv preprint arXiv：1903.04277，2019.

〔16〕S. Shahrampour，and A. Jadbabaie，“Distributed online optimization in dynamic environments using mirror descent，” IEEE Trans. Autom. Control，vol. 63，no. 3，pp. 714–725，2018.

〔17〕Xiong Y，Xu J，You K，et al.” Privacy Preserving Distributed Online Optimization over Unbalanced Digraphs via Subgradient Rescaling”[J]. IEEE Transactions on Control of Network Systems，2020，pp（99）：1-1.

〔18〕Wenpeng Zhang， Peilin Zhao， Wenwu Zhu， Steven C. H. Hoi， Tong Zhang. Projection-free Distributed Online Learning in Networks. Association for Computing Machinery，2017，pp：4054-4062.

〔19〕Dud′lk，Miroslav，Malick，J′er？ome，et al. Lifted coordinate descent for learning with trace-norm regularization. In International Conference on Artificial Intelligence and Statistics，pp. 327–336，2012.

〔20〕Hazan， Elad and Luo， Haipeng. Variance-reduced and projection-free stochastic optimization. In International Conference on Machine Learning， pp. 235–243，2016.

〔21〕Hazan，Elad. Introduction to online convex optimization. Foundations and Trends R in Optimization，2（3-4）：157–325，2016.