cs.LGJan 29, 2026

Sampling-Free Privacy Accounting for Matrix Mechanisms under Random Allocation

Authors: Jan Schuchardt, Nikita Kalinin

Organizations: Machine Learning Research, Morgan Stanley · Institute of Science and Technology Austria

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 (ε,δ)(ε,δ)-DP is inversely proportional to δδ. In contrast, we develop sampling-free bounds based on Rényi 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ényi 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.

Figures & tables

Appendix figures & tables16 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Efficient privacy loss accounting for subsampling and random allocation

    Feb 19, 2026Vitaly Feldman, Moshe ShenfeldPrivacy AccountingDifferential Privacy