mlsanityData to 14 Oct 2026

Memory-Query Tradeoffs for Randomized Convex Optimization

arXiv 2306.12534 ↗First posted 21 Jun 2023cs.DS cs.AI cs.LGcited by 4

Not on the map. Why?

Abstract (arXiv)

We show that any randomized first-order algorithm which minimizes a d-dimensional, 1-Lipschitz convex function over the unit ball must either use Omega(d2-δ) bits of memory or make Omega(d1+δ/6-o(1)) queries, for any constant δ∈ (0,1) and when the precision ε is quasipolynomially small in d. Our result implies that cutting plane methods, which use tildeO(d2) bits of memory and tildeO(d) queries, are Pareto-optimal among randomized first-order algorithms, and quadratic memory is required to achieve optimal query complexity for convex optimization.

Key facts. Cited by 4 papers in the map (data through 14 Oct 2026). Builds on 35 of its 61 references that are in the map. First posted on arXiv 21 Jun 2023.

Builds on

35 of 61 references.

References · 35

  1. 2014Convex Optimization: Algorithms and Complexitycited by 575
  2. 2019Does Learning Require Memorization? A Short Tale about a Long Tailcited by 460
  3. 2014Sketching as a Tool for Numerical Linear Algebracited by 288
  4. 2020When is Memorization of Irrelevant Training Data Necessary for High-Accuracy Learning?cited by 104
  5. 2017Gradient Descent Can Take Exponential Time to Escape Saddle Pointscited by 74
  6. 2015Newton Sketch: A Linear-time Optimization Algorithm with Linear-Quadratic Convergencecited by 72
  7. 2020An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applicationscited by 57
  8. 2015Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequalitycited by 50
  9. 2015A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimizationcited by 50
  10. 2016Tight Complexity Bounds for Optimizing Composite Objectivescited by 48
  11. 2016Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learningcited by 33
  12. 2014On Communication Cost of Distributed Statistical Estimation and Dimensionalitycited by 24
23 more
  1. 2019Memory-Sample Tradeoffs for Linear Regression with Small Errorcited by 22
  2. 2019Complexity of Highly Parallel Non-Smooth Convex Optimizationcited by 22
  3. 2022Memory Bounds for the Experts Problemcited by 20
  4. 2017Extractor-Based Time-Space Lower Bounds for Learningcited by 19
  5. 2018Detecting Correlations with Little Memory and Communicationcited by 19
  6. 2022Memory Bounds for Continual Learningcited by 19
  7. 2014Lower Bounds on the Oracle Complexity of Nonsmooth Convex Optimization via Information Theorycited by 17
  8. 2018Lower Bounds for Parallel and Randomized Convex Optimizationcited by 17
  9. 2022Online Prediction in Sub-linear Spacecited by 16
  10. 2023Near Optimal Memory-Regret Tradeoff for Online Learningcited by 15
  11. 2019Space lower bounds for linear prediction in the streaming modelcited by 14
  12. 2022Efficient Convex Optimization Requires Superlinear Memorycited by 14
  13. 2018Parallelization does not Accelerate Convex Optimization: Adaptivity Lower Bounds for Non-smooth Convex Minimizationcited by 12
  14. 2018Tight Query Complexity Lower Bounds for PCA via Finite Sample Deformed Wigner Lawcited by 11
  15. 2022Strong Memory Lower Bounds for Learning Natural Modelscited by 11
  16. 2021Memory-Sample Lower Bounds for Learning Parity with Noisecited by 10
  17. 2019The gradient complexity of linear regressioncited by 9
  18. 2020Towards a combinatorial characterization of bounded memory learningcited by 9
  19. 2019Open Problem: The Oracle Complexity of Convex Optimization with Limited Memorycited by 8
  20. 2023Quadratic Memory is Necessary for Optimal Query Complexity in Convex Optimization: Center-of-Mass is Pareto-Optimalcited by 5
  21. 2023Improved Space Bounds for Learning with Expertscited by 5
  22. 2023Streaming Algorithms for Learning with Experts: Deterministic Versus Robustcited by 3
  23. 2023Memory-Constrained Algorithms for Convex Optimization via Recursive Cutting-Planescited by 3

Built on by

Cited by year (2026 to 14 Oct)

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

4 papers.

  1. 2024Improved Complexity for Smooth Nonconvex Optimization: A Two-Level Online Learning Approach with Quasi-Newton Methodscited by 7
  2. 2024The I/O Complexity of Attention, or How Optimal is Flash Attention?cited by 6
  3. 2024Gradient Descent is Pareto-Optimal in the Oracle Complexity and Memory Tradeoff for Feasibility Problemscited by 1
  4. 2026Stronger Memory-Query Tradeoffs for Convex Optimization: The Limitations of Subquadratic Memorycited by 0