# Near Exact Privacy Amplification for Matrix Mechanisms

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Oct 2024.

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

- [Privacy amplification by random allocation](https://mlsanity.com/paper/2502.08202/) (2025)
- [Balls-and-Bins Sampling for DP-SGD](https://mlsanity.com/paper/2412.16802/) (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)
- [To Shuffle or not to Shuffle: Auditing DP-SGD with Shuffling](https://mlsanity.com/paper/2411.10614/) (2024)
- [The Hitchhiker's Guide to Efficient, End-to-End, and Tight DP Auditing](https://mlsanity.com/paper/2506.16666/) (2025)
- [Empirical Privacy Variance](https://mlsanity.com/paper/2503.12314/) (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)
- [Efficient privacy loss accounting for subsampling and random allocation](https://mlsanity.com/paper/2602.17284/) (2026)
- [JAX-Privacy: A library for differentially private machine learning](https://mlsanity.com/paper/2602.17861/) (2026)
- [Learning Rate Scheduling with Matrix Factorization for Private Training](https://mlsanity.com/paper/2511.17994/) (2025)
- [High-Probability Bounds for SGD under the Polyak-Lojasiewicz Condition with Markovian Noise](https://mlsanity.com/paper/2603.14514/) (2026)
- [Cocoon: A System Architecture for Differentially Private Training with Correlated Noises](https://mlsanity.com/paper/2510.07304/) (2025)
- [Trade-off Functions for DP-SGD with Subsampling based on Random Allocation: Tight Upper and Lower Bounds](https://mlsanity.com/paper/2605.06259/) (2026)
- [Optimization Risk Bounds for Kolmogorov-Arnold Networks Trained by DP-SGD with Correlated Noise](https://mlsanity.com/paper/2605.12648/) (2026)
- [Beyond Square Roots: A Memory-Efficient Explicit Factorization for Multi-Epoch Private Learning](https://mlsanity.com/paper/2605.18379/) (2026)
- [When Do Fewer Coordinates Suffice in DP-SGD?](https://mlsanity.com/paper/2606.04375/) (2026)
- [Revisiting Privacy Amplification by Subsampling in Selective Release DPSGD](https://mlsanity.com/paper/2606.04384/) (2026)

## Abstract (arXiv)

We study the problem of computing the privacy parameters for DP machine learning when using privacy amplification via random batching and noise correlated across rounds via a correlation matrix C (i.e., the matrix mechanism). Past work on this problem either only applied to banded C, or gave loose privacy parameters. In this work, we give a framework for computing near-exact privacy parameters for any lower-triangular, non-negative C. Our framework allows us to optimize the correlation matrix C while accounting for amplification, whereas past work could not. Empirically, we show this lets us achieve smaller RMSE on prefix sums than the previous state-of-the-art (SOTA). We also show that we can improve on the SOTA performance on deep learning tasks. Our two main technical tools are (i) using Monte Carlo accounting to bypass composition, which was the main technical challenge for past work, and (ii) a "balls-in-bins" batching scheme that enables easy privacy analysis and is closer to practical random batching than Poisson sampling.