The Cost of Privacy: Rates of Convergence for Parameter Estimation with Differential Privacy

Abstract

We study the minimax cost of $(\epsilon ,\delta )$-differential privacy for mean estimation and Gaussian linear regression in low and high dimensions. For low-dimensional mean estimation, a resampling reduction to fingerprinting yields the privacy contribution $d^2\log (1/\delta )/(n^2{\epsilon }^2)$ in the stated polynomial-$\delta$ regime. For low-dimensional regression, a tracing argument gives the contribution $d^2/(n^2{\epsilon }^2)$ under an explicit approximate-DP remainder condition. For sparse mean estimation and sparse regression, a constant-weight packing and a private Fano lemma produce an effective privacy entropy of order $\min \{s\log (ed/s),[\log ((e^{\epsilon }-1)/\delta ){]}_{+}\}$ for $\delta >0$, up to universal constants and a fixed threshold; for pure DP it is $s\log (ed/s)$. Thus, when $\delta$ is polynomially smaller than $\epsilon$, the pure-DP dependence is retained up to polylogarithmic factors whenever the effective dimension is polylogarithmic in $n$, including regimes with $\epsilon =o(1)$. Coordinatewise-clipping estimators for means and split-sample noisy-gradient estimators for regression attain the lower bounds up to explicit logarithmic factors. Simulations and data examples illustrate related implementations.

arXiv commentCorrected version; 61 pages, 4 figures, including supplementary material

References in corpus (10)

• Deep Learning with Differential Privacy
• Renyi Differential Privacy
• A Unified Framework for High-Dimensional Analysis of M-Estimators with Decomposable Regularizers
• Gaussian Differential Privacy
• Privacy for Free: Posterior Sampling and Stochastic Gradient Monte Carlo
• Private Stochastic Convex Optimization with Optimal Rates
• On Iterative Hard Thresholding Methods for High-dimensional M-Estimation
• CoinPress: Practical Private Mean and Covariance Estimation
• Privacy-preserving Prediction
• Differentially Private False Discovery Rate Control

Cited by in corpus (27)

• Gaussian Differential Privacy
• Private Mean Estimation of Heavy-Tailed Distributions
• Privately Learning High-Dimensional Distributions
• CoinPress: Practical Private Mean and Covariance Estimation
• Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanism
• A Primer on Private Statistics
• Privacy Preserving Set-Based Estimation Using Partially Homomorphic Encryption
• Large Scale Private Learning via Low-rank Reparametrization
• Propose, Test, Release: Differentially private estimation with high probability
• The Cost of Privacy in Generalized Linear Models: Algorithms and Minimax Lower Bounds
• 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
• Private Identity Testing for High-Dimensional Distributions
• Wide Network Learning with Differential Privacy
• Differentially Private Assouad, Fano, and Le Cam
• Differential privacy and robust statistics in high dimensions
• A Private and Computationally-Efficient Estimator for Unbounded Gaussians
• Privately Learning Markov Random Fields
• Differentially private depth functions and their associated medians
• Statistical Inference in the Differential Privacy Model
• Median regression with differential privacy
• Universal Private Estimators
• Privately Learning Mixtures of Axis-Aligned Gaussians
• High-Dimensional Differentially-Private EM Algorithm: Methods and Near-Optimal Statistical Guarantees
• Learning with User-Level Privacy
• Improved Complexities for Stochastic Conditional Gradient Methods under Interpolation-like Conditions