mlsanityData to 14 Oct 2026

Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanism

arXiv 2111.12981 ↗First posted 25 Nov 2021cs.DS cs.CR cs.ITcited by 50

Not on the map. Why?

Abstract (arXiv)

We give the first polynomial-time algorithm to estimate the mean of a d-variate probability distribution with bounded covariance from tildeO(d) independent samples subject to pure differential privacy. Prior algorithms for this problem either incur exponential running time, require Omega(d1.5) samples, or satisfy only the weaker concentrated or approximate differential privacy conditions. In particular, all prior polynomial-time algorithms require d1+Omega(1) samples to guarantee small privacy loss with "cryptographically" high probability, 1-2^-dOmega(1), while our algorithm retains tildeO(d) sample complexity even in this stringent setting. Our main technique is a new approach to use the powerful Sum of Squares method (SoS) to design differentially private algorithms. SoS proofs to algorithms is a key theme in numerous recent works in high-dimensional algorithmic statistics -- estimators which apparently require exponential running time but whose analysis can be captured by low-degree Sum of Squares proofs can be automatically turned into polynomial-time algorithms with the same provable guarantees. We demonstrate a similar proofs to private algorithms phenomenon: instances of the workhorse exponential mechanism which apparently require exponential time but which can be analyzed with low-degree SoS proofs can be automatically turned into polynomial-time differentially private algorithms. We prove a meta-theorem capturing this phenomenon, which we expect to be of broad use in private algorithm design. Our techniques also draw new connections between differentially private and robust statistics in high dimensions. In particular, viewed through our proofs-to-private-algorithms lens, several well-studied SoS proofs from recent works in algorithmic robust statistics directly yield key components of our differentially private mean estimation algorithm.

Key facts. Cited by 50 papers in the map (data through 14 Oct 2026). Builds on 48 of its 75 references that are in the map. First posted on arXiv 25 Nov 2021.

Builds on

48 of 75 references.

References · 48

  1. 2016Robust Estimators in High Dimensions without the Computational Intractabilitycited by 209
  2. 2019Mean estimation and regression under heavy-tailed distributions--a surveycited by 136
  3. 2016Agnostic Estimation of Mean and Covariancecited by 131
  4. 2014Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Boundscited by 107
  5. 2017Finite Sample Differentially Private Confidence Intervalscited by 104
  6. 2018Privately Learning High-Dimensional Distributionscited by 104
  7. 2019Recent Advances in Algorithmic High-Dimensional Robust Statisticscited by 101
  8. 2013Fingerprinting Codes and the Price of Approximate Differential Privacycited by 82
  9. 2017Mixture Models, Robustness, and Sum of Squares Proofscited by 81
  10. 2020CoinPress: Practical Private Mean and Covariance Estimationcited by 74
  11. 2020Private Mean Estimation of Heavy-Tailed Distributionscited by 73
  12. 2021Learning with User-Level Privacycited by 72
36 more
  1. 2021Robust and Differentially Private Mean Estimationcited by 66
  2. 2021Differential privacy and robust statistics in high dimensionscited by 64
  3. 2019Private Hypothesis Selectioncited by 60
  4. 2017The power of sum-of-squares for detecting hidden structurescited by 54
  5. 2019Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimationcited by 52
  6. 2020On Differentially Private Stochastic Convex Optimization with Heavy-tailed Datacited by 51
  7. 2020Outlier Robust Mean Estimation with Subgaussian Rates via Stabilitycited by 50
  8. 2017Sub-Gaussian estimators of the mean of a random vectorcited by 47
  9. 2021Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Datacited by 47
  10. 2021Covariance-Aware Private Mean Estimation Without Private Covariance Estimationcited by 46
  11. 2020Robust and Heavy-Tailed Mean Estimation Made Simple, via Regret Minimizationcited by 44
  12. 2017Resilience: A Criterion for Learning in the Presence of Arbitrary Outlierscited by 43
  13. 2020Learning discrete distributions: user vs item-level privacycited by 41
  14. 2020On the Sample Complexity of Privately Learning Unbounded High-Dimensional Gaussianscited by 41
  15. 2021Private and polynomial time algorithms for learning Gaussians and beyondcited by 39
  16. 2019Robust subgaussian estimation of a mean vector in nearly linear timecited by 37
  17. 2021Instance-optimal Mean Estimation Under Differential Privacycited by 37
  18. 2014Interactive Fingerprinting Codes and the Hardness of Preventing False Discoverycited by 35
  19. 2021A Private and Computationally-Efficient Estimator for Unbounded Gaussianscited by 34
  20. 2018Mean Estimation with Sub-Gaussian Rates in Polynomial Timecited by 33
  21. 2020A Primer on Private Statisticscited by 30
  22. 2017Outlier-robust moment-estimation via sum-of-squarescited by 27
  23. 2019Differentially Private Algorithms for Learning Mixtures of Separated Gaussianscited by 27
  24. 2018High-dimensional estimation via sum-of-squares proofscited by 25
  25. 2017Better Agnostic Clustering Via Relaxed Tensor Normscited by 21
  26. 2020Differentially Private Confidence Intervalscited by 20
  27. 2019Fast Mean Estimation with Sub-Gaussian Ratescited by 18
  28. 2017Exact tensor completion with sum-of-squarescited by 14
  29. 2020Privately Learning Markov Random Fieldscited by 14
  30. 2020Optimal Private Median Estimation under Minimal Distributional Assumptionscited by 13
  31. 2021Privately Learning Mixtures of Axis-Aligned Gaussianscited by 13
  32. 2018The Power of The Hybrid Model for Mean Estimationcited by 11
  33. 2019A Unified Approach to Robust Mean Estimationcited by 11
  34. 2019Differentially private sub-Gaussian location estimatorscited by 9
  35. 2021Sampling from Log-Concave Distributions with Infinity-Distance Guaranteescited by 8
  36. 2014Privately Solving Linear Programscited by 7

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 1; 2022: 9; 2023: 18; 2024: 12; 2025: 7; 2026: 3.

