On Acceleration with Noise-Corrupted Gradients
arXiv:1805.12591
Abstract
Accelerated algorithms have broad applications in large-scale optimization, due to their generality and fast convergence. However, their stability in the practical setting of noise-corrupted gradient oracles is not well-understood. This paper provides two main technical contributions: (i) a new accelerated method AGDP that generalizes Nesterov's AGD and improves on the recent method AXGD (Diakonikolas & Orecchia, 2018), and (ii) a theoretical study of accelerated algorithms under noisy and inexact gradient oracles, which is supported by numerical experiments. This study leverages the simplicity of AGDP and its analysis to clarify the interaction between noise and acceleration and to suggest modifications to the algorithm that reduce the mean and variance of the error incurred due to the gradient noise.
arXiv commentAppeared in Proc. ICML'18; v2 corrects the statement of Corollary 3.9; v3 added references to concurrent work
Cited by in corpus (14)
- The Approximate Duality Gap Technique: A Unified Theory of First-Order Methods
- Estimate Sequences for Stochastic Composite Optimization: Variance Reduction, Acceleration, and Robustness to Noise
- Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron
- A Universally Optimal Multistage Accelerated Stochastic Gradient Method
- A Generic Acceleration Framework for Stochastic Composite Optimization
- Generalized Mirror Prox for Monotone Variational Inequalities: Universality and Inexact Oracle
- On the Convergence of Nesterov's Accelerated Gradient Method in Stochastic Settings
- Accelerated Dual Averaging Methods for Decentralized Constrained Optimization
- Acceleration with a Ball Optimization Oracle
- Global Riemannian Acceleration in Hyperbolic and Spherical Spaces
- Conjugate Gradients and Accelerated Methods Unified: The Approximate Duality Gap View
- Parameter-free Locally Accelerated Conditional Gradients
- Locally Accelerated Conditional Gradients
- Convergence Analysis of Accelerated Stochastic Gradient Descent under the Growth Condition