分布式隨機(jī)方差消減梯度下降算法topkSVRG*

王建飛，亢良伊，劉 杰，葉 丹

1.中國科學(xué)院 軟件研究所 軟件工程技術(shù)研發(fā)中心，北京 100190

2.中國科學(xué)院大學(xué)，北京 100190

1 介紹

在機(jī)器學(xué)習(xí)領(lǐng)域，機(jī)器學(xué)習(xí)問題通常轉(zhuǎn)換成一個(gè)目標(biāo)函數(shù)，然后利用優(yōu)化算法求解目標(biāo)函數(shù)中的參數(shù)，因此優(yōu)化算法在機(jī)器學(xué)習(xí)中具有非常重要的地位。

給定n個(gè)訓(xùn)練樣本，xi表示輸入向量，yi為輸出，(x1,y1),(x2,y2),…,(xn,yn),xi∈Rd,yi∈R ，求解一個(gè)目標(biāo)函數(shù)確保每個(gè)樣本對(duì)應(yīng)輸出與已知輸出誤差最小。利用φ表示目標(biāo)函數(shù)，目標(biāo)函數(shù)表示為：

通常利用標(biāo)準(zhǔn)的梯度下降（gradient descent，GD）進(jìn)行求解，更新公式如式（2）所示：

然而，每一步模型更新，需要計(jì)算所有樣本點(diǎn)的梯度，代價(jià)較大。一個(gè)更加高效的算法是隨機(jī)梯度下降（stochastic gradient descent，SGD）[1]，每次隨機(jī)從數(shù)據(jù)集中選擇一個(gè)樣本點(diǎn)it進(jìn)行梯度更新，即式（3）：

隨后，針對(duì)類似的大規(guī)模分布式機(jī)器學(xué)習(xí)問題，SGD出現(xiàn)了改進(jìn)的Mini-Batch[2]版本。隨機(jī)選取m個(gè)樣本進(jìn)行并行或者分布式計(jì)算，(x1,y1),(x2,y2),…,(xm,ym),xi∈Rd,yi∈R ，其中 m 代表批（batch）的大小，然后使用式（4）更新模型：

理論分析和實(shí)踐經(jīng)驗(yàn)表明，SGD是大規(guī)模機(jī)器學(xué)習(xí)問題比較好的求解方法，具有廣泛應(yīng)用。然而SGD在穩(wěn)定性方面還有所欠缺，容易受噪聲梯度的影響，在固定學(xué)習(xí)率的情況下，很難達(dá)到某一最優(yōu)解，在學(xué)習(xí)率逐漸減小的情況下，只能達(dá)到次線性的收斂速率。

針對(duì)SGD受噪聲干擾的問題，文獻(xiàn)[3]提出了隨機(jī)方差消減梯度算法（stochastic variance reduction gradient，SVRG），核心思想是利用全局的梯度信息對(duì)每次用于模型更新的梯度進(jìn)行修正。理論分析可以證明SVRG具有線性收斂速率。因?yàn)镾VRG是單機(jī)串行算法，難以應(yīng)用到大數(shù)據(jù)環(huán)境。已有的分布式SVRG算法（distributed SVRG，DSVRG）[4]采用循環(huán)節(jié)點(diǎn)更新策略，并不是完全的并行化，SCOPE（scalable composite optimization for learning）[5]理論證明了線性收斂性，但是存在較難調(diào)優(yōu)的參數(shù)。因此，本文對(duì)原始SVRG的模型更新進(jìn)行了改進(jìn)，提出一種新的算法topkSVRG（top-k model average based SVRG）。其改進(jìn)在于：主節(jié)點(diǎn)維護(hù)一個(gè)全局模型，從節(jié)點(diǎn)基于本地?cái)?shù)據(jù)進(jìn)行局部模型更新，每輪迭代時(shí)，選擇與當(dāng)前全局模型距離最小的k個(gè)局部模型進(jìn)行平均來更新全局模型，參數(shù)k調(diào)大可以提高收斂速度，調(diào)小k可以保證收斂。topkSVRG的動(dòng)機(jī)也是通過選擇與全局模型最近的局部模型，來減少噪音的影響。本文理論分析了算法的線性收斂性，基于Spark進(jìn)行算法實(shí)現(xiàn)，通過與Mini-Batch SGD、CoCoA、Splash及相關(guān)算法的實(shí)驗(yàn)比較，topkSVRG可以在高精度要求下更快地收斂。topkSVRG魯棒性比較好，在稀疏數(shù)據(jù)集、稠密數(shù)據(jù)集上都可以取得不錯(cuò)的加速效果。

