On the Convergence of Nesterov's Accelerated Gradient Method in Stochastic Settings

Abstract

We study Nesterov's accelerated gradient method with constant step-size and momentum parameters in the stochastic approximation setting (unbiased gradients with bounded variance) and the finite-sum setting (where randomness is due to sampling mini-batches). To build better insight into the behavior of Nesterov's method in stochastic settings, we focus throughout on objectives that are smooth, strongly-convex, and twice continuously differentiable. In the stochastic approximation setting, Nesterov's method converges to a neighborhood of the optimal point at the same accelerated rate as in the deterministic setting. Perhaps surprisingly, in the finite-sum setting, we prove that Nesterov's method may diverge with the usual choice of step-size and momentum, unless additional conditions on the problem related to conditioning and data coherence are satisfied. Our results shed light as to why Nesterov's method may fail to converge or achieve acceleration in the finite-sum setting.

References in corpus (10)

• Scikit-learn: Machine Learning in Python
• A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights
• Quasi-hyperbolic momentum and Adam for deep learning
• Unified Convergence Analysis of Stochastic Momentum Methods for Convex and Non-convex Optimization
• Accelerating SGD with momentum for over-parameterized learning
• On Acceleration with Noise-Corrupted Gradients
• Understanding the Role of Momentum in Stochastic Gradient Methods
• Estimate Sequences for Variance-Reduced Stochastic Composite Optimization
• Accelerated Linear Convergence of Stochastic Momentum Methods in Wasserstein Distances
• Negative Momentum for Improved Game Dynamics

Cited by in corpus (4)

• A Selective Review on Statistical Methods for Massive Data Computation: Distributed Computing, Subsampling, and Minibatch Techniques
• Nesterov's method with decreasing learning rate leads to accelerated stochastic gradient descent
• An Asymptotic Analysis of Minibatch-Based Momentum Methods for Linear Regression Models
• Memory Augmented Optimizers for Deep Learning