機器學(xué)習(xí)中隨機遞歸梯度算法的步長規(guī)則

甄 娜，王福勝

(太原師范學(xué)院 數(shù)學(xué)系，山西 晉中 030619)

0 引言

在大規(guī)模機器學(xué)習(xí)背景下，廣泛考慮下列優(yōu)化問題：

(1)

其中n是訓(xùn)練集大小，每個fi,i∈{1,2,…,n}是凸函數(shù)且有Lipschitz連續(xù)導(dǎo)數(shù).這類問題在監(jiān)督學(xué)習(xí)應(yīng)用中經(jīng)常出現(xiàn)，而在應(yīng)用中通常n相對比較大使得標準的梯度下降(GD)方法效率較低，因為它需要多次計算全梯度.針對這個不足，隨機梯度下降(SGD)[1]進行了改進，它在每次迭代中隨機選取訓(xùn)練集中的一個實例來近似全梯度.在SGD的第t次迭代中，更新規(guī)則為：

xt+1=xt-ηtfit(xt),

(2)

其中下標it可以從{1,2,…,n}中隨機選取，ηt>0在機器學(xué)習(xí)中通常被稱為學(xué)習(xí)率，即優(yōu)化迭代中的步長.在(2)中通常假設(shè)隨機梯度估計fit(xt)的期望值是F(xt)的無偏估計，即Ε[fit(xt)|xt]=F(xt).然而隨機選取一個實例將可能產(chǎn)生方差，不能確保目標函數(shù)F(xt)收斂.為了克服這個缺陷，人們通常在迭代過程中選取一個下降步長序列以更新步長，一般情況下SGD的下降步長ηt滿足如下條件：

(3)

但這種做法又會導(dǎo)致隨機梯度方法的收斂速度較慢，在強凸條件下，標準的SGD算法是次線性收斂的.

近年來，有關(guān)學(xué)者通過引入方差約簡技術(shù)進一步改進了SGD算法，例如隨機雙坐標上升(SDCA)[2]，隨機方差約簡梯度(SVRG)[3]，小批量半隨機梯度下降(mS2GD)[4]，隨機遞歸梯度(SARAH)[5]等.值得注意的是,上述大部分算法均使用固定的步長.文獻AdaGrad[6]基于過去梯度的平方和自適應(yīng)地選擇步長，獲得了較好的數(shù)值效果.在非線性優(yōu)化問題的算法設(shè)計中，BB步長方法[7]具有較好的特性，戴彧虹等學(xué)者對此進行了深入研究，獲得了豐富的成果[8-11].近年來有關(guān)學(xué)者創(chuàng)新性地將BB方法與梯度下降方法相結(jié)合，提出了另外一類算法用于解決機器學(xué)習(xí)中優(yōu)化問題，獲得了較好的數(shù)值效果，例如SVRG-BB[12]， SARAH-1-BB[13]，STSG[14]等.受上述方法的啟發(fā)，考慮將交替BB步長方法[8]與隨機遞歸梯度方法(SARAH)結(jié)合，提出一個新算法.

1 算法描述

為了構(gòu)造新算法，首先來回顧一下SARAH算法[5](如算法1所示).實際上，SARAH和SVRG[3]是兩種類似的方法，它們執(zhí)行的是一個通常稱為外循環(huán)的確定性步驟，即在外循環(huán)計算目標函數(shù)的全梯度，然后是隨機過程.具體來看，SARAH算法的關(guān)鍵步驟是遞歸更新隨機梯度估計：

vt=fit(xt)-fit(xt-1)+vt-1,

(4)

迭代更新規(guī)則為：

xt+1=xt-ηkvt.

(5)

相比SVRG的梯度更新：

vt=fit(xt)-fit(x0)+v0,

(6)

根據(jù)式(6)發(fā)現(xiàn)SVRG的vt是梯度的無偏估計，而SARAH的vt是梯度的有偏估計，但文獻[5]中證明SARAH的更新規(guī)則的優(yōu)勢在于算法內(nèi)部循環(huán)本身可以實現(xiàn)次線性收斂.

算法1(SARAH)

步2 隨機選取it∈{1,2,…,n}，計算

令t:=t+1.

步3 若t>m，轉(zhuǎn)步4；否則轉(zhuǎn)步2.

步5 令k:=k+1，若k>epoch，停止；否則轉(zhuǎn)步1.

接下來，介紹一下BB[7]方法.該方法在求解非線性優(yōu)化問題中取得了良好的效果.考慮下面的無約束優(yōu)化問題：

minf(x),x∈Rd,

(7)

