# On Learning Mixtures of Well-Separated Gaussians

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

## Key facts

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

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

- [Learning Mixtures of Gaussians Using the DDPM Objective](https://mlsanity.com/paper/2307.01178/) (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)
- [Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation](https://mlsanity.com/paper/2106.08537/) (2021)
- [Private estimation algorithms for stochastic block models and mixture models](https://mlsanity.com/paper/2301.04822/) (2023)
- [Polynomial Time and Private Learning of Unbounded Gaussian Mixture Models](https://mlsanity.com/paper/2303.04288/) (2023)
- [Differentially-Private Clustering of Easy Instances](https://mlsanity.com/paper/2112.14445/) (2021)
- [List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filtering](https://mlsanity.com/paper/2206.05245/) (2022)
- [Improved Convergence Guarantees for Learning Gaussian Mixture Models by EM and Gradient EM](https://mlsanity.com/paper/2101.00575/) (2021)
- [SoS Degree Reduction with Applications to Clustering and Robust Moment Estimation](https://mlsanity.com/paper/2101.01509/) (2021)
- [Active clustering with bandit feedback](https://mlsanity.com/paper/2406.11485/) (2024)
- [How does promoting the minority fraction affect generalization? A theoretical study of the one-hidden-layer neural network on group imbalance](https://mlsanity.com/paper/2403.07310/) (2024)
- [Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Models](https://mlsanity.com/paper/2411.15669/) (2024)
- [Uniform Consistency in Nonparametric Mixture Models](https://mlsanity.com/paper/2108.14003/) (2021)
- [A Fourier Approach to Mixture Learning](https://mlsanity.com/paper/2210.02415/) (2022)
- [Mixtures of Gaussians are Privately Learnable with a Polynomial Number of Samples](https://mlsanity.com/paper/2309.03847/) (2023)
- [Sample Complexity Bounds for Learning High-dimensional Simplices in Noisy Regimes](https://mlsanity.com/paper/2209.05953/) (2022)
- [Adversarially robust clustering with optimality guarantees](https://mlsanity.com/paper/2306.09977/) (2023)
- [SQ Lower Bounds for Learning Mixtures of Linear Classifiers](https://mlsanity.com/paper/2310.11876/) (2023)
- [Tight Bounds on the Hardness of Learning Simple Nonparametric Mixtures](https://mlsanity.com/paper/2203.15150/) (2022)
- [On the Role of Channel Capacity in Learning Gaussian Mixture Models](https://mlsanity.com/paper/2202.07707/) (2022)
- [Learning Mixtures of Gaussians with Censored Data](https://mlsanity.com/paper/2305.04127/) (2023)
- [Robust Mixture Learning when Outliers Overwhelm Small Groups](https://mlsanity.com/paper/2407.15792/) (2024)
- [Learning Mixture Models via Efficient High-dimensional Sparse Fourier Transforms](https://mlsanity.com/paper/2601.05157/) (2026)
- [False membership rate control in mixture models](https://mlsanity.com/paper/2203.02597/) (2022)
- [The Parametric Stability of Well-separated Spherical Gaussian Mixtures](https://mlsanity.com/paper/2302.00242/) (2023)
- [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)
- [Low-degree Lower bounds for clustering in moderate dimension](https://mlsanity.com/paper/2602.23023/) (2026)
- [Model Selection and Parameter Estimation for Multidimensional Gaussian Mixture Models with a Common Covariance Matrix](https://mlsanity.com/paper/2603.19657/) (2026)

## 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.