# Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergences

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

## Key facts

- Cited by 242 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Jul 2018.

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

- [Adversary Instantiation: Lower Bounds for Differentially Private Machine Learning](https://mlsanity.com/paper/2101.04535/) (2021)
- [How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy](https://mlsanity.com/paper/2303.00654/) (2023)
- [Machine Unlearning via Algorithmic Stability](https://mlsanity.com/paper/2102.13179/) (2021)
- [Large-Scale Differentially Private BERT](https://mlsanity.com/paper/2108.01624/) (2021)
- [Hyperparameter Tuning with Renyi Differential Privacy](https://mlsanity.com/paper/2110.03620/) (2021)
- [Privacy-Preserving In-Context Learning with Differentially Private Few-Shot Generation](https://mlsanity.com/paper/2309.11765/) (2023)
- [Do Not Let Privacy Overbill Utility: Gradient Embedding Perturbation for Private Learning](https://mlsanity.com/paper/2102.12677/) (2021)
- [Optimal Accounting of Differential Privacy via Characteristic Function](https://mlsanity.com/paper/2106.08567/) (2021)
- [DisPFL: Towards Communication-Efficient Personalized Federated Learning via Decentralized Sparse Training](https://mlsanity.com/paper/2206.00187/) (2022)
- [Differential Privacy Dynamics of Langevin Diffusion and Noisy Gradient Descent](https://mlsanity.com/paper/2102.05855/) (2021)
- [Selective Differential Privacy for Language Modeling](https://mlsanity.com/paper/2108.12944/) (2021)
- [Don't Generate Me: Training Differentially Private Generative Models with Sinkhorn Divergence](https://mlsanity.com/paper/2111.01177/) (2021)
- [Privacy-Preserving In-Context Learning for Large Language Models](https://mlsanity.com/paper/2305.01639/) (2023)
- [When Does Differentially Private Learning Not Suffer in High Dimensions?](https://mlsanity.com/paper/2207.00160/) (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)
- [Releasing Graph Neural Networks with Differential Privacy Guarantees](https://mlsanity.com/paper/2109.08907/) (2021)
- [Just Fine-tune Twice: Selective Differential Privacy for Large Language Models](https://mlsanity.com/paper/2204.07667/) (2022)
- [Sparse Random Networks for Communication-Efficient Federated Learning](https://mlsanity.com/paper/2209.15328/) (2022)
- [Conformal Prediction for Federated Uncertainty Quantification Under Label Shift](https://mlsanity.com/paper/2306.05131/) (2023)
- [Fine-Tuning Large Language Models with User-Level Differential Privacy](https://mlsanity.com/paper/2407.07737/) (2024)
- [Muffliato: Peer-to-Peer Privacy Amplification for Decentralized Optimization and Averaging](https://mlsanity.com/paper/2206.05091/) (2022)
- [The Role of Adaptive Optimizers for Honest Private Hyperparameter Selection](https://mlsanity.com/paper/2111.04906/) (2021)
- [Decentralized Federated Learning: A Survey on Security and Privacy](https://mlsanity.com/paper/2401.17319/) (2024)
- [Privacy Amplification for Federated Learning via User Sampling and Wireless Aggregation](https://mlsanity.com/paper/2103.01953/) (2021)
- [Privacy Amplification via Compression: Achieving the Optimal Privacy-Accuracy-Communication Trade-off in Distributed Mean Estimation](https://mlsanity.com/paper/2304.01541/) (2023)
- [Computing Differential Privacy Guarantees for Heterogeneous Compositions Using FFT](https://mlsanity.com/paper/2102.12412/) (2021)
- [Individual Privacy Accounting for Differentially Private Stochastic Gradient Descent](https://mlsanity.com/paper/2206.02617/) (2022)
- [Differentially Private Natural Language Models: Recent Advances and Future Directions](https://mlsanity.com/paper/2301.09112/) (2023)
- [Leave-one-out Distinguishability in Machine Learning](https://mlsanity.com/paper/2309.17310/) (2023)

## Abstract (arXiv)

Differential privacy comes equipped with multiple analytical tools for the design of private data analyses. One important tool is the so-called "privacy amplification by subsampling" principle, which ensures that a differentially private mechanism run on a random subsample of a population provides higher privacy guarantees than when run on the entire population. Several instances of this principle have been studied for different random subsampling methods, each with an ad-hoc analysis. In this paper we present a general method that recovers and improves prior analyses, yields lower bounds and derives new instances of privacy amplification by subsampling. Our method leverages a characterization of differential privacy as a divergence which emerged in the program verification community. Furthermore, it introduces new tools, including advanced joint convexity and privacy profiles, which might be of independent interest.