Stochastic gradient algorithms compute the gradient based on only one sample (or just a few samples) and enjoy low computational cost per iteration. They are widely used in large-scale optimization problems. However, stochastic gradient algorithms are usually slow to converge and achieve sub-linear convergence rates, due to the inherent variance in the gradient computation. To accelerate the convergence, some variance-reduced stochastic gradient algorithms have been proposed. Under the \emph{strongly convex condition}, these variance-reduced stochastic gradient algorithms achieve a linear convergence rate. However, in many machine learning problems, the objective function to be minimized is convex but \emph{not} strongly convex. In this paper, we propose a Variance-Reduced Projected Stochastic Gradient (VRPSG) algorithm, which can efficiently solve a class of constrained optimization problems. As the main technical contribution of this paper, we show that the proposed VRPSG algorithm achieves a linear convergence rate \emph{without} the strong convexity assumption. To the best of our knowledge, this is the first work that establishes the linear convergence rate for the variance-reduced stochastic gradient algorithm \emph{without} strong convexity.

本研究介绍了Prox-SVRG及其投影变体VRPSG算法，用于解决一类在机器学习中广泛使用的非强凸优化问题。通过SSC不等式的使用，本文证明了两种算法可以在无强凸性的情况下实现线性收敛率。

无强凸性的方差缩减随机梯度线性收敛