Mironov 2017 - Renyi Differential Privacy - Overview

Summary

Mironov defines $(\alpha ,\epsilon )$-Renyi differential privacy (RDP): the Renyi divergence of order $\alpha$ between output distributions on adjacent inputs is at most $\epsilon$. RDP is a strictly stronger notion than $(\epsilon ,\delta )$-DP, generalizes pure DP (the case $\alpha =\infty$), composes by simply adding the curves $\alpha \mapsto \epsilon (\alpha )$, and makes the Gaussian mechanism trivial to analyze ($\epsilon (\alpha )=\alpha /(2{\sigma }^2)$ for unit sensitivity). It converts back to $(\epsilon ,\delta )$-DP via $\epsilon +\log (1/\delta )/(\alpha -1)$.

Overview

Problem. $(\epsilon ,\delta )$-DP fits poorly its two most common uses. A single Gaussian mechanism satisfies a whole curve of incomparable $(\epsilon (\delta ),\delta )$ guarantees, so reporting one point discards information. Advanced composition yields a combinatorial explosion of $(\epsilon ,\delta )$ choices, and optimal composition of heterogeneous mechanisms is P-hard (Murtagh and Vadhan).

Contribution. A privacy definition based on Renyi divergence that (i) shares the key properties of DP (Table I), (ii) is analytically tractable for Gaussian noise, (iii) restores a privacy budget (curves add) while still allowing advanced-composition-type bounds (Proposition 4), and (iv) converts to $(\epsilon ,\delta )$-DP (Proposition 3).

Relation to prior work. Concentrated DP and zero-concentrated DP (Dwork-Rothblum; Bun-Steinke) require a linear bound on all positive moments of the privacy-loss variable. RDP bounds one moment at a time: less restrictive and allowing more accurate numerics. The moments accountant of Abadi 2016 - Moments Accountant Theorems and Proofs introduced the same quantity as an internal tool, with a lossy translation to $(\epsilon ,\delta )$.

Key results.

Result	Statement
$\epsilon$-DP $⟺$ $(\infty ,\epsilon )$-RDP	$D_{\infty }(f(D)\Vert f(D^{\prime }))\le \epsilon$
Composition (Prop. 1)	$(\alpha ,{\epsilon }_1)$ then $(\alpha ,{\epsilon }_2)$ gives $(\alpha ,{\epsilon }_1+{\epsilon }_2)$
RDP to DP (Prop. 3)	$(\alpha ,\epsilon )$-RDP $\Rightarrow (\epsilon +\frac{\log (1/\delta )}{\alpha -1},\delta )$-DP
Gaussian (Cor. 3)	$\sigma$-noise on sensitivity 1 is $(\alpha ,\alpha /(2{\sigma }^2))$-RDP
Advanced composition (Cor. 1)	$n$-fold $\epsilon$-DP is $(4\epsilon \sqrt{2n\log (1/\delta )},\delta )$-DP when $\log (1/\delta )\ge {\epsilon }^{2}n$

Main Content

Source Map

Paper section	Content	Covered in
Abstract, I Introduction	motivation, contributions, outline	this note
II Differential privacy and its flavors (Defs. 1-2, Laplace, Gaussian, advanced composition, CDP/zCDP/moments accountant, other relaxations)	background	Mironov 2017 - Renyi Divergence and the RDP Definition
III Renyi DP (Defs. 3-4, Remarks 1-2, Table I, Prop. 1, Prop. 2)	definition and properties	Mironov 2017 - Renyi Divergence and the RDP Definition; Mironov 2017 - RDP Properties and Composition
IV RDP and $(\epsilon ,\delta )$-DP (Prop. 3)	conversion	Mironov 2017 - From RDP to Approximate DP and Advanced Composition
V Advanced composition theorem (Lemma 1, Prop. 4, Cor. 1, Remark 3)	composition	Mironov 2017 - From RDP to Approximate DP and Advanced Composition
VI Basic mechanisms (Props. 5-7, Cors. 2-3, Tables II, Figs. 1-2)	randomized response, Laplace, Gaussian	Mironov 2017 - RDP of Randomized Response, Laplace and Gaussian
VII Discussion (probabilistic guarantee, baseline-dependent bounds, tracking, Fig. 3)	interpretation	Mironov 2017 - Discussion, Budget Curves and Open Questions
VIII Conclusions and open questions	summary	Mironov 2017 - Discussion, Budget Curves and Open Questions
Appendix (Props. 8-11, Cor. 4)	Renyi divergence facts	Mironov 2017 - Appendix Renyi Divergence Properties

Examples

The one-line reason to prefer RDP for Gaussian noise

$n$ compositions of a Gaussian mechanism with parameter $\sigma$ (unit sensitivity) have RDP curve $\alpha \mapsto n\alpha /(2{\sigma }^2)$, identical to a single Gaussian with parameter $\sigma /\sqrt{n}$. No $(\epsilon ,\delta )$ bookkeeping is needed until the very end.

Connections

• Accounting for DP-SGD: Abadi 2016 - Deep Learning with Differential Privacy - Overview.
• Hypothesis-testing refinement that is strictly more informative than any divergence: Dong Roth Su 2022 - Divergence Conversion, Discussion and Limitations.
• A real deployment that uses the zCDP member of this family: Abowd 2022 - Why Differential Privacy, zCDP and Curator Models.
• Marketing relevance: Mironov 2017 - Discussion, Budget Curves and Open Questions (budget curves for multi-release reporting).

See Also

• Mironov 2017 - RDP of Randomized Response, Laplace and Gaussian
• Mironov 2017 - RDP Properties and Composition
• Dwork Roth 2014 - Basic Composition and Divergence Tools — basic composition and privacy-loss divergence background.
• Dwork Roth 2014 - Advanced Composition and the Gaussian Mechanism — the advanced composition theorem RDP re-derives.