Robust and Differentially Private Mean Estimation

Abstract

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.

arXiv comment58 pages, 2 figures, both exponential time and efficient algorithms no longer require a known bound on the true mean

References in corpus (25)

• Deep Learning with Differential Privacy
• Targeted Backdoor Attacks on Deep Learning Systems Using Data Poisoning
• Is feature selection secure against training data poisoning?
• Privacy Loss in Apple's Implementation of Differential Privacy on MacOS 10.12
• Sever: A Robust Meta-Algorithm for Stochastic Optimization
• Recent Advances in Algorithmic High-Dimensional Robust Statistics
• Robust Regression via Hard Thresholding
• Being Robust (in High Dimensions) Can Be Practical
• Privacy and Statistical Risk: Formalisms and Minimax Bounds
• The Cost of Privacy: Rates of Convergence for Parameter Estimation with Differential Privacy
• Private Mean Estimation of Heavy-Tailed Distributions
• High Dimensional Robust Sparse Regression
• Privately Learning High-Dimensional Distributions
• Generalized Resilience and Robust Statistics
• CoinPress: Practical Private Mean and Covariance Estimation
• Robustly Learning any Clusterable Mixture of Gaussians
• Faster Algorithms for High-Dimensional Robust Covariance Estimation
• On the Sample Complexity of Privately Learning Unbounded High-Dimensional Gaussians
• Globally-convergent Iteratively Reweighted Least Squares for Robust Regression Problems
• Robust Sub-Gaussian Principal Component Analysis and Width-Independent Schatten Packing
• Private Center Points and Learning of Halfspaces
• When does the Tukey median work?
• Robustly Clustering a Mixture of Gaussians
• Privately Learning Markov Random Fields
• Designing Differentially Private Estimators in High Dimensions

Cited by in corpus (9)

• Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanism
• SPECTRE: Defending Against Backdoor Attacks Using Robust Statistics
• Covariance-Aware Private Mean Estimation Without Private Covariance Estimation
• Optimal Rates of (Locally) Differentially Private Heavy-tailed Multi-Armed Bandits
• Differential privacy and robust statistics in high dimensions
• A Private and Computationally-Efficient Estimator for Unbounded Gaussians
• Private and polynomial time algorithms for learning Gaussians and beyond
• Bayesian Sensitivity Analysis for Missing Data Using the E-value
• Privately Learning Mixtures of Axis-Aligned Gaussians