技术摘要：基于随机打乱的 DP-SGD 的权衡函数

问题陈述

差分隐私随机梯度下降（DP-SGD）是在隐私约束下训练深度学习模型的标准机制。虽然 $f$-差分隐私（$f$-DP）框架通过假阳性和假阴性率之间的权衡函数提供了对隐私保证的最紧刻画，但现有分析主要集中于泊松子采样（即数据点以固定概率独立地包含在 minibatch 中）。

然而，DP-SGD 和随机优化的实际实现通常采用随机打乱，即每个 epoch 对数据集进行一次排列，然后划分为固定大小的 minibatch。这种被分析的算法（泊松）与部署的算法（打乱）之间的差异，导致现实世界中系统的隐私保证刻画得不够精确。以往关于打乱 DP-SGD 的工作仅通过显式的对抗事件或数值评估提供了权衡函数的上界（即隐私损失的下界），缺乏封闭形式且透明的表达式。此外，近期的不可能性结果表明，对于低噪声乘数（$\sigma \le 1/\sqrt{2 \ln M}$），权衡函数被证明远离理想的随机猜测对角线（$1-a$），但高噪声区域的行为仍是一个开放问题，需要紧密的、封闭形式的分析。

方法论

作者在 $f$-DP 框架下，推导了基于随机打乱的 DP-SGD 权衡函数的紧密、封闭形式分析。方法论通过以下阶段进行：

1. 对抗归约：问题被归约为一个标量假设检验问题。在最坏情况对抗模型下（该模型可以隔离单个不同记录的贡献），对抗者观察 $M$ 轮。在零假设（$H_0$）下，所有观测值均为纯噪声 $N(0, 1)$。在备择假设（$H_1$）下，恰好有一轮（由打乱排列均匀随机选择）包含偏移观测值 $N(1/\sigma, 1)$，而其余轮次仍为噪声。
2. 似然比检验：根据奈曼 - 皮尔逊引理，最优检验对似然比进行阈值判定，这等价于对对数正态变量 $Y_j = \exp(X_j/\sigma - 1/(2\sigma^2))$ 的样本均值进行阈值判定，其中 $X_j \sim N(0, 1)$。
3. 非渐近分析（Berry-Esseen）：对于单个 epoch，作者应用 Berry-Esseen 定理来界定这些对数正态变量样本均值收敛到正态分布的速率。这为 $\sigma \ge \sqrt{3/\ln M}$ 区域提供了权衡函数 $f(a)$ 的具体非渐近下界。该界限表示为 $f(a) \ge 1 - a - \delta$，其中 $\delta$ 是噪声乘数 $\sigma$ 和轮数 $M$ 的显式函数。
4. 渐近分析（Edgeworth 展开）：为了改进受限于 $O(1/\sqrt{M})$ 误差项的 Berry-Esseen 界限，作者引入了一种基于两项 Edgeworth 展开的证明技术。这种对中心极限定理的推广允许对对数正态变量之和的分布进行更精细的渐近估计。该方法确立了当 $M \to \infty$ 且 epoch 数 $E$ 按 $E = c_M^2 M$ 缩放（其中 $c_M \to 0$）时，权衡函数的渐近行为。

主要贡献

1. 单个 epoch 的封闭形式下界：本文提供了高噪声区域（$\sigma \ge \sqrt{3/\ln M}$）中打乱 DP-SGD 权衡函数的首个紧密、封闭形式下界。该界限由下式给出：
   $$f(a) \ge 1 - a - \delta$$
   其中 $\delta$ 根据 $\sigma$ 和 $M$ 显式定义（定理 4.1）。在 Berry-Esseen 证明框架内，该结果在常数因子范围内是紧密的。
2. 具体参数建议：作者推导了具有实际意义差分隐私的具体参数设置。对于单个 epoch（$E=1$），当 $\sigma=1$ 且 $\delta=10^{-2}$ 时，他们表明将数据集大小设为 $N \approx 1.14 \times 10^7$ 并划分为 $M \approx 1.14 \times 10^6$ 轮即足够。这证明了在具有大数据集和单个 epoch 的联邦学习设置中，可以实现有意义的隐私。
3. 渐近高斯-DP 刻画：利用 Edgeworth 展开，本文确立了对于固定的 $\sigma$，当 $M \to \infty$ 且 $E = c_M^2 M$（其中 $c_M \to 0$）时，$E$ 次复合权衡函数一致收敛于随机猜测对角线（$1-a$）。这将 epoch 数的依赖关系从朴素复合所暗示的线性 $O(E)$ 惩罚改进为渐近的 $O(\sqrt{E})$ 分离（推论 5.3）。
4. 与泊松子采样的比较：作者将他们的渐近结果与相应的泊松子采样渐近结果进行了比较。他们发现，在低噪声极限（$\sigma \to 0$）下，随机打乱在渐近意义上比泊松子采样更接近理想随机猜测对角线 $\sqrt{2}$ 倍，而在高噪声极限（$\sigma \to \infty$）下，这两种区域变得等价。

结果

• 区域有效性：该分析适用于 $\sigma \ge \sqrt{3/\ln M}$。该区域与 Ertan 和 van Dijk [12] 的不可能性结果互补，后者表明对于 $\sigma < 1/\sqrt{2 \ln M}$，权衡函数被界定在 $1-a$ 之外。综合这些结果，描绘了打乱 DP-SGD 的隐私景观。
• 复合界限：
  • 非渐近：迭代单个 epoch 界限得到 $f^{\otimes E}(a) \ge (1-\delta)^E - a$，意味着隐私损失对 $E$ 呈线性依赖。
  • 渐近：基于 Edgeworth 的分析表明了一种更紧密的依赖关系，其中与对角线的分离度按 $O(\mu \sqrt{E})$ 缩放，而非 $O(\mu E)$，前提是 $E$ 随 $M$ 呈次线性缩放。
• 实际意义：本文确定了单个 epoch 区域是打乱 DP-SGD 的“实际最佳点”。在客户端参与少量 epoch 的联邦学习场景中，使用现实的数据集大小即可实现有意义的隐私保证（$\delta \approx 0.01$）。相反，本文强调了“多 epoch 爆炸”现象，即在复合界限下增加 $E$ 会迅速使所需的数据集大小 $N$ 变得不切实际（例如，对于 $E=100$，需要 $N \sim 10^{11}$）。

意义与主张

本文声称提供了一种紧密的、封闭形式的分析，解决了文献中分析的算法（泊松）与实际部署的算法（随机打乱）之间的不匹配。通过推导透明、可解释的界限，作者使从业者能够直接读取参数要求，而无需依赖不透明的数值工具。

这项工作的意义在于：

1. 弥合理论与实践：验证了随机打乱（机器学习框架中的标准做法）允许进行严格的隐私分析，且在低噪声区域通常比泊松子采样更有利。
2. 定义隐私景观：补充现有的不可能性结果，以定义打乱 DP-SGD 中实现有意义隐私所需的精确噪声阈值。
3. 指导参数选择：提供具体的公式来选择 $M$、$N$ 和 $\sigma$ 以实现特定的隐私预算，这对于联邦学习应用尤为相关。

作者对未来工作保持谦逊，指出虽然渐近结果暗示多 epoch 情况下具有改进的 $\sqrt{E}$ 依赖关系，但推导这种依赖关系的具体、封闭形式证明（而非渐近极限）仍然是一个开放问题。此外，使 Edgeworth 展开中的序列 $\delta_M$ 和 $\gamma_M$ 显式化以获得具体的多 epoch 界限，被确定为未来的研究方向。