PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Murat Bilgehan Ertan, Marten van Dijk

arXiv:2601.10237v3cs.LGcs.CR

TL;DR

DP-SGD’s privacy–utility limits under worst-case adversarial definitions, especially with practical shuffled sampling, remain insufficiently understood. Using f-DP analysis of one-epoch shuffled and Poisson-subsampled training, the paper derives explicit lower bounds showing that noise and worst-case distinguishability cannot both be made small, with substantial accuracy degradation at practical scales.

  • Problem

    The privacy–utility tension and analytical mismatch between practical shuffled batching and Poisson-based guarantees remain unresolved for DP-SGD.

  • Method

    The paper analyzes one-epoch shuffled and Poisson-subsampled DP-SGD in the f-DP hypothesis-testing framework.

  • Results

    The noise multiplier and worst-case distinguishability cannot be simultaneously driven below explicit lower bounds, and the implied noise causes substantial utility degradation at practical scales.

  • Takeaways & Limitations

    The findings define a boundary on DP-SGD privacy–utility trade-offs under strong worst-case definitions rather than private learning generally.

  • Takeaways & Limitations

    The shuffled-DP-SGD lower bound assumes one-epoch random shuffling, attained worst-case sensitivity, and M dividing N.

Abstract

from arXiv · show

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 $κ$, 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 $κ$. 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 $$σ\ge \frac{1}{\sqrt{2\ln M}} \quad\text{or}\quad κ\ge\ \frac{1}{\sqrt{8}}\!\left(1-\frac{1}{\sqrt{4π\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.

1 Introduction

The introduction frames shuffled DP-SGD as a practical but theoretically mismatched setting where rigorous worst-case privacy requires noise that degrades utility. Using f-DP, the paper derives explicit limitations on the noise multiplier σ and trade-off separation κ, extending them to Poisson subsampling and validating their accuracy impact empirically.

  • Motivation: Shuffled batching is common in practice but violates the independence assumptions underlying much Poisson-subsampling privacy analysis.Practical implementations often report privacy parameters as if Poisson subsampling were used.
  • Framework: The analysis studies single-epoch shuffled DP-SGD under a standard worst-case adversary using f-DP trade-off curves.The f-DP framework characterizes the strongest adversary’s false-positive and false-negative trade-off against the random-guessing baseline.
  • Main limitation: The paper derives an explicit trade-off-curve upper bound that yields a geometric lower bound on separation κ, so σ and κ cannot both be small.Small κ corresponds to stronger privacy, while larger σ harms accuracy.
  • Extensions: A mixture argument shows that Poisson subsampling inherits the same privacy–utility limitation up to a constant factor.The result provides a unified worst-case characterization of shuffled and Poisson sampling schemes.
  • Empirical validation: Experiments show that noise levels implied by the bounds cause substantial accuracy degradation across models, datasets, and batch sizes.The paper also translates the f-DP results into lower bounds for classical (ε, δ)-DP.

2 Related Work

Prior work developed tighter privacy accounting for DP-SGD and studied shuffled sampling, while this paper analyzes shuffled DP-SGD directly in the f-DP framework. Related research also highlights weaker shuffled privacy than Poisson subsampling, practical adoption of shuffling, and utility degradation from Gaussian noise.

  • RDP and PLD composition frameworks refine DP-SGD privacy accounting by tracking cumulative privacy loss across training iterations.
  • The relationship between f-DP trade-off curves and (ε, δ)-DP guarantees enables techniques from classical DP to transfer into f-DP analysis.
  • Privacy amplification by shuffling strengthens locally randomized mechanisms, but this result does not directly apply to centralized DP-SGD.
  • Chua et al. provide shuffled DP-SGD privacy-loss lower bounds, while this work offers a closed-form trade-off upper bound with broader f-DP applicability and Poisson transfer.Their analysis requires numerical evaluation and inversion for each parameter setting, whereas the paper uses a max-statistic construction.
  • Random shuffling remains standard in deep learning despite weaker provable privacy than Poisson subsampling, while allocation-style samplers seek Poisson-like accounting with shuffling’s implementability.Poisson subsampling can be inefficient for large datasets that do not fit in memory.
  • Prior work consistently reports DP-SGD utility degradation under meaningful privacy guarantees, with injected Gaussian noise controlled by σ identified as a dominant source.

3 Preliminaries

This section defines DP-SGD’s clipped-gradient and Gaussian-noise update, introduces its sampling mechanisms, and specifies the f-DP privacy framework and adjacency assumptions used in the analysis. The core results analyze one shuffled epoch under zero-out adjacency, with substitution adjacency requiring twice the noise scale.

  • DP-SGD Mechanism: DP-SGD clips each per-sample gradient to bound sensitivity and adds Gaussian noise scaled by the clipping threshold before averaging and updating model parameters.The noise standard deviation is Cσ, and σ = 0 with C = ∞ recovers standard mini-batch SGD.
  • Scope of Analysis: The analysis studies one epoch of DP-SGD under a standard worst-case adversarial model, with shuffled index sets S1, . . . , SM each used exactly once.Multiple epochs require additional composition and are outside the core lower bound.
  • Sampling Mechanisms: Sampling affects privacy amplification because records influence only the updates in which they are sampled; the canonical mechanisms are Poisson subsampling and random shuffling.The analysis focuses on random shuffling, while the stated limitations extend to Poisson subsampling up to constant factors.
  • Privacy Framework: f-DP represents privacy through the trade-off function f(α), capturing the Type I–Type II error trade-off for distinguishing neighboring datasets.The framework provides a geometric privacy representation, supports composition, and matches the Gaussian mechanism used in DP-SGD.
  • Adjacency Models: Substitution adjacency has clipped-gradient-sum sensitivity at most 2C, imposing a factor-of-two increase in the required Gaussian noise scale relative to zero-out analysis.Poisson subsampling is paired with add/remove adjacency because each record is independently included with probability q.
  • Adjacency Models: Zero-out adjacency is used for the tightest possible worst-case guarantees, comparing datasets that differ at one position between a genuine record and the ghost record ⊥.The mechanism is unchanged; only the neighboring datasets used for analysis differ.

4 Adversarial Model

The section distinguishes a practical eavesdropper who sees only noisy aggregated updates from a worst-case adversary granted auxiliary information under zero-out adjacency. This information lets the worst-case adversary isolate the differing record’s noisy contribution, reducing privacy analysis to reconstructed variables.

  • The practical adversary observes only noisy averaged updates transmitted to the server, without access to individual gradients or intermediate computations.
  • The worst-case analysis grants the adversary additional knowledge, including batch sizes and partial sums of clipped gradients excluding the potentially differing record.The neighboring datasets share N−1 records and differ in the final record, which is replaced by a ghost record under zero-out adjacency.
  • With the public update and auxiliary information, the adversary can deterministically recover the noisy contribution of the differing record.This is formalized as Proposition 4.3 under the stated assumptions.
  • Under the ghost-record dataset, the reconstructed contribution is pure noise, whereas under the valid-record dataset it includes the differing record’s contribution.
  • Because the reconstructed variables expose an explicit distinguishing test, analyzing them suffices for valid lower bounds on the protocol’s privacy leakage.Other functions of the adversary’s view may contain additional information, so restricting attention to these variables can only understate the adversary.

5 Hypothesis Testing and f-DP Characterization

This section formulates worst-case privacy leakage for shuffled DP-SGD as a Gaussian hypothesis test and connects its optimal error trade-off to f-DP. It then introduces geometric separation from random guessing, which supports the later limitation argument through explicit suboptimal trade-off bounds.

  • Hypothesis-testing formulation: Projecting onto the signal direction reduces the adversary’s observation to the one-dimensional Gaussian test N(0, 1) versus N(σ^-1, 1).Rotational symmetry makes the signal direction sufficient for distinguishing inclusion from replacement by a ghost record.
  • Hypothesis-testing formulation: Under H1, the differing record appears in exactly one of M batches at a uniformly random index, whereas under H0 every batch contains only noise.The analysis assumes M divides N, so shuffling discards no records.
  • f-DP characterization: The Neyman–Pearson framework identifies likelihood-ratio tests as uniformly most powerful and summarizes the optimal Type I–Type II trade-off through an f-DP trade-off function.The subsequent bound uses a suboptimal test rather than the exact rejection rule.
  • Geometric separation: Pointwise separation measures the Euclidean distance between a trade-off curve and the random-guessing line β = 1 −α, while global separation is its maximum over the curve.For symmetric and convex trade-off functions, the maximum occurs at the unique fixed point satisfying f(â) = â.
  • Geometric separation: The separation framework allows any explicit pointwise upper bound on the true trade-off curve to yield a lower bound on global separation.Separation is a uniform geometric intermediate for f-DP families and can translate back to (ε, δ) in closed form.

6 Limitations of Favorable Privacy–Utility Trade-offs

Under standard worst-case adversarial assumptions, one-epoch shuffled DP-SGD cannot simultaneously achieve noise below the 1/sqrt(2 ln M) threshold and arbitrarily small separation κ. The same limitation extends to Poisson subsampling up to constant factors, while the threshold decays extremely slowly with M.

  • Privacy–utility trade-off: Reducing separation κ below the stated lower bound requires entering a noise regime that degrades utility.The paper identifies this as an inevitable privacy–utility trade-off unless the worst-case assumptions are relaxed.
  • (ε, δ)-DP implication: ε ≥ 0.96 at M = 10^3 and ε ≥ 1.00 at M = 5 × 10^6 under the one-epoch baseline δ = 1/N with N = 10^8.The implication holds across practically relevant M and follows by substituting the separation lower bound into the ε map.
  • Practical scale: σ ≳ 0.24 for ImageNet-1k with batch size 256 and M ≈ 5 × 10^3, illustrating the slow decay of the required noise threshold.The passage reports ImageNet-1k as approximately 1.3M images and notes that even very large M leaves substantial noise requirements.
  • Poisson subsampling: Poisson-sampled DP-SGD inherits the shuffled worst-case limitation up to a constant factor, requiring σ ≥ 1/sqrt(2 ln M) to approach the random-guessing regime.A mixture argument transfers the shuffled separation lower bound to Poisson subsampling in the one-epoch setting.

7 Empirical Analysis

The experiments evaluate the theoretical noise floor across vision and text benchmarks, showing substantial accuracy degradation and very large privacy-accounting ε values at the threshold. Results span shuffling and Poisson subsampling, multiple batch sizes, and epoch budgets.

  • Datasets and Model Architectures: Experiments cover CIFAR-10/100, SVHN, and AG News using ResNet, ViT, and encoder-only Transformer architectures.Model variants range from Tiny to Base to examine how capacity interacts with privacy noise.
  • Experimental protocol and hyperparameter selection: For epoch budgets E ∈{1, 10, 25}, clean-training hyperparameters are selected with σ = 0 and then held fixed in subsequent experiments.The comparison includes clean training without clipping and full DP-SGD with clipping and Gaussian noise at the theoretical lower bound.
  • Results and interpretation: CIFAR-10 with ResNet-18 at batch size 128 saw σ = 0.29 reduce accuracy from 80.1% to 40.4% at 10 epochs and from 82.2% to 43.4% at 25 epochs.The reported utility gap is substantial and persistent relative to clean training.
  • Privacy accounting at the noise floor: ε ≥19.5 after one epoch, ε ≥103.7 after 10, and ε ≥219.2 after 25 at CIFAR-10’s noise threshold.These values use N = 50,000, δ = 2 × 10−5, and batch size 128.
  • Privacy accounting at the noise floor: Every ImageNet-21k configuration at the threshold yields ε ≫10, reaching ε ≥28.8 after one epoch.The bound tightens for larger datasets because fixed batch sizes produce more rounds per epoch and smaller δ = 1/N.

8 Discussion and Future Directions

The discussion frames DP-SGD’s limits as a structural tension under the standard worst-case adversarial model, while identifying alternative privacy notions and algorithmic changes as possible ways forward. It also highlights unresolved questions about multi-epoch separation and the practical accuracy costs of strong worst-case guarantees.

  • Adversarial model: The lower bounds may reflect limitations of the standard worst-case adversary, which permits arbitrary side information and observes all noisy updates.The paper presents this as potentially a limitation of the adversarial model rather than an indictment of DP-SGD itself.
  • Alternative privacy notions: Instance-based or distributional privacy could relax the trade-off by requiring privacy with high probability over the data distribution rather than uniformly over neighboring datasets.Separation κ is proposed as a yardstick for comparing these notions at the same noise level σ.
  • Algorithmic alternatives: Improving privacy–utility trade-offs may require algorithmic changes rather than simply increasing the noise multiplier.Suggested directions include changing gradient clipping and aggregation, reducing update dimensionality or sparsity before noise injection, and reconsidering training schedules.
  • Multi-epoch behavior: Multi-epoch training remains insufficiently understood because existing µ-GDP asymptotic analyses leave non-asymptotic constants open and do not directly capture separation.The main lower bound is derived for a single epoch, although multi-epoch training is common in practice.
  • Practical implications: The implied noise levels already cause substantial accuracy degradation at realistic batch sizes and model scales, while not proving that private learning is infeasible.The discussion emphasizes the concrete costs of strong worst-case guarantees within standard SGD-based training pipelines.

9 Conclusion

The paper establishes a fundamental limitation for DP-SGD under the standard worst-case adversarial model: noise and worst-case distinguishability cannot both be reduced below explicit lower bounds. This limitation applies to shuffling and Poisson subsampling, with experiments showing substantial utility degradation at the implied noise levels.

  • Conclusion: The f-DP hypothesis-testing framework reveals a fundamental limitation for DP-SGD under the standard worst-case adversarial model.The analysis considers realistic shuffling and Poisson subsampling.
  • Conclusion: Noise multiplier and worst-case distinguishability cannot be simultaneously driven below explicit lower bounds.This is characterized as a geometric limitation of the privacy-utility trade-off.
  • Conclusion: The limitation applies to both sampling schemes, and experiments confirm substantial utility degradation at the implied noise levels.The two schemes are realistic shuffling and Poisson subsampling.

Ethics Considerations … C Extended Experimental Results

The paper reports ethically limited, reproducible experiments using public data and open-source implementations, with extended results broadly confirming the main empirical behavior across sampling regimes, architectures, and datasets. Appendices document the training pipeline, model designs, reproducibility controls, and complete evaluations.

  • Ethics Considerations: The theoretical study introduces no attack, weakens no existing guarantee, and uses public benchmarks without human subjects or personal data.
  • A Open Science Appendix; A.2 Figures in Appendix F: A complete artifact reproduces empirical results from Section 7 and Appendices C and F using open-source frameworks, public datasets, Python 3.11, and provided packages.
  • A.1 Main Empirical Results (Section 7 and Appendix C): Experiments use public CIFAR-10, CIFAR-100, SVHN, and AG News datasets, with scripts supporting reproduction from saved runs or fresh runs at epoch budgets {1, 10, 25}.Saved specifications include per-epoch hyperparameters, clipping constant C†, and noise level σ; fresh runs compare clean training with DP-SGD.
  • A.1 Main Empirical Results (Section 7 and Appendix C); B.7 Reproducibility and Determinism: Explicit seeding makes sampling, shuffling, noise generation, padding, and microbatch ordering deterministic, although GPU and mixed-precision differences may cause negligible metric deviations.GPU memory requirements range from approximately 16–24GB for some configurations to ∼80GB for others.
  • B Implementation Details; B.1 Experimental Pipeline and DP-SGD Implementation; B.3 Sampling Mechanisms: The implementation uses JAX’s official DP-SGD primitives, Poisson subsampling, random shuffling, and standard image and text benchmarks while retaining practical alignment with theoretical assumptions.Shuffling uses fresh permutations and contiguous fixed-size batches; Poisson sampling independently includes examples with probability q and pads variable-length batches.
  • B.2 Microbatching; B.3 Sampling Mechanisms: Microbatching reduces memory and compilation overhead without changing the effective privacy mechanism, noise scale, clipping bound, or privacy accounting.Dummy padding indices have zero gradients, so padding does not affect optimization or privacy.

C.1 Per-Dataset (ε, δ)-DP Sweeps at the Noise Floor

Per-dataset sweeps evaluate (ε, δ)-DP at the Theorem 6.1 noise floor, σ = 1/sqrt(2 ln M), with δ = 1/N. Across the grid, larger batches reduce ε, larger datasets increase it at fixed batch size, and no configuration reaches ε ≤ 11.

  • C.1 Per-Dataset (ε, δ)-DP Sweeps at the Noise Floor: σ = 1/sqrt(2 ln M) defines the Theorem 6.1 noise floor, while δ = 1/N and ε values are shuffle-accountant lower bounds.The matching deterministic-batching upper bound agrees within 0.16 in every cell and within 0.03 for batch sizes BS ≤ 512.
  • C.1 Per-Dataset (ε, δ)-DP Sweeps at the Noise Floor: Increasing batch size raises σ and lowers ε because fewer rounds per epoch weaken the max-statistic.Here, M = floor(N/BS) is the number of rounds in one epoch.
  • C.1 Per-Dataset (ε, δ)-DP Sweeps at the Noise Floor: Increasing dataset size at a fixed batch size raises ε across every dataset block.N counts records; for ImageNet-21k, N is the whole corpus because it lacks an official train–validation split.
  • C.1 Per-Dataset (ε, δ)-DP Sweeps at the Noise Floor: No configuration anywhere in the sweep grid reaches ε ≤ 11.For the five representative Table 1 rows, the two accounting bounds agree within 0.03 throughout, making the quoted values tight.

D Proof of Lemma 6.5

The proof upper-bounds the Poisson-subsampled trade-off curve by conditioning on the distinguishing record’s inclusion count and reducing the experiment to a two-branch mixture. The never-sampled branch is indistinguishable under both hypotheses, while the sampled-once branch matches the shuffling experiment, yielding the claimed Poisson bound.

  • Conditioning and coarsening: K ∼ Binomial(M, q) counts rounds containing the distinguishing record, and coarsening K ≥1 to K = 1 produces a two-branch mixture that upper-bounds the true Poisson trade-off curve.The mixture has K = 0 with probability p = (1 − q)^M and K = 1 with probability 1 − p.
  • K = 0 branch: On K = 0, the distinguishing record is never sampled, so the observed-output distributions are identical under H0 and H1 and the adversary can do no better than random guessing.The computed gradients depend only on the common subset d ∩ d′, and the resulting distribution coincides with the null-hypothesis likelihood.
  • K = 1 branch: On K = 1, the distinguishing record appears in a uniformly random round, and the conditional observation model exactly matches the one-epoch shuffling experiment.Under H1, exactly one round has a shift of magnitude 1/σ; under H0, no round is shifted.
  • Mixture reduction: The mixture’s type-I and type-II errors combine the K = 0 random-guessing component with the K = 1 shuffling errors, reducing the optimization to the shuffling trade-off curve.The proof then applies the assumed shuffling bound to conclude the stated Poisson result.

E From Separation to (ε, δ)-DP Guarantees

This section converts the shuffled mechanism’s geometric separation κ into lower bounds on any compatible (ε, δ)-DP guarantee. Under δ = 1/N, the resulting minimum ε increases with separation, remains substantial for shuffled DP-SGD, and extends to Poisson subsampling up to a constant factor.

  • From separation to (ε, δ)-DP: A lower bound on shuffled separation κshuf imposes a minimum admissible ε for any reported (ε, δ)-DP guarantee of the same mechanism.The argument compares the mechanism’s separation with the closed-form separation of the canonical (ε, δ)-DP trade-off under δ = 1/N.
  • From separation to (ε, δ)-DP: κshuf must not exceed the separation κε,δ induced by any compatible (ε, δ)-DP guarantee.This ordering follows because the shuffled trade-off curve lies pointwise above the canonical (ε, δ)-DP trade-off curve.
  • From separation to (ε, δ)-DP: εmin(κ; N) is monotonically increasing in κ, so stronger separation forces a strictly larger minimum ε.A smaller ε is possible only with larger σ, violating the assumption used for the separation lower bound and hurting utility.
  • Poisson subsampling: κpois ≥ (1 −1/e) κshuf, so Poisson subsampling inherits the same εmin formula with a constant-factor weaker separation bound.The corresponding εmin is obtained by substituting κpois for κ in the shuffled-regime formula.
  • Numerical illustration: ε ≈1 is forced for shuffled DP-SGD at δ = 1/N with N = 10^8, while Poisson subsampling has a comparable but slightly weaker constraint.These are reported as best-case values for an optimistic one-epoch baseline.

F Asymptotic Separation Bound for Poisson Subsampling · F.1 Illustrative Asymptotic Instantiation

The asymptotic μ-GDP analysis translates Poisson-subsampled DP-SGD guarantees into separation predictions under proportional growth, while emphasizing that these predictions lack non-asymptotic convergence rates. An illustrative one-epoch extrapolation suggests that noise schedules of order σ = Θ(1/√ln M) yield rapidly increasing separation, whereas the paper’s main bound is finite-M and privacy-measure independent.

  • F Asymptotic Separation Bound for Poisson Subsampling: Lemma F.1 translates asymptotic μ-GDP guarantees for Poisson subsampling into an explicit separation prediction under proportional epoch-and-round growth.The result fixes σ^-1 > 0 and considers epoch budgets satisfying the stated scaling assumption as M →∞.
  • F Asymptotic Separation Bound for Poisson Subsampling: The predicted separation converges to a limiting value determined by the asymptotic μ-GDP parameter, with approximation error vanishing as M grows.The convergence is rigorous along sequences satisfying the proportional-growth condition, although the supplied passages do not provide convergence-rate constants.
  • F Asymptotic Separation Bound for Poisson Subsampling: Asymptotic closeness alone does not provide a formal privacy guarantee because the f-DP analysis supplies no convergence rates.The heuristic expectation that finite settings near the scaling curve inherit small privacy loss is explicitly distinguished from a proved guarantee.
  • F.1 Illustrative Asymptotic Instantiation: In the illustrative instantiation, the setting departs from Lemma F.1 by fixing one epoch and allowing σ to vary with M.Thus, the subsequent calculation is an extrapolation outside the lemma’s stated regime rather than a formal consequence of its asymptotic theory.
  • F.1 Illustrative Asymptotic Instantiation: This illustrative computation is heuristic, and the proofs of Theorems 6.1 and 6.4 do not rely on it.The paper explicitly separates the extrapolated μ-GDP calculation from its main finite-sample results.
  • F.1 Illustrative Asymptotic Instantiation: The main separation bound is non-asymptotic, holding for every finite M in the single-epoch setting without a limiting regime.The associated 2 ln M threshold is attributed to the observation model and persists under changes in privacy measurement.
  • F.1 Illustrative Asymptotic Instantiation: The 2 ln M scale reflects Gaussian extreme-value behavior, making the limitation structural rather than an artifact of the separation metric.A shifted coordinate must remain hidden among M unshifted Gaussian coordinates, and the paper formalizes this through a max-statistic converse and a reduction to Poisson subsampling.
Loading 2601.10237v3…