NeurIPS Poster Estimation of Entropy in Constant Space with Improved Sample Complexity

Estimation of Entropy in Constant Space with Improved Sample Complexity

[ Abstract ]

[ Paper] [ OpenReview]

Abstract: Recent work of Acharya et al.~(NeurIPS 2019) showed how to estimate the entropy of a distribution

D

$\mathcal D$ over an alphabet of size

k

$k$ up to

\pm ϵ

$\pm\epsilon$ additive error by streaming over

(k / ϵ^{3}) \cdot polylog (1 / ϵ)

$(k/\epsilon^3) \cdot \text{polylog}(1/\epsilon)$ i.i.d.\ samples and using only

O (1)

$O(1)$ words of memory. In this work, we give a new constant memory scheme that reduces the sample complexity to

(k / ϵ^{2}) \cdot polylog (1 / ϵ)

$(k/\epsilon^2)\cdot \text{polylog}(1/\epsilon)$ . We conjecture that this is optimal up to

polylog (1 / ϵ)

$\text{polylog}(1/\epsilon)$ factors.

Chat is not available.