A Strengthened Conjecture on the Minimax Optimal Constant Stepsize for Gradient Descent
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_ | 1866910529512013824 |
|---|---|
| author | Grimmer, Benjamin Shu, Kevin Wang, Alex L. |
| author_facet | Grimmer, Benjamin Shu, Kevin Wang, Alex L. |
| contents | Drori and Teboulle [4] conjectured that the minimax optimal constant stepsize for N steps of gradient descent is given by the stepsize that balances performance on Huber and quadratic objective functions. This was numerically supported by semidefinite program (SDP) solves of the associated performance estimation problems up to $N\approx 100$. This note presents a strengthened version of the initial conjecture. Specifically, we conjecture the existence of a certificate for the convergence rate with a very specific low-rank structure. This structure allows us to bypass SDPs and to numerically verify both conjectures up to $N = 20160$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_11739 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Strengthened Conjecture on the Minimax Optimal Constant Stepsize for Gradient Descent Grimmer, Benjamin Shu, Kevin Wang, Alex L. Optimization and Control Drori and Teboulle [4] conjectured that the minimax optimal constant stepsize for N steps of gradient descent is given by the stepsize that balances performance on Huber and quadratic objective functions. This was numerically supported by semidefinite program (SDP) solves of the associated performance estimation problems up to $N\approx 100$. This note presents a strengthened version of the initial conjecture. Specifically, we conjecture the existence of a certificate for the convergence rate with a very specific low-rank structure. This structure allows us to bypass SDPs and to numerically verify both conjectures up to $N = 20160$. |
| title | A Strengthened Conjecture on the Minimax Optimal Constant Stepsize for Gradient Descent |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2407.11739 |