求解非凸優(yōu)化問題的一類帶動(dòng)量步的隨機(jī)方差縮減算法

謝小磊 楊毅

DOI：10.16660/j.cnki.1674-098X.2106-5640-0582

摘? 要：本文研究一類非凸有限和問題，求解該類問題比較常用的方法是隨機(jī)方差縮減算法。在隨機(jī)方差縮減算法的基礎(chǔ)上，考慮到動(dòng)量步能夠提升算法的求解效率，將動(dòng)量步與隨機(jī)方差縮減算法相結(jié)合，提出了一類帶動(dòng)量步的隨機(jī)方差縮減算法。給出了該算法的具體迭代格式，并對(duì)該算法進(jìn)行收斂性分析，證明了該算法在非凸情況下的次線性收斂率。

關(guān)鍵詞：方差縮減 經(jīng)典動(dòng)量 非凸優(yōu)化 小批量

中圖分類號(hào)：TP181? ? ? ? ? ? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼：A? ? ? ? ? ? ? ? ?文章編號(hào)：1674-098X（2021）06（b）-0078-04

A Class of stochastic variance reduction algorithms for nonconvex optimization problems with momentum steps

XIE Xiaolei? YANG Yi

（Nanjing University of Information Science and Technology， Nanjing， Jiangsu Province， 210044 China）

Abstract： This paper studies a class of nonconvex finite sum problems. The commonly used method to solve this kind of problems is random variance reduction algorithm. Based on the random variance reduction algorithm， considering that the momentum step can improve the solution efficiency of the algorithm， we combine the momentum step with the random variance reduction algorithm， and propose a kind of random variance reduction algorithm driven by the quantity step. We give the specific iterative format of the algorithm， analyze the convergence of the algorithm， and prove the sublinear convergence rate of the algorithm in the case of nonconvex.

Key Words： Variance reduction; Classical momentum; Nonconvex optimization; Minibatch

1? 引言

1.1 已有算法

本文主要研究非凸有限和形式問題，其格式如下

（1）

其中，，為非凸函數(shù)，且▽f，▽fi為L(zhǎng)ipschitz連續(xù)。這一類有限和問題在機(jī)器學(xué)習(xí)的過程中有著廣泛應(yīng)用[1-6]，同時(shí)機(jī)器學(xué)習(xí)也被廣泛應(yīng)用在計(jì)算機(jī)視覺、語音識(shí)別及數(shù)據(jù)挖掘等領(lǐng)域中[3]。

解決這類問題最經(jīng)典的方法是梯度下降算法，全梯度下降（FGD）[7]，其算法迭代格式如下：

其中，為第t輪迭代的學(xué)習(xí)率，n為樣本總數(shù)。當(dāng)目標(biāo)函數(shù)f為強(qiáng)凸函數(shù)時(shí)，F(xiàn)GD能夠達(dá)到線性收斂速度;當(dāng)目標(biāo)函數(shù)f為非凸函數(shù)時(shí)，F(xiàn)GD能達(dá)到次線性收斂速度。

考慮本文n比較大，為減少計(jì)算量，有人提出隨機(jī)梯度下降法（SGD），在每一輪進(jìn)行更新參數(shù)時(shí)，只會(huì)隨機(jī)選擇一個(gè)樣本來計(jì)算梯度以此來代替整個(gè)梯度估計(jì)值，其算法迭代格式如下：

其中，表示第t輪迭代中隨機(jī)等概率的選取一個(gè)指數(shù)。不僅參數(shù)更新過程簡(jiǎn)單而且還不會(huì)線性依賴于樣本總數(shù)，當(dāng)目標(biāo)函數(shù)為非凸和強(qiáng)凸函數(shù)時(shí)，達(dá)到次線性收斂。此外，有人提出在每次更新時(shí)隨機(jī)選取個(gè)樣本，即小批量隨機(jī)梯度下降法[8]。將它們的平均值代替成為整個(gè)梯度的估計(jì)值。其更新公式為：

