# Tight Time-Space Lower Bounds for Constant-Pass Learning

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 21 references that are in the map.
- First posted on arXiv 12 Oct 2023.

## Builds on (most cited first, 11 of 11)

- [Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning](https://mlsanity.com/paper/1602.05161/) (2016)
- [Fundamental Limits of Online and Distributed Algorithms for Statistical Learning and Estimation](https://mlsanity.com/paper/1311.3494/) (2013)
- [Memory-Sample Tradeoffs for Linear Regression with Small Error](https://mlsanity.com/paper/1904.08544/) (2019)
- [Extractor-Based Time-Space Lower Bounds for Learning](https://mlsanity.com/paper/1708.02639/) (2017)
- [Detecting Correlations with Little Memory and Communication](https://mlsanity.com/paper/1803.01420/) (2018)
- [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)
- [Memory-Sample Lower Bounds for Learning Parity with Noise](https://mlsanity.com/paper/2107.02320/) (2021)
- [Towards a combinatorial characterization of bounded memory learning](https://mlsanity.com/paper/2002.03123/) (2020)
- [Time-Space Tradeoffs for Distinguishing Distributions and Applications to Security of Goldreich's PRG](https://mlsanity.com/paper/2002.07235/) (2020)
- [Mixing Complexity and its Applications to Neural Networks](https://mlsanity.com/paper/1703.00729/) (2017)

## Built on by (most cited first, 2 of 2)

- [From Sparse Dependence to Sparse Attention: Unveiling How Chain-of-Thought Enhances Transformer Sample Efficiency](https://mlsanity.com/paper/2410.05459/) (2024)
- [A Simple, Optimal and Efficient Algorithm for Online Exp-Concave Optimization](https://mlsanity.com/paper/2512.23190/) (2025)

## Abstract (arXiv)

In his breakthrough paper, Raz showed that any parity learning algorithm requires either quadratic memory or an exponential number of samples [FOCS'16, JACM'19]. A line of work that followed extended this result to a large class of learning problems. Until recently, all these results considered learning in the streaming model, where each sample is drawn independently, and the learner is allowed a single pass over the stream of samples. Garg, Raz, and Tal [CCC'19] considered a stronger model, allowing multiple passes over the stream. In the 2-pass model, they showed that learning parities of size n requires either a memory of size n1.5 or at least 2^√n samples. (Their result also generalizes to other learning problems.) In this work, for any constant q, we prove tight memory-sample lower bounds for any parity learning algorithm that makes q passes over the stream of samples. We show that such a learner requires either Omega(n2) memory size or at least 2Omega(n) samples. Beyond establishing a tight lower bound, this is the first non-trivial lower bound for q-pass learning for any q≥ 3. Similar to prior work, our results extend to any learning problem with many nearly-orthogonal concepts. We complement the lower bound with an upper bound, showing that parity learning with q passes can be done efficiently with O(n2/log q) memory.