本文主要记录 Differential Privacy 中的 Composition Theorem (naive composition & advanced composition) 及其证明。本文主要参考自 Aaron Roth 的课件。
Setting
我们考虑下述过程
如果用 Alice – Bob 语言，那就是，Bob 在一开始选定 b = 0 或者 b = 1 ，而 Alice 作为 Adversary ，每次会提供两个 neighboring databases $D^{i,0}, D^{i,1}$，以及一个 mechanism $\mathcal{M}_i \in \mathcal{M}$，Bob 根据 Alice 提供的内容，运算 $y_i = \mathcal{M}_i(D^{i,b})$ 返回给 Alice。我们希望这个过程是 differential private 的，也就是说希望 Alice 根据有限的信息，反推得出 b = 0 或者 b = 1 得可能性不高，或者说，Alice 得到的信息没有办法区分出 b = 0 或者 b = 1 。而本文要研究的是，假若每一个 $\mathcal{M}_i$ 都是 $\epsilon$-DP 的，那么 $Compose(\mathcal{A}, \mathcal{M}, k, b)$ 会满足什么性质。
我们通常定义 Alice 的 view 为 $v_b = (r, y_1, y_2, \cdots, y_k)$，这也是我们最后得到的 $P[v_0\in S]$ 和 $P[v_1 \in S]$ 考虑的内容。
Basic Composition
Theorem 1 (Basic Composition Theorem). 假若 $\mathcal{M}_i$ 满足 $\epsilon$-DP，那么 $Compose(\mathcal{A}, \mathcal{M}, k, b)$ 满足 $k\epsilon$-DP。
Proof of Theorem 1:
固定一个 view $v = (r, y_1, y_2, \cdots, y_k)$：
\begin{align}
\frac{P[V^0 = v]}{P[V^1 = v]} =& \frac{P[R^0=r]}{P[R^1=r]}\cdot \prod_{i=1}^k \frac{P[Y^0_i=y_i|Y^0_{i-1}=y_{i-1},\cdots, Y^0_{1} = y_{1}, R^0=r]}{P[Y^1_i = y_i|Y^1_{i-1}=y_{i-1},\cdots, Y^1_{1} = y_{1}, R^1=r]} \\
\le& exp(k\epsilon)
\end{align}
Max Divergence and KL Divergence
在同一个概率测度空间 $(X, \mathcal{F}, P)$ 上，给定两个随机变量 $Y, Z$，可以定义其 Max Divergence 为
\[D_\infty (Y ||Z) = \sup\limits_{S\subset Supp(Y)}\left[ \ln \frac{P[Y\in S]}{P[Z\in S]}\right]\]
类似地，定义 $\delta$-Approximate Max Divergence 为
\[D_\infty^\delta (Y ||Z) = \sup\limits_{S\subset Supp(Y): P[Y\in S]\ge \delta}\left[ \ln \frac{P[Y\in S]-\delta}{P[Z\in S]}\right]\]
同样，我们定义这两个随机变量的 KL Divergence 为
\[D(Y ||Z) = \mathbb{E}_{y\sim Y}\left[ \ln \frac{P[Y = y]}{P[Z = y]}\right] = \int_{\mathbb{R}} \ln \frac{dP_Y}{dP_Z} dP_Y\]
其中，注意到 $\forall S\subset \mathbb{R}, S \mapsto P(Y\in S)$ 事实上定义了一个在 $(\mathbb{R}, \mathcal{B}(\mathbb{R})$ 上的测度，记为$P_Y$。$\frac{dP_Y}{dP_Z}$ 表示 Radon-Nikodym Derivative 。
我们有下述结论：
Lemma 2. 对两个随机变量 $Y,Z$，假若有 $D_\infty(Y||Z) \le \epsilon$ 和 $D_\infty(Z||Y) \le \epsilon$，那么我们有 $D(Y||Z) \le \epsilon(e^\epsilon-1)$。
Proof of Lemma 2:
\begin{align}
D(Y||Z) \le& D(Y||Z) + D(Z||Y) \\
=& \int_{\mathbb{R}} \left( \ln\frac{P_Y(dx)}{P_Z(dx)} + \ln\frac{P_Z(dx)}{P_Y(dx)} \right) P_Y(dx) \\
&+ \int_{\mathbb{R}} \ln\frac{P_Z(dx)}{P_Y(dx)} \left(P_Z(dx)-P_Y(dx)\right) \\
=& 0 + \int_{P_Z\ge P_Y} \ln\frac{P_Z(dx)}{P_Y(dx)} \left(P_Z(dx)-P_Y(dx)\right) \\
&-\int_{P_Y\ge P_Z} \ln\frac{P_Z(dx)}{P_Y(dx)} \left(P_Y(dx)-P_Z(dx)\right)\\
\le& \epsilon \cdot \left(\int_{P_Z\ge P_Y} \left(P_Z(dx)-P_Y(dx)\right) + \int_{P_Y\ge P_Z} \left(P_Y(dx)-P_Z(dx)\right)\right)\\
\le& \epsilon \cdot \sup_{D\subset \mathbb{R}} |P_Z(D)-P_Y(D)| \\
\le& \epsilon(e^\epsilon-1)
\end{align}
最后一步是因为$D_\infty(Y||Z) \le \epsilon$ 和 $D_\infty(Z||Y) \le \epsilon$。
Azuma’s Inequality
Lemma 3 (Azuma’s Inequality). 若一个随机变量序列 $\{X_i\}$ 满足 $\mathbb{E}[X_i | X_i, \cdots, X_1]\le \beta$，且有 $|X_i| \le c_i$恒成立，那么有
\[P\left[ \sum_{i = 1}^{k} X_i \ge k\beta + t \right] \le \exp\left(-\frac{t^2}{2\sum_{i = 1}^{k} c_i^2}\right)\]
Advanced Composition
Theorem 4 (Advanced Composition Theorem). 假若 $\mathcal{M}_i$ 满足 $\epsilon$-DP，那么 $Compose(\mathcal{A}, \mathcal{M}, k, b)$ 满足 $(\epsilon^\prime, \delta)$-DP，其中 $\epsilon^\prime = \sqrt{2k\ln(1/\delta)}\epsilon + k\epsilon(e^\epsilon-1)$。
Proof of Theorem 4.
令 $X_i= \ln\frac{P[Y^0_i = y_i | Y^0_{i-1} = y_{i-1}, \cdots, Y^0_1 = y_1, R^0 = r]}{P[Y^1_i = y_i | Y^1_{i-1} = y_{i-1}, \cdots, Y^1_1 = y_1, R^1 = r]}$，我们有 $|X_i| \le \epsilon$ （由 Max Divergence），以及 $\mathbb{E}[X_i | X_{i-1}, \cdots, X_1] \le \epsilon(e^\epsilon-1)$ (KL Divergence)，那么我们有
\[P\left[ \sum_{i = 1}^{k} X_i \ge k\epsilon(e^\epsilon-1) + \sqrt{2k\ln(1/\delta)}\epsilon \right] \le \delta\]
即证。
注意到当 $\epsilon$ 很小时，$(e^\epsilon-1)$ 趋于 0 ，所以可以认为$Compose(\mathcal{A}, \mathcal{M}, k, b)$ 满足 $(O(\sqrt{k}\epsilon), \delta)$-DP。
Leave a Reply