mlsanityData to 7 Oct 2026

Robustness Implies Privacy in Statistical Estimation

arXiv 2212.05015 ↗First posted 9 Dec 2022cs.DS cs.CR cs.ITcited by 47

Not on the map. Why?

Abstract (arXiv)

We study the relationship between adversarial robustness and differential privacy in high-dimensional algorithmic statistics. We give the first black-box reduction from privacy to robustness which can produce private estimators with optimal tradeoffs among sample complexity, accuracy, and privacy for a wide range of fundamental high-dimensional parameter estimation problems, including mean and covariance estimation. We show that this reduction can be implemented in polynomial time in some important special cases. In particular, using nearly-optimal polynomial-time robust estimators for the mean and covariance of high-dimensional Gaussians which are based on the Sum-of-Squares method, we design the first polynomial-time private estimators for these problems with nearly-optimal samples-accuracy-privacy tradeoffs. Our algorithms are also robust to a nearly optimal fraction of adversarially-corrupted samples.

Key facts. Cited by 47 papers in the map (data through 7 Oct 2026). Builds on 32 of its 50 references that are in the map. First posted on arXiv 9 Dec 2022.

Builds on

32 of 50 references.

References · 32

  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. 2019Recent Advances in Algorithmic High-Dimensional Robust Statisticscited by 100
  5. 2017Being Robust (in High Dimensions) Can Be Practicalcited by 83
  6. 2017Mixture Models, Robustness, and Sum of Squares Proofscited by 81
  7. 2018Efficient Algorithms and Lower Bounds for Robust Linear Regressioncited by 76
  8. 2020Private Mean Estimation of Heavy-Tailed Distributionscited by 73
  9. 2018Efficient Algorithms for Outlier-Robust Regressioncited by 72
  10. 2021Robust and Differentially Private Mean Estimationcited by 66
  11. 2021Differential privacy and robust statistics in high dimensionscited by 64
  12. 2019Private Hypothesis Selectioncited by 60
20 more
  1. 2019Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimationcited by 51
  2. 2021Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanismcited by 50
  3. 2021Covariance-Aware Private Mean Estimation Without Private Covariance Estimationcited by 46
  4. 2017Resilience: A Criterion for Learning in the Presence of Arbitrary Outlierscited by 43
  5. 2020On the Sample Complexity of Privately Learning Unbounded High-Dimensional Gaussianscited by 41
  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. 2021Tight and Robust Private Mean Estimation with Few Userscited by 26
  11. 2018High-dimensional estimation via sum-of-squares proofscited by 25
  12. 2022Privacy Induces Robustness: Information-Computation Gaps and Sparse Mean Estimationcited by 25
  13. 2019Privacy-preserving parametric inference: a case for robust statisticscited by 17
  14. 2019How Hard Is Robust Mean Estimation?cited by 16
  15. 2022On robustness and local differential privacycited by 15
  16. 2021Polynomial-Time Sum-of-Squares Can Robustly Estimate Mean and Covariance of Gaussians Optimallycited by 14
  17. 2020Robust and Private Learning of Halfspacescited by 7
  18. 2021Differentially private depth functions and their associated medianscited by 7
  19. 2021Perturbed M-Estimation: A Further Investigation of Robust Statistics for Differential Privacycited by 2
  20. 2022Differentially private multivariate medianscited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 1; 2023: 16; 2024: 17; 2025: 8; 2026: 5.

47 papers.

Sort:

