程禹嘉 陶 蔚 劉宇翔 陶 卿

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

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

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

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

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

本文的主要工作有3個方面：

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

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

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

1 典型動量方法的收斂性介紹

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

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

(1)

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

(2)

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

(3)

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

(4)

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

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

(5)

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

(6)

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

(7)

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

(8)

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

(9)

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

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

(10)

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

文獻[19]通過在投影次梯度上進行了線性插值的操作：

(11)

(12)

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

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

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

(13)

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

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

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

具體證明見附錄1.

具體證明見附錄2.

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

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

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

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

(14)

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

(15)

其中i為迭代到第t步時隨機抽取的樣本序號.

(16)

算法1.隨機Heavy-ball算法.

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

輸出:wt.

① 初始化向量w1=0；

② Fork=1 tot

④ 隨機選取i∈{1,2,…,m}；

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

⑦ End For

3 實 驗

本節(jié)對算法1的個體收斂速率及其稀疏性的理論分析進行實驗驗證.

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

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

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

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

3.2 實驗方法及結(jié)論

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

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

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

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

4 結(jié) 論

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