王福勝,李曉桐

(太原師范學(xué)院數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,山西 晉中 030619)

1.引言

在機(jī)器學(xué)習(xí)中,經(jīng)常會出現(xiàn)以下的優(yōu)化問題:

其中n是訓(xùn)練集大小,每個(gè)fi,i ∈{1,2,···,n}是凸函數(shù)且有Lipschitz連續(xù)導(dǎo)數(shù).解決上述優(yōu)化問題的標(biāo)準(zhǔn)有效的方法為梯度下降法(GD)[1].對于光滑優(yōu)化問題(1.1),梯度下降的迭代方法為

其中ηt>0表示步長.當(dāng)n較大時(shí)需要計(jì)算全梯度,導(dǎo)致計(jì)算量很大.Robbins和Monro[2]在1951年提出了隨機(jī)近似(stochastic approximation,SA).之后,研究者提出了隨機(jī)梯度下降(stochastic gradient descent,SGD)[3-4],該方法的迭代公式如下:

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

在機(jī)器學(xué)習(xí)中有一系列改進(jìn)SGD的工作[3-4].SGD算法的收斂性質(zhì)取決于隨機(jī)方向和真實(shí)梯度的方差,因此,如何縮減方差是改進(jìn)SGD的方法之一.常見的有隨機(jī)方差縮減梯度算法(SVRG)[5],隨機(jī)遞歸梯度算法(SARAH)[6],隨機(jī)平均梯度算法(SAG)[7]等.

對于方差縮減類算法而言,步長也是關(guān)鍵因素.傳統(tǒng)的步長要選擇遞減步長或者較小的固定步長,并且滿足

關(guān)于步長的工作也有很多,AdaGrad[8]和Adam[9]等采用對角修正技術(shù)為每個(gè)分量自適應(yīng)地選取步長.當(dāng)前,由于BB步長[10]特有的性質(zhì),許多學(xué)者將方差縮減方法與BB步長相結(jié)合,如SARAH-I-BB[11]算法.本文考慮將Polyak[12]步長與隨機(jī)遞歸梯度下降算法[6]結(jié)合,提出SARAH-Polyak.

2.算法

其中,it ∈{1,2,···,n}.可以看出,SARAH算法的迭代方向vt是真實(shí)梯度的有偏估計(jì),即

接下來,我們介紹一下Polyak[12]步長,它普遍用于投影次梯度法.假設(shè)我們要求解以下的無約束優(yōu)化問題:

其中f:Rd →R是凸但可能非光滑的函數(shù).假設(shè)f在xk處的次梯度f′(xk)∈?f(xk)是可計(jì)算的.投影次梯度法有如下形式:

再根據(jù)文[13]中引理8.11有

其中x?是問題(2,1)的最優(yōu)解,f(x?)是(2.1)的最優(yōu)值.tk的一種選擇是取不等式(2.2)右端的最小值,因此有

當(dāng)f′(xk)=0時(shí),上述式子未定義,我們可以人為的定義tk=1(也可以取任意正數(shù)),最后得到Polyak步長

從上述表達(dá)式可知,Polyak步長依賴于f(x?)的值.在一些應(yīng)用中,f(x?)的值是已知的.并且現(xiàn)有的算法中Polyak步長使用的是隨機(jī)的次梯度,而本文使用的是全梯度.即

文[14]構(gòu)建了一個(gè)簡單函數(shù)h,通過下式計(jì)算步長

函數(shù)h有不同的形式:

因?yàn)樵谠缙诘?可以選取較大步長加速收斂,然后逐漸選擇較小步長防止振蕩.因此,當(dāng)選取h=g(k)時(shí),可以令g(k)是關(guān)于外循環(huán)數(shù)k的單調(diào)遞增函數(shù).文[14] 中的算法(SARAH-AS)選取函數(shù)的具體形式如下:

為了加快收斂,本文中的步長也采用上述方式,具體形式為

其中tk為(2.4)中的步長,h=

下面我們將上述Polyak步長與隨機(jī)遞歸梯度下降算法相結(jié)合構(gòu)造成新的算法,算法框架見算法2.

3.收斂性分析

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

這里我們定義x?為問題(1.1)的最優(yōu)解.并且由于F(x)是強(qiáng)凸的,因此x?是唯一的.

假設(shè)3.2假設(shè)每個(gè)函數(shù)fi(x)的梯度是L-Lipschitz連續(xù)的,即

即?F(x)也是L-Lipschitz連續(xù)的.

引理3.1[15]假設(shè)F(x)是凸函數(shù),且?F(x)是L-Lipschitz連續(xù)的,則對?x,y ∈Rd,有

引理3.2[15]假設(shè)F(x)是凸函數(shù),且?F(x)是L-Lipschitz連續(xù)的,則對?x,y ∈Rd,有

