谢小磊 杨毅

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轮迭代中随机等概率的选取一个指数。不仅参数更新过程简单而且还不会线性依赖于样本总数，当目标函数为非凸和强凸函数时，达到次线性收敛。……