Accelerated First-Order Methods: Differential Equations and Lyapunov Functions

Abstract

We develop a theory of accelerated first-order optimization from the viewpoint of differential equations and Lyapunov functions. Building upon the previous work of many researchers, we consider differential equations which model the behavior of accelerated gradient descent. Our main contributions are to provide a general framework for discretizating the differential equations to produce accelerated methods, and to provide physical intuition which helps explain the optimal damping rate. An important novelty is the generality of our approach, which leads to a unified derivation of a wide variety of methods, including versions of Nesterov's accelerated gradient descent, FISTA, and accelerated coordinate descent.

arXiv comment18 pages, 0 figures

References in corpus (6)

• A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights
• A Variational Perspective on Accelerated Methods in Optimization
• Acceleration Schemes for Ab-Initio Molecular Dynamics and Electronic Structure Calculations
• A Lyapunov Analysis of Momentum Methods in Optimization
• A geometric alternative to Nesterov's accelerated gradient descent
• Accelerating Greedy Coordinate Descent Methods

Cited by in corpus (5)

• From differential equation solvers to accelerated first-order methods for convex optimization
• First order optimization methods based on Hessian-driven Nesterov accelerated gradient flow
• A Unified Convergence Analysis of First Order Convex Optimization Methods via Strong Lyapunov Functions
• A Dynamical View on Optimization Algorithms of Overparameterized Neural Networks
• Accelerated differential inclusion for convex optimization