AdaSVRG：自適應學習率加速SVRG

吉 夢，何清龍

貴州大學 數學與統計學院，貴陽550025

理論上，深度學習問題可轉化為求解如下數學中的一個有限和目標函數的最小化問題：

其中，ψi(·)表示第i個樣本的損失函數（成本函數），ω表示可學習參數，n表示樣本總量（通常n很大）。在深度學習問題中，基于一階梯度信息的隨機梯度法是求解問題（1）常用方法[1-8]。在基于一階梯度信息的優化方法中，全梯度下降法（full gradient descent method，FG）是一種特殊的學習方法，其在每次迭代過程中利用全部樣本的梯度信息進行參數更新[9]，參數更新方式為：

其中，t表示迭代步數，αt表示第t步迭代的學習率，?表示梯度算子。FG 充分利用全部樣本進行梯度估計，因此可以獲得較好的下降方向，能夠達到線性收斂速率[10-11]。然而，當訓練樣本過大時，FG 需要對所有樣本進行梯度計算才能進行參數更新，因此，其計算量較大，阻礙了其在大規模學習中的應用[12-13]。此外，在深度學習任務中，樣本數據常常具有冗余性，降低了FG的計算效率。

隨機梯度下降法（stochastic gradient descent method，SGD）在每次迭代過程中只需計算一個樣本的梯度[14]。因此，其每次迭代的計算量相對較小，其迭代格式為：

其中，it表示第t步迭代從{1,2,…,n}中隨機選取的一個樣本。SGD每次迭代只計算一個訓練樣本的梯度，大大降低了每次迭代的計算量。SGD 能快速收斂到一個可接受的解，但若想要得到更精確的解則需要更長的訓練時間[15]。當部分樣本數據存在較強的噪音時，由于SGD選取樣本的隨機性，導致SGD穩定性差、計算效率低。

小批量隨機梯度下降法[16]（mini-batch stochastic gradient descent method，Mini-Batch SGD）充分利用FG和SGD各自的優點，即在每次更新參數時從全部樣本數據中隨機選取部分樣本（稱為一個小批量，記大小為|B|）進行梯度估計，因此，其參數更新方式為：

相比FG 來說，Mini-Batch SGD 在大規模學習任務上具有較高的計算效率。然而，Mini-Batch SGD 用一個小批量樣本的梯度去近似整個訓練集的梯度，梯度往往具有較高的方差，降低了Mini-Batch SGD 的收斂速度。針對隨機梯度下降法中的高方差問題，通過對學習率進行衰減，以降低學習過程的震蕩，但Mini-Batch SGD的收斂速度仍然較慢。

基于方差衰減的隨機梯度法逐漸成為求解深度學習問題的研究熱點，如隨機平均梯度下降法[17]（stochastic average gradient method，SAG）、隨機對偶坐標上升法[18]（stochastic dual coordinate ascent method，SDCA）及相關方法[19-22]。SAG、SDCA 等方法通過降低梯度的方差，從而達到對隨機梯度下降法的加速。然而，SAG和SDCA在參數更新過程中均需要存儲全部梯度（或對偶變量），對存儲空間有較高的要求。隨機方差衰減梯度法[23]（stochastic variance reduced gradient method，SVRG）克服了SAG和SDCA對大量存儲空間需求的問題。SVRG的主要思想是：每隔m次參數更新計算一次全梯度，以降低存儲需求，且該方法可以使用較大的學習率，具有較快的收斂速度。批量隨機方差衰減梯度法[24]（mini-batch stochastic variance reduced gradient method，Mini-Batch SVRG）的提出彌補了SVRG 需要計算全梯度的不足，利用“小批量”計算量小的優點，即利用一個小批量樣本的梯度去近似全梯度，避免了大計算量問題。

SVRG 和批量SVRG 在優化過程中均使用固定的學習率，當參數離最優點較遠時，大的學習率能加快收斂速度；當參數離最優點較近時，若仍然采用大的學習率，可能會跳過最優點，導致學習過程在最優點附近震蕩，降低收斂速度。此外，當之前的參數離當前參數較遠時，當前參數離最優點越接近，此時SVRG 和批量SVRG 過多地利用歷史梯度對當前梯度進行修正反而會造成學習過程震蕩，降低算法收斂速度。針對固定學習率和過多使用歷史梯度帶來的學習過程震蕩和收斂速度慢的問題，本文基于SVRG，利用學習率自適應的策略，并對下降方向進行加權平均，提出了自適應隨機方差衰減梯度法（adaptive stochastic variance reduced gradient method，AdaSVRG）。基于MNIST和CIFAR-10數據集進行數值實驗，以驗證AdaSVRG方法的有效性。