在SGD中，我們假設(shè)單個(gè)樣本梯度是整個(gè)樣本梯度上無偏估計(jì)，但因梯度方差存在，所以僅當(dāng)學(xué)習(xí)率逐步遞減并趨于0時(shí)，SGD能夠達(dá)到收斂。但若學(xué)習(xí)率過小，整個(gè)迭代過程會(huì)很慢。

為解決上述問題，有人提出“方差縮減”，這是構(gòu)造一些特殊的梯度估計(jì)量，讓每輪的梯度方差有一個(gè)不斷縮減的上界，這樣即使學(xué)習(xí)率不是很小也能較快收斂。其中最常用的是基于方差縮減的隨機(jī)梯度下降算法（SVRG）[9]。該算法是每輪外迭代時(shí)會(huì)進(jìn)行一輪內(nèi)迭代;在進(jìn)行內(nèi)迭代前，先用當(dāng)前計(jì)算全部樣本的平均梯度內(nèi)部迭代的初始值被賦值給當(dāng)前的。內(nèi)部迭代中每次迭代梯度為：

可以將視為梯度估計(jì)的偏差。因此，在每次迭代中，算法都對(duì)基于當(dāng)前參數(shù)作的梯度估計(jì)進(jìn)行修正。它可以達(dá)到強(qiáng)凸函數(shù)下線性收斂凸函數(shù)下次線性收斂的結(jié)果，將其推廣到非凸函數(shù)，可以得到期望意義下梯度的次線性收斂[10]。

1.2 加速方法

已有學(xué)者在SGD基礎(chǔ)上提出一種加速算法收斂的方法：動(dòng)量法（CM）[10]。這是一種幫助SGD在相關(guān)方向上抑制搖擺并且進(jìn)行加速的一種方法。此外動(dòng)量法（CM）在進(jìn)行參數(shù)更新的時(shí)候，還利用當(dāng)前批量以此微調(diào)最終的更新方向，同時(shí)也一定的程度上保留之前的更新方向，也就是相當(dāng)于通過積累先前的動(dòng)量以此來加速當(dāng)前的梯度，其更新公式為：

其中為動(dòng)量項(xiàng)，當(dāng)=0時(shí)，這個(gè)方法就變?yōu)榱薙GD。因此，才能減少搖擺，從而得到更快收斂速度[11]。

1.3 本文工作

于是考慮到經(jīng)典動(dòng)量能夠提升算法的求解效率，本文將SVRG與經(jīng)典動(dòng)量的技巧結(jié)合，提出一種求解非凸優(yōu)化的一類帶動(dòng)量步的隨機(jī)方差縮減算法（SVRG-CM），并給出算法收斂性分析，證明在求解非凸問題時(shí)，算法可以達(dá)到次線性收斂率。

本文的其余部分安排如下：在第二部分中，將介紹一些預(yù)備知識(shí);在第三部分中，我們將會(huì)給出算法，并對(duì)所給算法進(jìn)行收斂分析。最后第四節(jié)總結(jié)全文。

2? 預(yù)備知識(shí)

為討論算法收斂性，下面介紹一些本文涉及的符號(hào)以及定義。首先對(duì)文中用到的符號(hào)做出如下定義： d為歐幾里得空間，表示向量?jī)?nèi)積，表示歐氏范數(shù)。

引理2.1[12]：令函數(shù)f：d→以及梯度f（L- Lipschitz）連續(xù)，那么對(duì)任意的，有：

定義2.2：是L-光滑的，即。

定義2.3：如果，則稱點(diǎn)x為穩(wěn)定點(diǎn);如果，則可以獲得期望意義下的-穩(wěn)定點(diǎn)。

3? 收斂分析

本節(jié)將給出相應(yīng)算法，并給出其收斂結(jié)果和收斂分析。

SVRG-CM算法如下。

該算法中，是本地更新公式的隨機(jī)經(jīng)典動(dòng)量的參數(shù)，這里，本文算法與SVRG的唯一區(qū)別就是多一個(gè)動(dòng)量項(xiàng)[13-14]，即：

