瓦瑟斯坦差分隐私（Wasserstein DP）中的一个推导

---

公式68的推导基于最优传输理论和敏感度分析的结合，其核心是利用Wasserstein距离与数据敏感度之间的内在联系。以下分步骤详细解释：

---

1. 背景与符号定义

• 相邻数据集：设 $D$ 和 $D^{\prime }$ 是相邻数据集（例如相差一条记录）。
• 机制 $\mathcal{M}$：一个随机化算法，输出服从分布 ${\mathrm{Pr}}_{\mathcal{M}}(D)$ 和 ${\mathrm{Pr}}_{\mathcal{M}}(D^{\prime })$。
• 敏感度 ${\Delta }_{p}f$：定义为在相邻数据集上函数 $f$ 输出的最大 $l_p$ 范数差：
  $${\Delta }_{p}f=\underset{D,D^{\prime }}{\sup }\Vert f(D)-f(D^{\prime }){\Vert }_p.$$
• Wasserstein距离 $W_{\mu }$：如定义1，基于最优运输成本。

---

2. 公式67的作用

公式67给出了机制输出分布在相邻数据集上的敏感度约束：
$$\{\begin{array}{ll}{p}_{\mathcal{M}}(D)\le p_{\mathcal{M}}(D^{\prime })+{\Delta }_{p}f,& \text{当 }{p}_{\mathcal{M}}(D)\ge p_{\mathcal{M}}(D^{\prime }),\\ p_{\mathcal{M}}(D^{\prime })\le p_{\mathcal{M}}(D)+{\Delta }_{p}f,& \text{当 }{p}_{\mathcal{M}}(D)\le p_{\mathcal{M}}(D^{\prime }).\end{array}$$
这表明两个分布的差异被敏感度 ${\Delta }_{p}f$ 所限制，为后续推导提供了不等式条件。

---

3. 引用Bobkov-Ledoux定理2.7

Bobkov和Ledoux的定理指出，对于两个概率测度 $P$ 和 $Q$，若存在一个函数 $f$ 满足 Hölder连续条件，即：
$$|f(x)-f(y)|\le L\cdot \rho (x,y{)}^{\alpha }(0<\alpha \le 1),$$
则其期望差异可被Wasserstein距离上界：
$$|{\mathbb{E}}_P[f]-{\mathbb{E}}_Q[f]|\le L\cdot W_{\mu }(P,Q{)}^{\mu /(\mu +1)},$$
其中 $\mu$ 与Hölder指数 $\alpha$ 满足关系 $\alpha =\mu /(\mu +1)$。

---

4. 推导公式68的关键步骤

(1) 将敏感度视为Hölder条件

公式67中的敏感度约束可重新表述为：
$$\Vert f(D)-f(D^{\prime }){\Vert }_p\le {\Delta }_{p}f.$$
这等价于函数 $f$ 在相邻数据集上满足 Lipschitz条件（即 $\alpha =1$ 的Hölder条件），但需注意此处敏感度的定义基于 $l_p$ 范数。

(2) 链接到Wasserstein距离

根据Bobkov-Ledoux定理，若将机制输出分布 ${\mathrm{Pr}}_{\mathcal{M}}(D)$ 和 ${\mathrm{Pr}}_{\mathcal{M}}(D^{\prime })$ 视为 $P$ 和 $Q$，则：
$${\Delta }_{p}f\le L\cdot W_{\mu }(P,Q{)}^{\mu /(\mu +1)}.$$
其中：

• $L=1$（因敏感度已归一化），
• $\mu$ 是Wasserstein距离的阶数，与 $l_p$ 范数的选择相关。

(3) 参数匹配

• Hölder指数 $\alpha$：在定理中，$\alpha =\mu /(\mu +1)$。
• Wasserstein阶数 $\mu$：通常与敏感度范数 $l_p$ 对应。例如，若 $p=1$，则 $\mu =1$；若 $p=2$，则 $\mu =2$。

由此直接导出公式68：
$${\Delta }_{p}f\le W_{\mu }{\left(\underset{\mathcal{M}}{\mathrm{Pr}}(D)\parallel \underset{\mathcal{M}}{\mathrm{Pr}}(D^{\prime })\right)}^{\mu /(\mu +1)}.$$

---

5. 直观解释

• 敏感度与运输成本：${\Delta }_{p}f$ 衡量数据变化对输出的最大影响，而 $W_{\mu }$ 衡量分布间的最小运输成本。
• 指数项的意义：$\mu /(\mu +1)$ 反映了运输成本随距离阶数的非线性衰减。当 $\mu \to \infty$ 时，指数趋近于1，敏感度与Wasserstein距离直接线性相关。

---

6. 应用场景

该不等式在差分隐私中有重要意义：

• 隐私预算分析：通过约束 $W_{\mu }$ 来控制敏感度 ${\Delta }_{p}f$，进而设计满足 $(ϵ,\delta )$-差分隐私的机制。
• 噪声尺度设计：例如，拉普拉斯机制中噪声参数 $\lambda \propto {\Delta }_{p}f/ϵ$，与此处的 $W_{\mu }$ 上界一致。

---

总结

公式68的推导本质是将敏感度的局部约束（相邻数据集差异）与分布的全局差异（Wasserstein距离）通过Hölder条件和对偶理论联系起来。这一结果为隐私保护算法提供了理论工具，将数据敏感性转化为可计算的分布距离上界。