当前位置：首页 > news >正文

【差分隐私相关概念】瑞丽差分隐私（RDP）命题4

news 来源：原创 2025/8/26 13:22:22

在这里插入图片描述

命题4的证明详解（分情况讨论）

背景与设定

机制： $\mathcal{D} \to \mathcal{R}$ 是由 $n$ 个 $\epsilon$ -差分隐私机制自适应组合而成。
相邻输入： $D$ 和 $D^{'}$ 是相邻数据集。
目标：证明对任意事件 $\subseteq \mathcal{R}$ ，有：
$\Pr[f(D) \in S] \leq \exp\left( 2\epsilon \sqrt{n \log(1/\Pr[f(D') \in S])} \right) \cdot \Pr[f(D') \in S].$

证明概述

Rényi差分隐私（RDP）的组合性：
根据命题1（RDP的组合性），每个机制的RDP参数为 $(\alpha, 2\alpha \epsilon^2)$ ，组合后得到：
$D_\alpha(f(D) \parallel f(D')) \leq 2\alpha n \epsilon^2 \quad (\alpha \geq 1).$
概率保持定理（命题10）：
对于事件 $S$ ，若 $\Pr[f(D') \in S]$ ，则：
$\Pr[f(D) \in S] \leq \left( \exp(D_\alpha(P \parallel Q)) \cdot Q \right)^{(\alpha - 1)/\alpha}.$

情况I： $\log(1/Q) \geq \epsilon^2 n$

步骤1：选择最优的 $\alpha$
令 $\alpha = \frac{\sqrt{\log(1/Q)}}{\epsilon \sqrt{n}}$ 。

验证 $\alpha \geq 1$ ：
由 $\log(1/Q) \geq \epsilon^2 n$ ，得：
$\alpha = \frac{\sqrt{\log(1/Q)}}{\epsilon \sqrt{n}} \geq \frac{\sqrt{\epsilon^2 n}}{\epsilon \sqrt{n}} = 1.$

步骤2：应用概率保持定理
代入 $D_\alpha(P \parallel Q) \leq 2\alpha n \epsilon^2$ ，得：
$\Pr[f(D) \in S] \leq \left( \exp(2\alpha n \epsilon^2) \cdot Q \right)^{(\alpha - 1)/\alpha}.$

步骤3：展开指数项
对指数部分进行分解：
$\exp(2\alpha n \epsilon^2) \cdot Q = \exp\left( 2\alpha n \epsilon^2 + \log Q \right).$
由于 $\log Q = -\log(1/Q)$ ，令 $\log(1/Q)$ ，则：
$\exp\left( 2\alpha n \epsilon^2 - L \right).$

步骤4：代入 $\alpha$ 并化简
代入 $\alpha = \sqrt{L}/(\epsilon \sqrt{n})$ ，计算指数部分：
$2\alpha n \epsilon^2 - L = 2 \cdot \frac{\sqrt{L}}{\epsilon \sqrt{n}} \cdot n \epsilon^2 - L = 2\epsilon \sqrt{n L} - L.$
进一步化简：
$\exp\left( 2\epsilon \sqrt{n L} - L \right) = \exp\left( L \cdot \left( \frac{2\epsilon \sqrt{n}}{\sqrt{L}} - 1 \right) \right).$

步骤5：结合 $Q^{1 - 1/\alpha}$
注意到 $Q^{1 - 1/\alpha} = \exp\left( -\log(1/Q) \cdot (1 - 1/\alpha) \right)$ ，因此最终结果为：
$\Pr[f(D) \in S] \leq \exp\left( 2\epsilon \sqrt{n L} \right) \cdot Q.$

情况II： $\log(1/Q) < \epsilon^2 n$

步骤1：直接验证右边超过1
令 $\log(1/Q)$ ，则 $\epsilon^2 n$ 。需证明：
$\exp\left( 2\epsilon \sqrt{n L} \right) \cdot Q \geq 1.$

步骤2：利用基本不等式
由 $\sqrt{n L} \geq L/\epsilon$ （因 $\epsilon^2 n$ ，即 $L/\epsilon < \epsilon n$ ），得：
$2\epsilon \sqrt{n L} \geq 2L.$
因此：
$\exp\left( 2\epsilon \sqrt{n L} \right) \cdot Q \geq \exp(2L) \cdot e^{-L} = e^{L} \geq 1 \quad (\text{因} \ L \geq 0).$

步骤3：结论
由于概率 $\Pr[f(D) \in S] \leq 1$ ，而右边 $\exp\left( 2\epsilon \sqrt{n L} \right) \cdot Q \geq 1$ ，原不等式自然成立。

关键点总结

情况I：当事件 $S$ 在 $D^{'}$ 下的概率 $Q$ 极小时（即 $\log(1/Q) \geq \epsilon^2 n$ ），通过优化选择 $\alpha$ ，将RDP参数转化为指数形式的上界。
情况II：当 $Q$ 不太小时，直接验证右侧超过1，从而不等式自动成立。
核心技巧：通过RDP的组合性和概率保持定理，结合参数优化（选择 $\alpha$ ），最终统一了两种情况的结果。

命题4的证明详解（分情况讨论）

背景与设定

证明概述

情况I： log ⁡ ( 1 / Q ) ≥ ϵ 2 n \log(1/Q) \geq \epsilon^2 n log(1/Q)≥ϵ2n

情况II： log ⁡ ( 1 / Q ) < ϵ 2 n \log(1/Q) < \epsilon^2 n log(1/Q)<ϵ2n

关键点总结

相关文章：

情况I： $\log(1/Q) \geq \epsilon^2 n$

情况II： $\log(1/Q) < \epsilon^2 n$