Memory-Query Tradeoffs for Randomized Convex Optimization
Xi Chen, Binghui Peng · 2023
We show that any randomized first-order algorithm which minimizes a d-dimensional, 1-Lipschitz convex function over the unit ball must either use $\Omega\left(d^{2-\delta}\right)$ bits of memory or make $\Omega\left(d^{1+\delta / 6-o(1)}\right)$ queries, for any constant $\delta \in(0,1)$ and when the precision $\epsilon$ is quasipolynomially small in d. Our result implies that cutting plane methods, which use $\tilde{O}\left(d^{2}\right)$ bits of memory and $\tilde{O}(d)$ queries, are Pareto-optimal among randomized first-order algorithms, and quadratic memory is required to achieve optimal query complexity for convex optimization.