# Instance-optimal Mean Estimation Under Differential Privacy

arXiv: https://arxiv.org/abs/2106.00463 · HTML: https://mlsanity.com/paper/2106.00463/

## Key facts

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

## Built on by (most cited first, 30 of 37)

- [Differential privacy and robust statistics in high dimensions](https://mlsanity.com/paper/2111.06578/) (2021)
- [Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanism](https://mlsanity.com/paper/2111.12981/) (2021)
- [Covariance-Aware Private Mean Estimation Without Private Covariance Estimation](https://mlsanity.com/paper/2106.13329/) (2021)
- [FriendlyCore: Practical Differentially Private Aggregation](https://mlsanity.com/paper/2110.10132/) (2021)
- [A Private and Computationally-Efficient Estimator for Unbounded Gaussians](https://mlsanity.com/paper/2111.04609/) (2021)
- [New Lower Bounds for Private Estimation and a Generalized Fingerprinting Lemma](https://mlsanity.com/paper/2205.08532/) (2022)
- [Tight and Robust Private Mean Estimation with Few Users](https://mlsanity.com/paper/2110.11876/) (2021)
- [Better and Simpler Lower Bounds for Differentially Private Statistical Estimation](https://mlsanity.com/paper/2310.06289/) (2023)
- [Differentially Private Covariance Revisited](https://mlsanity.com/paper/2205.14324/) (2022)
- [A Bias-Accuracy-Privacy Trilemma for Statistical Estimation](https://mlsanity.com/paper/2301.13334/) (2023)
- [A Fast Algorithm for Adaptive Private Mean Estimation](https://mlsanity.com/paper/2301.07078/) (2023)
- [A Huber Loss Minimization Approach to Mean Estimation under User-level Differential Privacy](https://mlsanity.com/paper/2405.13453/) (2024)
- [Exact Optimality of Communication-Privacy-Utility Tradeoffs in Distributed Mean Estimation](https://mlsanity.com/paper/2306.04924/) (2023)
- [Mean estimation in the add-remove model of differential privacy](https://mlsanity.com/paper/2312.06658/) (2023)
- [PLAN: Variance-Aware Private Mean Estimation](https://mlsanity.com/paper/2306.08745/) (2023)
- [Dimension-free Private Mean Estimation for Anisotropic Distributions](https://mlsanity.com/paper/2411.00775/) (2024)
- [A Polynomial Time, Pure Differentially Private Estimator for Binary Product Distributions](https://mlsanity.com/paper/2304.06787/) (2023)
- [Finite-Sample Symmetric Mean Estimation with Fisher Information Rate](https://mlsanity.com/paper/2306.16573/) (2023)
- [Algorithms for bounding contribution for histogram estimation under user-level privacy](https://mlsanity.com/paper/2206.03008/) (2022)
- [Optimality in Mean Estimation: Beyond Worst-Case, Beyond Sub-Gaussian, and Beyond 1+α Moments](https://mlsanity.com/paper/2311.12784/) (2023)
- [Correlated Privacy Mechanisms for Differentially Private Distributed Mean Estimation](https://mlsanity.com/paper/2407.03289/) (2024)
- [General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean Estimation](https://mlsanity.com/paper/2301.13850/) (2023)
- [Subset-Based Instance Optimality in Private Estimation](https://mlsanity.com/paper/2303.01262/) (2023)
- [Learning with User-Level Local Differential Privacy](https://mlsanity.com/paper/2405.17079/) (2024)
- [The importance of feature preprocessing for differentially private linear optimization](https://mlsanity.com/paper/2307.11106/) (2023)
- [Tukey Depth Mechanisms for Practical Private Mean Estimation](https://mlsanity.com/paper/2502.18698/) (2025)
- [Federated Learning of Quantile Inference under Local Differential Privacy](https://mlsanity.com/paper/2509.21800/) (2025)
- [Differential Private Stochastic Optimization with Heavy-tailed Data: Towards Optimal Rates](https://mlsanity.com/paper/2408.09891/) (2024)
- [On Theoretical Limits of Learning with Label Differential Privacy](https://mlsanity.com/paper/2502.14309/) (2025)
- [Optimal Differentially Private Sampling of Unbounded Gaussians](https://mlsanity.com/paper/2503.01766/) (2025)

## 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.