Dwork Roth 2014 - Basic Composition and Divergence Tools

Summary

Simple composition: running an $({\epsilon }_1,{\delta }_1)$-DP and an $({\epsilon }_2,{\delta }_2)$-DP algorithm yields $({\epsilon }_1+{\epsilon }_2,{\delta }_1+{\delta }_2)$-DP (Thm. 3.14-3.16). To prove sharper bounds the book rephrases DP via max-divergence $D_{\infty }$ and its $\delta$-approximate version (Remark 3.2), proves their coupling characterisation (Lemma 3.17), bounds KL by $\epsilon (e^{\epsilon }-1)$ (Lemma 3.18), and states Azuma’s inequality (Lemma 3.19) for the next note’s advanced composition. Chapter 3.1 collects the Chernoff, Azuma and Stirling bounds.

Overview

“The combination of two differentially private algorithms [should] be differentially private itself… Of course the parameters $\epsilon$ and $\delta$ will necessarily degrade”: repeatedly computing the same statistic with an $\epsilon$-DP Laplace mechanism lets the average converge to the truth, so the guarantee must weaken with repeated use. “It is a strength of differential privacy that composition is ‘automatic,’ in that the bounds obtained hold without any special effort by the database curator.”

Main Content

Probabilistic tools (Sec. 3.1, pp. 28-29)

Theorem 3.1 - Additive Chernoff bound

$X_1,\dots ,X_m$ independent with $0\le X_i\le 1$; $S=\frac{1}{m}\sum X_i$, $\mu =\mathbb{E}[S]$. Then $\mathrm{Pr}[S>\mu +\epsilon ]\le e^{-2m{\epsilon }^2}$ and $\mathrm{Pr}[S<\mu -\epsilon ]\le e^{-2m{\epsilon }^2}$.

Theorem 3.2 - Multiplicative Chernoff bound

Same setting. $\mathrm{Pr}[S>(1+\epsilon )\mu ]\le e^{-m\mu {\epsilon }^2/3}$ and $\mathrm{Pr}[S<(1-\epsilon )\mu ]\le e^{-m\mu {\epsilon }^2/2}$.

Theorem 3.3 - Azuma's inequality

Let $f$ be a function of $m$ random variables $X_1,\dots ,X_m$, $X_i$ taking values in $A_i$, $\mathbb{E}[f]$ bounded. Let $c_i$ be the maximum effect of $X_i$ on $f$: for all $a_i,a_i^{\prime }\in A_i$, $\mathbb{E}[f\mid X_1,\dots ,X_{i-1},X_i=a_i]-\mathbb{E}[f\mid X_1,\dots ,X_{i-1},X_i=a_i^{\prime }]\le c_i$. Then $\mathrm{Pr}[f(X_1,\dots ,X_m)\ge \mathbb{E}[f]+t]\le \exp (-\frac{2t^2}{{\sum }_i{c}_i^2})$.

Theorem 3.4 - Stirling's approximation

$\sqrt{2n\pi }(n/e{)}^n{e}^{1/(12n+1)}<n!<\sqrt{2n\pi }(n/e{)}^n{e}^{1/(12n)}$.

Basic composition (Sec. 3.5, pp. 41-43)

Theorem 3.14 - Composition of two $\epsilon$-DP algorithms (p. 42)

Let ${\mathcal{M}}_1:{\mathbb{N}}^{|\mathcal{X}|}\to R_1$ be ${\epsilon }_1$-DP and ${\mathcal{M}}_2:{\mathbb{N}}^{|\mathcal{X}|}\to R_2$ be ${\epsilon }_2$-DP. Then ${\mathcal{M}}_{1,2}(x)=({\mathcal{M}}_1(x),{\mathcal{M}}_2(x))$ is $({\epsilon }_1+{\epsilon }_2)$-differentially private.

Proof (p. 42)

Fix $x,y$ with $\Vert x-y{\Vert }_1\le 1$ and $(r_1,r_2)\in R_1\times R_2$. By independence of the two mechanisms’ coins,

