Heavy-Ball型動(dòng)量方法的最優(yōu)個(gè)體收斂速率

程禹嘉 陶 蔚 劉宇翔 陶 卿

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

機(jī)器學(xué)習(xí)問(wèn)題普遍可以轉(zhuǎn)化為求解目標(biāo)函數(shù)最小值的優(yōu)化問(wèn)題，一階梯度優(yōu)化方法由于具有算法簡(jiǎn)單、迭代成本小等特點(diǎn)，成為處理大規(guī)模數(shù)據(jù)問(wèn)題的首要選擇.在此基礎(chǔ)上發(fā)展起來(lái)的隨機(jī)優(yōu)化方法由于避免了每一次迭代都需要遍歷整個(gè)樣本集，充分利用訓(xùn)練樣本集合的冗余性，從而具有計(jì)算代價(jià)低和實(shí)際收斂速率快等優(yōu)點(diǎn)，已經(jīng)成為處理大規(guī)模機(jī)器學(xué)習(xí)問(wèn)題的實(shí)用方法[1].

動(dòng)量方法是在經(jīng)典梯度下降方法的基礎(chǔ)上通過(guò)添加動(dòng)量而獲得的一種特殊的一階優(yōu)化方法.研究者將動(dòng)量算法分為2類：一類是Polyak于1964年提出的Heavy-ball型動(dòng)量方法[2],另一類是1983年Nesterov提出的NAG(Nesterov accelerated gradient)型動(dòng)量方法[3].這2類算法的主要差別在于所使用動(dòng)量項(xiàng)的不同，前者只是使用了前一步的迭代信息而后者引入了當(dāng)前步迭代算法的二階信息.對(duì)于不同條件下的優(yōu)化問(wèn)題，這2類算法的收斂性也有不同的表現(xiàn).當(dāng)目標(biāo)函數(shù)光滑時(shí)，NAG具有最優(yōu)的O(1/t2)收斂速率[3]，其中t為算法的迭代步數(shù).當(dāng)目標(biāo)函數(shù)強(qiáng)凸且二次可微時(shí)，盡管Heavy-ball型動(dòng)量方法、梯度下降法和NAG方法都具有相同的線性收斂速率，但Heavy-ball型動(dòng)量方法具有最小的收斂因子[2].隨機(jī)動(dòng)量方法被廣泛應(yīng)用于神經(jīng)網(wǎng)絡(luò)的訓(xùn)練，并顯著的提高了其收斂性能[4].

NAG是優(yōu)化領(lǐng)域具有里程碑意義的算法，它填補(bǔ)了Nemirovski與Yudin所證明的“任何一階優(yōu)化算法都不可能得到比O(1/t2)更快的收斂速率[5]”的間隙，也吸引了眾多機(jī)器學(xué)習(xí)研究者的關(guān)注.特別是針對(duì)大規(guī)模具有特定含義的正則化損失函數(shù)優(yōu)化問(wèn)題，研究工作層出不窮.早期重要的工作主要包括只要損失函數(shù)滿足光滑性條件就可得到整個(gè)目標(biāo)函數(shù)光滑時(shí)的最優(yōu)收斂速率[6-7]，以及NAG隨機(jī)形式的最優(yōu)收斂速率等等[8].近期NAG的研究主要集中在與其他優(yōu)化方法的結(jié)合上.如2015年Lin等人基于NAG提出了一種通用的加速策略Catalyst[9]，在目標(biāo)函數(shù)強(qiáng)凸的條件下將批處理優(yōu)化方法、坐標(biāo)優(yōu)化方法和增量?jī)?yōu)化算法進(jìn)行了加速.最近，Allen-Zhu引入帶有動(dòng)量參數(shù)的方差項(xiàng)，提出了著名的Katyusha算法[10]，成功地將方差減少方法與NAG相結(jié)合.2018年Shang等人將NAG算法與Mixed Optimization算法相結(jié)合，僅使用了一個(gè)動(dòng)量項(xiàng)就取得了與Katyusha算法相同的收斂速率[11-12].

