基于随机分配的 DP-SGD 子采样权衡函数：紧致上下界

View PDF HTML (experimental)

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 \geq \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 $\geq 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 \leq 1/\sqrt{2 \ln M}$ for which no significant DP guarantee can exist.

Subjects:	Machine Learning (cs.LG); Cryptography and Security (cs.CR)
Cite as:	arXiv:2605.06259 [cs.LG]
	(or arXiv:2605.06259v3 [cs.LG] for this version)
	https://doi.org/10.48550/arXiv.2605.06259 arXiv-issued DOI via DataCite

Submission history

From: Murat Bilgehan Ertan [view email]
[v1] Thu, 7 May 2026 13:35:43 UTC (79 KB)
[v2] Sun, 24 May 2026 15:38:04 UTC (79 KB)
[v3] Fri, 2 Oct 2026 17:13:16 UTC (104 KB)