差分隐私蕴含泛化

定理接口与作用层次 ​

差分隐私公理库差分隐私Differential privacy · DP · 差分隐私定义用相邻数据集上的输出分布似然比，限制随机机制泄露任何单条记录影响的稳定性定义。本身是相邻数据集输出分布的比较定义；本页固定其中的替换邻接，并研究它何时推出统计泛化。设数据集 $S,S^{\prime }\in Z^m$ 只在一个位置不同，算法 $A$ 对任意相邻输入满足 $(\epsilon ,\delta )$-DP。隐私语义限制观察者能否辨认单条记录，泛化定理则从同一不等式读出稳定性：替换一个样本点不会显著改变输出分布，因此算法难以把某个偶然样本特征编码进最终选择的统计查询。

这个推论还需要 IID 样本、查询值域、样本量与参数范围，并产生独立的泛化失败概率。删除/增加邻接的 DP 机制不能未经参数转换直接代入；一个机制满足 DP 也不意味着后续任意统计陈述自动泛化。下面固定一个单查询高概率版本，把这些量词完整列出。

一个固定版本的高概率定理 ​

本页采用 Bassily 等人的单查询版本。设 $0<\epsilon <1/3$、$0<\delta <\epsilon /4$，样本量满足

$$m\ge \frac{\log \left(4\epsilon /\delta \right)}{{\epsilon }^2}.$$

令 $S\sim D^m$，随机算法 $A$ 在上述替换邻接下满足 $(\epsilon ,\delta )$-DP，并输出一个数据依赖的统计查询 $\varphi :Z\to [0,1]$。记

$$P\varphi ={\mathbb{E}}_{Z\sim D}\varphi (Z),P_S\varphi =\frac{1}{m}\sum _{i=1}^m\varphi (Z_i).$$

则样本和算法内部随机性共同满足

$${\text{Pr}}_{S,A}[|P_S\varphi -P\varphi |\ge 18\epsilon ]\le \frac{\delta }{\epsilon }.$$

换言之，以至少 $1-\delta /\epsilon$ 的概率，私有选择的这一条查询在样本与总体上的差不超过 $18\epsilon$。常数 $18$ 属于这个具体定理版本；期望界、纯 DP 界、多查询 transfer theorem 和 max-information 路线有不同参数，不能与它互换常数。

从替换样本到高概率控制 ​

随机选一个索引 $I$，再取独立新样本 $Z^{\prime }\sim D$，把 $S$ 的第 $I$ 个元素替换为 $Z^{\prime }$ 得到 $S^{(I\leftarrow Z')} $。两组数据相邻，DP 使 $A(S)$ 与 $A(S^{(I\leftarrow Z^{\prime })})$ 的输出分布接近。前者在随机训练点 $Z_I$ 上的评价平均成 $P_S\varphi$；替换后，原来的 $Z_I$ 与算法输出近似解耦，对应总体均值 $P\varphi$。这是期望稳定性的核心耦合。

要得到上面的失败概率，还需 monitor argument。反设大偏差事件发生得过于频繁，监视器就在多份独立数据及其输出查询中挑出带符号的最大偏差。组合与后处理保证这个选择过程仍具有受控隐私；期望稳定性却禁止私有监视器持续挑出过大的偏差，从而推出 $18\epsilon$ 与 $\delta /\epsilon$ 的尾界。样本量条件负责让统计波动与近似隐私坏事件都落进同一预算。

这和经典 uniform stability 相似，却不相同。uniform stability 直接限制损失值在替换样本后的变化；DP 限制整个输出分布，因此后处理仍保持隐私，并能处理算法自适应选择的更广泛查询。

多查询与自适应分析 ​

所选定理只处理机制最终输出的一条 $[0,1]$ 查询。交互式分析若回答许多自适应查询，必须先证明整个 transcript 的组合隐私，再使用匹配的 transfer theorem；查询数会通过隐私组合、机制噪声和样本量进入结论。普通地查看许多查询后挑最大偏差会放大选择偏差，不能把单查询公式逐条套用后仍声称同样的失败概率。

一个发布统计量的例子 ​

数据分析者反复请求有界均值查询，并根据先前答案决定下一问。若每次答案都精确返回样本均值，足够多轮后可拼出样本的偶然细节。加入按敏感度校准的噪声，并按组合定理管理总隐私预算，可让整个交互保持 DP；泛化定理随后说明最终自适应选中的查询仍不容易在总体分布上严重偏离。

这不表示噪声越大越好。隐私噪声造成回答误差，泛化控制限制采样误差，两者要共同进入总精度。样本量必须同时支撑统计集中和隐私机制的噪声尺度。

边界 ​

DP 是充分的稳定机制，不是泛化的必要条件。固定的非私有查询照样可由 Hoeffding 不等式泛化；某些稳定算法也不满足实用的 DP 参数。反过来，差的隐私参数如 $\epsilon \gg 1$ 几乎不给稳定性，不能只凭“使用了 DP”就声称泛化可靠。

隐私随机性、样本随机性和结论的失败概率必须分别说明。$(\epsilon ,\delta )$ 中的 $\delta$ 是隐私近似参数；在本页选定的定理里，它导出泛化失败上界 $\delta /\epsilon$，但两者不是同一个定义参数。其他版本常另设失败概率 $\beta$，此时必须同时列出 $\delta$ 与 $\beta$。

参考资料

• Cynthia Dwork et al., “Preserving Statistical Validity in Adaptive Data Analysis,” STOC, 2015.
• Raef Bassily et al., “Algorithmic Stability for Adaptive Data Analysis,” arXiv:1511.02513v1, 2015，Definition 2.3（替换一个元素的 max-KL stability，即本文 DP 约定）与 Theorem 7.2（$\mathrm{\Delta }=1/m$ 的统计查询给出本页 $18\epsilon$ 界）；会议版发表于 STOC 2016。
• Cynthia Dwork and Aaron Roth, The Algorithmic Foundations of Differential Privacy, 2014.