A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights

Abstract

We derive a second-order ordinary differential equation (ODE) which is the limit of Nesterov's accelerated gradient method. This ODE exhibits approximate equivalence to Nesterov's scheme and thus can serve as a tool for analysis. We show that the continuous time ODE allows for a better understanding of Nesterov's scheme. As a byproduct, we obtain a family of schemes with similar convergence rates. The ODE interpretation also suggests restarting Nesterov's scheme leading to an algorithm, which can be rigorously proven to converge at a linear rate whenever the objective is strongly convex.

To appear in Journal of Machine Learning Research. Added more simulation studies. Preliminary version appeared in NIPS 2014

Cited by in corpus (218)

• A Variational Perspective on Accelerated Methods in Optimization
• The rate of convergence of Nesterov's accelerated forward-backward method is actually faster than $1/k^2$
• A Review on Deep Learning in Medical Image Reconstruction
• Ensemble Kalman Inversion: A Derivative-Free Technique For Machine Learning Tasks
• A Lyapunov Analysis of Momentum Methods in Optimization
• On the Optimization of Deep Networks: Implicit Acceleration by Overparameterization
• Exact Worst-case Performance of First-order Methods for Composite Convex Optimization
• Review: Deep Learning in Electron Microscopy
• Even Faster Accelerated Coordinate Descent Using Non-Uniform Sampling
• Understanding the Acceleration Phenomenon via High-Resolution Differential Equations
• From Averaging to Acceleration, There is Only a Step-size
• Edge Federated Learning Via Unit-Modulus Over-The-Air Computation
• The Approximate Duality Gap Technique: A Unified Theory of First-Order Methods
• From differential equation solvers to accelerated first-order methods for convex optimization
• Direct Runge-Kutta Discretization Achieves Acceleration
• A Generalized Accelerated Composite Gradient Method: Uniting Nesterov's Fast Gradient Method and FISTA
• Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent
• A Dynamical Systems Perspective on Nesterov Acceleration
• ADMM and Accelerated ADMM as Continuous Dynamical Systems
• Generalizing the optimized gradient method for smooth convex minimization
• An Accelerated Composite Gradient Method for Large-scale Composite Objective Problems
• Implicit Regularization and Momentum Algorithms in Nonlinearly Parameterized Adaptive Control and Prediction
• Is There an Analog of Nesterov Acceleration for MCMC?
• Hamiltonian Descent Methods
• Inducing strong convergence of trajectories in dynamical systems associated to monotone inclusions with composite structure
• On Symplectic Optimization
• On the Koopman operator of algorithms
• Towards Riemannian Accelerated Gradient Methods
• Global Convergence of Stochastic Gradient Hamiltonian Monte Carlo for Non-Convex Stochastic Optimization: Non-Asymptotic Performance Bounds and Momentum-Based Acceleration
• A Nonsmooth Dynamical Systems Perspective on Accelerated Extensions of ADMM
• HiGrad: Uncertainty Quantification for Online Learning and Stochastic Approximation
• An Accelerated Correlation Filter Tracker
• A new class of accelerated regularization methods, with application to bioluminescence tomography
• Continuous-in-Depth Neural Networks
• On the diffusion approximation of nonconvex stochastic gradient descent
• Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balanced
• Decentralized Stochastic Gradient Langevin Dynamics and Hamiltonian Monte Carlo
• Universal gradient descent
• Fast Stochastic Variance Reduced Gradient Method with Momentum Acceleration for Machine Learning
• KKT Conditions, First-Order and Second-Order Optimization, and Distributed Optimization: Tutorial and Survey
• Accelerated Linear Convergence of Stochastic Momentum Methods in Wasserstein Distances
• Accelerated Optimization With Orthogonality Constraints
• Gradient flows and proximal splitting methods: A unified view on accelerated and stochastic optimization
• Heavy Ball Neural Ordinary Differential Equations
• Accelerated First-Order Methods: Differential Equations and Lyapunov Functions
• From Nesterov's Estimate Sequence to Riemannian Acceleration
• Neural Mechanics: Symmetry and Broken Conservation Laws in Deep Learning Dynamics
• Nesterov Acceleration for Equality-Constrained Convex Optimization via Continuously Differentiable Penalty Functions
• Potential-Function Proofs for First-Order Methods
• A class of second-order geometric quasilinear hyperbolic PDEs and their application in imaging science
• On Accelerated Methods in Optimization
• The Role of Memory in Stochastic Optimization
• VR-SGD: A Simple Stochastic Variance Reduction Method for Machine Learning
• A Fast First-Order Optimization Approach to Elastoplastic Analysis of Skeletal Structures
• On Learning Rates and Schrödinger Operators
• Optimal Deterministic Algorithm Generation
• Accelerating Block Coordinate Descent for Nonnegative Tensor Factorization
• To Infinity and Beyond: Some ODE and PDE Case Studies
• A general system of differential equations to model first order adaptive algorithms
• Accelerating Gradient Boosting Machine
• On-line Non-Convex Constrained Optimization
• Accelerated Learning with Robustness to Adversarial Regressors
• Accelerated Proximal Point Method for Maximally Monotone Operators
• Distributed Stochastic Gradient Descent: Nonconvexity, Nonsmoothness, and Convergence to Local Minima
• The Physical Systems Behind Optimization Algorithms
• New Analysis of Linear Convergence of Gradient-type Methods via Unifying Error Bound Conditions
• Accelerating Greedy Coordinate Descent Methods
• On the Generalization of Stochastic Gradient Descent with Momentum
• Generalized Affine Scaling Algorithms for Linear Programming Problems
• A Control-Theoretic Perspective on Optimal High-Order Optimization
• Regularization in High-Dimensional Regression and Classification via Random Matrix Theory
• On the Convergence of Nesterov's Accelerated Gradient Method in Stochastic Settings
• First order optimization methods based on Hessian-driven Nesterov accelerated gradient flow
• Practical Perspectives on Symplectic Accelerated Optimization
• Accelerated iterative regularization via dual diagonal descent
• Convergence Rates of Inertial Primal-Dual Dynamical Methods for Separable Convex Optimization Problems
• Geometry of First-Order Methods and Adaptive Acceleration
• Momentum Improves Optimization on Riemannian Manifolds
• Multi-sample Estimation of Bacterial Composition Matrix in Metagenomics Data
• Asymptotic Analysis via Stochastic Differential Equations of Gradient Descent Algorithms in Statistical and Computational Paradigms
• Convex optimization via inertial algorithms with vanishing Tikhonov regularization: fast convergence to the minimum norm solution
• Stochastic Relaxed Inertial Forward-Backward-Forward splitting for Monotone Inclusions in Hilbert spaces
• ANITA: An Optimal Loopless Accelerated Variance-Reduced Gradient Method
• On the Effectiveness of Richardson Extrapolation in Machine Learning
• Selection dynamics for deep neural networks
• Hessian barrier algorithms for linearly constrained optimization problems
• Implicit Regularization of Accelerated Methods in Hilbert Spaces
• Aggregated Momentum: Stability Through Passive Damping
• Stochastic Heavy Ball
• Potential Function-based Framework for Making the Gradients Small in Convex and Min-Max Optimization
• On the Generalised Langevin Equation for Simulated Annealing
• On the Hyperparameters in Stochastic Gradient Descent with Momentum
• Accelerated Optimization on Riemannian Manifolds via Discrete Constrained Variational Integrators
• Generalized Linear Models with Linear Constraints for Microbiome Compositional Data
• Near-Optimal Methods for Minimizing Star-Convex Functions and Beyond
• On the Curse of Memory in Recurrent Neural Networks: Approximation and Optimization Analysis
• Uniform-in-Time Weak Error Analysis for Stochastic Gradient Descent Algorithms via Diffusion Approximation
• Nesterov's method with decreasing learning rate leads to accelerated stochastic gradient descent
• Acceleration by Stepsize Hedging I: Multi-Step Descent and the Silver Stepsize Schedule
• On Accelerating Distributed Convex Optimizations
• Cooperative Beamforming for Wireless Fronthaul and Access Links in Ultra-Dense C-RANs with SWIPT: A First-Order Approach
• Gradient descent with momentum --- to accelerate or to super-accelerate?
• A Unified Convergence Analysis of First Order Convex Optimization Methods via Strong Lyapunov Functions
• A Toolkit For Steady States of Nonlinear Wave Equations: Continuous Time Nesterov and Exponential Time Differencing Schemes
• Ultra-low-energy defibrillation through adjoint optimization
• No-Regret Dynamics in the Fenchel Game: A Unified Framework for Algorithmic Convex Optimization
• High-Resolution Modeling of the Fastest First-Order Optimization Method for Strongly Convex Functions
• Noether: The More Things Change, the More Stay the Same
• A High-order Tuner for Accelerated Learning and Control
• Optimization with Momentum: Dynamical, Control-Theoretic, and Symplectic Perspectives
• Acceleration and Averaging in Stochastic Mirror Descent Dynamics
• A Continuous-Time Nesterov Accelerated Gradient Method for Centralized and Distributed Online Convex Optimization
• Maximum likelihood estimation of regularisation parameters in high-dimensional inverse problems: an empirical Bayesian approach. Part II: Theoretical Analysis
• SGD in the Large: Average-case Analysis, Asymptotics, and Stepsize Criticality
• Global Riemannian Acceleration in Hyperbolic and Spherical Spaces
• A Dynamical View on Optimization Algorithms of Overparameterized Neural Networks
• Exploring Critical Points of Energy Landscapes: From Low-Dimensional Examples to Phase Field Crystal PDEs
• A Direct Shooting Method is Equivalent to an Indirect Method
• Continuous-time Lower Bounds for Gradient-based Algorithms
• An $O(s^r)$-Resolution ODE Framework for Understanding Discrete-Time Algorithms and Applications to the Linear Convergence of Minimax Problems
• Accelerated Gradient Methods with Memory
• Accelerated graph-based nonlinear denoising filters
• Local and Global Convergence of an Inertial Version of Forward-Backward Splitting
• The long time behavior and the rate of convergence of symplectic convex algorithms obtained via splitting discretizations of inertial damping systems
• Parametrized Accelerated Methods Free of Condition Number
• Model predictive control of resistive wall mode for ITER
• Accelerated Gradient Boosting
• An Optimal Control Theory for Accelerated Optimization
• How Does Momentum Help Frank Wolfe?
• Control Interpretations for First-Order Optimization Methods
• Accelerated differential inclusion for convex optimization
• Stochasticity of Deterministic Gradient Descent: Large Learning Rate for Multiscale Objective Function
• Hessian-Free High-Resolution Nesterov Acceleration for Sampling
• Convergence of inertial dynamics and proximal algorithms governed by maximally monotone operators
• A Continuous-time Perspective for Modeling Acceleration in Riemannian Optimization
• Asymptotic study of stochastic adaptive algorithm in non-convex landscape
• On the Global Convergence of Continuous-Time Stochastic Heavy-Ball Method for Nonconvex Optimization
• Accelerated Flow for Probability Distributions
• Finite-time and Fixed-time Convergence in Continuous-time Optimization
• Limiting Behaviors of Nonconvex-Nonconcave Minimax Optimization via Continuous-Time Systems
• Dataset Dynamics via Gradient Flows in Probability Space
• Conjugate Gradients and Accelerated Methods Unified: The Approximate Duality Gap View
• Stochastic Modified Equations for Continuous Limit of Stochastic ADMM
• A New Primal-Dual Algorithm for a Class of Nonlinear Compositional Convex Optimization Problems
• A piecewise conservative method for unconstrained convex optimization
• Reverse engineering learned optimizers reveals known and novel mechanisms
• Analytical Study of Momentum-Based Acceleration Methods in Paradigmatic High-Dimensional Non-Convex Problems
• Acceleration via Fractal Learning Rate Schedules
• Inertial primal-dual methods for linear equality constrained convex optimization problems
• A Contraction Theory Approach to Optimization Algorithms from Acceleration Flows
• Applying FISTA to optimization problems (with or) without minimizers
• Nesterov Acceleration of Alternating Least Squares for Canonical Tensor Decomposition: Momentum Step Size Selection and Restart Mechanisms
• A unified differential equation solver approach for separable convex optimization: splitting, acceleration and nonergodic rate
• A geometric integration approach to smooth optimisation: Foundations of the discrete gradient method
• On Tuning Neural ODE for Stability, Consistency and Faster Convergence
• Fast symplectic integrator for Nesterov-type acceleration method
• On the second order asymptotical regularization of linear ill-posed inverse problems
• Perturbed primal-dual dynamics with damping and time scaling coefficients for affine constrained convex optimization problems
• Delayed Projection Techniques for Linearly Constrained Problems: Convergence Rates, Acceleration, and Applications
• A Conservation Law Method in Optimization
• On Inexact Accelerated Proximal Gradient Methods with Relative Error Rules
• Searching equillibriums in large transport networks
• Variational Optimization on Lie Groups, with Examples of Leading (Generalized) Eigenvalue Problems
• The Search direction Correction makes first-order methods faster
• Proximal bundle algorithms for nonsmooth convex optimization via fast gradient smooth methods
• New Computational Guarantees for Solving Convex Optimization Problems with First Order Methods, via a Function Growth Condition Measure
• Second-order Information in First-order Optimization Methods
• A Continuized View on Nesterov Acceleration for Stochastic Gradient Descent and Randomized Gossip
• Inducing Uniform Asymptotic Stability in Non-Autonomous Accelerated Optimization Dynamics via Hybrid Regularization
• Hamiltonian descent for composite objectives
• The connections between Lyapunov functions for some optimization algorithms and differential equations
• Efficient Consensus Model based on Proximal Gradient Method applied to Convolutional Sparse Problems
• Adaptive Hamiltonian Variational Integrators and Symplectic Accelerated Optimization
• Penalized Langevin dynamics with vanishing penalty for smooth and log-concave targets
• Provably Correct Learning Algorithms in the Presence of Time-Varying Features Using a Variational Perspective
• Noether's Learning Dynamics: Role of Symmetry Breaking in Neural Networks
• On Constraints in First-Order Optimization: A View from Non-Smooth Dynamical Systems
• A closed loop gradient descent algorithm applied to Rosenbrock's function
• On the Curved Geometry of Accelerated Optimization
• On Adapting Nesterov's Scheme to Accelerate Iterative Methods for Linear Problems
• Understanding Modern Techniques in Optimization: Frank-Wolfe, Nesterov's Momentum, and Polyak's Momentum
• Contractivity of Runge-Kutta methods for convex gradient systems
• Rethinking the Variational Interpretation of Nesterov's Accelerated Method
• The Confluence of Networks, Games and Learning
• An Explicit Convergence Rate for Nesterov's Method from SDP
• Non-ergodic Complexity of Convex Proximal Inertial Gradient Descents
• Resource-Aware Discretization of Accelerated Optimization Flows
• Continuous-time Models for Stochastic Optimization Algorithms
• DessiLBI: Exploring Structural Sparsity of Deep Networks via Differential Inclusion Paths
• Second order dynamical systems with penalty terms associated to monotone inclusions
• Revisiting the Role of Euler Numerical Integration on Acceleration and Stability in Convex Optimization
• PDE-Inspired Algorithms for Semi-Supervised Learning on Point Clouds
• Accelerated Information Gradient flow
• $\beta$-High Resolution ODE and Phase Transition between NAG-SC and Heavy Ball Method
• Stochastic gradient algorithms from ODE splitting perspective
• Weighted Cheeger and Buser Inequalities, with Applications to Clustering and Cutting Probability Densities
• Convergence Rate of Inertial Forward-Backward Algorithms Based on the Local Error Bound Condition
• Forward-backward algorithms with different inertial terms for structured non-convex minimization problems
• On the stability of optimization algorithms given by discretizations of the Euler-Lagrange ODE
• An efficient method for computing stationary states of phase field crystal models
• Gradient flow encoding with distance optimization adaptive step size
• Meta Learning in the Continuous Time Limit
• Smoothing fast iterative hard thresholding algorithm for ${\ell }_0$ regularized nonsmooth convex regression problem
• A Discrete Variational Derivation of Accelerated Methods in Optimization
• A gradient descent akin method for inequality constrained optimization
• Second order asymptotical regularization methods for inverse problems in partial differential equations
• Monotone Inclusions, Acceleration and Closed-Loop Control
• Convergence and Stability of the Stochastic Proximal Point Algorithm with Momentum
• Inertial Newton Algorithms Avoiding Strict Saddle Points
• A New Class of Composite Objective Multi-step Estimating-sequence Techniques (COMET)
• Towards Optimal Randomized Strategies in Adversarial Example Game
• Robust Hybrid Zero-Order Optimization Algorithms with Acceleration via Averaging in Time
• FLAG n' FLARE: Fast Linearly-Coupled Adaptive Gradient Methods
• Asymptotic for a second order evolution equation with vanishing damping term and Tikhonov regularization
• Proximal Distance Algorithms: Theory and Examples
• Projection Neural Network for a Class of Sparse Regression Problems with Cardinality Penalty
• Online Algorithms and Policies Using Adaptive and Machine Learning Approaches
• Multi-sample estimation of centered log-ratio matrix in microbiome studies