Mironov 2017 - Renyi Divergence and the RDP Definition

Summary

Section II reviews $\epsilon$-DP, $(\epsilon ,\delta )$-DP, the Laplace and Gaussian mechanisms and why $(\epsilon ,\delta )$ is an imperfect fit for them. Section III defines the Renyi divergence $D_{\alpha }$ and $(\alpha ,\epsilon )$-RDP: $D_{\alpha }(f(D)\Vert f(D^{\prime }))\le \epsilon$ for adjacent $D,D^{\prime }$. Pure DP is the $\alpha =\infty$ case, and monotonicity of $D_{\alpha }$ in $\alpha$ means $(\infty ,\epsilon )$-RDP implies $(\alpha ,\epsilon )$-RDP for all finite $\alpha$.

Overview

The conceptual move is to measure closeness of the output distributions by a one-parameter family of divergences rather than a worst-case density ratio ($\epsilon$-DP) or a tail-mass slack ($\delta$). The parameter $\alpha$ selects which moment of the privacy loss to control.

Main Content

Background definitions (Sec. II)

Definition 1: $\epsilon$-DP

A randomized mechanism $f:\mathcal{D}\mapsto \mathcal{R}$ satisfies $\epsilon$-DP if for any adjacent $D,D^{\prime }\in \mathcal{D}$ and $S\subset \mathcal{R}$: $\mathrm{Pr}[f(D)\in S]\le e^{\epsilon }\mathrm{Pr}[f(D^{\prime })\in S]$. Adjacency is domain-specific, typically capturing the contribution of one individual.

Laplace mechanism

${\mathcal{L}}_{\epsilon }f(x)\triangleq f(x)+\Lambda (0,{\Delta }_{1}f/\epsilon )$ where $\Lambda$ is the Laplace distribution and ${\Delta }_{1}f\triangleq {\max }_{D,D^{\prime }}\Vert f(D)-f(D^{\prime }){\Vert }_1$. Basic composition: if $f,g$ are ${\epsilon }_1$- and ${\epsilon }_2$-DP then releasing $(f(D),g(D))$ is $({\epsilon }_1+{\epsilon }_2)$-DP, even if $g$ is chosen adaptively after seeing $f(D)$.

Definition 2: $(\epsilon ,\delta )$-DP

$f$ offers $(\epsilon ,\delta )$-DP if for adjacent $D,D^{\prime }$ and $S\subset \mathcal{R}$: $\mathrm{Pr}[f(D)\in S]\le e^{\epsilon }\mathrm{Pr}[f(D^{\prime })\in S]+\delta$.

Why $(\epsilon ,\delta )$ is qualitatively different from pure DP. The informal reading “$\epsilon$-DP except with probability $\delta$” is hard to formalize: for two inputs one can build an $\epsilon$-DP mechanism agreeing with $f$ on all but $\delta$ probability, but not for exponentially large input domains without exponentially diluting the guarantee. The $\delta$ term also hides two very different failure modes. With probability $\delta$, privacy may degrade gracefully (to ${\epsilon }_1$-DP w.p. $\delta /2$, ${\epsilon }_2$-DP w.p. $\delta /4$, and so on), leaving residual deniability, or the secret (whether a record is present) may become completely exposed. A single $(\epsilon ,\delta )$ statement cannot distinguish them. The standard advice is $\delta \ll 1/N$ or negligible in $N$.

Gaussian mechanism. ${\mathcal{G}}_{\sigma }f(x)\triangleq f(x)+\mathcal{N}(0,{\sigma }^2)$. It cannot satisfy $\epsilon$-DP for any $\epsilon$; instead it satisfies a continuum of incomparable $(\epsilon ,\delta )$ guarantees for $\epsilon <1$ and $\sigma >\sqrt{2\ln (1.25/\delta )}{\Delta }_{2}f/\epsilon$, with ${\Delta }_{2}f\triangleq \max \Vert f(D)-f(D^{\prime }){\Vert }_2$. Reasons to prefer Gaussian over Laplace: Gaussian noise is closed under addition (like errors already in the data), noise scales with ${\ell }_2$ not ${\ell }_1$ sensitivity (no larger, often much smaller), and Gaussian tails decay faster than exponential tails.

Advanced composition. For $k$-fold adaptive composition of an $(\epsilon ,\delta )$-DP mechanism, for any ${\delta }^{\prime }>0$ the composite is $({\epsilon }^{\prime },k\delta +{\delta }^{\prime })$-DP with ${\epsilon }^{\prime }=\sqrt{2k\ln (1/{\delta }^{\prime })}\epsilon +k\epsilon (e^{\epsilon }-1)$ (Dwork, Rothblum, Vadhan). Kairouz et al. give the optimal $k$-fold bound for a single $(\epsilon ,\delta )$; Murtagh and Vadhan show that composing heterogeneous mechanisms optimally is P-hard, with a PTAS. None of these handles mechanisms that satisfy several $(\epsilon ,\delta )$ guarantees at once.

