丁成誠(chéng) 陶 蔚 陶 卿

1(中國(guó)人民解放軍陸軍炮兵防空兵學(xué)院信息工程系 合肥 230031)2(中國(guó)人民解放軍陸軍工程大學(xué)指揮控制工程學(xué)院 南京 210007)(dcc18851507462@163.com)

無(wú)論是經(jīng)典的正則化損失函數(shù)框架,如稀疏學(xué)習(xí)和支持向量機(jī),還是當(dāng)前的研究熱點(diǎn)深度學(xué)習(xí),如卷積和遞歸神經(jīng)網(wǎng)絡(luò),都可以視為給定模型空間的參數(shù)尋優(yōu)問(wèn)題,隨機(jī)梯度下降法(stochastic gradient descent, SGD)是解決這類參數(shù)尋優(yōu)問(wèn)題簡(jiǎn)單而又有效的方法.為了獲得更好的收斂性能,人們開(kāi)始在SGD的基礎(chǔ)上使用動(dòng)量方法.

動(dòng)量實(shí)際上是物理學(xué)中的一個(gè)概念,動(dòng)量原理告訴我們運(yùn)動(dòng)的物體會(huì)因?yàn)閼T性繼續(xù)保持運(yùn)動(dòng),除非受到外力作用而停下來(lái).在優(yōu)化算法中,動(dòng)量方法可以在梯度很小的情形下仍然保持更新,從而可以加速SGD在求解凸優(yōu)化問(wèn)題時(shí)的收斂速率[1-3],幫助SGD在求解非凸優(yōu)化問(wèn)題時(shí)擺脫局部最優(yōu)點(diǎn)[4-5].對(duì)于隨機(jī)優(yōu)化問(wèn)題,由于動(dòng)量可以分解成過(guò)往梯度加權(quán)平均的方式,因此比SGD具有更小的方差,據(jù)此使算法獲得了更好的收斂性和穩(wěn)定性[6].

我們通常討論的動(dòng)量方法有2種標(biāo)準(zhǔn)形式：一種是由Polyak于1964年提出HB(heavy ball)方法[7]；另一種是Nesterov于1983年提出的NAG(Nesterov’s accelerated gradient)方法[8].HB的加速性主要體現(xiàn)在目標(biāo)函數(shù)強(qiáng)凸且二次可微時(shí),盡管與梯度下降法、NAG具有相同的線性收斂速率,但HB具有最小的收斂因子.NAG的加速性主要體現(xiàn)在求解凸光滑目標(biāo)函數(shù)時(shí),可以將梯度下降法的收斂速率加速至最優(yōu)O(1t2),其中t是迭代步數(shù).對(duì)于非光滑凸優(yōu)化問(wèn)題,SGD，HB和NAG具有相同的最優(yōu)平均收斂速率,但對(duì)于個(gè)體收斂性,HB和NAG也具有加速效果,可將SGD的個(gè)體收斂速率從O(log加速至最優(yōu)的[1-2].

在深度神經(jīng)網(wǎng)絡(luò)訓(xùn)練中,使用動(dòng)量?jī)?yōu)化方法替代無(wú)法選取合適步長(zhǎng)的SGD,已經(jīng)在計(jì)算機(jī)視覺(jué)等方面取得了很好的效果[9].Ochs等人通過(guò)實(shí)驗(yàn)驗(yàn)證了批處理形式的HB方法能夠逃離局部最小值點(diǎn)[4].2019年Sun等人從理論上證明了HB方法比GD方法有更大的步長(zhǎng)從而可以逃避鞍點(diǎn)[5].而NAG也表現(xiàn)不凡,可以提高RNN在許多任務(wù)中的性能[10].

