# Privacy Amplification for Matrix Mechanisms

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 29 references that are in the map.
- First posted on arXiv 24 Oct 2023.

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

- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [R'enyi Differential Privacy of the Sampled Gaussian Mechanism](https://mlsanity.com/paper/1908.10530/) (2019)
- [Practical and Private (Deep) Learning without Sampling or Shuffling](https://mlsanity.com/paper/2103.00039/) (2021)
- [Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity](https://mlsanity.com/paper/1811.12469/) (2018)
- [How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy](https://mlsanity.com/paper/2303.00654/) (2023)
- [Privacy Amplification by Iteration](https://mlsanity.com/paper/1808.06651/) (2018)
- [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)
- [Improved Differential Privacy for SGD via Optimal Private Linear Operators on Adaptive Streams](https://mlsanity.com/paper/2202.08312/) (2022)
- [(Amplified) Banded Matrix Factorization: A unified approach to private training](https://mlsanity.com/paper/2306.08153/) (2023)
- [Multi-Epoch Matrix Factorization Mechanisms for Private Machine Learning](https://mlsanity.com/paper/2211.06530/) (2022)
- [Composition of Differential Privacy & Privacy Amplification by Subsampling](https://mlsanity.com/paper/2210.00597/) (2022)
- [Privacy Amplification via Random Check-Ins](https://mlsanity.com/paper/2007.06605/) (2020)
- [Constant matters: Fine-grained Complexity of Differentially Private Continual Observation](https://mlsanity.com/paper/2202.11205/) (2022)
- [A Unifying Framework for Differentially Private Sums under Continual Observation](https://mlsanity.com/paper/2307.08970/) (2023)
- [HDMM: Optimizing error of high-dimensional statistical queries under differential privacy](https://mlsanity.com/paper/2106.12118/) (2021)

## Built on by (most cited first, 17 of 17)

- [Teach LLMs to Phish: Stealing Private Information from Language Models](https://mlsanity.com/paper/2403.00871/) (2024)
- [Fine-Tuning Large Language Models with User-Level Differential Privacy](https://mlsanity.com/paper/2407.07737/) (2024)
- [Privacy amplification by random allocation](https://mlsanity.com/paper/2502.08202/) (2025)
- [Banded Square Root Matrix Factorization for Differentially Private Model Training](https://mlsanity.com/paper/2405.13763/) (2024)
- [Preserving Node-level Privacy in Graph Neural Networks](https://mlsanity.com/paper/2311.06888/) (2023)
- [Streaming Private Continual Counting via Binning](https://mlsanity.com/paper/2412.07093/) (2024)
- [Back to Square Roots: An Optimal Bound on the Matrix Factorization Error for Multi-Epoch Differentially Private SGD](https://mlsanity.com/paper/2505.12128/) (2025)
- [Improved Communication-Privacy Trade-offs in L2 Mean Estimation under Streaming Differential Privacy](https://mlsanity.com/paper/2405.02341/) (2024)
- [An Inversion Theorem for Buffered Linear Toeplitz (BLT) Matrices and Applications to Streaming Differential Privacy](https://mlsanity.com/paper/2504.21413/) (2025)
- [Sampling-Free Privacy Accounting for Matrix Mechanisms under Random Allocation](https://mlsanity.com/paper/2601.21636/) (2026)
- [DP-λCGD: Efficient Noise Correlation for Differentially Private Model Training](https://mlsanity.com/paper/2601.22334/) (2026)
- [Less Random, More Private: What is the Optimal Subsampling Scheme for DP-SGD?](https://mlsanity.com/paper/2605.07072/) (2026)
- [Federated Learning with Enhanced Privacy via Model Splitting and Random Client Participation](https://mlsanity.com/paper/2509.25906/) (2025)
- [Secret-Protected Evolution for Differentially Private Synthetic Text Generation](https://mlsanity.com/paper/2510.10990/) (2025)
- [Prediction with Expert Advice under Local Differential Privacy](https://mlsanity.com/paper/2512.06971/) (2025)
- [Beyond Square Roots: A Memory-Efficient Explicit Factorization for Multi-Epoch Private Learning](https://mlsanity.com/paper/2605.18379/) (2026)
- [Provable Robustness against Backdoor Attacks via the Primal-Dual Perspective on Differential Privacy](https://mlsanity.com/paper/2605.21780/) (2026)

## Abstract (arXiv)

Privacy amplification exploits randomness in data selection to provide tighter differential privacy (DP) guarantees. This analysis is key to DP-SGD's success in machine learning, but, is not readily applicable to the newer state-of-the-art algorithms. This is because these algorithms, known as DP-FTRL, use the matrix mechanism to add correlated noise instead of independent noise as in DP-SGD. In this paper, we propose "MMCC", the first algorithm to analyze privacy amplification via sampling for any generic matrix mechanism. MMCC is nearly tight in that it approaches a lower bound as ε→0. To analyze correlated outputs in MMCC, we prove that they can be analyzed as if they were independent, by conditioning them on prior outputs. Our "conditional composition theorem" has broad utility: we use it to show that the noise added to binary-tree-DP-FTRL can asymptotically match the noise added to DP-SGD with amplification. Our amplification algorithm also has practical empirical utility: we show it leads to significant improvement in the privacy-utility trade-offs for DP-FTRL algorithms on standard benchmarks.