本文主要貢獻(xiàn)有如下兩點(diǎn)：

（1）提出了一種新的分布式SVRG實(shí)現(xiàn)算法，通過k個(gè)最近似局部模型來更新全局模型，從而加快收斂速度，并進(jìn)行了基本的理論分析。

（2）基于Spark平臺(tái)進(jìn)行了算法的分布式實(shí)現(xiàn)，與Mini-Batch SGD、CoCoA、Splash，以及Mini-Batch SGD結(jié)合Adadelta、Adagrad、Adam和Momentum等算法進(jìn)行了評(píng)測對(duì)比，證明了topkSVRG在高精度要求下收斂速度較快，這與原始SVRG的實(shí)驗(yàn)效果一致。

本文組織結(jié)構(gòu)如下：第2章介紹了主流的分布式梯度下降算法；第3章提出了topkSVRG算法，并且理論分析了該算法的線性收斂性；第4章給出了實(shí)驗(yàn)評(píng)測方案和結(jié)果；第5章進(jìn)行了總結(jié)和展望。

2 相關(guān)工作

梯度下降法是應(yīng)用最廣泛的優(yōu)化方法，有大量相關(guān)工作，本文主要介紹三類：（1）以Mini-Batch SGD為基礎(chǔ)的相關(guān)優(yōu)化；（2）分布式SVRG的相關(guān)工作；（3）其他分布式SGD的重要工作。本文面向凸優(yōu)化問題，因此不介紹深度學(xué)習(xí)相關(guān)優(yōu)化算法。

分布式環(huán)境下目前主流的方法都是基于Mini-Batch的思想，Spark目前實(shí)現(xiàn)了Mini-Batch SGD算法，用于支持MLLib[2]大量模型求解，但是該算法存在收斂速度慢，穩(wěn)定性欠缺，難以確定學(xué)習(xí)率等問題[6]。于是出現(xiàn)了自適應(yīng)學(xué)習(xí)率的Momentum[7]、Adagrad[8]、Adadelta[9]、Adam[10]等優(yōu)化方法，這些方法不改變Mini-Batch SGD的執(zhí)行邏輯，比較容易進(jìn)行分布式實(shí)現(xiàn)。

隨機(jī)方差削減梯度（SVRG）[3]是噪聲梯度去除方法中的典型方法。這個(gè)方法的整體思路是：為了提高梯度計(jì)算的準(zhǔn)確性，利用全局的梯度信息對(duì)每次用于模型更新的梯度進(jìn)行修正。理論分析和實(shí)踐經(jīng)驗(yàn)表明，串行SVRG可以取得目前幾乎最好的單機(jī)收斂速度。隨后，諸多學(xué)者研究分布式模式下的SVRG方法。Jason等人提出了DSVRG[4]，證明了在數(shù)據(jù)隨機(jī)劃分的條件下，相比其他一階優(yōu)化方法，可以取得最優(yōu)的運(yùn)行時(shí)間、最少的通信次數(shù)等。但是DSVRG存在如下問題：該算法是單機(jī)多線程模式，每個(gè)線程代表一個(gè)計(jì)算節(jié)點(diǎn)，通過節(jié)點(diǎn)之間相互傳遞消息，實(shí)現(xiàn)參數(shù)的更新。本質(zhì)上來講，這種循環(huán)更新模式是串行的，當(dāng)一個(gè)機(jī)器更新模型的時(shí)候，其他機(jī)器會(huì)存在等待的情況，不是真正意義上的分布式并行。針對(duì)該問題，Zhao等人提出了SCOPE[5]，其是對(duì)SVRG的分布式實(shí)現(xiàn)，理論證明了該方法具有線性的收斂速度，并且通過實(shí)驗(yàn)表明，在很多數(shù)據(jù)集上SCOPE可以取得明顯優(yōu)于其他分布式SGD的收斂速率。但是在SCOPE中，收斂保證因子C難以確定（C的取值范圍太大），如果設(shè)置太小，會(huì)降低收斂速率，如果設(shè)置太大，可能導(dǎo)致不收斂。

