基于條件梯度的Adam分布式在線優(yōu)化算法

張宇衡，李德權，李蘇木

（安徽理工大學 數(shù)學與大數(shù)據學院，安徽 淮南 232001）

近年來，分布式優(yōu)化在機器學習中的使用受到了較多關注。許多經典問題本質上是分布式優(yōu)化問題，如數(shù)據管理問題、分布式學習問題、資源分配問題等[1]，其主要思想是將大型優(yōu)化問題分解為更小的、易于處理的子問題，這些子問題由一組具有空間分布特征的節(jié)點，通過與其鄰近節(jié)點相互通信耦合成網絡，從而協(xié)同合作來解決優(yōu)化問題。因此，分布式優(yōu)化算法具有網絡規(guī)模的可展性、網絡拓撲的魯棒性等優(yōu)點，并保護了自主決策者的數(shù)據隱私。目前流行的分布式算法有分布式次梯度法[2-3]、對偶平均法[4]等。

分布式優(yōu)化方法通常假設有一個靜態(tài)的網絡目標函數(shù)，其要求收集網絡中所有節(jié)點的數(shù)據后再進行決策優(yōu)化，這種離線的學習方法會帶來高昂的通信代價。而網絡系統(tǒng)通常處于動態(tài)變化和不確定的環(huán)境中，目標函數(shù)可能是時變的。尤其在線學習情形下，目標函數(shù)可以表述為學習者與對手間的重復博弈，學習者使用實時數(shù)據流來更新決策，對手則向學習者揭示損失函數(shù)，因而目標函數(shù)通常是時變的，其本質也是隨機優(yōu)化方法的一種擴展。這種在線學習或優(yōu)化處理的優(yōu)點，是可以利用任意改變的代價函數(shù)來表示網絡系統(tǒng)的不確定性，同時也方便對節(jié)點的動態(tài)數(shù)據流進行實時處理[5-6]。在線優(yōu)化算法的性能通常用Regret界來表達。根據研究問題的不同，目前提出了兩類Regret界的概念。例如，如果估計的參數(shù)為固定序列，且所有損失函數(shù)都是事后才知道，一般使用靜態(tài)Regret界來衡量在線優(yōu)化算法與離線優(yōu)化器所造成的額外損失。而若感興趣的參數(shù)是時變的，動態(tài)Regret界則是一個更為合適的度量，可以衡量瞬時損失與最小損失之間的累積差[7]。

受經典的隨機梯度下降算法[8]啟發(fā)，Diederik等提出了一種可以代替?zhèn)鹘y(tǒng)隨機梯度下降過程的一階優(yōu)化算法（Adam）[9]，該算法通過計算梯度的一階矩估計和二階矩估計，為不同的參數(shù)設計獨立的自適應學習率。Adam算法不僅獲得了AdamGrad[10]和RMSProp[11]算法的優(yōu)點，而且能夠很好地解決稀疏梯度和噪聲問題。同時Adam算法的調參相對簡單，因此其在深度學習領域內十分流行，已有許多成功應用。以時變目標函數(shù)為特征的分布式優(yōu)化問題也得到了廣泛的研究，DAdam[12]算法將Adam算法擴展到分布式在線優(yōu)化中，分別對有約束的凸函數(shù)和非凸函數(shù)進行了收斂性分析。文獻[13]提出了基于梯度跟蹤的Adam分布式算法，主要研究無約束的在線優(yōu)化問題，并給出了動態(tài)Regret界的收斂性分析。

條件梯度算法在處理大規(guī)模機器學習問題上效率較高，近年來引起了大家的關注。條件梯度算法（Frank-Wolfe）主要用于解決一般的約束優(yōu)化問題。分布式在線學習環(huán)境中，文獻[14]提出分布式在線條件梯度算法，利用簡單的線性優(yōu)化步驟，避免了代價昂貴的投影運算問題。文獻[15]提出的FWAdam算法主要考慮集中式情形下的在線約束問題，優(yōu)點是將Adam算法與Frank-Wolfe算法相結合來求解帶約束的優(yōu)化問題常見的代價昂貴的投影操作問題，實驗結果顯示是可行的。

1 分布式在線凸優(yōu)化問題

1.1 網絡拓撲

