陶 蔚 潘志松 朱小輝 陶 卿

1(中國人民解放軍理工大學(xué)指揮信息系統(tǒng)學(xué)院 南京 210007)2 (中國人民解放軍陸軍軍官學(xué)院十一系 合肥 230031)(wtao_plaust@163.com)

線性插值投影次梯度方法的最優(yōu)個體收斂速率

陶 蔚1潘志松1朱小輝2陶 卿2

1(中國人民解放軍理工大學(xué)指揮信息系統(tǒng)學(xué)院 南京 210007)2(中國人民解放軍陸軍軍官學(xué)院十一系 合肥 230031)(wtao_plaust@163.com)

投影次梯度算法(projected subgradient method, PSM)是求解非光滑約束優(yōu)化問題最簡單的一階梯度方法，目前只是對所有迭代進行加權(quán)平均的輸出方式得到最優(yōu)收斂速率，其個體收斂速率問題甚至作為open問題被提及.最近，Nesterov和Shikhman在對偶平均方法(dual averaging method, DAM)的迭代中嵌入一種線性插值操作，得到一種擬單調(diào)的求解非光滑問題的次梯度方法，并證明了在一般凸情形下具有個體最優(yōu)收斂速率,但其討論僅限于對偶平均方法.通過使用相同技巧，提出了一種嵌入線性插值操作的投影次梯度方法，與線性插值對偶平均方法不同的是，所提方法還對投影次梯度方法本身進行了適當(dāng)?shù)男薷囊源_保個體收斂性.同時證明了該方法在一般凸情形下可以獲得個體最優(yōu)收斂速率，并進一步將所獲結(jié)論推廣至隨機方法情形.實驗驗證了理論分析的正確性以及所提算法在保持實時穩(wěn)定性方面的良好性能.

一階梯度方法；個體收斂速率；投影次梯度方法；線性插值操作；對偶平均方法

投影次梯度方法(projected subgradient method, PSM)是求解非光滑約束優(yōu)化問題的一種簡單的一階梯度方法，在數(shù)學(xué)優(yōu)化中占據(jù)著十分重要的歷史地位[1-2]，在其基礎(chǔ)上發(fā)展出許多具有重要影響的一階梯度方法，如鏡面下降方法(mirror descent method, MDM)[3]和對偶平均方法(dual averaging method, DAM)[4].相比而言，對偶平均方法的梯度權(quán)重和步長選擇策略更為靈活，可以在多種不同步長情形下得到最優(yōu)收斂速率.但與投影次梯度方法一樣，標準的對偶平均方法也只是在一般凸情形下，將所有迭代結(jié)果進行平均,得到了最優(yōu)收斂速率[5].

SGD(stochastic gradient descent)是梯度下降法的隨機形式，由于不需要遍歷樣本集合，SGD在處理大規(guī)模學(xué)習(xí)問題方面具有明顯優(yōu)勢[6-7].但對于強凸優(yōu)化問題，即使是采用對所有迭代進行平均的輸出方式，目前標準的SGD也未能證明能獲得最優(yōu)的收斂速率，這一問題引起了學(xué)者對SGD統(tǒng)治地位的質(zhì)疑.為了捍衛(wèi)SGD的經(jīng)典與尊嚴，Shamir[8]在2012年的COLT會議上把SGD的個體最優(yōu)收斂速率作為open問題提出.緊接著，Shamir和Zhang[9]提出一種由平均輸出方式收斂速率得到個體收斂速率的一般技巧，盡管得到了SGD的個體收斂速率，但獲得的收斂速率與最優(yōu)收斂速率相差一個對數(shù)因子，仍未能達到最優(yōu).

對于強凸情形下SGD的最優(yōu)收斂速率問題，已經(jīng)有了相當(dāng)多的研究.從總體上來看，一種思路是對算法本身進行修改，如Hazan等人[10]在SGD中嵌入適當(dāng)數(shù)目的內(nèi)循環(huán)，提出一種Epoch-GD算法，獲得了平均輸出方式的最優(yōu)收斂速率；Chen等人[11]在算法每一步迭代中采用兩次求解不同形式的子優(yōu)化問題，提出了一種改進的隨機對偶平均方法，獲得了最優(yōu)個體收斂速率.另一種思路是對輸出方式進行修改，如Rakhlin等人[12]以部分迭代解平均的α-suffix技巧來代替全部平均的輸出方式；Lacoste-Julien等人[13]提出一種加權(quán)平均的輸出方式.這些方法均獲得了最優(yōu)的收斂速率.

