📊 statistics

Less Random, More Private: What is the Optimal Subsampling Scheme for DP-SGD?

本文证明，在差分隐私随机梯度下降（DP-SGD）中，用一种结构化的平衡迭代子采样（BIS）方案替代标准的泊松子采样，该方案在保持均匀边际参与度的同时消除了参与方差，从而实现了更优的隐私放大，并在低噪声情形下将所需的噪声乘数降低了高达 9.6%。

原作者： Andy Dong, Ayfer Özgür

发布于 2026-05-11

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Andy Dong, Ayfer Özgür

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象你正在运行一个庞大的秘密投票系统，用于训练一台智能计算机（人工智能）。你有一份庞大的人员名单（数据），在每一轮选举中，你都会挑选少数人进行投票。为了保护隐私，你会在结果中加入一点“杂音”（噪声），这样就没有人能确切知道谁投了什么票。

在过去十年中，挑选这些投票者的标准方法是泊松采样。这就像一场每个人都会买彩票的抽奖，但每个人获得的彩票数量是随机的。有些人可能被选中 10 次，有些人 0 次，还有些人 50 次，纯粹出于偶然。其逻辑是：“越多的随机性等于越强的隐私。”

重大发现
这篇由斯坦福大学研究人员撰写的论文指出，这种“抽奖”方法实际上存在缺陷。他们发现，一个人被选中次数的随机性会制造一个隐藏的弱点。这就像一场抽奖，有些人中了 50 次头奖，而有些人从未中奖；这种不平衡实际上会让聪明的攻击者更容易推断出谁在系统中。

他们提出了一种名为**平衡迭代采样（BIS）**的新方法。

创意类比：完美平衡的轮班

旧方法（泊松采样）：
想象你是一名经理，需要为 1000 名员工安排 100 天的轮班。你告诉所有人：“每天早上抛一枚硬币；如果是正面，你就上班。”

结果： 有些员工工作了 80 天，其他人只工作了 20 天。排班混乱不堪。
问题： 由于工作量如此不均，间谍可以查看总工作时长并猜测：“啊，那个工作了 80 天的人肯定就是我们要找的人！”方差（最忙与最不忙之间的差异）泄露了信息。

新方法（BIS）：
现在，想象你告诉所有人：“我们需要每天恰好有 50 人上班，并且在 100 天内，每个人总共恰好工作 50 天。”你洗牌并发牌，确保每个人恰好获得 50 个班次，但具体在哪几天工作仍然是随机的。

结果： 每个人的工作量完全相同。排班完美平衡。
优势： 间谍查看总工作时数后会发现：“所有人都工作了 50 天。我无法分辨谁是谁。”通过消除不平衡（方差），你实际上让系统更难被破解。

论文实际内容

更少的随机性，更强的隐私： 与直觉相反，论文证明限制随机性（确保每个人参与的次数完全相同）比让其完全随机能提供更强的隐私。
两种极端场景： 研究人员从数学上证明，这种新方法在两种极端情况下是“最佳可能”的：
- 当噪声非常低时（高效用）： 这是最重要的现实场景。在这里，旧抽奖方法的“不平衡”是最大的泄露源。BIS 解决了这个问题，允许你使用更少的噪声（最多减少 9.6%）来获得相同的隐私保护。更少的噪声意味着 AI 学习得更好，也更实用。
- 当噪声非常高时： 在这里，新方法的表现与旧抽奖方法一样好。它绝不会更差。
“数学魔法”（会计）：
- 计算这种新“平衡”方法的精确隐私度极其困难。这就像试图计算一副牌所有可能的发牌方式，这个数字之大足以让超级计算机崩溃。
- 作者构建了一个新的计算器（会计），使用了一个巧妙的技巧。它首先运行一个超快速的“筛选测试”，以查看特定场景是否值得检查。如果不是，它就跳过；如果是，它就进行繁重的数学运算。
- 这使得他们能够在没有任何“猜测”或松散近似的情况下证明，新方法确实更优。

