基于随机分配子采样的 DP-SGD 权衡函数：紧致的上界与下界

arXiv:2605.06259v3 公告类型：替换 摘要：在 $f$-DP 框架下，我们对基于随机分配子采样的差分隐私随机梯度下降（DP-SGD）的权衡函数进行了紧致分析。在该随机分配方案中，每个样本被独立地分配到每个 epoch 的 $M$ 个小批次中的恰好一个，而每个小批次对应单个 epoch 内 $M$ 轮 SGD 中的一轮。我们的分析在一个明确的有效性条件下成立，该条件的假设共同推出 $\sigma \geq \sqrt{3/\ln M}$，其中 $\sigma$ 是 DP 噪声乘子。不同于 Poisson 子采样的 $f$-DP 分析所得到的非闭式隐式公式——这类公式虽可由机器计算，却缺乏透明性——随机分配方案能够给出紧致的分析，并得到透明且易于解释的闭式界。对于单个 epoch，我们通过 Berry-Esseen 定理推导出的具体界在常数因子范围内是紧致的。我们展示了单个 epoch（$E=1$）下的参数设置示例，其对应的权衡函数满足 $\geq 1-a-\delta$；也就是说，它仅比理想随机猜测对角线 $1-a$ 低 $\delta$。当 $\delta = 1/100$ 且 $\sigma = 1$ 时，大约 $M \approx 1.14\times 10^6$ 轮和 $N \approx 1.14\times 10^7$ 个训练样本就足以实现有意义的差分隐私。这与近期针对 $\sigma \leq 1/\sqrt{2 \ln M}$ 情形的否定性结果形成对比；对于该情形，不可能存在显著的 DP 保证。