Mironov 2017 - RDP Properties and Composition

Summary

RDP inherits the properties that make DP useful: a “bad outcomes” guarantee (weaker than $e^{\epsilon }$ but never a total breach), a Bayes-factor interpretation, closure under post-processing, additive adaptive composition at each order (Proposition 1), and group privacy under stable transformations (Proposition 2). Table I places these side by side with pure DP.

Overview

Section III verifies, one by one, that the relaxed definition preserves the desiderata of pure DP. The key facts: ${\epsilon }_1+{\epsilon }_2$ composition holds at each fixed $\alpha$, so a privacy budget (per order) is restored.

Main Content

Bad-outcomes guarantee

For pure DP, if some outputs $S$ are labelled “bad”, their probability changes by at most a factor $e^{\epsilon }$ whether or not a person’s record is included. For $(\alpha ,\epsilon )$-RDP the bound is the probability-preservation inequality (Proposition 10, Mironov 2017 - Appendix Renyi Divergence Properties):

$$e^{-\epsilon }\mathrm{Pr}[f(D^{\prime })\in S{]}^{\alpha /(\alpha -1)}\le \mathrm{Pr}[f(D)\in S]\le (e^{\epsilon }\mathrm{Pr}[f(D^{\prime })\in S]{)}^{(\alpha -1)/\alpha }.$$

Robustness to auxiliary information (Bayes factor)

For pure DP, with any prior $p(D)$ and observation $X$, the posterior odds satisfy $\frac{p(D\mid X)}{p(D^{\prime }\mid X)}\le e^{\epsilon }\frac{p(D)}{p(D^{\prime })}$. For RDP, define $R(D,D^{\prime })=\frac{p(D^{\prime }\mid X)}{p(D\mid X)}$ where $X\sim f(D)$; $R_{\text{post}}/R_{\text{prior}}=\frac{p(X\mid D^{\prime })}{p(X\mid D)}$, and

$${\mathbb{E}}_{f(D)}\left[\right(\frac{R_{\text{post}}(D,D^{\prime })}{R_{\text{prior}}(D,D^{\prime })}{)}^{\alpha }]=\exp [(\alpha -1)D_{\alpha }(f(D^{\prime })\Vert f(D))]\le e^{(\alpha -1)\epsilon }.$$

Taking logs and Jensen: ${\mathbb{E}}_{f(D)}[\log R_{\text{post}}-\log R_{\text{prior}}]\le D_{\alpha }(f(D)\Vert f(D^{\prime }))\le \epsilon$ (it equals $D_1$, and uses monotonicity). Compare with pure DP, which gives $|\log R_{\text{post}}-\log R_{\text{prior}}|\le \epsilon$ everywhere, not just in expectation.

Post-processing

If $f$ is $(\alpha ,\epsilon )$-RDP and $g:\mathcal{R}\mapsto {\mathcal{R}}^{\prime }$ is a randomized mapping, then $g\circ f$ is $(\alpha ,\epsilon )$-RDP. Reason: the data-processing inequality $D_{\alpha }(P\Vert Q)\ge D_{\alpha }(g(P)\Vert g(Q))$.

Proposition 1 (adaptive composition)

Let $f:\mathcal{D}\mapsto {\mathcal{R}}_1$ be $(\alpha ,{\epsilon }_1)$-RDP and $g:{\mathcal{R}}_1\times \mathcal{D}\mapsto {\mathcal{R}}_2$ be $(\alpha ,{\epsilon }_2)$-RDP (for each fixed first argument). Then the mechanism outputting $(X,Y)$ with $X\sim f(D)$, $Y\sim g(X,D)$ satisfies $(\alpha ,{\epsilon }_1+{\epsilon }_2)$-RDP.

Proof. Write $X,Y,Z$ for the distributions of $f(D)$, $g(X,D)$ and the joint $h(D)$, and $X^{\prime },Y^{\prime },Z^{\prime }$ for the same under $D^{\prime }$.

$$e^{(\alpha -1)D_{\alpha }(h(D)\Vert h(D^{\prime }))}=\iint Z^{\alpha }{Z}^{\prime 1-\alpha }=\int X(x{)}^{\alpha }{X}^{\prime }(x{)}^{1-\alpha }[\int Y(x,y{)}^{\alpha }{Y}^{\prime }(x,y{)}^{1-\alpha }dy]dx\le e^{(\alpha -1){\epsilon }_2}\int X^{\alpha }{X}^{\prime 1-\alpha }\le e^{(\alpha -1)({\epsilon }_1+{\epsilon }_2)}.$$

The guarantee holds whether releases are coordinated or not, or computed over the same or different versions of the data. This yields a well-defined notion of a per-individual privacy budget: a finite resource consumed with each release. For RDP the budget is a curve parameterized by $\alpha$.

$c$-stable transformation and group privacy

A map $g:{\mathcal{D}}^{\prime }\mapsto \mathcal{D}$ is $c$-stable if $g(A),g(B)$ adjacent in $\mathcal{D}$ implies there is a chain $D_0=A,\dots ,D_c=B$ in ${\mathcal{D}}^{\prime }$ with each consecutive pair adjacent. For pure DP, if $f$ is $\epsilon$-DP and $g$ is $c$-stable then $f\circ g$ is $c\epsilon$-DP. Group privacy is the case where $g$ blows up one person’s impact.

