Learning Populations of Parameters

Abstract

Consider the following estimation problem: there are n entities, each with an unknown parameter p_i [0,1], and we observe n independent random variables, X_1,,X_n, with X_i Binomial(t, p_i). How accurately can one recover the "histogram" (i.e. cumulative density function) of the p_i's? While the empirical estimates would recover the histogram to earth mover distance (1t) (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.

Tasks

Reproductions