基于AdaBelief的Heavy-Ball動量方法

張澤東 隴 盛 鮑 蕾 陶 卿

隨機梯度下降法[1]是解決優(yōu)化問題的經(jīng)典算法之一，在其基礎(chǔ)上添加動量和自適應(yīng)步長技巧是機器學(xué)習(xí)領(lǐng)域用于提升優(yōu)化算法性能常用的兩種方式.動量方法利用梯度的歷史累積信息調(diào)整解向量的更新方向，而自適應(yīng)步長技巧利用梯度的歷史信息調(diào)整梯度在不同維度上的步長.從理論分析的角度上說:動量方法能加速梯度下降方法的收斂速率，避開非凸優(yōu)化中的局部極小點和鞍點[2-3]；自適應(yīng)步長方法能降低對人為指定步長的依賴，在處理稀疏學(xué)習(xí)問題時具有更緊的收斂界[4-5].

為了進一步提升Adam性能，學(xué)者們開始試圖對自適應(yīng)步長方法進行更精細的改進[10].特別是Zhuang等[11]提出AdaBelief，在Adam的基礎(chǔ)上將動量的EMA形式看成是下一次迭代的預(yù)估方向，根據(jù)當前位置梯度方向是否與動量的EMA形式方向一致而靈活地調(diào)整步長.當梯度方向與動量的EMA形式方向一致時，選擇相信，采用較大的步長；當兩者方向相反時，選擇懷疑，采用較小的步長.AdaBelief的這種步長策略更好地適應(yīng)問題自身的特征，同時具有Adam快速收斂特性和隨機梯度下降法的泛化性能.實驗表明，AdaBelief在訓(xùn)練和測試精度方面均取得較優(yōu)的實際效果，但由于其使用與Adam一樣的EMA策略，仍無法避免收斂性方面存在的Reddi問題，導(dǎo)致未能較好體現(xiàn)動量的加速性能.

1 相關(guān)知識

本節(jié)介紹動量方法和自適應(yīng)算法，以及它們的收斂性.

考慮約束優(yōu)化問題:

其中,f(w)為目標函數(shù),一般為凸函數(shù)，Q?Rn為有界閉凸集.投影次梯度方法的迭代步驟[1]為

wt+1=wt-αtgt.

為了簡單起見，與文獻[8]和文獻[13]一樣，在算法的更新公式中省略偏差修正步驟.Adam更新公式如下[6]：

可以看出，Adam與投影次梯度算法的不同主要體現(xiàn)在使用動量的EMA形式mt調(diào)整參數(shù)更新方向，并采用自適應(yīng)矩陣Vt調(diào)整參數(shù)更新的每維步長.

AMSGrad具體形式如下：

AdaBelief更新公式如下：

Heavy-Ball動量方法的迭代公式為

wt+1=wt-αtgt+βt(wt-wt-1),

其中，αt為設(shè)置的衰減學(xué)習(xí)率，βt∈[0,1)為動量系數(shù)[2]，wt-wt-1為動量項.當動量系數(shù)為常數(shù)時，分別將Heavy-Ball動量和EMA動量展開為梯度累加和的形式，可得

可以看出，Heavy-Ball動量在參數(shù)更新時利用αi(i=1,2,…,t)的信息，而動量的EMA形式僅利用αt的信息，另外當動量系數(shù)β趨近于1時，(1-β)→0，使用動量的EMA形式時，wt+1≈wt， 而使用Heavy-Ball動量卻不會出現(xiàn)這樣的問題[12].

AdaHB迭代公式為

2 基于AdaBelief的Heavy-Ball動量方法

本節(jié)提出基于AdaBelief的Heavy-Ball動量方法(AdaBHB)，給出在目標函數(shù)為非光滑一般凸情況下算法的最優(yōu)個體收斂性證明.

將AdaBelief策略下的自適應(yīng)步長技巧與AdaHB結(jié)合，提出AdaBHB，迭代形式為

不同于AdaHB,AdaBHB中自適應(yīng)矩陣St的更新借鑒AdaBelief的思想，即對當前梯度與動量項差值的外積矩陣對角陣進行EMA平均，與之不同的是動量項不再采用EMA形式的動量mt，而是借鑒AdaHB的思想,采用Heavy-Ball動量wt-wt-1.

