Hands-On Differential Privacy

Appendix B. Rényi Differential Privacy

Here, we present a series of theorems demonstrating the relationship between RDP and $(ϵ,\delta )$ differential privacy.

Theorem: RDP Is Immune to Postprocessing

For a mechanism $f$ that is $(\alpha ,ϵ)$-RDP, and a randomized mapping $g$, the composition $g\left(f\right(x\left)\right)$ is also $(\alpha ,ϵ)$-RDP.

Proof

See Mironov¹ for a proof of this claim, building on van Ervan and Harremoës.²

Now, let’s demonstrate the equivalence between RDP and $(ϵ,\delta )$-DP. First, we will need some mathematical preliminaries.

Theorem: Young’s Inequality

If $a,b\ge 0$ and $\frac{1}{p}+\frac{1}{q}=1$ with $p,q>1$, then $ab\le \frac{a^p}{p}+\frac{b^q}{q}$

Proof via Calculus

Define $f\left(x\right)=\frac{x^p}{p}+\frac{1}{q}-x$ and take the derivative to determine the minimum of the function.

The derivative is $f^{\text{'}}\left(x\right)=x^{p-1}-1$, and setting this equal to 0:

$$f^{\text{'}}\left(x\right)=x^{p-1}-1=0$$

$$x^{p-1}=1\Rightarrow x=1$$

We know this is a minimum by the second derivative test: $f^{\text{'}\text{'}}\left(x\right)=(p-1)x^{p-2}\ge 0$.

So we know that the minimum of $f\left(x\right)$ occurs at $x=1$ and that this minimum is $f\left(1\right)=0$.

This means that:

$$f\left(x\right)\ge f\left(1\right)=0\Rightarrow \frac{x^p}{p}+\frac{1}{q}-x\ge 0$$

Without loss of generality, assume $a>b$. Then $a^p{b}^{-q}\ge 1$. This further implies that:

$$f\left(a^p{b}^{-q}\right)\ge f\left(1\right)$$

$$\frac{a^p{b}^{-q}}{p}+\frac{1}{q}-a{b}^{-\frac{q}{p}}\ge \frac{1}{p}+\frac{1}{q}-1$$

and we know that $\frac{1}{p}+\frac{1}{q}=1$, so:

$$\frac{a^p{b}^{-q}}{p}+\frac{1}{q}\ge a{b}^{-\frac{q}{p}}$$

Multiplying both sides ...