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.

Corrected version; 61 pages, 4 figures, including supplementary material