Faster Convergence of Stochastic Accelerated Gradient Descent under Interpolation
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_ | 1866915118703443968 |
|---|---|
| author | Mishkin, Aaron Pilanci, Mert Schmidt, Mark |
| author_facet | Mishkin, Aaron Pilanci, Mert Schmidt, Mark |
| contents | We prove new convergence rates for a generalized version of stochastic Nesterov acceleration under interpolation conditions. Unlike previous analyses, our approach accelerates any stochastic gradient method which makes sufficient progress in expectation. The proof, which proceeds using the estimating sequences framework, applies to both convex and strongly convex functions and is easily specialized to accelerated SGD under the strong growth condition. In this special case, our analysis reduces the dependence on the strong growth constant from $ρ$ to $\sqrtρ$ as compared to prior work. This improvement is comparable to a square-root of the condition number in the worst case and address criticism that guarantees for stochastic acceleration could be worse than those for SGD. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_02378 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Faster Convergence of Stochastic Accelerated Gradient Descent under Interpolation Mishkin, Aaron Pilanci, Mert Schmidt, Mark Optimization and Control Machine Learning We prove new convergence rates for a generalized version of stochastic Nesterov acceleration under interpolation conditions. Unlike previous analyses, our approach accelerates any stochastic gradient method which makes sufficient progress in expectation. The proof, which proceeds using the estimating sequences framework, applies to both convex and strongly convex functions and is easily specialized to accelerated SGD under the strong growth condition. In this special case, our analysis reduces the dependence on the strong growth constant from $ρ$ to $\sqrtρ$ as compared to prior work. This improvement is comparable to a square-root of the condition number in the worst case and address criticism that guarantees for stochastic acceleration could be worse than those for SGD. |
| title | Faster Convergence of Stochastic Accelerated Gradient Descent under Interpolation |
| topic | Optimization and Control Machine Learning |
| url | https://arxiv.org/abs/2404.02378 |