From differential equation solvers to accelerated first-order methods for convex optimization

Abstract

Convergence analysis of accelerated first-order methods for convex optimization problems are presented from the point of view of ordinary differential equation solvers. A new dynamical system, called Nesterov accelerated gradient flow, has been derived from the connection between acceleration mechanism and $A$-stability of ODE solvers, and the exponential decay of a tailored Lyapunov function along with the solution trajectory is proved. Numerical discretizations are then considered and convergence rates are established via a unified discrete Lyapunov function. The proposed differential equation solver approach can not only cover existing accelerated methods, such as FISTA, Güler's proximal algorithm and Nesterov's accelerated gradient method, but also produce new algorithms for composite convex optimization that possess accelerated convergence rates.

References in corpus (4)

• Understanding the Acceleration Phenomenon via High-Resolution Differential Equations
• Accelerated First-Order Methods: Differential Equations and Lyapunov Functions
• Fast inertial dynamics and FISTA algorithms in convex optimization. Perturbation aspects
• Acceleration in First Order Quasi-strongly Convex Optimization by ODE Discretization

Cited by in corpus (5)

• First order optimization methods based on Hessian-driven Nesterov accelerated gradient flow
• Convergence Rates of Inertial Primal-Dual Dynamical Methods for Separable Convex Optimization Problems
• A Unified Convergence Analysis of First Order Convex Optimization Methods via Strong Lyapunov Functions
• Accelerated differential inclusion for convex optimization
• A unified differential equation solver approach for separable convex optimization: splitting, acceleration and nonergodic rate