Accelerating Stochastic Gradient Descent

By Prateek Jain, Sham M. Kakade, Rahul Kidambi, Praneeth Netrapalli, Aaron Sidford. 2017

84 citations recorded by the source corpus.

There is widespread sentiment that it is not possible to effectively utilize fast gradient methods (e.g. Nesterov's acceleration, conjugate gradient, heavy ball) for the purposes of stochastic optimization due to their instability and error accumulation, a notion made precise in d'Aspremont 2008 and Devolder, Glineur, and Nesterov 2014. This work considers these issues for the special case of stochastic approximation for the least squares regression problem, and our main result refutes the conventional wisdom by showing that acceleration can be made robust to statistical errors. In particular, this work introduces an accelerated stochastic gradient method that provably achieves the minimax optimal statistical risk faster than stochastic gradient descent. Critical to the analysis is a sharp characterization of accelerated stochastic gradient descent as a stochastic process. We hope this characterization gives insights towards the broader question of designing simple and effective accelerated stochastic methods for more general convex and non-convex optimization problems.

Subfields: Artificial Intelligence, Computational Mechanics

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

Citations in the corpus

Communication trade-offs for synchronized distributed SGD with large step size (2019, background): “…nonasymptotic analysis is provided by Défossez and Bach (2015), acceleration under the additive noise oracle (see Assumption A4 below) is studied by Dieuleveut et al. (2016) (without this assumption by Jain et al. (2017)), and Jain et al. (2016) analyze the effects of mini-batch and tail averaging.”
Communication trade-offs for Local-SGD with large step size (2019, methodology): “…non-asymptotic analysis is provided by Défossez and Bach [28], acceleration under the additive noise oracle (see Assumption A 4 below) is studied by Dieuleveut et al. [29] (without this assumption by Jain et al. [30]), and Jain et al. [20] analyze the effects of mini-batch and tail averaging.”
Quasi-hyperbolic momentum and Adam for deep learning (2018, background): “Jain et al. (2017) and Kidambi et al. (2018) point out various failures of momentum and NAG in the setting of stochastic least squares optimization.”
On the Insufficiency of Existing Momentum Schemes for Stochastic Optimization (2018, methodology): “Jain et al. (2017) require it to be smaller than 1 / 6 but any constant smaller than 1 seems to work in practice.”
An Adaptive Remote Stochastic Gradient Method for Training Neural Networks (2019, background): “They further present ASGD [13, 14] and show improvement on SGD in any information-theoretically admissible regime.”
The Step Decay Schedule: A Near Optimal, Geometrically Decaying Learning Rate Procedure (2019, methodology): “…that present a non-asymptotic understanding of SGD for least squares regression, with the caveat being that these results crucially rely on iterate averaging with constant stepsize sequences (Bach and Moulines, 2013; D ´ efossez and Bach, 2015; Jain et al., 2016, 2017b,a; Neu and Rosasco, 2018).”
Parallelizing Stochastic Gradient Descent for Least Squares Regression: Mini-batching, Averaging, and Model Misspecification (2016, methodology): “Refer to Jain et al. (2017b) for more details.”
On Acceleration with Noise-Corrupted Gradients (2018, methodology): “mi & Lan,2013) for the setting of constrained smooth and strongly convex minimization, by coupling AC-SA algorithm from (Ghadimi & Lan,2012) with a domain-shrinking procedure. More recently, (Jain et al., 2018) completely closed this gap for the case of linear regression. These references ar”
Accelerating Stochastic Training for Over-parametrized Learning (2018, methodology): “Following (Jain et al., 2017), we introduce the quantity κ̃ (called statistical condition number in (Jain et al., 2017)), which is the smallest positive real number such that E [ ‖x̃‖2H−1 x̃x̃ T ] κ̃H.”