mlsanityData to 7 Oct 2026

Learning GMMs with Nearly Optimal Robustness Guarantees

arXiv 2104.09665 ↗First posted 19 Apr 2021cs.LG cs.DS math.STcited by 12

Not on the map. Why?

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.

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

Builds on

21 of 52 references.

References · 21

  1. 2016Robust Estimators in High Dimensions without the Computational Intractabilitycited by 209
  2. 2016Agnostic Estimation of Mean and Covariancecited by 131
  3. 2018Sever: A Robust Meta-Algorithm for Stochastic Optimizationcited by 123
  4. 2016Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixturescited by 114
  5. 2019Recent Advances in Algorithmic High-Dimensional Robust Statisticscited by 100
  6. 2016Learning from Untrusted Datacited by 90
  7. 2017Being Robust (in High Dimensions) Can Be Practicalcited by 83
  8. 2017Mixture Models, Robustness, and Sum of Squares Proofscited by 81
  9. 2018Efficient Algorithms for Outlier-Robust Regressioncited by 72
  10. 2020Outlier Robust Mean Estimation with Subgaussian Rates via Stabilitycited by 50
  11. 2020Robust Linear Regression: Optimal Rates in Polynomial Timecited by 42
  12. 2017Robustly Learning a Gaussian: Getting Optimal Error, Efficientlycited by 39
9 more
  1. 2020Settling the Robust Learnability of Mixtures of Gaussianscited by 32
  2. 2014Tight bounds for learning a mixture of two gaussianscited by 29
  3. 2015Learning Mixtures of Gaussians in High Dimensionscited by 29
  4. 2020Robustly Learning any Clusterable Mixture of Gaussianscited by 28
  5. 2020Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contaminationcited by 26
  6. 2020Outlier-Robust Clustering of Non-Spherical Mixturescited by 19
  7. 2019How Hard Is Robust Mean Estimation?cited by 16
  8. 2020Robust Learning of Mixtures of Gaussianscited by 15
  9. 2017Sample-Efficient Learning of Mixturescited by 9

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 2; 2022: 1; 2023: 3; 2024: 2; 2025: 3; 2026: 1.

12 papers.

  1. 2023Polynomial Time and Private Learning of Unbounded Gaussian Mixture Modelscited by 19
  2. 2022Minimax Rates for Robust Community Detectioncited by 12
  3. 2023Mixtures of Gaussians are Privately Learnable with a Polynomial Number of Samplescited by 5
  4. 2024Distribution Learnability and Robustnesscited by 4
  5. 2021Robust Model Selection and Nearly-Proper Learning for GMMscited by 3
  6. 2025Nonparametric MLE for Gaussian Location Mixtures: Certified Computation and Generic Behaviorcited by 3
  7. 2021Robust Voting Rules from Algorithmic Robust Statisticscited by 1
  8. 2023A Spectral Algorithm for List-Decodable Covariance Estimation in Relative Frobenius Normcited by 1
  9. 2024Factor Adjusted Spectral Clustering for Mixture Modelscited by 1
  10. 2025On the Learnability of Distribution Classes with Adaptive Adversariescited by 1
  11. 2026Learning Mixture Models via Efficient High-dimensional Sparse Fourier Transformscited by 1
  12. 2025On Learning Parallel Pancakes with Mostly Uniform Weightscited by 0