錢玉香,趙 勇,楊 帆

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

0 引 言

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

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

(1)

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

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

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

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

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

1 基本符號與定義

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

為g在x處的次微分。

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

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

定義3[16]對于一個(gè)凸函數(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]為

但是使用全梯度導(dǎo)致計(jì)算成本非常昂貴,故利用隨機(jī)梯度代替全梯度,有

其中γ為正常數(shù)。受到BB步長成功應(yīng)用于隨機(jī)優(yōu)化算法的啟發(fā)[11-13],將改進(jìn)的BB步長與近端隨機(jī)遞歸動(dòng)量(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)造一個(gè)Lyapunov輔助函數(shù)

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

證畢。

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

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

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

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

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

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

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

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

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

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

實(shí)驗(yàn)結(jié)果:

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

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

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