multiscale FFT 加速随机分配采样的差分隐私审计
Fast Privacy Loss Accounting for Random Allocation via Multiscale FFT
隐私审计的运行时间从 α^-2 压到 α^-1·log(1/α)，做 DP-SGD 训练的人能拿到更紧的隐私界，速度还快几个数量级。
论文针对 random allocation 采样机制（每个用户的数据用于从 t 步中随机均匀选取的 k 步）提出 multiscale FFT 算法。该算法在每个二进制区间内用均匀网格表示似然比，并逐区间用 FFT 计算成对和的精确舍入，把现有 PLD 审计器（Feldman 和 Shenfeld, 2026）的运行时间对精度参数 α 的依赖从 O(α^-2) 降到 O(α^-1·log(1/α))。论文还证明可用 Doroshenko et al. (2026) 的 mean-preserving connect-the-dots 投影执行舍入，把隐私损失均值和 χ² 散度的误差从 α 量级降到 O(α²/log(t))。实验显示在高精度下速度提升数个数量级，并为带 PREAMBLE 的 DP-SGD 给出更优的隐私界。
Fast Privacy Loss Accounting for Random Allocation via Multiscale FFT
In the random allocation sampling scheme each user's data is used in $k$ steps chosen randomly and uniformly from a sequence of $t$ steps. This scheme is known to improve on Poisson sampling in private optimization and in communication-efficient aggregation. The existing privacy loss distribution (PLD) accountant for this scheme runs in time quadratic in the inverse of the accuracy parameter $α$ (Feldman and Shenfeld, 2026). We give an algorithm, \emph{multiscale FFT}, that represents likelihood ratios on a grid that is uniform within each dyadic interval and computes the exact rounding of every pairwise sum using FFTs within each interval. It keeps the guarantees of the accountant and improves the dependence of its running time on $α$ from $O(α^{-2})$ to $O(α^{-1}\log(1/α))$. In addition, we demonstrate that rounding can be performed via the mean-preserving connect-the-dots projection of (Doroshenko et al., 2026). This reduces the errors that rounding introduces in the mean of the privacy loss and in the $χ^2$ divergence of the computed pair from the order of $α$ to $O(α^2/\log(t))$. In our experiments, our algorithm achieves speedups of several orders of magnitude at high accuracy and gives improved privacy bounds for DP-SGD with PREAMBLE.
