Efficient Convex Optimization Requires Superlinear Memory
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2022
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909265735712768 |
|---|---|
| author | Marsden, Annie Sharan, Vatsal Sidford, Aaron Valiant, Gregory |
| author_facet | Marsden, Annie Sharan, Vatsal Sidford, Aaron Valiant, Gregory |
| contents | We show that any memory-constrained, first-order algorithm which minimizes $d$-dimensional, $1$-Lipschitz convex functions over the unit ball to $1/\mathrm{poly}(d)$ accuracy using at most $d^{1.25 - δ}$ bits of memory must make at least $\tildeΩ(d^{1 + (4/3)δ})$ first-order queries (for any constant $δ\in [0, 1/4]$). Consequently, the performance of such memory-constrained algorithms are a polynomial factor worse than the optimal $\tilde{O}(d)$ query bound for this problem obtained by cutting plane methods that use $\tilde{O}(d^2)$ memory. This resolves a COLT 2019 open problem of Woodworth and Srebro. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2203_15260 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Efficient Convex Optimization Requires Superlinear Memory Marsden, Annie Sharan, Vatsal Sidford, Aaron Valiant, Gregory Machine Learning Computational Complexity Data Structures and Algorithms Optimization and Control We show that any memory-constrained, first-order algorithm which minimizes $d$-dimensional, $1$-Lipschitz convex functions over the unit ball to $1/\mathrm{poly}(d)$ accuracy using at most $d^{1.25 - δ}$ bits of memory must make at least $\tildeΩ(d^{1 + (4/3)δ})$ first-order queries (for any constant $δ\in [0, 1/4]$). Consequently, the performance of such memory-constrained algorithms are a polynomial factor worse than the optimal $\tilde{O}(d)$ query bound for this problem obtained by cutting plane methods that use $\tilde{O}(d^2)$ memory. This resolves a COLT 2019 open problem of Woodworth and Srebro. |
| title | Efficient Convex Optimization Requires Superlinear Memory |
| topic | Machine Learning Computational Complexity Data Structures and Algorithms Optimization and Control |
| url | https://arxiv.org/abs/2203.15260 |