基于自適應步長的隨機遞歸梯度算法

李曉桐,王福勝*,喬曉云

(1.太原師范學院 數學與統計學院,山西 晉中 030619;2.山西工程科技職業大學 基礎課教學部,山西 晉中 030619)

0 引言

在大規模機器學習中,如下優化問題常常出現:

(1)

xt+1=xt-ηt?fit(xt),

(2)

其中下標it是從{1,2,…,n}中隨機選取得到.

在機器學習中有許多改進SGD的工作[3-4].近年來,出現了大量被稱為方差減少方法的隨機梯度算法的改進變體,如:隨機方差縮減梯度算法(SVRG)[5],隨機遞歸梯度算法(SARAH,SARAH+)[6],隨機平均梯度算法(SAG)[7],隨機對偶坐標上升算法(SDCA)[8],小批量半隨機梯度下降算法(mS2GD)[9],和SAGA[10]等.近年來,對于隨機遞歸梯度算法有新的改進,如SARAH++[11].

1 算法

因此,文獻[11]中將SARAH+修改為SARAH++,算法如下:

算法1 SARAH++輸入: 0<γ≤1,步長0<η≤γL,內循環數m,最大迭代數T,樣本數n以及初始點x～0,G=0,s=0;1:while G

下面將上述自適應步長與SARAH++算法相結合構造成新的算法,見算法2.

算法2 SARAH++AS輸入: 0<γ≤1,步長0<η≤γL,內循環數m,最大迭代數T,樣本數n以及初始點x～0,G=0,s=0;1:while G1 then4: 計算Ls= Fxs()- F(xs-1)xs-xs-15: 計算步長ηs=γmLs6: end if7: while v(s)t2≥γv(s)02 and t≤m do8: x(s)t+1=x(s)t-ηv(s)t,t=t+19: if m≠0 do10: 隨機選取it∈{1,2,…,n},11: v(s)t= fit(x(s)t)- fit(x(s)t-1)+v(s)t-112: end if 13: end while14:KS=t,x～s=x(s)KS,G=G+KS15: end whileS=s,x^=x～s

2 收斂性分析

假設1假設每個函數fi(x)的梯度是L-Lipschitz連續的,即存在一個常數L,有

假設2假設每個fi都是凸的,且目標函數F(x)是μ-強凸的,即

在假設2中,我們定義x*為最優解,F(x)的強凸性等價為:

假設3假設每個函數fi(x)都是凸函數,則有

fi(y)≥fi(x)+?fi(x)T(y-x),?x,y∈d.

其中x*是F(x)的最優解.

在上述式子中,若假設Lη

證：根據F(x)的強凸的可知:

(1-μη)

3 數值實驗

針對機器學習中二分類的l2正則化邏輯回歸問題:給定一組訓練集(a1,b1),……,(an,bn),其中ai∈d,bi∈{+1,-1},通過求解下列問題得到最優預測值x∈d,

實驗包括三個部分:首先,展示了SARAH++AS與SARAH++兩個算法的收斂速度,驗證了SARAH++AS的有效性;其次,對比了兩個算法取不同步長的變化趨勢;最后,對比了SARAH++AS取不同γ之后對殘差的影響.所有的實驗結果如圖1所示.

圖1 不同數據集上的SARAH++AS和SARAH++算法殘差對比

圖1對比了SARAH++AS與SARAH++兩個算法的收斂速度,其中x軸代表外循環數,y軸表示殘差對比,即F(xs)-F(x*).圖中,藍色,紅色和綠色實線代表不同步長的 SARAH++AS 算法,藍色,紅色和綠色虛線對應著固定步長的 SARAH++ 算法.四個子圖(a),(b),(c)和(d)分別對應于phishing,ijcnn1,w8a和 splice 四個數據集.從圖中可以看出,SARAH++AS比固定步長的SARAH++算法快,并且當選擇不同的初始步長η時,SARAH++AS算法的收斂性能不受影響,對于步長的選取更加容易.

圖2對比了兩個算法在不同數據集上的求解目標函數時步長的變化趨勢,其中x軸代表外循環數,y軸表示步長變化.圖中藍色,紅色和綠色實線代表不同步長的 SARAH++AS 算法,藍色,紅色和綠色虛線對應著固定步長的 SARAH++ 算法.從圖中可以看出,SARAH++AS比固定步長的SARAH++算法快,并且當選擇不同的初始步長η時,SARAH++AS算法的收斂性能不受影響,對于步長的選取更加容易.

圖2 不同數據集上的SARAH++AS和SARAH++算法步長對比

圖3 SARAH++AS算法中取不同γ對殘差的影響

4 結論

在本文中,將自適應步長與SARAH++算法結合,提出了一種改進的算法SARAH++AS.從實驗結果分析來看,相比于使用固定步長的SARAH++算法,新算法的收斂速度更快,不受初始步長選取的影響.新算法對初始步長的選擇是有效的.