# Composition of Differential Privacy & Privacy Amplification by Subsampling

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

## Key facts

- Cited by 45 papers in the map (data through 14 Oct 2026).
- Builds on 34 of its 61 references that are in the map.
- First posted on arXiv 2 Oct 2022.

## Builds on (most cited first, 30 of 34)

- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Membership Inference Attacks against Machine Learning Models](https://mlsanity.com/paper/1610.05820/) (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)
- [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)
- [Improving the Gaussian Mechanism for Differential Privacy: Analytical Calibration and Optimal Denoising](https://mlsanity.com/paper/1805.06530/) (2018)
- [R'enyi Differential Privacy of the Sampled Gaussian Mechanism](https://mlsanity.com/paper/1908.10530/) (2019)
- [Numerical Composition of Differential Privacy](https://mlsanity.com/paper/2106.02848/) (2021)
- [Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity](https://mlsanity.com/paper/1811.12469/) (2018)
- [Concentrated Differential Privacy](https://mlsanity.com/paper/1603.01887/) (2016)
- [The Discrete Gaussian for Differential Privacy](https://mlsanity.com/paper/2004.00010/) (2020)
- [Distributed Differential Privacy via Shuffling](https://mlsanity.com/paper/1808.01394/) (2018)
- [Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds](https://mlsanity.com/paper/1405.7085/) (2014)
- [Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling](https://mlsanity.com/paper/2012.12803/) (2020)
- [Optimal Accounting of Differential Privacy via Characteristic Function](https://mlsanity.com/paper/2106.08567/) (2021)
- [A General Approach to Adding Differential Privacy to Iterative Training Procedures](https://mlsanity.com/paper/1812.06210/) (2018)
- [Fingerprinting Codes and the Price of Approximate Differential Privacy](https://mlsanity.com/paper/1311.3158/) (2013)
- [The Privacy Blanket of the Shuffle Model](https://mlsanity.com/paper/1903.02837/) (2019)
- [Individual Privacy Accounting via a Renyi Filter](https://mlsanity.com/paper/2008.11193/) (2020)
- [Between Pure and Approximate Differential Privacy](https://mlsanity.com/paper/1501.06095/) (2015)
- [Prochlo: Strong Privacy for Analytics in the Crowd](https://mlsanity.com/paper/1710.00901/) (2017)
- [Tight Differential Privacy for Discrete-Valued Mechanisms and for the Subsampled Gaussian Mechanism Using FFT](https://mlsanity.com/paper/2006.07134/) (2020)
- [Privacy Odometers and Filters: Pay-as-you-Go Composition](https://mlsanity.com/paper/1605.08294/) (2016)
- [A Primer on Private Statistics](https://mlsanity.com/paper/2005.00010/) (2020)
- [Stronger Privacy Amplification by Shuffling for R'enyi and Approximate Differential Privacy](https://mlsanity.com/paper/2208.04591/) (2022)
- [A Better Bound Gives a Hundred Rounds: Enhanced Privacy Guarantees via f-Divergences](https://mlsanity.com/paper/2001.05990/) (2020)
- [Computing Differential Privacy Guarantees for Heterogeneous Compositions Using FFT](https://mlsanity.com/paper/2102.12412/) (2021)
- [Faster Privacy Accounting via Evolving Discretization](https://mlsanity.com/paper/2207.04381/) (2022)

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

- [Privacy Auditing with One (1) Training Run](https://mlsanity.com/paper/2305.08846/) (2023)
- [DP-Forward: Fine-tuning and Inference on Language Models with Differential Privacy in Forward Pass](https://mlsanity.com/paper/2309.06746/) (2023)
- [(Amplified) Banded Matrix Factorization: A unified approach to private training](https://mlsanity.com/paper/2306.08153/) (2023)
- [One-shot Empirical Privacy Estimation for Federated Learning](https://mlsanity.com/paper/2302.03098/) (2023)
- [Privacy-Preserving Instructions for Aligning Large Language Models](https://mlsanity.com/paper/2402.13659/) (2024)
- [Selective Pre-training for Private Fine-tuning](https://mlsanity.com/paper/2305.13865/) (2023)
- [Differentially Private Next-Token Prediction of Large Language Models](https://mlsanity.com/paper/2403.15638/) (2024)
- [Practical Differentially Private Hyperparameter Tuning with Subsampling](https://mlsanity.com/paper/2301.11989/) (2023)
- [Privacy Amplification for Matrix Mechanisms](https://mlsanity.com/paper/2310.15526/) (2023)
- [Privacy amplification by random allocation](https://mlsanity.com/paper/2502.08202/) (2025)
- [On Differentially Private Federated Linear Contextual Bandits](https://mlsanity.com/paper/2302.13945/) (2023)
- [Differential Privacy Mechanisms in Neural Tangent Kernel Regression](https://mlsanity.com/paper/2407.13621/) (2024)
- [Avoiding Pitfalls for Privacy Accounting of Subsampled Mechanisms under Composition](https://mlsanity.com/paper/2405.20769/) (2024)
- [The Last Iterate Advantage: Empirical Auditing and Principled Heuristic Analysis of Differentially Private SGD](https://mlsanity.com/paper/2410.06186/) (2024)
- [Contrastive Private Data Synthesis via Weighted Multi-PLM Fusion](https://mlsanity.com/paper/2502.00245/) (2025)
- [InvisibleInk: High-Utility and Low-Cost Text Generation with Differential Privacy](https://mlsanity.com/paper/2507.02974/) (2025)
- [Subsampling Suffices for Adaptive Data Analysis](https://mlsanity.com/paper/2302.08661/) (2023)
- [Truthfulness of Calibration Measures](https://mlsanity.com/paper/2407.13979/) (2024)
- [Revisiting Differentially Private Hyper-parameter Tuning](https://mlsanity.com/paper/2402.13087/) (2024)
- [Private Collaborative Edge Inference via Over-the-Air Computation](https://mlsanity.com/paper/2407.21151/) (2024)
- [Private Regression via Data-Dependent Sufficient Statistic Perturbation](https://mlsanity.com/paper/2405.15002/) (2024)
- [Adaptively Private Next-Token Prediction of Large Language Models](https://mlsanity.com/paper/2410.02016/) (2024)
- [Large Language Model Powered Intelligent Urban Agents: Concepts, Capabilities, and Applications](https://mlsanity.com/paper/2507.00914/) (2025)
- [IRG: Modular Synthetic Relational Database Generation with Complex Relational Schemas](https://mlsanity.com/paper/2312.15187/) (2023)
- [Empirical Privacy Variance](https://mlsanity.com/paper/2503.12314/) (2025)
- [Efficient privacy loss accounting for subsampling and random allocation](https://mlsanity.com/paper/2602.17284/) (2026)
- [Differentially Private Synthetic Data Generation for Relational Databases](https://mlsanity.com/paper/2405.18670/) (2024)
- [Learning with Differentially Private (Sliced) Wasserstein Gradients](https://mlsanity.com/paper/2502.01701/) (2025)
- [Adaptive Data Analysis for Growing Data](https://mlsanity.com/paper/2405.13375/) (2024)
- [On Using Secure Aggregation in Differentially Private Federated Learning with Multiple Local Steps](https://mlsanity.com/paper/2407.19286/) (2024)

## Abstract (arXiv)

This chapter is meant to be part of the book "Differential Privacy for Artificial Intelligence Applications." We give an introduction to the most important property of differential privacy -- composition: running multiple independent analyses on the data of a set of people will still be differentially private as long as each of the analyses is private on its own -- as well as the related topic of privacy amplification by subsampling. This chapter introduces the basic concepts and gives proofs of the key results needed to apply these tools in practice.