Proposition 2 (group privacy / pre-processing)

If $f:\mathcal{D}\mapsto \mathcal{R}$ is $(\alpha ,\epsilon )$-RDP, $g:{\mathcal{D}}^{\prime }\mapsto \mathcal{D}$ is $2^c$-stable and $\alpha \ge 2^{c+1}$, then $f\circ g$ is $(\alpha /2^c,3^c\epsilon )$-RDP.

Proof sketch ($c=1$, induction for the rest). Since $g$ is 2-stable, for adjacent $D,D^{\prime }\in {\mathcal{D}}^{\prime }$ there is $A\in \mathcal{D}$ with $g(D),A$ and $A,g(D^{\prime })$ adjacent. Corollary 4(1) (weak triangle inequality with $p=q=2$) and monotonicity give $D_{\alpha /2}(h(D)\Vert h(D^{\prime }))\le \frac{\alpha -1}{\alpha -2}{D}_{\alpha }(h(D)\Vert h(A))+D_{\alpha -1}(h(A)\Vert h(D^{\prime }))\le 3\epsilon$. So group privacy degrades both the order (halved) and the level ($\times 3$), a weaker statement than pure DP’s linear scaling.

Table I: properties shared by DP and RDP

Property	Differential privacy	Renyi differential privacy
Change in probability of outcome $S$	$\mathrm{Pr}[f(D)\in S]\le e^{\epsilon }\mathrm{Pr}[f(D^{\prime })\in S]$; $\mathrm{Pr}[f(D)\in S]\ge e^{-\epsilon }\mathrm{Pr}[f(D^{\prime })\in S]$	$\mathrm{Pr}[f(D)\in S]\le (e^{\epsilon }\mathrm{Pr}[f(D^{\prime })\in S]{)}^{(\alpha -1)/\alpha }$; $\mathrm{Pr}[f(D)\in S]\ge e^{-\epsilon }\mathrm{Pr}[f(D^{\prime })\in S{]}^{\alpha /(\alpha -1)}$
Change in the Bayes factor	$R_{\text{post}}/R_{\text{prior}}\le e^{\epsilon }$ always	$\mathbb{E}[(R_{\text{post}}/R_{\text{prior}}{)}^{\alpha }]\le \exp [(\alpha -1)\epsilon ]$
Change in log of the Bayes factor	$|\Delta \log R|\le \epsilon$ always	$\mathbb{E}[\Delta \log R]\le \epsilon$
Post-processing	$f$ is $\epsilon$-DP $\Rightarrow g\circ f$ is $\epsilon$-DP	$f$ is $(\alpha ,\epsilon )$-RDP $\Rightarrow g\circ f$ is $(\alpha ,\epsilon )$-RDP
Adaptive sequential composition (basic)	$f,g$ are $\epsilon$-DP $\Rightarrow (f,g)$ is $2\epsilon$-DP	$f,g$ are $(\alpha ,\epsilon )$-RDP $\Rightarrow (f,g)$ is $(\alpha ,2\epsilon )$-RDP
Group privacy, pre-processing	$f$ is $\epsilon$-DP, $g$ is $2^c$-stable $\Rightarrow f\circ g$ is $2^c\epsilon$-DP	$f$ is $(\alpha ,\epsilon )$-RDP, $g$ is $2^c$-stable $\Rightarrow f\circ g$ is $(\alpha /2^c,3^c\epsilon )$-RDP

Examples

Budget curve composition

Setup: three Gaussian releases with ${\sigma }_1={\sigma }_2=2$ and ${\sigma }_3=1$ (unit sensitivity). Solution: each has RDP curve $\alpha /(2{\sigma }_i^2)$. Adding at each $\alpha$: $\epsilon (\alpha )=\alpha (\frac{1}{8}+\frac{1}{8}+\frac{1}{2})=0.75\alpha$, which equals the curve of a single Gaussian with ${\sigma }_{\text{eff}}^2=1/(2\cdot 0.75)=2/3$. Interpretation: heterogeneous mechanisms are added per order with no $\delta$ choices; only at the end do we pick the best $\alpha$ for an $(\epsilon ,\delta )$ statement (Mironov 2017 - From RDP to Approximate DP and Advanced Composition).

Connections

• Conversion of the composed curve to $(\epsilon ,\delta )$: Mironov 2017 - From RDP to Approximate DP and Advanced Composition.
• Exact f-DP counterpart of composition (tensor product), strictly more informative: Dong Roth Su 2022 - Composition Theorem and Central Limit Theorems.
• zCDP is the special case where the budget curve is linear $\rho \alpha$ for all $\alpha >1$: Abowd 2022 - Why Differential Privacy, zCDP and Curator Models.

See Also

• Mironov 2017 - Renyi Differential Privacy - Overview
• Mironov 2017 - Discussion, Budget Curves and Open Questions