Quadratic Memory Is Necessary for Optimal Query Complexity in Convex Optimization: Center of Mass Is Pareto Optimal

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-plane algorithms in dimension d, which use [Formula: see text] memory and [Formula: see text] queries, are Pareto optimal for both convex optimization and the feasibility problem, up to logarithmic factors. Precisely, building upon techniques introduced in previous works, we prove that to minimize 1-Lipschitz convex functions over the unit ball to [Formula: see text] accuracy, any deterministic first-order algorithms using at most [Formula: see text] bits of memory must make [Formula: see text] queries for any [Formula: see text]. For the feasibility problem, in which an algorithm only has access to a separation oracle, we show a stronger trade-off; for at most [Formula: see text] memory, the number of queries required is [Formula: see text]. This resolves a Conference on Learning Theory 2019 open problem. Funding: This work was partly supported by the Air Force Office of Scientific Research [Grant FA9550-19-1-0263] and the Office of Naval Research [Grant N00014-18-1-2122].