"Central Limit Theorems and Tight Lower Bounds for Entropy Estimation"
Paul Valiant
University of California, Berkeley
Monday, April 2nd, 2012, 2:00 pm
EBU3B, Room 4140
Abstract
In joint work with Gregory Valiant, we have been investigating a new approach to estimating symmetric properties of distributions, including the standard and fundamental properties of entropy and support size. In a companion talk on Wednesday I will introduce the first explicit sublinear-sample estimators for these problems, which estimate these quantities to constant additive error using O(n/log n) samples. In this independent but complementary talk, I show that this result is in fact optimal up to constant factors. The analysis makes crucial use of two new multivariate central limit theorems that appear quite natural and general. The first is proven directly via Stein's method; the second is proven in terms of the first using a recent generalization of Newton's inequalities. The talk will include a high level overview of these techniques, and their application both in our context and more generally.
Short biography
Paul Valiant is a postdoctoral fellow at the University of California, Berkeley. He earned his PhD from MIT in EECS in 2008 under the supervision of Silvio Micali and previously graduated from Stanford University in 2004 with a BS in mathematics and physics and an MS in computer science. His research investigates applications of the computational perspective to other areas of science, particularly focusing on statistics, biology, and mathematics. He was a co-winner of the Machtey award for best student paper at FOCS 2005, winner of the best student paper award at the Theoretical Cryptography Conference in 2008, and was awarded the NSF Mathematical Sciences Postdoctoral Research Fellowship in 2009.