Sampling-Free Privacy Accounting for Matrix Mechanisms under Random Allocation
arXiv:2601.21636v1 Announce Type: cross Abstract: 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 $(epsilon,delta)$-DP is inversely proportional to $delta$. In […]