$$\frac{\mathrm{Pr}[{\mathcal{M}}_{1,2}(x)=(r_1,r_2)]}{\mathrm{Pr}[{\mathcal{M}}_{1,2}(y)=(r_1,r_2)]}=\frac{\mathrm{Pr}[{\mathcal{M}}_1(x)=r_1]}{\mathrm{Pr}[{\mathcal{M}}_1(y)=r_1]}\cdot \frac{\mathrm{Pr}[{\mathcal{M}}_2(x)=r_2]}{\mathrm{Pr}[{\mathcal{M}}_2(y)=r_2]}\le e^{{\epsilon }_1}{e}^{{\epsilon }_2}=e^{{\epsilon }_1+{\epsilon }_2}.$$

By symmetry the ratio is at least $e^{-({\epsilon }_1+{\epsilon }_2)}$.

Corollary 3.15 (p. 43)

If ${\mathcal{M}}_i$ is $({\epsilon }_i,0)$-DP for $i\in [k]$, then ${\mathcal{M}}_{[k]}(x)=({\mathcal{M}}_1(x),\dots ,{\mathcal{M}}_k(x))$ is $({\sum }_{i=1}^k{\epsilon }_i,0)$-DP.

Theorem 3.16 - Basic composition for $(\epsilon ,\delta )$ (p. 43)

If ${\mathcal{M}}_i$ is $({\epsilon }_i,{\delta }_i)$-DP for $i\in [k]$, then ${\mathcal{M}}_{[k]}$ is $({\sum }_{i=1}^k{\epsilon }_i,{\sum }_{i=1}^k{\delta }_i)$-differentially private. (Proof in Appendix B, due to Dwork and Lei; outside this capture.)

Divergences (Sec. 3.5.1, pp. 43-48)

Definition 3.5 - KL-divergence (p. 43)

$D(Y\Vert Z)={\mathbb{E}}_{y\sim Y}\left[\ln \frac{\mathrm{Pr}[Y=y]}{\mathrm{Pr}[Z=y]}\right]$ (a fraction with zero denominator is infinite). $D\ge 0$ with equality iff $Y,Z$ are identically distributed; $D$ is not symmetric, does not satisfy the triangle inequality, and can be infinite when $\mathrm{Supp}(Y)⊈\mathrm{Supp}(Z)$.

Definition 3.6 - Max divergence and $\delta$-approximate max divergence (pp. 43-44)

$$D_{\infty }(Y\Vert Z)=\underset{S\subseteq \mathrm{Supp}(Y)}{\max }\ln \frac{\mathrm{Pr}[Y\in S]}{\mathrm{Pr}[Z\in S]},D_{\infty }^{\delta }(Y\Vert Z)=\underset{S\subseteq \mathrm{Supp}(Y):\mathrm{Pr}[Y\in S]\ge \delta }{\max }\ln \frac{\mathrm{Pr}[Y\in S]-\delta }{\mathrm{Pr}[Z\in S]}.$$

Remark 3.2 (p. 44)

$\mathcal{M}$ is $\epsilon$-DP iff for every two neighbours $x,y$: $D_{\infty }(\mathcal{M}(x)\Vert \mathcal{M}(y))\le \epsilon$ and $D_{\infty }(\mathcal{M}(y)\Vert \mathcal{M}(x))\le \epsilon$. $\mathcal{M}$ is $(\epsilon ,\delta )$-DP iff $D_{\infty }^{\delta }(\mathcal{M}(x)\Vert \mathcal{M}(y))\le \epsilon$ and $D_{\infty }^{\delta }(\mathcal{M}(y)\Vert \mathcal{M}(x))\le \epsilon$.

The statistical distance is $\Delta (Y,Z)={\max }_S|\mathrm{Pr}[Y\in S]-\mathrm{Pr}[Z\in S]|$; $Y,Z$ are $\delta$-close if $\Delta (Y,Z)\le \delta$.

Lemma 3.17 - Approximate max-divergence via coupling (pp. 44-47)

