基于BB步長的近端隨機遞歸動量算法

錢玉香,趙 勇,楊 帆

(重慶交通大學數學與統計學院,重慶 400074)

0 引 言

本文考慮如下的復合優化問題:

minx∈dΨ(x)=f(x)+g(x) ,

(1)

為了有效求解復合優化問題(1),國內外學者提出了諸多高效的算法。FUKUSHIMA等[3]提出的近端梯度下降(ProxGD)算法是解決該類問題的一種經典算法,其主要迭代步驟為:

xt=proxηg(xt-1-η?f(xt-1)) ,

其中η>0為步長。當樣本數據非常大時,ProxGD算法每一步的計算成本都非常昂貴。因此,GHADIMI[4]用隨機梯度代替全梯度,提出了近端隨機梯度下降(ProxSGD)算法。但隨機采樣的方式引入了隨機誤差,限制了該算法的收斂速度。XIAO和ZHANG[5]提出了一種近端隨機方差縮減(ProxSVRG)算法來提高ProxSGD算法的收斂速度。NGUYEN等[6]提出了一種近端隨機遞歸梯度(ProxSARAH)算法并達到了相同的效果。此外,CUTKOSKY和ORABONA[7]提出了一種隨機遞歸動量(STORM)算法求解非凸優化問題,該算法結合動量遞歸技術和自適應步長來實現方差縮減的效果。WANG和WEN[8]將動量遞歸技術與近端梯度算法結合,提出了求解非凸非光滑復合優化問題的近端隨機遞歸動量(ProxSTORM)算法。

眾所周知,步長是影響梯度類算法收斂速度的一個關鍵因素。在大多數隨機算法中,通常采用兩種步長策略:1)固定步長,需要手動調整參數以達到最佳性能;2)衰減步長,但是當迭代接近最小值時,可能會降低算法性能。為了解決這一問題,TAN等[9]將Barzilai-Borwein(BB)步長[10]應用到SVRG中,提出了SVRG-BB 算法求解強凸優化問題,并且通過數值實驗驗證了SVRG-BB算法具有良好的算法性能,可以達到與使用最佳步長的SVRG算法相同甚至更好的效果。YANG等[11]將BB 步長與mS2GD算法結合,提出mS2GD-BB算法,并證明了mS2GD-BB算法對于非光滑強凸目標函數在期望意義下是線性收斂的。為了進一步提高小批量算法的收斂速度,YANG等[12]將改進的BB步長(RBB)與Acc-ProxSVRG算法結合,提出Acc-ProxSVRG-RBB算法求解強凸優化問題,BB步長的使用解決了參數調優的困難并達到了與這些算法使用最佳步長時相同甚至更好的收斂速度。然而,當目標函數非凸時,使用BB步長或RBB步長導致分母可能接近零,甚至為負。故上述算法不能有效求解非凸問題。因此,MA等[13]提出SVRG-SBB算法求解隨機非凸嵌入問題,該算法將SBB步長和SVRG算法結合并通過數值實驗驗證了算法的有效性。但是計算步長時,SBB步長使用全梯度,導致計算成本較昂貴。

受文獻[11-13]的啟發,本文將改進的SBB步長與ProxSTORM算法結合,提出ProxSTORM-BB算法求解非凸非光滑復合優化問題。然后,在合適的假設條件下證明了算法的收斂性。最后,通過數值實驗驗證了算法的有效性。

1 基本符號與定義

定義1[14]設g:d→d∪{∞}是適定的下半連續凸函數,對x∈domg,定義

為g在x處的次微分。

定義2[15]定義廣義梯度為

其中,ηt表示第t次迭代的步長。當g≡0時,Gηt(x)=?f(x)。

定義3[16]對于一個凸函數g,定義它的鄰近算子為

假設1 設?fi(x),i∈[n]是利普希茨(Lipschitz)連續的,其中利普希茨常數L>0,即

‖?fi(y)-?fi(x)‖≤L‖y-x‖, ?x、y∈d。

假設2 存在σ∈[0,+∞),使得

E[‖?fi(x)-f(x)‖2]≤σ2, ?x∈d,i∈[n] 。

2 ProxSTORM-BB算法

經典的BB步長[10]為

但是使用全梯度導致計算成本非常昂貴,故利用隨機梯度代替全梯度,有

其中γ為正常數。受到BB步長成功應用于隨機優化算法的啟發[11-13],將改進的BB步長與近端隨機遞歸動量(ProxSTORM)算法相結合,提出了ProxSTORM-BB算法求解問題(1)。具體算法框架如下:

3 收斂性分析

下面來分析ProxSTORM-BB算法的收斂性,首先介紹本節將用到的引理。

