Optimal Convergence Rates for Nesterov Acceleration
| hal.structure.identifier | Institut de Mathématiques de Bordeaux [IMB] | |
| dc.contributor.author | AUJOL, Jean François | |
| hal.structure.identifier | Institut de Mathématiques de Toulouse UMR5219 [IMT] | |
| dc.contributor.author | DOSSAL, Charles | |
| hal.structure.identifier | Institut de Mathématiques de Toulouse UMR5219 [IMT] | |
| hal.structure.identifier | Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes [LAAS-ROC] | |
| dc.contributor.author | RONDEPIERRE, Aude | |
| dc.date.accessioned | 2024-04-04T03:00:35Z | |
| dc.date.available | 2024-04-04T03:00:35Z | |
| dc.date.issued | 2019-12 | |
| dc.identifier.issn | 1052-6234 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/192830 | |
| dc.description.abstractEn | In this paper, we study the behavior of solutions of the ODE associated to Nesterov acceleration. It is well-known since the pioneering work of Nesterov that the rate of convergence $O(1/t^2)$ is optimal for the class of convex functions with Lipschitz gradient. In this work, we show that better convergence rates can be obtained with some additional geometrical conditions, such as \L ojasiewicz property. More precisely, we prove the optimal convergence rates that can be obtained depending on the geometry of the function $F$ to minimize. The convergence rates are new, and they shed new light on the behavior of Nesterov acceleration schemes. We prove in particular that the classical Nesterov scheme may provide convergence rates that are worse than the classical gradient descent scheme on sharp functions: for instance, the convergence rate for strongly convex functions is not geometric for the classical Nesterov scheme (while it is the case for the gradient descent algorithm). This shows that applying the classical Nesterov acceleration on convex functions without looking more at the geometrical properties of the objective functions may lead to sub-optimal algorithms. | |
| dc.description.sponsorship | Centre International de Mathématiques et d'Informatique (de Toulouse) - ANR-11-LABX-0040 | |
| dc.description.sponsorship | Université Fédérale de Toulouse - ANR-11-IDEX-0002 | |
| dc.language.iso | en | |
| dc.publisher | Society for Industrial and Applied Mathematics | |
| dc.subject.en | Lyapunov functions | |
| dc.subject.en | rate of convergence | |
| dc.subject.en | Lojasiewicz property | |
| dc.subject.en | ODEs | |
| dc.subject.en | optimization | |
| dc.title.en | Optimal Convergence Rates for Nesterov Acceleration | |
| dc.type | Article de revue | |
| dc.identifier.doi | 10.1137/18M1186757 | |
| dc.subject.hal | Mathématiques [math]/Optimisation et contrôle [math.OC] | |
| dc.identifier.arxiv | 1805.05719 | |
| bordeaux.journal | SIAM Journal on Optimization | |
| bordeaux.page | 3131–3153 | |
| bordeaux.volume | 29 | |
| bordeaux.hal.laboratories | Institut de Mathématiques de Bordeaux (IMB) - UMR 5251 | * |
| bordeaux.issue | 4 | |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| bordeaux.peerReviewed | oui | |
| hal.identifier | hal-01786117 | |
| hal.version | 1 | |
| hal.popular | non | |
| hal.audience | Internationale | |
| hal.origin.link | https://hal.archives-ouvertes.fr//hal-01786117v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=SIAM%20Journal%20on%20Optimization&rft.date=2019-12&rft.volume=29&rft.issue=4&rft.spage=3131%E2%80%933153&rft.epage=3131%E2%80%933153&rft.eissn=1052-6234&rft.issn=1052-6234&rft.au=AUJOL,%20Jean%20Fran%C3%A7ois&DOSSAL,%20Charles&RONDEPIERRE,%20Aude&rft.genre=article |
Fichier(s) constituant ce document
| Fichiers | Taille | Format | Vue |
|---|---|---|---|
|
Il n'y a pas de fichiers associés à ce document. |
|||