1. $D_{\infty }^{\delta }(Y\Vert Z)\le \epsilon$ iff there exists a random variable $Y^{\prime }$ with $\Delta (Y,Y^{\prime })\le \delta$ and $D_{\infty }(Y^{\prime }\Vert Z)\le \epsilon$.
2. Both $D_{\infty }^{\delta }(Y\Vert Z)\le \epsilon$ and $D_{\infty }^{\delta }(Z\Vert Y)\le \epsilon$ iff there exist $Y^{\prime },Z^{\prime }$ with $\Delta (Y,Y^{\prime })\le \delta /(e^{\epsilon }+1)$, $\Delta (Z,Z^{\prime })\le \delta /(e^{\epsilon }+1)$ and $D_{\infty }(Y^{\prime }\Vert Z^{\prime })\le \epsilon$.

Proof sketch (pp. 44-47)

Part 1, ($\Leftarrow$). For every $S$: $\mathrm{Pr}[Y\in S]\le \mathrm{Pr}[Y^{\prime }\in S]+\delta \le e^{\epsilon }\mathrm{Pr}[Z\in S]+\delta$. ($\Rightarrow$). Let $S=\{y:\mathrm{Pr}[Y=y]>e^{\epsilon }\mathrm{Pr}[Z=y]\}$; then ${\sum }_{y\in S}(\mathrm{Pr}[Y=y]-e^{\epsilon }\mathrm{Pr}[Z=y])\le \delta$. Lower the mass of $Y$ on $S$ down to $e^{\epsilon }\mathrm{Pr}[Z=y]$ and raise it on $T=\{y:\mathrm{Pr}[Y=y]<\mathrm{Pr}[Z=y]\}$ (there is enough room since total mass removed is at most the mass available in $T$) while keeping $\mathrm{Pr}[Y^{\prime }=y]\le \mathrm{Pr}[Z=y]$ there; then $D_{\infty }(Y^{\prime }\Vert Z)\le \epsilon$ and $\Delta (Y,Y^{\prime })\le \delta$. Part 2, ($\Leftarrow$). $\mathrm{Pr}[Y\in S]\le \mathrm{Pr}[Y^{\prime }\in S]+\frac{\delta }{e^{\epsilon }+1}\le e^{\epsilon }\mathrm{Pr}[Z^{\prime }\in S]+\frac{\delta }{e^{\epsilon }+1}\le e^{\epsilon }\mathrm{Pr}[Z\in S]+\frac{e^{\epsilon }\delta }{e^{\epsilon }+1}+\frac{\delta }{e^{\epsilon }+1}=e^{\epsilon }\mathrm{Pr}[Z\in S]+\delta$. ($\Rightarrow$). On $S=\{y:\mathrm{Pr}[Y=y]>e^{\epsilon }\mathrm{Pr}[Z=y]\}$ move both distributions toward each other: set $\mathrm{Pr}[Y^{\prime }=y]=e^{\epsilon }\mathrm{Pr}[Z^{\prime }=y]=\frac{e^{\epsilon }}{1+e^{\epsilon }}(\mathrm{Pr}[Y=y]+\mathrm{Pr}[Z=y])$, which lies in $[e^{\epsilon }\mathrm{Pr}[Z=y],\mathrm{Pr}[Y=y]]$; the mass moved on each side totals $\alpha =\frac{\mathrm{Pr}[Y\in S]-e^{\epsilon }\mathrm{Pr}[Z\in S]}{e^{\epsilon }+1}\le \frac{\delta }{e^{\epsilon }+1}$. Do the same on $S^{\prime }=\{y:\mathrm{Pr}[Z=y]>e^{\epsilon }\mathrm{Pr}[Y=y]\}$ with total ${\alpha }^{\prime }$; if $\alpha \ne {\alpha }^{\prime }$ the leftover $\beta =|\alpha -{\alpha }^{\prime }|$ of normalisation is fixed by shifting mass on points where $\mathrm{Pr}[Y^{\prime }=y]<\mathrm{Pr}[Z^{\prime }=y]$, keeping $D_{\infty }(Y^{\prime }\Vert Z^{\prime })\le \epsilon$ and $\Delta \le \alpha$.

Lemma 3.18 - KL bound from max-divergence (p. 47)

If $D_{\infty }(Y\Vert Z)\le \epsilon$ and $D_{\infty }(Z\Vert Y)\le \epsilon$ then $D(Y\Vert Z)\le \epsilon (e^{\epsilon }-1)$.

