# Statistical Inference with Limited Memory: A Survey

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 140 references that are in the map.
- First posted on arXiv 23 Dec 2023.

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

- [The Information Bottleneck Problem and Its Applications in Machine Learning](https://mlsanity.com/paper/2004.14941/) (2020)
- [Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequality](https://mlsanity.com/paper/1506.07216/) (2015)
- [Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning](https://mlsanity.com/paper/1602.05161/) (2016)
- [Geometric Lower Bounds for Distributed Parameter Estimation under Communication Constraints](https://mlsanity.com/paper/1802.08417/) (2018)
- [Inference under Information Constraints I: Lower Bounds from Chi-Square Contraction](https://mlsanity.com/paper/1812.11476/) (2018)
- [Fundamental Limits of Online and Distributed Algorithms for Statistical Learning and Estimation](https://mlsanity.com/paper/1311.3494/) (2013)
- [On Communication Cost of Distributed Statistical Estimation and Dimensionality](https://mlsanity.com/paper/1405.1665/) (2014)
- [Memory-Sample Tradeoffs for Linear Regression with Small Error](https://mlsanity.com/paper/1904.08544/) (2019)
- [Inference under Information Constraints II: Communication Constraints and Shared Randomness](https://mlsanity.com/paper/1905.08302/) (2019)
- [Testing Identity of Structured Distributions](https://mlsanity.com/paper/1410.2266/) (2014)
- [Optimal Identity Testing with High Probability](https://mlsanity.com/paper/1708.02728/) (2017)
- [Detecting Correlations with Little Memory and Communication](https://mlsanity.com/paper/1803.01420/) (2018)
- [Inference under Information Constraints III: Local Privacy Constraints](https://mlsanity.com/paper/2101.07981/) (2021)
- [Communication-constrained hypothesis testing: Optimality, robustness, and reverse data processing inequalities](https://mlsanity.com/paper/2206.02765/) (2022)
- [Memory-Sample Lower Bounds for Learning Parity with Noise](https://mlsanity.com/paper/2107.02320/) (2021)
- [Communication and Memory Efficient Testing of Discrete Distributions](https://mlsanity.com/paper/1906.04709/) (2019)
- [Estimating Entropy of Distributions in Constant Space](https://mlsanity.com/paper/1911.07976/) (2019)
- [Domain Compression and its Application to Randomness-Optimal Distributed Goodness-of-Fit](https://mlsanity.com/paper/1907.08743/) (2019)
- [Distributed Estimation of Gaussian Correlations](https://mlsanity.com/paper/1805.12472/) (2018)
- [Communication Complexity of Estimating Correlations](https://mlsanity.com/paper/1901.09100/) (2019)
- [Estimation of Entropy in Constant Space with Improved Sample Complexity](https://mlsanity.com/paper/2205.09804/) (2022)
- [Testing properties of distributions in the streaming model](https://mlsanity.com/paper/2309.03245/) (2023)
- [An Information-Theoretic Proof of the Streaming Switching Lemma for Symmetric Encryption](https://mlsanity.com/paper/2004.09935/) (2020)
- [Comparison Graphs: a Unified Method for Uniformity Testing](https://mlsanity.com/paper/2012.01882/) (2020)
- [Simpler Distribution Testing with Little Memory](https://mlsanity.com/paper/2311.01145/) (2023)

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

- [Statistical Inference on Gradient Flows](https://mlsanity.com/paper/2606.01257/) (2026)

## Abstract (arXiv)

The problem of statistical inference in its various forms has been the subject of decades-long extensive research. Most of the effort has been focused on characterizing the behavior as a function of the number of available samples, with far less attention given to the effect of memory limitations on performance. Recently, this latter topic has drawn much interest in the engineering and computer science literature. In this survey paper, we attempt to review the state-of-the-art of statistical inference under memory constraints in several canonical problems, including hypothesis testing, parameter estimation, and distribution property testing/estimation. We discuss the main results in this developing field, and by identifying recurrent themes, we extract some fundamental building blocks for algorithmic construction, as well as useful techniques for lower bound derivations.