通過積累先前的動(dòng)量來加速當(dāng)前的梯度，最終達(dá)到加速收斂的效果。小批量的處理通常用于減少隨機(jī)梯度的方差并增加并行度[15]。下面我們提供非凸情況下SVRG-CM結(jié)果的證明，為簡(jiǎn)便書寫，這里令，在同一個(gè)內(nèi)循環(huán)中省略上標(biāo)，這里默認(rèn)是在第s+1層外循環(huán)中進(jìn)行的迭代更新。先給出以下引理。

引理3.1：假設(shè)是算法1產(chǎn)生的迭代點(diǎn)列，則有以下不等式成立：

引理3.2：假設(shè)，是算法1產(chǎn)生的迭代點(diǎn)列，則有以下不等式成立：

引理3.3：定義，假設(shè)對(duì)和，令，有：

并且參數(shù)被恰當(dāng)?shù)倪x擇

使得。

則帶有小批量大小為b的算法1產(chǎn)生的迭代點(diǎn)滿足以下不等式：

定理3.1：令

使得。定義，設(shè)T為m的倍數(shù)，對(duì)于算法1中的輸出，有以下不等式成立：

其中為（1）的最優(yōu)解。

4? 結(jié)語

本文根據(jù)方差縮減的隨機(jī)梯度下降算法，提出針對(duì)非凸優(yōu)化問題的一種帶動(dòng)量步的隨機(jī)方差縮減算法，該算法較之SVRG是在內(nèi)循環(huán)更新梯度時(shí)使用經(jīng)典動(dòng)量方法，來提升收斂效率，在一些函數(shù)光滑性假設(shè)下，本文得到非凸情況下該算法的次線性收斂，并提供收斂證明。本人認(rèn)為，將動(dòng)量與方差縮減結(jié)合可以很好地進(jìn)行非凸優(yōu)化。

參考文獻(xiàn)

[1] Jordan M.， Mitchell T.Machine learning： Trends， perspectives， and prospects[J].Science，2015， 349（6245）：255-260.

[2] 林懿倫，戴星原，李力，等.人工智能研究的新前線：生成式對(duì)抗網(wǎng)絡(luò)[J].自動(dòng)化學(xué)報(bào)，2019，44（5）：775-792.

[3] 史加榮，王丹，尚凡華，等.隨機(jī)梯度下降算法研究進(jìn)展[J/OL].自動(dòng)化學(xué)報(bào)，2019.

[4] Bottou L.， Curtis F. https：//doi.org/10.16383/j.aas.c190260.Optimization methods for large-scale machine learning[J].Siam Review， 2016，60（2）：223-311.

[5] Liu S.， Deng W. Very deep convolutional neural network based image classification using small training sample size[C].IEEE，2016.

[6] Shamir O.Convergence of stochastic gradient descent for PCA[J].Mathematics，2016，257-265.

[7] Nesterov Y.Gradient methods for minimizing composite functions[J].Mathematical Programming，2013，140（1）：125-161.

[8] Mu L. Efficient mini-batch training for stochastic optimization[C].ACM， 2014，661-670.

[9] Reddi S.， Hefny A.， Sra S.， et al.Stochastic variance reduction for nonconvex optimization[J]. JMLR，2016.

[10] Qian N.On the momentum term in gradient descent learning algorithms[J].Neural Networks， 1999，12（1）：145-151.

[11] Ruder S.An overview of gradient descent optimization algorithms[J].ArXiv，preprint arXiv：2016，1609.04747v2.

[12] Nesterov Y.Introductory lectures on convex optimization： A basic course[M].Springer，2004.

[13] 張弛，高雨佳，劉亮.一種適用于聯(lián)邦學(xué)習(xí)的分布式Non-IID數(shù)據(jù)集生成方法[J].2021.

[14] Keith A J， Ahner D K.A survey of decision making and optimization under uncertainty[J].? 2021.

[15] 朱小輝，陶卿，邵言劍.一種減小方差求解非光滑問題的隨機(jī)優(yōu)化算法[J].軟件學(xué)報(bào)，2015，26（11）：2752-2761.