Optimization with Momentum: Dynamical, Control-Theoretic, and Symplectic Perspectives

Abstract

We analyze the convergence rate of various momentum-based optimization algorithms from a dynamical systems point of view. Our analysis exploits fundamental topological properties, such as the continuous dependence of iterates on their initial conditions, to provide a simple characterization of convergence rates. In many cases, closed-form expressions are obtained that relate algorithm parameters to the convergence rate. The analysis encompasses discrete time and continuous time, as well as time-invariant and time-variant formulations, and is not limited to a convex or Euclidean setting. In addition, the article rigorously establishes why symplectic discretization schemes are important for momentum-based optimization algorithms, and provides a characterization of algorithms that exhibit accelerated convergence.

arXiv comment30 pages; 20 pages appendix and references

References in corpus (10)

• A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights
• A Variational Perspective on Accelerated Methods in Optimization
• A geometric alternative to Nesterov's accelerated gradient descent
• The Approximate Duality Gap Technique: A Unified Theory of First-Order Methods
• On Nonconvex Optimization for Machine Learning: Gradients, Stochasticity, and Saddle Points
• Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent
• A Dynamical Systems Perspective on Nesterov Acceleration
• Hamiltonian Descent Methods
• Near-optimal method for highly smooth convex optimization
• Robust and structure exploiting optimization algorithms: An integral quadratic constraint approach