From Averaging to Acceleration, There is Only a Step-size

Abstract

We show that accelerated gradient descent, averaged gradient descent and the heavy-ball method for non-strongly-convex problems may be reformulated as constant parameter second-order difference equation algorithms, where stability of the system is equivalent to convergence at rate O(1/n 2), where n is the number of iterations. We provide a detailed analysis of the eigenvalues of the corresponding linear dynamical system , showing various oscillatory and non-oscillatory behaviors, together with a sharp stability result with explicit constants. We also consider the situation where noisy gradients are available, where we extend our general convergence result, which suggests an alternative algorithm (i.e., with different step sizes) that exhibits the good aspects of both averaging and acceleration.

References in corpus (5)

• A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights
• Convergence Rates of Inexact Proximal-Gradient Methods for Convex Optimization
• Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)
• Adaptive Restart for Accelerated Gradient Schemes
• Constant Step Size Least-Mean-Square: Bias-Variance Trade-offs and Optimal Sampling Distributions

Cited by in corpus (34)

• A Variational Perspective on Accelerated Methods in Optimization
• Stochastic Gradient Descent as Approximate Bayesian Inference
• The Unusual Effectiveness of Averaging in GAN Training
• Dive into Deep Learning
• A Variational Analysis of Stochastic Gradient Algorithms
• Towards Riemannian Accelerated Gradient Methods
• Robust Distributed Accelerated Stochastic Gradient Methods for Multi-Agent Networks
• Decentralized Stochastic Gradient Langevin Dynamics and Hamiltonian Monte Carlo
• A Universally Optimal Multistage Accelerated Stochastic Gradient Method
• On the Iteration Complexity of Oblivious First-Order Optimization Algorithms
• Accelerated Linear Convergence of Stochastic Momentum Methods in Wasserstein Distances
• Dissipativity Theory for Nesterov's Accelerated Method
• Differentially Private Accelerated Optimization Algorithms
• Fast inertial dynamics and FISTA algorithms in convex optimization. Perturbation aspects
• Asymptotic Analysis via Stochastic Differential Equations of Gradient Descent Algorithms in Statistical and Computational Paradigms
• Average-case Acceleration Through Spectral Density Estimation
• On the interplay between noise and curvature and its effect on optimization and generalization
• Stochastic Heavy Ball
• On the Effectiveness of Richardson Extrapolation in Machine Learning
• Nesterov's method with decreasing learning rate leads to accelerated stochastic gradient descent
• Momentum via Primal Averaging: Theoretical Insights and Learning Rate Schedules for Non-Convex Optimization
• No-Regret Dynamics in the Fenchel Game: A Unified Framework for Algorithmic Convex Optimization
• A Generic online acceleration scheme for Optimization algorithms via Relaxation and Inertia
• Stochastic Composite Least-Squares Regression with convergence rate O(1/n)
• Noise and Fluctuation of Finite Learning Rate Stochastic Gradient Descent
• Conjugate Gradients and Accelerated Methods Unified: The Approximate Duality Gap View
• Analytical Study of Momentum-Based Acceleration Methods in Paradigmatic High-Dimensional Non-Convex Problems
• From Convex Optimization to MDPs: A Review of First-Order, Second-Order and Quasi-Newton Methods for MDPs
• Quickly Finding a Benign Region via Heavy Ball Momentum in Non-Convex Optimization
• Learning Curves for SGD on Structured Features
• Larger is Better: The Effect of Learning Rates Enjoyed by Stochastic Optimization with Progressive Variance Reduction
• Stable Anderson Acceleration for Deep Learning
• A New Class of Composite Objective Multi-step Estimating-sequence Techniques (COMET)
• A Modular Analysis of Provable Acceleration via Polyak's Momentum: Training a Wide ReLU Network and a Deep Linear Network