返回学习路线

U17：同一个发布流程的灵敏度、机制与组合 ​

题目 ​

1. 固定 $n=100$，每条记录在 $[0,1]$ 内，邻接为替换一条。发布均值时求 ${\mathrm{\Delta }}_2$，并给出 $(\epsilon ,\delta )=(0.5,{10}^{-6})$ 的一个经典 Gaussian 噪声尺度。
2. 若只想从公开网格 $\mathcal{R}=\{0,0.01,\dots ,1\}$ 中选一个近似均值，取效用 $u(D,r)=-|r-\overline{x}(D)|$。求效用灵敏度，写指数机制分布，并解释这与直接高斯发布的输出差别。
3. 另有一个增删邻接的 DP-SGD 流程：每轮 Poisson 抽样率 $q=0.01$，逐样本裁剪阈值 $C=1$，归一化分母公开固定，抽样身份不发布。未抽样裁剪和的噪声机制校准为 $(0.5,{10}^{-7})$-DP，运行 $T=100$ 轮。使用放大与高级组合，选择最终 $\delta ={10}^{-6}$，给出完整预算。
4. 对 $P=(0.6,0.4),Q=(0.4,0.6)$ 及 $\epsilon =\log 1.25$，分别求损失越界概率与精确 hockey-stick 超额质量。

解答 ​

一次替换使均值最多移动 $1/100=0.01$，且把一个零改为一可达到此界。经典充分尺度为

$$\sigma >\frac{0.01\sqrt{2\log (1.25\cdot {10}^6)}}{0.5}\approx 0.10598.$$

可取 $\sigma =0.107$。这是高斯标准差；输出为连续实数，随后可截到 $[0,1]$ 而保持隐私。

绝对值的反三角不等式给

$$|u(D,r)-u(D^{\prime },r)|\le |\overline{x}(D)-\overline{x}(D^{\prime })|\le 0.01,$$

故 $\mathrm{\Delta }u=0.01$，取同一个 $\epsilon =0.5$ 时，网格候选的权重正比于 $\exp (-25|r-\overline{x}(D)|)$。该机制给纯 $0.5$-DP，输出必在固定网格内；它随机选择候选，而 Gaussian 机制给连续查询加噪声。两个方案的准确性还受网格分辨率、候选数和噪声尺度影响，不能只比较输出类型就断言谁总更好。

DP-SGD 的增删灵敏度为 $C=1$，因为一条新增记录只多贡献一个范数不超过 $C$ 的裁剪向量。未抽样高斯噪声的标准差需大于

$$\sqrt{2\log (1.25\cdot {10}^7)}/0.5\approx 11.4337,$$

例如取噪声乘子 $11.5$。固定分母之后，查询灵敏度与噪声一起缩放，隐私比值不变。若实际实现换成替换邻接，未抽样和的灵敏度可变为 $2C$，必须重算。

每轮放大后有

$${\epsilon }_1={\log }^{1+0.01(e^{0.5}-1)}\approx 0.00646626,{\delta }_1={10}^{-9}.$$

一百轮先消耗 $T{\delta }_1={10}^{-7}$，额外组合松弛取 ${\delta }^{\prime }=9\cdot {10}^{-7}$。所以

$${\epsilon }_{\mathrm{tot}}={\epsilon }_1\sqrt{200\log \left(1/{\delta }^{\prime }\right)}+100{\epsilon }_1(e^{{\epsilon }_1}-1)\approx 0.34539,{\delta }_{\mathrm{tot}}={10}^{-6}.$$

这是便于手工核查的保守上界。专门 sampled-Gaussian RDP 核算可更紧，但需保持同一邻接、抽样方式与输出范围。

最后，损失在第一个输出为 $\log 1.5$，第二个为 $\log \left(2/3\right)$。越界事件仅含第一个输出，所以 $P[L>\epsilon ]=0.6$；超额质量为 $0.6-1.25\cdot 0.4=0.1$，反向相同。$\delta$ 支付超出乘法基线的部分，未支付全部越界事件概率。

验收标准 ​

• 明确两个子题的邻接分别是替换与增删，不能混用灵敏度
• 高斯噪声写清标准差、方差与噪声乘子的区别
• 指数机制的候选集公开固定，归一化常数随数据变化但已计入证明
• 多轮预算包含单轮 $\delta$ 与额外组合 ${\delta }^{\prime }$，抽样规则和隐藏身份条件完整
• 明确 $0.6$ 与 $0.1$ 的不同含义，而非用“坏概率”一词合并