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.

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

References in corpus (1)

• SLOPE - Adaptive variable selection via convex optimization

Cited by in corpus (219)

• 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
• Optimized first-order methods for smooth convex minimization
• 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
• Global Convergence of Stochastic Gradient Hamiltonian Monte Carlo for Non-Convex Stochastic Optimization: Non-Asymptotic Performance Bounds and Momentum-Based Acceleration
• Towards Riemannian Accelerated Gradient Methods
• HiGrad: Uncertainty Quantification for Online Learning and Stochastic Approximation
• A Nonsmooth Dynamical Systems Perspective on Accelerated Extensions of ADMM
• A new class of accelerated regularization methods, with application to bioluminescence tomography
• An Accelerated Correlation Filter Tracker
• On the diffusion approximation of nonconvex stochastic gradient descent
• Continuous-in-Depth Neural Networks
• 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 Optimization With Orthogonality Constraints
• Accelerated Linear Convergence of Stochastic Momentum Methods in Wasserstein Distances
• Gradient flows and proximal splitting methods: A unified view on accelerated and stochastic optimization
• Heavy Ball Neural Ordinary Differential Equations
• From Nesterov's Estimate Sequence to Riemannian Acceleration
• Accelerated First-Order Methods: Differential Equations and Lyapunov Functions
• Potential-Function Proofs for First-Order Methods
• Nesterov Acceleration for Equality-Constrained Convex Optimization via Continuously Differentiable Penalty Functions
• On Accelerated Methods in Optimization
• Neural Mechanics: Symmetry and Broken Conservation Laws in Deep Learning Dynamics
• A class of second-order geometric quasilinear hyperbolic PDEs and their application in imaging science
• On Learning Rates and Schrödinger Operators
• VR-SGD: A Simple Stochastic Variance Reduction Method for Machine Learning
• Accelerating Block Coordinate Descent for Nonnegative Tensor Factorization
• The Role of Memory in Stochastic Optimization
• A Fast First-Order Optimization Approach to Elastoplastic Analysis of Skeletal Structures
• Optimal Deterministic Algorithm Generation
• Accelerating Gradient Boosting Machine
• To Infinity and Beyond: Some ODE and PDE Case Studies
• A general system of differential equations to model first order adaptive algorithms
• Distributed Stochastic Gradient Descent: Nonconvexity, Nonsmoothness, and Convergence to Local Minima
• On-line Non-Convex Constrained Optimization
• Accelerated Learning with Robustness to Adversarial Regressors
• Accelerated Proximal Point Method for Maximally Monotone Operators
• 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
• Regularization in High-Dimensional Regression and Classification via Random Matrix Theory
• Generalized Affine Scaling Algorithms for Linear Programming Problems
• First order optimization methods based on Hessian-driven Nesterov accelerated gradient flow
• A Control-Theoretic Perspective on Optimal High-Order Optimization
• On the Convergence of Nesterov's Accelerated Gradient Method in Stochastic Settings
• Accelerated iterative regularization via dual diagonal descent
• Practical Perspectives on Symplectic Accelerated Optimization
• Convergence Rates of Inertial Primal-Dual Dynamical Methods for Separable Convex Optimization Problems
• Momentum Improves Optimization on Riemannian Manifolds
• Geometry of First-Order Methods and Adaptive Acceleration
• 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
• 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
• Implicit Regularization of Accelerated Methods in Hilbert Spaces
• Selection dynamics for deep neural networks
• On the Effectiveness of Richardson Extrapolation in Machine Learning
• Stochastic Heavy Ball
• ANITA: An Optimal Loopless Accelerated Variance-Reduced Gradient Method
• Aggregated Momentum: Stability Through Passive Damping
• On the Generalised Langevin Equation for Simulated Annealing
• Hessian barrier algorithms for linearly constrained optimization problems
• Potential Function-based Framework for Making the Gradients Small in Convex and Min-Max Optimization
• On the Curse of Memory in Recurrent Neural Networks: Approximation and Optimization Analysis
• Near-Optimal Methods for Minimizing Star-Convex Functions and Beyond
• Accelerated Optimization on Riemannian Manifolds via Discrete Constrained Variational Integrators
• On the Hyperparameters in Stochastic Gradient Descent with Momentum
• Nesterov's method with decreasing learning rate leads to accelerated stochastic gradient descent
• On Accelerating Distributed Convex Optimizations
• Uniform-in-Time Weak Error Analysis for Stochastic Gradient Descent Algorithms via Diffusion Approximation
• Generalized Linear Models with Linear Constraints for Microbiome Compositional Data
• Cooperative Beamforming for Wireless Fronthaul and Access Links in Ultra-Dense C-RANs with SWIPT: A First-Order Approach
• Acceleration by Stepsize Hedging I: Multi-Step Descent and the Silver Stepsize Schedule
• Noether: The More Things Change, the More Stay the Same
• Gradient descent with momentum --- to accelerate or to super-accelerate?
• A Toolkit For Steady States of Nonlinear Wave Equations: Continuous Time Nesterov and Exponential Time Differencing Schemes
• Ultra-low-energy defibrillation through adjoint optimization
• High-Resolution Modeling of the Fastest First-Order Optimization Method for Strongly Convex Functions
• A Unified Convergence Analysis of First Order Convex Optimization Methods via Strong Lyapunov Functions
• No-Regret Dynamics in the Fenchel Game: A Unified Framework for Algorithmic Convex Optimization
• 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
• On the Global Convergence of Continuous-Time Stochastic Heavy-Ball Method for Nonconvex Optimization
• Parametrized Accelerated Methods Free of Condition Number
• Accelerated Gradient Boosting
• Model predictive control of resistive wall mode for ITER
• How Does Momentum Help Frank Wolfe?
• A Continuous-time Perspective for Modeling Acceleration in Riemannian Optimization
• Accelerated differential inclusion for convex optimization
• An Optimal Control Theory for Accelerated Optimization
• Hessian-Free High-Resolution Nesterov Acceleration for Sampling
• Stochasticity of Deterministic Gradient Descent: Large Learning Rate for Multiscale Objective Function
• Control Interpretations for First-Order Optimization Methods
• Convergence of inertial dynamics and proximal algorithms governed by maximally monotone operators
• Asymptotic study of stochastic adaptive algorithm in non-convex landscape
• Finite-time and Fixed-time Convergence in Continuous-time Optimization
• Accelerated Flow for Probability Distributions
• Limiting Behaviors of Nonconvex-Nonconcave Minimax Optimization via Continuous-Time Systems
• Dataset Dynamics via Gradient Flows in Probability Space
• Perturbed primal-dual dynamics with damping and time scaling coefficients for affine constrained convex optimization problems
• Stochastic Modified Equations for Continuous Limit of Stochastic ADMM
• A New Primal-Dual Algorithm for a Class of Nonlinear Compositional Convex Optimization Problems
• Conjugate Gradients and Accelerated Methods Unified: The Approximate Duality Gap View
• 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
• On the second order asymptotical regularization of linear ill-posed inverse problems
• Fast symplectic integrator for Nesterov-type acceleration method
• Proximal bundle algorithms for nonsmooth convex optimization via fast gradient smooth methods
• 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
• Noether's Learning Dynamics: Role of Symmetry Breaking in Neural Networks
• Hamiltonian descent for composite objectives
• Efficient Consensus Model based on Proximal Gradient Method applied to Convolutional Sparse Problems
• The connections between Lyapunov functions for some optimization algorithms and differential equations
• Inducing Uniform Asymptotic Stability in Non-Autonomous Accelerated Optimization Dynamics via Hybrid Regularization
• Adaptive Hamiltonian Variational Integrators and Symplectic Accelerated Optimization
• Penalized Langevin dynamics with vanishing penalty for smooth and log-concave targets
• 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
• Provably Correct Learning Algorithms in the Presence of Time-Varying Features Using a Variational Perspective
• On Constraints in First-Order Optimization: A View from Non-Smooth Dynamical Systems
• A closed loop gradient descent algorithm applied to Rosenbrock's function
• Rethinking the Variational Interpretation of Nesterov's Accelerated Method
• An Explicit Convergence Rate for Nesterov's Method from SDP
• Non-ergodic Complexity of Convex Proximal Inertial Gradient Descents
• On Adapting Nesterov's Scheme to Accelerate Iterative Methods for Linear Problems
• Robust Hybrid Zero-Order Optimization Algorithms with Acceleration via Averaging in Time
• Revisiting the Role of Euler Numerical Integration on Acceleration and Stability in Convex Optimization
• $\beta$-High Resolution ODE and Phase Transition between NAG-SC and Heavy Ball Method
• Stochastic gradient algorithms from ODE splitting perspective
• DessiLBI: Exploring Structural Sparsity of Deep Networks via Differential Inclusion Paths
• Weighted Cheeger and Buser Inequalities, with Applications to Clustering and Cutting Probability Densities
• FLAG n' FLARE: Fast Linearly-Coupled Adaptive Gradient Methods
• Accelerated Information Gradient flow
• Projection Neural Network for a Class of Sparse Regression Problems with Cardinality Penalty
• Meta Learning in the Continuous Time Limit
• On the stability of optimization algorithms given by discretizations of the Euler-Lagrange ODE
• A gradient descent akin method for inequality constrained optimization
• Smoothing fast iterative hard thresholding algorithm for ${\ell }_0$ regularized nonsmooth convex regression problem
• Resource-Aware Discretization of Accelerated Optimization Flows
• On the Curved Geometry of Accelerated Optimization
• Online Algorithms and Policies Using Adaptive and Machine Learning Approaches
• Contractivity of Runge-Kutta methods for convex gradient systems
• Continuous-time Models for Stochastic Optimization Algorithms
• PDE-Inspired Algorithms for Semi-Supervised Learning on Point Clouds
• The Confluence of Networks, Games and Learning
• Gradient flow encoding with distance optimization adaptive step size
• Second order asymptotical regularization methods for inverse problems in partial differential equations
• A Discrete Variational Derivation of Accelerated Methods in Optimization
• Convergence Rate of Inertial Forward-Backward Algorithms Based on the Local Error Bound Condition
• 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)
• Proximal Distance Algorithms: Theory and Examples
• Towards Optimal Randomized Strategies in Adversarial Example Game
• Asymptotic for a second order evolution equation with vanishing damping term and Tikhonov regularization
• Forward-backward algorithms with different inertial terms for structured non-convex minimization problems
• Second order dynamical systems with penalty terms associated to monotone inclusions
• Multi-sample estimation of centered log-ratio matrix in microbiome studies
• Understanding Modern Techniques in Optimization: Frank-Wolfe, Nesterov's Momentum, and Polyak's Momentum
• An efficient method for computing stationary states of phase field crystal models