mlsanityData to 14 Oct 2026

Differential privacy and robust statistics in high dimensions

arXiv 2111.06578 ↗First posted 12 Nov 2021math.ST cs.CR cs.ITcited by 64

Not on the map. Why?

Abstract (arXiv)

We introduce a universal framework for characterizing the statistical efficiency of a statistical estimation problem with differential privacy guarantees. Our framework, which we call High-dimensional Propose-Test-Release (HPTR), builds upon three crucial components: the exponential mechanism, robust statistics, and the Propose-Test-Release mechanism. Gluing all these together is the concept of resilience, which is central to robust statistical estimation. Resilience guides the design of the algorithm, the sensitivity analysis, and the success probability analysis of the test step in Propose-Test-Release. The key insight is that if we design an exponential mechanism that accesses the data only via one-dimensional robust statistics, then the resulting local sensitivity can be dramatically reduced. Using resilience, we can provide tight local sensitivity bounds. These tight bounds readily translate into near-optimal utility guarantees in several cases. We give a general recipe for applying HPTR to a given instance of a statistical estimation problem and demonstrate it on canonical problems of mean estimation, linear regression, covariance estimation, and principal component analysis. We introduce a general utility analysis technique that proves that HPTR nearly achieves the optimal sample complexity under several scenarios studied in the literature.

Key facts. Cited by 64 papers in the map (data through 14 Oct 2026). Builds on 31 of its 80 references that are in the map. First posted on arXiv 12 Nov 2021.

Builds on

31 of 80 references.

References · 31

  1. 2016Deep Learning with Differential Privacycited by 2,728
  2. 2021Differentially Private Fine-tuning of Language Modelscited by 400
  3. 2016Agnostic Estimation of Mean and Covariancecited by 131
  4. 2021Large-Scale Differentially Private BERTcited by 118
  5. 2016Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixturescited by 115
  6. 2017Finite Sample Differentially Private Confidence Intervalscited by 104
  7. 2017Being Robust (in High Dimensions) Can Be Practicalcited by 83
  8. 2018Robust Estimation via Robust Gradient Estimationcited by 76
  9. 2020CoinPress: Practical Private Mean and Covariance Estimationcited by 74
  10. 2020Private Mean Estimation of Heavy-Tailed Distributionscited by 73
  11. 2021Robust and Differentially Private Mean Estimationcited by 66
  12. 2018Revisiting differentially private linear regression: optimal and adaptive prediction & estimation in unbounded domaincited by 61
19 more
  1. 2019Private Hypothesis Selectioncited by 60
  2. 2019Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimationcited by 52
  3. 2021Covariance-Aware Private Mean Estimation Without Private Covariance Estimationcited by 46
  4. 2020Robust and Heavy-Tailed Mean Estimation Made Simple, via Regret Minimizationcited by 44
  5. 2020On the Sample Complexity of Privately Learning Unbounded High-Dimensional Gaussianscited by 41
  6. 2019Robust subgaussian estimation of a mean vector in nearly linear timecited by 37
  7. 2019Generalized Resilience and Robust Statisticscited by 37
  8. 2021Instance-optimal Mean Estimation Under Differential Privacycited by 37
  9. 2016On the Theory and Practice of Privacy-Preserving Bayesian Data Analysiscited by 35
  10. 2020Robust Sub-Gaussian Principal Component Analysis and Width-Independent Schatten Packingcited by 35
  11. 2021A Private and Computationally-Efficient Estimator for Unbounded Gaussianscited by 34
  12. 2018Mean Estimation with Sub-Gaussian Rates in Polynomial Timecited by 33
  13. 2020Optimal Robust Linear Regression in Nearly Linear Timecited by 32
  14. 2017Robust Regression via Mutivariate Regression Depthcited by 20
  15. 2019Privacy-preserving parametric inference: a case for robust statisticscited by 18
  16. 2020Propose, Test, Release: Differentially private estimation with high probabilitycited by 15
  17. 2021Robust Regression Revisited: Acceleration and Improved Estimation Ratescited by 15
  18. 2019Differentially private sub-Gaussian location estimatorscited by 9
  19. 2019The Cost of Privacy: Rates of Convergence for Parameter Estimation with Differential Privacycited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 2; 2022: 15; 2023: 18; 2024: 15; 2025: 8; 2026: 6.

