張澤東 隴 盛 鮑 蕾 陶 卿

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

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

1 相關(guān)知識(shí)

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

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

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

wt+1=wt-αtgt.

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

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

AMSGrad具體形式如下：

AdaBelief更新公式如下：

Heavy-Ball動(dòng)量方法的迭代公式為

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

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

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

AdaHB迭代公式為

2 基于AdaBelief的Heavy-Ball動(dòng)量方法

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

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

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

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

pt=t(wt-wt-1)，

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

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

引理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，但為了解決變步長(zhǎng)和動(dòng)量系數(shù)導(dǎo)致的遞歸問題，先提出引理2.

引理2令

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

證畢

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

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

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

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

證畢

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

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

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

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

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

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

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

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

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

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

(3)

其中，

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

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

(4)

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

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

算法AdaBHB

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

輸出wT

初始化向量w1∈Q

Fort=1 toT

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

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

通過式(4)計(jì)算wt+1

End for

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

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

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

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

3 實(shí)驗(yàn)及結(jié)果分析

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

在深度學(xué)習(xí)實(shí)驗(yàn)中，按照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常用標(biāo)準(zhǔn)數(shù)據(jù)集.CIFAR10數(shù)據(jù)集包含50 000個(gè)訓(xùn)練樣本，10 000個(gè)測(cè)試樣本.CIFAR100數(shù)據(jù)集包含50 000個(gè)訓(xùn)練樣本，10 000個(gè)測(cè)試樣本.MNIST數(shù)據(jù)集包含60 000個(gè)訓(xùn)練樣本，10 000個(gè)測(cè)試樣本.

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

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

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

{w∶‖w≤z‖1}

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

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

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

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

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

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

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

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

4 結(jié) 束 語(yǔ)

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