核心结论

这篇论文推翻了一个长期持有的信念，即“越多的随机性总是对隐私越好”。相反，它表明结构和平衡更胜一筹。

通过从混乱的抽奖（泊松采样）切换到完美平衡的排班（BIS），你可以训练出更准确的隐私保护 AI 模型（因为你需要的噪声更少），同时保持相同水平的隐私保护。作者甚至发布了这个新计算器的代码，以便其他人可以立即使用。

简而言之： 如果你想要为你的 AI 获得最佳隐私，就不要再让骰子随机滚动了。给每个人一个公平、固定的轮次，你将获得更强大的防护盾。

技术摘要：更少随机，更隐私

问题陈述

在差分隐私随机梯度下降（DP-SGD）中，数据子采样方案的选择是隐私 - 效用权衡的核心驱动因素。过去十年间，泊松子采样一直是默认机制，其中每个样本以固定概率独立地参与每次迭代。这一选择主要基于分析上的便利性，以及“非结构化随机性最大化隐私放大”的直觉。

然而，作者指出了该方法的一个根本缺陷：泊松子采样的无约束随机性引入了显著的参与方差。在泊松子采样中，特定样本参与的迭代次数服从二项分布，导致不同样本的参与次数出现大幅波动。本文认为，这种方差并非仅仅是实践中的产物，而是隐私放大次优化的根本来源，特别是在与高效用训练相关的低噪声机制中。

核心研究问题是：在独立样本机制家族中（即每个样本独立地生成其参与模式，但受限于固定的期望参与次数），DP-SGD 理论上最优的数据子采样方案是什么？

方法论

1. 隐私损失的理论分析

作者在“零出”（zero-out）邻接关系下分析了隐私损失随机变量 $L(y) = \log(P(y)/Q(y))$ ，其中 $P$ 是包含一个不同示例的输出分布， $Q$ 是不包含该示例的分布。他们推导了隐私损失在噪声乘数 $\sigma$ 的两个极端机制下的渐近行为：

低噪声极限（ $\sigma \to 0$ ）：
在此机制下（与高效用部署相关），隐私损失主要由项 $\|x\|_2^2 / (2\sigma^2)$ 主导，其中 $x$ 是参与向量。分析表明，隐私损失的上尾主要由 $\|x\|_2^2$ （参与次数）的波动驱动。
- 优化策略： 为了最小化隐私损失，必须首先消除 $\|x\|_2^2$ 的方差。这要求强制实施确定性的参与次数 $k$ 。只有在固定方差之后，分布的熵（在有效模式中最大化随机性）才成为次要的优化因素。
- 结果： 允许参与次数存在方差的泊松子采样是次优的。最优策略是平衡迭代子采样（Balanced Iteration Subsampling, BIS），其中每个样本恰好参与 $T$ 次迭代中的 $k$ 次，且这些迭代是均匀随机选择的。
高噪声极限（ $\sigma \to \infty$ ）：
在此机制下，主导项由边际参与概率 $\mu = E[x]$ 决定。
- 优化策略： 一阶项要求均匀的边际概率（ $\mu_t = k/T$ ）。泊松子采样和 BIS 均满足此条件。二阶项涉及参与向量的协方差矩阵 $\Sigma$ 。为了最小化最坏情况下的尾部，方案必须消除全 1 向量方向上的方差（即 $\text{Var}(\sum x_t) = 0$ ）。
- 结果： BIS 是最优的，因为它确定性地固定了总参与次数，消除了该方差。虽然泊松子采样在主导阶上与 BIS 匹配，但 BIS 最小化了二阶波动，理论上趋近于缩放后的全批量更新的基本下界。

2. 近精确蒙特卡洛核算

为了将这些渐近洞察转化为有限噪声下的保证，作者解决了评估 BIS 精确隐私成本计算不可行的问题。精确评估需要对 $\binom{T}{k}$ 种组合求和，这在组合上是爆炸性的。