Jaggi等人提出了CoCoA[11]，CoCoA是一種分布式坐標(biāo)下降方法，該方法在梯度計(jì)算過程中會(huì)對(duì)模型進(jìn)行本地更新，從而使得最后每個(gè)計(jì)算節(jié)點(diǎn)計(jì)算出的模型更加準(zhǔn)確，然后進(jìn)行全局的聚合操作，有效地減少了全局的通信次數(shù)。Zhang等人提出了Splash[12]。Splash的核心思想是：首先將集群中的計(jì)算單元分成K組，然后每個(gè)計(jì)算處理單元使用本地?cái)?shù)據(jù)計(jì)算本地模型，K個(gè)組分別合并組內(nèi)的模型，通過交叉驗(yàn)證法選擇K組內(nèi)最好的模型，從而獲得更為精準(zhǔn)的計(jì)算結(jié)果。

3 topkSVRG算法

本章首先簡單介紹SVRG原始算法，然后介紹本文提出的topkSVRG算法。

3.1 串行SVRG

為了降低梯度噪聲，SVRG通過全局的梯度進(jìn)行修正。SVRG中，每個(gè)計(jì)算節(jié)點(diǎn)使用式（5）、（6）進(jìn)行更新：

其中，w∈Rd表示模型參數(shù)；η表示更新步長；?Rn(wt)是使用上一輪的模型wt計(jì)算出的平均梯度；?fij(wt)表示函數(shù) f在樣本點(diǎn)ij的梯度；?fij(wt)-?Rn(wt)是梯度的偏差是經(jīng)過修正的梯度，是無偏的，使用更新模型算法偽代碼如算法1所示。

算法1SVRG(T,m,η)

從wt到wt+1需要2m+n次梯度計(jì)算，其中步驟3執(zhí)行n次，步驟7執(zhí)行2m次。因此，每輪迭代需要2m+n次梯度計(jì)算，SVRG的單次迭代代價(jià)比SGD（m次梯度計(jì)算）要大。實(shí)踐經(jīng)驗(yàn)表明：在大多數(shù)應(yīng)用上，SVRG比SGD收斂速度更快，其具有線性收斂率[3]，尤其是需要大量數(shù)據(jù)集遍歷（epochs）的時(shí)候。此外，算法1步驟1對(duì)w1進(jìn)行初始化，對(duì)于凸優(yōu)化問題，可以通過運(yùn)行1輪SGD確定；對(duì)于非凸優(yōu)化問題，可以運(yùn)行大約10輪SGD確定。

3.2 分布式SVRG

