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 $deltain (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.