mlsanityData to 7 Oct 2026

A Private and Computationally-Efficient Estimator for Unbounded Gaussians

arXiv 2111.04609 ↗First posted 8 Nov 2021stat.ML cs.CR cs.DScited by 34

Not on the map. Why?

Abstract (arXiv)

We give the first polynomial-time, polynomial-sample, differentially private estimator for the mean and covariance of an arbitrary Gaussian distribution N(μ,Sigma) in ℝd. All previous estimators are either nonconstructive, with unbounded running time, or require the user to specify a priori bounds on the parameters μ and Sigma. The primary new technical tool in our algorithm is a new differentially private preconditioner that takes samples from an arbitrary Gaussian N(0,Sigma) and returns a matrix A such that A Sigma AT has constant condition number.

Key facts. Cited by 34 papers in the map (data through 7 Oct 2026). Builds on 34 of its 56 references that are in the map. First posted on arXiv 8 Nov 2021.

Builds on

34 of 56 references.

References · 34

  1. 2016Concentrated Differential Privacy: Simplifications, Extensions, and Lower Boundscited by 339
  2. 2016Robust Estimators in High Dimensions without the Computational Intractabilitycited by 209
  3. 2017Finite Sample Differentially Private Confidence Intervalscited by 103
  4. 2018Privately Learning High-Dimensional Distributionscited by 103
  5. 2013Fingerprinting Codes and the Price of Approximate Differential Privacycited by 81
  6. 2020CoinPress: Practical Private Mean and Covariance Estimationcited by 74
  7. 2020Private Mean Estimation of Heavy-Tailed Distributionscited by 73
  8. 2021Learning with User-Level Privacycited by 72
  9. 2021Robust and Differentially Private Mean Estimationcited by 66
  10. 2019Private Hypothesis Selectioncited by 60
  11. 2015Between Pure and Approximate Differential Privacycited by 55
  12. 2020Differentially Private Assouad, Fano, and Le Camcited by 54
22 more
  1. 2019Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimationcited by 51
  2. 2020On Differentially Private Stochastic Convex Optimization with Heavy-tailed Datacited by 51
  3. 2021Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Datacited by 47
  4. 2021Covariance-Aware Private Mean Estimation Without Private Covariance Estimationcited by 46
  5. 2020Learning discrete distributions: user vs item-level privacycited by 41
  6. 2020On the Sample Complexity of Privately Learning Unbounded High-Dimensional Gaussianscited by 41
  7. 2021Instance-optimal Mean Estimation Under Differential Privacycited by 37
  8. 2015Simultaneous Private Learning of Multiple Conceptscited by 34
  9. 2021FriendlyCore: Practical Differentially Private Aggregationcited by 34
  10. 2017Tight Lower Bounds for Differentially Private Selectioncited by 33
  11. 2020A Primer on Private Statisticscited by 30
  12. 2019Differentially Private Algorithms for Learning Mixtures of Separated Gaussianscited by 27
  13. 2016Make Up Your Mind: The Price of Online Queries in Differential Privacycited by 26
  14. 2016Locating a Small Cluster Privatelycited by 20
  15. 2020Differentially Private Confidence Intervalscited by 20
  16. 2021Privately Learning Subspacescited by 16
  17. 2020Privately Learning Markov Random Fieldscited by 14
  18. 2020Optimal Private Median Estimation under Minimal Distributional Assumptionscited by 13
  19. 2021Privately Learning Mixtures of Axis-Aligned Gaussianscited by 13
  20. 2018The Power of The Hybrid Model for Mean Estimationcited by 11
  21. 2019Differentially private sub-Gaussian location estimatorscited by 9
  22. 2018Individual Sensitivity Preprocessing for Data Privacycited by 8

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 4; 2022: 6; 2023: 13; 2024: 7; 2025: 3; 2026: 1.

34 papers.

Sort:

  1. 2021Differential privacy and robust statistics in high dimensionscited by 64
  2. 2021Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanismcited by 50
  3. 2022Robustness Implies Privacy in Statistical Estimationcited by 47
  4. 2021Private and polynomial time algorithms for learning Gaussians and beyondcited by 39
  5. 2021Private Robust Estimation by Stabilizing Convex Relaxationscited by 38
  6. 2022New Lower Bounds for Private Estimation and a Generalized Fingerprinting Lemmacited by 32
  7. 2022Private Estimation with Public Datacited by 31
  8. 2022DP-PCA: Statistically Optimal and Differentially Private PCAcited by 24
  9. 2023Fast, Sample-Efficient, Affine-Invariant Private Mean and Covariance Estimation for Subgaussian Distributionscited by 22
  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 16
  12. 2022Differentially Private Covariance Revisitedcited by 15
22 more
  1. 2023Private Distribution Learning with Public Data: The View from Sample Compressioncited by 14
  2. 2023A Bias-Accuracy-Privacy Trilemma for Statistical Estimationcited by 12
  3. 2024Lower Bounds for Private Estimation of Gaussian Covariance Matrices under All Reasonable Parameter Regimescited by 9
  4. 2023Smooth Lower Bounds for Differentially Private Algorithms via Padding-and-Permuting Fingerprinting Codescited by 8
  5. 2024Insufficient Statistics Perturbation: Stable Estimators for Private Least Squarescited by 7
  6. 2023Unbounded Differentially Private Quantile and Maximum Estimationcited by 6
  7. 2023PLAN: Variance-Aware Private Mean Estimationcited by 6
  8. 2023A Polynomial Time, Pure Differentially Private Estimator for Binary Product Distributionscited by 5
  9. 2023Mixtures of Gaussians are Privately Learnable with a Polynomial Number of Samplescited by 5
  10. 2023A Simple and Practical Method for Reducing the Disparate Impact of Differential Privacycited by 4
  11. 2024Distribution Learnability and Robustnesscited by 4
  12. 2023Sample-Optimal Locally Private Hypothesis Selection and the Provable Benefits of Interactivitycited by 3
  13. 2024Not All Learnable Distribution Classes are Privately Learnablecited by 3
  14. 2024Agnostic Private Density Estimation for GMMs via List Global Stabilitycited by 2
  15. 2024On Differentially Private Subspace Estimation in a Distribution-Free Settingcited by 1
  16. 2025Optimal Differentially Private Sampling of Unbounded Gaussianscited by 1
  17. 2025DP-SPRT: Differentially Private Sequential Probability Ratio Testscited by 1
  18. 2026Minimax and Adaptive Covariance Matrix Estimation under Differential Privacycited by 1
  19. 2022Privately Estimating a Gaussian: Efficient, Robust and Optimalcited by 0
  20. 2023Instance-Specific Asymmetric Sensitivity in Differential Privacycited by 0
  21. 2024Sample-Efficient Private Learning of Mixtures of Gaussianscited by 0
  22. 2025A Private Approximation of the 2nd-Moment Matrix of Any Subsamplable Inputcited by 0