mlsanityData to 7 Oct 2026

Tight bounds for learning a mixture of two gaussians

arXiv 1404.4997 ↗First posted 19 Apr 2014cs.LG cs.DS stat.MLcited by 29

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 7; 2022: 9; 2023: 4; 2024: 3; 2025: 4; 2026: 2.

29 papers.

Sort:

By area:

  1. 2023Learning Mixtures of Gaussians Using the DDPM Objectivecited by 56
  2. 2021Fair Normalizing Flowscited by 38
  3. 2023Demystifying Softmax Gating Function in Gaussian Mixture of Expertscited by 33
  4. 2021Clustering Mixtures with Almost Optimal Separation in Polynomial Timecited by 28
  5. 2022Continuous LWE is as Hard as LWE & Applications to Learning Gaussian Mixturescited by 26
  6. 2022Refined Convergence Rates for Maximum Likelihood Estimation under Finite Mixture Modelscited by 22
  7. 2021Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimationcited by 21
  8. 2021Learning GMMs with Nearly Optimal Robustness Guaranteescited by 12
  9. 2021Improved Convergence Guarantees for Learning Gaussian Mixture Models by EM and Gradient EMcited by 11
  10. 2022On Learning Mixture of Linear Regressions in the Non-Realizable Settingcited by 10
  11. 2022A Fourier Approach to Mixture Learningcited by 5
  12. 2024Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Modelscited by 5
17 more
  1. 2021Lower Bounds on the Total Variation Distance Between Mixtures of Two Gaussianscited by 4
  2. 2021Robust Model Selection and Nearly-Proper Learning for GMMscited by 3
  3. 2022Tight Bounds on the Hardness of Learning Simple Nonparametric Mixturescited by 3
  4. 2024Learning With Multi-Group Guarantees For Clusterable Subpopulationscited by 3
  5. 2025Nonparametric MLE for Gaussian Location Mixtures: Certified Computation and Generic Behaviorcited by 3
  6. 2022On the Role of Channel Capacity in Learning Gaussian Mixture Modelscited by 2
  7. 2022Support Recovery in Mixture Models with Sparse Parameterscited by 2
  8. 2022On the Semi-supervised Expectation Maximizationcited by 2
  9. 2023Learning Mixtures of Gaussians with Censored Datacited by 2
  10. 2025Dendrograms of Mixing Measures for Softmax-Gated Gaussian Mixture of Experts: Consistency Without Model Sweepscited by 2
  11. 2026Learning Mixture Models via Efficient High-dimensional Sparse Fourier Transformscited by 1
  12. 2022Mean Estimation in High-Dimensional Binary Markov Gaussian Mixture Modelscited by 0
  13. 2023SQ Lower Bounds for Learning Bounded Covariance GMMscited by 0
  14. 2024Model Selection and Parameter Estimation of One-Dimensional Gaussian Mixture Modelscited by 0
  15. 2025On Learning Parallel Pancakes with Mostly Uniform Weightscited by 0
  16. 2025Pair Correlation Factor and the Sample Complexity of Gaussian Mixturescited by 0
  17. 2026Fidelity-Diversity Metrics for Textcited by 0