A Universally Optimal Multistage Accelerated Stochastic Gradient Method
arXiv:1901.08022
Abstract
We study the problem of minimizing a strongly convex, smooth function when we have noisy estimates of its gradient. We propose a novel multistage accelerated algorithm that is universally optimal in the sense that it achieves the optimal rate both in the deterministic and stochastic case and operates without knowledge of noise characteristics. The algorithm consists of stages that use a stochastic version of Nesterov's method with a specific restart and parameters selected to achieve the fastest reduction in the bias-variance terms in the convergence rate bounds.
arXiv comment33rd Conference on Neural Information Processing Systems (NeurIPS 2019)
References in corpus (10)
- Adding Gradient Noise Improves Learning for Very Deep Networks
- Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysis
- Understanding the Acceleration Phenomenon via High-Resolution Differential Equations
- From Averaging to Acceleration, There is Only a Step-size
- Accelerating Stochastic Gradient Descent For Least Squares Regression
- On Acceleration with Noise-Corrupted Gradients
- Global Convergence of Stochastic Gradient Hamiltonian Monte Carlo for Non-Convex Stochastic Optimization: Non-Asymptotic Performance Bounds and Momentum-Based Acceleration
- Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron
- On the Iteration Complexity of Oblivious First-Order Optimization Algorithms
- Breaking Reversibility Accelerates Langevin Dynamics for Global Non-Convex Optimization
Cited by in corpus (7)
- The Step Decay Schedule: A Near Optimal, Geometrically Decaying Learning Rate Procedure For Least Squares
- Characterizing the Exact Behaviors of Temporal Difference Learning Algorithms Using Markov Jump Linear System Theory
- Robust Distributed Accelerated Stochastic Gradient Methods for Multi-Agent Networks
- Accelerated Linear Convergence of Stochastic Momentum Methods in Wasserstein Distances
- A Generic Acceleration Framework for Stochastic Composite Optimization
- From low probability to high confidence in stochastic convex optimization
- Convergence Analysis of Accelerated Stochastic Gradient Descent under the Growth Condition