Differentially Private Stochastic Gradient Descent (DP-SGD) is thedominant paradigm for private training, but its fundamental lim-itations under worst-case adversarial privacy definitions remainpoorly understood. We analyze DP-SGD in the $f$-differential privacy framework, which characterizes privacy via hypothesis-testing trade-off curves, and study shuffled sampling over a single epoch with $M$ gradient updates. We derive an explicit suboptimal upperbound on the achievable trade-off curve. This result induces a geometric lower bound on the separation $\kappa$, which is the maximum distance between the mechanism's trade-off curve and the ideal random-guessing line. Because a large separation implies significant adversarial advantage, meaningful privacy requires small $\kappa$. However, we prove that enforcing a small separation imposes a strict lower bound on the Gaussian noise multiplier $\sigma$, which directly limits the achievable utility. In particular, under the standard worst-case adversarial model, shuffled DP-SGD must satisfy $\sigma \geq \frac{1}{\sqrt{2 \ln M}}$ or $\kappa \geq \frac{1}{\sqrt{8}}\left(1 - \frac{1}{\sqrt{4 \pi \ln M}}\right)$, thus cannot simultaneously achieve strong privacy and high utility. Although the noise threshold vanishes asymptotically as $M \to \infty$, the convergence is extremely slow. Even for practically relevant numbers of updates the required noise magnitude remains substantial. We further show that the same limitation extends to Poisson subsampling up to constant factors. Our experiments confirm that the noise levels implied by this bound lead to significant accuracy degradation at realistic training settings, thus showing a bottleneck in DP-SGD under standard worst-case adversarial assumptions.

, , ,
doi.org/10.1145/3830454.3832629
CCS '26: ACM SIGSAC Conference on Computer and Communications Security
creativecommons.org/licenses/by/4.0/
Computer Security

Ertan, B.& van Dijk, M. (2026). Fundamental limitations of favorable privacy–utility guarantees for DP-SGD. Proceedings of the ACM Conference on Computer and Communications Security, 540–554.https://doi.org/10.1145/3830454.3832629