mlsanityData to 14 Oct 2026

Private Mean Estimation of Heavy-Tailed Distributions

arXiv 2002.09464 ↗First posted 21 Feb 2020cs.DS cs.CR cs.ITcited by 73

Not on the map. Why?

Abstract (arXiv)

We give new upper and lower bounds on the minimax sample complexity of differentially private mean estimation of distributions with bounded k-th moments. Roughly speaking, in the univariate case, we show that n = Thetaleft(frac1α2 + frac1α^frackk-1varepsilonright) samples are necessary and sufficient to estimate the mean to α-accuracy under varepsilon-differential privacy, or any of its common relaxations. This result demonstrates a qualitatively different behavior compared to estimation absent privacy constraints, for which the sample complexity is identical for all k ≥ 2. We also give algorithms for the multivariate setting whose sample complexity is a factor of O(d) larger than the univariate case.

Key facts. Cited by 73 papers in the map (data through 14 Oct 2026). First posted on arXiv 21 Feb 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 15; 2022: 17; 2023: 17; 2024: 10; 2025: 7; 2026: 7.

73 papers.

Sort:

  1. 2021Learning with User-Level Privacycited by 72
  2. 2021Robust and Differentially Private Mean Estimationcited by 66
  3. 2021Differential privacy and robust statistics in high dimensionscited by 64
  4. 2021Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanismcited by 50
  5. 2021Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Datacited by 47
  6. 2022Robustness Implies Privacy in Statistical Estimationcited by 47
  7. 2021Covariance-Aware Private Mean Estimation Without Private Covariance Estimationcited by 46
  8. 2021High Dimensional Differentially Private Stochastic Optimization with Heavy-tailed Datacited by 42
  9. 2021Private and polynomial time algorithms for learning Gaussians and beyondcited by 39
  10. 2021Private Robust Estimation by Stabilizing Convex Relaxationscited by 38
  11. 2021FriendlyCore: Practical Differentially Private Aggregationcited by 34
  12. 2021A Private and Computationally-Efficient Estimator for Unbounded Gaussianscited by 34
38 more
  1. 2022New Lower Bounds for Private Estimation and a Generalized Fingerprinting Lemmacited by 33
  2. 2022On the Impossible Safety of Large AI Modelscited by 28
  3. 2023From Robustness to Privacy and Backcited by 27
  4. 2021Optimal Rates of (Locally) Differentially Private Heavy-tailed Multi-Armed Banditscited by 25
  5. 2022Privacy Induces Robustness: Information-Computation Gaps and Sparse Mean Estimationcited by 25
  6. 2022Optimal and Differentially Private Data Acquisition: Central and Local Mechanismscited by 24
  7. 2022DP-PCA: Statistically Optimal and Differentially Private PCAcited by 24
  8. 2023Score Attack: A Lower Bound Technique for Optimal Differentially Private Learningcited by 21
  9. 2021Differentially-Private Clustering of Easy Instancescited by 17
  10. 2023Better and Simpler Lower Bounds for Differentially Private Statistical Estimationcited by 17
  11. 2021Privately Learning Mixtures of Axis-Aligned Gaussianscited by 13
  12. 2022Private High-Dimensional Hypothesis Testingcited by 12
  13. 2023A Bias-Accuracy-Privacy Trilemma for Statistical Estimationcited by 12
  14. 2024A Huber Loss Minimization Approach to Mean Estimation under User-level Differential Privacycited by 11
  15. 2024Optimal Federated Learning for Nonparametric Regression with Heterogeneous Distributed Differential Privacy Constraintscited by 10
  16. 2023Mean estimation in the add-remove model of differential privacycited by 9
  17. 2022Differentially Private ℓ1-norm Linear Regression with Heavy-tailed Datacited by 8
  18. 2022Instance-Optimal Differentially Private Estimationcited by 7
  19. 2025Towards hyperparameter-free optimization with differential privacycited by 7
  20. 2022Nonparametric extensions of randomized response for private confidence setscited by 6
  21. 2023On Private and Robust Banditscited by 6
  22. 2023PLAN: Variance-Aware Private Mean Estimationcited by 6
  23. 2024Federated Nonparametric Hypothesis Testing with Differential Privacy Constraints: Optimal Rates and Adaptive Testscited by 6
  24. 2022Continual Mean Estimation Under User-Level Privacycited by 5
  25. 2023A Polynomial Time, Pure Differentially Private Estimator for Binary Product Distributionscited by 5
  26. 2023Private Federated Learning with Autotuned Compressioncited by 5
  27. 2022Algorithms for bounding contribution for histogram estimation under user-level privacycited by 4
  28. 2023Differentially Private Episodic Reinforcement Learning with Heavy-tailed Rewardscited by 4
  29. 2023Data Structures for Density Estimationcited by 4
  30. 2023Improved Analysis of Sparse Linear Regression in Local Differential Privacy Modelcited by 4
  31. 2023A Simple and Practical Method for Reducing the Disparate Impact of Differential Privacycited by 4
  32. 2024Distribution Learnability and Robustnesscited by 4
  33. 2022Private Stochastic Optimization With Large Worst-Case Lipschitz Parametercited by 3
  34. 2023Subset-Based Instance Optimality in Private Estimationcited by 3
  35. 2023Striking a Balance: An Optimal Mechanism Design for Heterogenous Differentially Private Data Acquisition for Logistic Regressioncited by 3
  36. 2023Sample-Optimal Locally Private Hypothesis Selection and the Provable Benefits of Interactivitycited by 3
  37. 2026Harnessing Synthetic Data from Generative AI for Statistical Inferencecited by 3
  38. 2021High-Dimensional Differentially-Private EM Algorithm: Methods and Near-Optimal Statistical Guaranteescited by 2

50 most cited of 73 All 73 (JSON)