mlsanityData to 14 Oct 2026

Mixtures of Gaussians are Privately Learnable with a Polynomial Number of Samples

arXiv 2309.03847 ↗First posted 7 Sep 2023stat.ML cs.CR cs.DScited by 5

Not on the map. Why?

Abstract (arXiv)

We study the problem of estimating mixtures of Gaussians under the constraint of differential privacy (DP). Our main result is that poly(k,d,1/α,1/varepsilon,log(1/δ)) samples are sufficient to estimate a mixture of k Gaussians in ℝd up to total variation distance α while satisfying (varepsilon, δ)-DP. This is the first finite sample complexity upper bound for the problem that does not make any structural assumptions on the GMMs. To solve the problem, we devise a new framework which may be useful for other tasks. On a high level, we show that if a class of distributions (such as Gaussians) is (1) list decodable and (2) admits a "locally small'' cover (Bun et al., 2021) with respect to total variation distance, then the class of its mixtures is privately learnable. The proof circumvents a known barrier indicating that, unlike Gaussians, GMMs do not admit a locally small cover (Aden-Ali et al., 2021b).

Key facts. Cited by 5 papers in the map (data through 14 Oct 2026). Builds on 44 of its 77 references that are in the map. First posted on arXiv 7 Sep 2023.

Builds on

44 of 77 references.

References · 44

  1. 2016Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixturescited by 115
  2. 2017Finite Sample Differentially Private Confidence Intervalscited by 104
  3. 2018Privately Learning High-Dimensional Distributionscited by 104
  4. 2017Mixture Models, Robustness, and Sum of Squares Proofscited by 81
  5. 2018Private PAC learning implies finite Littlestone dimensioncited by 74
  6. 2020CoinPress: Practical Private Mean and Covariance Estimationcited by 74
  7. 2021Robust and Differentially Private Mean Estimationcited by 66
  8. 2020An Equivalence Between Private Classification and Online Predictioncited by 64
  9. 2021Differential privacy and robust statistics in high dimensionscited by 64
  10. 2015Differentially Private Release and Learning of Threshold Functionscited by 60
  11. 2019Private Hypothesis Selectioncited by 60
  12. 2020Differentially Private Assouad, Fano, and Le Camcited by 55
32 more
  1. 2021Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanismcited by 50
  2. 2022Robustness Implies Privacy in Statistical Estimationcited by 47
  3. 2021Covariance-Aware Private Mean Estimation Without Private Covariance Estimationcited by 46
  4. 2020On the Sample Complexity of Privately Learning Unbounded High-Dimensional Gaussianscited by 41
  5. 2021Private and polynomial time algorithms for learning Gaussians and beyondcited by 39
  6. 2021Private Robust Estimation by Stabilizing Convex Relaxationscited by 38
  7. 2015Simultaneous Private Learning of Multiple Conceptscited by 34
  8. 2021FriendlyCore: Practical Differentially Private Aggregationcited by 34
  9. 2021A Private and Computationally-Efficient Estimator for Unbounded Gaussianscited by 34
  10. 2022New Lower Bounds for Private Estimation and a Generalized Fingerprinting Lemmacited by 33
  11. 2020Settling the Robust Learnability of Mixtures of Gaussianscited by 32
  12. 2022Private Estimation with Public Datacited by 32
  13. 2019Privately Learning Thresholds: Closing the Exponential Gapcited by 31
  14. 2017On Learning Mixtures of Well-Separated Gaussianscited by 30
  15. 2021Clustering Mixtures with Almost Optimal Separation in Polynomial Timecited by 28
  16. 2019Differentially Private Algorithms for Learning Mixtures of Separated Gaussianscited by 27
  17. 2023From Robustness to Privacy and Backcited by 27
  18. 2022Privacy Induces Robustness: Information-Computation Gaps and Sparse Mean Estimationcited by 25
  19. 2023Fast, Sample-Efficient, Affine-Invariant Private Mean and Covariance Estimation for Subgaussian Distributionscited by 22
  20. 2023Private estimation algorithms for stochastic block models and mixture modelscited by 21
  21. 2023Polynomial Time and Private Learning of Unbounded Gaussian Mixture Modelscited by 19
  22. 2013The More, the Merrier: the Blessing of Dimensionality for Learning Large Gaussian Mixturescited by 18
  23. 2022~Optimal Differentially Private Learning of Thresholds and Quasi-Concave Optimizationcited by 18
  24. 2021Differentially-Private Clustering of Easy Instancescited by 17
  25. 2015Sample-Optimal Density Estimation in Nearly-Linear Timecited by 16
  26. 2023Private Distribution Learning with Public Data: The View from Sample Compressioncited by 14
  27. 2021Privately Learning Mixtures of Axis-Aligned Gaussianscited by 13
  28. 2021Learning GMMs with Nearly Optimal Robustness Guaranteescited by 12
  29. 2023A Fast Algorithm for Adaptive Private Mean Estimationcited by 11
  30. 2017Sample-Efficient Learning of Mixturescited by 9
  31. 2018Some techniques in density estimationcited by 4
  32. 2021Robust Model Selection and Nearly-Proper Learning for GMMscited by 3

Built on by

Cited by year

Citing papers per year: 2023: 1; 2024: 3; 2025: 1.

5 papers.

  1. 2023Sample-Optimal Locally Private Hypothesis Selection and the Provable Benefits of Interactivitycited by 3
  2. 2024Not All Learnable Distribution Classes are Privately Learnablecited by 3
  3. 2024Agnostic Private Density Estimation for GMMs via List Global Stabilitycited by 2
  4. 2024Sample-Efficient Private Learning of Mixtures of Gaussianscited by 0
  5. 2025Robust Learnability of Sample-Compressible Distributions under Noisy or Adversarial Perturbationscited by 0