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

arXiv: https://arxiv.org/abs/2607.24827 · HTML: https://mlsanity.com/paper/2607.24827/

## 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 (most cited first, 23 of 23)

- [When is Memorization of Irrelevant Training Data Necessary for High-Accuracy Learning?](https://mlsanity.com/paper/2012.06421/) (2020)
- [Generalization in Adaptive Data Analysis and Holdout Reuse](https://mlsanity.com/paper/1506.02629/) (2015)
- [Newton Sketch: A Linear-time Optimization Algorithm with Linear-Quadratic Convergence](https://mlsanity.com/paper/1505.02250/) (2015)
- [Communication Complexity of Distributed Convex Learning and Optimization](https://mlsanity.com/paper/1506.01900/) (2015)
- [An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applications](https://mlsanity.com/paper/2004.04250/) (2020)
- [Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequality](https://mlsanity.com/paper/1506.07216/) (2015)
- [A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization](https://mlsanity.com/paper/1508.04874/) (2015)
- [The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication](https://mlsanity.com/paper/2102.01583/) (2021)
- [Fundamental Limits of Online and Distributed Algorithms for Statistical Learning and Estimation](https://mlsanity.com/paper/1311.3494/) (2013)
- [Complexity of Highly Parallel Non-Smooth Convex Optimization](https://mlsanity.com/paper/1906.10655/) (2019)
- [Detecting Correlations with Little Memory and Communication](https://mlsanity.com/paper/1803.01420/) (2018)
- [Lower Bounds on the Oracle Complexity of Nonsmooth Convex Optimization via Information Theory](https://mlsanity.com/paper/1407.5144/) (2014)
- [Lower Bounds for Parallel and Randomized Convex Optimization](https://mlsanity.com/paper/1811.01903/) (2018)
- [Near Optimal Memory-Regret Tradeoff for Online Learning](https://mlsanity.com/paper/2303.01673/) (2023)
- [Space lower bounds for linear prediction in the streaming model](https://mlsanity.com/paper/1902.03498/) (2019)
- [Efficient Convex Optimization Requires Superlinear Memory](https://mlsanity.com/paper/2203.15260/) (2022)
- [Open Problem: The Oracle Complexity of Convex Optimization with Limited Memory](https://mlsanity.com/paper/1907.00762/) (2019)
- [Information-constrained optimization: can adaptive processing of gradients help?](https://mlsanity.com/paper/2104.00979/) (2021)
- [Quadratic Memory is Necessary for Optimal Query Complexity in Convex Optimization: Center-of-Mass is Pareto-Optimal](https://mlsanity.com/paper/2302.04963/) (2023)
- [Memory-Query Tradeoffs for Randomized Convex Optimization](https://mlsanity.com/paper/2306.12534/) (2023)
- [Memory-Constrained Algorithms for Convex Optimization via Recursive Cutting-Planes](https://mlsanity.com/paper/2306.10096/) (2023)
- [On the Gradient Complexity of Private Optimization with Private Oracles](https://mlsanity.com/paper/2511.13999/) (2025)
- [Gradient Descent is Pareto-Optimal in the Oracle Complexity and Memory Tradeoff for Feasibility Problems](https://mlsanity.com/paper/2404.06720/) (2024)

## 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.