mlsanityData to 7 Oct 2026

Settling the Robust Learnability of Mixtures of Gaussians

arXiv 2011.03622 ↗First posted 6 Nov 2020cs.DS cs.LG math.STcited by 32

Not on the map. Why?

Abstract (arXiv)

This work represents a natural coalescence of two important lines of work: learning mixtures of Gaussians and algorithmic robust statistics. In particular we give the first provably robust algorithm for learning mixtures of any constant number of Gaussians. We require only mild assumptions on the mixing weights (bounded fractionality) and that the total variation distance between components is bounded away from zero. At the heart of our algorithm is a new method for proving dimension-independent polynomial identifiability through applying a carefully chosen sequence of differential operations to certain generating functions that not only encode the parameters we would like to learn but also the system of polynomial equations we would like to solve. We show how the symbolic identities we derive can be directly used to analyze a natural sum-of-squares relaxation.

Key facts. Cited by 32 papers in the map (data through 7 Oct 2026). First posted on arXiv 6 Nov 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 7; 2022: 5; 2023: 11; 2024: 6; 2025: 2; 2026: 1.

32 papers.

Sort:

  1. 2022Robust Sparse Mean Estimation via Sum of Squarescited by 23
  2. 2021Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimationcited by 21
  3. 2022Streaming Algorithms for High-Dimensional Robust Statisticscited by 21
  4. 2023Learning quantum Hamiltonians at any temperature in polynomial timecited by 20
  5. 2023Polynomial Time and Private Learning of Unbounded Gaussian Mixture Modelscited by 19
  6. 2021Outlier-Robust Learning of Ising Models Under Dobrushin's Conditioncited by 14
  7. 2021Learning GMMs with Nearly Optimal Robustness Guaranteescited by 12
  8. 2022Minimax Rates for Robust Community Detectioncited by 12
  9. 2023Nearly-Linear Time and Streaming Algorithms for Outlier-Robust PCAcited by 10
  10. 2022List-Decodable Covariance Estimationcited by 8
  11. 2021Kalman Filtering with Adversarial Corruptionscited by 6
  12. 2021Beyond Parallel Pancakes: Quasi-Polynomial Time Guarantees for Non-Spherical Gaussian Mixturescited by 5
20 more
  1. 2023Mixtures of Gaussians are Privately Learnable with a Polynomial Number of Samplescited by 5
  2. 2023Beyond Moments: Robustly Learning Affine Transformations with Asymptotically Optimal Errorcited by 4
  3. 2023SQ Lower Bounds for Learning Mixtures of Linear Classifierscited by 4
  4. 2024Efficient Certificates of Anti-Concentration Beyond Gaussianscited by 4
  5. 2024Distribution Learnability and Robustnesscited by 4
  6. 2021Robust Model Selection and Nearly-Proper Learning for GMMscited by 3
  7. 2022Efficient Algorithms for Sparse Moment Problems without Separationcited by 3
  8. 2023Online Robust Mean Estimationcited by 3
  9. 2023Clustering Mixtures of Bounded Covariance Distributions Under Optimal Separationcited by 3
  10. 2021Robust Voting Rules from Algorithmic Robust Statisticscited by 1
  11. 2023A Spectral Algorithm for List-Decodable Covariance Estimation in Relative Frobenius Normcited by 1
  12. 2024Robust Mixture Learning when Outliers Overwhelm Small Groupscited by 1
  13. 2024Factor Adjusted Spectral Clustering for Mixture Modelscited by 1
  14. 2025On the Learnability of Distribution Classes with Adaptive Adversariescited by 1
  15. 2026Learning Mixture Models via Efficient High-dimensional Sparse Fourier Transformscited by 1
  16. 2023The Parametric Stability of Well-separated Spherical Gaussian Mixturescited by 0
  17. 2023SQ Lower Bounds for Learning Bounded Covariance GMMscited by 0
  18. 2024Untangling Gaussian Mixturescited by 0
  19. 2024Sample-Efficient Private Learning of Mixtures of Gaussianscited by 0
  20. 2025On Learning Parallel Pancakes with Mostly Uniform Weightscited by 0