A Dynamical Systems Perspective on Nesterov Acceleration

2019/05/17 by Michael Muehlebach, Michael I. Jordan, Muehlebach, Michael +1 · 36 citations
Mathematics · Physics and Astronomy · #Acceleration #Applied mathematics #Classical mechanics #Curvature #Differential (mechanical device) #Differential equation #Discretization #Dynamical system (definition) #Dynamical systems theory #Euler method #Euler's formula #FOS: Computer and information sciences #FOS: Electrical engineering #FOS: Mathematics #Geometry #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Mathematical analysis #Mathematics #Mechanical and Optical Resonators #Model Reduction and Neural Networks #Numerical methods for differential equations #Optimization and Control (math.OC) #Ordinary differential equation #Perspective (graphical) #Physics #Systems and Control (eess.SY) #Term (time) #Work (physics) #electronic engineering #information engineering

paper · pdf · doi:10.48550/arxiv.1905.07436

published in arXiv (Cornell University) (Cornell University)

openalex publication_date 2019/05/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

Abstract

We present a dynamical system framework for understanding Nesterov's accelerated gradient method. In contrast to earlier work, our derivation does not rely on a vanishing step size argument. We show that Nesterov acceleration arises from discretizing an ordinary differential equation with a semi-implicit Euler integration scheme. We analyze both the underlying differential equation as well as the discretization to obtain insights into the phenomenon of acceleration. The analysis suggests that a curvature-dependent damping term lies at the heart of the phenomenon. We further establish connections between the discretized and the continuous-time dynamics.

Cited by

• When Rates Are Geometric: Rate-Certificate Transfer for Contact Splittings in Optimization
• A Systems-Theoretic View on the Convergence of Algorithms under Disturbances
• Automated algorithm design via Nevanlinna-Pick interpolation
• Automated algorithm design for convex optimization problems with linear equality constraints
• The connections between Lyapunov functions for some optimization algorithms and differential equations
• A Hybrid Perspective on Suboptimal Mixed-Integer Quadratic Programming
• Revisiting the Role of Euler Numerical Integration on Acceleration and Stability in Convex Optimization
• Continuous-Time Analysis of Heavy Ball Momentum in Min-Max Games
• Learning by solving differential equations
• Arbitrarily Small Execution-Time Certificate: What was Missed in Analog Optimization
• The long time behavior and the rate of convergence of symplectic convex algorithms obtained via splitting discretizations of inertial damping systems
• Inducing strong convergence of trajectories in dynamical systems associated to monotone inclusions with composite structure

Related

• On the Dynamics of Acceleration in First order Gradient Methods
• A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights
• A class of generalized Nesterov's accelerated gradient method from dynamical perspective
• Gradient Norm Minimization of Nesterov Acceleration: o(1/k³)
• A Continuized View on Nesterov Acceleration