多尺度FFT加速随机分配隐私损失核算

随机分配采样与隐私损失核算的瓶颈

在差分隐私（DP）的随机分配采样方案中，每个用户的数据会被随机且均匀地从t个步骤中选取k个步骤使用。这种方案在私有优化和通信高效聚合中相比泊松采样更具优势，因为它能更均匀地分散隐私预算。然而，精确核算该方案的隐私损失并不容易。现有的隐私损失分布（PLD）核算器的时间复杂度与精度参数α的平方成反比（Feldman and Shenfeld, 2026），当需要高精度结果时，计算成本会急剧上升。

隐私损失分布（PLD）核算器是一类通过计算隐私损失随机变量的完整分布来精确评估差分隐私保证的数值方法。与基于矩 accountant（MA）或 Rényi DP 的解析上界不同，PLD 直接对隐私损失分布的似然比进行数值卷积，从而在相同隐私预算下给出更紧致的 ε 下界。其核心计算是对若干随机变量的分布做重复的加法卷积，通常用 FFT 在离散网格上加速。精度参数 α 控制网格分辨率，PLD 的误差大致与网格间距成正比，因此高精度核算需要极细的网格，计算量急剧膨胀。

随机分配采样（shuffled/random allocation sampling） 指在 t 个步骤中为每个用户随机均匀地选取 k 个步骤参与计算，而非独立地以概率 p 选入每一步（泊松采样）。由于每个用户的参与步数固定为 k，隐私预算在步骤间分布更均匀，避免了泊松采样下某些用户可能恰好参与过多步的尾部风险，因此在私有优化和通信高效聚合中常能获得更优的隐私-效用权衡。但固定基数采样破坏了步骤间的独立性，其隐私损失核算无法直接套用泊松采样的分解公式，需要专门处理。

多尺度FFT：算法核心设计

网格表示与分治策略

论文提出的多尺度FFT算法将似然比表示在一种特殊网格上：在每个二进区间（dyadic interval）内网格是均匀的，但不同区间的粒度不同。这种设计允许算法在粗粒度上处理大范围数值，在细粒度上处理关键区域。对于每一对需要相加的似然比，算法利用快速傅里叶变换（FFT）在每个区间内计算精确的舍入结果。

通过这种分治策略，算法将运行时间对α的依赖从O(α^{-2})降低到O(α^{-1} log(1/α))，在保持核算器原有保证的同时实现了显著的效率提升。实验表明，在高精度需求下，该算法能带来数个数量级的加速。

似然比（likelihood ratio） 是差分隐私核算的基本对象：对相邻数据集 D 和 D'，隐私损失定义为 L = log(P[M(D)=o] / P[M(D')=o])，其分布决定了 (ε, δ)-DP 的保证。PLD 核算器需要反复计算两个似然比分布的卷积，即求 L₁ + L₂ 的分布。在离散网格上，这一步通过 FFT 将卷积转化为频域逐点相乘，复杂度从 O(n²) 降到 O(n log n)，其中 n 是网格点数。

二进区间（dyadic interval） 指形如 [2^j, 2^{j+1}) 的区间。似然比分布的尾部随 |L| 增大而指数衰减，大部分概率质量集中在原点附近，但高精度核算又要求远端尾部也有足够分辨率。多尺度网格在每个二进区间内使用与该区间尺度匹配的均匀网格，使总网格点数仅随 α^{-1} 对数增长，而非 α^{-2}。FFT 在每个区间内独立进行，跨区间的质量通过重采样合并，这正是运行时间得以从 O(α^{-2}) 降到 O(α^{-1} log(1/α)) 的关键。

均值保持的舍入投影

除了加速计算，论文还解决了舍入误差问题。传统的舍入操作会在隐私损失的均值和χ²散度中引入量级为α的误差。作者采用Doroshenko等人（2026）提出的均值保持的“连点成线”投影（connect-the-dots projection）进行舍入，将这两类误差降低到O(α²/log(t))。这意味着在计算配对和时，舍入对隐私损失分布的关键统计量的扰动更小，从而得到更紧致的隐私边界。

χ² 散度 在此处用于衡量舍入后分布与真实分布之间的偏差：χ²(P‖Q) = ∫ (dP/dQ − 1)² dQ。它比总变差距离更敏感，因为 PLD 核算中反复卷积会放大单次舍入的系统性偏差，而 χ² 散度直接刻画了这种偏差在后续卷积中的累积效应。

“连点成线”投影（connect-the-dots projection） 是一种将任意离散分布映射到指定网格上的舍入规则：它不是把每个点的质量简单归入最近的格点，而是用分段线性函数连接相邻格点的累积分布，再在格点上采样。这种构造能精确保持分布的一阶矩（均值），并将二阶统计量（方差及 χ² 散度）的扰动控制在 O(α²) 量级。相比之下，最近邻舍入会引入 O(α) 的均值偏移，在多次卷积后累积成不可忽略的隐私边界松弛。均值保持舍入使核算器在高精度下仍能维持紧致的 ε 下界。

实验效果与应用

在实验中，多尺度FFT算法在高精度设置下实现了数个数量级的加速。更重要的是，该算法与DP-SGD结合PREAMBLE机制时，能够给出改进的隐私边界。这表明该工作不仅具有理论意义，还能直接提升实际隐私保护机器学习系统的效用——在相同的隐私预算下允许更多的训练迭代或更大的模型。

行业影响与展望

随机分配采样在联邦学习和分布式优化中具有广泛应用，而隐私核算的效率一直是制约其落地的关键因素之一。多尺度FFT通过算法层面的创新，将核算时间从二次依赖降至近线性，使得高精度隐私审计在更大规模场景下变得可行。未来，这一技术有望被集成到主流的DP库中，推动隐私保护技术的标准化和实用化。