# Fundamental Limitations of Favorable Privacy-Utility Guarantees for DP-SGD

arXiv: https://arxiv.org/abs/2601.10237 · HTML: https://mlsanity.com/paper/2601.10237/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 52 of its 74 references that are in the map.
- First posted on arXiv 15 Jan 2026.

## Builds on (most cited first, 30 of 52)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [LAION-5B: An open large-scale dataset for training next generation image-text models](https://mlsanity.com/paper/2210.08402/) (2022)
- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Character-level Convolutional Networks for Text Classification](https://mlsanity.com/paper/1509.01626/) (2015)
- [Root Mean Square Layer Normalization](https://mlsanity.com/paper/1910.07467/) (2019)
- [ImageNet-21K Pretraining for the Masses](https://mlsanity.com/paper/2104.10972/) (2021)
- [Datasets: A Community Library for Natural Language Processing](https://mlsanity.com/paper/2109.02846/) (2021)
- [Opacus: User-Friendly Differential Privacy Library in PyTorch](https://mlsanity.com/paper/2109.12298/) (2021)
- [Differential Privacy Has Disparate Impact on Model Accuracy](https://mlsanity.com/paper/1905.12101/) (2019)
- [The Composition Theorem for Differential Privacy](https://mlsanity.com/paper/1311.0776/) (2013)
- [RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response](https://mlsanity.com/paper/1407.6981/) (2014)
- [Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergences](https://mlsanity.com/paper/1807.01647/) (2018)
- [Unlocking High-Accuracy Differentially Private Image Classification through Scale](https://mlsanity.com/paper/2204.13650/) (2022)
- [R'enyi Differential Privacy of the Sampled Gaussian Mechanism](https://mlsanity.com/paper/1908.10530/) (2019)
- [Practical and Private (Deep) Learning without Sampling or Shuffling](https://mlsanity.com/paper/2103.00039/) (2021)
- [Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity](https://mlsanity.com/paper/1811.12469/) (2018)
- [How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy](https://mlsanity.com/paper/2303.00654/) (2023)
- [Collecting Telemetry Data Privately](https://mlsanity.com/paper/1712.01524/) (2017)
- [Differentially Private Diffusion Models](https://mlsanity.com/paper/2210.09929/) (2022)
- [Large-Scale Differentially Private BERT](https://mlsanity.com/paper/2108.01624/) (2021)
- [GS-WGAN: A Gradient-Sanitized Approach for Learning Differentially Private Generators](https://mlsanity.com/paper/2006.08265/) (2020)
- [Deep Learning with Gaussian Differential Privacy](https://mlsanity.com/paper/1911.11607/) (2019)
- [Synthetic Text Generation with Differential Privacy: A Simple and Practical Recipe](https://mlsanity.com/paper/2210.14348/) (2022)
- [Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling](https://mlsanity.com/paper/2012.12803/) (2020)
- [Toward Training at ImageNet Scale with Differential Privacy](https://mlsanity.com/paper/2201.12328/) (2022)
- [Optimal Accounting of Differential Privacy via Characteristic Function](https://mlsanity.com/paper/2106.08567/) (2021)
- [Why Random Reshuffling Beats Stochastic Gradient Descent](https://mlsanity.com/paper/1510.08560/) (2015)

## Built on by (most cited first, 4 of 4)

- [Private Prediction via PAC Privacy](https://mlsanity.com/paper/2601.14033/) (2026)
- [Trade-off Functions for DP-SGD with Subsampling based on Random Allocation: Tight Upper and Lower Bounds](https://mlsanity.com/paper/2605.06259/) (2026)
- [PACZero: PAC-Private Fine-Tuning of Language Models via Sign Quantization](https://mlsanity.com/paper/2605.06505/) (2026)
- [Closed-Form Noise Calibration Against Membership Inference for Random-Allocation DP-SGD](https://mlsanity.com/paper/2610.09651/) (2026)

## Abstract (arXiv)

Differentially Private Stochastic Gradient Descent (DP-SGD) is the dominant paradigm for private training, but its fundamental limitations under worst-case adversarial privacy definitions remain poorly 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 upper bound 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 σ, which directly limits the achievable utility. In particular, under the standard worst-case adversarial model, shuffled DP-SGD must satisfy σ ≥ frac1√2ln M quadorquad kappa ≥ frac1√8!left(1-frac1√4πln Mright), thus cannot simultaneously achieve strong privacy and high utility. Although the noise threshold vanishes asymptotically as M → ∞, 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.