Total: 1
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 d1.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 a polynomial factor worse than the optimal ˜O(d) query bound for this problem obtained by cutting plane methods that use ˜O(d2) memory. This resolves one of the open problems in the COLT 2019 open problem publication of Woodworth and Srebro.