在分布式計算框架下，網絡不需要任何中央協(xié)調器，只需各節(jié)點通過局部通信來求解帶約束的分布式在線優(yōu)化問題。網絡節(jié)點間交互信息可建模成圖，通過鄰接矩陣或者Laplacian矩陣來刻畫該網絡拓撲。通常使用加權圖G=(V,E,W)表示網絡，V={1,2,3,…,N}表示節(jié)點集合，E=V×V表示網絡中所有無向邊的集合，W∈RN×N表示圖的權重鄰接矩陣，wij表示權重矩陣W第i行、第j列的元素。節(jié)點i的鄰近節(jié)點用Ni={j∈V|(j,i)∈E}表示。若矩陣W為雙隨機矩陣，其特征值為0 ≤σn(W)≤σn-1(W) ≤σn-2(W)≤…≤σ2(W)≤1。文獻[4]表明算法收斂速度依賴于刻畫網絡拓撲的雙隨機矩陣W的第二大奇異值σ2(W)，由此定義網絡譜間隙1-σ2(W)。

1.2 分布式在線優(yōu)化

在分布式在線優(yōu)化問題中，在迭代時刻t，以學習者i產生決策xi,t∈κ作為局部估計，提交決策后，學習者可觀測到對手返回的fi,t:κ→R，并且每個學習者i僅知道其自身的fi,t。分布式在線優(yōu)化的目標是生成一系列決策xi,t使得所有代價函數(shù)之和最小，即

2 Frank-Wolfe Adam分布式在線算法

2.1 基本假設

定義1對任意x,y∈κ,α∈[0,1]，函數(shù)f:κ→R 是凸函數(shù)，需滿足f(αx+(1-α)y)≤αf(x)+(1-α)f(y)。

定義2對任意x,y∈κ,函數(shù)f:κ→R若滿足

假設1局部損失函數(shù)fi,t對于L2范數(shù)是Lipschitz連續(xù)的，即存在一個正常數(shù)L，有

假設2設D∞為約束可行集κ的直徑上界，即對任意的x,y∈κ，有：‖x-y‖ ≤D∞。

2.2 DFWAdam算法

分布式優(yōu)化相對于集中式優(yōu)化的優(yōu)點是提供了一個靈活解決問題的框架。在該框架下，只需要計算各個節(jié)點的損失函數(shù)，通過節(jié)點間相互信息通信來解決最小化全局目標函數(shù)，方便對海量數(shù)據進行分布式儲存和計算。本文主要將文獻[15]提出的基于Frank-Wolfe的Adam集中式在線算法拓展到分布式的情形，使用加權平均的方法更新梯度，提出了一種新的基于Frank-Wolfe的Adam分布式在線算法來解決問題（1）。算法1給出了DFWAdam算法的具體步驟：首先采用加權平均的方法來更新局部損失函數(shù)的梯度，該方案通過和鄰居節(jié)點交互信息得到，具體實現(xiàn)見第14行；第8-10行表示更新得到梯度的一階矩估計和二階矩估計；然后定義一個新的函數(shù)，使用Frank-Wolfe避免投影操作，最后輸出更新的決策點xi,t+1，實現(xiàn)步驟見算法1第11-13行。

算法1DFWAdam算法

3 收斂性分析

4 實驗與結果

本文分別在合成數(shù)據集和真實數(shù)據集上進行了仿真實驗，并通過和一些先進的算法比較來評估DF‐WAdam算法的性能。在SGDLibrary[17]數(shù)據集Mushrooms和MNIST上進行實驗，使用支持向量機（SVM）來解決二值分類問題；利用卷積神經網絡（CNN）來解決多元分類問題。然后使用Metropolis constant edge權重矩陣W，在合成數(shù)據集和真實數(shù)據集中隨機生成N=10個節(jié)點的連通網絡，連通性比為0.5。

使用SVM來解決二值分類問題，訓練集D={(x1,y1),(x2,y2),(x3,y3),…,(xm,ym)}，標簽yi∈{-1,1}，則SVM的損失函數(shù)為

合成數(shù)據集和真實數(shù)據集的數(shù)值結果圖1所示?？梢钥闯?，該算法的收斂速度優(yōu)于其他算法。這說明利用簡單的線性優(yōu)化步驟來避免算法所需要的昂貴投影操作是可行的。在DAdam算法上運用Frank-Wolfe算法來避免代價昂貴的投影操作，實驗結果令人滿意。并且本文提出的算法對局部函數(shù)的梯度進行了加權平均，達到了加速效果。

圖1 不同算法在數(shù)據集上10個epoch的收斂性。（a）Mushrooms；（b）MNIST

5 總結

針對分布式網絡中實時更新數(shù)據流進行決策這一實際問題，本文提出了基于Frank-Wolfe的Adam分布式在線優(yōu)化算法，理論分析表明DFWAdam算法具有O(T3/4)的Regret界。數(shù)值實驗結果進一步顯示DFWAdam算法具有較好的收斂性能。實際網絡通常是時變、有向的，因此下一步的研究將把本文所提算法推廣到時變有向網絡。