Mironov 2017 - From RDP to Approximate DP and Advanced Composition

Summary

An $(\alpha ,\epsilon )$-RDP mechanism is $(\epsilon +\frac{\log (1/\delta )}{\alpha -1},\delta )$-DP for every $0<\delta <1$ (Proposition 3). Combining that with the bound $D_{\alpha }\le 2\alpha {\epsilon }^2$ for any $\epsilon$-DP mechanism (Lemma 1) and additivity gives an advanced composition theorem proved entirely in RDP language: $n$-fold $\epsilon$-DP composition is $(4\epsilon \sqrt{2n\log (1/\delta )},\delta )$-DP when $\log (1/\delta )\ge {\epsilon }^{2}n$.

Overview

Section IV reduces RDP to $(\epsilon ,\delta )$-DP; Section V proves a composition theorem whose structure follows Dwork-Rothblum-Vadhan but is phrased without explicit probability arguments. The first is the route by which almost all RDP accounting is eventually reported.

Main Content

Proposition 3 (from RDP to $(\epsilon ,\delta )$-DP)

If $f$ is an $(\alpha ,\epsilon )$-RDP mechanism, it also satisfies $(\epsilon +\frac{\log (1/\delta )}{\alpha -1},\delta )$-differential privacy for any $0<\delta <1$.

Proof. Let ${\epsilon }^{\prime }=\epsilon +\frac{1}{\alpha -1}\log \frac{1}{\delta }$ and write $Q=\mathrm{Pr}[f(D^{\prime })\in S]$. By Proposition 10 (probability preservation), $\mathrm{Pr}[f(D)\in S]\le (e^{\epsilon }Q{)}^{1-1/\alpha }$. Case I ($e^{\epsilon }Q>{\delta }^{\alpha /(\alpha -1)}$): $(e^{\epsilon }Q{)}^{1-1/\alpha }=e^{\epsilon }Q\cdot (e^{\epsilon }Q{)}^{-1/\alpha }\le e^{\epsilon }Q{\delta }^{-1/(\alpha -1)}=\exp (\epsilon +\frac{\log (1/\delta )}{\alpha -1})Q=e^{{\epsilon }^{\prime }}Q$ (the middle step uses $e^{\epsilon }Q>{\delta }^{\alpha /(\alpha -1)}$, i.e. $(e^{\epsilon }Q{)}^{-1/\alpha }<{\delta }^{-1/(\alpha -1)}$). Case II ($e^{\epsilon }Q\le {\delta }^{\alpha /(\alpha -1)}$): $\mathrm{Pr}[f(D)\in S]\le (e^{\epsilon }Q{)}^{1-1/\alpha }\le \delta$. In both cases $\mathrm{Pr}[f(D)\in S]\le \max (e^{{\epsilon }^{\prime }}Q,\delta )$, which is stronger than $({\epsilon }^{\prime },\delta )$-DP.

Since $\alpha$ is free, one reports ${\min }_{\alpha }\{\epsilon (\alpha )+\log (1/\delta )/(\alpha -1)\}$.

Lemma 1 (RDP curve of a pure-DP mechanism)

If $P,Q$ satisfy $D_{\infty }(P\Vert Q)\le \epsilon$ and $D_{\infty }(Q\Vert P)\le \epsilon$, then for $\alpha \ge 1$, $D_{\alpha }(P\Vert Q)\le 2\alpha {\epsilon }^2$.

Proof sketch. If $\alpha \ge 1+1/\epsilon$: $D_{\alpha }\le D_{\infty }=\epsilon \le (\alpha -1){\epsilon }^2$. If $\alpha <1+1/\epsilon$: use the inequality $x^{\beta +1}{y}^{-\beta }+x^{-\beta }{y}^{\beta +1}\le (1+(\beta \lambda {)}^2)(x+y)+\beta \lambda (x-y)$ for $x>y>0$, $\lambda =\log (x/y)$, $0\le \beta \le 1/\lambda$ (Eq. 2). With $\beta =\alpha -1\le 1/\epsilon$, integrating against $P,Q$ and using nonnegativity of $D_{\alpha }(Q\Vert P)$ gives $D_{\alpha }(P\Vert Q)\le 2(\alpha -1){\epsilon }^2+\epsilon \Vert P-Q{\Vert }_1$, and $\Vert P-Q{\Vert }_1\le \min (2,e^{\epsilon }-1)\le 2{\epsilon }^2$. The case $\alpha =1$ follows by continuity. The constant can be improved to $0.5$ with a more involved analysis (Bun-Steinke, Prop. 3.3).

Proposition 4 (advanced composition, probability form)

Let $f$ be an adaptive composition of $n$ mechanisms, each $\epsilon$-DP, and let $D,D^{\prime }$ be adjacent. For any $S\subset \mathcal{R}$,

$$\mathrm{Pr}[f(D)\in S]\le \exp \left(2\epsilon \sqrt{n\log \frac{1}{\mathrm{Pr}[f(D^{\prime })\in S]}}\right)\cdot \mathrm{Pr}[f(D^{\prime })\in S].$$

Proof. Lemma 1 plus Proposition 1 give $D_{\alpha }(f(D)\Vert f(D^{\prime }))\le 2\alpha n{\epsilon }^2$ for all $\alpha \ge 1$. Put $Q=\mathrm{Pr}[f(D^{\prime })\in S]$. Case $\log (1/Q)\ge {\epsilon }^{2}n$: choose $\alpha =\sqrt{\log (1/Q)}/(\epsilon \sqrt{n})\ge 1$; Proposition 10 gives $\mathrm{Pr}[f(D)\in S]\le \exp (2(\alpha -1)n{\epsilon }^2)Q^{1-1/\alpha }<\exp (2\epsilon \sqrt{n\log (1/Q)})Q$. Case $\log (1/Q)<{\epsilon }^{2}n$: the right-hand side exceeds 1 trivially.

