基于多尺度 FFT 的随机分配快速隐私损失核算

arXiv:2610.42117v1 公告类型：新论文 摘要：在随机分配采样方案中，每位用户的数据会用于从包含 $t$ 个步骤的序列中均匀随机选出的 $k$ 个步骤。已知该方案在隐私优化和通信高效聚合中优于泊松采样。该方案现有的隐私损失分布（PLD）核算器的运行时间与精度参数 $\alpha$ 的倒数呈二次关系（Feldman 和 Shenfeld，2026）。我们提出一种名为 \emph{multiscale FFT} 的算法，在每个二进尺度区间内均匀分布的网格上表示似然比，并利用各区间内的 FFT 精确计算每个两两求和结果的舍入值。该算法保留了原核算器的保证，并将运行时间对 $\alpha$ 的依赖从 $O(\alpha^{-2})$ 改进为 $O(\alpha^{-1}\log(1/\alpha))$。此外，我们证明，舍入可通过 Doroshenko 等人（2026）提出的保持均值的连点投影来完成。这使得舍入对隐私损失均值以及所计算分布对的 $\chi^2$ 散度引入的误差，从 $\alpha$ 量级降至 $O(\alpha^2/\log(t))$。实验表明，在高精度条件下，我们的算法实现了数个数量级的加速，并为结合 PREAMBLE 的 DP-SGD 提供了更优的隐私界。