The Algorithmic Foundations of Differential Privacy - 3(2)

引理 3.18.
假设随机变量 $Y$ 和 $Z$ 满足

$$D_{\infty }(Y\Vert Z)\le \epsilon \text{且}{D}_{\infty }(Z\Vert Y)\le \epsilon .$$

那么有：

$$D(Y\Vert Z)\le \epsilon \cdot (e^{\epsilon }-1).$$

证明.
我们知道对于任意 $Y$ 和 $Z$，总有 $D(Y\Vert Z)\ge 0$（来自 “对数和不等式”）。因此只需对 $D(Y\Vert Z)+D(Z\Vert Y)$ 进行上界估计：

D(Y∥Z)≤D(Y∥Z)+D(Z∥Y)=∑yPr⁡[Y=y]⋅ln⁡Pr⁡[Y=y]Pr⁡[Z=y]+ln⁡Pr⁡[Z=y]Pr⁡[Y=y]+(Pr⁡[Z=y]−Pr⁡[Y=y])⋅ln⁡Pr⁡[Z=y]Pr⁡[Y=y]≤∑y[0+∣Pr⁡[Z=y]−Pr⁡[Y=y]∣⋅ε]=ε⋅∑y(max⁡{ Pr⁡[Y=y],Pr⁡[Z=y]}−min⁡{ Pr⁡[Y=y],Pr⁡[Z=y]})≤ε⋅∑y((eε−1)⋅min⁡{ Pr⁡[Y=y],Pr⁡[Z=y]})≤ε⋅(eε−1). \begin{aligned} D(Y\|Z) &\leq D(Y\|Z) + D(Z\|Y) \\ &= \sum_y \Pr[Y=y]\cdot \ln \frac{\Pr[Y=y]}{\Pr[Z=y]} + \ln \frac{\Pr[Z=y]}{\Pr[Y=y]} \\ &\quad + (\Pr[Z=y] - \Pr[Y=y]) \cdot \ln \frac{\Pr[Z=y]}{\Pr[Y=y]} \\ &\leq \sum_y \big[0 + |\Pr[Z=y] - \Pr[Y=y]|\cdot \varepsilon \big] \\ &= \varepsilon \cdot \sum_y \Big(\max\{\Pr[Y=y], \Pr[Z=y]\} - \min\{\Pr[Y=y], \Pr[Z=y]\}\Big) \\ &\leq \varepsilon \cdot \sum_y \Big((e^\varepsilon - 1) \cdot \min\{\Pr[Y=y], \Pr[Z=y]\}\Big) \\ &\leq \varepsilon \cdot (e^\varepsilon - 1). \end{aligned} D(Y∥Z)​≤D(Y∥Z)+D(Z∥Y)=y∑​Pr[Y=y]⋅lnPr[Z=y]Pr[Y=y]​+lnPr[Y=y]Pr[Z=y]​+(Pr[Z=y]−Pr[Y=y])⋅lnPr[Y=y]Pr[Z=y]​≤y∑​[0+∣Pr[Z=y]−Pr[Y=y]∣⋅ε]=ε⋅y∑​(max{ Pr[Y=y],Pr[Z=y]}−min{ Pr[Y=y],Pr[Z=y]})≤ε⋅y∑​((eε−1)⋅min{ Pr[Y=y],Pr[Z=y]})≤ε⋅(eε−1).​

---

引理 3.19 （Azuma 不等式）.
设 $C_1,\dots ,C_k$ 是实值随机变量，满足：

1. 对每个 $i\in [k]$，$\mathrm{Pr}[|C_i|\le \alpha ]=1$；