分布式實(shí)現(xiàn)SVRG的主要目的是每輪迭代，由多個(gè)節(jié)點(diǎn)通過Mini-Batch的方式來計(jì)算梯度，更新局部模型。主要難點(diǎn)在于主節(jié)點(diǎn)每輪更新模型的時(shí)候如何在有效利用每個(gè)計(jì)算節(jié)點(diǎn)計(jì)算結(jié)果的同時(shí)，又能保證算法的收斂性。如果直接對(duì)從節(jié)點(diǎn)模型進(jìn)行平均可能導(dǎo)致不收斂；SCOPE[5]通過增加一個(gè)收斂保證因子來確定收斂性，但是參數(shù)較難確定。本文提出一種直觀的方法，主節(jié)點(diǎn)維護(hù)一個(gè)全局模型，從節(jié)點(diǎn)基于本地?cái)?shù)據(jù)進(jìn)行局部模型更新，每輪迭代時(shí)，選擇與當(dāng)前全局模型距離最小的k個(gè)局部模型進(jìn)行平均來更新全局模型，參數(shù)k調(diào)大可以提高收斂速度，調(diào)小k可以保證收斂。該算法的動(dòng)機(jī)也是通過選擇與全局模型最近的局部模型，來減少噪音的影響。因此算法命名為topkSVRG。topkSVRG架構(gòu)如圖1。

算法偽代碼如算法2所示。topkSVRG主要包括4階段：

（1）計(jì)算平均梯度，采用Spark實(shí)現(xiàn)分布式計(jì)算，如步驟3所示；

（2）多個(gè)計(jì)算節(jié)點(diǎn)并行地按照串行SVRG的模型更新策略更新模型，如步驟4～步驟11所示；

Fig.1 Framework of topkSVRG圖1 topkSVRG架構(gòu)圖

（4）平均這k個(gè)模型,從而獲得最終的模型wt+1，如步驟16所示。

算法2分布式SVRG(T,K,k,h,r,η)

3.3 算法實(shí)現(xiàn)

本文提出的topkSVRG基于整體同步并行計(jì)算模型（bulk synchronization parallel computing model，BSP）[13]，適合目前主流的Spark平臺(tái)。通過Spark RDD[14]（resilient distributed datasets）操作，可以方便高效地實(shí)現(xiàn)上面的每一個(gè)過程，具體說明如下：

（1）通過Spark RDD的map、aggregate操作實(shí)現(xiàn)平均梯度的計(jì)算。

（2）通過Spark RDD的mapPartition操作實(shí)現(xiàn)各個(gè)計(jì)算節(jié)點(diǎn)的并行計(jì)算。

（3）主節(jié)點(diǎn)通過Spark RDD的takeOrdered操作獲取k個(gè)與上一輪模型最接近的模型。

（4）主節(jié)點(diǎn)通過Spark RDD的average操作對(duì)k個(gè)模型進(jìn)行平均。

具體實(shí)現(xiàn)參見實(shí)驗(yàn)部分所示地址http://github.com/codlife/Ssgd。

3.4 算法收斂性分析

本文提出一種“top k最鄰近模型平均策略”，即主節(jié)點(diǎn)聚合每個(gè)計(jì)算節(jié)點(diǎn)模型的時(shí)候，選取k個(gè)與當(dāng)前模型最接近的模型，對(duì)這k個(gè)模型進(jìn)行平均。該策略是算法收斂性證明的關(guān)鍵。算法收斂性分析如下：單機(jī)串行SVRG每一輪迭代有式（7）成立。其中L為常數(shù),w*是模型的最優(yōu)解，因此串行SVRG具有線性收斂速度[6]。

本文提出的topkSVRG中每個(gè)計(jì)算節(jié)點(diǎn)同樣有式（8）成立。其中 p表示第p個(gè)計(jì)算節(jié)點(diǎn)，K表示節(jié)點(diǎn)個(gè)數(shù)。

假設(shè)各個(gè)wpt都比較接近，通過平行四邊形法則可以證明，對(duì)于任意兩個(gè) wpt、wit、wjt有式（9）、（10）成立：

由式（8）可以得到式（11）成立：

由式（9）、（10）、（11）可以得到式（12）成立：

式（12）表明：當(dāng)每個(gè)計(jì)算節(jié)點(diǎn)的計(jì)算結(jié)果wpt比較接近的時(shí)候，直接對(duì)模型進(jìn)行平均可以獲得和單機(jī)串行SVRG相同的線性收斂速率。

