Minimax Rates of Entropy Estimation on Large Alphabets via Best Polynomial Approximation

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 the universal multiplicative constant factors of (k/n log k) 2 t log 2 k/n if n exceeds a constant factor of (k/log k); otherwise, there exists no consistent estimator. This refines the recent result of Valiant and Valiant that the minimal sample size for consistent entropy estimation scales according to Θ(k/log k). The apparatus of the best polynomial approximation plays a key role in both the construction of optimal estimators and, by a duality argument, the minimax lower bound.