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

We study the minimax cost of (varepsilon,δ)-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 d2log(1/δ)/(n2varepsilon2) in the stated polynomial-δ regime. For low-dimensional regression, a tracing argument gives the contribution d2/(n2varepsilon2) 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 minslog(ed/s),[log((e^varepsilon-1)/δ)]_+ for δ>0, up to universal constants and a fixed threshold; for pure DP it is slog(ed/s). Thus, when δ is polynomially smaller than varepsilon, the pure-DP dependence is retained up to polylogarithmic factors whenever the effective dimension is polylogarithmic in n, including regimes with varepsilon=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.