關(guān)于參數(shù)k，在初始數(shù)據(jù)隨機(jī)劃分的情況下，將k設(shè)置為計(jì)算節(jié)點(diǎn)的個(gè)數(shù)能夠取得較快的收斂速度；通過縮小k，可以保證收斂。通常建議將k設(shè)置為Round（0.9×K）、Round（0.8×K）、Round（0.6×K）、Round（0.5×K）（Round為下取整操作）等幾個(gè)常見的值。

4 實(shí)驗(yàn)評(píng)測

針對(duì)求解L2正則化的邏輯回歸（logistic regression，LR）[15]的場景，對(duì)本文提出的方法和一些實(shí)驗(yàn)基準(zhǔn)（Baseline）進(jìn)行評(píng)測。目標(biāo)函數(shù)如下所示：

Table 1 Dataset表1 數(shù)據(jù)集

其中，學(xué)習(xí)率η設(shè)置為（t是迭代輪數(shù)）；采樣因子r設(shè)置為0.1；計(jì)算節(jié)點(diǎn)內(nèi)循環(huán)次數(shù)h設(shè)置為1 000。

對(duì)于參數(shù)設(shè)置：本文的實(shí)驗(yàn)超參數(shù)λ設(shè)置為10-4；參數(shù)k，實(shí)驗(yàn)1、實(shí)驗(yàn)3數(shù)據(jù)集都是稀疏數(shù)據(jù)集，k設(shè)置為Round（0.8×K），實(shí)驗(yàn)2數(shù)據(jù)集是稠密數(shù)據(jù)集，k設(shè)置為Round（0.9×K），實(shí)驗(yàn)4測試數(shù)據(jù)集較多，k設(shè)置為Round（0.8×K），以獲得一個(gè)比較穩(wěn)定的收斂過程。

4.1 數(shù)據(jù)集

本文使用多個(gè)數(shù)據(jù)集進(jìn)行測評(píng)，從LibSVM網(wǎng)站獲取，選取具有代表性的數(shù)據(jù)集，實(shí)驗(yàn)數(shù)據(jù)集如表1所示。

4.2 實(shí)驗(yàn)環(huán)境和實(shí)驗(yàn)基準(zhǔn)

使用具有10個(gè)節(jié)點(diǎn)的Spark集群，Spark采用2.0版本。集群配置如表2所示。

Table 2 Machine configuration表2 機(jī)器配置

實(shí)現(xiàn)了本文提出的topkSVRG和工業(yè)界廣泛使用的Mini-Batch SGD、Mini-Batch SGD with Adadelta、Adagrad、Adam、Momentum。同時(shí)將上述算法和CoCoA、Splash等算法進(jìn)行對(duì)比。

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

實(shí)驗(yàn)結(jié)果如圖2～圖4所示，圖中的縱軸為對(duì)模型精度取對(duì)數(shù)lg。

實(shí)驗(yàn)1基于Rcv1數(shù)據(jù)集（高維，稀疏，N>>d），實(shí)驗(yàn)結(jié)果如圖2。通過該實(shí)驗(yàn)可以發(fā)現(xiàn)，在高維稀疏樣本數(shù)遠(yuǎn)遠(yuǎn)大于特征維數(shù)的數(shù)據(jù)集上有以下特點(diǎn)：

Fig.2 Experiment on Rcv1 dataset圖2 數(shù)據(jù)集Rcv1上的實(shí)驗(yàn)

（1）topkSVRG收斂速率相比其他分布式SGD加速明顯，并且可以達(dá)到較高的收斂精度。這是由于在稀疏數(shù)據(jù)集上，其他分布式SGD更易受梯度噪聲的影響。

（2）Spark Mini-Batch SGD穩(wěn)定性欠缺。

