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

arXiv: https://arxiv.org/abs/1902.04495 · HTML: https://mlsanity.com/paper/1902.04495/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Feb 2019.

## Built on by (most cited first, 2 of 2)

- [Differential privacy and robust statistics in high dimensions](https://mlsanity.com/paper/2111.06578/) (2021)
- [Differentially Private Federated Learning: Servers Trustworthiness, Estimation, and Statistical Inference](https://mlsanity.com/paper/2404.16287/) (2024)

## Abstract (arXiv)

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.