On the connections between optimization algorithms, Lyapunov functions, and differential equations: theory and insights
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911879938441216 |
|---|---|
| author | Dobson, Paul Sanz-Serna, Jesus Maria Zygalakis, Konstantinos |
| author_facet | Dobson, Paul Sanz-Serna, Jesus Maria Zygalakis, Konstantinos |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2305_08658 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | On the connections between optimization algorithms, Lyapunov functions, and differential equations: theory and insights Dobson, Paul Sanz-Serna, Jesus Maria Zygalakis, Konstantinos Optimization and Control Numerical Analysis Machine Learning 65L06, 65L20, 90C25, 93C15 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. |
| title | On the connections between optimization algorithms, Lyapunov functions, and differential equations: theory and insights |
| topic | Optimization and Control Numerical Analysis Machine Learning 65L06, 65L20, 90C25, 93C15 |
| url | https://arxiv.org/abs/2305.08658 |