在進行最優(yōu)個體收斂性的證明時，參考Tao等[13]提出的僅采用EMA策略調(diào)整步長的Heavy-Ball動量方法的收斂性分析思路，引入加權(quán)動量項

pt=t(wt-wt-1)，

巧妙選取時變步長αt和動量因子β1t，從而將AdaBHB的迭代方式轉(zhuǎn)化為類似于投影次梯度法的形式[13]：

借鑒此方法處理迭代，得到如下引理1.為了證明的簡潔性，這里的證明采用無約束情況下的證明方式，有約束情況下的證明只需在此基礎(chǔ)上利用投影的非擴張性即可.

引理1令

pt=t(wt-wt-1)，

假設(shè)wt由式(1)產(chǎn)生，取

則有

(2)

證明根據(jù)迭代式(1),并令

pt=t(wt-wt-1)，

有

wt+1+pt+1=wt+1+(t+1)(wt+1-wt)=

(t+2)wt+1-(t+1)wt=

代入

可得

證畢

基于式(2)可證明定理1，但為了解決變步長和動量系數(shù)導(dǎo)致的遞歸問題，先提出引理2.

引理2令

證明使用Zhuang等[11]證明在線AdaBelief的regret界時采用的迭代技巧，進行如下整理：

證畢

定理1設(shè)f(w)為一般凸函數(shù)，取

證明由引理1及投影的非擴張性可得

將上式從t=1,2,…,T累加，得

根據(jù)引理2，可得

證畢

推論1設(shè)f(w)為一般凸函數(shù)，取

wt由式(1)產(chǎn)生，則

推論1也表明個體收斂速率比平均收斂速率更難以獲得.綜上所述，獲得AdaBHB在非光滑一般凸條件下的個體收斂速率.然而上述證明都是在批處理條件下完成的，所以這種操作并不適用于大規(guī)模數(shù)據(jù)集.為了使AdaBHB適合處理大規(guī)模機器學(xué)習(xí)問題，接下來將算法推廣至隨機形式.

考慮較簡單的二分類問題，訓(xùn)練樣本集:

S={(xi,yi)|i=1,2,…,m}?Rn×{1,-1},

其中，xi為樣本特征，yi為樣本的標簽值，假設(shè)(xi,yi)是獨立同分布的.

假設(shè)非光滑學(xué)習(xí)問題的損失函數(shù)為hinge損失，即

fi(w)=max{0,1-yi〈w,xi〉}，

則優(yōu)化目標函數(shù)為：

由于hinge損失函數(shù)的次梯度有多種計算方式，這里采用文獻[18]的方式進行計算，即

(3)

其中，

實驗中設(shè)定|At|=1,i是算法迭代到第t步時為計算當前梯度而隨機抽取的樣本序號.當樣本滿足獨立同分布條件時，經(jīng)過隨機抽取方式計算得到的隨機次梯度?fi(wt)就是梯度在wt處的無偏估計.

約束條件下隨機形式的AdaBHB的迭代公式如下：

(4)

相比批處理形式下次梯度gt的每次計算都需遍歷樣本集，隨機次梯度?fi(wt)只需選取一個樣本即可.

AdaBHB的執(zhí)行步驟如下所示.

算法AdaBHB

輸入循環(huán)次數(shù)T

輸出wT

初始化向量w1∈Q

Fort=1 toT

等可能地選取i=1,2,…,m

根據(jù)式(3)計算次梯度?fi(wt)

通過式(4)計算wt+1

End for

從算法中可看出，隨機形式的算法只是將批處理形式下目標函數(shù)的梯度替換為無偏估計.Rakhlin等[19]給出將批處理算法的regret界轉(zhuǎn)換為隨機算法regret界的技巧，該技巧對于定理1同樣成立.與文獻[14]和文獻[15]類似，本文可將定理1推廣至隨機形式，得到定理2.

定理2設(shè)f(w)為一般凸函數(shù)，取

wt由式(4)產(chǎn)生，則

E(f(wT)-f(w*))≤

3 實驗及結(jié)果分析

凸優(yōu)化實驗中的問題模型為支持向量機中常見的hinge損失.本文采用Astro、A9a、Covtype、Ijcnn1、Rcv1、W8a標準數(shù)據(jù)集，均來源于LIBSVM網(wǎng)站.