1 AdaSVRG算法

在基于梯度信息的深度學習過程中，學習率和梯度是影響優化方法收斂速度的兩個主要因素。因此，調整學習率和修正下降方向是提高優化方法收斂速度的兩種策略[25]。FG對訓練樣本的充分使用能夠準確估計梯度下降方向，但同時造成了計算成本過高的問題。Mini-Batch SGD 由于計算量小，不受訓練集樣本數量的影響，收斂速度快等優點，因此，常用于求解深度學習任務問題。然而，Mini-Batch SGD 常常伴隨較高的梯度方差，使學習過程震蕩大，降低了收斂速度。SVRG結合了FG 和SGD 的優點，在梯度估計時同時使用FG和SGD，通過降低梯度的方差，使得SVRG 具有較快的收斂速度。SVRG中使用FG進行梯度計算：

在式（6）中，使用小批量樣本的梯度去近似全梯度時存在的誤差會對訓練精確度產生影響。文獻[18]中指出，當批量SVRG 中的SGD 迭代沒有采取小批量策略時，可以通過逐漸增加批量大小|B1|的方式來降低這個誤差，并且當批量大小|B1|滿足|B1|≥（S2為樣本梯度范數的方差的上界，γ≥0，為常量）時，批量SVRG的收斂速率與標準SVRG的收斂速率相同。

在標準的梯度下降法中，每個參數在更新時都使用相同的學習率。由于每個參數的收斂速度都不相同，因此，根據不同參數的收斂情況分別設置不同的學習率，可以使得每個參數的更新盡量保持“同步”，從而達到對算法加速的目的。均方根傳播法（root mean square propagation method，RMSprop）是由Tieleman 提出的一種自適應學習率方法[27]。其主要思想為設置初始學習率之后，每次通過初始學習率α逐參數地除以經過衰減系數β（本文中β=0.9）控制的歷史梯度平方和的平方根，使得每個參數的學習率不同，達到學習率自動調節的作用，具體實現如下：

其中，⊙為按元素乘積，gt為第t次參數更新時的梯度，ε是為了保持數值穩定性而設置的非常小的常數，一般取值ε-7到ε-10。

自適應Delta法[28]（adaptive Delta method，AdaDelta）也是通過梯度平方的指數衰減移動平均來調整學習率，但還引入了每次參數更新差值Δω的平方的指數衰減移動平均，具體實現如下：

其中，rt的計算方式與式（8）相同。

自適應矩估計法[29]（adaptive moment estimation method，Adam）可以看作動量法與RMSprop 的結合，既使用動量作為參數更新方向，又采用RMSprop 自適應計算學習率的策略。具體實現如下：

其中，β1和β2為不同移動平均對應的衰減率。Adam需要對Mt和Gt進行修正。即

Adam的參數更新差值為：

SVRG 和批量SVRG 使用的都是恒定的學習率，雖然可以使用較大的學習率來加快收斂速度，但較大的學習率可能會導致迭代不穩定甚至跳過最優值點，造成在最優值附近震蕩的問題，反而降低了收斂速度。針對固定學習率造成的學習過程震蕩問題，本文將RMSprop中的自適應學習率策略引入到批量SVRG 中。提出了學習率自適應的AdaSVRG。AdaSVRG 與RMSprop、AdaDelta、Adam 等算法的不同之處在于：AdaSVRG 在自適應調整學習率時應用的是方差衰減的梯度估計。如算法1所示。

在AdaSVRG 中，第8 步為批量SVRG 梯度平方的指數加權平均，用于自動調整每個參數的學習率，降低學習過程的震蕩，提高收斂速度。第9 步中AdaSVRG相較于批量SVRG的改進之處在于：對第7步中計算梯度的式子采用加權平均來估計AdaSVRG 的下降方向，提高算法的穩定性。在批量SVRG 中，由于μs和ωs需要經過m次迭代后才更新一次，而ωt在這m次迭代中已經逐漸接近最優值ω*，故ωs與ωt-1之間的差異在這m次迭代中逐漸增大。因此，若過多采用參數為ωs時的歷史梯度來對當前梯度（此時參數為ωt-1）進行修正，反而使得梯度估計變差，導致學習過程產生震蕩。針對這一問題，AdaSVRG通過對梯度估計采用加權平均策略，使得當前的梯度估計既可以利用上歷史梯度信息，又避免了因過多使用歷史梯度信息進行修正帶來的問題。因此，AdaSVRG具有更好的穩定性和更快的收斂速度。

2 收斂性分析

