Tight Bounds for Learning a Mixture of Two Gaussians

Citation

Authors: Moritz Hardt, Eric Price
Year: 2015
Venue: Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC 2015), 753-760
arXiv: arXiv:1404.4997
URL: https://www.mit.edu/~ecprice/papers/gaussians.pdf

One-Line Takeaway

Hardt and Price quantify the local difficulty of recovering a two-Gaussian mixture, showing how sample complexity worsens near singular or nearly colliding parameter configurations even though the model remains identifiable in principle.

Technical Summary

Setup: for a one-dimensional mixture $F = p_1 \mathcal N(\mu_1,\sigma_1^2) + p_2 \mathcal N(\mu_2,\sigma_2^2),$ the paper studies estimation in parameter distance, with error measured relative to the mixture variance $\sigma^2$ .
Reparameterization: after centering, rewrite the model using parameters $(\alpha,\beta,\gamma)$ that are invariant under adding the same Gaussian noise to both components, and express the informative content of the model through excess moments $X_3,\dots,X_6$ .
Main bounds: in one dimension, $\Theta(\epsilon^{-12}\log(1/\delta))$ samples are necessary and sufficient in the worst case to estimate parameters to additive accuracy on the order of $\epsilon\sigma$ (means) and $\epsilon^2\sigma^2$ (variances); if $|\mu_1-\mu_2|=\Omega(\sigma)$ , the rate improves to $\Theta(\epsilon^{-2}\log(1/\delta))$ .
Higher dimension: the paper reduces the $d$ -dimensional problem to one-dimensional projections with only a provably necessary logarithmic loss in $d$ , so the local geometry of the moment map still controls learnability.

Assumptions And Limits

The scope is the two-component Gaussian case. The results clarify local conditioning and finite-sample behavior, but they do not remove the basic fragility of parameter recovery near degenerate mixtures.

Relevance To This Project

This is one of the most directly relevant mixture papers for the repo because it separates exact identifiability from stable finite-sample recovery. In x -> z -> y, even if latent strategies are theoretically identifiable, the strategy signal can be so weak or nearly overlapping that practical recovery becomes ill-conditioned for finite data.

Comparison Notes

Kalai, Moitra, and Valiant (2010) establish polynomial-time recovery for two Gaussians; Hardt and Price refine the local statistical geometry of that case. Ashtiani et al. (2020) shift attention from parameter recovery to density learning, which can remain far easier than recovering individual components.

Source Note

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

Verified from source: title, authors, arXiv identifier, the noise-invariant $(\alpha,\beta,\gamma)$ reparameterization and excess-moment viewpoint, the worst-case $\Theta(\epsilon^{-12}\log(1/\delta))$ one-dimensional rate, the separated-means $\Theta(\epsilon^{-2}\log(1/\delta))$ regime, and the logarithmic- $d$ dimensional reduction claim were checked against the alphaXiv-extracted paper text.