A Variational Perspective on Accelerated Methods in Optimization

Abstract

Accelerated gradient methods play a central role in optimization, achieving optimal rates in many settings. While many generalizations and extensions of Nesterov's original acceleration method have been proposed, it is not yet clear what is the natural scope of the acceleration concept. In this paper, we study accelerated methods from a continuous-time perspective. We show that there is a Lagrangian functional that we call the \emph{Bregman Lagrangian} which generates a large class of accelerated methods in continuous time, including (but not limited to) accelerated gradient descent, its non-Euclidean extension, and accelerated higher-order gradient methods. We show that the continuous-time limit of all of these methods correspond to traveling the same curve in spacetime at different speeds. From this perspective, Nesterov's technique and many of its generalizations can be viewed as a systematic way to go from the continuous-time curves generated by the Bregman Lagrangian to a family of discrete-time accelerated algorithms.

38 pages. Subsumes an earlier working draft arXiv:1509.03616

References in corpus (6)

• A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights
• A geometric alternative to Nesterov's accelerated gradient descent
• Hessian Riemannian gradient flows in convex programming
• From Averaging to Acceleration, There is Only a Step-size
• On Lower and Upper Bounds for Smooth and Strongly Convex Optimization Problems
• Fast inertial dynamics and FISTA algorithms in convex optimization. Perturbation aspects

Cited by in corpus (104)