本章分析AdaSVRG 算法的收斂性。在本文中，如無特殊說明，表示實歐式空間中的內積，‖·‖均表示2-范數。假設ψi(ω)光滑且凸，?ψi(ω)為L-Lipschitz連續函數，P(ω)為μ-強凸函數。假設‖ωt-ω*‖≤Z，Z≥0，對所有的t成立。假設μs近似全梯度時的誤差為es。定義函數：

記ρ(L,L)=ρ，本文討論a=b=L時的特殊情況。

定理1若μs=?P(ωs)+es，設‖gt‖≤G，≤R，選取α、β、m、ξ使得0＜ρ＜1，則AdaSVRG 算法在option II下，滿足：

由定理1 可知，當誤差es以一定的速率減小時，AdaSVRG算法收斂。

在給出定理1的證明之前，先介紹如下幾個相關引理。以下證明中假設ω*為最優值。

引理1?ω，有：

證明由于?ψi(ω)為L-Lipschitz連續函數，滿足：

令ω′=ω*，對不等式在所有i上求和后兩端乘以可得引理1。

證畢。

引理2?a，b，c∈Rn，若＞0 且b所有分量為正，則存在ξ＞0，使得：

證明由Cauchy-Schwartz不等式可知：

因此，存在ξ＞0，η≥‖b‖＞0，使得：

即存在ξ＞0，使得：

證畢。

用νt表示第t步時的搜索方向，即：

可得：

E[νt]=β?P(ωt-1)+es

引理3在參數更新的內循環中，對第t次迭代成立：

證畢。

引理4在參數更新的內循環中，設‖gt‖≤G，對第t次迭代成立：

證明由于‖gt‖≤G，故存在R＞0，使得≤R，由引理2、引理3 以及AdaSVRG 算法的迭代規則ωt=ωt-1-，可得：

第一個不等式根據引理2 所得，由于-νt為參數更新方向，因此＞0。第二個不等式根據引理3所得。第三個不等式根據P(ω) 的凸性，即滿足不等式-(ωt-1-ω*)T?P(ωt-1)≤P(ω*)-P(ωt-1)，第四個不等式利用了Cauchy-Schwartz 不等式和‖ωt-1-ω*‖≤Z。證畢。

為了證明定理1，將引理4 中的不等式對所有t=1,2,…,m相加后求期望，可得：

對固定的第s次循環，記ω0=ωs，E[P(ωt-1)]=E[P(ωs+1)]，對AdaSVRG算法option II可得：

第二個不等式根據P(ω)的μ-強凸性質，即滿足P(ω)-P(ω′)-≥?P(ω′)T(ω-ω′)且?P(ω*)=0。由于0＜ρ＜1，故2ξβm-4β2LR2m＞0，則有：

證畢。

3 數值實驗分析

3.1 MNIST數據集

為了驗證AdaSVRG的有效性，本章基于MNIST和CIFAR-10 數據集分別進行數值實驗。為了公平起見，批量SVRG算法中，全梯度也采用小批量進行近似。通過比較AdaSVRG 與Mini-Batch SGD、批量SVRG 對同一數據集及網絡的表現來說明AdaSVRG在收斂速度上的優越性。實驗中對不同的數據集使用了不同的訓練網絡，MNIST 數據集使用網絡N1（3 層全連接層，激活函數為ReLU 函數），CIFAR-10 數據集使用網絡N2（ResNet 網絡）。關于實驗數據集的具體說明見表1。為了避免實驗的偶然性，對所有數據集均在相同條件下進行了三次同等重復實驗，下文中所有數據均取三次重復實驗的平均值。

表1 數據集及對應訓練網絡說明Table 1 Description of data sets and training networks

實驗參數說明：iteration_times=10 000，表示網絡訓練次數；α=0.01，表示初始學習率；lg_batch為近似全梯度的批量大小；batch_size表示AdaSVRG中方差衰減的Mini-Batch SGD迭代的批量大小和Mini-Batch SGD的批量大小；m為AdaSVRG 中進行方差衰減的Mini-Batch SGD迭代的次數。

由表2、表3、表4可知，對于MNIST數據集，同一條件下，由于AdaSVRG需要自適應計算學習率，因此其所用的訓練時間在三者中最長，但AdaSVRG 在訓練集和測試集上的精確度也是三者中最高的，相較于批量SVRG 和Mini-Batch SGD 來說，AdaSVRG 在訓練集和測試集上的精確度提升明顯。同一條件下，批量SVRG在訓練集、測試集上的精確度低于Mini-Batch SGD。隨著batch_size的增大，三種方法在訓練集和測試集上的精確度都有微小的提高，但伴隨著訓練時間也在增加。因此，在MNIST 數據集上，若想進一步使用AdaSVRG提高訓練集和測試集的精確度，可在增加訓練時間為代價的情況下，適當增大batch_size。若想降低AdaSVRG的訓練時間，使用較小的batch_size 也能在訓練集和測試集上達到理想的精確度。

