Accelerating Stochastic Gradient Descent For Least Squares Regression

Abstract

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.

54 pages, 3 figures, 1 table; updated acknowledgements, minor title change. Paper appeared in the proceedings of the Conference on Learning Theory (COLT), 2018

Cited by in corpus (39)

• The Step Decay Schedule: A Near Optimal, Geometrically Decaying Learning Rate Procedure For Least Squares
• Accelerating SGD with momentum for over-parameterized learning
• Bridging the Gap between Constant Step Size Stochastic Gradient Descent and Markov Chains
• Momentum-Based Variance Reduction in Non-Convex SGD
• Robust Distributed Accelerated Stochastic Gradient Methods for Multi-Agent Networks
• Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates
• Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron
• Decentralized Stochastic Gradient Langevin Dynamics and Hamiltonian Monte Carlo
• On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration
• A Universally Optimal Multistage Accelerated Stochastic Gradient Method
• Accelerated Stochastic Power Iteration
• Accelerated Linear Convergence of Stochastic Momentum Methods in Wasserstein Distances
• The Role of Memory in Stochastic Optimization
• A Unified Analysis of First-Order Methods for Smooth Games via Integral Quadratic Constraints
• Reducing the variance in online optimization by transporting past gradients
• Accelerated Learning with Robustness to Adversarial Regressors
• Federated Composite Optimization
• Benign Overfitting of Constant-Stepsize SGD for Linear Regression
• Sharp Bounds for Federated Averaging (Local SGD) and Continuous Perspective
• Statistical Adaptive Stochastic Gradient Methods
• Tight High Probability Bounds for Linear Stochastic Approximation with Fixed Stepsize
• Last iterate convergence of SGD for Least-Squares in the Interpolation regime
• Momentum via Primal Averaging: Theoretical Insights and Learning Rate Schedules for Non-Convex Optimization
• Nesterov's method with decreasing learning rate leads to accelerated stochastic gradient descent
• The Speed-Robustness Trade-Off for First-Order Methods with Additive Gradient Noise
• A High-order Tuner for Accelerated Learning and Control
• SGD in the Large: Average-case Analysis, Asymptotics, and Stepsize Criticality
• A Stochastic Subgradient Method for Distributionally Robust Non-Convex Learning
• Learning Curves for SGD on Structured Features
• A Stochastic Primal-Dual Method for Optimization with Conditional Value at Risk Constraints
• A hybrid ensemble method with negative correlation learning for regression
• A Continuized View on Nesterov Acceleration for Stochastic Gradient Descent and Randomized Gossip
• On the Last Iterate Convergence of Momentum Methods
• Predictive Local Smoothness for Stochastic Gradient Methods
• Big-Step-Little-Step: Efficient Gradient Methods for Objectives with Multiple Scales
• An Adaptive Remote Stochastic Gradient Method for Training Neural Networks
• COCO Denoiser: Using Co-Coercivity for Variance Reduction in Stochastic Convex Optimization
• Mixing of Stochastic Accelerated Gradient Descent
• Compositional Stochastic Average Gradient for Machine Learning and Related Applications