Memory-Query Tradeoffs for Randomized Convex Optimization
Xi Chen Binghui Peng
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(d^{2-\delta})$ bits of memory or make $\Omega(d^{1+\delta/6-o(1)})$
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}(d^2)$ 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.