A Dynamical Systems Perspective on Nesterov Acceleration

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.

11 pages, 4 figures, to appear in the Proceedings of the 36th International Conference on Machine Learning

Cited by in corpus (17)

• Lyapunov functions for nabla discrete fractional order systems
• Design of generalized fractional order gradient descent method
• Implicit Regularization and Momentum Algorithms in Nonlinearly Parameterized Adaptive Control and Prediction
• Inducing strong convergence of trajectories in dynamical systems associated to monotone inclusions with composite structure
• A Control-Theoretic Perspective on Optimal High-Order Optimization
• Optimization with Momentum: Dynamical, Control-Theoretic, and Symplectic Perspectives
• Continuous-time Lower Bounds for Gradient-based Algorithms
• The long time behavior and the rate of convergence of symplectic convex algorithms obtained via splitting discretizations of inertial damping systems
• A Contraction Theory Approach to Optimization Algorithms from Acceleration Flows
• A unified differential equation solver approach for separable convex optimization: splitting, acceleration and nonergodic rate
• 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 Convergence of Euler Discretization of Finite-Time Convergent Gradient Flows
• The connections between Lyapunov functions for some optimization algorithms and differential equations
• Monotone Inclusions, Acceleration and Closed-Loop Control
• Revisiting the Role of Euler Numerical Integration on Acceleration and Stability in Convex Optimization
• Meta Learning in the Continuous Time Limit