知识卡片：基于多尺度 FFT 的随机分配采样隐私损失快速核算

一句话结论

论文提出“多尺度 FFT”算法，将随机分配（random allocation）采样方案下隐私损失分布（PLD）核算器运行时间对精度参数 α 的依赖从 O(α⁻²) 降到 O(α⁻¹log(1/α))，并在高精度下实现数个数量级加速、改进 DP-SGD with PREAMBLE 的隐私界。

事件概述或研究问题

在随机分配采样方案中，每个用户的数据被用于从 t 个步骤中随机均匀选出的 k 个步骤。该方案在私有优化和通信高效聚合中已知优于泊松采样。既有针对该方案的 PLD 核算器（Feldman and Shenfeld, 2026）运行时间与精度参数倒数 α 呈二次关系。本文研究如何在保持核算器保证的前提下降低该时间依赖，并控制舍入引入的误差。

方法/产品要点

• 提出 multiscale FFT 算法：在每个二进区间（dyadic interval）内使用均匀网格表示似然比，并在各区间内用 FFT 精确计算每一对求和（pairwise sum）的舍入。
• 保持原核算器的保证不变。
• 运行时间对 α 的依赖由 O(α⁻²) 改进为 O(α⁻¹log(1/α))。
• 证明舍入可通过 Doroshenko et al. (2026) 的保均值“连线投影”（mean-preserving connect-the-dots projection）完成。
• 该舍入方式将隐私损失均值与所计算对的 χ² 散度中的舍入误差从 α 量级降至 O(α²/log(t))。

主要结果或产业意义

• 实验中在高精度条件下取得数个数量级的加速。
• 给出 DP-SGD with PREAMBLE 更优（更紧）的隐私界。
• 对隐私核算工具链而言，意味着高精度 PLD 核算在随机分配采样下的计算成本大幅下降，可用于更紧的隐私预算评估。

为什么重要

随机分配采样在私有优化与通信高效聚合中优于泊松采样，但其 PLD 核算长期受限于 α⁻² 的时间开销；本文把该瓶颈降到近线性（α⁻¹log(1/α)），使高精度隐私核算在实践上更可行，并直接改进 DP-SGD with PREAMBLE 的隐私界。相对既有卡片（如 EdgeRefine 的图差分隐私、类别型 MRF 扩散样本复杂度、XRFormer 光谱分词），本条聚焦隐私核算算法复杂度这一不同层面，属于差分隐私工具链的增量进展，而非同一事实的重复。

局限与不确定性

• 论文为 arXiv 预印本（v1，2026-10-30），尚未确认同行评审状态，待核实。
• 实验细节（数据集、模型、具体加速倍数与隐私界数值）未在摘要中给出，待核实。
• “数个数量级加速”的具体条件（精度水平、t 与 k 取值）待核实。
• 与 PREAMBLE 结合时的完整实现与超参数设置待核实。

可用于图书/PPT/简报的角度

• 差分隐私核算器的“精度—时间”权衡：从 O(α⁻²) 到 O(α⁻¹log(1/α)) 的算法改进叙事。
• 多尺度/二进网格 + FFT 在隐私损失分布计算中的工程化思路。
• 舍入误差控制：保均值投影如何把均值与 χ² 散度误差压到 O(α²/log(t))。
• 采样方案选择（随机分配 vs 泊松采样）对私有优化与通信效率的影响。
• DP-SGD with PREAMBLE 的隐私界改进作为案例。

与既有脉络的关系

既有卡片分别涉及图差分隐私的效用平衡（EdgeRefine）、离散扩散样本复杂度、以及光谱表征学习，均不涉及 PLD 核算算法；本条为其补充“隐私核算算法复杂度”这一新维度，属于差分隐私工具链的独立增量，而非对上述卡片的延续或更新。

原始材料

• 标题：Fast Privacy Loss Accounting for Random Allocation via Multiscale FFT
• 作者：Vitaly Feldman, Moshe Shenfeld
• arXiv ID：2610.42117v1（cs.LG）
• 发布/更新：2026-10-30T17:51:03Z
• Abstract URL：https://arxiv.org/abs/2610.42117v1
• PDF URL：https://arxiv.org/pdf/2610.42117v1
• 关键词：random allocation；privacy loss distribution (PLD)；multiscale FFT；DP-SGD；PREAMBLE；χ² divergence；mean-preserving connect-the-dots projection