差分隐私蕴含泛化

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

先考虑一个监视器 $W$：它读取 $T$ 份相互独立的样本 $S_1,\dots ,S_T\sim D^m$，输出查询 $g:Z\to [0,1]$ 和块编号 $t$。若 $W$ 对这 $mT$ 条记录中的单点替换满足 $(a,b)$-DP，则

证明只需逐记录替换。把 $\mathbb{E}{P}_{S_t}g$ 展开成 $m^{-1}\sum _{j,i}\mathbb{E}[\mathbf{1}\{t=j\}g(Z_{j,i})]$；固定其余数据和一个独立新点，用 DP 比较替换前后的监视器。每个被比较的输出函数都在 $[0,1]$ 内，所以其期望至多乘 $e^a$ 再加 $b$。替换后，旧点独立于监视器输出；交换旧点与新点的同分布角色，再对 $mT$ 项求和，得到 $\mathbb{E}{P}_{S_t}g\le e^a\mathbb{E}Pg+Tb$。最后用 $Pg\le 1$。这里控制的是有符号间隙的期望，而不是绝对间隙的期望。

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

设 $\beta =\delta /\epsilon$、$T=\lfloor 1/\beta \rfloor$。在 $T$ 份独立样本上独立运行 $A$，得到查询 ${\varphi }_t$。对每个块建立两个候选 $g_{t,+}={\varphi }_t$、$g_{t,-}=1-{\varphi }_t$，评分为

两种符号使最高分恰为 $\underset{t}{max}|P_{S_t}{\varphi }_t-P{\varphi }_t|\ge 0$。监视器按指数机制理路指数隐私机制Exponential mechanism通过效用的指数权重选择离散输出，用分子与归一化常数两项共同控制隐私损失。选择候选索引，权重是 $\exp (m\epsilon u(t,s)/2)$，再输出该查询和块编号。固定第一阶段产生的所有查询后，每个评分对单条记录的灵敏度至多 $1/m$，所以第二阶段为纯 $\epsilon$-DP。第一阶段在互不相交的块上运行，单次替换只影响一个块，故整体为 $(\epsilon ,\delta )$-DP；两阶段组合得到 $(2\epsilon ,\delta )$-DP。监视器知道总体均值只是证明中的思想实验，不要求实际学习算法知道 $D$。选择最高经验偏差会重新读取私有样本，因此需要这一步私有选择，不能当作普通后处理。

对 $N$ 个评分以权重 $e^{\eta u}$ 抽样，记归一化常数为 $Z$、候选概率为 $p$，则 $\log Z=\eta {\mathbb{E}}_{p}u+H(p)$，其中以自然对数计的Shannon 熵理路Shannon 熵Shannon entropy · Information entropy随机变量不确定性的平均信息量，以最优编码所需位数为基本解释。满足 $H(p)=-\sum p\log p\le \log N$；又有 $\log Z\ge \eta maxu$。取 $N=2T$、$\eta =m\epsilon /2$，得到条件期望界

若单次运行的大偏差概率至少为 $\beta$，则 $T\beta \ge 1-\beta >3/4$，所以至少一块偏差达到 $18\epsilon$ 的概率为 $1-(1-\beta {)}^T>1/2$。最高分非负，因而 $\mathbb{E}maxu>9\epsilon$，所选评分的期望大于 $7\epsilon$。但前面的期望稳定性引理给出

其中用了 $0<\epsilon <1/3$ 时 $e^{2\epsilon }-1<3\epsilon$ 及 $T\delta \le \epsilon$。矛盾说明单次失败概率小于 $\beta$，从而得到所陈述的上界。

这和经典算法稳定性理路算法稳定性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 假设、邻接类型、样本量、总隐私预算以及要保证的是单个最终输出还是整个查询序列。