Faculty Recruiting Support CICS

Exact Parameter Learning for Mixture Distributions with Applications

24 Sep
Tuesday, 09/24/2019 4:00pm to 5:00pm
Computer Science Building Room 140
Theory Seminar
Speaker: Andrew McGregor

We present upper bounds on the sample complexity on learning the exact parameters of a mixture distribution. The bound applies for a range of distributions including Gaussian, Binomial, Poisson, and Chi-Squared and, at least in the case of Binomial mixtures, the bound is essentially tight. We then discuss applications to the problems of trace reconstruction (i.e., how many random subsequences of an unknown string x are required to determine x) and mixed sparse linear regression (i.e., how many linear measurements are required to learn a collection of sparse signals).

This is joint work with Akshay Krishnamurthy, Arya Mazumdar, and Soumyabrata Pal. Related papers appear at ESA 2019 and NeurIPS 2019.

Faculty Host