實(shí)驗(yàn)2基于Susy數(shù)據(jù)集（低維，稠密，N>>d），實(shí)驗(yàn)結(jié)果如圖3。通過該實(shí)驗(yàn)可以發(fā)現(xiàn)，在低維稠密樣本數(shù)遠(yuǎn)遠(yuǎn)多于特征維數(shù)的數(shù)據(jù)集上有以下特點(diǎn)：

Fig.3 Experiment on Susy dataset圖3 數(shù)據(jù)集Susy上的實(shí)驗(yàn)

Table 3 AUC on many datasets within 100 iterations表3 在大量數(shù)據(jù)集上100輪迭代時(shí)的AUC

（1）topkSVRG收斂速率略優(yōu)于Spark Mini-Batch SGD，加速相對(duì)較差。

（2）Spark Mini-Batch SGD穩(wěn)定性欠缺，并且收斂速度較慢。

（3）CoCoA、Splash等算法很難達(dá)到較高的精度。

實(shí)驗(yàn)3基于Real-sim數(shù)據(jù)集（低維，稀疏，N>d），實(shí)驗(yàn)結(jié)果如圖4。通過該實(shí)驗(yàn)可以發(fā)現(xiàn)，在低維稀疏樣本數(shù)多于特征維數(shù)的數(shù)據(jù)集上有以下特點(diǎn)：

（1）topkSVRG收斂速率相比Spark Mini-Batch SGD加速明顯，尤其是在高精度范圍內(nèi)。

（2）Spark Mini-Batch SGD穩(wěn)定性欠缺，收斂速度較慢。

（3）CoCoA、Splash等算法很難達(dá)到較高精度。

Fig.4 Experiment on Real-sim dataset圖4 數(shù)據(jù)集Real-sim上的實(shí)驗(yàn)

實(shí)驗(yàn)4將本文提出的topkSVRG和Spark Mini-Batch SGD with Adadelta/Adagrad/Adam/Momentum等在不同數(shù)據(jù)集上迭代100輪時(shí)的AUC值進(jìn)行對(duì)比，結(jié)果如表3所示。可以發(fā)現(xiàn)，在各種類型數(shù)據(jù)集上，相同迭代次數(shù)，topkSVRG性能最穩(wěn)定。

4.4 實(shí)驗(yàn)總結(jié)

通過實(shí)驗(yàn)1～實(shí)驗(yàn)3可以發(fā)現(xiàn)分布式SVRG相比Spark Mini-Batch SGD結(jié)合Adadelta、Adagrad、Adam和Momentum等算法，以及CoCoA、Splash等算法在較高收斂精度要求下，收斂加速效果明顯。通過實(shí)驗(yàn)4可以發(fā)現(xiàn)topkSVRG是一個(gè)相對(duì)穩(wěn)定的算法，模型準(zhǔn)確率相對(duì)較高。

5 結(jié)束語

采用top-k局部模型平均來更新全局模型的思想，本文設(shè)計(jì)實(shí)現(xiàn)了分布式SVRG算法topkSVRG，用于求解大規(guī)模分布式機(jī)器學(xué)習(xí)最優(yōu)化問題；基于Spark平臺(tái)進(jìn)行實(shí)現(xiàn)，并理論分析了topkSVRG的線性收斂性；實(shí)驗(yàn)表明topkSVRG優(yōu)于目前Spark支持的Mini-Batch SGD算法，尤其是在高精度范圍內(nèi)可以取得明顯的加速效果。此外，topkSVRG魯棒性比較好,在稀疏數(shù)據(jù)集、稠密數(shù)據(jù)集上都可以取得不錯(cuò)的加速效果。

對(duì)于訓(xùn)練樣本小于特征維數(shù)的情況(N≤d)，topkSVRG還存在一些不足，相比Spark Mini-Batch沒有太大優(yōu)勢。下一步針對(duì)樣本數(shù)少于特征維數(shù)的情況進(jìn)行算法優(yōu)化，并進(jìn)一步完善理論證明。此外，將topkSVRG應(yīng)用于深度學(xué)習(xí)場景并進(jìn)行優(yōu)化。