Heavy-Ball型動量方法的最優個體收斂速率

程禹嘉 陶 蔚 劉宇翔 陶 卿

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

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

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

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

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

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

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

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

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

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

本節我們對2種動量方法的收斂性以及它們之間的聯系和區別進行必要的介紹.

考慮有約束優化問題:

(1)

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

(2)

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

(3)

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

(4)

這與最優速率之間還是存在著數量級上的差距.

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

(5)

其中,β為動量參數，s≥0.隨著s由大至小，式(5)依次變為

(6)

2) 當s=1時，即為NAG方法：

(7)

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

(8)

通過選取適當的步長，文獻[14]給出了平均收斂速率：

(9)

在光滑目標函數條件下，由于NAG方法進行每一步迭代時都會使用之前迭代的部分甚至全部信息，所以通常可以取得較Heavy-ball方法更快的收斂速率.當目標函數光滑且強凸時，梯度下降方法、Heavy-ball方法與NAG均可以達到線性收斂，即：

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

(10)

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

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

(11)

(12)

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

2 個體最優收斂性分析

本節給出Heavy-ball方法在目標函數非光滑條件下的個體收斂性證明.

(13)

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

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

基于這個關系式，我們可以證明定理1.為了解決變步長和權重導致的遞歸問題，我們先證明引理1.

具體證明見附錄1.

具體證明見附錄2.

僅考慮二分類問題，假設訓練樣本集

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

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

考慮非光滑稀疏學習問題的損失函數為“hinge損失”，即fi(w)=max{0,1-yiw,xi}的優化目標函數為

(14)

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

(15)

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

(16)

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

輸入: 循環次數t；

輸出:wt.

① 初始化向量w1=0；

② Fork=1 tot

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

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

⑦ End For

3 實 驗

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

3.1 實驗數據集和比較算法

實驗所采用的6個常用標準數據集，分別為ijcnn1,covtype,a9a,CCAT,RCV1,astro-physic.數據集來源于LIBSVM網站[注]https:www.csie.ntu.edu.tw～cjlinlibsvm.表1給出了這6個數據集的詳細描述.

Table 1 Introduction of Standard Datasets表1 標準數據集描述

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

3.2 實驗方法及結論

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

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

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

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

4 結 論

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