mlsanityData to 7 Oct 2026

A Bias-Accuracy-Privacy Trilemma for Statistical Estimation

arXiv 2301.13334 ↗First posted 30 Jan 2023math.ST cs.CR cs.DScited by 12

Not on the map. Why?

Abstract (arXiv)

Differential privacy (DP) is a rigorous notion of data privacy, used for private statistics. The canonical algorithm for differentially private mean estimation is to first clip the samples to a bounded range and then add noise to their empirical mean. Clipping controls the sensitivity and, hence, the variance of the noise that we add for privacy. But clipping also introduces statistical bias. This tradeoff is inherent: we prove that no algorithm can simultaneously have low bias, low error, and low privacy loss for arbitrary distributions. Additionally, we show that under strong notions of DP (i.e., pure or concentrated DP), unbiased mean estimation is impossible, even if we assume that the data is sampled from a Gaussian. On the positive side, we show that unbiased mean estimation is possible under a more permissive notion of differential privacy (approximate DP) if we assume that the distribution is symmetric.

Key facts. Cited by 12 papers in the map (data through 7 Oct 2026). Builds on 46 of its 75 references that are in the map. First posted on arXiv 30 Jan 2023.

Builds on

46 of 75 references.

References · 46

  1. 2016Concentrated Differential Privacy: Simplifications, Extensions, and Lower Boundscited by 339
  2. 2016Concentrated Differential Privacycited by 139
  3. 2016Minimax Optimal Procedures for Locally Private Estimationcited by 103
  4. 2017Finite Sample Differentially Private Confidence Intervalscited by 103
  5. 2018Privately Learning High-Dimensional Distributionscited by 103
  6. 2015Algorithmic Stability for Adaptive Data Analysiscited by 88
  7. 2013Fingerprinting Codes and the Price of Approximate Differential Privacycited by 81
  8. 2020CoinPress: Practical Private Mean and Covariance Estimationcited by 74
  9. 2020Private Mean Estimation of Heavy-Tailed Distributionscited by 73
  10. 2021Learning with User-Level Privacycited by 72
  11. 2021Robust and Differentially Private Mean Estimationcited by 66
  12. 2021Differential privacy and robust statistics in high dimensionscited by 64
34 more
  1. 2019Private Hypothesis Selectioncited by 60
  2. 2015Between Pure and Approximate Differential Privacycited by 55
  3. 2019Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimationcited by 51
  4. 2020On Differentially Private Stochastic Convex Optimization with Heavy-tailed Datacited by 51
  5. 2021Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanismcited by 50
  6. 2021Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Datacited by 47
  7. 2022Robustness Implies Privacy in Statistical Estimationcited by 47
  8. 2021Covariance-Aware Private Mean Estimation Without Private Covariance Estimationcited by 46
  9. 2020Learning discrete distributions: user vs item-level privacycited by 41
  10. 2020On the Sample Complexity of Privately Learning Unbounded High-Dimensional Gaussianscited by 41
  11. 2021Private Robust Estimation by Stabilizing Convex Relaxationscited by 38
  12. 2021Instance-optimal Mean Estimation Under Differential Privacycited by 37
  13. 2014Preventing False Discovery in Interactive Data Analysis is Hardcited by 34
  14. 2021FriendlyCore: Practical Differentially Private Aggregationcited by 34
  15. 2021A Private and Computationally-Efficient Estimator for Unbounded Gaussianscited by 34
  16. 2017Tight Lower Bounds for Differentially Private Selectioncited by 33
  17. 2022New Lower Bounds for Private Estimation and a Generalized Fingerprinting Lemmacited by 32
  18. 2022Private Estimation with Public Datacited by 31
  19. 2020A Primer on Private Statisticscited by 30
  20. 2016Make Up Your Mind: The Price of Online Queries in Differential Privacycited by 26
  21. 2017Generalization for Adaptively-chosen Estimators via Stable Mediancited by 26
  22. 2016Max-Information, Differential Privacy, and Post-Selection Hypothesis Testingcited by 25
  23. 2022Privacy Induces Robustness: Information-Computation Gaps and Sparse Mean Estimationcited by 25
  24. 2023Private estimation algorithms for stochastic block models and mixture modelscited by 21
  25. 2020Differentially Private Confidence Intervalscited by 20
  26. 2020Parametric Bootstrap for Differentially Private Confidence Intervalscited by 19
  27. 2020The Cost of Privacy in Generalized Linear Models: Algorithms and Minimax Lower Boundscited by 15
  28. 2021Unbiased Statistical Estimation and Valid Confidence Intervals Under Differential Privacycited by 15
  29. 2020Bias and Variance of Post-processing in Differential Privacycited by 14
  30. 2018The Power of The Hybrid Model for Mean Estimationcited by 11
  31. 2023A Fast Algorithm for Adaptive Private Mean Estimationcited by 11
  32. 2022Post-processing of Differentially Private Data: A Fairness Perspectivecited by 9
  33. 2022Continual Mean Estimation Under User-Level Privacycited by 5
  34. 2023Privacy and Bias Analysis of Disclosure Avoidance Systemscited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 6; 2024: 0; 2025: 2; 2026: 4.

12 papers.

  1. 2023Differentially Private Image Classification by Learning Priors from Random Processescited by 19
  2. 2023Mean estimation in the add-remove model of differential privacycited by 9
  3. 2023Smooth Lower Bounds for Differentially Private Algorithms via Padding-and-Permuting Fingerprinting Codescited by 8
  4. 2023PLAN: Variance-Aware Private Mean Estimationcited by 6
  5. 2023A Polynomial Time, Pure Differentially Private Estimator for Binary Product Distributionscited by 5
  6. 2023General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean Estimationcited by 3
  7. 2025High-Dimensional Differentially Private Quantile Regression: Distributed Estimation and Statistical Inferencecited by 1
  8. 2026Harnessing Synthetic Data from Generative AI for Statistical Inferencecited by 1
  9. 2025Privately Estimating Black-Box Statisticscited by 0
  10. 2026Noise-Calibrated Inference from Differentially Private Sufficient Statistics in Exponential Familiescited by 0
  11. 2026Protecting and Preserving Protest Dynamics for Responsible Analysiscited by 0
  12. 2026Near-optimal node-private community estimation in polynomial-timecited by 0