• A distributed primal-dual algorithm for computation of generalized Nash equilibria with shared affine coupling constraints via operator splitting methods
• User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient
• On the Optimization of Deep Networks: Implicit Acceleration by Overparameterization
• Fixed-Time Stable Gradient Flows: Applications to Continuous-Time Optimization
• Dissecting Neural ODEs
• The Approximate Duality Gap Technique: A Unified Theory of First-Order Methods
• From differential equation solvers to accelerated first-order methods for convex optimization
• Direct Runge-Kutta Discretization Achieves Acceleration
• A Dynamical Systems Perspective on Nesterov Acceleration
• Acceleration Methods
• ADMM and Accelerated ADMM as Continuous Dynamical Systems
• Beyond Convexity -- Contraction and Global Convergence of Gradient Descent
• Implicit Regularization and Momentum Algorithms in Nonlinearly Parameterized Adaptive Control and Prediction
• Hamiltonian Descent Methods
• Inducing strong convergence of trajectories in dynamical systems associated to monotone inclusions with composite structure
• On Symplectic Optimization
• Global Convergence of Stochastic Gradient Hamiltonian Monte Carlo for Non-Convex Stochastic Optimization: Non-Asymptotic Performance Bounds and Momentum-Based Acceleration
• Connections Between Adaptive Control and Optimization in Machine Learning
• A Nonsmooth Dynamical Systems Perspective on Accelerated Extensions of ADMM
• CAPPA: Continuous-time Accelerated Proximal Point Algorithm for Sparse Recovery
• An Accelerated Correlation Filter Tracker
• On the diffusion approximation of nonconvex stochastic gradient descent
• Sampling as optimization in the space of measures: The Langevin dynamics as a composite optimization problem
• On dissipative symplectic integration with applications to gradient-based optimization
• Conformal Symplectic and Relativistic Optimization
• Gradient flows and proximal splitting methods: A unified view on accelerated and stochastic optimization
• Accelerated First-Order Methods: Differential Equations and Lyapunov Functions
• Potential-Function Proofs for First-Order Methods
• The Role of Memory in Stochastic Optimization
• Optimal Deterministic Algorithm Generation
• On Quantum Speedups for Nonconvex Optimization via Quantum Tunneling Walks
• Accelerated Learning with Robustness to Adversarial Regressors
• To Infinity and Beyond: Some ODE and PDE Case Studies
• Distributed Stochastic Gradient Descent: Nonconvexity, Nonsmoothness, and Convergence to Local Minima
• A general system of differential equations to model first order adaptive algorithms
• The Physical Systems Behind Optimization Algorithms
• Lagrangian and Hamiltonian Mechanics for Probabilities on the Statistical Manifold
• A Control-Theoretic Perspective on Optimal High-Order Optimization
• Momentum Improves Optimization on Riemannian Manifolds
• Practical Perspectives on Symplectic Accelerated Optimization
• Asymptotic Analysis via Stochastic Differential Equations of Gradient Descent Algorithms in Statistical and Computational Paradigms
• Geometric Methods for Sampling, Optimisation, Inference and Adaptive Agents
• A continuous-time analysis of distributed stochastic gradient
• Aggregated Momentum: Stability Through Passive Damping
• Time-adaptive Lagrangian Variational Integrators for Accelerated Optimization on Manifolds
• Selection dynamics for deep neural networks
• Hessian barrier algorithms for linearly constrained optimization problems
• Nesterov's method with decreasing learning rate leads to accelerated stochastic gradient descent
• Accelerated Optimization on Riemannian Manifolds via Discrete Constrained Variational Integrators
• Acceleration by Stepsize Hedging I: Multi-Step Descent and the Silver Stepsize Schedule
• Bregman Itoh--Abe methods for sparse optimisation
• Continuous Relaxations for the Traveling Salesman Problem
• No-Regret Dynamics in the Fenchel Game: A Unified Framework for Algorithmic Convex Optimization
• Accelerating proximal Markov chain Monte Carlo by using an explicit stabilised method
• Accelerated PDE's for efficient solution of regularized inversion problems
• Optimization with Momentum: Dynamical, Control-Theoretic, and Symplectic Perspectives
• Continuous-time Lower Bounds for Gradient-based Algorithms
• Accelerated first-order primal-dual proximal methods for linearly constrained composite convex programming
• Exploring Critical Points of Energy Landscapes: From Low-Dimensional Examples to Phase Field Crystal PDEs
• Continuous vs. Discrete Optimization of Deep Neural Networks
• On Computational Poisson Geometry II: Numerical Methods
• Accelerated Gradient Methods with Memory
• Global Riemannian Acceleration in Hyperbolic and Spherical Spaces
• Accelerated differential inclusion for convex optimization
• A Continuous-time Perspective for Modeling Acceleration in Riemannian Optimization
• Stochasticity of Deterministic Gradient Descent: Large Learning Rate for Multiscale Objective Function
• Escaping spurious local minimum trajectories in online time-varying nonconvex optimization
• Hessian-Free High-Resolution Nesterov Acceleration for Sampling
• Control Interpretations for First-Order Optimization Methods
• Optimization on manifolds: A symplectic approach
• Conjugate Gradients and Accelerated Methods Unified: The Approximate Duality Gap View
• Distributed Gradient Methods for Nonconvex Optimization: Local and Global Convergence Guarantees
• Mass-spring-damper Networks for Distributed Optimization in Non-Euclidean Spaces
• A Contraction Theory Approach to Optimization Algorithms from Acceleration Flows
• Differential Equations for Modeling Asynchronous Algorithms
• A geometric integration approach to smooth optimisation: Foundations of the discrete gradient method
• A unified differential equation solver approach for separable convex optimization: splitting, acceleration and nonergodic rate
• A Conservation Law Method in Optimization
• Adaptive Hamiltonian Variational Integrators and Symplectic Accelerated Optimization
• The connections between Lyapunov functions for some optimization algorithms and differential equations
• On The Convergence of Euler Discretization of Finite-Time Convergent Gradient Flows
• Hamiltonian descent for composite objectives
• A Dynamical Systems Approach for Convergence of the Bayesian EM Algorithm
• On Constraints in First-Order Optimization: A View from Non-Smooth Dynamical Systems
• A closed loop gradient descent algorithm applied to Rosenbrock's function
• Inducing Uniform Asymptotic Stability in Non-Autonomous Accelerated Optimization Dynamics via Hybrid Regularization
• Noether's Learning Dynamics: Role of Symmetry Breaking in Neural Networks
• Provably Correct Learning Algorithms in the Presence of Time-Varying Features Using a Variational Perspective
• Stochastic mirror descent dynamics and their convergence in monotone variational inequalities
• Achieving Acceleration in Distributed Optimization via Direct Discretization of the Heavy-Ball ODE
• On the Curved Geometry of Accelerated Optimization
• On the stability of optimization algorithms given by discretizations of the Euler-Lagrange ODE
• A New Class of Composite Objective Multi-step Estimating-sequence Techniques (COMET)
• Convergence and Stability of the Stochastic Proximal Point Algorithm with Momentum
• Robust Hybrid Zero-Order Optimization Algorithms with Acceleration via Averaging in Time
• Online Algorithms and Policies Using Adaptive and Machine Learning Approaches
• FLAG n' FLARE: Fast Linearly-Coupled Adaptive Gradient Methods
• The Confluence of Networks, Games and Learning
• A Discrete Variational Derivation of Accelerated Methods in Optimization
• Non-ergodic Complexity of Convex Proximal Inertial Gradient Descents
• Contractivity of Runge-Kutta methods for convex gradient systems
• Accelerated Information Gradient flow
• Monotone Inclusions, Acceleration and Closed-Loop Control
• On Adapting Nesterov's Scheme to Accelerate Iterative Methods for Linear Problems