Stronger Memory-Query Tradeoffs for Convex Optimization: The Limitations of Subquadratic Memory

We prove two lower bounds for the first order oracle complexity of minimizing a d-dimensional 1-Lipschitz convex function over the unit ball with m bits of memory. We first show that any such (possibly randomized) algorithm must make \tildeΩ(\frac{d^2}{\sqrt{m}}) oracle queries. For deterministic optimization algorithms, we show that \tildeΩ(\min{d^{1.6},\frac{d^{8/3}}{m^{2/3}}}) queries are required. For all memory regimes of interest, these improves upon the previous best known lower bounds of \tildeΩ(\max{\frac{d^{8/3}}{m^{4/3}},\frac{d^{4/3}}{m^{1/6}}}) and \tildeΩ(\frac{d^{5/3}}{m^{1/3}}) for randomized and deterministic algorithms respectively. Notably, due to existing upper bounds, our lower bound for deterministic algorithms is the first to show a sharp oracle complexity phase transition around m\approx d^2, where a polylogarithmic change in memory leads to a poly(d) change in the number of required oracle calls. Further, when the suboptimality is polynomially small in d, our lower bound randomized algorithms is the first to show that \tildeΩ(d^2) memory is necessary to nearly match the optimal query complexity among algorithms without memory constraints. Previously, such a result was only known for the regime where the suboptimality is quasipolynomially small in d.