![[2602.17284] Efficient privacy loss accounting for subsampling and random allocation](https://arxiv.org/static/browse/0.3.4/images/arxiv-logo-fb.png){kind=logo}
[2602.17284] Efficient privacy loss accounting for subsampling and random allocation
Summary
This paper presents an efficient method for privacy loss accounting in subsampling and random allocation, demonstrating advantages over traditional Poisson sampling in differential privacy contexts.
Why It Matters
As data privacy becomes increasingly critical in machine learning, this research addresses the limitations of existing privacy accounting methods. By improving the efficiency and accuracy of privacy loss calculations, it enhances the utility of differentially private algorithms, which is essential for maintaining user trust and compliance with regulations.
Key Takeaways
- Introduces a new method for privacy loss accounting in subsampling.
- Shows that random allocation can outperform Poisson sampling in differential privacy settings.
- Develops tools for accurate privacy loss accounting, reducing manual analysis requirements.
- Demonstrates improved privacy-utility trade-offs for training via DP-SGD.
- Addresses significant shortcomings in current theoretical analyses of privacy parameters.
Computer Science > Machine Learning arXiv:2602.17284 (cs) [Submitted on 19 Feb 2026] Title:Efficient privacy loss accounting for subsampling and random allocation Authors:Vitaly Feldman, Moshe Shenfeld View a PDF of the paper titled Efficient privacy loss accounting for subsampling and random allocation, by Vitaly Feldman and Moshe Shenfeld View PDF HTML (experimental) Abstract: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. 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 Renyi 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 algorit...