Related relaxations. CDP and zCDP (Dwork-Rothblum; Bun-Steinke) require a linear bound on all positive moments of the privacy-loss variable; RDP applies to one moment at a time. The moments accountant (Abadi 2016 - Moments Accountant Theorems and Proofs) introduced the same quantity internally with a lossy translation to $(\epsilon ,\delta )$. IND-CDP limits the adversary computationally; Pufferfish and coupled-worlds use different stability constraints but the same closeness notion as $(\epsilon ,\delta )$.

Renyi divergence and RDP (Sec. III)

Definition 3: Renyi divergence

For distributions $P,Q$ over $\mathbb{R}$, the Renyi divergence of order $\alpha >1$ is

$$D_{\alpha }(P\Vert Q)\triangleq \frac{1}{\alpha -1}\log {\mathbb{E}}_{x\sim Q}\left[\right(\frac{P(x)}{Q(x)}{)}^{\alpha }].$$

All logarithms are natural. At the endpoints, by continuity: $D_1(P\Vert Q)={\lim }_{\alpha \to 1}{D}_{\alpha }={\mathbb{E}}_{x\sim P}\log \frac{P(x)}{Q(x)}$ (the Kullback-Leibler divergence; note the expectation is over $P$), and $D_{\infty }(P\Vert Q)={\sup }_{x\in \text{supp}Q}\log \frac{P(x)}{Q(x)}$. It is possible that $D_1$ is finite while $D_{\alpha }=+\infty$ for every $\alpha >1$.

A mechanism $f$ is $\epsilon$-DP if and only if $D_{\infty }(f(D)\Vert f(D^{\prime }))\le \epsilon$ for all adjacent $D,D^{\prime }$. This motivates the relaxation.

Definition 4: $(\alpha ,\epsilon )$-RDP

A randomized mechanism $f:\mathcal{D}\mapsto \mathcal{R}$ has $\epsilon$-Renyi differential privacy of order $\alpha$, or $(\alpha ,\epsilon )$-RDP, if for any adjacent $D,D^{\prime }\in \mathcal{D}$,

$$D_{\alpha }(f(D)\Vert f(D^{\prime }))\le \epsilon .$$

Remark 1. A finite $\epsilon$ implies that feasible outcomes of $f(D)$ for some $D$ are feasible (non-zero density) for all inputs, except on a measure-zero set; the event space is taken to be the support. Remark 2. Renyi divergence can be defined for $\alpha <1$, including negative orders, but those are not used in the definition.

By monotonicity of $D_{\alpha }$ in $\alpha$ (Mironov 2017 - Appendix Renyi Divergence Properties, Prop. 9), $(\infty ,\epsilon )$-RDP implies $(\alpha ,\epsilon )$-RDP for every finite $\alpha$, so RDP is a relaxation that contains pure DP as an end point. A mechanism’s guarantee is a curve $\epsilon (\alpha )$, which Mironov calls its budget curve.

Examples

Divergence of two Gaussians as a one-line RDP bound

Setup: $P=\mathcal{N}(0,{\sigma }^2)$, $Q=\mathcal{N}(\mu ,{\sigma }^2)$. Solution: $D_{\alpha }(P\Vert Q)=\alpha {\mu }^2/(2{\sigma }^2)$ (Proposition 7). For adjacent inputs with $|f(D)-f(D^{\prime })|\le 1$, $\mu \le 1$, hence $(\alpha ,\alpha /(2{\sigma }^2))$-RDP. Interpretation: the budget curve is a straight line through the origin with slope $1/(2{\sigma }^2)$. No $\delta$ appears. Details in Mironov 2017 - RDP of Randomized Response, Laplace and Gaussian.

Connections

• Properties of RDP: Mironov 2017 - RDP Properties and Composition; conversion to $(\epsilon ,\delta )$: Mironov 2017 - From RDP to Approximate DP and Advanced Composition.
• KL divergence appears at $\alpha =1$; for KL in a Bayesian context see The ELBO and KL Divergence Minimization.
• The hypothesis-testing view treats DP as a trade-off between type I and type II errors; see Dong Roth Su 2022 - Trade-off Functions and f-DP.

See Also

• Mironov 2017 - Renyi Differential Privacy - Overview
• Abowd 2022 - Why Differential Privacy, zCDP and Curator Models (zCDP is $D_{\alpha }\le \rho \alpha$ for all $\alpha >1$)