Acceleration by Random Stepsizes: Hedging, Equalization, and the Arcsine Stepsize Schedule
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_ | 1866916067003072512 |
|---|---|
| author | Altschuler, Jason M. Parrilo, Pablo A. |
| author_facet | Altschuler, Jason M. Parrilo, Pablo A. |
| contents | We show that for separable convex optimization, random stepsizes fully accelerate Gradient Descent. Specifically, using inverse stepsizes i.i.d. from the Arcsine distribution improves the convergence rate from $O(k)$ to $O(\sqrt{k})$, where $k$ is the condition number. No momentum or other algorithmic modifications are required. Our starting point is a remarkable "equalization property" of the Arcsine distribution: it yields an identical convergence rate for all quadratic functions. A key technical insight is that martingale arguments extend this phenomenon to all separable convex functions. We interpret this equalization as an extreme form of hedging: by using this random distribution over stepsizes, Gradient Descent converges at exactly the same rate for all functions in the function class. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_05790 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Acceleration by Random Stepsizes: Hedging, Equalization, and the Arcsine Stepsize Schedule Altschuler, Jason M. Parrilo, Pablo A. Optimization and Control Data Structures and Algorithms We show that for separable convex optimization, random stepsizes fully accelerate Gradient Descent. Specifically, using inverse stepsizes i.i.d. from the Arcsine distribution improves the convergence rate from $O(k)$ to $O(\sqrt{k})$, where $k$ is the condition number. No momentum or other algorithmic modifications are required. Our starting point is a remarkable "equalization property" of the Arcsine distribution: it yields an identical convergence rate for all quadratic functions. A key technical insight is that martingale arguments extend this phenomenon to all separable convex functions. We interpret this equalization as an extreme form of hedging: by using this random distribution over stepsizes, Gradient Descent converges at exactly the same rate for all functions in the function class. |
| title | Acceleration by Random Stepsizes: Hedging, Equalization, and the Arcsine Stepsize Schedule |
| topic | Optimization and Control Data Structures and Algorithms |
| url | https://arxiv.org/abs/2412.05790 |