Efficiently Learning Mixtures of Two Gaussians

Citation

• Authors: Adam Tauman Kalai, Ankur Moitra, Gregory Valiant
• Year: 2010
• Venue: Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC 2010)
• arXiv: None
• URL: https://www.microsoft.com/en-us/research/publication/efficiently-learning-mixtures-two-gaussians/

One-Line Takeaway

Kalai, Moitra, and Valiant give the first polynomial-time algorithm with inverse-polynomial statistical guarantees for learning mixtures of two arbitrary Gaussians under essentially minimal nondegeneracy assumptions.

Technical Summary

• Setup: the target law is $$F = w_1 \mathcal N(\mu_1,\Sigma_1) + w_2 \mathcal N(\mu_2,\Sigma_2),$$ with $w_1,w_2$ bounded away from $0$ and the two component distributions separated by inverse-polynomial statistical distance.
• One-dimensional core: the hard part is robust inversion of the first six moments of a one-dimensional two-Gaussian mixture; the paper proves that sufficiently accurate estimates of those moments determine the parameters to inverse-polynomial accuracy.
• Multivariate reduction: the $d$-dimensional problem is reduced to a carefully chosen family of one-dimensional projections, after which the projected moment systems are stitched back together to recover $(w_i,\mu_i,\Sigma_i)$.
• Main guarantee: mixtures of two arbitrary Gaussians are learnable in polynomial time and with polynomial sample complexity under essentially minimal nondegeneracy assumptions, giving the first inverse-polynomial recovery guarantee for this case.

Assumptions And Limits

The result is specific to two Gaussian components and still requires nondegeneracy through bounded-away-from-zero weights and component statistical distance. It is a recovery algorithm, not a generic theorem for arbitrary component families.

Relevance To This Project

This paper is the first clear bridge from pure identifiability to efficient recovery. In the repo's terms, it says that if latent strategies correspond to a very rigid two-component Gaussian-like family, then one can hope not only for theoretical identifiability of z but also for a computationally feasible estimator.

Comparison Notes

Moitra and Valiant (2010) generalize the computational story from two Gaussians to fixed k. Hardt and Price (2015) later sharpen the local sample-complexity picture for the two-component case.

Related Notes

• Background on identification and learning of mixture distributions
• Settling the Polynomial Learnability of Mixtures of Gaussians
• Tight Bounds for Learning a Mixture of Two Gaussians