mlsanityData to 7 Oct 2026

Efficient Convex Optimization Requires Superlinear Memory

arXiv 2203.15260 ↗First posted 29 Mar 2022cs.LG cs.CC cs.DScited by 14

Not on the map. Why?

Abstract (arXiv)

We show that any memory-constrained, first-order algorithm which minimizes d-dimensional, 1-Lipschitz convex functions over the unit ball to 1/poly(d) accuracy using at most d1.25 - δ bits of memory must make at least tildeOmega(d1 + (4/3)δ) first-order queries (for any constant δ ∈ [0, 1/4]). Consequently, the performance of such memory-constrained algorithms are a polynomial factor worse than the optimal tildeO(d) query bound for this problem obtained by cutting plane methods that use tildeO(d2) memory. This resolves a COLT 2019 open problem of Woodworth and Srebro.

Key facts. Cited by 14 papers in the map (data through 7 Oct 2026). Builds on 31 of its 81 references that are in the map. First posted on arXiv 29 Mar 2022.

Builds on

31 of 81 references.

References · 31

  1. 2014Convex Optimization: Algorithms and Complexitycited by 569
  2. 2018The Convergence of Sparsified Gradient Methodscited by 228
  3. 2013Communication Efficient Distributed Optimization using an Approximate Newton-type Methodcited by 131
  4. 2015Newton Sketch: A Linear-time Optimization Algorithm with Linear-Quadratic Convergencecited by 72
  5. 2015Communication Complexity of Distributed Convex Learning and Optimizationcited by 59
  6. 2020An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applicationscited by 57
  7. 2015Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequalitycited by 50
  8. 2015A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimizationcited by 50
  9. 2016Tight Complexity Bounds for Optimizing Composite Objectivescited by 47
  10. 2017Newton-Type Methods for Non-Convex Optimization Under Inexact Hessian Informationcited by 41
  11. 2016Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learningcited by 32
  12. 2014Communication-Efficient Distributed Dual Coordinate Ascentcited by 30
19 more
  1. 2021The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communicationcited by 30
  2. 2018Communication-Computation Efficient Gradient Codingcited by 26
  3. 2014On Communication Cost of Distributed Statistical Estimation and Dimensionalitycited by 24
  4. 2013Fundamental Limits of Online and Distributed Algorithms for Statistical Learning and Estimationcited by 23
  5. 2019Memory-Sample Tradeoffs for Linear Regression with Small Errorcited by 22
  6. 2019Complexity of Highly Parallel Non-Smooth Convex Optimizationcited by 21
  7. 2018Detecting Correlations with Little Memory and Communicationcited by 19
  8. 2017Extractor-Based Time-Space Lower Bounds for Learningcited by 18
  9. 2018Lower Bounds for Parallel and Randomized Convex Optimizationcited by 17
  10. 2021Thinking Inside the Ball: Near-Optimal Minimization of the Maximal Losscited by 17
  11. 2014Lower Bounds on the Oracle Complexity of Nonsmooth Convex Optimization via Information Theorycited by 16
  12. 2019Space lower bounds for linear prediction in the streaming modelcited by 14
  13. 2018Tight Query Complexity Lower Bounds for PCA via Finite Sample Deformed Wigner Lawcited by 11
  14. 2018Parallelization does not Accelerate Convex Optimization: Adaptivity Lower Bounds for Non-smooth Convex Minimizationcited by 11
  15. 2017Lower Bound for Randomized First Order Convex Optimizationcited by 9
  16. 2019The gradient complexity of linear regressioncited by 9
  17. 2019Querying a Matrix through Matrix-Vector Productscited by 8
  18. 2019Open Problem: The Oracle Complexity of Convex Optimization with Limited Memorycited by 8
  19. 2018On the Randomized Complexity of Minimizing a Convex Quadratic Functioncited by 5

Built on by

Cited by year (2026 to 7 Oct)

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

14 papers.

Sort:

  1. 2022Memory Bounds for Continual Learningcited by 18
  2. 2022Online Prediction in Sub-linear Spacecited by 16
  3. 2023Near Optimal Memory-Regret Tradeoff for Online Learningcited by 15
  4. 2022Strong Memory Lower Bounds for Learning Natural Modelscited by 10
  5. 2024Improved Complexity for Smooth Nonconvex Optimization: A Two-Level Online Learning Approach with Quasi-Newton Methodscited by 7
  6. 2024The I/O Complexity of Attention, or How Optimal is Flash Attention?cited by 6
  7. 2023Quadratic Memory is Necessary for Optimal Query Complexity in Convex Optimization: Center-of-Mass is Pareto-Optimalcited by 5
  8. 2023Improved Space Bounds for Learning with Expertscited by 5
  9. 2023Tight Memory-Regret Lower Bounds for Streaming Banditscited by 4
  10. 2023Memory-Query Tradeoffs for Randomized Convex Optimizationcited by 4
  11. 2023Memory-Constrained Algorithms for Convex Optimization via Recursive Cutting-Planescited by 3
  12. 2023Tight Time-Space Lower Bounds for Constant-Pass Learningcited by 2
2 more
  1. 2024Gradient Descent is Pareto-Optimal in the Oracle Complexity and Memory Tradeoff for Feasibility Problemscited by 1
  2. 2026Stronger Memory-Query Tradeoffs for Convex Optimization: The Limitations of Subquadratic Memorycited by 0