目前,人們已經(jīng)將典型的動(dòng)量?jī)?yōu)化方法寫(xiě)進(jìn)了深度學(xué)習(xí)的優(yōu)化器中.隨著優(yōu)化方法進(jìn)一步發(fā)展,出現(xiàn)了眾多形式的動(dòng)量方法.典型的有2016年Lessard等人提出的SNV(synthesized Nesterov variants)[11]、2018年Kidambi等人的AccSGD(accelerated SGD)[12]、Bryan等人的Triple動(dòng)量方法[13]以及Cyrus等人提出的Robust動(dòng)量方法[14]等等.

綜上,無(wú)論是從理論分析還是從理解動(dòng)量在優(yōu)化算法中作用的角度來(lái)看,建立一個(gè)統(tǒng)一的動(dòng)量方法的一般框架都是十分必要的.實(shí)際上,早在2013年,Sutskever等人就發(fā)現(xiàn)HB方法和NAG方法的區(qū)別僅僅在于計(jì)算梯度的點(diǎn)選取不同[15]；通過(guò)引入中間變量,Yang等人于2016年提出了一種隨機(jī)統(tǒng)一化動(dòng)量方法(stochastic unified momentum, SUM),統(tǒng)一了SGD，HB和NAG[16];2019年Ma等人提出了QHM(quasi-hyperbolic momentum)方法,其迭代步驟可以表示成SGD與動(dòng)量緩沖項(xiàng)的一種加權(quán)平均方式.QHM通過(guò)使用動(dòng)量緩沖和加權(quán)SGD的2個(gè)折中參數(shù)將AccSGD，Triple，Robust等形式的動(dòng)量方法進(jìn)行統(tǒng)一[6].顯然,SUM和QHM在統(tǒng)一化動(dòng)量方法上的思路是不同的.

動(dòng)量方法在有效提高SGD收斂性能的同時(shí),也存在一些令人質(zhì)疑的地方,即由于動(dòng)量改變了SGD中梯度下降的操作,是否還能保持SGD原有的收斂性能?具體來(lái)說(shuō),對(duì)于非光滑凸問(wèn)題,我們首先應(yīng)該證明動(dòng)量方法具有和SGD一樣的最優(yōu)平均收斂速率.但遺憾的是目前的研究還存在一些欠缺.特別地,對(duì)于非光滑凸目標(biāo)函數(shù),盡管SUM得到了最優(yōu)的O(1t)平均收斂速率[16],但其使用的步長(zhǎng)嚴(yán)重依賴預(yù)先設(shè)定的迭代步數(shù),這種固定總迭代步數(shù)的方法在處理大規(guī)模數(shù)據(jù)時(shí)由于不能增量地執(zhí)行算法而缺少實(shí)用性.另一方面,QHM雖然在實(shí)驗(yàn)中的性能超越了HB和NAG,但只討論了光滑情況下的收斂性,也沒(méi)有給出具體的收斂速率[6,17].除此以外,這些方法均只適用于無(wú)約束情況,不能用于解決機(jī)器學(xué)習(xí)中如稀疏學(xué)習(xí)導(dǎo)致的有約束問(wèn)題.據(jù)我們所知,目前還沒(méi)有文獻(xiàn)涉及詳細(xì)分析動(dòng)量方法在有約束非光滑情況下的平均收斂性問(wèn)題.

本文的貢獻(xiàn)主要體現(xiàn)在3個(gè)方面:

1) 提出了一種含三參數(shù)的統(tǒng)一化動(dòng)量方法TPUM(triple-parameters unified momentum),通過(guò)取不同的參數(shù),能夠同時(shí)包含SUM和QHM,是目前最一般的動(dòng)量算法的統(tǒng)一框架.

2) 即使是對(duì)特例QHM,本文也給出約束非光滑情形的最優(yōu)平均速率,而QHM目前只有光滑情形下的收斂性結(jié)論.即使是對(duì)特例SUM,本文也去掉了SUM原有收斂性中需要固定迭代步數(shù)和無(wú)約束等不合理限制.