表2 實驗參數（lg_batch=1 000，batch_size=100，m=10）Table 2 Experiment parameters

表3 實驗參數（lg_batch=1 000，batch_size=300，m=10）Table 3 Experiment parameters

表4 實驗參數（lg_batch=1 000，batch_size=500，m=10）Table 4 Experiment parameters

由表3、表5 可知，在MNIST 數據集上，同等條件下，若增大m，AdaSVRG 的學習效果仍然優于批量SVRG。并且，增大m后，AdaSVRG在測試集上的精確度有小幅提高，并且AdaSVRG 的訓練時間也有微小減少，說明適當增大m可以節省AdaSVRG訓練時間。然而，隨著m的增大，更新參數的梯度估計變差，會使學習效果變差。如在m增大后，AdaSVRG在訓練集上的精確度有所降低。

表5 實驗參數（lg_batch=1 000，batch_size=300，m=50）Table 5 Experiment parameters

由圖1 可知，AdaSVRG 在MNIST 數據集上的收斂速度明顯優于批量SVRG和Mini-Batch SGD。AdaSVRG在學習過程中的震蕩程度明顯降低，并且在訓練達到一定次數后，Loss的值便開始趨于穩定不再下降。

圖1 MNIST數據集收斂過程圖Fig.1 Convergence process of MNIST data set

3.2 CIFAR-10數據集

由表6、表7、表8可知，由于ResNet網絡的復雜度高，因此AdaSVRG 在CIFAR-10 數據集上所需的訓練時間較長，但對訓練集和測試集精確度的提升比批量SVRG和Mini-Batch SGD明顯。在同等條件下，AdaSVRG在測試集上的精確度比批量SVRG和Mini-Batch SGD最多分別高出了15.7個百分點（見表7）、16.6個百分點（見表8）。Mini-Batch SGD在一定條件下的學習效果甚至優于批量SVRG（見表6、表7）。

表6 實驗參數（lg_batch=1 000，batch_size=100，m=10）Table 6 Experiment parameters

表7 實驗參數（lg_batch=1 000，batch_size=300，m=10）Table 7 Experiment parameters

表8 實驗參數（lg_batch=1 000，batch_size=500，m=10）Table 8 Experiment parameters

由表7、表9 可知，在CIFAR-10 數據集上，增大m后，批量SVRG 和AdaSVRG 的訓練時間都有不同程度的減少，但批量SVRG 的訓練集和測試集精確度降低，而AdaSVRG有微小的提高。

表9 實驗參數（lg_batch=1 000，batch_size=300，m=50）Table 9 Experiment parameters

由圖2 可看出，AdaSVRG 在CIFAR-10 數據集上的收斂速度同樣優于批量SVRG 和Mini-Batch SGD，學習過程的震蕩大幅降低。并且AdaSVRG 在CIFAR-10數據集上訓練達到一定次數后，Loss曲線也開始趨于穩定不再變化。

圖2 CIFAR-10數據集收斂過程圖Fig.2 Convergence process of CIFAR-10 data set

4 總結

本文通過對批量SVRG采取自適應學習率的策略，以及對梯度估計采取加權平均的思想，使得AdaSVRG在學習率和梯度估計修正方面都進行了改進。實驗結果表明AdaSVRG 在收斂速度和訓練集、測試集上的準確率等方面均優于批量SVRG和Mini-Batch SGD，并克服了批量SVRG 中因使用固定學習率和過多使用歷史梯度對當前梯度進行修正所帶來的問題，同時克服了Mini-Batch SGD在迭代中由于梯度估計隨機性產生的高方差問題。由于AdaSVRG有較好的學習率和梯度估計，因此AdaSVRG 穩定性高，學習過程震蕩小，收斂速度快。在訓練相同的次數時，雖然AdaSVRG 在迭代時需要自適應計算學習率會導致訓練網絡所需要的時間相對較長，實驗證明可以通過適當降低AdaSVRG 中使用的Mini-Batch SGD 的批量大小、適當增大m的值以及適當減少訓練次數等方法來降低AdaSVRG的訓練時間。相較于標準SVRG和批量SVRG，AdaSVRG額外引入了一個超參數系數β，因此，如何選取超參數的值對提高AdaSVRG的計算效率非常有意義。