  We give query complexity lower bounds for convex optimization and the related
feasibility problem. We show that quadratic memory is necessary to achieve the
optimal oracle complexity for first-order convex optimization. In particular,
this shows that center-of-mass cutting-planes algorithms in dimension $d$ which
use $\tilde O(d^2)$ memory and $\tilde O(d)$ queries are Pareto-optimal for
both convex optimization and the feasibility problem, up to logarithmic
factors. Precisely, we prove that to minimize $1$-Lipschitz convex functions
over the unit ball to $1/d^4$ accuracy, any deterministic first-order
algorithms using at most $d^{2-\delta}$ bits of memory must make
$\tilde\Omega(d^{1+\delta/3})$ queries, for any $\delta\in[0,1]$. For the
feasibility problem, in which an algorithm only has access to a separation
oracle, we show a stronger trade-off: for at most $d^{2-\delta}$ memory, the
number of queries required is $\tilde\Omega(d^{1+\delta})$. This resolves a
COLT 2019 open problem of Woodworth and Srebro.
