# Trade-off Functions for DP-SGD with Subsampling based on Random Allocation: Tight Upper and Lower Bounds

arXiv: https://arxiv.org/abs/2605.06259 · HTML: https://mlsanity.com/paper/2605.06259/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 36 references that are in the map.
- First posted on arXiv 7 May 2026.

## Builds on (most cited first, 26 of 26)

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds](https://mlsanity.com/paper/1605.02065/) (2016)
- [The Composition Theorem for Differential Privacy](https://mlsanity.com/paper/1311.0776/) (2013)
- [Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergences](https://mlsanity.com/paper/1807.01647/) (2018)
- [Subsampled R'enyi Differential Privacy and Analytical Moments Accountant](https://mlsanity.com/paper/1808.00087/) (2018)
- [R'enyi Differential Privacy of the Sampled Gaussian Mechanism](https://mlsanity.com/paper/1908.10530/) (2019)
- [Numerical Composition of Differential Privacy](https://mlsanity.com/paper/2106.02848/) (2021)
- [Deep Learning with Gaussian Differential Privacy](https://mlsanity.com/paper/1911.11607/) (2019)
- [Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling](https://mlsanity.com/paper/2012.12803/) (2020)
- [Connect the Dots: Tighter Discrete Approximations of Privacy Loss Distributions](https://mlsanity.com/paper/2207.04380/) (2022)
- [Privacy Amplification via Random Check-Ins](https://mlsanity.com/paper/2007.06605/) (2020)
- [How Private are DP-SGD Implementations?](https://mlsanity.com/paper/2403.17673/) (2024)
- [Near Exact Privacy Amplification for Matrix Mechanisms](https://mlsanity.com/paper/2410.06266/) (2024)
- [Scalable DP-SGD: Shuffling vs. Poisson Subsampling](https://mlsanity.com/paper/2411.04205/) (2024)
- [Privacy amplification by random allocation](https://mlsanity.com/paper/2502.08202/) (2025)
- [Edgeworth Accountant: An Analytical Approach to Differential Privacy Composition](https://mlsanity.com/paper/2206.04236/) (2022)
- [Balls-and-Bins Sampling for DP-SGD](https://mlsanity.com/paper/2412.16802/) (2024)
- [Sharp Composition Bounds for Gaussian Differential Privacy via Edgeworth Expansion](https://mlsanity.com/paper/2003.04493/) (2020)
- [Differentially Private Stochastic Gradient Descent with Fixed-Size Minibatches: Tighter RDP Guarantees with or without Replacement](https://mlsanity.com/paper/2408.10456/) (2024)
- [Leveraging Randomness in Model and Data Partitioning for Privacy Amplification](https://mlsanity.com/paper/2503.03043/) (2025)
- [Gaussian DP for Reporting Differential Privacy Guarantees in Machine Learning](https://mlsanity.com/paper/2503.10945/) (2025)
- [Shuffle Gaussian Mechanism for Differential Privacy](https://mlsanity.com/paper/2206.09569/) (2022)
- [Fundamental Limitations of Favorable Privacy-Utility Guarantees for DP-SGD](https://mlsanity.com/paper/2601.10237/) (2026)
- [Efficient privacy loss accounting for subsampling and random allocation](https://mlsanity.com/paper/2602.17284/) (2026)
- [Proactive DP: A Multple Target Optimization Framework for DP-SGD](https://mlsanity.com/paper/2102.09030/) (2021)

## Built on by (most cited first, 1 of 1)

- [Closed-Form Noise Calibration Against Membership Inference for Random-Allocation DP-SGD](https://mlsanity.com/paper/2610.09651/) (2026)

## Abstract (arXiv)

Within the f-DP framework, we derive a tight analysis of the trade-off function for Differentially Private Stochastic Gradient Descent (DP-SGD) with subsampling based on random allocation in which each sample is independently assigned to exactly one of M minibatches per epoch, each minibatch corresponding to one of the M SGD rounds within a single epoch. Our analysis holds under an explicit validity condition, whose hypotheses together force σ ≥ √3/ln M, where σ is the DP noise multiplier. Unlike f-DP analyses for Poisson subsampling, which yield non-closed implicit formulas that can be machine computed but are non-transparent, random allocation admits a tight analysis yielding transparent and interpretable closed-form bounds. For a single epoch, our concrete bounds, derived via the Berry-Esseen theorem, are tight up to constant factors. We demonstrate worked parameter settings for a single epoch (E=1) with a corresponding trade-off function ≥ 1-a-δ, that is, only δ below the ideal random guessing diagonal 1-a. For δ = 1/100 and σ = 1, roughly M ≈ 1.14× 106 rounds and N ≈ 1.14× 107 training samples suffice to achieve meaningful differential privacy. This is in contrast to recent negative results for the regime σ ≤ 1/√2 ln M for which no significant DP guarantee can exist.