上面最后一個(gè)不等式中我們利用了引理3.6以及F(x)的強(qiáng)凸性.并且有

即算法2具有R-線性收斂速度.

證根據(jù)目標(biāo)函數(shù)F(x)的強(qiáng)凸性以及?F(x?)=0,可知

上式蘊(yùn)含算法2具有R-線性收斂速度.

近年來,強(qiáng)凸性假設(shè)一直是證明算法收斂的標(biāo)準(zhǔn)假設(shè),但這一假設(shè)并不適用于文獻(xiàn)中的許多問題.為了在一般凸條件下證明算法的收斂性,我們先給出一些條件.我們將X?表示為問題(1.1)的最優(yōu)解集,將xproj表示為x在X?上的投影.因此,?F(xproj)=0.我們使用x?表示(1.1)的最優(yōu)值.首先假設(shè)F是一階連續(xù)可微的,并且F是L-Lipschitz連續(xù)的,ν>0.我們給出以下四個(gè)條件:

接下來,我們分析了RSI條件下SARAH的性質(zhì).

引理3.7[11]若假設(shè)F是凸的并且滿足(3.1)并且?F(x)是L-Lipschitz連續(xù)的,那么對于任何α ∈[0,1],有

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

在本節(jié)中,通過數(shù)值實(shí)驗(yàn)結(jié)果驗(yàn)證算法SARAH-Polyak的有效性.我們針對機(jī)器學(xué)習(xí)中二分類的?2正則化邏輯回歸問題: 給定一組訓(xùn)練集(a1,b1),(a2,b2),···,(an,bn),其中ai ∈Rd,bi ∈{+1,-1},通過求解下列問題得到最優(yōu)預(yù)測值x ∈Rd,

其中λ>0是正則化參數(shù).我們使用了三個(gè)公開的數(shù)據(jù)集,數(shù)據(jù)集的大小為n,維度為d,詳細(xì)信息如表4.1所示,所有數(shù)據(jù)可以在LIBSVM網(wǎng)站(www.csie.ntu.edu.tw/～cjlin/libsvmtools/datasets/)下載.表中還列出了實(shí)驗(yàn)中所選取的λ>0值(在所有數(shù)據(jù)集上設(shè)置參數(shù)為λ=10-4,m=2n.所有的數(shù)值實(shí)驗(yàn)均在相同的Python計(jì)算環(huán)境下進(jìn)行.所有的實(shí)驗(yàn)結(jié)果如圖4.1-4.6所示.

圖4.1 heart上的殘差損失

表4.1 數(shù)值實(shí)驗(yàn)中使用的數(shù)據(jù)集和正則化參數(shù)

圖4.1到圖4.6展示了SARAH-BB,SARAH 以及SARAH-Polyak三個(gè)算法在數(shù)據(jù)集heart,splice和ijcnn1上的殘差損失及步長變化趨勢.在所有的圖中,藍(lán)色,紅色和綠色實(shí)線代表不同步長的SARAH-Polyak 算法;黑色實(shí)線代表最優(yōu)步長的SARAH-BB算法;藍(lán)色,紅色和綠色虛線對應(yīng)著固定步長的SARAH算法.在所有的圖中,x軸代表外循環(huán)數(shù),圖4.1,4.3和圖4.5中y軸表示最優(yōu)間隔，即F(xk)-F(x?),圖4.2,4.4和4.6中y軸表示步長變化趨勢.

圖4.2 heart上的步長變化趨勢

圖4.3 splice上的殘差損失

圖4.4 splice上的步長變化趨勢

圖4.5 ijcnn1上的殘差損失

圖4.6 ijcnn1上的步長變化趨勢

從圖4.1,4.3和4.5中可以看出:SARAH-Polyak算法收斂速度整體上比采用固定步長的SARAH 算法快,并且當(dāng)選擇不同的初始步長η0時(shí),SARAH-Polyak算法的收斂性能不受影響.并且SARAH-Polyak與最優(yōu)步長的SARAH-BB算法相差不大.圖4.2,4.4和4.6中可以看出: 當(dāng)選取不同的初始步長時(shí),SARAH-Polyak算法的步長最終收斂于最優(yōu)步長的鄰域.

5.結(jié)論

在本文中,我們提出了一種改進(jìn)的算法SARAH-Polyak.首先我們用理論說明Polyak步長并沒有增加算法的復(fù)雜度,因?yàn)樵撍惴ㄒ呀?jīng)計(jì)算出全梯度,并且可以通過其他算法得到最優(yōu)值.然后分別在強(qiáng)凸和一般凸的假設(shè)下證明了它的收斂性.最后從實(shí)驗(yàn)結(jié)果分析來看,相比于使用固定步長的SARAH算法,新算法的收斂速度更快,并且可以和最優(yōu)步長的SARAH-BB相媲美,不受初始步長選取的影響.新算法對初始步長的選擇是有效的.