相比于強凸情形，SGD在一般凸情形下的個體收斂速率問題研究卻較少，這或許是因為平均輸出方式已經(jīng)獲得了最優(yōu)收斂速率.2015年，Nesterov和Shikhman[5]在對偶平均方法的迭代中嵌入了一種線性插值操作策略，證明了該方法在一般凸情形下具有最優(yōu)的個體收斂速率，并給出了這種個體收斂結(jié)果在系統(tǒng)實時穩(wěn)定化中的應(yīng)用.從理論角度來說，這種改動與標準的對偶平均方法區(qū)別極小，是對偶平均方法很好的擴展，也是對一階梯度方法個體最優(yōu)收斂速率比較接近大家期待的一種回答.但美中不足的是，其算法設(shè)計和收斂速率分析的思路僅適用于步長策略靈活的對偶平均方法.

本文使用相同的線性插值操作，對投影次梯度方法進行適當(dāng)修改，得到了一種嵌入線性插值操作投影次梯度方法，證明了在一般凸情形下這種方法具有個體最優(yōu)收斂速率，并進一步得到了對應(yīng)的隨機方法也具有最優(yōu)個體收斂速率的結(jié)論，并且該方法的個體收斂結(jié)果在系統(tǒng)實時穩(wěn)定化中也有廣泛應(yīng)用前景.值得指出的是，本文對投影次梯度方法的修改也與標準投影次梯度方法的差別很小，但與文獻[5]關(guān)于對偶平均算法修改還是存在著一定的差異，即如果按照該文獻步驟進行簡單類似的修改，得不到相關(guān)結(jié)果.由于算法形式上的不同，本文的收斂速率分析方法也與文獻[5]區(qū)別很大.另外，本文的算法與文獻[14]動力系統(tǒng)離散化后所得的算法雖然在形式上十分類似，但不僅避免了只能得到平均輸出方式收斂速率的問題，還減弱了對目標函數(shù)不必要的強凸和光滑條件.作為應(yīng)用，我們考慮了l1范數(shù)約束的hinge損失函數(shù)稀疏學(xué)習(xí)問題，實驗驗證了理論分析的正確性.

1 幾種典型的一階梯度方法及其收斂速率

考慮約束的優(yōu)化問題：

(1)

其中,f(w)是凸函數(shù)，Q?n是有界閉凸集合.記w*是式(1)的一個最優(yōu)解.

對于式(1)，批處理形式投影次梯度方法的迭代步驟為

(2)

(3)

(4)

(5)

在鏡面下降算法的基礎(chǔ)上，Nesterov[4-5]提出了對偶平均算法，其主要迭代步驟為

(6)

其中，d(w)是強凸函數(shù)，也稱為近鄰函數(shù)，滿足：

x,y∈Q.

與投影次梯度和鏡面下降方法相比，對偶平均算法引進了另外的步長參數(shù)γt，使得梯度的權(quán)重的取法at更加靈活.特別地可以取平均at=1t，這也是這種對偶平均算法中平均名稱的由來.該方法具有收斂速率界[5]：

(7)

當(dāng)取at=Θ(1)時，投影次梯度方法和鏡面下降方法的上述收斂界均可以達到最優(yōu)的收斂速率O(1)；當(dāng)at=1且)時，對偶平均優(yōu)化方法也取得最優(yōu)收斂速率[4-5].另外，一些文獻對這3種一階算法分別給出了在線形式的regret界[15-17]，并且使用標準的在線與隨機算法之間的切換技巧[10]，也得到了上述3種算法平均輸出方式同樣階的收斂速率.

2013年，Shamir和Zhang[9]未對算法進行任何改動，在平均方式輸出收斂速率的基礎(chǔ)上，運用一種得到個體收斂速率的一般技巧，在一般凸非光滑情況下得到了SGD個體收斂速率為O(lnt)，在強凸情形下得到SGD個體收斂速率為O(lntt)，這是關(guān)于個體收斂速率方面的首批結(jié)果，也是SGD最優(yōu)收斂速率open問題比較接近的一種回答[18].但不難發(fā)現(xiàn)，獲得的收斂速率與最優(yōu)收斂速率相差一個對數(shù)因子lnt，仍然未能達到open問題中所期待的最優(yōu).

為了討論一階梯度方法的最優(yōu)個體收斂速率問題，Nesterov和Shikhman[5]在2015年對于對偶平均算法作了如下修改：

(8)

2 嵌入插值操作的投影次梯度方法

我們沿用Nesterov和Shikhman在處理對偶平均算法個體最優(yōu)收斂速率時的插值思路，提出如下嵌入線性插值操作的投影次梯度方法：

(9)

其中，t≥1.

