Efficient Convex Optimization Requires Superlinear Memory

Annie Marsden, Vatsal Sharan, Aaron Sidford, Gregory Valiant
Proceedings of Thirty Fifth Conference on Learning Theory, PMLR 178:2390-2430, 2022.

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 this Paper

BibTeX
@InProceedings{pmlr-v178-marsden22a, title = {Efficient Convex Optimization Requires Superlinear Memory}, author = {Marsden, Annie and Sharan, Vatsal and Sidford, Aaron and Valiant, Gregory}, booktitle = {Proceedings of Thirty Fifth Conference on Learning Theory}, pages = {2390--2430}, year = {2022}, editor = {Loh, Po-Ling and Raginsky, Maxim}, volume = {178}, series = {Proceedings of Machine Learning Research}, month = {02--05 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v178/marsden22a/marsden22a.pdf}, url = {https://proceedings.mlr.press/v178/marsden22a.html}, 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.} }
Endnote
%0 Conference Paper %T Efficient Convex Optimization Requires Superlinear Memory %A Annie Marsden %A Vatsal Sharan %A Aaron Sidford %A Gregory Valiant %B Proceedings of Thirty Fifth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2022 %E Po-Ling Loh %E Maxim Raginsky %F pmlr-v178-marsden22a %I PMLR %P 2390--2430 %U https://proceedings.mlr.press/v178/marsden22a.html %V 178 %X 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.
APA
Marsden, A., Sharan, V., Sidford, A. & Valiant, G.. (2022). Efficient Convex Optimization Requires Superlinear Memory. Proceedings of Thirty Fifth Conference on Learning Theory, in Proceedings of Machine Learning Research 178:2390-2430 Available from https://proceedings.mlr.press/v178/marsden22a.html.

Related Material