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(f(x))$ 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(x)=\frac{x^p}{p}+\frac{1}{q}-x$ and take the derivative to determine the minimum of the function.

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

$$f^{\prime }(x)=x^{p-1}-1=0$$

$$x^{p-1}=1⟹x=1$$

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

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

This means that:

$$f(x)\ge f(1)=0⟹\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(a^p{b}^{-q})\ge f(1)$$

$$\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 by $b^q$:

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

and simplifying the exponent:

$$-\frac{q}{p}+q=-\frac{qp+q}{p}=q(1-\frac{1}{p})=1$$

Therefore:

$$ab\le \frac{a^p}{p}+\frac{b^q}{q}$$

Elementary Proof

For this proof, you will only need to know a few facts about logarithms and exponentials.

The exponential and logarithms are inverses of each other—that is, applying them both to a function does nothing: ...