Efficient Convex Optimization Requires Superlinear Memory

We show that any memory-constrained, first-order algorithm which minimizes d -dimensional, 1-Lipschitz convex functions over the unit ball to 1/poly( d ) accuracy using at most d 1.25 - δ bits of memory must make at least \(\tilde{\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 at least a polynomial factor worse than the optimal Õ( d ) query bound for this problem obtained by cutting plane methods that use Õ(d 2 ) memory. This resolves one of the open problems in the COLT 2019 open problem publication of Woodworth and Srebro.