錢玉香,趙 勇,楊 帆

(重慶交通大學數(shù)學與統(tǒng)計學院,重慶 400074)

0 引 言

本文考慮如下的復(fù)合優(yōu)化問題:

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

(1)

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

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

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

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

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

1 基本符號與定義

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

為g在x處的次微分。

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

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

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

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

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

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

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

2 ProxSTORM-BB算法

經(jīng)典的BB步長[10]為

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

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

3 收斂性分析

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

引理1假設(shè)1～2成立,{vt}是由算法1產(chǎn)生的,其中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)),由近端算子的最優(yōu)性條件[16]可得

即

由于?f是Lipschitz連續(xù)的,則

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

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

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

結(jié)合假設(shè)2可知,

下面,我們構(gòu)造一個Lyapunov輔助函數(shù)

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

證畢。

4 數(shù)值實驗

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

例1[17]考慮如下非凸非光滑復(fù)合優(yōu)化問題:

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

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

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

例2考慮如下非凸非光滑復(fù)合優(yōu)化問題:

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

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

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

實驗結(jié)果:

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

圖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,在數(shù)據(jù)集CINA上,不同的初始步長對ProxSTORM-BB算法的影響很小;在數(shù)據(jù)集a9a上,不同的初始步長對ProxSTORM-BB算法的影響幾乎可以忽略。因此,ProxSTORM-BB算法對于初始步長的選取具有魯棒性。

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

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

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