需要特別指出，式(9)對投影次梯度方法的修改不是顯然的，因為如果使用文獻[5]對于對偶平均算法的直接修改，我們一般會考慮以下算法：

(10)

但是對這種形式的算法，目前我們?nèi)晕茨茏C明期望的個體收斂速率結(jié)果.另外，文獻[14]通過對連續(xù)形式的梯度動力系統(tǒng)進行離散化，得到與式(10)形式上非常相似的算法：

但只能得到平均輸出形式的收斂速率，并且對目標函數(shù)附加了不必要的光滑性等條件.

盡管與直接修改投影次梯度方法(式(10))存在著差異，式(9)對投影次梯度方法的修改仍然是十分微小的.下面對嵌入插值操作的投影次梯度方法(式(9))進行收斂性分析.

引理1[1]. 假設(shè)其中PQ是閉凸集合Q上的投影算子，則對于任意w∈n，w0∈Q，則〈w-w0,u-w0〉≤0對任意u∈Q都成立的充要條件是w0=PQ(w).

引理2. 對于任意w∈Q，

具體證明見附錄A.

引理3.

具體證明見附錄B.

具體證明見附錄C.

根據(jù)定理1，類似于文獻[16]，我們可以得出推論：

推論1. 假設(shè)f(w)是閉凸集合Q?n上的凸函數(shù)，存在G>0，滿足,?w∈Q.取at=1和ηt=1，對于任意w∈Q，有：

推論2具體證明見附錄D.

推論1和推論2表明嵌入插值操作投影次梯度方法對一般凸問題具有個體最優(yōu)收斂速率.與標準投影次梯度方法不同的是:由于存在著插值權(quán)重，步長選擇比較靈活，可以得到多種形式獲得個體最優(yōu)收斂速率的參數(shù)組合，這一點與對偶平均算法極為類似.因此，可以說我們將文獻[5]關(guān)于個體最優(yōu)收斂速率的研究思路適當(dāng)修改使之適用于投影次梯度方法.

3 嵌入插值操作的隨機投影次梯度方法

為了更加簡單直接地討論嵌入插值操作投影次梯度方法所對應(yīng)的隨機優(yōu)化方法，我們直接考慮二分類的稀疏學(xué)習(xí)問題.假設(shè)訓(xùn)練樣本集合S={(x1,y1),(x2,y2),…,(xm,ym)}∈n×{1,-1}是一些獨立同分布樣本組成，稀疏學(xué)習(xí)問題可以表示為求解優(yōu)化問題：

(11)

(12)

其中,t≥1,i是從樣本集合中第t+1次迭代隨機抽取樣本的序號.

同樣，在分析隨機優(yōu)化算法收斂速率時，我們的主要手段就是將梯度的無偏估計在期望條件下?lián)Q成整個目標函數(shù)的梯度，從而與批處理算法收斂分析方法建立密切的聯(lián)系.與文獻[12]引理1的證明完全類似，我們可以獲得期望條件下引理1和引理2對應(yīng)的結(jié)論.更進一步得到:

在定理2的基礎(chǔ)上，很容易將推論1和推論2拓廣至隨機情形，即嵌入線性插值操作的隨機投影次梯度方法具有個體最優(yōu)收斂速率.

4 實 驗

本節(jié)對隨機嵌入線性插值操作投影次梯度方法的個體收斂速率及其實時穩(wěn)定性進行實驗驗證.實驗采用的是6個常用的標準數(shù)據(jù)庫，其中，covtype，ijcnn1，a9a這3個數(shù)據(jù)庫稀疏度較高，另外3個數(shù)據(jù)庫的稀疏度均在1%以下.數(shù)據(jù)庫來自于LIBSVM網(wǎng)站①.表1給出了這6個數(shù)據(jù)庫的基本描述.

Table 1 Introduction of Standard Datasets

在實驗中，采取隨機方法抽取樣本，各算法均取相同的約束參數(shù)和步長，并且每個算法均運行10次，將10次輸出結(jié)果的平均值作為最終輸出.實驗結(jié)果如圖1所示，其中橫坐標表示迭代次數(shù)，最大迭代次數(shù)均設(shè)置為10 000次，縱坐標表示當(dāng)前目標函數(shù)值與最優(yōu)目標函數(shù)值之差的平均值，這里目標函數(shù)的最優(yōu)值取各算法迭代過程中10次平均后最小的目標函數(shù)值.圖1中的黑色實線(PSM_average)反映了平均輸出方式投影次梯度方法的收斂趨勢，長虛線(PSM_individual)顯示了個體輸出方式投影次梯度方法的收斂趨勢，帶有“+”的曲線(DAM_modified)反映了文獻[5]中提出的具有個體收斂速率對偶平均方法的收斂趨勢，而短虛線(PSM_interpolation)表示本文提出的嵌入線性插值操作投影次梯度方法的收斂趨勢.

