Quadratic Memory is Necessary for Optimal Query Complexity in Convex Optimization: Center-of-Mass is Pareto-Optimal
This work addresses a foundational problem in optimization theory, providing theoretical limits that impact algorithm design for researchers and practitioners in machine learning and optimization, though it is incremental in refining existing lower bounds.
The paper tackles the problem of determining the memory-query trade-off in convex optimization, showing that quadratic memory is necessary for optimal query complexity, with center-of-mass algorithms being Pareto-optimal up to logarithmic factors. It resolves an open problem from COLT 2019 by proving lower bounds, such as requiring Ω̃(d^(1+δ/3)) queries for deterministic first-order algorithms with d^(2-δ) memory to achieve 1/d^4 accuracy.
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-δ}$ bits of memory must make $\tildeΩ(d^{1+δ/3})$ queries, for any $δ\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-δ}$ memory, the number of queries required is $\tildeΩ(d^{1+δ})$. This resolves a COLT 2019 open problem of Woodworth and Srebro.