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

arXiv:2605.06259v2 Announce Type: replace Abstract: We derive a tight analysis of the trade-off function for Differentially Private Stochastic Gradient Descent (DP-SGD) with subsampling based on random shuffling within the f-DP framework. Our analysis covers the regime sigma geq sqrt{3/ln M}, where sigma is the noise multiplier and M is the number of rounds within a single epoch. Unlike f-DP analyses for Poisson subsampling, which yield non-closed implicit formulas that can be machine computed but are non-transparent, random shuffling admits a tight analysis yielding transparent and interpretable closed-form bounds. Our concrete bounds, derived via the Berry-Esseen theorem, are tight up to constant factors within the proof framework. We demonstrate worked parameter settings for a single epoch (E=1) with a corresponding trade-off function geq 1-a-elta, that is, only elta below the ideal random guessing diagonal 1-a: For elta = 1/100 and sigma = 1, roughly M approx 1.14imes 10^6 rounds and N approx 1.14imes 10^7 training samples suffice to achieve meaningful differential privacy. This is in contrast to recent negative results for the regime sigma leq 1/sqrt{2 ln M}. Our concrete bounds can be composed over multiple epochs leading to elta having a linear in E dependency, which restricts E=O(sqrt{M}). To go beyond Berry--Esseen, we introduce a new proof technique based on a generalization of the law of large numbers that yields an asymptotic random guessing diagonal-limit result: if E=c_M^2M with c_Mo 0, then the E-fold composed trade-off function satisfies f^{otimes E}(a)o 1-a uniformly in ain[0,1] with elta having only an O(sqrt{E}) dependency. We compare this asymptotic regime with the corresponding Poisson subsampling asymptotic, and highlight the characterization of explicit convergence rates as an open question.

Source: arXiv cs.LG | 2026-05-26