# The Composition Theorem for Differential Privacy

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

## Key facts

- Cited by 297 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Nov 2013.

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

- [Membership Inference Attacks From First Principles](https://mlsanity.com/paper/2112.03570/) (2021)
- [Enhanced Membership Inference Attacks against Machine Learning Models](https://mlsanity.com/paper/2111.09679/) (2021)
- [Adversary Instantiation: Lower Bounds for Differentially Private Machine Learning](https://mlsanity.com/paper/2101.04535/) (2021)
- [Numerical Composition of Differential Privacy](https://mlsanity.com/paper/2106.02848/) (2021)
- [How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy](https://mlsanity.com/paper/2303.00654/) (2023)
- [Reconstructing Training Data with Informed Adversaries](https://mlsanity.com/paper/2201.04845/) (2022)
- [Invisible Image Watermarks Are Provably Removable Using Generative AI](https://mlsanity.com/paper/2306.01953/) (2023)
- [Privacy Auditing with One (1) Training Run](https://mlsanity.com/paper/2305.08846/) (2023)
- [Privacy for Free: How does Dataset Condensation Help Privacy?](https://mlsanity.com/paper/2206.00240/) (2022)
- [Measuring Forgetting of Memorized Training Examples](https://mlsanity.com/paper/2207.00099/) (2022)
- [Optimal Accounting of Differential Privacy via Characteristic Function](https://mlsanity.com/paper/2106.08567/) (2021)
- [Differentially Private Federated Learning on Heterogeneous Data](https://mlsanity.com/paper/2111.09278/) (2021)
- [The Skellam Mechanism for Differentially Private Federated Learning](https://mlsanity.com/paper/2110.04995/) (2021)
- [Differentially Private Language Models for Secure Data Sharing](https://mlsanity.com/paper/2210.13918/) (2022)
- [Robust and Differentially Private Mean Estimation](https://mlsanity.com/paper/2102.09159/) (2021)
- [FedDM: Iterative Distribution Matching for Communication-Efficient Federated Learning](https://mlsanity.com/paper/2207.09653/) (2022)
- [TAPAS: a Toolbox for Adversarial Privacy Auditing of Synthetic Data](https://mlsanity.com/paper/2211.06550/) (2022)
- [FedFed: Feature Distillation against Data Heterogeneity in Federated Learning](https://mlsanity.com/paper/2310.05077/) (2023)
- [Connect the Dots: Tighter Discrete Approximations of Privacy Loss Distributions](https://mlsanity.com/paper/2207.04380/) (2022)
- [Are we making progress in unlearning? Findings from the first NeurIPS unlearning competition](https://mlsanity.com/paper/2406.09073/) (2024)
- [Membership Inference Attacks Cannot Prove that a Model Was Trained On Your Data](https://mlsanity.com/paper/2409.19798/) (2024)
- [Langevin Unlearning: A New Perspective of Noisy Gradient Descent for Machine Unlearning](https://mlsanity.com/paper/2401.10371/) (2024)
- [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)
- [Debugging Differential Privacy: A Case Study for Privacy Auditing](https://mlsanity.com/paper/2202.12219/) (2022)
- [Federated Learning with Local Differential Privacy: Trade-offs between Privacy, Utility, and Communication](https://mlsanity.com/paper/2102.04737/) (2021)
- [Privately Fine-Tuning Large Language Models with Differential Privacy](https://mlsanity.com/paper/2210.15042/) (2022)
- [Privacy-Preserving Retrieval-Augmented Generation with Differential Privacy](https://mlsanity.com/paper/2412.04697/) (2024)
- [RelaxLoss: Defending Membership Inference Attacks without Losing Utility](https://mlsanity.com/paper/2207.05801/) (2022)
- [Why Is Public Pretraining Necessary for Private Model Training?](https://mlsanity.com/paper/2302.09483/) (2023)

## Abstract (arXiv)

Sequential querying of differentially private mechanisms degrades the overall privacy level. In this paper, we answer the fundamental question of characterizing the level of overall privacy degradation as a function of the number of queries and the privacy levels maintained by each privatization mechanism. Our solution is complete: we prove an upper bound on the overall privacy level and construct a sequence of privatization mechanisms that achieves this bound. The key innovation is the introduction of an operational interpretation of differential privacy (involving hypothesis testing) and the use of new data processing inequalities. Our result improves over the state-of-the-art, and has immediate applications in several problems studied in the literature including differentially private multi-party computation.