# Memory-Sample Lower Bounds for Learning Parity with Noise

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 27 references that are in the map.
- First posted on arXiv 5 Jul 2021.

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

- [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)
- [Mixing Complexity and its Applications to Neural Networks](https://mlsanity.com/paper/1703.00729/) (2017)
- [Information Theoretically Secure Databases](https://mlsanity.com/paper/1605.02646/) (2016)

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

- [Online Prediction in Sub-linear Space](https://mlsanity.com/paper/2207.07974/) (2022)
- [Near Optimal Memory-Regret Tradeoff for Online Learning](https://mlsanity.com/paper/2303.01673/) (2023)
- [Exponential quantum advantage in processing massive classical data](https://mlsanity.com/paper/2604.07639/) (2026)
- [Memory-Query Tradeoffs for Randomized Convex Optimization](https://mlsanity.com/paper/2306.12534/) (2023)
- [New constructions of pseudorandom codes](https://mlsanity.com/paper/2409.07580/) (2024)
- [Estimation of Entropy in Constant Space with Improved Sample Complexity](https://mlsanity.com/paper/2205.09804/) (2022)
- [Tight Time-Space Lower Bounds for Constant-Pass Learning](https://mlsanity.com/paper/2310.08070/) (2023)
- [Statistical Inference with Limited Memory: A Survey](https://mlsanity.com/paper/2312.15225/) (2023)
- [Gradient Descent is Pareto-Optimal in the Oracle Complexity and Memory Tradeoff for Feasibility Problems](https://mlsanity.com/paper/2404.06720/) (2024)
- [Foundations of Artificial Intelligence Frameworks: Notion and Limits of AGI](https://mlsanity.com/paper/2511.18517/) (2025)

## Abstract (arXiv)

In this work, we show, for the well-studied problem of learning parity under noise, where a learner tries to learn x=(x1,ldots,xn) ∈ 0,1n from a stream of random linear equations over F2 that are correct with probability frac12+varepsilon and flipped with probability frac12-varepsilon, that any learning algorithm requires either a memory of size Omega(n2/varepsilon) or an exponential number of samples. In fact, we study memory-sample lower bounds for a large class of learning problems, as characterized by [GRT'18], when the samples are noisy. A matrix M: A × X rightarrow -1,1 corresponds to the following learning problem with error parameter varepsilon: an unknown element x ∈ X is chosen uniformly at random. A learner tries to learn x from a stream of samples, (a1, b1), (a2, b2) ldots, where for every i, ai ∈ A is chosen uniformly at random and bi = M(ai,x) with probability 1/2+varepsilon and bi = -M(ai,x) with probability 1/2-varepsilon (0<varepsilon< frac12). Assume that k,ℓ, r are such that any submatrix of M of at least 2-k · |A| rows and at least 2-ℓ · |X| columns, has a bias of at most 2-r. We show that any learning algorithm for the learning problem corresponding to M, with error, requires either a memory of size at least Omegaleft(frack · ℓvarepsilon right), or at least 2Omega(r) samples. In particular, this shows that for a large class of learning problems, same as those in [GRT'18], any learning algorithm requires either a memory of size at least Omegaleft(frac(log |X|) · (log |A|)varepsilonright) or an exponential number of noisy samples. Our proof is based on adapting the arguments in [Raz'17,GRT'18] to the noisy case.