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

陶 蔚 潘志松 朱小輝 陶 卿

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)

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

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

(2)

(3)

(4)

(5)

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

(6)

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

x,y∈Q.

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

(7)

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

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

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

(8)

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

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

(9)

其中，t≥1.

需要特別指出，式(9)對(duì)投影次梯度方法的修改不是顯然的，因?yàn)槿绻褂梦墨I(xiàn)[5]對(duì)于對(duì)偶平均算法的直接修改，我們一般會(huì)考慮以下算法：

(10)

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

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

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

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

引理2. 對(duì)于任意w∈Q，

具體證明見附錄A.

引理3.

具體證明見附錄B.

具體證明見附錄C.

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

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

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

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

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

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

(11)

(12)

其中,t≥1,i是從樣本集合中第t+1次迭代隨機(jī)抽取樣本的序號(hào).

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

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

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

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

Table 1 Introduction of Standard Datasets

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

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

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

5 結(jié) 論

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

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

與文獻(xiàn)[5]不同的是，我們需要對(duì)投影次梯度算法進(jìn)行一定的修改，才能結(jié)合線性插值策略，得到個(gè)體最優(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)(邵言劍, 陶卿, 姜紀(jì)遠(yuǎn), 等. 一種求解強(qiáng)凸優(yōu)化問題的最優(yōu)隨機(jī)算法[J]. 軟件學(xué)報(bào), 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))+

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

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

證畢.

附錄D

正文推論2證明.

根據(jù)定理1：

當(dāng)at=t和ηt=1時(shí)，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

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

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

TP181