mlsanityData to 14 Oct 2026

Private and polynomial time algorithms for learning Gaussians and beyond

arXiv 2111.11320 ↗First posted 22 Nov 2021stat.ML cs.DS cs.ITcited by 39

Not on the map. Why?

Abstract (arXiv)

We present a fairly general framework for reducing (varepsilon, δ) differentially private (DP) statistical estimation to its non-private counterpart. As the main application of this framework, we give a polynomial time and (varepsilon,δ)-DP algorithm for learning (unrestricted) Gaussian distributions in ℝd. The sample complexity of our approach for learning the Gaussian up to total variation distance α is widetildeO(d2/α2 + d2√ln(1/δ)/α varepsilon + dln(1/δ) / α varepsilon) matching (up to logarithmic factors) the best known information-theoretic (non-efficient) sample complexity upper bound due to Aden-Ali, Ashtiani, and Kamath (ALT'21). In an independent work, Kamath, Mouzakis, Singhal, Steinke, and Ullman (arXiv:2111.04609) proved a similar result using a different approach and with O(d5/2) sample complexity dependence on d. As another application of our framework, we provide the first polynomial time (varepsilon, δ)-DP algorithm for robust learning of (unrestricted) Gaussians with sample complexity widetildeO(d3.5). In another independent work, Kothari, Manurangsi, and Velingker (arXiv:2112.03548) also provided a polynomial time (varepsilon, δ)-DP algorithm for robust learning of Gaussians with sample complexity widetildeO(d8).

Key facts. Cited by 39 papers in the map (data through 14 Oct 2026). Builds on 23 of its 44 references that are in the map. First posted on arXiv 22 Nov 2021.

Builds on

23 of 44 references.

References · 23

  1. 2016Concentrated Differential Privacy: Simplifications, Extensions, and Lower Boundscited by 346
  2. 2016Robust Estimators in High Dimensions without the Computational Intractabilitycited by 209
  3. 2016Concentrated Differential Privacycited by 144
  4. 2016Agnostic Estimation of Mean and Covariancecited by 131
  5. 2017Finite Sample Differentially Private Confidence Intervalscited by 104
  6. 2018Privately Learning High-Dimensional Distributionscited by 104
  7. 2020CoinPress: Practical Private Mean and Covariance Estimationcited by 74
  8. 2020Private Mean Estimation of Heavy-Tailed Distributionscited by 73
  9. 2021Robust and Differentially Private Mean Estimationcited by 66
  10. 2019Private Hypothesis Selectioncited by 60
  11. 2021Covariance-Aware Private Mean Estimation Without Private Covariance Estimationcited by 46
  12. 2019Quantum Entropy Scoring for Fast Robust Mean Estimation and Improved Outlier Detectioncited by 41
11 more
  1. 2020On the Sample Complexity of Privately Learning Unbounded High-Dimensional Gaussianscited by 41
  2. 2015Simultaneous Private Learning of Multiple Conceptscited by 34
  3. 2021FriendlyCore: Practical Differentially Private Aggregationcited by 34
  4. 2021A Private and Computationally-Efficient Estimator for Unbounded Gaussianscited by 34
  5. 2020A Primer on Private Statisticscited by 30
  6. 2019Differentially Private Algorithms for Learning Mixtures of Separated Gaussianscited by 27
  7. 2016Locating a Small Cluster Privatelycited by 20
  8. 2020Differentially Private Confidence Intervalscited by 20
  9. 2021Privately Learning Subspacescited by 16
  10. 2021Privately Learning Mixtures of Axis-Aligned Gaussianscited by 13
  11. 2021Universal Private Estimatorscited by 3

Built on by

Cited by year (2026 to 14 Oct)

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

39 papers.

Sort:

  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. 2021Private Robust Estimation by Stabilizing Convex Relaxationscited by 38
  4. 2022New Lower Bounds for Private Estimation and a Generalized Fingerprinting Lemmacited by 33
  5. 2022Private Estimation with Public Datacited by 32
  6. 2023From Robustness to Privacy and Backcited by 27
  7. 2023On the Privacy-Robustness-Utility Trilemma in Distributed Learningcited by 24
  8. 2023Fast, Sample-Efficient, Affine-Invariant Private Mean and Covariance Estimation for Subgaussian Distributionscited by 22
  9. 2023Private estimation algorithms for stochastic block models and mixture modelscited by 21
  10. 2023Polynomial Time and Private Learning of Unbounded Gaussian Mixture Modelscited by 19
  11. 2023Better and Simpler Lower Bounds for Differentially Private Statistical Estimationcited by 17
  12. 2022Differentially Private Covariance Revisitedcited by 15
27 more
  1. 2023Private Distribution Learning with Public Data: The View from Sample Compressioncited by 14
  2. 2023A Fast Algorithm for Adaptive Private Mean Estimationcited by 11
  3. 2022Differentially Private Regression with Unbounded Covariatescited by 10
  4. 2023Near Optimal Private and Robust Linear Regressioncited by 9
  5. 2024Lower Bounds for Private Estimation of Gaussian Covariance Matrices under All Reasonable Parameter Regimescited by 9
  6. 2023Smooth Lower Bounds for Differentially Private Algorithms via Padding-and-Permuting Fingerprinting Codescited by 8
  7. 2024Insufficient Statistics Perturbation: Stable Estimators for Private Least Squarescited by 7
  8. 2023PLAN: Variance-Aware Private Mean Estimationcited by 6
  9. 2022Robust Estimation of Discrete Distributions under Local Differential Privacycited by 5
  10. 2023A Polynomial Time, Pure Differentially Private Estimator for Binary Product Distributionscited by 5
  11. 2023Mixtures of Gaussians are Privately Learnable with a Polynomial Number of Samplescited by 5
  12. 2023A Simple and Practical Method for Reducing the Disparate Impact of Differential Privacycited by 4
  13. 2023Sample-Optimal Locally Private Hypothesis Selection and the Provable Benefits of Interactivitycited by 3
  14. 2024Not All Learnable Distribution Classes are Privately Learnablecited by 3
  15. 2024Agnostic Private Density Estimation for GMMs via List Global Stabilitycited by 2
  16. 2024The Broader Landscape of Robustness in Algorithmic Statisticscited by 2
  17. 2024On Differentially Private Subspace Estimation in a Distribution-Free Settingcited by 1
  18. 2025Optimal Differentially Private Sampling of Unbounded Gaussianscited by 1
  19. 2025Private Statistical Estimation via Truncationcited by 1
  20. 2025Private Geometric Median in Nearly-Linear Timecited by 1
  21. 2025Privately Estimating Black-Box Statisticscited by 1
  22. 2026Minimax and Adaptive Covariance Matrix Estimation under Differential Privacycited by 1
  23. 2022Privately Estimating a Gaussian: Efficient, Robust and Optimalcited by 0
  24. 2023Instance-Specific Asymmetric Sensitivity in Differential Privacycited by 0
  25. 2024Sample-Efficient Private Learning of Mixtures of Gaussianscited by 0
  26. 2025A Private Approximation of the 2nd-Moment Matrix of Any Subsamplable Inputcited by 0
  27. 2025Robust Learnability of Sample-Compressible Distributions under Noisy or Adversarial Perturbationscited by 0