mlsanityData to 14 Oct 2026

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

arXiv 2302.04963 ↗First posted 9 Feb 2023cs.LG cs.CC cs.DScited by 5

Not on the map. Why?

Abstract (arXiv)

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(d2) 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/d4 accuracy, any deterministic first-order algorithms using at most d2-δ bits of memory must make tildeOmega(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 tildeOmega(d1+δ). This resolves a COLT 2019 open problem of Woodworth and Srebro.

Key facts. Cited by 5 papers in the map (data through 14 Oct 2026). Builds on 18 of its 47 references that are in the map. First posted on arXiv 9 Feb 2023.

Builds on

18 of 47 references.

References · 18

  1. 2020When is Memorization of Irrelevant Training Data Necessary for High-Accuracy Learning?cited by 104
  2. 2015Communication Complexity of Distributed Convex Learning and Optimizationcited by 60
  3. 2020An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applicationscited by 57
  4. 2015A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimizationcited by 50
  5. 2016Tight Complexity Bounds for Optimizing Composite Objectivescited by 48
  6. 2016Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learningcited by 33
  7. 2021The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communicationcited by 31
  8. 2019Memory-Sample Tradeoffs for Linear Regression with Small Errorcited by 22
  9. 2019Complexity of Highly Parallel Non-Smooth Convex Optimizationcited by 22
  10. 2013Memory Limited, Streaming PCAcited by 21
  11. 2017Extractor-Based Time-Space Lower Bounds for Learningcited by 19
  12. 2018Detecting Correlations with Little Memory and Communicationcited by 19
6 more
  1. 2019Space lower bounds for linear prediction in the streaming modelcited by 14
  2. 2022Efficient Convex Optimization Requires Superlinear Memorycited by 14
  3. 2018Parallelization does not Accelerate Convex Optimization: Adaptivity Lower Bounds for Non-smooth Convex Minimizationcited by 12
  4. 2022Strong Memory Lower Bounds for Learning Natural Modelscited by 11
  5. 2017Lower Bound for Randomized First Order Convex Optimizationcited by 9
  6. 2019Open Problem: The Oracle Complexity of Convex Optimization with Limited Memorycited by 8

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 3; 2024: 1; 2025: 0; 2026: 1.

5 papers.

  1. 2023Near Optimal Memory-Regret Tradeoff for Online Learningcited by 15
  2. 2023Memory-Query Tradeoffs for Randomized Convex Optimizationcited by 4
  3. 2023Memory-Constrained Algorithms for Convex Optimization via Recursive Cutting-Planescited by 3
  4. 2024Gradient Descent is Pareto-Optimal in the Oracle Complexity and Memory Tradeoff for Feasibility Problemscited by 1
  5. 2026Stronger Memory-Query Tradeoffs for Convex Optimization: The Limitations of Subquadratic Memorycited by 0