差分隐私的高级组合

每轮最坏隐私损失都可能接近 $\epsilon$，但连续多轮总是向同一个最坏方向偏移通常不是典型情况。高级组合把损失拆为小的平均漂移，加上围绕均值的波动。前者累积为约 $k{\epsilon }^2$，后者只以约 $\sqrt{k}\epsilon$ 增长。

这种改进用额外 ${\delta }^{\prime }$ 换取。若坚持最终仍为纯 DP，即 $\delta ={\delta }^{\prime }=0$，公式没有有限意义；不能把平方根规律当成纯 DP 的通用组合定律。

为什么自适应选择仍可处理 ​

先看每轮纯 DP 的情形。固定相邻输入 $D,D^{\prime }$，联合记录的概率由条件概率连乘，因此总对数似然比满足

给定过去，纯 DP 使 $L_i\in [-\epsilon ,\epsilon ]$。其条件均值是两个条件分布间的 KL 散度，可上界为 $\epsilon (e^{\epsilon }-1)$。减去这些条件均值后得到鞅差，其条件取值区间的长度仍为 $2\epsilon$，但绝对值不必至多 $\epsilon$。使用Azuma–Hoeffding 的条件区间版本公理库Azuma–Hoeffding 不等式Azuma-Hoeffding inequality · Azuma inequality有界鞅差之和偏离初值的概率具有高斯型指数上界。，总波动超过 $t$ 的概率至多 $\exp (-t^2/(2k{\epsilon }^2))$；取 $t=\epsilon \sqrt{2k\log \left(1/{\delta }^{\prime }\right)}$ 就得到平方根项。$\epsilon =0$ 时每轮纯 DP 分布相同，直接处理即可。

这里不要求不同轮的损失独立，只要求每个历史下的条件保证成立。近似 DP 的推广还要处理每轮的加法松弛，最终支付 $k\delta$；不能以“每轮存在概率恰为 $\delta$ 的坏集合”替代这个证明，因为一般 DP 的 $\delta$ 是事件概率的超额质量。

一百轮的小预算 ​

设 $k=100$，每轮为纯 $\epsilon =0.01$，选 ${\delta }^{\prime }={10}^{-6}$。基本组合给 $(1,0)$-DP。高级组合得到

因此同一过程也满足 $(0.536,{10}^{-6})$-DP。这个结论降低了 $\epsilon$，同时改变了允许的 $\delta$；不能只报告“预算从 1 降为 0.536”而省略后一项。

若每轮本已有 $\delta ={10}^{-8}$，同一计算的最终 $\delta$ 是 $100\cdot {10}^{-8}+{10}^{-6}=2\cdot {10}^{-6}$。给定总目标 $\overline{\delta }$ 后，先决定分配多少给 $k\delta$ 和 ${\delta }^{\prime }$，再计算每轮参数。

哪些选择会使口径改变 ​

分析者看过前几轮结果后更换查询是允许的；但每轮必须在固定历史下仍有预算保证。如果运行轮数本身按未保护的原始数据决定，停止时间也可能泄露信息。安全的简单做法是预先固定最大轮数并核算所有可能输出；更灵活的隐私过滤器需要另外的定理。

当 $k=1$ 或 $\epsilon$ 较大时，高级组合数值常比直接相加更差。其主要优势区间是小单轮 $\epsilon$、适度轮数，以及允许非零额外松弛的场景。

通用高级组合只知道每轮的两项 DP 参数，因此会丢掉机制的具体分布。若多轮都是 Gaussian 机制，Rényi DP公理库Rényi 差分隐私Renyi differential privacy · RDP以 Rényi 散度控制隐私损失的指数矩，使同一阶数的自适应组合预算可加。保留不同阶数的矩信息，往往得到更紧核算。选择核算方式时，应先固定整个发布流程，再比较合法的界，不能用不同核算器分别忽略不同轮次。