Revisiting the Role of Euler Numerical Integration on Acceleration and Stability in Convex Optimization
arXiv:2102.11537
Abstract
Viewing optimization methods as numerical integrators for ordinary differential equations (ODEs) provides a thought-provoking modern framework for studying accelerated first-order optimizers. In this literature, acceleration is often supposed to be linked to the quality of the integrator (accuracy, energy preservation, symplecticity). In this work, we propose a novel ordinary differential equation that questions this connection: both the explicit and the semi-implicit (a.k.a symplectic) Euler discretizations on this ODE lead to an accelerated algorithm for convex programming. Although semi-implicit methods are well-known in numerical analysis to enjoy many desirable features for the integration of physical systems, our findings show that these properties do not necessarily relate to acceleration.
arXiv comment18 pages, 5 figures; Proceedings of the 24th International Conference on Artificial Intelligence and Statistics (AISTATS) 2021, San Diego, California, USA. PMLR: Volume 130
References in corpus (12)
- A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights
- On Empirical Comparisons of Optimizers for Deep Learning
- Contact Hamiltonian Mechanics
- A Lyapunov Analysis of Momentum Methods in Optimization
- Understanding the Acceleration Phenomenon via High-Resolution Differential Equations
- On damped second-order gradient systems
- A Dynamical Systems Perspective on Nesterov Acceleration
- Understanding the Role of Momentum in Stochastic Gradient Methods
- On Symplectic Optimization
- The Role of Memory in Stochastic Optimization
- Shadowing Properties of Optimization Algorithms
- The long time behavior and the rate of convergence of symplectic convex algorithms obtained via splitting discretizations of inertial damping systems