Stochastic Variance Reduction for Nonconvex Optimization

By Sashank J. Reddi, Ahmed S. Hefny, Suvrit Sra, Barnab'as P'oczos, Alex Smola. 2016

654 citations recorded by the source corpus.

We study nonconvex finite-sum problems and analyze stochastic variance reduced gradient (SVRG) methods for them. SVRG and related methods have recently surged into prominence for convex optimization given their edge over stochastic gradient descent (SGD); but their theoretical analysis almost exclusively assumes convexity. In contrast, we prove non-asymptotic rates of convergence (to stationary points) of SVRG for nonconvex optimization, and show that it is provably faster than SGD and gradient descent. We also analyze a subclass of nonconvex problems on which SVRG attains linear convergence to the global optimum. We extend our analysis to mini-batch variants of SVRG, showing (theoretical) linear speedup due to mini-batching in parallel settings.

Subfields: Artificial Intelligence, Computational Mechanics, Statistics and Probability, 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 Statistics and Probability

In Optimization & Training

Citations in the corpus

On Sampling Strategies for Neural Network-based Collaborative Filtering (2017, background): “So we show the SGD with the proposed sampling strategies follow a local convergence bound (similar to [10, 24]).”
Adaptive Federated Optimization (2020, background): “Assumptions 1 and 3 are fairly standard in nonconvex optimization literature (Reddi et al., 2016; Ward et al., 2018; Zaheer et al., 2018).”
Federated Optimization: Distributed Machine Learning for On-Device Intelligence (2016, background): “Vanilla experiments in [43, 77] suggest that SVRG matches basic SGD, and even outperforms in the sense that variance of the iterates seems to be signiﬁcantly smaller for SVRG.”
ATOMO: Communication-efficient Learning via Atomic Sparsification (2018, background): “This is a well-known fact in optimization, and most convergence bounds for stochastic-gradient based methods, including minibatch, involve upper bounds on E[‖ĝ(wk)‖](2)2, in a multiplicative form, for both convex and nonconvex setups [39, 40, 41, 42, 42, 43, 44, 45, 46, 47].”
Learning to Reweight Examples for Robust Deep Learning (2018, background): “Analysis: convergence of the reweighted training Convergence results of SGD based optimization methods are well-known (Reddi et al., 2016).”
Stochastic, Distributed and Federated Optimization for Machine Learning (2017, background): “Vanilla experiments in [80, 146] suggest that SVRG matches basic SGD, and even outperforms in the sense that variance of the iterates seems to be significantly smaller for SVRG.”
Variance Reduction for Matrix Games (2019, methodology): “Similar bounds are used in variance reduction for bilinear saddle-point problems with Euclidean norm [3], as well as for finding stationary points in smooth nonconvex finite-sum problems [2, 34, 12, 46].”
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].”
Hybrid Stochastic Gradient Descent Algorithms for Stochastic Nonconvex Optimization (2019, methodology): “We verify our algorithms on two numerical examples and compare them with several existing methods: SVRG [23], SVRG+ [11], SPIDER [8], SpiderBoost [27], and SGD [9].”
Differentially Private Empirical Risk Minimization Revisited: Faster and More General (2018, neutral): “This topic has been studied in [18][27][26][24][22].”