Efficient privacy loss accounting for subsampling and 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 and Shenfeld, 2025, Dong et al., 2025] lead to bounds that are close to those of Poisson sampling, yet still have two significant shortcomings. First, in many practical settings, the resulting privacy parameters are not tight due to the approximation steps in the analysis. Second, the computed parameters are either the hockey stick or Rényi divergence, both of which introduce overheads when used in privacy loss accounting. 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 the privacy-utility trade-off for random allocation is at least as good as that of Poisson subsampling. In particular, random allocation is better suited for training via DP-SGD. To support these computations, our work develops new tools for general privacy loss accounting based on a notion of PLD realization. This notion allows us to extend accurate privacy loss accounting to subsampling which previously required manual noise-mechanism-specific analysis.

Modern AI systems are often trained on sensitive records, such as people’s text, images, or medical data. To reduce privacy risk, researchers use differential privacy, which limits how much the trained model can reveal about any one record by adding carefully calibrated random noise. Poisson sampling, a standard way to analyze this protection, assumes that each training batch is formed by flipping an independent coin for every record. That assumption is mathematically convenient, but it is not how many training systems form batches, and it can make training less efficient. This paper analyzes a more practical batching method, called random allocation, where each record is used in a fixed number of randomly chosen training steps. Earlier work suggested that this method is more practical and leads to more accurate training, but did not provide a way to calculate its privacy guarantee precisely. We develop such a calculation method. It enables accurate tracking of privacy guarantees for random allocation and improves on previous algorithms.