Optimal entropy estimation on large alphabet: fundamental limits and fast algorithms

Consider the problem of estimating the Shannon entropy of a distribution over k elements from n independent samples. We obtain the minimax mean- square error within universal multiplicative constant factors 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 (2011) that the mini- mal sample size for consistent entropy estimation scales. 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