mlsanityData to 7 Oct 2026

On the Sample Complexity of Privately Learning Unbounded High-Dimensional Gaussians

arXiv 2010.09929 ↗First posted 19 Oct 2020stat.ML cs.CR cs.DScited by 41

Not on the map. Why?

Abstract (arXiv)

We provide sample complexity upper bounds for agnostically learning multivariate Gaussians under the constraint of approximate differential privacy. These are the first finite sample upper bounds for general Gaussians which do not impose restrictions on the parameters of the distribution. Our bounds are near-optimal in the case when the covariance is known to be the identity, and conjectured to be near-optimal in the general case. From a technical standpoint, we provide analytic tools for arguing the existence of global "locally small" covers from local covers of the space. These are exploited using modifications of recent techniques for differentially private hypothesis selection. Our techniques may prove useful for privately learning other distribution classes which do not possess a finite cover.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

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

41 papers.

Sort:

  1. 2021Robust and Differentially Private Mean Estimationcited by 66
  2. 2021Differential privacy and robust statistics in high dimensionscited by 64
  3. 2021Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanismcited by 50
  4. 2022Robustness Implies Privacy in Statistical Estimationcited by 47
  5. 2021Covariance-Aware Private Mean Estimation Without Private Covariance Estimationcited by 46
  6. 2021Private and polynomial time algorithms for learning Gaussians and beyondcited by 39
  7. 2021Private Robust Estimation by Stabilizing Convex Relaxationscited by 38
  8. 2021A Private and Computationally-Efficient Estimator for Unbounded Gaussianscited by 34
  9. 2022New Lower Bounds for Private Estimation and a Generalized Fingerprinting Lemmacited by 32
  10. 2022Private Estimation with Public Datacited by 31
  11. 2023From Robustness to Privacy and Backcited by 27
  12. 2023Fast, Sample-Efficient, Affine-Invariant Private Mean and Covariance Estimation for Subgaussian Distributionscited by 22
29 more
  1. 2023Polynomial Time and Private Learning of Unbounded Gaussian Mixture Modelscited by 19
  2. 2023Better and Simpler Lower Bounds for Differentially Private Statistical Estimationcited by 16
  3. 2022Differentially Private Covariance Revisitedcited by 15
  4. 2023Private Distribution Learning with Public Data: The View from Sample Compressioncited by 14
  5. 2021Privately Learning Mixtures of Axis-Aligned Gaussianscited by 13
  6. 2023A Bias-Accuracy-Privacy Trilemma for Statistical Estimationcited by 12
  7. 2022Differentially Private Regression with Unbounded Covariatescited by 10
  8. 2024Lower Bounds for Private Estimation of Gaussian Covariance Matrices under All Reasonable Parameter Regimescited by 9
  9. 2024Insufficient Statistics Perturbation: Stable Estimators for Private Least Squarescited by 7
  10. 2024Dimension-free Private Mean Estimation for Anisotropic Distributionscited by 6
  11. 2023A Polynomial Time, Pure Differentially Private Estimator for Binary Product Distributionscited by 5
  12. 2023Mixtures of Gaussians are Privately Learnable with a Polynomial Number of Samplescited by 5
  13. 2024Differentially Private Post-Processing for Fair Regressioncited by 5
  14. 2024Distribution Learnability and Robustnesscited by 4
  15. 2023Sample-Optimal Locally Private Hypothesis Selection and the Provable Benefits of Interactivitycited by 3
  16. 2023Differentially private projection-depth-based medianscited by 3
  17. 2024Not All Learnable Distribution Classes are Privately Learnablecited by 3
  18. 2024Agnostic Private Density Estimation for GMMs via List Global Stabilitycited by 2
  19. 2025Learning with Differentially Private (Sliced) Wasserstein Gradientscited by 2
  20. 2026On the Price of Privacy for Language Identification and Generationcited by 2
  21. 2025Optimal Differentially Private Sampling of Unbounded Gaussianscited by 1
  22. 2025Private Statistical Estimation via Truncationcited 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. 2025Nearly-Linear Time Private Hypothesis Selection with the Optimal Approximation Factorcited by 0
  28. 2025Private Training & Data Generation by Clustering Embeddingscited by 0
  29. 2025Query-Efficient Locally Private Hypothesis Selection via the Scheffe Graphcited by 0