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

(1.太原師范學(xué)院 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,山西 晉中 030619;2.山西工程科技職業(yè)大學(xué) 基礎(chǔ)課教學(xué)部,山西 晉中 030619)

0 引言

在大規(guī)模機(jī)器學(xué)習(xí)中,如下優(yōu)化問(wèn)題常常出現(xiàn):

(1)

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

(2)

其中下標(biāo)it是從{1,2,…,n}中隨機(jī)選取得到.

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

1 算法

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

算法1 SARAH++輸入: 0<γ≤1,步長(zhǎng)0<η≤γL,內(nèi)循環(huán)數(shù)m,最大迭代數(shù)T,樣本數(shù)n以及初始點(diǎn)x～0,G=0,s=0;1:while G

下面將上述自適應(yīng)步長(zhǎng)與SARAH++算法相結(jié)合構(gòu)造成新的算法,見(jiàn)算法2.

算法2 SARAH++AS輸入: 0<γ≤1,步長(zhǎng)0<η≤γL,內(nèi)循環(huán)數(shù)m,最大迭代數(shù)T,樣本數(shù)n以及初始點(diǎn)x～0,G=0,s=0;1:while G1 then4: 計(jì)算Ls= Fxs()- F(xs-1)xs-xs-15: 計(jì)算步長(zhǎng)η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: 隨機(jī)選取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 收斂性分析

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

假設(shè)2假設(shè)每個(gè)fi都是凸的,且目標(biāo)函數(shù)F(x)是μ-強(qiáng)凸的,即

在假設(shè)2中,我們定義x*為最優(yōu)解,F(x)的強(qiáng)凸性等價(jià)為:

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

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

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

在上述式子中,若假設(shè)Lη

證：根據(jù)F(x)的強(qiáng)凸的可知:

(1-μη)

3 數(shù)值實(shí)驗(yàn)

針對(duì)機(jī)器學(xué)習(xí)中二分類(lèi)的l2正則化邏輯回歸問(wèn)題:給定一組訓(xùn)練集(a1,b1),……,(an,bn),其中ai∈d,bi∈{+1,-1},通過(guò)求解下列問(wèn)題得到最優(yōu)預(yù)測(cè)值x∈d,

實(shí)驗(yàn)包括三個(gè)部分:首先,展示了SARAH++AS與SARAH++兩個(gè)算法的收斂速度,驗(yàn)證了SARAH++AS的有效性;其次,對(duì)比了兩個(gè)算法取不同步長(zhǎng)的變化趨勢(shì);最后,對(duì)比了SARAH++AS取不同γ之后對(duì)殘差的影響.所有的實(shí)驗(yàn)結(jié)果如圖1所示.

圖1 不同數(shù)據(jù)集上的SARAH++AS和SARAH++算法殘差對(duì)比

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

圖2對(duì)比了兩個(gè)算法在不同數(shù)據(jù)集上的求解目標(biāo)函數(shù)時(shí)步長(zhǎng)的變化趨勢(shì),其中x軸代表外循環(huán)數(shù),y軸表示步長(zhǎng)變化.圖中藍(lán)色,紅色和綠色實(shí)線代表不同步長(zhǎng)的 SARAH++AS 算法,藍(lán)色,紅色和綠色虛線對(duì)應(yīng)著固定步長(zhǎng)的 SARAH++ 算法.從圖中可以看出,SARAH++AS比固定步長(zhǎng)的SARAH++算法快,并且當(dāng)選擇不同的初始步長(zhǎng)η時(shí),SARAH++AS算法的收斂性能不受影響,對(duì)于步長(zhǎng)的選取更加容易.

圖2 不同數(shù)據(jù)集上的SARAH++AS和SARAH++算法步長(zhǎng)對(duì)比

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

4 結(jié)論

在本文中,將自適應(yīng)步長(zhǎng)與SARAH++算法結(jié)合,提出了一種改進(jìn)的算法SARAH++AS.從實(shí)驗(yàn)結(jié)果分析來(lái)看,相比于使用固定步長(zhǎng)的SARAH++算法,新算法的收斂速度更快,不受初始步長(zhǎng)選取的影響.新算法對(duì)初始步長(zhǎng)的選擇是有效的.