mlsanityData to 14 Oct 2026

Robust and Differentially Private Mean Estimation

arXiv 2102.09159 ↗First posted 18 Feb 2021cs.LG cs.CR cs.ITcited by 66

Not on the map. Why?

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.

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

61 of 89 references.

References · 61

  1. 2019Advances and Open Problems in Federated Learningcited by 3,046
  2. 2016Deep Learning with Differential Privacycited by 2,728
  3. 2017Targeted Backdoor Attacks on Deep Learning Systems Using Data Poisoningcited by 1,055
  4. 2013The Composition Theorem for Differential Privacycited by 297
  5. 2014RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Responsecited by 272
  6. 2016Robust Estimators in High Dimensions without the Computational Intractabilitycited by 209
  7. 2016Agnostic Estimation of Mean and Covariancecited by 131
  8. 2018Sever: A Robust Meta-Algorithm for Stochastic Optimizationcited by 125
  9. 2016Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixturescited by 115
  10. 2017Finite Sample Differentially Private Confidence Intervalscited by 104
  11. 2018Privately Learning High-Dimensional Distributionscited by 104
  12. 2019Recent Advances in Algorithmic High-Dimensional Robust Statisticscited by 101
38 more
  1. 2018Is feature selection secure against training data poisoning?cited by 93
  2. 2016Learning from Untrusted Datacited by 90
  3. 2017Being Robust (in High Dimensions) Can Be Practicalcited by 83
  4. 2017Mixture Models, Robustness, and Sum of Squares Proofscited by 81
  5. 2018Robust Estimation via Robust Gradient Estimationcited by 76
  6. 2018Efficient Algorithms and Lower Bounds for Robust Linear Regressioncited by 76
  7. 2020CoinPress: Practical Private Mean and Covariance Estimationcited by 74
  8. 2020Private Mean Estimation of Heavy-Tailed Distributionscited by 73
  9. 2018Efficient Algorithms for Outlier-Robust Regressioncited by 72
  10. 2017List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussianscited by 70
  11. 2019Private Hypothesis Selectioncited by 60
  12. 2017Sub-Gaussian estimators of the mean of a random vectorcited by 47
  13. 2020Robust and Heavy-Tailed Mean Estimation Made Simple, via Regret Minimizationcited by 44
  14. 2017Resilience: A Criterion for Learning in the Presence of Arbitrary Outlierscited by 43
  15. 2017Privacy Loss in Apple's Implementation of Differential Privacy on MacOS 10.12cited by 43
  16. 2019List-Decodable Linear Regressioncited by 42
  17. 2019Quantum Entropy Scoring for Fast Robust Mean Estimation and Improved Outlier Detectioncited by 41
  18. 2020Robust Meta-learning for Mixed Linear Regression with Small Batchescited by 41
  19. 2020On the Sample Complexity of Privately Learning Unbounded High-Dimensional Gaussianscited by 41
  20. 2015Robust Regression via Hard Thresholdingcited by 39
  21. 2017Robustly Learning a Gaussian: Getting Optimal Error, Efficientlycited by 39
  22. 2018High-Dimensional Robust Mean Estimation in Nearly-Linear Timecited by 39
  23. 2019List Decodable Learning via Sum of Squarescited by 37
  24. 2019Robust subgaussian estimation of a mean vector in nearly linear timecited by 37
  25. 2019Generalized Resilience and Robust Statisticscited by 37
  26. 2020Robust Sub-Gaussian Principal Component Analysis and Width-Independent Schatten Packingcited by 35
  27. 2015Simultaneous Private Learning of Multiple Conceptscited by 34
  28. 2018Mean Estimation with Sub-Gaussian Rates in Polynomial Timecited by 33
  29. 2019Outlier-robust estimation of a sparse linear model using ℓ1-penalized Huber's M-estimatorcited by 31
  30. 2019Privately Learning Thresholds: Closing the Exponential Gapcited by 31
  31. 2018High Dimensional Robust Sparse Regressioncited by 29
  32. 2019Faster Algorithms for High-Dimensional Robust Covariance Estimationcited by 28
  33. 2020Robustly Learning any Clusterable Mixture of Gaussianscited by 28
  34. 2019Differentially Private Algorithms for Learning Mixtures of Separated Gaussianscited by 27
  35. 2017Robust Regression via Mutivariate Regression Depthcited by 20
  36. 2020List Decodable Mean Estimation in Nearly Linear Timecited by 20
  37. 2015Building a RAPPOR with the Unknown: Privacy-Preserving Learning of Associations and Data Dictionariescited by 16
  38. 2019How Hard Is Robust Mean Estimation?cited by 16

50 most cited of 61 All 61 (JSON)

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 11; 2022: 12; 2023: 21; 2024: 11; 2025: 9; 2026: 2.

