# Tight bounds for learning a mixture of two gaussians

arXiv: https://arxiv.org/abs/1404.4997 · HTML: https://mlsanity.com/paper/1404.4997/

## Key facts

- Cited by 29 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Apr 2014.

## Built on by (most cited first, 29 of 29)

- [Learning Mixtures of Gaussians Using the DDPM Objective](https://mlsanity.com/paper/2307.01178/) (2023)
- [Fair Normalizing Flows](https://mlsanity.com/paper/2106.05937/) (2021)
- [Demystifying Softmax Gating Function in Gaussian Mixture of Experts](https://mlsanity.com/paper/2305.03288/) (2023)
- [Clustering Mixtures with Almost Optimal Separation in Polynomial Time](https://mlsanity.com/paper/2112.00706/) (2021)
- [Continuous LWE is as Hard as LWE & Applications to Learning Gaussian Mixtures](https://mlsanity.com/paper/2204.02550/) (2022)
- [Refined Convergence Rates for Maximum Likelihood Estimation under Finite Mixture Models](https://mlsanity.com/paper/2202.08786/) (2022)
- [Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation](https://mlsanity.com/paper/2106.08537/) (2021)
- [Learning GMMs with Nearly Optimal Robustness Guarantees](https://mlsanity.com/paper/2104.09665/) (2021)
- [Improved Convergence Guarantees for Learning Gaussian Mixture Models by EM and Gradient EM](https://mlsanity.com/paper/2101.00575/) (2021)
- [On Learning Mixture of Linear Regressions in the Non-Realizable Setting](https://mlsanity.com/paper/2205.13166/) (2022)
- [Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Models](https://mlsanity.com/paper/2411.15669/) (2024)
- [A Fourier Approach to Mixture Learning](https://mlsanity.com/paper/2210.02415/) (2022)
- [Lower Bounds on the Total Variation Distance Between Mixtures of Two Gaussians](https://mlsanity.com/paper/2109.01064/) (2021)
- [Robust Model Selection and Nearly-Proper Learning for GMMs](https://mlsanity.com/paper/2106.02774/) (2021)
- [Tight Bounds on the Hardness of Learning Simple Nonparametric Mixtures](https://mlsanity.com/paper/2203.15150/) (2022)
- [Learning With Multi-Group Guarantees For Clusterable Subpopulations](https://mlsanity.com/paper/2410.14588/) (2024)
- [Nonparametric MLE for Gaussian Location Mixtures: Certified Computation and Generic Behavior](https://mlsanity.com/paper/2503.20193/) (2025)
- [On the Role of Channel Capacity in Learning Gaussian Mixture Models](https://mlsanity.com/paper/2202.07707/) (2022)
- [Support Recovery in Mixture Models with Sparse Parameters](https://mlsanity.com/paper/2202.11940/) (2022)
- [On the Semi-supervised Expectation Maximization](https://mlsanity.com/paper/2211.00537/) (2022)
- [Learning Mixtures of Gaussians with Censored Data](https://mlsanity.com/paper/2305.04127/) (2023)
- [Dendrograms of Mixing Measures for Softmax-Gated Gaussian Mixture of Experts: Consistency Without Model Sweeps](https://mlsanity.com/paper/2510.12744/) (2025)
- [Learning Mixture Models via Efficient High-dimensional Sparse Fourier Transforms](https://mlsanity.com/paper/2601.05157/) (2026)
- [Mean Estimation in High-Dimensional Binary Markov Gaussian Mixture Models](https://mlsanity.com/paper/2206.02455/) (2022)
- [SQ Lower Bounds for Learning Bounded Covariance GMMs](https://mlsanity.com/paper/2306.13057/) (2023)
- [Model Selection and Parameter Estimation of One-Dimensional Gaussian Mixture Models](https://mlsanity.com/paper/2404.12613/) (2024)
- [On Learning Parallel Pancakes with Mostly Uniform Weights](https://mlsanity.com/paper/2504.15251/) (2025)
- [Pair Correlation Factor and the Sample Complexity of Gaussian Mixtures](https://mlsanity.com/paper/2508.03633/) (2025)
- [Fidelity-Diversity Metrics for Text](https://mlsanity.com/paper/2607.04563/) (2026)

## Abstract (arXiv)

We consider the problem of identifying the parameters of an unknown mixture of two arbitrary d-dimensional gaussians from a sequence of independent random samples. Our main results are upper and lower bounds giving a computationally efficient moment-based estimator with an optimal convergence rate, thus resolving a problem introduced by Pearson (1894). Denoting by σ2 the variance of the unknown mixture, we prove that Theta(σ12) samples are necessary and sufficient to estimate each parameter up to constant additive error when d=1. Our upper bound extends to arbitrary dimension d>1 up to a (provably necessary) logarithmic loss in d using a novel---yet simple---dimensionality reduction technique. We further identify several interesting special cases where the sample complexity is notably smaller than our optimal worst-case bound. For instance, if the means of the two components are separated by Omega(σ) the sample complexity reduces to O(σ2) and this is again optimal. Our results also apply to learning each component of the mixture up to small error in total variation distance, where our algorithm gives strong improvements in sample complexity over previous work. We also extend our lower bound to mixtures of k Gaussians, showing that Omega(σ6k-2) samples are necessary to estimate each parameter up to constant additive error.