Variance Reduction for Faster Non-Convex Optimization

By Zeyuan Allen-Zhu, Elad Hazan. 2016

414 citations recorded by the source corpus.

We consider the fundamental problem in non-convex optimization of efficiently reaching a stationary point. In contrast to the convex case, in the long history of this basic problem, the only known theoretical results on first-order non-convex optimization remain to be full gradient descent that converges in $O(1/\varepsilon)$ iterations for smooth objectives, and stochastic gradient descent that converges in $O(1/\varepsilon^2)$ iterations for objectives that are sum of smooth functions. We provide the first improvement in this line of research. Our result is based on the variance reduction trick recently introduced to convex optimization, as well as a brand new analysis of variance reduction that is suitable for non-convex optimization. For objectives that are sum of smooth functions, our first-order minibatch stochastic method converges with an $O(1/\varepsilon)$ rate, and is faster than full gradient descent by $\Omega(n^{1/3})$. We demonstrate the effectiveness of our methods on empirical risk minimizations with non-convex loss functions and training neural nets.

Subfields: Artificial Intelligence, Computational Mechanics, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Optimization & Training

Citations in the corpus

Reducing Noise in GAN Training with Variance Reduced Extragradient (2019, background): “, 2016; Allen-Zhu and Hazan, 2016), the effectiveness of variance reduced methods is still an open question, and a recent technical report by Defazio and Bottou (2018) provides negative empirical results on the variance reduction aspect.”
Katyusha: the first direct acceleration of stochastic gradient methods (2016, methodology): “1) also lead to fast algorithms for neural nets [2, 20] as well as SVD, PCA, and CCA [4, 5, 17].”
SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator (2018, background): “In special, the finite-sum Stochastic Variance-Reduced Gradient (SVRG) and on-line Stochastically Controlled Stochastic Gradient (SCSG), to the gradient cost of Õ(min(n2/3 −2, −3.333)) (Allen-Zhu & Hazan, 2016; Reddi et al., 2016; Lei et al., 2017).”
Solving Weakly-Convex-Weakly-Concave Saddle-Point Problems as Successive Strongly Monotone Variational Inequalities (2018, background): “Instead of considering a min-max problem, most of them contribute to the non-convex minimization problem [29, 70, 30, 63, 61, 44, 1, 2, 25, 24, 72, 24].”
Unified Convergence Analysis of Stochastic Momentum Methods for Convex and Non-convex Optimization (2016, background): “Additionally, two recent studies (Reddi et al., 2016; Zhu and Hazan, 2016) have analyzed stochastic variance reduced gradient (SVRG) methods for nonconvex finite-sum problems and established potentially faster convergence than SG.”
Stochastic Approximation of Smooth and Strongly Convex Functions: Beyond the O(1/T) Convergence Rate (2019, background): “While our paper focuses on stochastic convex optimization, we note there has been a recent surge of interests in developing SA algorithms for non-convex problems (Ge et al., 2015; Allen-Zhu and Hazan, 2016; Reddi et al., 2016; Zhang et al., 2017b).”
Non-convex Finite-Sum Optimization Via SCSG Methods (2017, background): “When the component f i ( x ) satisﬁes the P-L condition, it is known that the global minimum can be found efﬁciently by SGD [17] and SVRG-type algorithms [26, 4].”
Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problems (2020, methodology): “Variance reduction techniques has been widely used in stochastic optimization [2, 4, 15, 22, 23, 29, 30, 35, 37].”
Momentum-Based Variance Reduction in Non-Convex SGD (2019, methodology): “The first application of variance-reduction method to non-convex SGD is due to Allen-Zhu and Hazan [2].”
NESTT: A Nonconvex Primal-Dual Splitting Method for Distributed and Stochastic Optimization (2016, background): “These features are critical in our following rate analysis.”
Data-Dependent Stability of Stochastic Gradient Descent (2017, background): “In this light, our work is also related to non-convex optimization by SGD. Literature on this subject typically studies rates of convergence to the stationary points (Ghadimi and Lan, 2013; Allen-Zhu and Hazan, 2016; Reddi et al., 2016), and ways to avoid saddles (Ge et al., 2015; Lee et al., 2016).”
A Stochastic Semismooth Newton Method for Nonsmooth Nonconvex Optimization (2018, methodology): “ach of the component functions fior even stronger assumptions. Ghadimi and Lan [29, 30] generalize the basic andacceleratedSGD methodto solvenonconvexandsmoothminimizationproblems. AllenZhu and Hazan [5] and Reddi et al. [66] analyze stochastic variance reduction techniques for the nonconvex version”
Stochastic Recursive Gradient Algorithm for Nonconvex Optimization (2017, background): “Limited results have been developed for the nonconvex problems [20, 3, 2], in particular, [20, 3] introduce nonconvex SVRG, and Natasha [2] is a new algorithm but a variant of SVRG for nonconvex optimization.”