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

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

1.中國科學院 軟件研究所 軟件工程技術研發中心，北京 100190

2.中國科學院大學，北京 100190

1 介紹

在機器學習領域，機器學習問題通常轉換成一個目標函數，然后利用優化算法求解目標函數中的參數，因此優化算法在機器學習中具有非常重要的地位。

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

通常利用標準的梯度下降（gradient descent，GD）進行求解，更新公式如式（2）所示：

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

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

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

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

本文主要貢獻有如下兩點：

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

（2）基于Spark平臺進行了算法的分布式實現，與Mini-Batch SGD、CoCoA、Splash，以及Mini-Batch SGD結合Adadelta、Adagrad、Adam和Momentum等算法進行了評測對比，證明了topkSVRG在高精度要求下收斂速度較快，這與原始SVRG的實驗效果一致。

本文組織結構如下：第2章介紹了主流的分布式梯度下降算法；第3章提出了topkSVRG算法，并且理論分析了該算法的線性收斂性；第4章給出了實驗評測方案和結果；第5章進行了總結和展望。

2 相關工作

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

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

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

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

3 topkSVRG算法

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

3.1 串行SVRG

為了降低梯度噪聲，SVRG通過全局的梯度進行修正。SVRG中，每個計算節點使用式（5）、（6）進行更新：

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

算法1SVRG(T,m,η)

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

3.2 分布式SVRG

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

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

（1）計算平均梯度，采用Spark實現分布式計算，如步驟3所示；

（2）多個計算節點并行地按照串行SVRG的模型更新策略更新模型，如步驟4～步驟11所示；

Fig.1 Framework of topkSVRG圖1 topkSVRG架構圖

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

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

3.3 算法實現

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

（1）通過Spark RDD的map、aggregate操作實現平均梯度的計算。

（2）通過Spark RDD的mapPartition操作實現各個計算節點的并行計算。

（3）主節點通過Spark RDD的takeOrdered操作獲取k個與上一輪模型最接近的模型。

（4）主節點通過Spark RDD的average操作對k個模型進行平均。

具體實現參見實驗部分所示地址http://github.com/codlife/Ssgd。

3.4 算法收斂性分析

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

本文提出的topkSVRG中每個計算節點同樣有式（8）成立。其中 p表示第p個計算節點，K表示節點個數。

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

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

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

式（12）表明：當每個計算節點的計算結果wpt比較接近的時候，直接對模型進行平均可以獲得和單機串行SVRG相同的線性收斂速率。

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

4 實驗評測

針對求解L2正則化的邏輯回歸（logistic regression，LR）[15]的場景，對本文提出的方法和一些實驗基準（Baseline）進行評測。目標函數如下所示：

Table 1 Dataset表1 數據集

其中，學習率η設置為（t是迭代輪數）；采樣因子r設置為0.1；計算節點內循環次數h設置為1 000。

對于參數設置：本文的實驗超參數λ設置為10-4；參數k，實驗1、實驗3數據集都是稀疏數據集，k設置為Round（0.8×K），實驗2數據集是稠密數據集，k設置為Round（0.9×K），實驗4測試數據集較多，k設置為Round（0.8×K），以獲得一個比較穩定的收斂過程。

4.1 數據集

本文使用多個數據集進行測評，從LibSVM網站獲取，選取具有代表性的數據集，實驗數據集如表1所示。

4.2 實驗環境和實驗基準

使用具有10個節點的Spark集群，Spark采用2.0版本。集群配置如表2所示。

Table 2 Machine configuration表2 機器配置

實現了本文提出的topkSVRG和工業界廣泛使用的Mini-Batch SGD、Mini-Batch SGD with Adadelta、Adagrad、Adam、Momentum。同時將上述算法和CoCoA、Splash等算法進行對比。

4.3 實驗結果

實驗結果如圖2～圖4所示，圖中的縱軸為對模型精度取對數lg。

實驗1基于Rcv1數據集（高維，稀疏，N>>d），實驗結果如圖2。通過該實驗可以發現，在高維稀疏樣本數遠遠大于特征維數的數據集上有以下特點：

Fig.2 Experiment on Rcv1 dataset圖2 數據集Rcv1上的實驗

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

（2）Spark Mini-Batch SGD穩定性欠缺。

實驗2基于Susy數據集（低維，稠密，N>>d），實驗結果如圖3。通過該實驗可以發現，在低維稠密樣本數遠遠多于特征維數的數據集上有以下特點：

Fig.3 Experiment on Susy dataset圖3 數據集Susy上的實驗

Table 3 AUC on many datasets within 100 iterations表3 在大量數據集上100輪迭代時的AUC

（1）topkSVRG收斂速率略優于Spark Mini-Batch SGD，加速相對較差。

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

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

實驗3基于Real-sim數據集（低維，稀疏，N>d），實驗結果如圖4。通過該實驗可以發現，在低維稀疏樣本數多于特征維數的數據集上有以下特點：

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

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

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

Fig.4 Experiment on Real-sim dataset圖4 數據集Real-sim上的實驗

實驗4將本文提出的topkSVRG和Spark Mini-Batch SGD with Adadelta/Adagrad/Adam/Momentum等在不同數據集上迭代100輪時的AUC值進行對比，結果如表3所示。可以發現，在各種類型數據集上，相同迭代次數，topkSVRG性能最穩定。

4.4 實驗總結

通過實驗1～實驗3可以發現分布式SVRG相比Spark Mini-Batch SGD結合Adadelta、Adagrad、Adam和Momentum等算法，以及CoCoA、Splash等算法在較高收斂精度要求下，收斂加速效果明顯。通過實驗4可以發現topkSVRG是一個相對穩定的算法，模型準確率相對較高。

5 結束語

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

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