3) 證明了所提出的TPUM方法在求解有約束非光滑凸優(yōu)化問(wèn)題時(shí)具有最優(yōu)的平均收斂速率,并將其推廣到隨機(jī)情況,從而保證了添加動(dòng)量不會(huì)影響標(biāo)準(zhǔn)梯度下降法的收斂性能以及動(dòng)量方法對(duì)機(jī)器學(xué)習(xí)問(wèn)題的可應(yīng)用性.

1 TPUM方法

考慮優(yōu)化問(wèn)題:

minf(x), s.t.x∈Q,

(1)

批處理形式的投影次梯度方法的迭代步驟為

(2)

f(xt)-f(x*),

其中，t是總迭代次數(shù),x*是最優(yōu)解.平均輸出收斂速率的數(shù)學(xué)表達(dá)式為

HB更新為

(3)

其中，αk≥0為步長(zhǎng),β∈[0,1)為動(dòng)量xk-xk-1的系數(shù).

NAG更新為

NAG等價(jià)于:

(5)

其中，s≥0為一常數(shù),不同的s對(duì)應(yīng)不同動(dòng)量方法.

QHM更新如下:

其中，dk稱為動(dòng)量緩沖器.顯然,QHM也是使用當(dāng)前梯度與過(guò)去梯度的凸組合,但由于折中參數(shù)vk，βk的存在,破壞了更容易理解的動(dòng)量項(xiàng)形式β(xk-xk-1),與SUM統(tǒng)一動(dòng)量的出發(fā)點(diǎn)是不同的.

然而,通過(guò)對(duì)文獻(xiàn)[17]的研究發(fā)現(xiàn),動(dòng)量緩沖器與動(dòng)量項(xiàng)β(xk-xk-1)具有密切聯(lián)系,可以推出-αβkdk-1=β(xk-xk-1).正是基于這種聯(lián)系,受SUM統(tǒng)一思路的啟發(fā),本文增加2個(gè)折中參數(shù)δ1，δ2,將QHM和SUM進(jìn)行統(tǒng)一,提出TPUM方法:

其中,步長(zhǎng)αk>0,β∈[0,1)為動(dòng)量系數(shù),δ1,δ2∈[0,1]為折中參數(shù).顯然:

當(dāng)δ1=0，s=0，δ2=1時(shí),TPUM為HB;

當(dāng)δ1=0，s=1，δ2=1時(shí),TPUM為NAG;

當(dāng)δ1=0，δ2=0時(shí),TPUM為梯度下降法;

當(dāng)δ1=1，s=0，δ2≠0，δ2≠1時(shí),TPUM為QHM.

由此可見(jiàn),TPUM是目前最一般的動(dòng)量算法的統(tǒng)一框架.

2 TPUM方法平均收斂性分析

對(duì)于有約束問(wèn)題(1),TPUM更新式(8)可以等價(jià)寫(xiě)成:

其中,P是Q上的投影算子.式(9)等價(jià)于:

(10)

在無(wú)約束情況下,文獻(xiàn)[16]中定義:

一個(gè)直接的優(yōu)勢(shì)就是利用式(11)得到:

(12)

與已知的梯度優(yōu)化方法十分相像[18],由式(12)出發(fā)很容易得到收斂性結(jié)論,也這正是SUM的主要證明思路.然而,這種方法僅對(duì)無(wú)約束有效,且使用的是固定步長(zhǎng),對(duì)于有約束情況的證明將十分困難.

為此,區(qū)別于式(11),修改動(dòng)量項(xiàng)，得到:

pk=b(xk-xk-1),

其中，b為一個(gè)正常數(shù),則

xk+pk=xk+b(xk-xk-1)，
xk+1+pk+1=xk+1+b(xk+1-xk)，
x-(xk+1+pk+1)=x-(b+1)xk+1+bxk，
x-(xk+pk)=x-(b+1)xk+bxk-1.

引理2[19].對(duì)于任意x∈RN,x0∈Q:

x-x0,y-x0≤0

