Sampling-Free Privacy Accounting for Matrix Mechanisms under Random Allocation
Not on the map. Why?
Abstract (arXiv)
We study privacy amplification for differentially private model training with matrix factorization under random allocation (also known as the balls-in-bins model). Recent work by Choquette-Choo et al. (2025) proposes a sampling-based Monte Carlo approach to compute amplification parameters in this setting. However, their guarantees either only hold with some high probability or require random abstention by the mechanism. Furthermore, the required number of samples for ensuring (ε,δ)-DP is inversely proportional to δ. In contrast, we develop sampling-free bounds based on R'enyi divergence and conditional composition. The former is facilitated by a dynamic programming formulation to efficiently compute the bounds. The latter complements it by offering stronger privacy guarantees for small ε, where R'enyi divergence bounds inherently lead to an over-approximation. Our framework applies to arbitrary banded and non-banded matrices. Through numerical comparisons, we demonstrate the efficacy of our approach across a broad range of matrix mechanisms used in research and practice.
Key facts. Cited by 3 papers in the map (data through 14 Oct 2026). Builds on 25 of its 36 references that are in the map. First posted on arXiv 29 Jan 2026.
Builds on
25 of 36 references.
References · 25
- 2016Deep Learning with Differential Privacycited by 2,728
- 2016Variational Inference: A Review for Statisticianscited by 1,472
- 2017Renyi Differential Privacycited by 650
- 2018Subsampled R'enyi Differential Privacy and Analytical Moments Accountantcited by 236
- 2018Improving the Gaussian Mechanism for Differential Privacy: Analytical Calibration and Optimal Denoisingcited by 218
- 2023How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacycited by 153
- 2020The Discrete Gaussian for Differential Privacycited by 135
- 2021Optimal Accounting of Differential Privacy via Characteristic Functioncited by 86
- 2022Improved Differential Privacy for SGD via Optimal Private Linear Operators on Adaptive Streamscited by 59
- 2022Connect the Dots: Tighter Discrete Approximations of Privacy Loss Distributionscited by 52
- 2023(Amplified) Banded Matrix Factorization: A unified approach to private trainingcited by 49
- 2022Multi-Epoch Matrix Factorization Mechanisms for Private Machine Learningcited by 48
13 more
- 2020Encode, Shuffle, Analyze Privacy Revisited: Formalizations and Empirical Evaluationcited by 39
- 2024Near Exact Privacy Amplification for Matrix Mechanismscited by 18
- 2023Privacy Amplification for Matrix Mechanismscited by 17
- 2024Efficient and Near-Optimal Noise Generation for Streaming Differential Privacycited by 17
- 2025Privacy amplification by random allocationcited by 15
- 2024Balls-and-Bins Sampling for DP-SGDcited by 14
- 2025Correlated Noise Mechanisms for Differentially Private Learningcited by 14
- 2024Scaling up the Banded Matrix Factorization Mechanism for Differentially Private MLcited by 13
- 2024Avoiding Pitfalls for Privacy Accounting of Subsampled Mechanisms under Compositioncited by 13
- 2024Banded Square Root Matrix Factorization for Differentially Private Model Trainingcited by 12
- 2023A Randomized Approach for Tight Privacy Accountingcited by 11
- 2025Leveraging Randomness in Model and Data Partitioning for Privacy Amplificationcited by 7
- 2025Back to Square Roots: An Optimal Bound on the Matrix Factorization Error for Multi-Epoch Differentially Private SGDcited by 7
Built on by
Citing papers per year: 2026: 3.
3 papers.