Efficient Convex Optimization Requires Superlinear Memory
This work addresses a foundational issue in optimization theory for researchers and practitioners, providing a theoretical lower bound that is not incremental but resolves a known open problem.
The paper tackles the problem of memory-constrained convex optimization by proving that algorithms with limited memory require significantly more queries than optimal methods, specifically showing that using at most d^{1.25 - δ} bits leads to at least Ω̃(d^{1 + (4/3)δ}) queries for 1/poly(d) accuracy, resolving an open problem from COLT 2019.
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.