技术摘要：随机分配下矩阵机制的无采样隐私核算

问题陈述

本文解决了在利用矩阵分解机制结合随机分配（也称为“球入桶”或平衡迭代子采样方案）进行差分隐私模型训练时，计算紧确的确定性隐私保证所面临的挑战。

虽然通过子采样进行隐私放大是降低差分隐私随机梯度下降（DP-SGD）中噪声的标准技术，但由于其计算效率和均匀的数据覆盖性，“球入桶”方案在大规模训练中优于泊松子采样。然而，当与矩阵分解（通过引入跨迭代的相关噪声以提高效用）结合时，现有的隐私核算方法面临显著局限：

1. 蒙特卡洛依赖：近期方法（如 Choquette-Choo 等人，2025）依赖蒙特卡洛采样来估计放大参数。这种方法计算成本高昂，特别是在高隐私区域，所需样本量与 $\delta$ 成反比（例如，证明 $(\epsilon, 10^{-8})$-DP 的成本是 $(\epsilon, 10^{-3})$-DP 的 $10^5$ 倍）。
2. 概率性保证：这些基于采样的方法通常仅以高概率提供保证，或要求机制采用随机弃权，而非提供确定性的 $(\epsilon, \delta)$-DP 界限。
3. 计算不可行性：随机分配下矩阵机制的隐私损失分布涉及高维混合，使得在不采样的情况下精确评估曲棍球棒散度（hockey-stick divergence）变得不可行。

方法论

作者提出了两种截然不同的无采样核算程序，通过利用随机分配方案的结构以及矩阵分解引入的相关性，显式计算确定性界限。

1. 雷尼散度核算器（动态规划）

该方法计算雷尼散度的上界，随后利用标准转换定理将其转换为 $(\epsilon, \delta)$-DP。

• 核心洞察：“移除”方向（即从数据集中移除一个数据点）的隐私损失分布可以表示为源自策略矩阵 $C$ 的格拉姆矩阵 $G$ 的求和。
• 复杂度降低：对于一般矩阵，计算该求和被证明是 #P-完全的。然而，对于结构化矩阵（例如，策略矩阵 $C$ 具有带宽 $p$ 的带状矩阵），格拉姆矩阵 $G$ 继承了循环带状结构。
• 算法：作者 formulate 了一种动态规划方法，以精确计算 $p$-带状矩阵的求和。
  • 复杂度：运行时间从指数级 $O(2^\alpha)$（关于阶数 $\alpha$）降低到多项式级 $O(b p \alpha^{2p})$，其中 $b$ 是每个周期的批次数量。
  • 截断：对于非严格带状但条目快速衰减的矩阵（例如，带状逆矩阵），该方法截断格拉姆矩阵并添加一个可计算的加性修正项，以确保界限仍然有效。
• 添加方向：利用算术 - 几何平均不等式（AM-GM），针对“添加”方向推导了一个独立的、紧确的分析上界。

2. 条件组合核算器

该方法针对雷尼转换公式可能较为宽松的“小 $\epsilon$"（高隐私）区域。它克服了由噪声相关性和固定参与计数引起的步骤间依赖性。

• 概念：该方法不使用独立步骤假设，而是采用条件组合。它识别“好”结果，在这些结果中，步骤 $n$ 处机制的条件分布由一对固定的、可分解的分布 $(P^{(n)}, Q^{(n)})$ 控制。
• 坏事件：该方法通过界定其概率 $\delta_E$ 来考虑“坏”结果（即控制失效的情况）。总隐私损失是独立步骤的组合加上 $\delta_E$。
• 控制判据：作者基于高斯混合权重的逆风险函数推导了一个判据。他们表明，如果后验逆风险函数逐点小于目标分布的逆风险，则控制成立。
• 尾部界限：为了确定主导分布的参数，作者推导了三元高斯混合隐私损失的解析尾部界限。他们利用分布的变分族来收紧这些界限，通过优化温度参数以最小化尾部界限的标准差。
• 效率：虽然初始评估的复杂度为 $O(N^2 b^2)$，但针对不同噪声乘数 $\sigma$ 的后续评估可摊销至 $O(N b^2)$，使其在机制校准方面高效。

主要贡献

1. 确定性核算：本文引入了首个针对随机分配下矩阵机制计算确定性 $(\epsilon, \delta)$-DP 保证的无采样方法，消除了对蒙特卡洛估计的需求。
2. DP-SGD 的复杂度改进：对于不相关噪声（标准 DP-SGD）的特殊情况，所提出的雷尼核算器将随机分配下精确核算的计算复杂度从指数级 $O(2^\alpha)$ 提升至多项式级 $O(b \alpha^2)$，显著优于之前的精确方法。
3. 推广至相关噪声：该框架扩展至任意带状和非带状矩阵机制（包括带状平方根、带状逆和缓冲线性托普利茨），处理这些机制固有的复杂步间相关性。
4. 双区域紧确性：雷尼核算器（在低隐私/大 $\epsilon$ 区域表现强劲）与条件组合核算器（在高隐私/小 $\epsilon$ 区域更紧确）的结合提供了全面的核算解决方案。

结果

作者在各种矩阵机制（DP-SGD、BSR、BISR、BandMF、BandInvMF、BLT）和设置（单周期和多周期）下，将其方法与最先进的蒙特卡洛核算器进行了评估。

• 准确性：在低隐私区域（$\epsilon \ge 2$），雷尼核算器与蒙特卡洛参考值高度吻合。在高隐私区域（$\epsilon \le 1$），条件组合核算器产生更紧确的界限，允许使用比蒙特卡洛估计更小的校准噪声乘数 $\sigma$。
• 鲁棒性：性能在不同带宽（$p$）和批次数量（$b$）下均保持稳定。
• 效用：CIFAR-10 上的实验表明，源自这些无采样保证的噪声乘数保留了使用相关噪声相对于不相关噪声的效用优势。
• 运行时间：这些方法克服了蒙特卡洛采样的 $O(\delta^{-1})$ 依赖性。虽然条件组合核算器在 $N$ 较大时初始成本较高，但其针对校准的摊销成本在严格隐私预算下显著低于蒙特卡洛方法。

意义与主张

本文声称提供了针对具有相关梯度和参与度的机制的首个无采样隐私核算。其意义在于：

• 实现确定性保证：它消除了对概率性界限或随机弃权的依赖，这些方法对于生产系统而言往往不切实际或理论较弱。
• 可扩展性：通过将随机分配下精确雷尼核算的复杂度从指数级降低到多项式级，使得在蒙特卡洛采样计算上不可行的大规模训练运行中进行精确隐私核算成为可能。
• 实用校准：能够高效计算广泛 $\epsilon$ 和 $\delta$ 范围内的紧确界限，促进了噪声乘数的更好校准，直接改善了差分隐私深度学习中的效用 - 隐私权衡。

作者承认了局限性，指出雷尼核算器的复杂度在带宽 $p$ 上仍为指数级（尽管在 $\alpha$ 上为多项式级），且条件组合方法依赖于结果的粗略划分，这可能过于悲观。他们建议未来的工作可以探索更细粒度的划分和更高效的变分推断，以进一步收紧界限。