A Lyapunov Analysis of Momentum Methods in Optimization

Abstract

Momentum methods play a significant role in optimization. Examples include Nesterov's accelerated gradient method and the conditional gradient algorithm. Several momentum methods are provably optimal under standard oracle models, and all use a technique called estimate sequences to analyze their convergence properties. The technique of estimate sequences has long been considered difficult to understand, leading many researchers to generate alternative, "more intuitive" methods and analyses. We show there is an equivalence between the technique of estimate sequences and a family of Lyapunov functions in both continuous and discrete time. This connection allows us to develop a simple and unified analysis of many existing momentum algorithms, introduce several new algorithms, and strengthen the connection between algorithms and continuous-time dynamical systems.

Major revision. Cleaned up presentation and added results

Cited by in corpus (68)

• A Review on Deep Learning in Medical Image Reconstruction
• Beyond Finite Layer Neural Networks: Bridging Deep Architectures and Numerical Differential Equations
• The Approximate Duality Gap Technique: A Unified Theory of First-Order Methods
• From differential equation solvers to accelerated first-order methods for convex optimization
• High-Order Langevin Diffusion Yields an Accelerated MCMC Algorithm
• Implicit Regularization and Momentum Algorithms in Nonlinearly Parameterized Adaptive Control and Prediction
• Is There an Analog of Nesterov Acceleration for MCMC?
• Hamiltonian Descent Methods
• Global Convergence of Stochastic Gradient Hamiltonian Monte Carlo for Non-Convex Stochastic Optimization: Non-Asymptotic Performance Bounds and Momentum-Based Acceleration
• A Nonsmooth Dynamical Systems Perspective on Accelerated Extensions of ADMM
• An Accelerated Correlation Filter Tracker
• Accelerated Linear Convergence of Stochastic Momentum Methods in Wasserstein Distances
• Heavy Ball Neural Ordinary Differential Equations
• From Nesterov's Estimate Sequence to Riemannian Acceleration
• Accelerated First-Order Methods: Differential Equations and Lyapunov Functions
• Effective Federated Adaptive Gradient Methods with Non-IID Decentralized Data
• Integration Methods and Accelerated Optimization Algorithms
• Accelerated Learning with Robustness to Adversarial Regressors
• On the Generalization of Stochastic Gradient Descent with Momentum
• Breaking Locality Accelerates Block Gauss-Seidel
• First order optimization methods based on Hessian-driven Nesterov accelerated gradient flow
• A Control-Theoretic Perspective on Optimal High-Order Optimization
• Robust and structure exploiting optimization algorithms: An integral quadratic constraint approach
• Aggregated Momentum: Stability Through Passive Damping
• Potential Function-based Framework for Making the Gradients Small in Convex and Min-Max Optimization
• Deep Lyapunov Function: Automatic Stability Analysis for Dynamical Systems
• Acceleration by Stepsize Hedging I: Multi-Step Descent and the Silver Stepsize Schedule
• Nesterov's method with decreasing learning rate leads to accelerated stochastic gradient descent
• Robust and efficient algorithms for high-dimensional black-box quantum optimization
• Gradient descent with momentum --- to accelerate or to super-accelerate?
• High-Resolution Modeling of the Fastest First-Order Optimization Method for Strongly Convex Functions
• A High-order Tuner for Accelerated Learning and Control
• A Dynamical View on Optimization Algorithms of Overparameterized Neural Networks
• Accelerated Gradient Methods with Memory
• Continuous vs. Discrete Optimization of Deep Neural Networks
• Convex Synthesis of Accelerated Gradient Algorithms for Optimization and Saddle Point Problems using Lyapunov functions
• Accelerated differential inclusion for convex optimization
• Finite-time and Fixed-time Convergence in Continuous-time Optimization
• Dataset Dynamics via Gradient Flows in Probability Space
• Hessian-Free High-Resolution Nesterov Acceleration for Sampling
• Incrementally Stochastic and Accelerated Gradient Information mixed Optimization for Manipulator Motion Planning
• A Continuous-time Perspective for Modeling Acceleration in Riemannian Optimization
• Momentum Accelerates Evolutionary Dynamics
• Perturbed primal-dual dynamics with damping and time scaling coefficients for affine constrained convex optimization problems
• Reverse engineering learned optimizers reveals known and novel mechanisms
• A Conservation Law Method in Optimization
• The Search direction Correction makes first-order methods faster
• A Contraction Theory Approach to Optimization Algorithms from Acceleration Flows
• Hamiltonian descent for composite objectives
• 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
• Provably Correct Learning Algorithms in the Presence of Time-Varying Features Using a Variational Perspective
• Analytical Convergence Regions of Accelerated Gradient Descent in Nonconvex Optimization under Regularity Condition
• Decentralized Learning with Lazy and Approximate Dual Gradients
• A Continuized View on Nesterov Acceleration for Stochastic Gradient Descent and Randomized Gossip
• Penalized Langevin dynamics with vanishing penalty for smooth and log-concave targets
• Noether's Learning Dynamics: Role of Symmetry Breaking in Neural Networks
• Accelerate Distributed Stochastic Descent for Nonconvex Optimization with Momentum
• Understanding Modern Techniques in Optimization: Frank-Wolfe, Nesterov's Momentum, and Polyak's Momentum
• Momentum-inspired Low-Rank Coordinate Descent for Diagonally Constrained SDPs
• A Modular Analysis of Provable Acceleration via Polyak's Momentum: Training a Wide ReLU Network and a Deep Linear Network
• Boosting First-Order Methods by Shifting Objective: New Schemes with Faster Worst-Case Rates
• Revisiting the Role of Euler Numerical Integration on Acceleration and Stability in Convex Optimization
• $\beta$-High Resolution ODE and Phase Transition between NAG-SC and Heavy Ball Method
• Meta Learning in the Continuous Time Limit
• Resource-Aware Discretization of Accelerated Optimization Flows
• On the Curved Geometry of Accelerated Optimization
• Continuous-time Models for Stochastic Optimization Algorithms