Settling the Polynomial Learnability of Mixtures of Gaussians

Citation

Authors: Ankur Moitra, Gregory Valiant
Year: 2010
Venue: 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010)
arXiv: arXiv:1004.4223
URL: https://people.csail.mit.edu/moitra/docs/mv.pdf

One-Line Takeaway

Moitra and Valiant prove that mixtures of k Gaussians are polynomially learnable for fixed k, while also showing that the exponential dependence on k is unavoidable.

Technical Summary

Setup: for fixed $k$ , let $F = \sum_{i=1}^{k} \alpha_i \mathcal N(\mu_i,\Sigma_i).$ The paper defines $F$ to be $\epsilon$ -statistically learnable when every weight satisfies $\alpha_i\ge \epsilon$ and every pair of components has statistical distance at least $\epsilon$ .
Main theorem: for every fixed $k$ , if $F$ is $\epsilon$ -statistically learnable, then there is an algorithm running in time and sample complexity polynomial in the ambient dimension and $1/\epsilon$ that outputs a mixture $\widehat F$ with statistical distance at most $\epsilon$ from $F$ .
Structural point: the dependence on $k$ is not polynomial in general. The paper also proves an exponential lower bound in $k$ , showing that this fixed- $k$ learnability result is essentially the best possible dependence on the number of components.
Technique: recursively project to lower-dimensional problems, identify useful subspaces / clusters, and invoke robust lower-order recovery procedures until the full $k$ -mixture is reconstructed.

Assumptions And Limits

The guarantee is polynomial only when k is treated as fixed; the dependence on the number of components is exponential and provably cannot be removed in general. As with the Kalai-Moitra-Valiant paper, the results are for Gaussian mixtures rather than arbitrary latent classes.

Relevance To This Project

This paper is useful as a complexity baseline for latent-strategy recovery: even in a highly structured Gaussian setting, exact recovery can remain computationally expensive in the number of latent components. For x -> z -> y, that is a reminder that identifiability of many latent strategies does not imply practically learnable recovery.

Comparison Notes

Kalai, Moitra, and Valiant (2010) solve the k = 2 case cleanly; this paper handles general fixed k. Hsu and Kakade (2013) regain simpler spectral recovery by imposing the stronger spherical/general-position structure.

Source Note

Retrieval: alphaXiv MCP get_paper_content on arXiv:1004.4223; no local cache or downloaded source artifacts were created.

Verified from source: title, authors, year, FOCS venue, arXiv identifier, the definition of $\epsilon$ -statistical learnability, the fixed- $k$ polynomial learnability theorem, and the paper's matching claim that exponential dependence on $k$ is unavoidable were checked against the alphaXiv-extracted arXiv text.