求解非凸優化問題的一類帶動量步的隨機方差縮減算法

謝小磊 楊毅

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

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

關鍵詞：方差縮減 經典動量 非凸優化 小批量

中圖分類號：TP181? ? ? ? ? ? ? ? ? ? ? ? ? ?文獻標識碼：A? ? ? ? ? ? ? ? ?文章編號：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）

其中，，為非凸函數，且▽f，▽fi為Lipschitz連續。這一類有限和問題在機器學習的過程中有著廣泛應用[1-6]，同時機器學習也被廣泛應用在計算機視覺、語音識別及數據挖掘等領域中[3]。

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

其中，為第t輪迭代的學習率，n為樣本總數。當目標函數f為強凸函數時，FGD能夠達到線性收斂速度;當目標函數f為非凸函數時，FGD能達到次線性收斂速度。

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

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

在SGD中，我們假設單個樣本梯度是整個樣本梯度上無偏估計，但因梯度方差存在，所以僅當學習率逐步遞減并趨于0時，SGD能夠達到收斂。但若學習率過小，整個迭代過程會很慢。

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

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

1.2 加速方法

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

其中為動量項，當=0時，這個方法就變為了SGD。因此，才能減少搖擺，從而得到更快收斂速度[11]。

1.3 本文工作

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

本文的其余部分安排如下：在第二部分中，將介紹一些預備知識;在第三部分中，我們將會給出算法，并對所給算法進行收斂分析。最后第四節總結全文。

2? 預備知識

為討論算法收斂性，下面介紹一些本文涉及的符號以及定義。首先對文中用到的符號做出如下定義： d為歐幾里得空間，表示向量內積，表示歐氏范數。

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

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

定義2.3：如果，則稱點x為穩定點;如果，則可以獲得期望意義下的-穩定點。

3? 收斂分析

本節將給出相應算法，并給出其收斂結果和收斂分析。

SVRG-CM算法如下。

該算法中，是本地更新公式的隨機經典動量的參數，這里，本文算法與SVRG的唯一區別就是多一個動量項[13-14]，即：

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

引理3.1：假設是算法1產生的迭代點列，則有以下不等式成立：

引理3.2：假設，是算法1產生的迭代點列，則有以下不等式成立：

引理3.3：定義，假設對和，令，有：

并且參數被恰當的選擇

使得。

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

定理3.1：令

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

其中為（1）的最優解。

4? 結語

本文根據方差縮減的隨機梯度下降算法，提出針對非凸優化問題的一種帶動量步的隨機方差縮減算法，該算法較之SVRG是在內循環更新梯度時使用經典動量方法，來提升收斂效率，在一些函數光滑性假設下，本文得到非凸情況下該算法的次線性收斂，并提供收斂證明。本人認為，將動量與方差縮減結合可以很好地進行非凸優化。

參考文獻

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

[2] 林懿倫，戴星原，李力，等.人工智能研究的新前線：生成式對抗網絡[J].自動化學報，2019，44（5）：775-792.

[3] 史加榮，王丹，尚凡華，等.隨機梯度下降算法研究進展[J/OL].自動化學報，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] 張弛，高雨佳，劉亮.一種適用于聯邦學習的分布式Non-IID數據集生成方法[J].2021.

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

[15] 朱小輝，陶卿，邵言劍.一種減小方差求解非光滑問題的隨機優化算法[J].軟件學報，2015，26（11）：2752-2761.