Tuesday, December 2, 2014 - 4:00pm
Event Calendar Category
LIDS Seminar Series
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.
Reception to follow.