Corollary 1 (advanced composition, $(\epsilon ,\delta )$ form)

Let $f$ be a composition of $n$ $\epsilon$-DP mechanisms and $0<\delta <1$ with $\log (1/\delta )\ge {\epsilon }^{2}n$. Then $f$ is $({\epsilon }^{\prime },\delta )$-DP with ${\epsilon }^{\prime }\triangleq 4\epsilon \sqrt{2n\log (1/\delta )}$.

Proof sketch. Show $\mathrm{Pr}[f(D)\in S]\le \max (e^{{\epsilon }^{\prime }}Q,\delta )$. If $8\log \frac{1}{\delta }>\log \frac{1}{Q}$, Proposition 4 gives $\exp (2\epsilon \sqrt{8n\log \frac{1}{\delta }})Q=e^{{\epsilon }^{\prime }}Q$. Otherwise ($8\log \frac{1}{\delta }\le \log \frac{1}{Q}$) use $\log (1/\delta )\ge {\epsilon }^{2}n$ and Proposition 4: $2\epsilon \sqrt{n\log \frac{1}{Q}}\le 2\sqrt{\log \frac{1}{\delta }\log \frac{1}{Q}}\le \frac{1}{\sqrt{2}}\log \frac{1}{Q}$, so $\mathrm{Pr}[f(D)\in S]\le Q^{1-1/\sqrt{2}}\le Q^{1/8}\le \delta$.

Remark 3. The condition $\log (1/\delta )\ge {\epsilon }^{2}n$ is the “high privacy” regime of advanced composition, where ${\epsilon }^{\prime }<(1+\sqrt{2})\log (1/\delta )$. With $\delta <1\%$ this covers ${\epsilon }^{\prime }<11$. If $\log (1/\delta )<{\epsilon }^{2}n$, this and other composition theorems are unlikely to give strong bounds.

Examples

Numbers for advanced composition versus basic composition

Setup: $n=10,000$ mechanisms, each $\epsilon =0.01$-DP, $\delta =10^{-5}$ (so $\log (1/\delta )=11.51\ge {\epsilon }^{2}n=1$). Solution: basic composition gives $n\epsilon =100$. Corollary 1 gives ${\epsilon }^{\prime }=4(0.01)\sqrt{2\cdot 10^4\cdot 11.51}=19.2$. The Dwork-Rothblum-Vadhan form $\sqrt{2n\ln (1/{\delta }^{\prime })}\epsilon +n\epsilon (e^{\epsilon }-1)$ gives about $5.8$. Interpretation: Corollary 1 is much better than basic composition here but about 3x looser than the standard $(\epsilon ,\delta )$ advanced composition: the constant 4 reflects the generic Lemma 1 constant 2 (the paper notes it can be improved to 0.5), and the paper observes that Proposition 4’s bound is “consistently outperformed” by the standard form with optimal $\delta$ (Section VI-D). The RDP value comes from directly using the mechanism’s own curve, see Mironov 2017 - RDP of Randomized Response, Laplace and Gaussian. All numbers are recomputed here.

import numpy as np
 
def basic(n, eps):            return n * eps
def drv(n, eps, delta_p):     # Dwork-Rothblum-Vadhan advanced composition
    return np.sqrt(2 * n * np.log(1 / delta_p)) * eps + n * eps * (np.exp(eps) - 1)
def mironov_cor1(n, eps, delta):
    assert np.log(1 / delta) >= eps**2 * n
    return 4 * eps * np.sqrt(2 * n * np.log(1 / delta))
 
def rdp_to_dp(rdp_curve, delta, alphas=np.linspace(1.01, 300, 30000)):
    """Proposition 3, optimized over alpha. rdp_curve(alpha) -> epsilon."""
    vals = rdp_curve(alphas) + np.log(1 / delta) / (alphas - 1)
    i = int(np.argmin(vals))
    return vals[i], alphas[i]
 
n, eps, delta = 10_000, 0.01, 1e-5
print(basic(n, eps), drv(n, eps, delta), mironov_cor1(n, eps, delta))   # 100, ~5.8, ~19.2
# 100 compositions of a Gaussian with sigma=4 (sensitivity 1): RDP curve 100*alpha/(2*16)
print(rdp_to_dp(lambda a: 100 * a / 32, 1e-5))                          # ~(15.1, alpha~2.9)

Connections

• Alternative route for the same Gaussian composition: the exact GDP curve gives $\epsilon \approx 13.2$ at $\delta =10^{-5}$ for $\mu =100^{1/2}/4=2.5$ (recomputed), versus 15.1 through Proposition 3; see Dong Roth Su 2022 - Gaussian Differential Privacy Definition and Gaussian Mechanism.
• The same Markov-style conversion is how the moments accountant produces $(\epsilon ,\delta )$: Abadi 2016 - Moments Accountant Theorems and Proofs.
• zCDP to $(\epsilon ,\delta )$ conversion used for the census: Abowd 2022 - Why Differential Privacy, zCDP and Curator Models.

See Also

• Mironov 2017 - Renyi Differential Privacy - Overview
• Mironov 2017 - RDP Properties and Composition