When training machine learning models or executing iterative queries under Differential Privacy (DP), tracking the cumulative privacy loss is essential. Every time an algorithm accesses sensitive data—such as during a gradient descent step—a small amount of privacy budget is consumed. A "privacy accountant" tracks these increments to guarantee a total privacy budget, typically expressed via the parameters $(\epsilon, \delta)$.
Historically, calculating the exact cumulative privacy loss across thousands of iterations was computationally impractical. Practitioners relied on analytical relaxations like the Moments Accountant or Rényi Differential Privacy (RDP). While computationally fast, these methods introduce loose bounds, overestimating the privacy loss and forcing the addition of unnecessary noise that degrades model utility.
A powerful alternative approach bypasses these approximations by moving privacy accounting into the frequency domain. By leveraging the Fast Fourier Transform (FFT), this methodology computes nearly exact privacy guarantees orders of magnitude faster than traditional numerical methods.
The Composition Problem as a Convolution
To understand why the Fourier approach works, we must look at how privacy loss accumulates. As Sarwate et al. describe, a private algorithm can be viewed as an information-theoretic channel. The privacy loss itself is a random variable—often called the Privacy Loss Random Variable (PRV)—which reflects the log-likelihood ratio of the algorithm's outputs computed on two neighboring datasets.
When we compose multiple independent private mechanisms (such as sequential iterations in a training loop), the total privacy loss is simply the sum of these independent random variables.
In probability theory, the distribution of the sum of independent random variables is determined by the convolution of their individual probability distributions. Therefore, tracking exact cumulative privacy loss requires computing a multi-fold convolution of Privacy Loss Distributions (PLDs).
Iterative DP Steps (PRVs) ---> Sum of Random Variables ---> Convolution of PLDs
If we discretize these continuous distributions onto a grid of size $n$ to compute them numerically, a standard direct convolution requires algebraic combinations that scale quadratically, resulting in a computational complexity of $O(n^2)$. Performing this operation sequentially over hundreds or thousands of iterations creates a severe computational bottleneck.
The Fourier Transform Trick
The core insight of the frequency-domain approach—introduced via the "Fourier Accountant" framework by Koskela et al. (2019) and Koskela et al. (2020)—is to exploit a fundamental mathematical property of the Fourier transform: convolution in the primary domain corresponds to element-wise (pointwise) multiplication in the frequency domain.
Instead of convolving the discretized PLDs directly in the data domain, the process shifts to the frequency domain:
- Transform: Apply the Fast Fourier Transform (FFT) to the discretized individual privacy loss distributions.
- Multiply: Multiply the transformed distributions together element-wise. For $k$ identical iterations, this simplifies to raising each element to the power of $k$.
- Inverse Transform: Apply the Inverse Fast Fourier Transform (IFFT) to bring the composed distribution back to the primary domain.
[PLD 1] --FFT--> [Frequency Domain]
\
(Element-wise Multiplication) --> [Composed Frequency] --IFFT--> [Exact Total PLD]
/
[PLD 2] --FFT--> [Frequency Domain]
By substituting quadratic convolution with the log-linear complexity of the FFT, the computational overhead drops from $O(n^2)$ to $O(n \log n)$. As Koskela et al. (2021) demonstrate, this mathematical shift makes the execution time largely independent of the number of composition steps $k$. Complex compositions that would otherwise take hours can be computed with high precision in less than a second.
Tighter Bounds and Better Utility
The primary benefit of shifting to the frequency domain is accuracy. Because the FFT computes the exact numerical composition of the distributions (up to minor discretization errors), it avoids the loose tail bounds inherent to moments-based approximations.
Tighter privacy accounting directly translates to better machine learning performance. When the accountant provides a more precise, less pessimistic estimate of the privacy loss, practitioners do not need to inject as much noise into the system to guarantee a target $(\epsilon, \delta)$ budget. For instance, Koskela et al. (2021) showed that using FFT-based accounting can reduce the required noise variance by up to 75% for certain discrete and subsampled mechanisms compared to previous accounting techniques.
To ensure this method remains robust at scale, Wutschitz et al. developed refined algorithms for convolving discretized PRVs alongside rigorous error analysis. Their work achieves near-optimal runtimes, ensuring that numerical truncation and discretization errors do not compromise the mathematical validity of the final privacy guarantee when training large-scale models.
Applications Across Privacy Frameworks
The flexibility of convolving privacy losses via the frequency domain has allowed it to expand into several distinct privacy frameworks:
- The Shuffle Model: In decentralized architectures where user data is anonymized via an intermediary shuffler, Koskela et al. (2023) and Zeng et al. adapted FFT accounting to handle unified shuffle protocols. By converting the shuffle model's complex privacy loss distributions into the frequency domain, they achieved an efficient $O(n)$ approximation cost, making tight accounting scalable for federated learning.
- Individual Privacy Accounting: Standard accounting tracks the absolute worst-case privacy loss across an entire dataset. Koskela et al. (2023) integrated FFT composition with Gaussian Differential Privacy (GDP) to track individual privacy losses per sample in linear time, allowing models to train longer by avoiding global worst-case assumptions.
- Alternative Mechanisms: Beyond standard Gaussian noise, newer mechanisms like the Spherical Generalized Gamma family introduced by Wei et al. leverage Fourier-based accounting to maintain tight tracking in lower-dimensional settings.
- Software Integration: To bridge the gap between theory and practice, the open-source Python package
d3pdeveloped by Prediger et al. implements these Fourier transform-based composition methods directly on top of JAX, bringing automated, high-precision privacy accounting to probabilistic programming workflows.
Even in Local Differential Privacy (LDP), the core concept of using transforms to eliminate quadratic bottlenecks manifests. For example, Acharya et al. introduced the Hadamard Response, which uses the Fast Walsh-Hadamard Transform to let a server aggregate private samples and decode large-domain distributions in nearly linear time. Across all these variations, the underlying principle remains the same: mapping private distributions into a transform domain unlocks the computational efficiency needed for tight, scalable privacy protection.
Key Foundational Work
Computing Tight Differential Privacy Guarantees Using FFT (2020) — contributed 3 concept elements to this direction.
Computing Exact Guarantees for Differential Privacy (2019) — contributed 2 concept elements to this direction.
Hadamard Response: Estimating Distributions Privately, Efficiently, and with Little Communication (2019) — contributed 1 concept elements to this direction.