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

Abstract

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 $\sigma \ge \sqrt{3/\ln M}$, where $\sigma$ 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 $\ge 1-a-\delta$, that is, only $\delta$ below the ideal random guessing diagonal $1-a$. For $\delta =1/100$ and $\sigma =1$, roughly $M\approx 1.14\times 10^6$ rounds and $N\approx 1.14\times 10^7$ training samples suffice to achieve meaningful differential privacy. This is in contrast to recent negative results for the regime $\sigma \le 1/\sqrt{2\ln M}$ for which no significant DP guarantee can exist.