# Learning GMMs with Nearly Optimal Robustness Guarantees

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 52 references that are in the map.
- First posted on arXiv 19 Apr 2021.

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

- [Robust Estimators in High Dimensions without the Computational Intractability](https://mlsanity.com/paper/1604.06443/) (2016)
- [Agnostic Estimation of Mean and Covariance](https://mlsanity.com/paper/1604.06968/) (2016)
- [Sever: A Robust Meta-Algorithm for Stochastic Optimization](https://mlsanity.com/paper/1803.02815/) (2018)
- [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)
- [Learning from Untrusted Data](https://mlsanity.com/paper/1611.02315/) (2016)
- [Being Robust (in High Dimensions) Can Be Practical](https://mlsanity.com/paper/1703.00893/) (2017)
- [Mixture Models, Robustness, and Sum of Squares Proofs](https://mlsanity.com/paper/1711.07454/) (2017)
- [Efficient Algorithms for Outlier-Robust Regression](https://mlsanity.com/paper/1803.03241/) (2018)
- [Outlier Robust Mean Estimation with Subgaussian Rates via Stability](https://mlsanity.com/paper/2007.15618/) (2020)
- [Robust Linear Regression: Optimal Rates in Polynomial Time](https://mlsanity.com/paper/2007.01394/) (2020)
- [Robustly Learning a Gaussian: Getting Optimal Error, Efficiently](https://mlsanity.com/paper/1704.03866/) (2017)
- [Settling the Robust Learnability of Mixtures of Gaussians](https://mlsanity.com/paper/2011.03622/) (2020)
- [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)
- [Robustly Learning any Clusterable Mixture of Gaussians](https://mlsanity.com/paper/2005.06417/) (2020)
- [Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contamination](https://mlsanity.com/paper/2010.04157/) (2020)
- [Outlier-Robust Clustering of Non-Spherical Mixtures](https://mlsanity.com/paper/2005.02970/) (2020)
- [How Hard Is Robust Mean Estimation?](https://mlsanity.com/paper/1903.07870/) (2019)
- [Robust Learning of Mixtures of Gaussians](https://mlsanity.com/paper/2007.05912/) (2020)
- [Sample-Efficient Learning of Mixtures](https://mlsanity.com/paper/1706.01596/) (2017)

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

- [Polynomial Time and Private Learning of Unbounded Gaussian Mixture Models](https://mlsanity.com/paper/2303.04288/) (2023)
- [Minimax Rates for Robust Community Detection](https://mlsanity.com/paper/2207.11903/) (2022)
- [Mixtures of Gaussians are Privately Learnable with a Polynomial Number of Samples](https://mlsanity.com/paper/2309.03847/) (2023)
- [Distribution Learnability and Robustness](https://mlsanity.com/paper/2406.17814/) (2024)
- [Robust Model Selection and Nearly-Proper Learning for GMMs](https://mlsanity.com/paper/2106.02774/) (2021)
- [Nonparametric MLE for Gaussian Location Mixtures: Certified Computation and Generic Behavior](https://mlsanity.com/paper/2503.20193/) (2025)
- [Robust Voting Rules from Algorithmic Robust Statistics](https://mlsanity.com/paper/2112.06380/) (2021)
- [A Spectral Algorithm for List-Decodable Covariance Estimation in Relative Frobenius Norm](https://mlsanity.com/paper/2305.00966/) (2023)
- [Factor Adjusted Spectral Clustering for Mixture Models](https://mlsanity.com/paper/2408.12564/) (2024)
- [On the Learnability of Distribution Classes with Adaptive Adversaries](https://mlsanity.com/paper/2509.05137/) (2025)
- [Learning Mixture Models via Efficient High-dimensional Sparse Fourier Transforms](https://mlsanity.com/paper/2601.05157/) (2026)
- [On Learning Parallel Pancakes with Mostly Uniform Weights](https://mlsanity.com/paper/2504.15251/) (2025)

## Abstract (arXiv)

In this work we solve the problem of robustly learning a high-dimensional Gaussian mixture model with k components from ε-corrupted samples up to accuracy widetildeO(ε) in total variation distance for any constant k and with mild assumptions on the mixture. This robustness guarantee is optimal up to polylogarithmic factors. The main challenge is that most earlier works rely on learning individual components in the mixture, but this is impossible in our setting, at least for the types of strong robustness guarantees we are aiming for. Instead we introduce a new framework which we call em strong observability that gives us a route to circumvent this obstacle.