On the connections between optimization algorithms, Lyapunov functions, and differential equations: theory and insights
Not on the map. Why?
Abstract (arXiv)
We revisit the general framework introduced by Fazylab et al. (SIAM J. Optim. 28, 2018) to construct Lyapunov functions for optimization algorithms in discrete and continuous time. For smooth, strongly convex objective functions, we relax the requirements necessary for such a construction. As a result we are able to prove for Polyak's ordinary differential equations and for a two-parameter family of Nesterov algorithms rates of convergence that improve on those available in the literature. We analyse the interpretation of Nesterov algorithms as discretizations of the Polyak equation. We show that the algorithms are instances of Additive Runge-Kutta integrators and discuss the reasons why most discretizations of the differential equation do not result in optimization algorithms with acceleration. We also introduce a modification of Polyak's equation and study its convergence properties. Finally we extend the general framework to the stochastic scenario and consider an application to random algorithms with acceleration for overparameterized models; again we are able to prove convergence rates that improve on those in the literature.
Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 14 of its 34 references that are in the map. First posted on arXiv 15 May 2023.
Builds on
14 of 34 references.
References · 14
- 2015A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insightscited by 203
- 2017The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learningcited by 150
- 2018Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptroncited by 143
- 2016A Variational Perspective on Accelerated Methods in Optimizationcited by 108
- 2014Analysis and Design of Optimization Algorithms via Integral Quadratic Constraintscited by 105
- 2019A Dynamical Systems Perspective on Nesterov Accelerationcited by 33
- 2019Acceleration via Symplectic Discretization of High-Resolution Differential Equationscited by 27
- 2020Optimization with Momentum: Dynamical, Control-Theoretic, and Symplectic Perspectivescited by 27
- 2020On dissipative symplectic integration with applications to gradient-based optimizationcited by 23
- 2017Analysis of Optimization Algorithms via Integral Quadratic Constraints: Nonstrongly Convex Problemscited by 19
- 2019Nesterov's method with decreasing learning rate leads to accelerated stochastic gradient descentcited by 13
- 2020The connections between Lyapunov functions for some optimization algorithms and differential equationscited by 11
Built on by
Citing papers per year: 2025: 1; 2026: 1.
2 papers.