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 \(Ω ̃(d1 + (4/3)δ) \) first-order queries (for any constant δ ∈ [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.