mlsanityData to 14 Oct 2026

On Learning Mixtures of Well-Separated Gaussians

arXiv 1710.11592 ↗First posted 31 Oct 2017cs.DS cs.LG math.STcited by 30

Not on the map. Why?

Abstract (arXiv)

We consider the problem of efficiently learning mixtures of a large number of spherical Gaussians, when the components of the mixture are well separated. In the most basic form of this problem, we are given samples from a uniform mixture of k standard spherical Gaussians, and the goal is to estimate the means up to accuracy δ using poly(k,d, 1/δ) samples. In this work, we study the following question: what is the minimum separation needed between the means for solving this task? The best known algorithm due to Vempala and Wang [JCSS 2004] requires a separation of roughly mink,d1/4. On the other hand, Moitra and Valiant [FOCS 2010] showed that with separation o(1), exponentially many samples are required. We address the significant gap between these two bounds, by showing the following results. 1. We show that with separation o(√log k), super-polynomially many samples are required. In fact, this holds even when the k means of the Gaussians are picked at random in d=O(log k) dimensions. 2. We show that with separation Omega(√log k), poly(k,d,1/δ) samples suffice. Note that the bound on the separation is independent of δ. This result is based on a new and efficient "accuracy boosting" algorithm that takes as input coarse estimates of the true means and in time poly(k,d, 1/δ) outputs estimates of the means up to arbitrary accuracy δ assuming the separation between the means is Omega(min√log k,√d) (independently of δ). We also present a computationally efficient algorithm in d=O(1) dimensions with only Omega(√d) separation. These results together essentially characterize the optimal order of separation between components that is needed to learn a mixture of k spherical Gaussians with polynomial samples.

Key facts. Cited by 30 papers in the map (data through 14 Oct 2026). First posted on arXiv 31 Oct 2017.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 6; 2022: 7; 2023: 9; 2024: 5; 2025: 0; 2026: 3.

30 papers.

Sort:

By area:

  1. 2023Learning Mixtures of Gaussians Using the DDPM Objectivecited by 57
  2. 2021Clustering Mixtures with Almost Optimal Separation in Polynomial Timecited by 28
  3. 2022Continuous LWE is as Hard as LWE & Applications to Learning Gaussian Mixturescited by 26
  4. 2021Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimationcited by 21
  5. 2023Private estimation algorithms for stochastic block models and mixture modelscited by 21
  6. 2023Polynomial Time and Private Learning of Unbounded Gaussian Mixture Modelscited by 19
  7. 2021Differentially-Private Clustering of Easy Instancescited by 17
  8. 2022List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filteringcited by 13
  9. 2021Improved Convergence Guarantees for Learning Gaussian Mixture Models by EM and Gradient EMcited by 11
  10. 2021SoS Degree Reduction with Applications to Clustering and Robust Moment Estimationcited by 7
  11. 2024Active clustering with bandit feedbackcited by 7
  12. 2024How does promoting the minority fraction affect generalization? A theoretical study of the one-hidden-layer neural network on group imbalancecited by 6
18 more
  1. 2024Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Modelscited by 6
  2. 2021Uniform Consistency in Nonparametric Mixture Modelscited by 5
  3. 2022A Fourier Approach to Mixture Learningcited by 5
  4. 2023Mixtures of Gaussians are Privately Learnable with a Polynomial Number of Samplescited by 5
  5. 2022Sample Complexity Bounds for Learning High-dimensional Simplices in Noisy Regimescited by 4
  6. 2023Adversarially robust clustering with optimality guaranteescited by 4
  7. 2023SQ Lower Bounds for Learning Mixtures of Linear Classifierscited by 4
  8. 2022Tight Bounds on the Hardness of Learning Simple Nonparametric Mixturescited by 3
  9. 2022On the Role of Channel Capacity in Learning Gaussian Mixture Modelscited by 2
  10. 2023Learning Mixtures of Gaussians with Censored Datacited by 2
  11. 2024Robust Mixture Learning when Outliers Overwhelm Small Groupscited by 1
  12. 2026Learning Mixture Models via Efficient High-dimensional Sparse Fourier Transformscited by 1
  13. 2022False membership rate control in mixture modelscited by 0
  14. 2023The Parametric Stability of Well-separated Spherical Gaussian Mixturescited by 0
  15. 2023SQ Lower Bounds for Learning Bounded Covariance GMMscited by 0
  16. 2024Model Selection and Parameter Estimation of One-Dimensional Gaussian Mixture Modelscited by 0
  17. 2026Low-degree Lower bounds for clustering in moderate dimensioncited by 0
  18. 2026Model Selection and Parameter Estimation for Multidimensional Gaussian Mixture Models with a Common Covariance Matrixcited by 0