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.

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

References in corpus (12)

• Targeted Backdoor Attacks on Deep Learning Systems Using Data Poisoning
• Privacy Loss in Apple's Implementation of Differential Privacy on MacOS 10.12
• Recent Advances in Algorithmic High-Dimensional Robust Statistics
• Robust Regression via Hard Thresholding
• Privacy and Statistical Risk: Formalisms and Minimax Bounds
• Robustly Learning any Clusterable Mixture of Gaussians
• Faster Algorithms for High-Dimensional Robust Covariance Estimation
• Globally-convergent Iteratively Reweighted Least Squares for Robust Regression Problems
• On the Sample Complexity of Privately Learning Unbounded High-Dimensional Gaussians
• Robust Sub-Gaussian Principal Component Analysis and Width-Independent Schatten Packing
• Private Center Points and Learning of Halfspaces
• 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