Acceleration by Stepsize Hedging II: Silver Stepsize Schedule for Smooth Convex Optimization
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929602731966464 |
|---|---|
| author | Altschuler, Jason M. Parrilo, Pablo A. |
| author_facet | Altschuler, Jason M. Parrilo, Pablo A. |
| contents | We provide a concise, self-contained proof that the Silver Stepsize Schedule proposed in Part I directly applies to smooth (non-strongly) convex optimization. Specifically, we show that with these stepsizes, gradient descent computes an $ε$-minimizer in $O(ε^{-\log_ρ 2}) = O(ε^{-0.7864})$ iterations, where $ρ= 1+\sqrt{2}$ is the silver ratio. This is intermediate between the textbook unaccelerated rate $O(ε^{-1})$ and the accelerated rate $O(ε^{-1/2})$ due to Nesterov in 1983. The Silver Stepsize Schedule is a simple explicit fractal: the $i$-th stepsize is $1+ρ^{v(i)-1}$ where $v(i)$ is the $2$-adic valuation of $i$. The design and analysis are conceptually identical to the strongly convex setting in Part I, but simplify remarkably in this specific setting. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2309_16530 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Acceleration by Stepsize Hedging II: Silver Stepsize Schedule for Smooth Convex Optimization Altschuler, Jason M. Parrilo, Pablo A. Optimization and Control We provide a concise, self-contained proof that the Silver Stepsize Schedule proposed in Part I directly applies to smooth (non-strongly) convex optimization. Specifically, we show that with these stepsizes, gradient descent computes an $ε$-minimizer in $O(ε^{-\log_ρ 2}) = O(ε^{-0.7864})$ iterations, where $ρ= 1+\sqrt{2}$ is the silver ratio. This is intermediate between the textbook unaccelerated rate $O(ε^{-1})$ and the accelerated rate $O(ε^{-1/2})$ due to Nesterov in 1983. The Silver Stepsize Schedule is a simple explicit fractal: the $i$-th stepsize is $1+ρ^{v(i)-1}$ where $v(i)$ is the $2$-adic valuation of $i$. The design and analysis are conceptually identical to the strongly convex setting in Part I, but simplify remarkably in this specific setting. |
| title | Acceleration by Stepsize Hedging II: Silver Stepsize Schedule for Smooth Convex Optimization |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2309.16530 |