從圖1可以看出，對于6個標準數(shù)據(jù)庫，嵌入線性插值操作和平均輸出方式的投影次梯度方法均具有相同的收斂趨勢，這就從實驗上驗證了本文理論分析的正確性.其次，雖然個體輸出方式的隨機投影次梯度穩(wěn)定性也具有類似的收斂趨勢，但個體輸出方式的穩(wěn)定性明顯比嵌入線性插值操作投影次梯度方法要差.另外，文獻[5]中嵌入插值操作的對偶平均方法和本文嵌入線性插值操作的投影次梯度方法具有一樣的穩(wěn)定性結(jié)果，因此，嵌入線性插值操作的投影次梯度方法也可以作為無限時域系統(tǒng)實時穩(wěn)定化的一種有效工具.

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

5 結(jié) 論

SGD在求解凸優(yōu)化問題時能否達到個體最優(yōu)收斂速率是近期提出的open問題，但在一般凸情形下的個體最優(yōu)收斂速率的研究卻較少.最近，Nesterov和Shikhman在對偶平均方法中直接嵌入線性插值操作，得到了個體最優(yōu)收斂速率，但其結(jié)論僅限于對偶平均方法.

本文使用相同的線性插值操作策略，在投影次梯度的基礎(chǔ)上得到了一般凸情形下的個體最優(yōu)收斂速率，并進一步得到了隨機方法的最優(yōu)個體收斂速率.這是對投影次梯度方法在一般凸情形下是否具有個體最優(yōu)收斂比較接近的一種回答.

與文獻[5]不同的是，我們需要對投影次梯度算法進行一定的修改，才能結(jié)合線性插值策略，得到個體最優(yōu)收斂速率的結(jié)果.

[2]Shor N Z. Minimization methods for non-differentiable functions[M]. Berlin: Springer, 1985

[3]Beck A, Teboulle M. Mirror descent and nonlinear projected subgradient methods for convex optimization[J]. Operations Research Letters, 2003, 31(2): 167-175

[4]Nesterov Y. Primal-dual subgradient methods for convex problems[J]. Mathematical Programming, 2009, 120(1): 221-259

[5]Nesterov Y, Shikhman V. Quasi-monotone subgradient methods for nonsmooth convex minimization[J]. Journal of Optimization Theory and Applications. 2015, 165(3): 917-940

[6]Zhang Tong. Solving large scale linear prediction problems using stochastic gradient descent algorithms[C]Proc of the 21st Int Conf on Machine Learning. New York: ACM, 2004: 116-124

[7]Shalev-Shwartz S, Singer Y, Srebro N, et al. Pegasos: Primal estimated sub-gradient solver for SVM[J]. Mathematical Programming, 2011, 127(1): 3-30

[8]Shamir O. Open problem: Is averaging needed for strongly convex stochastic gradient descent?[C]Proc of the 25th Conf on Learning Theory. New York: ACM, 2012: 471-473

[9]Shamir O, Zhang Tong. Stochastic gradient descent for non-smooth optimization: Convergence results and optimal averaging schemes[C]Proc of the 29th Int Conf on Machine Learning. New York: ACM, 2012: 71-79

[10]Hazan E, Kale S. Beyond the regret minimization barrier: An optimal algorithm for stochastic strongly-convex optimization[C]Proc of the 24th Conf on Learning Theory. New York: ACM, 2011: 421-436

[11]Chen Xi, Lin Qihang, Pena J. Optimal regularized dual averaging methods for stochastic optimization[G]Advances in Neural Information Processing Systems. Vancouver, Canada: NIPS Foundation, 2012: 404-412

[12]Rakhlin A, Shamir O, Sridharan K. Making gradient descent optimal for strongly convex stochastic optimization[C]Proc of the 29th Int Conf on Machine Learning. New York: ACM, 2012: 449-456

[13]Lacoste-Julien S, Schmidt M, Bach F. A simpler approach to obtaining anO(1t) convergence rate for the projected stochastic subgradient method[OL]. (2012-12-20)[2015-9-10]. http:arxiv.orgabs1212.2002

[14]Tao Qing, Sun Zhengya, Kong Kang. Developing learning algorithms via optimized discretization of continuous dynamical systems[J]. IEEE Trans on Systems, Man, and Cybernetics, Part B: Cybernetics, 2012, 42(1): 140-149

