论文部分内容阅读
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.
摘 要：本文研究一类非凸有限和问题，求解该类问题比较常用的方法是随机方差缩减算法。在随机方差缩减算法的基础上，考虑到动量步能够提升算法的求解效率，将动量步与随机方差缩减算法相结合，提出了一类带动量步的随机方差缩减算法。给出了该算法的具体迭代格式，并对该算法进行收敛性分析，证明了该算法在非凸情况下的次线性收敛率。
关键词：方差缩减 经典动量 非凸优化 小批量
中图分类号：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.