mlsanityData to 7 Oct 2026

Space lower bounds for linear prediction in the streaming model

arXiv 1902.03498 ↗First posted 9 Feb 2019cs.LG stat.MLcited by 14

Not on the map. Why?

Abstract (arXiv)

We show that fundamental learning tasks, such as finding an approximate linear separator or linear regression, require memory at least quadratic in the dimension, in a natural streaming setting. This implies that such problems cannot be solved (at least in this setting) by scalable memory-efficient streaming algorithms. Our results build on a memory lower bound for a simple linear-algebraic problem -- finding orthogonal vectors -- and utilize the estimates on the packing of the Grassmannian, the manifold of all linear subspaces of fixed dimension.

Key facts. Cited by 14 papers in the map (data through 7 Oct 2026). First posted on arXiv 9 Feb 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 2; 2022: 5; 2023: 5; 2024: 1; 2025: 0; 2026: 1.

14 papers.

Sort:

  1. 2022Memory Bounds for Continual Learningcited by 18
  2. 2022Efficient Convex Optimization Requires Superlinear Memorycited by 14
  3. 2022Strong Memory Lower Bounds for Learning Natural Modelscited by 10
  4. 2022Accelerated SGD for Non-Strongly-Convex Least Squarescited by 9
  5. 2021Bounded Memory Active Learning through Enriched Queriescited by 8
  6. 2021Memory-Sample Lower Bounds for Learning Parity with Noisecited by 8
  7. 2024The I/O Complexity of Attention, or How Optimal is Flash Attention?cited by 6
  8. 2023Quadratic Memory is Necessary for Optimal Query Complexity in Convex Optimization: Center-of-Mass is Pareto-Optimalcited by 5
  9. 2023Improved Space Bounds for Learning with Expertscited by 5
  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. 2022Learning what to remembercited by 0
  2. 2026Stronger Memory-Query Tradeoffs for Convex Optimization: The Limitations of Subquadratic Memorycited by 0