與標(biāo)準(zhǔn)的梯度下降法相較，Heavy-ball型動(dòng)量方法在目標(biāo)函數(shù)在某些方向變化較弱而在另一些方向變化很強(qiáng)的時(shí)候，可以取得好的加速效果，復(fù)雜度卻幾乎沒有增加.但與NAG方法相比，Heavy-ball型動(dòng)量方法的研究卻屈指可數(shù).2014年Ghadimi等人對(duì)Heavy-ball方法的收斂性進(jìn)行了深入的研究，給出了目標(biāo)函數(shù)光滑條件下的平均和個(gè)體收斂速率[13]，但均未達(dá)到最優(yōu).2016年Yang等人建立了一種含有多種參數(shù)的算法框架，統(tǒng)一處理了梯度下降法、Heavy-ball方法以及NAG方法[14]，在該框架中設(shè)置不同的參數(shù)即可得到不同的優(yōu)化算法.這種統(tǒng)一的算法對(duì)于非光滑優(yōu)化問(wèn)題在平均輸出方式下具有最優(yōu)的收斂速率.

本文的主要工作有3個(gè)方面：

1) 對(duì)于非光滑優(yōu)化問(wèn)題，證明了Heavy-ball型動(dòng)量方法具有最優(yōu)的個(gè)體收斂速率.據(jù)我們所知，這一結(jié)果填補(bǔ)了Heavy-ball型動(dòng)量方法在非光滑情形下個(gè)體最優(yōu)收斂性研究的缺失，有助于更全面地理解Heavy-ball型動(dòng)量方法，也說(shuō)明了在處理非光滑問(wèn)題時(shí)Heavy-ball型動(dòng)量方法和NAG具有同樣的重要地位.

2) 本文證明基于光滑情形下Heavy-ball型動(dòng)量方法的收斂性分析[13]，但不同的是，為得到非光滑情形下的個(gè)體最優(yōu)收斂速率，我們巧妙構(gòu)造了步長(zhǎng)和動(dòng)量權(quán)重的迭代方式，同時(shí)利用Zinkevich在處理在線優(yōu)化方法收斂性使用的技巧[22]，避免了變步長(zhǎng)和權(quán)重導(dǎo)致的遞歸問(wèn)題.

3) 通過(guò)典型的稀疏優(yōu)化問(wèn)題實(shí)驗(yàn)，驗(yàn)證了理論分析的正確性以及所提算法在保持稀疏性方面的良好性能.

1 典型動(dòng)量方法的收斂性介紹

本節(jié)我們對(duì)2種動(dòng)量方法的收斂性以及它們之間的聯(lián)系和區(qū)別進(jìn)行必要的介紹.

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

(1)

其中，f(w)為凸函數(shù)，Q?Rn是有界閉凸集合，記w*為式(1)的一個(gè)最優(yōu)解.批處理形式投影次梯度方法的迭代步驟為

(2)

Agarwal等人給出非光滑條件下式(2)的平均收斂速率為[25]

(3)

式(2)的個(gè)體收斂速率由Shamir和Zhang Tong證得[18]：

(4)

這與最優(yōu)速率之間還是存在著數(shù)量級(jí)上的差距.

Yang等人建立了隨機(jī)梯度下降法與隨機(jī)動(dòng)量方法的統(tǒng)一框架[14]：

(5)

其中,β為動(dòng)量參數(shù)，s≥0.隨著s由大至小，式(5)依次變?yōu)?/p>

(6)

2) 當(dāng)s=1時(shí)，即為NAG方法：

(7)

3) 當(dāng)s=0時(shí)，即為Heavy-ball方法：

(8)

通過(guò)選取適當(dāng)?shù)牟介L(zhǎng)，文獻(xiàn)[14]給出了平均收斂速率：

(9)

在光滑目標(biāo)函數(shù)條件下，由于NAG方法進(jìn)行每一步迭代時(shí)都會(huì)使用之前迭代的部分甚至全部信息，所以通?？梢匀〉幂^Heavy-ball方法更快的收斂速率.當(dāng)目標(biāo)函數(shù)光滑且強(qiáng)凸時(shí)，梯度下降方法、Heavy-ball方法與NAG均可以達(dá)到線性收斂，即：

f(wt)-f(w*)≤qt[f(w0)-f(w*)],

(10)