他们引入了一种**“先筛选后精确”（Screen-Then-Exact）**的蒙特卡洛核算器：

**动态规划（$O(Tk) $）：** 他们推导了一种动态规划公式，以$ O(Tk) $的时间复杂度计算精确似然比$ P(y)/Q(y) $，将复杂度从$ O(\binom{T}{k})$ 降低。
筛选界（ $O(T)$ ）： 他们证明了一个快速的上界（引理 4.1），用于计算似然比，其计算时间为 $O(T)$ 。
过滤机制： 在蒙特卡洛核算中，仅当样本的对数似然比超过目标 $\epsilon$ 时，才将其计入隐私预算 $\delta$ 。 $O(T)$ 的筛选界充当过滤器：如果该界 $\le \epsilon$ ，则直接丢弃该样本，无需运行昂贵的 $O(Tk)$ 精确计算。
效率： 经验表明，只有 $O(\delta)$ 比例的样本会超过该界。这将启发式预期运行时间降低至 $O(T + \delta Tk)$ ，使得近精确核算在大规模训练中变得可行。

主要贡献

理论最优性： 本文证明，在独立样本子采样方案中，**平衡迭代子采样（BIS）**在噪声谱的两个极端（ $\sigma \to 0$ 和 $\sigma \to \infty$ ）下均是最优的。它推翻了“最大化随机性产生最强隐私”的直觉；相反，消除参与方差是低噪声机制下隐私放大的主要驱动力。
近精确有限噪声核算： 作者引入了一种实用的 BIS 蒙特卡洛核算器，消除了现有 Rényi 差分隐私（RDP）和基于组合的隐私损失分布（PLD）分析中固有的分析松弛。这是通过 $O(Tk) $动态规划和$ O(T)$ 筛选界实现的。
实证验证： 通过对 60 多种实际 DP-SGD 配置的评估，研究表明，在低噪声机制下，BIS 始终优于泊松子采样。

结果

隐私增益： 在低噪声机制（高效用）下，使用新的近精确核算器评估时，与泊松子采样相比，BIS 将所需的噪声乘数降低了高达 9.6%。
高噪声下的收敛： 在高噪声机制下，正如渐近理论所预测，BIS 和泊松子采样的隐私保证趋于收敛，BIS 匹配了基本下界。
核算松弛： 研究揭示，先前使用 RDP 或基于组合的 PLD（例如"RA-PLD"）对 BIS 的分析引入了显著的分析松弛。在某些设置中，这些宽松的界表明 BIS 比泊松子采样需要多 20.5% 的噪声，错误地暗示 BIS 更差。近精确蒙特卡洛核算纠正了这一点，表明 BIS 严格优于或等同于泊松子采样。
相关性： BIS 的实证优势与比率 $\epsilon/k$ 强相关（皮尔逊相关系数 0.93），证实了当每次参与的隐私预算较高（即低噪声机制）时，其优势最为显著。

意义与主张

本文主张推翻“更多采样随机性必然产生更强隐私放大”的普遍直觉。相反，它确立了结构化参与——具体而言，在保持均匀边际概率的同时消除参与次数方差——是 DP-SGD 中实现最优隐私放大的关键。

这项工作的意义在于：

完善 DP 直觉： 它将焦点从最大化熵转移到最小化参与过程中的方差，以实现隐私放大。
实用效用： 通过降低所需的噪声乘数，BIS 使得在不增加隐私预算的情况下提高私有模型的效用成为可能，或者在相同效用下提供更严格的隐私保证。
方法严谨性： “先筛选后精确”核算器的开发为获取复杂子采样机制的紧密、近精确隐私保证提供了蓝图，超越了基于组合界的松散性。

作者得出结论，BIS 是泊松子采样的稳健且原则性的替代方案，为推动私有训练的帕累托前沿提供了一条严谨的路径。