mlsanityData to 7 Oct 2026

Estimation of Entropy in Constant Space with Improved Sample Complexity

arXiv 2205.09804 ↗First posted 19 May 2022cs.DS cs.IT cs.LGcited by 3

Not on the map. Why?

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.

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

Builds on

8 of 45 references.

References · 8

  1. 2016Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learningcited by 32
  2. 2019Memory-Sample Tradeoffs for Linear Regression with Small Errorcited by 22
  3. 2017Extractor-Based Time-Space Lower Bounds for Learningcited by 18
  4. 2019Communication and Memory Efficient Testing of Discrete Distributionscited by 8
  5. 2021Memory-Sample Lower Bounds for Learning Parity with Noisecited by 8
  6. 2019Estimating Entropy of Distributions in Constant Spacecited by 7
  7. 2020Time-Space Tradeoffs for Distinguishing Distributions and Applications to Security of Goldreich's PRGcited by 3
  8. 2019Towards Optimal Moment Estimation in Streaming and Distributed Modelscited by 1

Built on by

Cited by year

Citing papers per year: 2022: 1; 2023: 2.

3 papers.

  1. 2022Online Prediction in Sub-linear Spacecited by 16
  2. 2023Testing properties of distributions in the streaming modelcited by 3
  3. 2023Statistical Inference with Limited Memory: A Surveycited by 1