Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2020
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2008.12690 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912032044875776 |
|---|---|
| author | Li, Chris Junchi Mou, Wenlong Wainwright, Martin J. Jordan, Michael I. |
| author_facet | Li, Chris Junchi Mou, Wenlong Wainwright, Martin J. Jordan, Michael I. |
| contents | We study the problem of solving strongly convex and smooth unconstrained optimization problems using stochastic first-order algorithms. We devise a novel algorithm, referred to as Recursive One-Over-T SGD (ROOT-SGD), based on an easily implementable, recursive averaging of past stochastic gradients. We prove that it simultaneously achieves state-of-the-art performance in both a finite-sample, nonasymptotic sense and an asymptotic sense. On the non-asymptotic side, we prove risk bounds on the last iterate of ROOT-SGD with leading-order terms that match the optimal statistical risk with a unity pre-factor, along with a higher-order term that scales at the sharp rate of $O(n^{-3/2})$ under the Lipschitz condition on the Hessian matrix. On the asymptotic side, we show that when a mild, one-point Hessian continuity condition is imposed, the rescaled last iterate of (multi-epoch) ROOT-SGD converges asymptotically to a Gaussian limit with the Cramér-Rao optimal asymptotic covariance, for a broad range of step-size choices. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2008_12690 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm Li, Chris Junchi Mou, Wenlong Wainwright, Martin J. Jordan, Michael I. Optimization and Control Machine Learning We study the problem of solving strongly convex and smooth unconstrained optimization problems using stochastic first-order algorithms. We devise a novel algorithm, referred to as Recursive One-Over-T SGD (ROOT-SGD), based on an easily implementable, recursive averaging of past stochastic gradients. We prove that it simultaneously achieves state-of-the-art performance in both a finite-sample, nonasymptotic sense and an asymptotic sense. On the non-asymptotic side, we prove risk bounds on the last iterate of ROOT-SGD with leading-order terms that match the optimal statistical risk with a unity pre-factor, along with a higher-order term that scales at the sharp rate of $O(n^{-3/2})$ under the Lipschitz condition on the Hessian matrix. On the asymptotic side, we show that when a mild, one-point Hessian continuity condition is imposed, the rescaled last iterate of (multi-epoch) ROOT-SGD converges asymptotically to a Gaussian limit with the Cramér-Rao optimal asymptotic covariance, for a broad range of step-size choices. |
| title | ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm |
| topic | Optimization and Control Machine Learning |
| url | https://arxiv.org/abs/2008.12690 |