PhD Seminar: Sample-efficient Learning of Mixtures

Wednesday, July 12, 2017 12:00 pm - 12:00 pm EDT (GMT -04:00)

Speaker: Hassan Ashtiani, PhD Candidate

We consider PAC learning of probability distributions (a.k.a. density estimation), where we are given an i.i.d. sample generated from an unknown target distribution, and want to output a distribution that is close to the target in total variation distance. Let F be an arbitrary class of probability distributions, and let \(F^k\) denote the class of k-mixtures of elements of F. Assuming the existence of a method for learning F in the realizable setting, we provide a method for learning \(F^k\) in the agnostic setting. Furthermore, roughly speaking, we show that the sample complexity increases at most by a factor of \({k}/{\epsilon^2}\)

 We provide two applications of our main result. First, we show that the class of mixtures of k axis-aligned Gaussians in d-dimensional Euclidean space is PAC-learnable in the agnostic setting with sample complexity \(O({kd}/{\epsilon ^ 4})\) which is tight in k and d. Second, we show that the class of mixtures of k Gaussians is PAC-learnable in the agnostic setting with sample complexity \(O({kd}/{\epsilon ^ 4})\), which improves the previous known bounds in its dependence on k and d.

 This is joint work with Abbas Mehrabian and Shai Ben-David.