mlsanityData to 7 Oct 2026

Instance-optimal Mean Estimation Under Differential Privacy

arXiv 2106.00463 ↗First posted 1 Jun 2021cs.CR cs.DS stat.MEcited by 37

Not on the map. Why?

Abstract (arXiv)

Mean estimation under differential privacy is a fundamental problem, but worst-case optimal mechanisms do not offer meaningful utility guarantees in practice when the global sensitivity is very large. Instead, various heuristics have been proposed to reduce the error on real-world data that do not resemble the worst-case instance. This paper takes a principled approach, yielding a mechanism that is instance-optimal in a strong sense. In addition to its theoretical optimality, the mechanism is also simple and practical, and adapts to a variety of data characteristics without the need of parameter tuning. It easily extends to the local and shuffle model as well.

Key facts. Cited by 37 papers in the map (data through 7 Oct 2026). First posted on arXiv 1 Jun 2021.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 6; 2022: 3; 2023: 12; 2024: 5; 2025: 6; 2026: 5.

37 papers.

Sort:

  1. 2021Differential privacy and robust statistics in high dimensionscited by 64
  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. 2021FriendlyCore: Practical Differentially Private Aggregationcited by 34
  5. 2021A Private and Computationally-Efficient Estimator for Unbounded Gaussianscited by 34
  6. 2022New Lower Bounds for Private Estimation and a Generalized Fingerprinting Lemmacited by 32
  7. 2021Tight and Robust Private Mean Estimation with Few Userscited by 26
  8. 2023Better and Simpler Lower Bounds for Differentially Private Statistical Estimationcited by 16
  9. 2022Differentially Private Covariance Revisitedcited by 15
  10. 2023A Bias-Accuracy-Privacy Trilemma for Statistical Estimationcited by 12
  11. 2023A Fast Algorithm for Adaptive Private Mean Estimationcited by 11
  12. 2024A Huber Loss Minimization Approach to Mean Estimation under User-level Differential Privacycited by 11
25 more
  1. 2023Exact Optimality of Communication-Privacy-Utility Tradeoffs in Distributed Mean Estimationcited by 9
  2. 2023Mean estimation in the add-remove model of differential privacycited by 9
  3. 2023PLAN: Variance-Aware Private Mean Estimationcited 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. 2023Finite-Sample Symmetric Mean Estimation with Fisher Information Ratecited by 5
  7. 2022Algorithms for bounding contribution for histogram estimation under user-level privacycited by 4
  8. 2023Optimality in Mean Estimation: Beyond Worst-Case, Beyond Sub-Gaussian, and Beyond 1+α Momentscited by 4
  9. 2024Correlated Privacy Mechanisms for Differentially Private Distributed Mean Estimationcited by 4
  10. 2023General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean Estimationcited by 3
  11. 2023Subset-Based Instance Optimality in Private Estimationcited by 3
  12. 2024Learning with User-Level Local Differential Privacycited by 3
  13. 2023The importance of feature preprocessing for differentially private linear optimizationcited by 2
  14. 2025Tukey Depth Mechanisms for Practical Private Mean Estimationcited by 2
  15. 2025Federated Learning of Quantile Inference under Local Differential Privacycited by 2
  16. 2024Differential Private Stochastic Optimization with Heavy-tailed Data: Towards Optimal Ratescited by 1
  17. 2025Optimal Differentially Private Sampling of Unbounded Gaussianscited by 1
  18. 2025On Theoretical Limits of Learning with Label Differential Privacycited by 0
  19. 2025Differentially Private Conformal Prediction via Quantile Binary Searchcited by 0
  20. 2025Privately Estimating Black-Box Statisticscited by 0
  21. 2026Near-Optimal Private Tests for Simple and MLR Hypothesescited by 0
  22. 2026Jacobian-Guided Anisotropic Noise Reshaping for Enhancing Representation Utility under Local Differential Privacycited by 0
  23. 2026Lumberjack: Better Differentially Private Random Forests through Heavy Hitter Detection in Treescited by 0
  24. 2026Computationally tractable robust differentially private mean estimationcited by 0
  25. 2026Robust Estimation of Sparse Numerical Vectors under Local Differential Privacycited by 0