Optimal estimation of entropy and other properties via best polynomial approximation

Consider the problem of estimating the Shannon entropy of a distribution on k elements from n independent samples. We provide a non-asymptotic characterization of the optimal mean-square estimation error within universal multiplicative constant factors. This strengthens the result of Valiant-Valiant that the sample complexity for estimating the entropy within a few bits scales sub-linearly as \Theta(k/ log k). The apparatus of best polynomial approximation plays a key role in both the minimax lower bound and the construction of linear-time estimators with provable optimality. We then extend our theory to other properties of distributions such as the support size, where the optimal convergence rate in sample size is found to be super-polynomial. Experimental results on real data will be discussed. (Joint work with Pengkun Yang).