[edit]
Quadratic Memory is Necessary for Optimal Query Complexity in Convex Optimization: Center-of-Mass is Pareto-Optimal
Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:4696-4736, 2023.
Abstract
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 ˜O(d2) memory and ˜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/d4 accuracy, any deterministic first-order algorithms using at most d2−δ bits of memory must make ˜Ω(d1+δ/3) queries, for any δ∈[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 d2−δ memory, the number of queries required is ˜Ω(d1+δ). This resolves a COLT 2019 open problem of Woodworth and Srebro.