差分隐私蕴含泛化

从替换样本到期望稳定性 ​

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

monitor 如何把期望界提升成尾界 ​

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

这和经典算法稳定性公理库算法稳定性algorithmic stability · uniform stability用训练集中单点替换对输出损失的影响，刻画学习算法的泛化敏感度。相似，却不相同。uniform stability 直接限制损失值在替换样本后的变化；DP 限制整个输出分布，因此后处理仍保持隐私，并能处理算法自适应选择的更广泛查询。

一条有界均值查询的发布 ​

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

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

多查询边界 ​

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

充分但非必要 ​

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

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

这一定理给自适应数据分析提供了一条模块化路线：先让完整交互记录满足差分隐私，再调用与参数相匹配的 transfer theorem，把记录中最终选出的查询转成总体保证。隐私组合决定可以安全复用数据多少轮，查询回答噪声决定发布精度，二者必须和采样误差一同设计。

从学习理论看，DP 是一种分布级稳定机制。它把“替换一个训练点时输出不剧变”从单个损失值提升到整个输出分布，因此可覆盖模型、统计量乃至后处理后的选择。这个视角也解释了它与一般算法稳定性结论的关系：两者都阻止记忆单点偶然性，但使用不同对象、不同参数和不同高概率提升工具。

在实践中，结论适用于私有模型选择、可复用留出集和多轮统计查询；它不替代威胁模型，也不自动证明任意学习算法准确。必须先写清查询值域、IID 假设、邻接类型、样本量、总隐私预算以及要保证的是单个最终输出还是整个查询序列。