# Clustering Mixtures with Almost Optimal Separation in Polynomial Time

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

## Key facts

- Cited by 28 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 50 references that are in the map.
- First posted on arXiv 1 Dec 2021.

## Builds on (most cited first, 25 of 25)

- [Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures](https://mlsanity.com/paper/1611.03473/) (2016)
- [Recent Advances in Algorithmic High-Dimensional Robust Statistics](https://mlsanity.com/paper/1911.05911/) (2019)
- [Mixture Models, Robustness, and Sum of Squares Proofs](https://mlsanity.com/paper/1711.07454/) (2017)
- [List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussians](https://mlsanity.com/paper/1711.07211/) (2017)
- [Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent](https://mlsanity.com/paper/2009.06107/) (2020)
- [Ten Steps of EM Suffice for Mixtures of Two Gaussians](https://mlsanity.com/paper/1609.00368/) (2016)
- [Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors](https://mlsanity.com/paper/1512.02337/) (2015)
- [Global analysis of Expectation Maximization for mixtures of two Gaussians](https://mlsanity.com/paper/1608.07630/) (2016)
- [On Learning Mixtures of Well-Separated Gaussians](https://mlsanity.com/paper/1710.11592/) (2017)
- [Tight bounds for learning a mixture of two gaussians](https://mlsanity.com/paper/1404.4997/) (2014)
- [Learning Mixtures of Gaussians in High Dimensions](https://mlsanity.com/paper/1503.00424/) (2015)
- [Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models](https://mlsanity.com/paper/2012.07774/) (2020)
- [Near-optimal-sample estimators for spherical Gaussian mixtures](https://mlsanity.com/paper/1402.4746/) (2014)
- [Polynomial-time Tensor Decompositions with Sum-of-Squares](https://mlsanity.com/paper/1610.01980/) (2016)
- [Faster and Sample Near-Optimal Algorithms for Proper Learning Mixtures of Gaussians](https://mlsanity.com/paper/1312.1054/) (2013)
- [Smoothed Analysis of Tensor Decompositions](https://mlsanity.com/paper/1311.3651/) (2013)
- [Clustering subgaussian mixtures by semidefinite programming](https://mlsanity.com/paper/1602.06612/) (2016)
- [The More, the Merrier: the Blessing of Dimensionality for Learning Large Gaussian Mixtures](https://mlsanity.com/paper/1311.2891/) (2013)
- [Sample-Optimal Density Estimation in Nearly-Linear Time](https://mlsanity.com/paper/1506.00671/) (2015)
- [Robust Learning of Mixtures of Gaussians](https://mlsanity.com/paper/2007.05912/) (2020)
- [Fast and robust tensor decomposition with applications to dictionary learning](https://mlsanity.com/paper/1706.08672/) (2017)
- [Near-Optimal Density Estimation in Near-Linear Time Using Variable-Width Histograms](https://mlsanity.com/paper/1411.0169/) (2014)
- [Strongly Refuting Random CSPs Below the Spectral Threshold](https://mlsanity.com/paper/1605.00058/) (2016)
- [SoS Degree Reduction with Applications to Clustering and Robust Moment Estimation](https://mlsanity.com/paper/2101.01509/) (2021)
- [Sparse Solutions to Nonnegative Linear Systems and Applications](https://mlsanity.com/paper/1501.01689/) (2015)

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

- [Learning Mixtures of Gaussians Using the DDPM Objective](https://mlsanity.com/paper/2307.01178/) (2023)
- [Dimension-Free Convergence of Diffusion Models for Approximate Gaussian Mixtures](https://mlsanity.com/paper/2504.05300/) (2025)
- [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)
- [Active clustering with bandit feedback](https://mlsanity.com/paper/2406.11485/) (2024)
- [High-accuracy and dimension-free sampling with diffusions](https://mlsanity.com/paper/2601.10708/) (2026)
- [Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Models](https://mlsanity.com/paper/2411.15669/) (2024)
- [Efficient Multivariate Robust Mean Estimation Under Mean-Shift Contamination](https://mlsanity.com/paper/2502.14772/) (2025)
- [Beyond Parallel Pancakes: Quasi-Polynomial Time Guarantees for Non-Spherical Gaussian Mixtures](https://mlsanity.com/paper/2112.05445/) (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)
- [Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor Decompositions](https://mlsanity.com/paper/2207.07417/) (2022)
- [Sample Complexity Bounds for Learning High-dimensional Simplices in Noisy Regimes](https://mlsanity.com/paper/2209.05953/) (2022)
- [Efficient Certificates of Anti-Concentration Beyond Gaussians](https://mlsanity.com/paper/2405.15084/) (2024)
- [Clustering Mixtures of Bounded Covariance Distributions Under Optimal Separation](https://mlsanity.com/paper/2312.11769/) (2023)
- [Entangled Mean Estimation in High-Dimensions](https://mlsanity.com/paper/2501.05425/) (2025)
- [Convergence Dynamics of Over-Parameterized Score Matching for a Single Gaussian](https://mlsanity.com/paper/2511.22069/) (2025)
- [Provably Learning from Modern Language Models via Low Logit Rank](https://mlsanity.com/paper/2512.09892/) (2025)
- [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)
- [Efficient and Noise-Tolerant PAC Learning of Multiclass Linear Classifiers](https://mlsanity.com/paper/2605.18662/) (2026)
- [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)
- [Sample-Efficient Private Learning of Mixtures of Gaussians](https://mlsanity.com/paper/2411.02298/) (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)
- [Mixtures Closest to a Given Measure: A Semidefinite Programming Approach](https://mlsanity.com/paper/2509.22879/) (2025)
- [Low-degree Lower bounds for clustering in moderate dimension](https://mlsanity.com/paper/2602.23023/) (2026)

## Abstract (arXiv)

We consider the problem of clustering mixtures of mean-separated Gaussians in high dimensions. We are given samples from a mixture of k identity covariance Gaussians, so that the minimum pairwise distance between any two pairs of means is at least Delta, for some parameter Delta > 0, and the goal is to recover the ground truth clustering of these samples. It is folklore that separation Delta = Theta (√log k) is both necessary and sufficient to recover a good clustering, at least information theoretically. However, the estimators which achieve this guarantee are inefficient. We give the first algorithm which runs in polynomial time, and which almost matches this guarantee. More precisely, we give an algorithm which takes polynomially many samples and time, and which can successfully recover a good clustering, so long as the separation is Delta = Omega (log1/2 + c k), for any c > 0. Previously, polynomial time algorithms were only known for this problem when the separation was polynomial in k, and all algorithms which could tolerate textsfpoly( log k ) separation required quasipolynomial time. We also extend our result to mixtures of translations of a distribution which satisfies the Poincar'e inequality, under additional mild assumptions. Our main technical tool, which we believe is of independent interest, is a novel way to implicitly represent and estimate high degree moments of a distribution, which allows us to extract important information about high-degree moments without ever writing down the full moment tensors explicitly.