基于Polyak步長的隨機遞歸梯度算法

王福勝,李曉桐

(太原師范學院數學與統計學院,山西 晉中 030619)

1.引言

在機器學習中,經常會出現以下的優化問題:

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

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

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

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

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

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

2.算法

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

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

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

再根據文[13]中引理8.11有

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

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

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

文[14]構建了一個簡單函數h,通過下式計算步長

函數h有不同的形式:

因為在早期迭代中,可以選取較大步長加速收斂,然后逐漸選擇較小步長防止振蕩.因此,當選取h=g(k)時,可以令g(k)是關于外循環數k的單調遞增函數.文[14] 中的算法(SARAH-AS)選取函數的具體形式如下:

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

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

下面我們將上述Polyak步長與隨機遞歸梯度下降算法相結合構造成新的算法,算法框架見算法2.

3.收斂性分析

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

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

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

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

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

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

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

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

證根據目標函數F(x)的強凸性以及?F(x?)=0,可知

上式蘊含算法2具有R-線性收斂速度.

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

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

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

4.數值實驗

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

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

圖4.1 heart上的殘差損失

表4.1 數值實驗中使用的數據集和正則化參數

圖4.1到圖4.6展示了SARAH-BB,SARAH 以及SARAH-Polyak三個算法在數據集heart,splice和ijcnn1上的殘差損失及步長變化趨勢.在所有的圖中,藍色,紅色和綠色實線代表不同步長的SARAH-Polyak 算法;黑色實線代表最優步長的SARAH-BB算法;藍色,紅色和綠色虛線對應著固定步長的SARAH算法.在所有的圖中,x軸代表外循環數,圖4.1,4.3和圖4.5中y軸表示最優間隔，即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 算法快,并且當選擇不同的初始步長η0時,SARAH-Polyak算法的收斂性能不受影響.并且SARAH-Polyak與最優步長的SARAH-BB算法相差不大.圖4.2,4.4和4.6中可以看出: 當選取不同的初始步長時,SARAH-Polyak算法的步長最終收斂于最優步長的鄰域.

5.結論

在本文中,我們提出了一種改進的算法SARAH-Polyak.首先我們用理論說明Polyak步長并沒有增加算法的復雜度,因為該算法已經計算出全梯度,并且可以通過其他算法得到最優值.然后分別在強凸和一般凸的假設下證明了它的收斂性.最后從實驗結果分析來看,相比于使用固定步長的SARAH算法,新算法的收斂速度更快,并且可以和最優步長的SARAH-BB相媲美,不受初始步長選取的影響.新算法對初始步長的選擇是有效的.