[15]Duchi J C, Shalev-Shwartz S, Singer Y, et al. Composite objective mirror descent[C]Proc of the 23rd Conf on Learning Theory. New York: ACM, 2010: 14-26

[16]Zinkevich M. Online convex programming and generalized infinitesimal gradient ascent[C]Proc of the 20th Int Conf on Machine Learning. New York: ACM, 2003: 928-936

[17]Xiao L. Dual averaging methods for regularized stochastic learning and online optimization[J]. Advances in Neural Information Processing Systems, 2010, 11(1): 2543-2596

[18]Shao Yanjian, Tao Qing, Jiang Jiyuan, et al. Stochastic algorithm with optimal convergence rate for strongly convex optimization problems[J]. Journal of Software, 2014, 25(9): 2160-2171 (in Chinese)(邵言劍, 陶卿, 姜紀遠, 等. 一種求解強凸優(yōu)化問題的最優(yōu)隨機算法[J]. 軟件學(xué)報, 2014, 25(9): 2160-2171)

[19]Duchi J, Shalev-Shwartz S, Singer Y, et al. Efficient projections onto thel1-ball for learning in high dimensions[C]Proc of the 25th Int Conf on Machine Learning. New York: ACM, 2008: 272-279

[20]Liu Jun, Ye Jieping. Efficient Euclidean projections in linear time[C]Proc of the 26th Int Conf on Machine Learning. New York: ACM, 2009: 657-664

Tao Wei, born in 1991. Master candidate. His main research interests include convex optimization algorithm and its application in machine learning, network security.

Pan Zhisong, born in 1973. PhD. Professor and PhD supervisor. Senior member of CCF. His main research interests include pattern recognition, machine learning and network security.

Zhu Xiaohui, born in 1989. Master. His main research interests include pattern recognition and machine learning.

Tao Qing, born in 1965. PhD. Professor and PhD supervisor. Senior member of CCF. His main research interests include pattern recognition, machine learning and applied mathematics.

附錄A

正文引理2證明.

(A1)

根據(jù)次梯度的定義:

所以根據(jù)式(12):

(A2)

綜合式(A1)和式(A2)，引理2得證.

證畢.

附錄B

正文引理3證明.

At-1f(wt-1)-At-1f(wt).

另一方面，

證畢.

附錄C

正文定理1證明.

根據(jù)引理2和引理3，

ηt(At-1f(wt-1)-At-1f(wt)).

即：

ηtAt(f(wt)-f(w))≤

At(f(wt)-f(w))≤At-1(f(wt-1)-f(w))+

對At(f(wt)-f(w))進行遞歸，可得：

由于ηt≤ηt-1，所以，

證畢.

附錄D

正文推論2證明.

根據(jù)定理1：

當(dāng)at=t和ηt=1時，At=t2且：

證畢.

The Optimal Individual Convergence Rate for the Projected Subgradient Method with Linear Interpolation Operation

Tao Wei1, Pan Zhisong1, Zhu Xiaohui2, and Tao Qing2

1(CollegeofCommandInformationSystem,PLAUniversityofScienceandTechnology,Nanjing210007)2(11stDepartment,ArmyOfficerAcademyofPLA,Hefei230031)

The projected subgradient method is one of the simplest algorithms for solving nonsmooth constrained optimization problems. So far, only the optimal convergence rate in terms of the averaged output has been obtained. Its individual convergence rate is even regarded as an open problem. Recently, by incorporating a linear interpolation operation into the dual averaging methods, Nesterov and Shikhman achieved a quasi-monotone subgradient method for nonsmooth convex minimization, which is proved to have the optimal individual convergence rate. Unfortunately, their discussion is only limited to the dual averaging methods. This paper focuses on the individual convergence rate of projected subgradient methods. By employing the same technique, we present a projected subgradient method with linear interpolation operation. In contrast to the work of Nesterov and Shikhman, the projected subgradient method itself in the proposed method has to be modified slightly so as to ensure the individual convergence rate. We prove that the proposed method has the optimal individual convergence rate for solving nonsmooth convex problems. Further, the corresponding stochastic method is proved to have the optimal individual convergence rate. This can be viewed as an approximate answer to the open problem of optimal individual convergence of the projected subgradient methods. The experiments verify the correctness of our analysis and demonstrate the high performance of the proposed methods in real-time stabilization.

first-order method; individual convergence rate; projected subgradient method; linear interpolation operation; dual averaging method

2016-03-11；

2016-05-09

國家自然科學(xué)基金項目(61673394,61273296) This work was supported by the National Natural Science Foundation of China (61673394, 61273296).

陶卿(qing.tao@ia.ac.cn)

TP181