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

張宇衡，李德權(quán)，李蘇木

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

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

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

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

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

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

1.1 網(wǎng)絡(luò)拓?fù)?/h3>

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

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

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

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

2.1 基本假設(shè)

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

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

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

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

2.2 DFWAdam算法

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

算法1DFWAdam算法

3 收斂性分析

4 實(shí)驗(yàn)與結(jié)果

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

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

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

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

5 總結(jié)

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