Efficient Convex Optimization Requires Superlinear Memory

We show that any memory-constrained, first-order algorithm which minimizesd-dimensional, 1-Lipschitz convex functions over the unit ball to 1/poly(d) accuracy using at most d1.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 Õ(d2) memory. This resolves one of the open problems in the COLT 2019 open problem publication of Woodworth and Srebro.