mlsanityData to 7 Oct 2026

Polynomial Time and Private Learning of Unbounded Gaussian Mixture Models

arXiv 2303.04288 ↗First posted 7 Mar 2023stat.ML cs.CR cs.DScited by 19

Not on the map. Why?

Abstract (arXiv)

We study the problem of privately estimating the parameters of d-dimensional Gaussian Mixture Models (GMMs) with k components. For this, we develop a technique to reduce the problem to its non-private counterpart. This allows us to privatize existing non-private algorithms in a blackbox manner, while incurring only a small overhead in the sample complexity and running time. As the main application of our framework, we develop an (varepsilon, δ)-differentially private algorithm to learn GMMs using the non-private algorithm of Moitra and Valiant [MV10] as a blackbox. Consequently, this gives the first sample complexity upper bound and first polynomial time algorithm for privately learning GMMs without any boundedness assumptions on the parameters. As part of our analysis, we prove a tight (up to a constant factor) lower bound on the total variation distance of high-dimensional Gaussians which can be of independent interest.

Key facts. Cited by 19 papers in the map (data through 7 Oct 2026). Builds on 35 of its 69 references that are in the map. First posted on arXiv 7 Mar 2023.

Builds on

35 of 69 references.

References · 35

  1. 2016Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixturescited by 114
  2. 2017Finite Sample Differentially Private Confidence Intervalscited by 103
  3. 2018Privately Learning High-Dimensional Distributionscited by 103
  4. 2017Mixture Models, Robustness, and Sum of Squares Proofscited by 81
  5. 2020CoinPress: Practical Private Mean and Covariance Estimationcited by 74
  6. 2021Robust and Differentially Private Mean Estimationcited by 66
  7. 2021Differential privacy and robust statistics in high dimensionscited by 64
  8. 2019Private Hypothesis Selectioncited by 60
  9. 2020Differentially Private Assouad, Fano, and Le Camcited by 54
  10. 2021Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanismcited by 50
  11. 2022Robustness Implies Privacy in Statistical Estimationcited by 47
  12. 2021Covariance-Aware Private Mean Estimation Without Private Covariance Estimationcited by 46
23 more
  1. 2020On the Sample Complexity of Privately Learning Unbounded High-Dimensional Gaussianscited by 41
  2. 2021Private and polynomial time algorithms for learning Gaussians and beyondcited by 39
  3. 2021Private Robust Estimation by Stabilizing Convex Relaxationscited by 38
  4. 2021FriendlyCore: Practical Differentially Private Aggregationcited by 34
  5. 2021A Private and Computationally-Efficient Estimator for Unbounded Gaussianscited by 34
  6. 2020Settling the Robust Learnability of Mixtures of Gaussianscited by 32
  7. 2022New Lower Bounds for Private Estimation and a Generalized Fingerprinting Lemmacited by 32
  8. 2022Private Estimation with Public Datacited by 31
  9. 2017On Learning Mixtures of Well-Separated Gaussianscited by 30
  10. 2021Clustering Mixtures with Almost Optimal Separation in Polynomial Timecited by 28
  11. 2019Differentially Private Algorithms for Learning Mixtures of Separated Gaussianscited by 27
  12. 2023From Robustness to Privacy and Backcited by 27
  13. 2022Privacy Induces Robustness: Information-Computation Gaps and Sparse Mean Estimationcited by 25
  14. 2023Private estimation algorithms for stochastic block models and mixture modelscited by 21
  15. 2013The More, the Merrier: the Blessing of Dimensionality for Learning Large Gaussian Mixturescited by 18
  16. 2021Differentially-Private Clustering of Easy Instancescited by 17
  17. 2015Sample-Optimal Density Estimation in Nearly-Linear Timecited by 16
  18. 2021Privately Learning Mixtures of Axis-Aligned Gaussianscited by 13
  19. 2021Learning GMMs with Nearly Optimal Robustness Guaranteescited by 12
  20. 2023A Fast Algorithm for Adaptive Private Mean Estimationcited by 11
  21. 2017Sample-Efficient Learning of Mixturescited by 9
  22. 2018Privacy and Utility Tradeoff in Approximate Differential Privacycited by 3
  23. 2021Robust Model Selection and Nearly-Proper Learning for GMMscited by 3

Built on by

Cited by year

Citing papers per year: 2023: 5; 2024: 6; 2025: 8.

19 papers.

Sort:

By area:

  1. 2025Does Generation Require Memorization? Creative Diffusion Models using Ambient Diffusioncited by 17
  2. 2023Private Distribution Learning with Public Data: The View from Sample Compressioncited by 14
  3. 2024Lower Bounds for Private Estimation of Gaussian Covariance Matrices under All Reasonable Parameter Regimescited by 9
  4. 2023Mixtures of Gaussians are Privately Learnable with a Polynomial Number of Samplescited by 5
  5. 2023Sample-Optimal Locally Private Hypothesis Selection and the Provable Benefits of Interactivitycited by 3
  6. 2024Not All Learnable Distribution Classes are Privately Learnablecited by 3
  7. 2024Privacy of SGD under Gaussian or Heavy-Tailed Noise: Guarantees without Gradient Clippingcited by 3
  8. 2024Learning With Multi-Group Guarantees For Clusterable Subpopulationscited by 3
  9. 2024Agnostic Private Density Estimation for GMMs via List Global Stabilitycited by 2
  10. 2025Approximating the total variation distance between spin systemscited by 2
  11. 2023Label Differential Privacy via Aggregationcited by 1
  12. 2025Approximating the Total Variation Distance between Gaussianscited by 1
7 more
  1. 2025Optimal Bounds for Tyler's M-Estimator for Elliptical Distributionscited by 1
  2. 2023The Normal Distributions Indistinguishability Spectrum and its Application to Privacy-Preserving Machine Learningcited by 0
  3. 2024Sample-Efficient Private Learning of Mixtures of Gaussianscited by 0
  4. 2025On Theoretical Limits of Learning with Label Differential Privacycited by 0
  5. 2025Robust Learnability of Sample-Compressible Distributions under Noisy or Adversarial Perturbationscited by 0
  6. 2025Private Training & Data Generation by Clustering Embeddingscited by 0
  7. 2025Mixtures Closest to a Given Measure: A Semidefinite Programming Approachcited by 0