Fast Privacy Loss Accounting for Random Allocation via Multiscale FFT

Vitaly Feldman; Moshe Shenfeld

cs.LGOct 30, 2026

Fast Privacy Loss Accounting for Random Allocation via Multiscale FFT

Authors: Vitaly Feldman, Moshe Shenfeld

Abstract

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, 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.

Figures & tables

Panel of Figure 1 — Figure 1: The dyadic grid and the merge step for $m=4$ . Top: the grid $\mathcal{G}_{4}$ and its bands $B_{j}=[2^{j},2^{j+1})$ (bands $-2,-3,\ldots$ accumulate at zero), where band $2$ is $[4,8)$ with spacing $h_{2}=1$ . Bottom: the uniform grid of band $2$ extended down to zero. A value $y$ below band $2$ is projected onto this grid (arrows), after which the mass below band $2$ occupies $m+1$ points. The knots of $\mathcal{G}_{4}$ in $[4,16)$ (dashed, in bands $2$ and $3$ ) are a subset of this grid, and $[4,16)$ contains the support of the three convolutions at band $2$ (band $2$ of both inputs with each other, and band $2$ of each input with the projected prefix of the other). Thus projecting the sums onto $\mathcal{G}_{4}$ gives the same measure as projecting the exact sums (Theorem 3.1 ).

Figure 2: Running time against the discrepancy

\varepsilon-\varepsilon_{\mathrm{ref}}

of the computed upper bound

\varepsilon

\delta=10^{-6}

from a reference

\varepsilon_{\mathrm{ref}}

, for direct convolution with rounding and multiscale FFT with CtD projections, for

t\in\{10,1000\}

, a single allocation (left) and its

100

-fold composition (right), with

\sigma=1

(top) and

\sigma=4

(bottom). Here

\varepsilon_{\mathrm{ref}}

is the bound of multiscale FFT with at least twice the largest

m

used in the same setting. The vertical lines mark the resolution of

\varepsilon_{\mathrm{ref}}

for each

t

, its difference from the bound with half its

m

. Each curve ends once its bound comes within twice this resolution of

\varepsilon_{\mathrm{ref}}

. A bound within this resolution of

\varepsilon_{\mathrm{ref}}

, or below it, is drawn on the line.

Figure 3: The comparison of Figure 2 at

t=1000

for the four combinations of the convolution method (direct convolution on the geometric grid or multiscale FFT on the dyadic grid) and the projection (rounding or CtD). The discrepancy

\varepsilon-\varepsilon_{\mathrm{ref}}

is as in Figure 2 , and the dotted line marks the resolution of

\varepsilon_{\mathrm{ref}}

, its difference from the bound with half its

m

Figure 4: The ratio between the noise scales required for

(1,10^{-6})

-DP by DP-SGD with PREAMBLE and by DP-SGD with Gaussian noise addition, as a function of the block size

B

, in the four settings of FS26. The results for RDP [ FS25 ] and for direct convolution are from FS26.

Privacy Accounting

See all 9 papers

Efficient privacy loss accounting for subsampling and random allocation
Feb 19, 2026Vitaly Feldman, Moshe ShenfeldPrivacy Accounting Differential Privacy
Apple · The Hebrew University of Jerusalem · *Work partially done while author was an intern at Apple.
Less Random, More Private: What is the Optimal Subsampling Scheme for DP-SGD?
May 8, 2026Andy Dong, Ayfer ÖzgürDifferentially Private Stochastic Gradient Descent Privacy Accounting
Stanford University
Counting on Dummies: Privacy Amplification with Observable Counts and Truncated Batches
Oct 30, 2026Vitaly Feldman, Audra McMillan, Kunal TalwarDifferential Privacy Differentially Private Stochastic Gradient Descent
Apple

Feb 19, 2026J/K move · Enter open · S save

Efficient privacy loss accounting for subsampling and random allocation

Vitaly Feldman, Moshe Shenfeld

Apple · The Hebrew University of Jerusalem · *Work partially done while author was an intern at Apple.

Privacy Accounting Differential Privacy Privacy-Utility Tradeoff

Open paper AskPDF arXiv

We consider the privacy amplification properties of a sampling scheme in which a user's data isused in

k

steps chosen randomly and uniformly from a sequence (or set) of

t

steps. This sampling scheme has been recently applied in the context of differentially private optimization (Chua et al., 2024a; Choquette-Choo et al., 2025) and communication-efficient high-dimensional private aggregation (Asi et al., 2026), where it was shown to have utility advantages over the standard Poisson sampling. Theoretical analyses of this sampling scheme (Feldman & Shenfeld, 2025; Dong et al., 2025) lead to bounds that are close to those of Poisson sampling, yet still have two significant shortcomings. First, in many practical settings, the resulting privacy parameters are not tight due to the approximation steps in the analysis. Second, the computed parameters are either the hockey stick or Renyi divergence, both of which introduce overheads when used in privacy loss accounting. In this work, we demonstrate that the privacy loss distribution (PLD) of random allocation applied to any differentially private algorithm can be computed efficiently. When applied to the Gaussian mechanism, our results demonstrate that the privacy-utility trade-off for random allocation is at least as good as that of Poisson subsampling. In particular, random allocation is better suited for training via DP-SGD. To support these computations, our work develops new tools for general privacy loss accounting based on a notion of PLD realization. This notion allows us to extend accurate privacy loss accounting to subsampling which previously required manual noise-mechanism-specific analysis.

Abstract

Privacy Accounting

Explore similar work

Efficient privacy loss accounting for subsampling and random allocation

Less Random, More Private: What is the Optimal Subsampling Scheme for DP-SGD?

Counting on Dummies: Privacy Amplification with Observable Counts and Truncated Batches