# Tight Differential Privacy for Discrete-Valued Mechanisms and for the Subsampled Gaussian Mechanism Using FFT

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

## Key facts

- Cited by 43 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Jun 2020.

## Built on by (most cited first, 30 of 43)

- [Differentially Private Fine-tuning of Language Models](https://mlsanity.com/paper/2110.06500/) (2021)
- [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)
- [Improved Differential Privacy for SGD via Optimal Private Linear Operators on Adaptive Streams](https://mlsanity.com/paper/2202.08312/) (2022)
- [Connect the Dots: Tighter Discrete Approximations of Privacy Loss Distributions](https://mlsanity.com/paper/2207.04380/) (2022)
- [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)
- [Bayesian Estimation of Differential Privacy](https://mlsanity.com/paper/2206.05199/) (2022)
- [Fast and Memory Efficient Differentially Private-SGD via JL Projections](https://mlsanity.com/paper/2102.03013/) (2021)
- [Fine-Tuning Large Language Models with User-Level Differential Privacy](https://mlsanity.com/paper/2407.07737/) (2024)
- [Mind the Privacy Unit! User-Level Differential Privacy for Language Model Fine-Tuning](https://mlsanity.com/paper/2406.14322/) (2024)
- [Computing Differential Privacy Guarantees for Heterogeneous Compositions Using FFT](https://mlsanity.com/paper/2102.12412/) (2021)
- [Individual Privacy Accounting with Gaussian Differential Privacy](https://mlsanity.com/paper/2209.15596/) (2022)
- [Gradient Descent with Linearly Correlated Noise: Theory and Applications to Differential Privacy](https://mlsanity.com/paper/2302.01463/) (2023)
- [Privacy-Aware Document Visual Question Answering](https://mlsanity.com/paper/2312.10108/) (2023)
- [Faster Privacy Accounting via Evolving Discretization](https://mlsanity.com/paper/2207.04381/) (2022)
- [Avoiding Pitfalls for Privacy Accounting of Subsampled Mechanisms under Composition](https://mlsanity.com/paper/2405.20769/) (2024)
- [Improving the Privacy and Practicality of Objective Perturbation for Differentially Private Linear Learners](https://mlsanity.com/paper/2401.00583/) (2023)
- [A Randomized Approach for Tight Privacy Accounting](https://mlsanity.com/paper/2304.07927/) (2023)
- [Subsampling is not Magic: Why Large Batch Sizes Work for Differentially Private Stochastic Optimisation](https://mlsanity.com/paper/2402.03990/) (2024)
- [Skellam Mixture Mechanism: a Novel Approach to Federated Learning with Differential Privacy](https://mlsanity.com/paper/2212.04371/) (2022)
- [Auditing Differential Privacy Guarantees Using Density Estimation](https://mlsanity.com/paper/2406.04827/) (2024)
- [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)
- [Group privacy for personalized federated learning](https://mlsanity.com/paper/2206.03396/) (2022)
- [The Saddle-Point Accountant for Differential Privacy](https://mlsanity.com/paper/2208.09595/) (2022)
- [Cactus Mechanisms: Optimal Differential Privacy Mechanisms in the Large-Composition Regime](https://mlsanity.com/paper/2207.00420/) (2022)
- [Breaking the Communication-Privacy-Accuracy Tradeoff with f-Differential Privacy](https://mlsanity.com/paper/2302.09624/) (2023)
- [Efficient privacy loss accounting for subsampling and random allocation](https://mlsanity.com/paper/2602.17284/) (2026)
- [D3p -- A Python Package for Differentially-Private Probabilistic Programming](https://mlsanity.com/paper/2103.11648/) (2021)

## Abstract (arXiv)

We propose a numerical accountant for evaluating the tight (varepsilon,δ)-privacy loss for algorithms with discrete one dimensional output. The method is based on the privacy loss distribution formalism and it uses the recently introduced fast Fourier transform based accounting technique. We carry out an error analysis of the method in terms of moment bounds of the privacy loss distribution which leads to rigorous lower and upper bounds for the true (varepsilon,δ)-values. As an application, we present a novel approach to accurate privacy accounting of the subsampled Gaussian mechanism. This completes the previously proposed analysis by giving strict lower and upper bounds for the privacy parameters. We demonstrate the performance of the accountant on the binomial mechanism and show that our approach allows decreasing noise variance up to 75 percent at equal privacy compared to existing bounds in the literature. We also illustrate how to compute tight bounds for the exponential mechanism applied to counting queries.