On Symplectic Optimization

Abstract

Accelerated gradient methods have had significant impact in machine learning -- in particular the theoretical side of machine learning -- due to their ability to achieve oracle lower bounds. But their heuristic construction has hindered their full integration into the practical machine-learning algorithmic toolbox, and has limited their scope. In this paper we build on recent work which casts acceleration as a phenomenon best explained in continuous time, and we augment that picture by providing a systematic methodology for converting continuous-time dynamics into discrete-time algorithms while retaining oracle rates. Our framework is based on ideas from Hamiltonian dynamical systems and symplectic integration. These ideas have had major impact in many areas in applied mathematics, but have not yet been seen to have a relationship with optimization.

arXiv comment20 pages, 5 figures

References in corpus (3)

• A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights
• A Variational Perspective on Accelerated Methods in Optimization
• Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent

Cited by in corpus (27)

• Understanding the Acceleration Phenomenon via High-Resolution Differential Equations
• Direct Runge-Kutta Discretization Achieves Acceleration
• Hamiltonian Descent Methods
• From Nesterov's Estimate Sequence to Riemannian Acceleration
• Accelerated Learning with Robustness to Adversarial Regressors
• A general system of differential equations to model first order adaptive algorithms
• A Control-Theoretic Perspective on Optimal High-Order Optimization
• Potential Function-based Framework for Making the Gradients Small in Convex and Min-Max Optimization
• Implicit Gradient Regularization
• Accelerated Gradient Methods with Memory
• Optimization on manifolds: A symplectic approach
• Accelerated Flow for Probability Distributions
• A Continuous-time Perspective for Modeling Acceleration in Riemannian Optimization
• Acceleration in First Order Quasi-strongly Convex Optimization by ODE Discretization
• Locally Accelerated Conditional Gradients
• Adaptive Hamiltonian Variational Integrators and Symplectic Accelerated Optimization
• A Statistician Teaches Deep Learning
• A Continuized View on Nesterov Acceleration for Stochastic Gradient Descent and Randomized Gossip
• On Constraints in First-Order Optimization: A View from Non-Smooth Dynamical Systems
• The connections between Lyapunov functions for some optimization algorithms and differential equations
• Hamiltonian descent for composite objectives
• Provably Correct Learning Algorithms in the Presence of Time-Varying Features Using a Variational Perspective
• Continuous-time Models for Stochastic Optimization Algorithms
• A Discrete Variational Derivation of Accelerated Methods in Optimization
• Revisiting the Effects of Stochasticity for Hamiltonian Samplers
• A Continuized View on Nesterov Acceleration
• Revisiting the Role of Euler Numerical Integration on Acceleration and Stability in Convex Optimization