Understanding the Acceleration Phenomenon via High-Resolution Differential Equations

Abstract

Gradient-based optimization algorithms can be studied from the perspective of limiting ordinary differential equations (ODEs). Motivated by the fact that existing ODEs do not distinguish between two fundamentally different algorithms---Nesterov's accelerated gradient method for strongly convex functions (NAG-SC) and Polyak's heavy-ball method---we study an alternative limiting process that yields high-resolution ODEs. We show that these ODEs permit a general Lyapunov function framework for the analysis of convergence in both continuous and discrete time. We also show that these ODEs are more accurate surrogates for the underlying algorithms; in particular, they not only distinguish between NAG-SC and Polyak's heavy-ball method, but they allow the identification of a term that we refer to as "gradient correction" that is present in NAG-SC but not in the heavy-ball method and is responsible for the qualitative difference in convergence of the two methods. We also use the high-resolution ODE framework to study Nesterov's accelerated gradient method for (non-strongly) convex functions, uncovering a hitherto unknown result---that NAG-C minimizes the squared gradient norm at an inverse cubic rate. Finally, by modifying the high-resolution ODE of NAG-C, we obtain a family of new optimization methods that are shown to maintain the accelerated convergence rates of NAG-C for smooth convex functions.

82 pages, 11 figures

References in corpus (2)

• Global Convergence of Stochastic Gradient Hamiltonian Monte Carlo for Non-Convex Stochastic Optimization: Non-Asymptotic Performance Bounds and Momentum-Based Acceleration
• Dissipativity Theory for Nesterov's Accelerated Method

Cited by in corpus (41)

• From differential equation solvers to accelerated first-order methods for convex optimization
• High-Order Langevin Diffusion Yields an Accelerated MCMC Algorithm
• Global Convergence of Stochastic Gradient Hamiltonian Monte Carlo for Non-Convex Stochastic Optimization: Non-Asymptotic Performance Bounds and Momentum-Based Acceleration
• A Universally Optimal Multistage Accelerated Stochastic Gradient Method
• On Learning Rates and Schrödinger Operators
• Accelerated Proximal Point Method for Maximally Monotone Operators
• A Control-Theoretic Perspective on Optimal High-Order Optimization
• First order optimization methods based on Hessian-driven Nesterov accelerated gradient flow
• Potential Function-based Framework for Making the Gradients Small in Convex and Min-Max Optimization
• On the Hyperparameters in Stochastic Gradient Descent with Momentum
• Nesterov's method with decreasing learning rate leads to accelerated stochastic gradient descent
• Acceleration by Stepsize Hedging I: Multi-Step Descent and the Silver Stepsize Schedule
• A Unified Convergence Analysis of First Order Convex Optimization Methods via Strong Lyapunov Functions
• High-Resolution Modeling of the Fastest First-Order Optimization Method for Strongly Convex Functions
• An $O(s^r)$-Resolution ODE Framework for Understanding Discrete-Time Algorithms and Applications to the Linear Convergence of Minimax Problems
• A Direct Shooting Method is Equivalent to an Indirect Method
• A Dynamical View on Optimization Algorithms of Overparameterized Neural Networks
• Continuous vs. Discrete Optimization of Deep Neural Networks
• Acceleration in First Order Quasi-strongly Convex Optimization by ODE Discretization
• Limiting Behaviors of Nonconvex-Nonconcave Minimax Optimization via Continuous-Time Systems
• Hessian-Free High-Resolution Nesterov Acceleration for Sampling
• Stochasticity of Deterministic Gradient Descent: Large Learning Rate for Multiscale Objective Function
• A Continuous-time Perspective for Modeling Acceleration in Riemannian Optimization
• An Optimal Control Theory for Accelerated Optimization
• A piecewise conservative method for unconstrained convex optimization
• Variational Optimization on Lie Groups, with Examples of Leading (Generalized) Eigenvalue Problems
• A unified differential equation solver approach for separable convex optimization: splitting, acceleration and nonergodic rate
• Perturbed primal-dual dynamics with damping and time scaling coefficients for affine constrained convex optimization 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
• A Continuized View on Nesterov Acceleration for Stochastic Gradient Descent and Randomized Gossip
• A Geometric Structure of Acceleration and Its Role in Making Gradients Small Fast
• On The Convergence of Euler Discretization of Finite-Time Convergent Gradient Flows
• On the stability of optimization algorithms given by discretizations of the Euler-Lagrange ODE
• Understanding Modern Techniques in Optimization: Frank-Wolfe, Nesterov's Momentum, and Polyak's Momentum
• Revisiting the Role of Euler Numerical Integration on Acceleration and Stability in Convex Optimization
• Monotone Inclusions, Acceleration and Closed-Loop Control
• A Modular Analysis of Provable Acceleration via Polyak's Momentum: Training a Wide ReLU Network and a Deep Linear Network
• $\beta$-High Resolution ODE and Phase Transition between NAG-SC and Heavy Ball Method
• Resource-Aware Discretization of Accelerated Optimization Flows
• Robust Hybrid Zero-Order Optimization Algorithms with Acceleration via Averaging in Time