Estimation of Entropy in Constant Space with Improved Sample Complexity
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.
Cite
Text
Aliakbarpour et al. "Estimation of Entropy in Constant Space with Improved Sample Complexity." Neural Information Processing Systems, 2022.Markdown
[Aliakbarpour et al. "Estimation of Entropy in Constant Space with Improved Sample Complexity." Neural Information Processing Systems, 2022.](https://mlanthology.org/neurips/2022/aliakbarpour2022neurips-estimation/)BibTeX
@inproceedings{aliakbarpour2022neurips-estimation,
title = {{Estimation of Entropy in Constant Space with Improved Sample Complexity}},
author = {Aliakbarpour, Maryam and McGregor, Andrew and Nelson, Jelani and Waingarten, Erik},
booktitle = {Neural Information Processing Systems},
year = {2022},
url = {https://mlanthology.org/neurips/2022/aliakbarpour2022neurips-estimation/}
}