其中f:Rd→R是一階連續(xù)可導(dǎo)的.文獻[7]中給出了標準的BB方法有兩種更新步長的規(guī)則，即：

(8)

其中sk=xk-xk-1，yk=f(xk)-f(xk-1).當(dāng)時，有這意味著能夠更快地減小目標函數(shù).例如文獻[15]討論了步長規(guī)則優(yōu)于值得注意的是，文獻[8]給出兩種BB步長的交替使用規(guī)則，即:

(9)

其中ε>0是一個常數(shù).注意到式(8)中的BB步長計算不需要任何其它參數(shù)，因此考慮將上述的交替BB步長規(guī)則與隨機遞歸梯度算法(SARAH)相結(jié)合構(gòu)造一個新的算法，算法框架見算法2.

算法2(SARAH-BB1)

步4 若t>m，轉(zhuǎn)步5；否則轉(zhuǎn)步3.

步6 令k:=k+1，若k>epoch，停止；否則轉(zhuǎn)步1.

注：在算法的第2步中ηk等于交替步長規(guī)則計算公式(9)除以m，這是因為在內(nèi)循環(huán)中為更新xt，需要將m個梯度估計依次與x0相加.

2 數(shù)值實驗

在本節(jié)中，通過數(shù)值實驗驗證了SARAH-BB1算法的有效性.實驗所用數(shù)據(jù)集如表1，所有數(shù)據(jù)可以在LIBSVM網(wǎng)站下載.

表1 數(shù)據(jù)信息

另外，通過解決機器學(xué)習(xí)中l(wèi)2正則化邏輯回歸問題來比較算法SARAH-BB1、SARAH與SGD，其中正則化參數(shù)λ>0，即下列問題：

(10)

在第一個實驗中，所有結(jié)果如圖1所示，包括2個子圖(a)和(b)，分別對應(yīng)使用數(shù)據(jù)ijcnn1，splice.在所有子圖中，x軸表示迭代次數(shù)k，y軸表示目標損失殘差.圖1為算法SARAH-BB1中交替BB步長規(guī)則的不同參數(shù)ε值對目標損失殘差的影響，圖1中使用了0.1到1范圍內(nèi)的十個值作為參數(shù)ε值.為了測試ε值對目標損失殘差的影響，對于ijcnn1數(shù)據(jù)，選擇算法SARAH-BB1的初始步長為0.1，對于splice數(shù)據(jù)，選擇初始步長為1.從圖1可以看出，當(dāng)參數(shù)ε取值為0.1或0.2時，算法SARAH-BB1的目標損失殘差穩(wěn)定于較小值；因此在下一個實驗中，固定ε取值為0.1.值得注意的是，其它ε取值同樣可以實現(xiàn)目標損失殘差趨于穩(wěn)定.

圖1 不同數(shù)據(jù)集上算法SARAH-BB1的參數(shù)ε對目標損失殘差的影響

在第二個實驗中，所有結(jié)果如圖2所示，包括6個子圖(a)，(b)，(c)，(d)，(e)和(f)，其中子圖(a)，(b)和(c)使用數(shù)據(jù)ijcnn1，子圖(d)，(e)和(f)使用數(shù)據(jù)splice.在所有子圖中，x軸表示迭代次數(shù)k，y軸表示目標損失殘差.圖2為算法SARAH-BB1、算法SARAH與算法SGD的目標損失殘差對比結(jié)果.此外，在圖2的子圖中，對于算法SARAH-BB1，使用三種不同的初始步長η0，對應(yīng)紅色虛線；而算法SARAH與算法SGD使用三種不同的步長η作為固定步長，其中算法SARAH對應(yīng)藍色虛線，算法SGD對應(yīng)綠色虛線.從圖中可以看出，新算法SARAH-BB1的目標損失殘差對初始步長η0的選擇不敏感，并且經(jīng)過幾次迭代后，它穩(wěn)定于較小值.值得注意的是，算法SARAH只有選擇合適的固定步長時，該算法的目標損失殘差才會穩(wěn)定于較小值.這意味著新的SARAH-BB1算法在初始步長選擇上具有魯棒性.

圖2 不同數(shù)據(jù)集上算法SARAH-BB1、SARAH和SGD的目標損失殘差比較

3 結(jié)論

本文將隨機遞歸梯度算法(SARAH)和交替BB步長方法相結(jié)合，提出了一種新的SARAH-BB1算法.新算法在運行過程中可以自適應(yīng)地調(diào)節(jié)步長大小，相比已有的使用固定步長的SARAH算法和SGD算法，新算法的收斂速度更快.大量的數(shù)值實驗表明，本文提出的新算法SARAH-BB1對初始步長具有魯棒性.