Differential privacy

Definition#

A randomised mechanism $\mathcal{M}$ with domain $\mathcal{D}$ and range $\mathcal{R}$ satisfies $(\varepsilon, \delta)$-differential privacy if for all neighbouring datasets $D, D'$ differing in one record, and all measurable $S \subseteq \mathcal{R}$:

$$ \Pr[\mathcal{M}(D) \in S] \;\le\; e^{\varepsilon} \Pr[\mathcal{M}(D') \in S] + \delta $$

• $\varepsilon \ge 0$ — the privacy loss parameter; smaller is stronger.
• $\delta \ge 0$ — the probability of the guarantee failing outright. Convention requires $\delta \ll 1/n$, since $\delta = 1/n$ admits a mechanism that publishes a random record in full.
• Neighbouring — under add/remove adjacency, $|D \triangle D'| = 1$; under replace-one, $|D| = |D'|$ and they differ in one entry. The two give different constants and are frequently conflated in papers.

$\delta = 0$ is pure $\varepsilon$-DP.

Properties that make it usable#

Post-processing immunity. For any function $g$, if $\mathcal{M}$ is $(\varepsilon,\delta)$-DP then $g \circ \mathcal{M}$ is too. No downstream analysis can undo the guarantee.

Group privacy. A group of $k$ correlated individuals is protected at $k\varepsilon$. This degrades quickly, which matters when records are not independent — families, repeated visits, one user with many rows.

Composition. Basic: $k$ mechanisms at $\varepsilon_i$ compose to $\sum_i \varepsilon_i$. Advanced (Dwork, Rothblum, Vadhan, 2010): for $k$ mechanisms each $(\varepsilon, \delta)$-DP, the composition is $(\varepsilon', k\delta + \delta')$-DP with

$$ \varepsilon' = \sqrt{2k \ln(1/\delta')}\,\varepsilon + k\varepsilon(e^{\varepsilon} - 1) $$

The $\sqrt{k}$ leading term is what makes iterative training tractable.

Mechanisms#

Laplace. For $f: \mathcal{D} \to \mathbb{R}^k$ with $\ell_1$-sensitivity $\Delta_1 f = \max_{D \sim D'} |f(D) - f(D')|_1$, releasing $f(D) + \text{Lap}(\Delta_1 f / \varepsilon)^k$ is $\varepsilon$-DP.

Gaussian. For $\ell_2$-sensitivity $\Delta_2 f$, adding $\mathcal{N}(0, \sigma^2)$ with $\sigma \ge \Delta_2 f \sqrt{2\ln(1.25/\delta)}/\varepsilon$ gives $(\varepsilon,\delta)$-DP for $\varepsilon < 1$. Balle and Wang (2018) give the exact analytic calibration, which is tighter and valid for all $\varepsilon$.

Exponential. For non-numeric outputs with a utility function $u(D, r)$, sample $r$ with probability $\propto \exp(\varepsilon u(D,r) / (2\Delta u))$.

Rényi DP and the moments accountant#

Composition under $(\varepsilon,\delta)$-DP is lossy. Mironov (2017) defines $(\alpha, \bar\varepsilon)$-RDP via the Rényi divergence of order $\alpha$:

$$ D_\alpha\big(\mathcal{M}(D) \,|\, \mathcal{M}(D')\big) \le \bar\varepsilon $$

RDP composes by simple addition of $\bar\varepsilon$ at fixed $\alpha$, and converts to $(\varepsilon,\delta)$-DP at the end. Abadi et al. (2016) introduced the equivalent moments accountant, which reduced the reported epsilon for deep learning by roughly an order of magnitude versus advanced composition — the result that made DP deep learning practical.

Privacy amplification by subsampling is the other essential ingredient: running an $\varepsilon$-DP mechanism on a random $q$-fraction of the data yields roughly $O(q\varepsilon)$-DP. Sampling is not a Poisson formality here; the accountant's correctness depends on the sampling scheme actually implemented matching the one assumed.

DP-SGD#

Per step: sample a lot by Poisson sampling with rate $q$; compute per-example gradients $g_i$; clip $\bar g_i = g_i / \max(1, |g_i|_2 / C)$; release $\frac{1}{L}\left(\sum_i \bar g_i + \mathcal{N}(0, \sigma^2 C^2 I)\right)$.

Empirical findings that reliably transfer:

• Large batches help. The signal-to-noise ratio of the averaged gradient improves with lot size, and the sampling rate is accounted separately.
• The clipping norm matters more than the learning rate. Tune $C$ first; a common heuristic is the median per-example gradient norm.
• Pretraining transforms the trade-off. De et al. (2022) show that DP fine-tuning of a publicly pretrained model reaches accuracy close to non-private baselines at moderate $\varepsilon$, whereas DP training from scratch on the same task does not.
• Cost falls on the tail. Bagdasaryan et al. (2019) show DP-SGD degrades accuracy disproportionately on under-represented subgroups. Privacy and fairness interact adversarially, and reporting only aggregate accuracy hides it.

What epsilon values mean in practice#

There is no consensus threshold, and honest reporting acknowledges that. Deployed examples span a wide range: the 2020 US Census used a per-attribute budget in the low tens; Apple has reported per-day, per-use-case budgets in the single digits to low tens; academic work on image classification commonly reports $\varepsilon \in [1, 8]$.

Two cautions. Epsilons are not comparable across different adjacency definitions, granularities (record versus user), or accounting methods. And the guarantee is worst-case over all adversaries, so a large formal $\varepsilon$ can still correspond to a small empirical attack success — which is an argument for reporting both, not for reporting neither.

Papers#

• Dwork, McSherry, Nissim and Smith, Calibrating Noise to Sensitivity in Private Data Analysis, TCC 2006
• Dwork and Roth, The Algorithmic Foundations of Differential Privacy, 2014 — the standard reference text
• Abadi et al., Deep Learning with Differential Privacy, CCS 2016 — arxiv.org/abs/1607.00133
• Mironov, Rényi Differential Privacy, CSF 2017 — arxiv.org/abs/1702.07476
• Balle and Wang, Improving the Gaussian Mechanism, ICML 2018 — arxiv.org/abs/1805.06530
• De et al., Unlocking High-Accuracy Differentially Private Image Classification through Scale, 2022 — arxiv.org/abs/2204.13650
• Bagdasaryan, Poursaeed and Shmatikov, Differential Privacy Has Disparate Impact on Model Accuracy, NeurIPS 2019
• Warner, Randomized Response, JASA 1965 — the original mechanism

What to learn next#

• Federated learning — the other half of the private-training story.
• Privacy in machine learning — the attacks this defends against.
• Probability — the distributions the noise is drawn from.