Differential privacy and robust statistics in high dimensions
arXiv:2111.06578
Abstract
We introduce a universal framework for characterizing the statistical efficiency of a statistical estimation problem with differential privacy guarantees. Our framework, which we call High-dimensional Propose-Test-Release (HPTR), builds upon three crucial components: the exponential mechanism, robust statistics, and the Propose-Test-Release mechanism. Gluing all these together is the concept of resilience, which is central to robust statistical estimation. Resilience guides the design of the algorithm, the sensitivity analysis, and the success probability analysis of the test step in Propose-Test-Release. The key insight is that if we design an exponential mechanism that accesses the data only via one-dimensional robust statistics, then the resulting local sensitivity can be dramatically reduced. Using resilience, we can provide tight local sensitivity bounds. These tight bounds readily translate into near-optimal utility guarantees in several cases. We give a general recipe for applying HPTR to a given instance of a statistical estimation problem and demonstrate it on canonical problems of mean estimation, linear regression, covariance estimation, and principal component analysis. We introduce a general utility analysis technique that proves that HPTR nearly achieves the optimal sample complexity under several scenarios studied in the literature.
References in corpus (24)
- Deep Learning with Differential Privacy
- Privacy for Free: Posterior Sampling and Stochastic Gradient Monte Carlo
- Beating Randomized Response on Incoherent Matrices
- Being Robust (in High Dimensions) Can Be Practical
- Privacy and Statistical Risk: Formalisms and Minimax Bounds
- Differentially Private Fine-tuning of Language Models
- The Cost of Privacy: Rates of Convergence for Parameter Estimation with Differential Privacy
- Privacy-preserving parametric inference: a case for robust statistics
- Private Mean Estimation of Heavy-Tailed Distributions
- Generalized Resilience and Robust Statistics
- Convergence Rates for Differentially Private Statistical Estimation
- CoinPress: Practical Private Mean and Covariance Estimation
- On the Theory and Practice of Privacy-Preserving Bayesian Data Analysis
- Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimation
- Propose, Test, Release: Differentially private estimation with high probability
- Optimal Robust Linear Regression in Nearly Linear Time
- Robust and Differentially Private Mean Estimation
- Covariance-Aware Private Mean Estimation Without Private Covariance Estimation
- On the Sample Complexity of Privately Learning Unbounded High-Dimensional Gaussians
- Differentially private sub-Gaussian location estimators
- Instance-optimal Mean Estimation Under Differential Privacy
- Robust Regression Revisited: Acceleration and Improved Estimation Rates
- Robust Sub-Gaussian Principal Component Analysis and Width-Independent Schatten Packing
- A Private and Computationally-Efficient Estimator for Unbounded Gaussians