# Estimation of Entropy in Constant Space with Improved Sample Complexity

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 45 references that are in the map.
- First posted on arXiv 19 May 2022.

## 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)
- [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)
- [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)
- [Time-Space Tradeoffs for Distinguishing Distributions and Applications to Security of Goldreich's PRG](https://mlsanity.com/paper/2002.07235/) (2020)
- [Towards Optimal Moment Estimation in Streaming and Distributed Models](https://mlsanity.com/paper/1907.05816/) (2019)

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

- [Online Prediction in Sub-linear Space](https://mlsanity.com/paper/2207.07974/) (2022)
- [Testing properties of distributions in the streaming model](https://mlsanity.com/paper/2309.03245/) (2023)
- [Statistical Inference with Limited Memory: A Survey](https://mlsanity.com/paper/2312.15225/) (2023)

## Abstract (arXiv)

Recent work of Acharya et al. (NeurIPS 2019) showed how to estimate the entropy of a distribution mathcal D over an alphabet of size k up to ±ε additive error by streaming over (k/ε3) · polylog(1/ε) i.i.d. samples and using only O(1) words of memory. In this work, we give a new constant memory scheme that reduces the sample complexity to (k/ε2)· polylog(1/ε). We conjecture that this is optimal up to polylog(1/ε) factors.