Optimal estimation of entropy and other properties via best polynomial approximation

Tuesday, December 2, 2014 - 4:00pm to Wednesday, December 3, 2014 - 3:55pm

Event Calendar Category

LIDS Seminar Series

Speaker Name

Yihong Wu


Univ. of Illinois, Urbana-Champaign

Building and Room number



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).


Yihong Wu received the B.E. degree from Tsinghua University, Beijing, China, in 2006 and the M.A. and Ph.D. degrees from Princeton University in 2008 and 2011, all in electrical engineering. Prior to joining the ECE department at University of Illinois in 2013 as an assistant professor, he was a postdoctoral fellow with the Statistics Department at The Wharton School of University of Pennsylvania. His research interests are in information theory, high-dimensional statistics, stochastic control and optimal transportation.