在深度學(xué)習(xí)實驗中，按照Wang等[20]和Tao等[13]的思路，模型為典型的ResNet-18網(wǎng)絡(luò)及構(gòu)造的一般4層卷積神經(jīng)網(wǎng)絡(luò)(Convolutional Neural Net-work, CNN)，采用CIFAR10、CIFAR100和MNIST常用標準數(shù)據(jù)集.CIFAR10數(shù)據(jù)集包含50 000個訓(xùn)練樣本，10 000個測試樣本.CIFAR100數(shù)據(jù)集包含50 000個訓(xùn)練樣本，10 000個測試樣本.MNIST數(shù)據(jù)集包含60 000個訓(xùn)練樣本，10 000個測試樣本.

為了驗證AdaBHB既在理論上具有最優(yōu)收斂性，又在實驗上具有良好效果，對比算法選取理論上收斂性最優(yōu)的Heavy-Ball(HB)算法、AdaHB，以及在實驗上表現(xiàn)良好的隨機梯度下降(Stochastic Gradient Descent, SGD)、Adam、Ada-Belief.

為了降低隨機因素產(chǎn)生的影響，各算法在每個數(shù)據(jù)集上均運行5次，取平均值作為最后輸出.

在凸優(yōu)化實驗中，調(diào)用有效投影稀疏學(xué)習(xí)(Spares Learning with Efficient Projections, SLEP)工具箱的函數(shù)，實現(xiàn)投影的計算，PQ為l1范數(shù)球

{w∶‖w≤z‖1}

上的投影算子.根據(jù)數(shù)據(jù)集的不同，z對應(yīng)選取不同的值，并且各算法均取相同的約束參數(shù).從理論分析的角度出發(fā)，AdaBHB應(yīng)具有最優(yōu)的收斂速率.

各算法在6個數(shù)據(jù)集上的收斂速率對比如圖1所示，圖中縱坐標表示當前目標函數(shù)值與最優(yōu)目標函數(shù)值之差.由圖可見，在100步迭代之后，各算法在6個標準數(shù)據(jù)集上都達到10-4的精度，收斂趨勢基本相同，AdaBHB收斂最快，這與理論分析是吻合的.

(a)Astro (b)A9a (c)Covtype

在深度學(xué)習(xí)實驗中，采用參數(shù)權(quán)重衰減和批量歸一化策略以減少過擬合，所用的損失為交叉熵.圖2為各算法在2個網(wǎng)絡(luò)上的損失對比，圖3為各算法在2個網(wǎng)絡(luò)上的測試精度對比.

(a1)CIFAR10 (a2)CIFAR100 (a3)MNIST

(a1)CIFAR10 (a2)CIFAR100 (a3)MNIST

由圖2和圖3可見，AdaBHB在損失降低速率上明顯占優(yōu)，這也促進其在測試精度上效果良好.在其它深度學(xué)習(xí)網(wǎng)絡(luò)上的實驗也驗證AdaBHB取得較優(yōu)的實驗效果，因此具有普遍性.由于論文篇幅限制，本文僅展示較典型的殘差網(wǎng)絡(luò)Res-Net18和CNN4上的結(jié)果.

實驗表明， AdaBHB不僅在非光滑凸條件下理論上可獲得最優(yōu)的個體收斂速率，并且在深度學(xué)習(xí)實驗中也取得性能的提升.這也說明AdaBelief 的步長調(diào)整技巧可作為一般性的減少震蕩、提升算法泛化性能的方法.AdaBHB結(jié)合傳統(tǒng)動量方法的優(yōu)點，可發(fā)展出更多性能良好的優(yōu)化算法.

4 結(jié) 束 語

本文結(jié)合AdaBelief的步長調(diào)整技巧和Heavy-Ball型動量項，提出基于AdaBelief的Heavy-Ball動量方法(AdaBHB),證明算法具有最優(yōu)的個體收斂速率，并在深度學(xué)習(xí)實驗中得到驗證.今后將研究強凸情況下AdaBHB的個體收斂速率，以及將Nesterov加速梯度(Nesterov Accelerated Gradient, NAG)型動量與AdaBelief的步長調(diào)整技巧結(jié)合的優(yōu)化算法的收斂速率等問題.