66 papers.

Sort:

By area:

  1. 2021SPECTRE: Defending Against Backdoor Attacks Using Robust Statisticscited by 130
  2. 2021Differential privacy and robust statistics in high dimensionscited by 64
  3. 2021Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanismcited by 50
  4. 2022Robustness Implies Privacy in Statistical Estimationcited by 47
  5. 2021Covariance-Aware Private Mean Estimation Without Private Covariance Estimationcited by 46
  6. 2021High Dimensional Differentially Private Stochastic Optimization with Heavy-tailed Datacited by 42
  7. 2021Private and polynomial time algorithms for learning Gaussians and beyondcited by 39
  8. 2021Private Robust Estimation by Stabilizing Convex Relaxationscited by 38
  9. 2021A Private and Computationally-Efficient Estimator for Unbounded Gaussianscited by 34
  10. 2023From Robustness to Privacy and Backcited by 27
  11. 2021Tight and Robust Private Mean Estimation with Few Userscited by 26
  12. 2021Optimal Rates of (Locally) Differentially Private Heavy-tailed Multi-Armed Banditscited by 25
38 more
  1. 2022Privacy Induces Robustness: Information-Computation Gaps and Sparse Mean Estimationcited by 25
  2. 2022DP-PCA: Statistically Optimal and Differentially Private PCAcited by 24
  3. 2023On the Privacy-Robustness-Utility Trilemma in Distributed Learningcited by 24
  4. 2022Easy Differentially Private Linear Regressioncited by 19
  5. 2023Polynomial Time and Private Learning of Unbounded Gaussian Mixture Modelscited by 19
  6. 2023Better and Simpler Lower Bounds for Differentially Private Statistical Estimationcited by 17
  7. 2021Privately Learning Mixtures of Axis-Aligned Gaussianscited by 13
  8. 2023A Bias-Accuracy-Privacy Trilemma for Statistical Estimationcited by 12
  9. 2023A Fast Algorithm for Adaptive Private Mean Estimationcited by 11
  10. 2024A Huber Loss Minimization Approach to Mean Estimation under User-level Differential Privacycited by 11
  11. 2022Differentially Private Regression with Unbounded Covariatescited by 10
  12. 2023Near Optimal Private and Robust Linear Regressioncited by 9
  13. 2023Mean estimation in the add-remove model of differential privacycited by 9
  14. 2022Differentially Private ℓ1-norm Linear Regression with Heavy-tailed Datacited by 8
  15. 2025Towards Trustworthy Federated Learning with Untrusted Participantscited by 8
  16. 2024Insufficient Statistics Perturbation: Stable Estimators for Private Least Squarescited by 7
  17. 2024Dimension-free Private Mean Estimation for Anisotropic Distributionscited by 6
  18. 2022Robust Estimation of Discrete Distributions under Local Differential Privacycited by 5
  19. 2023A Polynomial Time, Pure Differentially Private Estimator for Binary Product Distributionscited by 5
  20. 2023Private Federated Learning with Autotuned Compressioncited by 5
  21. 2023Mixtures of Gaussians are Privately Learnable with a Polynomial Number of Samplescited by 5
  22. 2022Renyi Differential Privacy of Propose-Test-Release and Applications to Private and Robust Machine Learningcited by 4
  23. 2022Lifelong Bandit Optimization: No Prior and No Regretcited by 4
  24. 2023Differentially Private Low-dimensional Synthetic Data from High-dimensional Datasetscited by 4
  25. 2023Data Minimization at Inference Timecited by 4
  26. 2023Differentially Private Episodic Reinforcement Learning with Heavy-tailed Rewardscited by 4
  27. 2023A Simple and Practical Method for Reducing the Disparate Impact of Differential Privacycited by 4
  28. 2024Distribution Learnability and Robustnesscited by 4
  29. 2022Scalable Collaborative Learning via Representation Sharingcited by 3
  30. 2023Differentially private projection-depth-based medianscited by 3
  31. 2024Not All Learnable Distribution Classes are Privately Learnablecited by 3
  32. 2024Learning with User-Level Local Differential Privacycited by 3
  33. 2025An Iterative Algorithm for Differentially Private k-PCA with Adaptive Noisecited by 3
  34. 2022Differentially private multivariate medianscited by 2
  35. 2023Personalized Privacy Auditing and Optimization at Test Timecited by 2
  36. 2023Learning Mixtures of Gaussians with Censored Datacited by 2
  37. 2024Private Edge Density Estimation for Random Graphs: Optimal, Efficient and Robustcited by 2
  38. 2024Agnostic Private Density Estimation for GMMs via List Global Stabilitycited by 2

50 most cited of 66 All 66 (JSON)