當(dāng)且僅當(dāng)x0=P(x)時(shí),對(duì)所有的y∈Q恒成立.

實(shí)際上,利用約束與投影的關(guān)系,與文獻(xiàn)[18]類似，式(10)中的投影運(yùn)算可以重新定義為一個(gè)優(yōu)化問(wèn)題:

引理3.式(10)等價(jià)于:

(13)

基于上述3條引理及假設(shè)1,可以得到:

對(duì)任意的x∈Q,s≥0,δ1≥0,則

具體證明見(jiàn)附錄A.

通過(guò)重新定義的動(dòng)量項(xiàng)和上述引理,利用凸函數(shù)的性質(zhì),Fenchel-Young不等式,可以得到:

且對(duì)任意t>0,

從定理1中可以看出：

1) TPUM是更為一般的統(tǒng)一化動(dòng)量方法,在非光滑約束情況下可以得到最優(yōu)的平均收斂速率,相比特殊情形的SUM與QHM,TPUM克服了固定步長(zhǎng)及無(wú)約束的缺陷.

2) 如果使用固定的步長(zhǎng),TPUM將與SUM的證明一樣簡(jiǎn)潔,并且同樣可以得到最優(yōu)收斂速率.

3) 文獻(xiàn)[1]證明了在非光滑情形下HB型動(dòng)量對(duì)SGD的個(gè)體收斂性具有加速作用,但其證明主要是針對(duì)無(wú)約束情形,且要求動(dòng)量系數(shù)是時(shí)變的.本文雖然只是得到較弱的平均收斂性,但針對(duì)的是有約束問(wèn)題且考慮的是更一般的統(tǒng)一化動(dòng)量方法.

優(yōu)化目標(biāo)函數(shù)為

(16)

其中i為迭代到第t步時(shí)隨機(jī)抽取的樣本序號(hào).

對(duì)于式(10),TPUM的隨機(jī)形式迭代步驟為

(18)

算法1.隨機(jī)TPUM算法.

輸入:循環(huán)次數(shù)t;

輸出:xt.

① 初始化x1=0,設(shè)定α1,δ1,δ2,s,b;

② Fork=1 tot;

④ 隨機(jī)選取i∈{1,2,…,m};

⑥ 由式(17)計(jì)算xk+1;

⑦ End For

s≥0,δ1≥0,則存在一個(gè)正數(shù)M,使得

且對(duì)任意t>0,

3 實(shí) 驗(yàn)

3.1 實(shí)驗(yàn)?zāi)康?/h3>

本節(jié)通過(guò)求解優(yōu)化問(wèn)題式(16),對(duì)隨機(jī)TPUM式(17)平均收斂速率的理論分析結(jié)果進(jìn)行實(shí)驗(yàn)驗(yàn)證.

主要實(shí)驗(yàn)?zāi)康挠?方面:

2) 為了驗(yàn)證所提出的TPUM具有最優(yōu)平均收斂速率,引入DA(dual averaging)算法[22]與TPUM框架下的SHB，SNAG和QHM進(jìn)行對(duì)比,同時(shí)在6個(gè)數(shù)據(jù)集中各任取了一組超參數(shù)作為T(mén)PUM.DA是一種求解非光滑約束問(wèn)題的經(jīng)典一階優(yōu)化方法[22],具有最優(yōu)的平均收斂速率,因此實(shí)驗(yàn)選取DA作為基準(zhǔn)方法，其參數(shù)選擇參照文獻(xiàn)[22]的定理3.

3.2 實(shí)驗(yàn)數(shù)據(jù)集與方法

實(shí)驗(yàn)采用的是6個(gè)常用的標(biāo)準(zhǔn)數(shù)據(jù)集,這些數(shù)據(jù)集可以在LIBSVM(1)http://www.csie.ntu.edu.tw/～cjlin/libsvm/網(wǎng)站中找到,詳細(xì)描述如表1所示:

Table 1 Description of Standard Datasets表1 標(biāo)準(zhǔn)數(shù)據(jù)庫(kù)描述

為了進(jìn)行公平地比較,所有的實(shí)驗(yàn)都在隨機(jī)示例序列上重復(fù)計(jì)算了10次,取平均值作為最后結(jié)果,最大迭代次數(shù)均設(shè)定為10 000次.在實(shí)驗(yàn)中固定β=0.9,取δ1=0,δ2=1,s=0,s=1分別表示TPUM框架下的SHB與SNAG;δ1=1,δ2=0.5,s=0時(shí)為QHM.6個(gè)數(shù)據(jù)庫(kù)中的TPUM參數(shù)選取如表1所示,分別標(biāo)記為T(mén)PUM1至TPUM6,可以粗略地幫助我們看出3個(gè)參數(shù)的敏感性.

3.3 實(shí)驗(yàn)結(jié)論

圖1為時(shí)變步長(zhǎng)與固定步長(zhǎng)對(duì)于收斂性影響的比較圖,其中帶有time-varying的曲線表示使用的是時(shí)變步長(zhǎng).實(shí)驗(yàn)驗(yàn)證,盡管固定步長(zhǎng)在計(jì)算上為常數(shù)更為簡(jiǎn)單,但時(shí)變步長(zhǎng)可以達(dá)到和固定步長(zhǎng)幾乎一致的最優(yōu)收斂速率.而在實(shí)際的機(jī)器學(xué)習(xí)問(wèn)題中,如果數(shù)據(jù)集樣本發(fā)生變化,或者處理大規(guī)模數(shù)據(jù)時(shí),使用時(shí)變步長(zhǎng)的方法無(wú)疑更具有實(shí)用性.

Fig. 1 Comparison of convergence rates with time-varying and constant step sizes圖1 時(shí)變步長(zhǎng)與固定步長(zhǎng)收斂速率比較圖

圖2為所提TPUM收斂性比較圖.如圖所示,在有約束情況下,從添加不同超參數(shù)的TPUM曲線可以看出，整體的收斂趨勢(shì)沒(méi)有改變.與現(xiàn)有的DA方法相比,TPUM方法的幾種變體,即SHB，SNAG和QHM與TPUM均有一致的收斂趨勢(shì),在迭代8 000步后，5種算法基本都能達(dá)到10-2的精度,這與本文的理論分析結(jié)果是吻合的,說(shuō)明了TPUM具有最優(yōu)平均收斂速率.

Fig. 2 Comparison of convergence rates圖2 收斂速率比較圖

4 結(jié) 論

本文提出了一種更一般的統(tǒng)一化動(dòng)量方法TPUM,包括了目前典型的統(tǒng)一框架SUM和QHM.其次,證明了所提出的TPUM方法在約束情況下具有最優(yōu)的平均收斂速率,從而保證了添加動(dòng)量不會(huì)影響標(biāo)準(zhǔn)梯度下降法的收斂性能以及動(dòng)量方法對(duì)機(jī)器學(xué)習(xí)問(wèn)題的可應(yīng)用性.

眾所周知,相比于平均輸出,個(gè)體輸出具有更好的稀疏性,但個(gè)體收斂性較難獲得.目前對(duì)于HB，NAG的個(gè)體收斂性已經(jīng)有所突破[1-3].能否得到TPUM的個(gè)體收斂性結(jié)論顯然值得考慮.另一方面,2015年Kingma等人提出一種Adam(adaptive moment estimation)方法,實(shí)際上是在HB基礎(chǔ)上對(duì)步長(zhǎng)的設(shè)置加以改進(jìn),以得到更好的收斂性能,目前在深度學(xué)習(xí)中被廣泛使用[24],而QHM與Adam的結(jié)合也已經(jīng)有所研究[6].將本文提出的TPUM與Adam結(jié)合,進(jìn)一步提升動(dòng)量方法在深度學(xué)習(xí)中的性能將是我們下一步的研究方向.