Proof (p. 47)

$D(Y\Vert Z)\le D(Y\Vert Z)+D(Z\Vert Y)$ since both are nonnegative (log-sum inequality). That sum equals ${\sum }_y[\mathrm{Pr}[Y=y]-\mathrm{Pr}[Z=y]]\ln \frac{\mathrm{Pr}[Y=y]}{\mathrm{Pr}[Z=y]}\le {\sum }_y|\mathrm{Pr}[Y=y]-\mathrm{Pr}[Z=y]|\epsilon =\epsilon {\sum }_y(\max -\min )\le \epsilon (e^{\epsilon }-1){\sum }_y\min \{\mathrm{Pr}[Y=y],\mathrm{Pr}[Z=y]\}\le \epsilon (e^{\epsilon }-1)$, using $\max \le e^{\epsilon }\min$ and $\sum \min \le 1$. The identity used is $D(Y\Vert Z)+D(Z\Vert Y)={\sum }_y(\mathrm{Pr}[Y=y]-\mathrm{Pr}[Z=y])\ln \frac{\mathrm{Pr}[Y=y]}{\mathrm{Pr}[Z=y]}$, each term of which is at most $|\mathrm{Pr}[Y=y]-\mathrm{Pr}[Z=y]|\epsilon$ because $|\ln (\mathrm{Pr}[Y=y]/\mathrm{Pr}[Z=y])|\le \epsilon$.

Lemma 3.19 - Azuma's inequality for martingale-difference sums (pp. 47-48)

Let $C_1,\dots ,C_k$ be real-valued random variables with $\mathrm{Pr}[|C_i|\le \alpha ]=1$ and, for every $(c_1,\dots ,c_{i-1})\in \mathrm{Supp}(C_1,\dots ,C_{i-1})$, $\mathbb{E}[C_i\mid C_1=c_1,\dots ,C_{i-1}=c_{i-1}]\le \beta$. Then for every $z>0$:

$$\mathrm{Pr}[\sum _{i=1}^k{C}_i>k\beta +z\sqrt{k}\cdot \alpha ]\le e^{-z^2/2}.$$

Examples

Two-hospital composition and budget split (derived). A lab runs three analyses on the same cohort with $(0.2,10^{-6})$, $(0.3,0)$ and $(0.5,2\times 10^{-6})$: by Thm. 3.16 the total is $(1.0,3\times 10^{-6})$. If the total budget is $\epsilon =1$ and there are 10 equally important reports, each can use $\epsilon =0.1$ under basic composition.

import numpy as np
rng = np.random.default_rng(0)
# Why composition must degrade: averaging k repeated eps-DP Laplace answers of one count converges to the truth
true, eps = 100.0, 0.5
for k in (1, 10, 100, 1000):
    ans = true + rng.laplace(0, 1/eps, size=k)
    print(k, abs(ans.mean() - true).round(3), "total eps (basic) =", k*eps)
# Max-divergence of two Laplace outputs for a count with sensitivity 1 equals eps
z = np.linspace(80, 120, 100001)
lp = lambda mu: np.exp(-eps*np.abs(z-mu))*eps/2
print(np.log(lp(100)/lp(101)).max(), eps)      # D_inf = eps

Connections

• Marketing measurement. Basic composition is the accounting rule for “privacy budget” across weekly reports: a total budget ${\epsilon }_{\text{total}}$ over $T$ releases means ${\epsilon }_{\text{total}}/T$ each unless advanced composition is used. Because repeated releases of the same time series average away the noise, a reporting cadence is a privacy decision as well as an analytic one.
• Max-divergence is the likelihood-ratio language for the hypothesis-testing view of DP in Wasserman Zhou 2010 - Differential Privacy as a Hypothesis-Testing Constraint.

See Also

• Dwork Roth 2014 - Advanced Composition and the Gaussian Mechanism
• Dwork Roth 2014 - Sparse Vector Technique
• Dwork 2006 - Postprocessing, Composition and Group Privacy (adaptive $\epsilon$-DP composition with a budget)