NeurIPS 2022accept11 citations
Estimation of Entropy in Constant Space with Improved Sample Complexity
Maryam Aliakbarpour, Andrew McGregor, Jelani Nelson, Erik Waingarten
Abstract
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 $\pm\epsilon$ additive error by streaming over $(k/\epsilon^3) \cdot \text{polylog}(1/\epsilon)$ 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/\epsilon^2)\cdot \text{polylog}(1/\epsilon)$. We conjecture that this is optimal up to $\text{polylog}(1/\epsilon)$ factors.
Sample complexityData streamsShannon Entropy
BibTeX
@inproceedings{
aliakbarpour2022estimation,
title={Estimation of Entropy in Constant Space with Improved Sample Complexity},
author={Maryam Aliakbarpour and Andrew McGregor and Jelani Nelson and Erik Waingarten},
booktitle={Advances in Neural Information Processing Systems},
editor={Alice H. Oh and Alekh Agarwal and Danielle Belgrave and Kyunghyun Cho},
year={2022},
url={https://openreview.net/forum?id=pV7f1Rq71I5}
}