Part of Advances in Neural Information Processing Systems 30 (NIPS 2017)
Kevin Tian, Weihao Kong, Gregory Valiant
Consider the following estimation problem: there are n entities, each with an unknown parameter pi∈[0,1], and we observe n independent random variables, X1,…,Xn, with Xi∼ Binomial(t,pi). How accurately can one recover the histogram'' (i.e. cumulative density function) of the pi's? While the empirical estimates would recover the histogram to earth mover distance Θ(1√t) (equivalently, ℓ1 distance between the CDFs), we show that, provided n is sufficiently large, we can achieve error O(1t) which is information theoretically optimal. We also extend our results to the multi-dimensional parameter case, capturing settings where each member of the population has multiple associated parameters. Beyond the theoretical results, we demonstrate that the recovery algorithm performs well in practice on a variety of datasets, providing illuminating insights into several domains, including politics, sports analytics, and variation in the gender ratio of offspring.