引理1假設1～2成立,{vt}是由算法1產生的,其中a∈(0,1),則

E[‖vt-?f(xt)‖2]≤(1-a)2E[‖vt-1-?f(xt-1)‖2]

基于上述引理,建立ProxSTORM-BB算法的收斂性。

證明:由xt+1的定義和g的凸性可得,對?y∈d,有

令y=proxηtg(xt-ηt?f(xt)),由近端算子的最優性條件[16]可得

即

由于?f是Lipschitz連續的,則

再結合Ψ(x)和Gηt(x)的定義并取全期望, 有

其中最后一步不等式由2ab≤a2+b2和Gηt(x)的定義可得。

接下來分析ηt的取值范圍

結合假設2可知,

下面,我們構造一個Lyapunov輔助函數

其中ξ>L+γ。由R(xt+1)的定義可得

證畢。

4 數值實驗

本節通過數值實驗來驗證ProxSTORM-BB算法的有效性。我們主要考慮了2個例子,所有的實驗均是在MATLAB 2019a,Windows10系統下進行的。計算機基本參數為AMD Ryzen 5 5500U @2.10 GHz 和16 GB內存。其中“loss”代表求解目標函數所得的殘差損失(目標函數值減去最優值),“CPU time”表示程序運行的時間,單位為秒。在實驗中固定批量大小b=20,并且選擇CINA.test(n=3 206;d=132)和a9a.test(n=16 281;d=122)為數據集。

例1[17]考慮如下非凸非光滑復合優化問題:

首先,為了驗證ProxSTORM-BB算法的有效性,將ProxSTORM-BB算法和使用固定步長的ProxSTORM算法進行對比。同時為了使實驗結果更加準確,其他參數(小批量b和動量參數a)的設定均相同,并且在實驗中兩個算法的初始步長均選取η0=0.015。實驗結果如圖 1所示。

下面,驗證初始步長對ProxSTORM-BB算法的影響。在保證其他參數相同的情況下,選取了3個相差較大的初始步長:η0=0.009,η0=0.015和η0=0.1,在不同的數據集上進行實驗。 實驗結果如圖2所示。

最后,為了比較ProxSTORM-BB算法與其他算法的性能,將ProxSTORM-BB算法、 ProxSGD算法和ProxSVRG算法在不同的數據集上進行了對比。為了使結果更加準確,在ProxSVRG算法中,選取小批量b=20。實驗結果如圖3所示。

例2考慮如下非凸非光滑復合優化問題:

與例1類似,為了驗證ProxSTORM-BB算法的有效性,將ProxSTORM-BB算法和使用固定步長的ProxSTORM算法進行對比。實驗結果如圖4所示。

下面,同樣在保證其他參數相同情況下,選取了3個相差較大的初始步長:η0=0.009,η0=0.015和η0=0.1,在不同的數據集上進行實驗來驗證初始步長對ProxSTORM-BB算法的影響。實驗結果如圖 5所示。

最后,將ProxSTORM-BB算法、ProxSGD算法和ProxSVRG算法在不同的數據集上進行了對比。實驗結果如圖6所示。

實驗結果:

1)在圖1和圖 4中,x軸代表CPU時間,y軸代表求解目標函數所得的殘差損失。由圖1和圖4可知,對于例1和例2,在不同的數據集上,ProxSTORM-BB算法和使用固定步長的ProxSTORM算法相比,都達到了相同甚至更好的效果。在相同的CPU時間下,ProxSTORM-BB算法使相應問題的目標函數值下降更快,有更小的殘差損失,這驗證了我們所提出算法的有效性。

圖1 BB步長與固定步長對比Fig.1 Comparison of BB step size and fixed step size

圖2 不同初始步長對比Fig.2 Comparison of different initial steps

圖4 BB步長與固定步長對比Fig.4 Comparison of BB step size and fixed step size

2)由圖2和圖5可知,針對例1和例2,在數據集CINA上,不同的初始步長對ProxSTORM-BB算法的影響很小;在數據集a9a上,不同的初始步長對ProxSTORM-BB算法的影響幾乎可以忽略。因此,ProxSTORM-BB算法對于初始步長的選取具有魯棒性。

圖5 不同初始步長對比Fig.5 Comparison of different initial steps

3)在圖3和圖6中,x軸代表CPU時間,y軸代表求解目標函數所得的殘差損失。由圖3和圖6可知,對于例1和例2,在不同的數據集上,ProxSTORM-BB算法都使相應問題的目標函數值下降更快。在相同的CPU時間下,有更小的殘差損失,實現了更快的收斂速度。因此,ProxSTORM-BB算法具有更好的性能。

圖6 與其他算法對比Fig.6 Comparison with other algorithms