50 papers.

Sort:

  1. 2022Robustness Implies Privacy in Statistical Estimationcited by 47
  2. 2021Private Robust Estimation by Stabilizing Convex Relaxationscited by 38
  3. 2022New Lower Bounds for Private Estimation and a Generalized Fingerprinting Lemmacited by 33
  4. 2022Private Estimation with Public Datacited by 32
  5. 2023From Robustness to Privacy and Backcited by 27
  6. 2022Privacy Induces Robustness: Information-Computation Gaps and Sparse Mean Estimationcited by 25
  7. 2022DP-PCA: Statistically Optimal and Differentially Private PCAcited by 24
  8. 2023On the Privacy-Robustness-Utility Trilemma in Distributed Learningcited by 24
  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. 2023A Bias-Accuracy-Privacy Trilemma for Statistical Estimationcited by 12
38 more
  1. 2023A Fast Algorithm for Adaptive Private Mean Estimationcited by 11
  2. 2024A Huber Loss Minimization Approach to Mean Estimation under User-level Differential Privacycited by 11
  3. 2022Differentially Private Regression with Unbounded Covariatescited by 10
  4. 2023Near Optimal Private and Robust Linear Regressioncited by 9
  5. 2025Towards Trustworthy Federated Learning with Untrusted Participantscited by 8
  6. 2024Insufficient Statistics Perturbation: Stable Estimators for Private Least Squarescited by 7
  7. 2023On Private and Robust Banditscited by 6
  8. 2023Mean Estimation Under Heterogeneous Privacy: Some Privacy Can Be Freecited by 6
  9. 2023PLAN: Variance-Aware Private Mean Estimationcited by 6
  10. 2023Mean Estimation Under Heterogeneous Privacy Demandscited by 6
  11. 2022Robust Estimation of Discrete Distributions under Local Differential Privacycited by 5
  12. 2023A Polynomial Time, Pure Differentially Private Estimator for Binary Product Distributionscited by 5
  13. 2023Mixtures of Gaussians are Privately Learnable with a Polynomial Number of Samplescited by 5
  14. 2024Efficient Certificates of Anti-Concentration Beyond Gaussianscited by 4
  15. 2024Distribution Learnability and Robustnesscited by 4
  16. 2023Subset-Based Instance Optimality in Private Estimationcited by 3
  17. 2023Differentially private projection-depth-based medianscited by 3
  18. 2024Private graphon estimation via sum-of-squarescited by 3
  19. 2024Learning with User-Level Local Differential Privacycited by 3
  20. 2025An Iterative Algorithm for Differentially Private k-PCA with Adaptive Noisecited by 3
  21. 2022Differentially private multivariate medianscited by 2
  22. 2023Learning Mixtures of Gaussians with Censored Datacited by 2
  23. 2024Private Edge Density Estimation for Random Graphs: Optimal, Efficient and Robustcited by 2
  24. 2024Agnostic Private Density Estimation for GMMs via List Global Stabilitycited by 2
  25. 2024The Broader Landscape of Robustness in Algorithmic Statisticscited by 2
  26. 2024Privacy-Aware Randomized Quantization via Linear Programmingcited by 1
  27. 2024Perturb-and-Project: Differentially Private Similarities and Marginalscited by 1
  28. 2024Differential Private Stochastic Optimization with Heavy-tailed Data: Towards Optimal Ratescited by 1
  29. 2025Improved subsample-and-aggregate via the private modified winsorized meancited by 1
  30. 2025Optimal Differentially Private Sampling of Unbounded Gaussianscited by 1
  31. 2025Private Statistical Estimation via Truncationcited by 1
  32. 2025Privately Estimating Black-Box Statisticscited by 1
  33. 2026Computation-Utility-Privacy Tradeoffs in Bayesian Estimationcited by 1
  34. 2022Privately Estimating a Gaussian: Efficient, Robust and Optimalcited by 0
  35. 2023Statistical Barriers to Affine-equivariant Estimationcited by 0
  36. 2025Private Training & Data Generation by Clustering Embeddingscited by 0
  37. 2026Near-Optimal Private Tests for Simple and MLR Hypothesescited by 0
  38. 2026Computationally tractable robust differentially private mean estimationcited by 0