Multi-scale FFT Accelerates Privacy Loss Accounting for Random Allocation Sampling

The Bottleneck of Random Allocation Sampling and Privacy Loss Accounting

In the random allocation sampling scheme of differential privacy (DP), each user's data is randomly and uniformly selected from t steps to be used in k steps. This scheme has advantages over Poisson sampling in private optimization and communication-efficient aggregation because it distributes the privacy budget more evenly. However, accurately accounting for the privacy loss of this scheme is not easy. The existing privacy loss distribution (PLD) accountant's time complexity is inversely proportional to the square of the accuracy parameter α (Feldman and Shenfeld, 2026), and the computational cost rises sharply when high-accuracy results are needed.

Privacy Loss Distribution (PLD) accountant is a class of numerical methods that precisely evaluate differential privacy guarantees by computing the full distribution of the privacy loss random variable. Unlike analytical upper bounds based on the moments accountant (MA) or Rényi DP, PLD directly performs numerical convolution on the likelihood ratio of the privacy loss distribution, thereby giving a tighter ε lower bound under the same privacy budget. Its core computation is repeated additive convolution of the distributions of several random variables, usually accelerated by FFT on a discrete grid. The accuracy parameter α controls the grid resolution, and the PLD error is roughly proportional to the grid spacing; therefore, high-accuracy accounting requires an extremely fine grid, and the computational cost expands dramatically.

Random allocation sampling (shuffled/random allocation sampling) means that for each user, k out of t steps are randomly and uniformly selected for participation in computation, rather than independently selecting each step with probability p (Poisson sampling). Since each user's number of participating steps is fixed at k, the privacy budget is distributed more evenly across steps, avoiding the tail risk in Poisson sampling that some users may happen to participate in too many steps. Therefore, it often achieves a better privacy-utility trade-off in private optimization and communication-efficient aggregation. However, fixed-cardinality sampling breaks the independence between steps, and its privacy loss accounting cannot directly apply the decomposition formula for Poisson sampling; it requires special handling.

Multi-scale FFT: Core Algorithm Design

Grid Representation and Divide-and-Conquer Strategy

The multi-scale FFT algorithm proposed in the paper represents the likelihood ratio on a special grid: within each dyadic interval the grid is uniform, but different intervals have different granularities. This design allows the algorithm to handle a wide range of values at coarse granularity and key regions at fine granularity. For each pair of likelihood ratios that need to be added, the algorithm uses the fast Fourier transform (FFT) to compute the exact rounding result within each interval.

Through this divide-and-conquer strategy, the algorithm reduces the runtime's dependence on α from O(α^{-2}) to O(α^{-1} log(1/α)), achieving significant efficiency gains while preserving the accountant's original guarantees. Experiments show that under high-accuracy requirements, this algorithm can bring speedups of several orders of magnitude.

Likelihood ratio is the basic object of differential privacy accounting: for neighboring datasets D and D', the privacy loss is defined as L = log(P[M(D)=o] / P[M(D')=o]), and its distribution determines the (ε, δ)-DP guarantee. The PLD accountant needs to repeatedly compute the convolution of two likelihood ratio distributions, that is, the distribution of L₁ + L₂. On a discrete grid, this step uses FFT to convert convolution into pointwise multiplication in the frequency domain, reducing the complexity from O(n²) to O(n log n), where n is the number of grid points.

Dyadic interval refers to an interval of the form [2^j, 2^{j+1}). The tail of the likelihood ratio distribution decays exponentially as |L| increases, and most of the probability mass is concentrated near the origin, but high-accuracy accounting also requires sufficient resolution in the far tail. The multi-scale grid uses a uniform grid matching the scale of each dyadic interval within that interval, so that the total number of grid points grows only logarithmically with α^{-1}, rather than α^{-2}. FFT is performed independently within each interval, and mass across intervals is merged by resampling. This is precisely the key to reducing the runtime from O(α^{-2}) to O(α^{-1} log(1/α)).

Mean-Preserving Rounding Projection

In addition to accelerating computation, the paper also addresses the rounding error problem. Traditional rounding operations introduce errors of order α into the mean and χ² divergence of the privacy loss. The authors use the mean-preserving "connect-the-dots" projection proposed by Doroshenko et al. (2026) for rounding, reducing these two types of errors to O(α²/log(t)). This means that when computing pairwise sums, rounding perturbs the key statistics of the privacy loss distribution less, thereby yielding tighter privacy bounds.

χ² divergence is used here to measure the deviation between the rounded distribution and the true distribution: χ²(P‖Q) = ∫ (dP/dQ − 1)² dQ. It is more sensitive than total variation distance because repeated convolution in PLD accounting amplifies the systematic bias of a single rounding, and χ² divergence directly characterizes the cumulative effect of this bias in subsequent convolutions.

"Connect-the-dots" projection is a rounding rule that maps an arbitrary discrete distribution onto a specified grid: instead of simply assigning the mass of each point to the nearest grid point, it connects the cumulative distributions of adjacent grid points with a piecewise linear function and then samples on the grid points. This construction can exactly preserve the first moment (mean) of the distribution and control the perturbation of second-order statistics (variance and χ² divergence) at the order of O(α²). In contrast, nearest-neighbor rounding introduces a mean shift of O(α), which accumulates after multiple convolutions into a non-negligible relaxation of the privacy bound. Mean-preserving rounding enables the accountant to maintain a tight ε lower bound even at high accuracy.

Experimental Results and Applications

In experiments, the multi-scale FFT algorithm achieved speedups of several orders of magnitude under high-accuracy settings. More importantly, when combined with DP-SGD and the PREAMBLE mechanism, the algorithm can provide improved privacy bounds. This shows that the work not only has theoretical significance but can also directly improve the utility of practical privacy-preserving machine learning systems—allowing more training iterations or larger models under the same privacy budget.

Industry Impact and Outlook

Random allocation sampling is widely used in federated learning and distributed optimization, and the efficiency of privacy accounting has always been one of the key factors constraining its deployment. Through algorithmic innovation, multi-scale FFT reduces accounting time from quadratic dependence to near-linear, making high-accuracy privacy auditing feasible in larger-scale scenarios. In the future, this technology is expected to be integrated into mainstream DP libraries, promoting the standardization and practical adoption of privacy-preserving technologies.

One-line Summary

Multi-scale FFT reduces privacy accounting for random allocation sampling from O(α⁻²) to near-linear while preserving the rounding mean.

Paragraph Summary

The article introduces the privacy loss distribution (PLD) accounting challenge for the random allocation sampling scheme in differential privacy. The existing accountant's time complexity is inversely proportional to the square of the accuracy parameter α, and the computational cost rises sharply under high-accuracy requirements. The paper proposes a multi-scale FFT algorithm that represents the likelihood ratio on a special grid that is uniform within dyadic intervals and has different granularities across intervals, uses FFT to compute rounding results exactly within each interval, and reduces the dependence on α from O(α^{-2}) to O(α^{-1} log(1/α)). At the same time, it uses a mean-preserving "connect-the-dots" projection for rounding, reducing the mean and χ² divergence errors from O(α) to O(α²/log(t)). Experiments show speedups of several orders of magnitude in high-accuracy scenarios and provide tighter privacy bounds for DP-SGD with PREAMBLE.