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

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.