Timezone: »

 
Poster
Learning Populations of Parameters
Kevin Tian · Weihao Kong · Gregory Valiant

Tue Dec 05 06:30 PM -- 10:30 PM (PST) @ Pacific Ballroom #60
in Posters Tue »
Consider the following estimation problem: there are $n$ entities, each with an unknown parameter $p_i \in [0,1]$, and we observe $n$ independent random variables, $X_1,\ldots,X_n$, with $X_i \sim $ 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 $\Theta(\frac{1}{\sqrt{t}})$ (equivalently, $\ell_1$ distance between the CDFs), we show that, provided $n$ is sufficiently large, we can achieve error $O(\frac{1}{t})$ 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.
Keywords: Learning Theory · Density Estimation

Author Information

Kevin Tian (Stanford University)
Weihao Kong (Stanford University)
Gregory Valiant (Stanford University)

More from the Same Authors