64 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. 2022Privacy Induces Robustness: Information-Computation Gaps and Sparse Mean Estimationcited by 25
  8. 2022DP-PCA: Statistically Optimal and Differentially Private PCAcited by 24
  9. 2023On the Privacy-Robustness-Utility Trilemma in Distributed Learningcited by 24
  10. 2023Fast, Sample-Efficient, Affine-Invariant Private Mean and Covariance Estimation for Subgaussian Distributionscited by 22
  11. 2023Private estimation algorithms for stochastic block models and mixture modelscited by 21
  12. 2022Easy Differentially Private Linear Regressioncited by 19
38 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 17
  3. 2022Differentially Private Covariance Revisitedcited by 15
  4. 2023Private Distribution Learning with Public Data: The View from Sample Compressioncited by 14
  5. 2023A Bias-Accuracy-Privacy Trilemma for Statistical Estimationcited by 12
  6. 2024Private Gradient Descent for Linear Regression: Tighter Error Bounds and Instance-Specific Uncertainty Estimationcited by 12
  7. 2023A Fast Algorithm for Adaptive Private Mean Estimationcited by 11
  8. 2024A Huber Loss Minimization Approach to Mean Estimation under User-level Differential Privacycited by 11
  9. 2022Differentially Private Regression with Unbounded Covariatescited by 10
  10. 2024Data-adaptive Differentially Private Prompt Synthesis for In-Context Learningcited by 10
  11. 2023Near Optimal Private and Robust Linear Regressioncited by 9
  12. 2024Lower Bounds for Private Estimation of Gaussian Covariance Matrices under All Reasonable Parameter Regimescited by 9
  13. 2022Differentially Private Image Classification from Featurescited by 7
  14. 2024Black-Box k-to-1-PCA Reductions: Theory and Applicationscited by 7
  15. 2024Insufficient Statistics Perturbation: Stable Estimators for Private Least Squarescited by 7
  16. 2024Certification for Differentially Private Prediction in Gradient-Based Trainingcited by 7
  17. 2022(Nearly) Optimal Private Linear Regression via Adaptive Clippingcited by 6
  18. 2022Generalized PTR: User-Friendly Recipes for Data-Adaptive Algorithms with Differential Privacycited by 6
  19. 2024Dimension-free Private Mean Estimation for Anisotropic Distributionscited by 6
  20. 2022Robust Estimation of Discrete Distributions under Local Differential Privacycited by 5
  21. 2023A Polynomial Time, Pure Differentially Private Estimator for Binary Product Distributionscited by 5
  22. 2023Private Federated Learning with Autotuned Compressioncited by 5
  23. 2023Mixtures of Gaussians are Privately Learnable with a Polynomial Number of Samplescited by 5
  24. 2022Renyi Differential Privacy of Propose-Test-Release and Applications to Private and Robust Machine Learningcited by 4
  25. 2023Differentially Private Low-dimensional Synthetic Data from High-dimensional Datasetscited by 4
  26. 2024Distribution Learnability and Robustnesscited by 4
  27. 2023Differentially private projection-depth-based medianscited by 3
  28. 2024Not All Learnable Distribution Classes are Privately Learnablecited by 3
  29. 2025An Iterative Algorithm for Differentially Private k-PCA with Adaptive Noisecited by 3
  30. 2022Differentially private multivariate medianscited by 2
  31. 2024Private Edge Density Estimation for Random Graphs: Optimal, Efficient and Robustcited by 2
  32. 2024Agnostic Private Density Estimation for GMMs via List Global Stabilitycited by 2
  33. 2024The Broader Landscape of Robustness in Algorithmic Statisticscited by 2
  34. 2025Tukey Depth Mechanisms for Practical Private Mean Estimationcited by 2
  35. 2025Sample-Optimal Private Regression in Polynomial Timecited by 2
  36. 2025The Gaussian Mixing Mechanism: Renyi Differential Privacy via Gaussian Sketchescited by 2
  37. 2026Differentially Private and Communication Efficient Large Language Model Split Inference via Stochastic Quantization and Soft Promptcited by 2
  38. 2023Robust probabilistic inference via a constrained transport metriccited by 1

50 most cited of 64 All 64 (JSON)