Efficient Convex Optimization Requires Superlinear Memory
Abstract
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 - \delta}$ bits of memory must make at least $\Omega(d^{1 + (4/3)\delta})$ first-order queries (for any constant $\delta \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 one of the open problems in the COLT 2019 open problem publication of Woodworth and Srebro.
Cite
Text
Marsden et al. "Efficient Convex Optimization Requires Superlinear Memory." Conference on Learning Theory, 2022.Markdown
[Marsden et al. "Efficient Convex Optimization Requires Superlinear Memory." Conference on Learning Theory, 2022.](https://mlanthology.org/colt/2022/marsden2022colt-efficient/)BibTeX
@inproceedings{marsden2022colt-efficient,
title = {{Efficient Convex Optimization Requires Superlinear Memory}},
author = {Marsden, Annie and Sharan, Vatsal and Sidford, Aaron and Valiant, Gregory},
booktitle = {Conference on Learning Theory},
year = {2022},
pages = {2390-2430},
volume = {178},
url = {https://mlanthology.org/colt/2022/marsden2022colt-efficient/}
}