By area:

  1. 2023From Robustness to Privacy and Backcited by 27
  2. 2023On the Privacy-Robustness-Utility Trilemma in Distributed Learningcited by 24
  3. 2023Fast, Sample-Efficient, Affine-Invariant Private Mean and Covariance Estimation for Subgaussian Distributionscited by 22
  4. 2023Polynomial Time and Private Learning of Unbounded Gaussian Mixture Modelscited by 19
  5. 2023Better and Simpler Lower Bounds for Differentially Private Statistical Estimationcited by 16
  6. 2023Private Distribution Learning with Public Data: The View from Sample Compressioncited by 14
  7. 2024Differential Privacy Mechanisms in Neural Tangent Kernel Regressioncited by 14
  8. 2024Provable Differentially Private Computation of the Cross-Attention Mechanismcited by 14
  9. 2023The Bayesian Stability Zoocited by 13
  10. 2023A Bias-Accuracy-Privacy Trilemma for Statistical Estimationcited by 12
  11. 2023A Fast Algorithm for Adaptive Private Mean Estimationcited by 11
  12. 2023Near Optimal Private and Robust Linear Regressioncited by 9
35 more
  1. 2024Lower Bounds for Private Estimation of Gaussian Covariance Matrices under All Reasonable Parameter Regimescited by 9
  2. 2024Fast John Ellipsoid Computation with Differential Privacy Optimizationcited by 7
  3. 2023On Private and Robust Banditscited by 6
  4. 2024Dimension-free Private Mean Estimation for Anisotropic Distributionscited by 6
  5. 2023A Polynomial Time, Pure Differentially Private Estimator for Binary Product Distributionscited by 5
  6. 2023Mixtures of Gaussians are Privately Learnable with a Polynomial Number of Samplescited by 5
  7. 2024Efficient Certificates of Anti-Concentration Beyond Gaussianscited by 4
  8. 2024Distribution Learnability and Robustnesscited by 4
  9. 2023Sample-Optimal Locally Private Hypothesis Selection and the Provable Benefits of Interactivitycited by 3
  10. 2024Not All Learnable Distribution Classes are Privately Learnablecited by 3
  11. 2024Private graphon estimation via sum-of-squarescited by 3
  12. 2024SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and Morecited by 3
  13. 2025SquarechiPO: Differentially Private and Robust chi2-Preference Optimization in Offline Direct Alignmentcited by 3
  14. 2024Private Edge Density Estimation for Random Graphs: Optimal, Efficient and Robustcited by 2
  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. 2025Tukey Depth Mechanisms for Practical Private Mean Estimationcited by 2
  18. 2025Causality Is Key to Understand and Balance Multiple Goals in Trustworthy ML and Foundation Modelscited by 2
  19. 2025Sample-Optimal Private Regression in Polynomial Timecited by 2
  20. 2023Differentially-Private Decision Trees and Provable Robustness to Data Poisoningcited by 1
  21. 2024Bridging Privacy and Robustness for Trustworthy Machine Learningcited by 1
  22. 2024Perturb-and-Project: Differentially Private Similarities and Marginalscited by 1
  23. 2025Optimal Differentially Private Sampling of Unbounded Gaussianscited by 1
  24. 2025Private Statistical Estimation via Truncationcited by 1
  25. 2026Computation-Utility-Privacy Tradeoffs in Bayesian Estimationcited by 1
  26. 2026Gap-Free Streaming PCA Beyond Rank-One Updates: Near-Optimal Rates and Applications to Differential Privacycited by 1
  27. 2022Privately Estimating a Gaussian: Efficient, Robust and Optimalcited by 0
  28. 2023Statistical Barriers to Affine-equivariant Estimationcited by 0
  29. 2024Sample-Efficient Private Learning of Mixtures of Gaussianscited by 0
  30. 2024Optimal Rates for Robust Stochastic Convex Optimizationcited by 0
  31. 2025Private Training & Data Generation by Clustering Embeddingscited by 0
  32. 2025Robust Estimation Under Heterogeneous Corruption Ratescited by 0
  33. 2026Robust Privacy: Inference-Stage Privacy through Certified Robustnesscited by 0
  34. 2026Computationally Efficient Replicable Learning of Parities and Applicationscited by 0
  35. 2026Robust Statistical Estimators with Bounded Empirical Sensitivitycited by 0