# Computing Differential Privacy Guarantees for Heterogeneous Compositions Using FFT

arXiv: https://arxiv.org/abs/2102.12412 · HTML: https://mlsanity.com/paper/2102.12412/

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 34 references that are in the map.
- First posted on arXiv 24 Feb 2021.

## Builds on (most cited first, 12 of 12)

- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Renyi Differential Privacy](https://mlsanity.com/paper/1702.07476/) (2017)
- [Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergences](https://mlsanity.com/paper/1807.01647/) (2018)
- [Subsampled R'enyi Differential Privacy and Analytical Moments Accountant](https://mlsanity.com/paper/1808.00087/) (2018)
- [R'enyi Differential Privacy of the Sampled Gaussian Mechanism](https://mlsanity.com/paper/1908.10530/) (2019)
- [cpSGD: Communication-efficient and differentially-private distributed SGD](https://mlsanity.com/paper/1805.10559/) (2018)
- [The Discrete Gaussian for Differential Privacy](https://mlsanity.com/paper/2004.00010/) (2020)
- [Deep Learning with Gaussian Differential Privacy](https://mlsanity.com/paper/1911.11607/) (2019)
- [Tight Differential Privacy for Discrete-Valued Mechanisms and for the Subsampled Gaussian Mechanism Using FFT](https://mlsanity.com/paper/2006.07134/) (2020)
- [A Better Bound Gives a Hundred Rounds: Enhanced Privacy Guarantees via f-Divergences](https://mlsanity.com/paper/2001.05990/) (2020)
- [Shuffled Model of Federated Learning: Privacy, Communication and Accuracy Trade-offs](https://mlsanity.com/paper/2008.07180/) (2020)

## Built on by (most cited first, 20 of 20)

- [Numerical Composition of Differential Privacy](https://mlsanity.com/paper/2106.02848/) (2021)
- [Optimal Accounting of Differential Privacy via Characteristic Function](https://mlsanity.com/paper/2106.08567/) (2021)
- [Connect the Dots: Tighter Discrete Approximations of Privacy Loss Distributions](https://mlsanity.com/paper/2207.04380/) (2022)
- [Privacy-Preserving In-Context Learning for Large Language Models](https://mlsanity.com/paper/2305.01639/) (2023)
- [Composition of Differential Privacy & Privacy Amplification by Subsampling](https://mlsanity.com/paper/2210.00597/) (2022)
- [Private Fine-tuning of Large Language Models with Zeroth-order Optimization](https://mlsanity.com/paper/2401.04343/) (2024)
- [Individual Privacy Accounting with Gaussian Differential Privacy](https://mlsanity.com/paper/2209.15596/) (2022)
- [Threshold KNN-Shapley: A Linear-Time and Privacy-Friendly Approach to Data Valuation](https://mlsanity.com/paper/2308.15709/) (2023)
- [Faster Privacy Accounting via Evolving Discretization](https://mlsanity.com/paper/2207.04381/) (2022)
- [A Randomized Approach for Tight Privacy Accounting](https://mlsanity.com/paper/2304.07927/) (2023)
- [Gaussian DP for Reporting Differential Privacy Guarantees in Machine Learning](https://mlsanity.com/paper/2503.10945/) (2025)
- [Tight Accounting in the Shuffle Model of Differential Privacy](https://mlsanity.com/paper/2106.00477/) (2021)
- [The Saddle-Point Accountant for Differential Privacy](https://mlsanity.com/paper/2208.09595/) (2022)
- [Efficient privacy loss accounting for subsampling and random allocation](https://mlsanity.com/paper/2602.17284/) (2026)
- [Learning Numeric Optimal Differentially Private Truncated Additive Mechanisms](https://mlsanity.com/paper/2107.12957/) (2021)
- [Closed-Form Bounds for DP-SGD against Record-level Inference](https://mlsanity.com/paper/2402.14397/) (2024)
- [PREAMBLE: Private and Efficient Aggregation via Block Sparse Vectors](https://mlsanity.com/paper/2503.11897/) (2025)
- [Weights Shuffling for Improving DPSGD in Transformer-based Models](https://mlsanity.com/paper/2407.15414/) (2024)
- [Towards Reliable and Generalizable Differentially Private Machine Learning (Extended Version)](https://mlsanity.com/paper/2508.15141/) (2025)
- [Provable Robustness against Backdoor Attacks via the Primal-Dual Perspective on Differential Privacy](https://mlsanity.com/paper/2605.21780/) (2026)

## Abstract (arXiv)

The recently proposed Fast Fourier Transform (FFT)-based accountant for evaluating (varepsilon,δ)-differential privacy guarantees using the privacy loss distribution formalism has been shown to give tighter bounds than commonly used methods such as R'enyi accountants when applied to homogeneous compositions, i.e., to compositions of identical mechanisms. In this paper, we extend this approach to heterogeneous compositions. We carry out a full error analysis that allows choosing the parameters of the algorithm such that a desired accuracy is obtained. The analysis also extends previous results by taking into account all the parameters of the algorithm. Using the error analysis, we also give a bound for the computational complexity in terms of the error which is analogous to and slightly tightens the one given by Murtagh and Vadhan (2018). We also show how to speed up the evaluation of tight privacy guarantees using the Plancherel theorem at the cost of increased pre-computation and memory usage.