mlsanityData to 14 Oct 2026

Stronger Memory-Query Tradeoffs for Convex Optimization: The Limitations of Subquadratic Memory

arXiv 2607.24827 ↗First posted 21 Jul 2026cs.DS cs.CC cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

We prove two lower bounds for the first order oracle complexity of minimizing a d-dimensional 1-Lipschitz convex function over the unit ball with m bits of memory. We first show that any such (possibly randomized) algorithm must make tildeOmega(fracd2√m) oracle queries. For deterministic optimization algorithms, we show that tildeOmega(mind1.6,fracd8/3m2/3) queries are required. For all memory regimes of interest, these improves upon the previous best known lower bounds of tildeOmega(maxfracd8/3m4/3,fracd4/3m1/6) and tildeOmega(fracd5/3m1/3) for randomized and deterministic algorithms respectively. Notably, due to existing upper bounds, our lower bound for deterministic algorithms is the first to show a sharp oracle complexity phase transition around m≈ d2, where a polylogarithmic change in memory leads to a mathsfpoly(d) change in the number of required oracle calls. Further, when the suboptimality is polynomially small in d, our lower bound randomized algorithms is the first to show that tildeOmega(d2) memory is necessary to nearly match the optimal query complexity among algorithms without memory constraints. Previously, such a result was only known for the regime where the suboptimality is quasipolynomially small in d.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 23 of its 36 references that are in the map. First posted on arXiv 21 Jul 2026.

Builds on

23 of 36 references.

References · 23

  1. 2020When is Memorization of Irrelevant Training Data Necessary for High-Accuracy Learning?cited by 104
  2. 2015Generalization in Adaptive Data Analysis and Holdout Reusecited by 83
  3. 2015Newton Sketch: A Linear-time Optimization Algorithm with Linear-Quadratic Convergencecited by 72
  4. 2015Communication Complexity of Distributed Convex Learning and Optimizationcited by 60
  5. 2020An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applicationscited by 57
  6. 2015Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequalitycited by 50
  7. 2015A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimizationcited by 50
  8. 2021The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communicationcited by 31
  9. 2013Fundamental Limits of Online and Distributed Algorithms for Statistical Learning and Estimationcited by 24
  10. 2019Complexity of Highly Parallel Non-Smooth Convex Optimizationcited by 22
  11. 2018Detecting Correlations with Little Memory and Communicationcited by 19
  12. 2014Lower Bounds on the Oracle Complexity of Nonsmooth Convex Optimization via Information Theorycited by 17
11 more
  1. 2018Lower Bounds for Parallel and Randomized Convex Optimizationcited by 17
  2. 2023Near Optimal Memory-Regret Tradeoff for Online Learningcited by 15
  3. 2019Space lower bounds for linear prediction in the streaming modelcited by 14
  4. 2022Efficient Convex Optimization Requires Superlinear Memorycited by 14
  5. 2019Open Problem: The Oracle Complexity of Convex Optimization with Limited Memorycited by 8
  6. 2021Information-constrained optimization: can adaptive processing of gradients help?cited by 8
  7. 2023Quadratic Memory is Necessary for Optimal Query Complexity in Convex Optimization: Center-of-Mass is Pareto-Optimalcited by 5
  8. 2023Memory-Query Tradeoffs for Randomized Convex Optimizationcited by 4
  9. 2023Memory-Constrained Algorithms for Convex Optimization via Recursive Cutting-Planescited by 3
  10. 2025On the Gradient Complexity of Private Optimization with Private Oraclescited by 2
  11. 2024Gradient Descent is Pareto-Optimal in the Oracle Complexity and Memory Tradeoff for Feasibility Problemscited by 1

Built on by

Not cited yet.