但Heavy-ball方法獲得的收斂因子q是最小的[13].

文獻(xiàn)[19]通過(guò)在投影次梯度上進(jìn)行了線性插值的操作：

(11)

(12)

其中,θt與ηt為步長(zhǎng)參數(shù)，與線性插值技巧不同的是該方法每一步的解都是通過(guò)投影直接得到，因此可以得到良好的稀疏效果.與之類似，Heavy-ball方法的個(gè)體解也應(yīng)當(dāng)具備稀疏性.

2 個(gè)體最優(yōu)收斂性分析

本節(jié)給出Heavy-ball方法在目標(biāo)函數(shù)非光滑條件下的個(gè)體收斂性證明.

(13)

從式(13)可以看出，Heavy-ball型動(dòng)量方法是在梯度下降法基礎(chǔ)上添加了動(dòng)量項(xiàng)pt.正是由于與梯度下降法的這種相似性，使得梯度下降法的收斂分析思路也可以用于Heavy-ball方法.

值得注意的是，文獻(xiàn)[13]將α和β均設(shè)定為常數(shù)，但對(duì)于非光滑優(yōu)化問(wèn)題，這樣的選取辦法無(wú)法獲得個(gè)體收斂速率.因此我們選取了時(shí)變的α與β，但此時(shí)又會(huì)導(dǎo)致式(13)的迭代關(guān)系不成立.為了解決這個(gè)問(wèn)題，我們?cè)O(shè)置pt=t(wt-wt-1)，通過(guò)巧妙地選取αt和βt(見定理1)，我們得到：

基于這個(gè)關(guān)系式，我們可以證明定理1.為了解決變步長(zhǎng)和權(quán)重導(dǎo)致的遞歸問(wèn)題，我們先證明引理1.

具體證明見附錄1.

具體證明見附錄2.

僅考慮二分類問(wèn)題，假設(shè)訓(xùn)練樣本集

S={(xi,yi)|i=1,2,…,m}?Rn×{+1,-1},

其中(xi,yi)是獨(dú)立同分布的.

考慮非光滑稀疏學(xué)習(xí)問(wèn)題的損失函數(shù)為“hinge損失”，即fi(w)=max{0,1-yiw,xi}的優(yōu)化目標(biāo)函數(shù)為

(14)

約束情況下隨機(jī)形式的Heavy-ball算法的迭代步驟自然可以表示為

(15)

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

(16)

算法1.隨機(jī)Heavy-ball算法.

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

輸出:wt.

① 初始化向量w1=0；

② Fork=1 tot

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

⑥ 由式(15)計(jì)算wk+1；

⑦ End For

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

本節(jié)對(duì)算法1的個(gè)體收斂速率及其稀疏性的理論分析進(jìn)行實(shí)驗(yàn)驗(yàn)證.

3.1 實(shí)驗(yàn)數(shù)據(jù)集和比較算法

實(shí)驗(yàn)所采用的6個(gè)常用標(biāo)準(zhǔn)數(shù)據(jù)集，分別為ijcnn1,covtype,a9a,CCAT,RCV1,astro-physic.數(shù)據(jù)集來(lái)源于LIBSVM網(wǎng)站[注]https:www.csie.ntu.edu.tw～cjlinlibsvm.表1給出了這6個(gè)數(shù)據(jù)集的詳細(xì)描述.

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

實(shí)驗(yàn)采用5種隨機(jī)優(yōu)化方法進(jìn)行比較，這些方法分別為平均形式輸出的標(biāo)準(zhǔn)投影次梯度方法[25,27]、線性插值投影次梯度方法[19]、NAG方法[20]、平均形式輸出的Heavy-ball方法[14]以及個(gè)體形式輸出的Heavy-ball方法.從理論分析的角度來(lái)說(shuō)，這5種隨機(jī)優(yōu)化方法的收斂速率均達(dá)到了最優(yōu).但在稀疏性方面，個(gè)體形式輸出的Heavy-ball方法與NAG方法應(yīng)該具有較好的表現(xiàn)，而平均形式輸出的Heavy-ball方法、線性插值投影次梯度方法與標(biāo)準(zhǔn)的投影次梯度方法的稀疏性應(yīng)該較差.

