# Robust and Differentially Private Mean Estimation

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

## Key facts

- Cited by 66 papers in the map (data through 14 Oct 2026).
- Builds on 61 of its 89 references that are in the map.
- First posted on arXiv 18 Feb 2021.

## Builds on (most cited first, 30 of 61)

- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Targeted Backdoor Attacks on Deep Learning Systems Using Data Poisoning](https://mlsanity.com/paper/1712.05526/) (2017)
- [The Composition Theorem for Differential Privacy](https://mlsanity.com/paper/1311.0776/) (2013)
- [RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response](https://mlsanity.com/paper/1407.6981/) (2014)
- [Robust Estimators in High Dimensions without the Computational Intractability](https://mlsanity.com/paper/1604.06443/) (2016)
- [Agnostic Estimation of Mean and Covariance](https://mlsanity.com/paper/1604.06968/) (2016)
- [Sever: A Robust Meta-Algorithm for Stochastic Optimization](https://mlsanity.com/paper/1803.02815/) (2018)
- [Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures](https://mlsanity.com/paper/1611.03473/) (2016)
- [Finite Sample Differentially Private Confidence Intervals](https://mlsanity.com/paper/1711.03908/) (2017)
- [Privately Learning High-Dimensional Distributions](https://mlsanity.com/paper/1805.00216/) (2018)
- [Recent Advances in Algorithmic High-Dimensional Robust Statistics](https://mlsanity.com/paper/1911.05911/) (2019)
- [Is feature selection secure against training data poisoning?](https://mlsanity.com/paper/1804.07933/) (2018)
- [Learning from Untrusted Data](https://mlsanity.com/paper/1611.02315/) (2016)
- [Being Robust (in High Dimensions) Can Be Practical](https://mlsanity.com/paper/1703.00893/) (2017)
- [Mixture Models, Robustness, and Sum of Squares Proofs](https://mlsanity.com/paper/1711.07454/) (2017)
- [Robust Estimation via Robust Gradient Estimation](https://mlsanity.com/paper/1802.06485/) (2018)
- [Efficient Algorithms and Lower Bounds for Robust Linear Regression](https://mlsanity.com/paper/1806.00040/) (2018)
- [CoinPress: Practical Private Mean and Covariance Estimation](https://mlsanity.com/paper/2006.06618/) (2020)
- [Private Mean Estimation of Heavy-Tailed Distributions](https://mlsanity.com/paper/2002.09464/) (2020)
- [Efficient Algorithms for Outlier-Robust Regression](https://mlsanity.com/paper/1803.03241/) (2018)
- [List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussians](https://mlsanity.com/paper/1711.07211/) (2017)
- [Private Hypothesis Selection](https://mlsanity.com/paper/1905.13229/) (2019)
- [Sub-Gaussian estimators of the mean of a random vector](https://mlsanity.com/paper/1702.00482/) (2017)
- [Robust and Heavy-Tailed Mean Estimation Made Simple, via Regret Minimization](https://mlsanity.com/paper/2007.15839/) (2020)
- [Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers](https://mlsanity.com/paper/1703.04940/) (2017)
- [Privacy Loss in Apple's Implementation of Differential Privacy on MacOS 10.12](https://mlsanity.com/paper/1709.02753/) (2017)
- [List-Decodable Linear Regression](https://mlsanity.com/paper/1905.05679/) (2019)
- [Quantum Entropy Scoring for Fast Robust Mean Estimation and Improved Outlier Detection](https://mlsanity.com/paper/1906.11366/) (2019)
- [Robust Meta-learning for Mixed Linear Regression with Small Batches](https://mlsanity.com/paper/2006.09702/) (2020)

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

- [SPECTRE: Defending Against Backdoor Attacks Using Robust Statistics](https://mlsanity.com/paper/2104.11315/) (2021)
- [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)
- [Robustness Implies Privacy in Statistical Estimation](https://mlsanity.com/paper/2212.05015/) (2022)
- [Covariance-Aware Private Mean Estimation Without Private Covariance Estimation](https://mlsanity.com/paper/2106.13329/) (2021)
- [High Dimensional Differentially Private Stochastic Optimization with Heavy-tailed Data](https://mlsanity.com/paper/2107.11136/) (2021)
- [Private and polynomial time algorithms for learning Gaussians and beyond](https://mlsanity.com/paper/2111.11320/) (2021)
- [Private Robust Estimation by Stabilizing Convex Relaxations](https://mlsanity.com/paper/2112.03548/) (2021)
- [A Private and Computationally-Efficient Estimator for Unbounded Gaussians](https://mlsanity.com/paper/2111.04609/) (2021)
- [From Robustness to Privacy and Back](https://mlsanity.com/paper/2302.01855/) (2023)
- [Tight and Robust Private Mean Estimation with Few Users](https://mlsanity.com/paper/2110.11876/) (2021)
- [Optimal Rates of (Locally) Differentially Private Heavy-tailed Multi-Armed Bandits](https://mlsanity.com/paper/2106.02575/) (2021)
- [Privacy Induces Robustness: Information-Computation Gaps and Sparse Mean Estimation](https://mlsanity.com/paper/2211.00724/) (2022)
- [DP-PCA: Statistically Optimal and Differentially Private PCA](https://mlsanity.com/paper/2205.13709/) (2022)
- [On the Privacy-Robustness-Utility Trilemma in Distributed Learning](https://mlsanity.com/paper/2302.04787/) (2023)
- [Easy Differentially Private Linear Regression](https://mlsanity.com/paper/2208.07353/) (2022)
- [Polynomial Time and Private Learning of Unbounded Gaussian Mixture Models](https://mlsanity.com/paper/2303.04288/) (2023)
- [Better and Simpler Lower Bounds for Differentially Private Statistical Estimation](https://mlsanity.com/paper/2310.06289/) (2023)
- [Privately Learning Mixtures of Axis-Aligned Gaussians](https://mlsanity.com/paper/2106.02162/) (2021)
- [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)
- [Differentially Private Regression with Unbounded Covariates](https://mlsanity.com/paper/2202.11199/) (2022)
- [Near Optimal Private and Robust Linear Regression](https://mlsanity.com/paper/2301.13273/) (2023)
- [Mean estimation in the add-remove model of differential privacy](https://mlsanity.com/paper/2312.06658/) (2023)
- [Differentially Private ℓ1-norm Linear Regression with Heavy-tailed Data](https://mlsanity.com/paper/2201.03204/) (2022)
- [Towards Trustworthy Federated Learning with Untrusted Participants](https://mlsanity.com/paper/2505.01874/) (2025)
- [Insufficient Statistics Perturbation: Stable Estimators for Private Least Squares](https://mlsanity.com/paper/2404.15409/) (2024)
- [Dimension-free Private Mean Estimation for Anisotropic Distributions](https://mlsanity.com/paper/2411.00775/) (2024)
- [Robust Estimation of Discrete Distributions under Local Differential Privacy](https://mlsanity.com/paper/2202.06825/) (2022)

## Abstract (arXiv)

In statistical learning and analysis from shared data, which is increasingly widely adopted in platforms such as federated learning and meta-learning, there are two major concerns: privacy and robustness. Each participating individual should be able to contribute without the fear of leaking one's sensitive information. At the same time, the system should be robust in the presence of malicious participants inserting corrupted data. Recent algorithmic advances in learning from shared data focus on either one of these threats, leaving the system vulnerable to the other. We bridge this gap for the canonical problem of estimating the mean from i.i.d. samples. We introduce PRIME, which is the first efficient algorithm that achieves both privacy and robustness for a wide range of distributions. We further complement this result with a novel exponential time algorithm that improves the sample complexity of PRIME, achieving a near-optimal guarantee and matching a known lower bound for (non-robust) private mean estimation. This proves that there is no extra statistical cost to simultaneously guaranteeing privacy and robustness.