Accelerated optimization algorithms and ordinary differential equations: the convex non Euclidean case
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866918411805655040 |
|---|---|
| author | Dobson, Paul Sanz-Serna, Jesus María Zygalakis, Konstantinos C. |
| author_facet | Dobson, Paul Sanz-Serna, Jesus María Zygalakis, Konstantinos C. |
| contents | We study the connections between ordinary differential equations and optimization algorithms in a non-Euclidean setting. We propose a novel accelerated algorithm for minimising convex functions over a convex constrained set. This algorithm is a natural generalization of Nesterov's accelerated gradient descent method to the non-Euclidean setting and can be interpreted as an additive Runge-Kutta algorithm. The algorithm can also be derived as a numerical discretization of the ODE appearing in Krichene et al. (2015a). We use Lyapunov functions to establish convergence rates for the ODE and show that the discretizations considered achieve acceleration beyond the setting studied in Krichene et al. (2015a). Finally, we discuss how the proposed algorithm connects to various equations and algorithms in the literature. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_19380 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Accelerated optimization algorithms and ordinary differential equations: the convex non Euclidean case Dobson, Paul Sanz-Serna, Jesus María Zygalakis, Konstantinos C. Optimization and Control 65L06, 65L20, 90C25 We study the connections between ordinary differential equations and optimization algorithms in a non-Euclidean setting. We propose a novel accelerated algorithm for minimising convex functions over a convex constrained set. This algorithm is a natural generalization of Nesterov's accelerated gradient descent method to the non-Euclidean setting and can be interpreted as an additive Runge-Kutta algorithm. The algorithm can also be derived as a numerical discretization of the ODE appearing in Krichene et al. (2015a). We use Lyapunov functions to establish convergence rates for the ODE and show that the discretizations considered achieve acceleration beyond the setting studied in Krichene et al. (2015a). Finally, we discuss how the proposed algorithm connects to various equations and algorithms in the literature. |
| title | Accelerated optimization algorithms and ordinary differential equations: the convex non Euclidean case |
| topic | Optimization and Control 65L06, 65L20, 90C25 |
| url | https://arxiv.org/abs/2410.19380 |