3.2 實(shí)驗(yàn)方法及結(jié)論

圖1為5種算法的收斂速率對(duì)比圖，其中縱坐標(biāo)表示當(dāng)前目標(biāo)函數(shù)值與目標(biāo)函數(shù)最優(yōu)值之差.粉色實(shí)線與藍(lán)色實(shí)線分別表示標(biāo)準(zhǔn)的投影次梯度方法與平均形式輸出的Heavy-ball方法的收斂趨勢(shì)，青綠色虛線與紅色虛線表示線性插值投影次梯度方法與NAG方法的收斂趨勢(shì)，綠色虛線則表示本文提出的以個(gè)體形式輸出的Heavy-ball方法的收斂趨勢(shì).從圖1可以看出，5種算法在6個(gè)標(biāo)準(zhǔn)數(shù)據(jù)集上運(yùn)行了約5 000步之后，基本都達(dá)到10-2的精度，可以說(shuō)均表現(xiàn)出基本相同的收斂趨勢(shì)，這與理論分析的結(jié)果是吻合的.

圖2給出了5種算法在6個(gè)標(biāo)準(zhǔn)數(shù)據(jù)集上的稀疏性對(duì)比，縱坐標(biāo)表示各算法對(duì)應(yīng)輸出方式的稀疏度.稀疏性通過(guò)稀疏度來(lái)衡量，稀疏度是指變量中非零向量所占的百分比，所以稀疏度越高則稀疏性越差.從圖2可以看出，線性插值投影次梯度方法雖然以個(gè)體形式輸出，但稀疏性較差.而Heavy-ball方法與NAG方法個(gè)體解的稀疏度近乎相同，且都明顯低于以平均形式輸出的投影次梯度方法及Heavy-ball方法.由此可知，Heavy-ball方法的個(gè)體輸出較好的保留了個(gè)體收斂在稀疏性上獨(dú)具的優(yōu)勢(shì).

另外，從圖2中還可以看出，對(duì)于維數(shù)較低的前3個(gè)數(shù)據(jù)庫(kù)，個(gè)體解的稀疏性明顯優(yōu)于平均解，基本接近數(shù)據(jù)集的稀疏度(見表1所示)，這充分說(shuō)明個(gè)體解比平均解能更好地描述樣本集的稀疏性.但個(gè)體解的稀疏度卻存在著震蕩現(xiàn)象，這主要是由于算法的隨機(jī)性和稀疏度的分母較小導(dǎo)致的.對(duì)維數(shù)較高的后3個(gè)數(shù)據(jù)集，個(gè)體解同樣可以描述數(shù)據(jù)集的稀疏度，但稀疏度已經(jīng)不再震蕩，與平均解一樣平穩(wěn).

Fig. 1 Comparison of convergence rate圖1 收斂速率比較圖

4 結(jié) 論

與其他優(yōu)化方法相比，Heavy-ball型動(dòng)量?jī)?yōu)化方法目前所知的主要優(yōu)勢(shì)是在目標(biāo)函數(shù)強(qiáng)凸且二次可微的條件下獲得的收斂速率是最快的.本文對(duì)非光滑條件下Heavy-ball型動(dòng)量?jī)?yōu)化方法的收斂性進(jìn)行了初步的研究，證明了這種方法可以獲得最優(yōu)的個(gè)體收斂速率.眾所周知，在不改變算法的情況下，梯度下降方法目前最好的個(gè)體收斂速率是Shamir和Zhang得到的與最優(yōu)收斂速率差一個(gè)log因子的個(gè)體收斂速率[18].顯然，本文的結(jié)論表明Heavy-ball型動(dòng)量技巧是對(duì)梯度下降法個(gè)體收斂速率的一種加速策略，并且與NAG方法具有相同的性能.下一步我們將考慮Heavy-ball型動(dòng)量?jī)?yōu)化方法在正則化和強(qiáng)凸條件下的最優(yōu)個(gè)體收斂速率問(wèn)題，我們還會(huì)考慮在隨機(jī)Heavy-ball型動(dòng)量?jī)?yōu)化方法中引進(jìn)方差減少技巧進(jìn)一步提升實(shí)際收斂效果.