Minimax rates of entropy estimation on large alphabets via best polynomial approximation

Abstract

Consider the problem of estimating the Shannon entropy of a distribution over $k$ elements from $n$ independent samples. We show that the minimax mean-square error is within universal multiplicative constant factors of $$(\frac{k}{n\log k}{)}^2+\frac{{\log }^{2}k}{n}$$ if $n$ exceeds a constant factor of $\frac{k}{\log k}$; otherwise there exists no consistent estimator. This refines the recent result of Valiant-Valiant \cite{VV11} that the minimal sample size for consistent entropy estimation scales according to $\Theta (\frac{k}{\log k})$. The apparatus of best polynomial approximation plays a key role in both the construction of optimal estimators and, via a duality argument, the minimax lower bound.

References in corpus (5)

• Universal Estimation of Directed Information
• Testing composite hypotheses, Hermite polynomials and optimal estimation of a nonsmooth functional
• Nonquadratic estimators of a quadratic functional
• Chebyshev polynomials, moment matching, and optimal estimation of the unseen
• Adaptive Estimation of Shannon Entropy

Cited by in corpus (1)

• Beyond Maximum Likelihood: from Theory to Practice