Costantinos Daskalakis: Learning Structured Distributions from a Constant Number of Samples

I will overview results on learning structured single-dimensional distributions, spending most of my time with two simple families:
- Poisson Binomial distributions: these are sums of independent but not necessarily iid Bernoullis; and
- SIIRVs: these are sums of independent integer valued random variables.
While both are well-studied families of distributions, I will argue that Berry-Esseen like results fall short from characterizing their general structure. Thus, I will offer stronger finitary central limit theorems, and will show how these are applicable to learning. In particular, I will show that these distributions can be learned from a number of samples that is independent of the number of variables that are summed over. I may also discuss applications to Nash equilibria of anonymous games.

Based on joint works (in order of intensity) with Papadimitriou, Diakonikolas, Servedio, O’Donnell and Tan