2. 对任意 $(c_1,\dots ,c_{i-1})\in \text{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 .$$

那么对任意 $z>0$，有：

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

---

3.5.2 高级合成（Advanced composition）

除了允许参数 $(\epsilon ,\delta )$ 以更缓慢的速度退化之外，我们还希望我们的定理能够处理更加复杂的合成形式。在开始之前，我们必须先讨论这里“合成”的确切含义。

我们希望定义的合成能够覆盖以下两种重要场景：

1. 对同一数据库反复使用差分隐私算法。
   这既包括多次重复使用同一个机制，也包括通过将不同的差分隐私模块组合在一起，构造出更复杂的差分隐私算法。

2. 对不同数据库反复使用差分隐私算法，而这些数据库可能仍然包含与同一个个体相关的信息。
   这让我们可以推理单个个体的累计隐私损失，即便其数据分散在多个数据库中，而这些数据库可能被分别用于不同的差分隐私计算。由于新数据库会不断产生，并且对手甚至可能影响这些数据库的组成，这个问题与反复查询同一个固定数据库是本质上不同的。

因此，我们需要对 自适应合成 建模：在这种情况下，对手不仅能影响未来机制的输入数据库，还能影响对这些机制的查询。

令 $\mathcal{F}$ 表示一族数据库访问机制（例如，$\mathcal{F}$ 可以是所有 $\epsilon$-差分隐私机制的集合）。对于一个概率型对手 $\mathcal{A}$，我们考虑如下两个实验：实验 0 和 实验 1。

---

实验 $b$：针对机制族 $\mathcal{F}$ 和对手 $\mathcal{A}$：
对于 $i=1,\dots ,k$：

1. $\mathcal{A}$ 输出一对相邻数据库 $x_i^0$ 和 $x_i^1$，一个机制 $M_i\in \mathcal{F}$，以及参数 $w_i$。

2. $\mathcal{A}$ 接收输出 $y_i\in \mathcal{R}$，其中

   $$y_i\sim M_i(w_i,x_i^b).$$

在整个实验过程中，我们允许对手 $\mathcal{A}$ 保持有状态，因此它可以根据先前机制的输出自适应地选择后续的数据库、机制和参数。我们定义 $\mathcal{A}$ 对实验的**视图（view）**为 $\mathcal{A}$ 的随机硬币投掷结果以及所有机制的输出 $(y_1,\dots ,y_k)$。 （因为 $x_i^j$、$M_i$ 和 $w_i$ 都可以从这些信息中重构出来。）

直观理解：
考虑一个对手，它总是选择 $x_i^0$ 包含 Bob 的数据，而 $x_i^1$ 与 $x_i^0$ 仅在删除 Bob 的数据上有所不同。那么：

• 实验 0 可以看作是真实世界（Bob 允许其数据被多次发布使用）；
• 实验 1 可以看作是理想世界（发布结果不依赖 Bob 的数据）。

我们的隐私定义依然要求这两个实验“接近”，就像差分隐私原始定义中所要求的那样。对 Bob 的直观保证是：即使观察到所有 $k$ 次机制的输出，对手也“无法分辨” Bob 的数据是否曾被使用。

---

定义 3.7.
我们称数据库访问机制族 $\mathcal{F}$ 在 $k$ 次自适应合成 下满足 $\epsilon$-差分隐私，如果对任意对手 $\mathcal{A}$，都有：

$$D_{\infty }(V^0\Vert V^1)\le \epsilon ,$$

其中 $V^b$ 表示对手 $\mathcal{A}$ 在上述 $k$ 次合成实验 $b$ 中的视图。

类似地，如果是 $(\epsilon ,\delta )$-差分隐私，则要求

$$D_{\infty }^{\delta }(V^0\Vert V^1)\le \epsilon .$$

---

定理 3.20 （高级合成定理，Advanced Composition）.
对任意 $\epsilon ,\delta ,{\delta }^{\prime }\ge 0$，若一类机制满足 $(\epsilon ,\delta )$-差分隐私，则在 $k$ 次自适应合成 下，该类机制满足：

$$({\epsilon }^{\prime },k\delta +{\delta }^{\prime })\text{-差分隐私},$$

其中：

$${\epsilon }^{\prime }=\sqrt{2k\ln (1/{\delta }^{\prime })}\cdot \epsilon +k\epsilon (e^{\epsilon }-1).$$

---

证明。 对手 $A$ 的一个视图由一个元组表示

$$v=(r,y_1,\dots ,y_k),$$

其中 $r$ 是 $A$ 的随机币掷结果，而 $y_1,\dots ,y_k$ 是机制 $M_1,\dots ,M_k$ 的输出。

定义集合

B={ v:Pr⁡[V0=v]>eε′⋅Pr⁡[V1=v]}. B = \{ v : \Pr[V_0 = v] > e^{\varepsilon'} \cdot \Pr[V_1 = v] \}. B={ v:Pr[V0​=v]>eε′⋅Pr[V1​=v]}.

我们将证明 $\mathrm{Pr}[V_0\in B]\le \delta$。因此对于任意集合 $S$，有

$$\begin{gathered} \mathrm{Pr}[V_0\in S]\le \mathrm{Pr}[V_0\in B]+\mathrm{Pr}[V_0\in (S\setminus B)] \\ \le \delta +e^{{\epsilon }^{\prime }}\cdot \mathrm{Pr}[V_1\in S]. \end{gathered}$$

这等价于说

$$D_{\delta }^{\infty }(V_0\parallel V_1)\le {\epsilon }^{\prime }.$$

剩下的就是证明 $\mathrm{Pr}[V_0\in B]\le \delta$。

设随机变量

$$V_0=(R_0,Y_1^0,\dots ,Y_k^0)$$

表示实验 0 中 $A$ 的视图，

$$V_1=(R_1,Y_1^1,\dots ,Y_k^1)$$

表示实验 1 中 $A$ 的视图。

那么对于一个固定的视图

$$v=(r,y_1,\dots ,y_k),$$

我们有：

$$\ln \frac{\mathrm{Pr}[V_0}{\mathrm{Pr}[V_1=v]}$$