Privacy amplification by random allocation

We consider the privacy amplification properties of a sampling scheme in which a user’s data is used in k steps chosen randomly and uniformly from a sequence (or set) of t steps. This sampling scheme has been recently applied in the context of differentially private optimization (Chua et al., 2024a; Choquette-Choo et al., 2025) and communication-efficient high-dimensional private aggregation (Asi et al., 2025), where it was shown to have utility advantages over the standard Poisson sampling. Theoretical analyses of this sampling scheme (Feldman & Shenfeld, 2025; Dong et al.,2025) lead to bounds that are close to those of Poisson sampling, yet still have two significant shortcomings. In this work, we demonstrate that the privacy loss distribution (PLD) of random allocation applied to any differentially private algorithm can be computed efficiently. When applied to the Gaussian mechanism, our results demonstrate that random allocation can be used in place of Poisson subsampling with no degradation in resulting privacy guarantees. In addition, our work develops tools for privacy accounting based on approximate stochastic domination of the privacy loss random variable. In particular, we demonstrate how to correctly perform subsampling directly on PLD bounds, enabling accurate privacy accounting for more general algorithms.