# Mixture Models, Robustness, and Sum of Squares Proofs

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

## Key facts

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

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

- [Robust and Differentially Private Mean Estimation](https://mlsanity.com/paper/2102.09159/) (2021)
- [Learning Mixtures of Gaussians Using the DDPM Objective](https://mlsanity.com/paper/2307.01178/) (2023)
- [Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanism](https://mlsanity.com/paper/2111.12981/) (2021)
- [Robustness Implies Privacy in Statistical Estimation](https://mlsanity.com/paper/2212.05015/) (2022)
- [Private Robust Estimation by Stabilizing Convex Relaxations](https://mlsanity.com/paper/2112.03548/) (2021)
- [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)
- [Robust Sparse Mean Estimation via Sum of Squares](https://mlsanity.com/paper/2206.03441/) (2022)
- [A New Approach to Learning Linear Dynamical Systems](https://mlsanity.com/paper/2301.09519/) (2023)
- [Learning quantum Hamiltonians at any temperature in polynomial time](https://mlsanity.com/paper/2310.02243/) (2023)
- [Dimension-Free Convergence of Diffusion Models for Approximate Gaussian Mixtures](https://mlsanity.com/paper/2504.05300/) (2025)
- [Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation](https://mlsanity.com/paper/2106.08537/) (2021)
- [Streaming Algorithms for High-Dimensional Robust Statistics](https://mlsanity.com/paper/2204.12399/) (2022)
- [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)
- [Outlier-Robust Learning of Ising Models Under Dobrushin's Condition](https://mlsanity.com/paper/2102.02171/) (2021)
- [Learning GMMs with Nearly Optimal Robustness Guarantees](https://mlsanity.com/paper/2104.09665/) (2021)
- [Minimax Rates for Robust Community Detection](https://mlsanity.com/paper/2207.11903/) (2022)
- [Estimation Contracts for Outlier-Robust Geometric Perception](https://mlsanity.com/paper/2208.10521/) (2022)
- [Learning a Latent Simplex in Input-Sparsity Time](https://mlsanity.com/paper/2105.08005/) (2021)
- [Robust Nonparametric Regression under Poisoning Attack](https://mlsanity.com/paper/2305.16771/) (2023)
- [On Learning Mixture of Linear Regressions in the Non-Realizable Setting](https://mlsanity.com/paper/2205.13166/) (2022)
- [Nearly-Linear Time and Streaming Algorithms for Outlier-Robust PCA](https://mlsanity.com/paper/2305.02544/) (2023)
- [SoS Certifiability of Subgaussian Distributions and its Algorithmic Applications](https://mlsanity.com/paper/2410.21194/) (2024)
- [Robust Estimation for Random Graphs](https://mlsanity.com/paper/2111.05320/) (2021)
- [List-Decodable Covariance Estimation](https://mlsanity.com/paper/2206.10942/) (2022)
- [The Power of Iterative Filtering for Supervised Learning with (Heavy) Contamination](https://mlsanity.com/paper/2505.20177/) (2025)
- [SoS Degree Reduction with Applications to Clustering and Robust Moment Estimation](https://mlsanity.com/paper/2101.01509/) (2021)
- [Spectral clustering in the Gaussian mixture block model](https://mlsanity.com/paper/2305.00979/) (2023)

## Abstract (arXiv)

We use the Sum of Squares method to develop new efficient algorithms for learning well-separated mixtures of Gaussians and robust mean estimation, both in high dimensions, that substantially improve upon the statistical guarantees achieved by previous efficient algorithms. Firstly, we study mixtures of k distributions in d dimensions, where the means of every pair of distributions are separated by at least kvarepsilon. In the special case of spherical Gaussian mixtures, we give a (dk)O(1/varepsilon2)-time algorithm that learns the means assuming separation at least kvarepsilon, for any varepsilon > 0. This is the first algorithm to improve on greedy ("single-linkage") and spectral clustering, breaking a long-standing barrier for efficient algorithms at separation k1/4. We also study robust estimation. When an unknown (1-varepsilon)-fraction of X1,ldots,Xn are chosen from a sub-Gaussian distribution with mean μ but the remaining points are chosen adversarially, we give an algorithm recovering μ to error varepsilon1-1/t in time dO(t2), so long as sub-Gaussian-ness up to O(t) moments can be certified by a Sum of Squares proof. This is the first polynomial-time algorithm with guarantees approaching the information-theoretic limit for non-Gaussian distributions. Previous algorithms could not achieve error better than varepsilon1/2. Both of these results are based on a unified technique. Inspired by recent algorithms of Diakonikolas et al. in robust statistics, we devise an SDP based on the Sum of Squares method for the following setting: given X1,ldots,Xn ∈ ℝd for large d and n = poly(d) with the promise that a subset of X1,ldots,Xn were sampled from a probability distribution with bounded moments, recover some information about that distribution.