Accelerated Objective Gap and Gradient Norm Convergence for Gradient Descent via Long Steps
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910407694745600 |
|---|---|
| author | Grimmer, Benjamin Shu, Kevin Wang, Alex L. |
| author_facet | Grimmer, Benjamin Shu, Kevin Wang, Alex L. |
| contents | This work considers gradient descent for L-smooth convex optimization with stepsizes larger than the classic regime where descent can be ensured. The stepsize schedules considered are similar to but differ slightly from the recent silver stepsizes of Altschuler and Parrilo. For one of our stepsize sequences, we prove a $O\left(N^{- 1.2716\dots}\right)$ convergence rate in terms of objective gap decrease and for the other, we show the same rate of decrease for squared-gradient-norm decrease. This first result improves on the recent result of Altschuler and Parrilo by a constant factor, while the second results improve on the exponent of the prior best squared-gradient-norm convergence guarantee of $O\left(N^{-1}\right)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_14045 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Accelerated Objective Gap and Gradient Norm Convergence for Gradient Descent via Long Steps Grimmer, Benjamin Shu, Kevin Wang, Alex L. Optimization and Control This work considers gradient descent for L-smooth convex optimization with stepsizes larger than the classic regime where descent can be ensured. The stepsize schedules considered are similar to but differ slightly from the recent silver stepsizes of Altschuler and Parrilo. For one of our stepsize sequences, we prove a $O\left(N^{- 1.2716\dots}\right)$ convergence rate in terms of objective gap decrease and for the other, we show the same rate of decrease for squared-gradient-norm decrease. This first result improves on the recent result of Altschuler and Parrilo by a constant factor, while the second results improve on the exponent of the prior best squared-gradient-norm convergence guarantee of $O\left(N^{-1}\right)$. |
| title | Accelerated Objective Gap and Gradient Norm Convergence for Gradient Descent via Long Steps |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2403.14045 |