# Numerical Composition of Differential Privacy

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

## Key facts

- Cited by 180 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 25 references that are in the map.
- First posted on arXiv 5 Jun 2021.

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

- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Renyi Differential Privacy](https://mlsanity.com/paper/1702.07476/) (2017)
- [Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds](https://mlsanity.com/paper/1605.02065/) (2016)
- [The Composition Theorem for Differential Privacy](https://mlsanity.com/paper/1311.0776/) (2013)
- [Improving the Gaussian Mechanism for Differential Privacy: Analytical Calibration and Optimal Denoising](https://mlsanity.com/paper/1805.06530/) (2018)
- [Concentrated Differential Privacy](https://mlsanity.com/paper/1603.01887/) (2016)
- [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)
- [Fast and Memory Efficient Differentially Private-SGD via JL Projections](https://mlsanity.com/paper/2102.03013/) (2021)
- [Computing Differential Privacy Guarantees for Heterogeneous Compositions Using FFT](https://mlsanity.com/paper/2102.12412/) (2021)

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

- [Large Language Models Can Be Strong Differentially Private Learners](https://mlsanity.com/paper/2110.05679/) (2021)
- [Differentially Private Fine-tuning of Language Models](https://mlsanity.com/paper/2110.06500/) (2021)
- [Privacy Auditing with One (1) Training Run](https://mlsanity.com/paper/2305.08846/) (2023)
- [Differentially Private Diffusion Models](https://mlsanity.com/paper/2210.09929/) (2022)
- [Large-Scale Differentially Private BERT](https://mlsanity.com/paper/2108.01624/) (2021)
- [Synthetic Text Generation with Differential Privacy: A Simple and Practical Recipe](https://mlsanity.com/paper/2210.14348/) (2022)
- [Privacy-Preserving In-Context Learning with Differentially Private Few-Shot Generation](https://mlsanity.com/paper/2309.11765/) (2023)
- [Automatic Clipping: Differentially Private Deep Learning Made Easier and Stronger](https://mlsanity.com/paper/2206.07136/) (2022)
- [Optimal Accounting of Differential Privacy via Characteristic Function](https://mlsanity.com/paper/2106.08567/) (2021)
- [Differentially Private Language Models for Secure Data Sharing](https://mlsanity.com/paper/2210.13918/) (2022)
- [DP-Forward: Fine-tuning and Inference on Language Models with Differential Privacy in Forward Pass](https://mlsanity.com/paper/2309.06746/) (2023)
- [Differentially Private Optimization on Large Model at Small Cost](https://mlsanity.com/paper/2210.00038/) (2022)
- [Differentially Private Synthetic Data via Foundation Model APIs 1: Images](https://mlsanity.com/paper/2305.15560/) (2023)
- [Connect the Dots: Tighter Discrete Approximations of Privacy Loss Distributions](https://mlsanity.com/paper/2207.04380/) (2022)
- [TAN Without a Burn: Scaling Laws of DP-SGD](https://mlsanity.com/paper/2210.03403/) (2022)
- [Exploring the Limits of Differentially Private Deep Learning with Group-wise Clipping](https://mlsanity.com/paper/2212.01539/) (2022)
- [Privacy-Preserving In-Context Learning for Large Language Models](https://mlsanity.com/paper/2305.01639/) (2023)
- [Differentially Private Bias-Term Fine-tuning of Foundation Models](https://mlsanity.com/paper/2210.00036/) (2022)
- [Bounding Training Data Reconstruction in DP-SGD](https://mlsanity.com/paper/2302.07225/) (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)
- [Privately Fine-Tuning Large Language Models with Differential Privacy](https://mlsanity.com/paper/2210.15042/) (2022)
- [Learn to Unlearn for Deep Neural Networks: Minimizing Unlearning Interference with Gradient Projection](https://mlsanity.com/paper/2312.04095/) (2023)
- [Normalized/Clipped SGD with Perturbation for Differentially Private Non-Convex Optimization](https://mlsanity.com/paper/2206.13033/) (2022)
- [Privacy-Preserving Instructions for Aligning Large Language Models](https://mlsanity.com/paper/2402.13659/) (2024)
- [Bayesian Estimation of Differential Privacy](https://mlsanity.com/paper/2206.05199/) (2022)
- [Dynamic Differential-Privacy Preserving SGD](https://mlsanity.com/paper/2111.00173/) (2021)
- [SAFE: Machine Unlearning With Shard Graphs](https://mlsanity.com/paper/2304.13169/) (2023)
- [FLUTE: A Scalable, Extensible Framework for High-Performance Federated Learning Simulations](https://mlsanity.com/paper/2203.13789/) (2022)
- [The Role of Adaptive Optimizers for Honest Private Hyperparameter Selection](https://mlsanity.com/paper/2111.04906/) (2021)

## Abstract (arXiv)

We give a fast algorithm to optimally compose privacy guarantees of differentially private (DP) algorithms to arbitrary accuracy. Our method is based on the notion of privacy loss random variables to quantify the privacy loss of DP algorithms. The running time and memory needed for our algorithm to approximate the privacy curve of a DP algorithm composed with itself k times is tildeO(√k). This improves over the best prior method by Koskela et al. (2020) which requires tildeOmega(k1.5) running time. We demonstrate the utility of our algorithm by accurately computing the privacy loss of DP-SGD algorithm of Abadi et al. (2016) and showing that our algorithm speeds up the privacy computations by a few orders of magnitude compared to prior work, while maintaining similar accuracy.