mlsanityData to 14 Oct 2026

Scalable DP-SGD: Shuffling vs. Poisson Subsampling

arXiv 2411.04205 ↗First posted 6 Nov 2024cs.LG cs.CR cs.DScited by 16

Not on the map. Why?

Abstract (arXiv)

We provide new lower bounds on the privacy guarantee of the multi-epoch Adaptive Batch Linear Queries (ABLQ) mechanism with shuffled batch sampling, demonstrating substantial gaps when compared to Poisson subsampling; prior analysis was limited to a single epoch. Since the privacy analysis of Differentially Private Stochastic Gradient Descent (DP-SGD) is obtained by analyzing the ABLQ mechanism, this brings into serious question the common practice of implementing shuffling-based DP-SGD, but reporting privacy parameters as if Poisson subsampling was used. To understand the impact of this gap on the utility of trained machine learning models, we introduce a practical approach to implement Poisson subsampling at scale using massively parallel computation, and efficiently train models with the same. We compare the utility of models trained with Poisson-subsampling-based DP-SGD, and the optimistic estimates of utility when using shuffling, via our new lower bounds on the privacy guarantee of ABLQ with shuffling.

Key facts. Cited by 16 papers in the map (data through 14 Oct 2026). Builds on 25 of its 36 references that are in the map. First posted on arXiv 6 Nov 2024.

Builds on

25 of 36 references.

References · 25

  1. 2016Deep Learning with Differential Privacycited by 2,728
  2. 2017Renyi Differential Privacycited by 650
  3. 2021Opacus: User-Friendly Differential Privacy Library in PyTorchcited by 383
  4. 2020Differentially Private Learning Needs Better Features (or Much More Data)cited by 235
  5. 2022Unlocking High-Accuracy Differentially Private Image Classification through Scalecited by 224
  6. 2018Improving the Gaussian Mechanism for Differential Privacy: Analytical Calibration and Optimal Denoisingcited by 218
  7. 2021Numerical Composition of Differential Privacycited by 180
  8. 2021Practical and Private (Deep) Learning without Sampling or Shufflingcited by 170
  9. 2023How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacycited by 153
  10. 2022Differentially Private Diffusion Modelscited by 119
  11. 2021Large-Scale Differentially Private BERTcited by 118
  12. 2020GS-WGAN: A Gradient-Sanitized Approach for Learning Differentially Private Generatorscited by 117
13 more
  1. 2018Privacy Amplification by Iterationcited by 100
  2. 2020Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shufflingcited by 96
  3. 2021Optimal Accounting of Differential Privacy via Characteristic Functioncited by 86
  4. 2022Privacy of Noisy Stochastic Gradient Descent: More Iterations without More Privacy Losscited by 61
  5. 2022Connect the Dots: Tighter Discrete Approximations of Privacy Loss Distributionscited by 52
  6. 2022Exploring the Limits of Differentially Private Deep Learning with Group-wise Clippingcited by 52
  7. 2022Scalable and Efficient Training of Large Convolutional Neural Networks with Differential Privacycited by 48
  8. 2024Private Fine-tuning of Large Language Models with Zeroth-order Optimizationcited by 41
  9. 2022Stronger Privacy Amplification by Shuffling for R'enyi and Approximate Differential Privacycited by 29
  10. 2022Faster Privacy Accounting via Evolving Discretizationcited by 15
  11. 2024Avoiding Pitfalls for Privacy Accounting of Subsampled Mechanisms under Compositioncited by 13
  12. 2024It's Our Loss: No Privacy Amplification for Hidden State DP-SGD With Non-Convex Losscited by 10
  13. 2023DP-NMT: Scalable Differentially-Private Machine Translationcited by 7

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 2; 2025: 8; 2026: 6.

16 papers.

Sort:

  1. 2025VaultGemma: A Differentially Private Gemma Modelcited by 16
  2. 2025Privacy amplification by random allocationcited by 15
  3. 2024Balls-and-Bins Sampling for DP-SGDcited by 14
  4. 2024To Shuffle or not to Shuffle: Auditing DP-SGD with Shufflingcited by 6
  5. 2025The Hitchhiker's Guide to Efficient, End-to-End, and Tight DP Auditingcited by 5
  6. 2026Fundamental Limitations of Favorable Privacy-Utility Guarantees for DP-SGDcited by 4
  7. 2025Empirical Privacy Variancecited by 3
  8. 2025Beyond Sin-Squared Error: Linear-Time Entrywise Uncertainty Quantification for Streaming PCAcited by 3
  9. 2026Efficient privacy loss accounting for subsampling and random allocationcited by 3
  10. 2026JAX-Privacy: A library for differentially private machine learningcited by 3
  11. 2025Private Rate-Constrained Optimization with Applications to Fair Learningcited by 1
  12. 2025Correlating Cross-Iteration Noise for DP-SGD using Model Curvaturecited by 1
4 more
  1. 2025Cocoon: A System Architecture for Differentially Private Training with Correlated Noisescited by 1
  2. 2026Trade-off Functions for DP-SGD with Subsampling based on Random Allocation: Tight Upper and Lower Boundscited by 1
  3. 2026From Privacy to Generalization: Linear Max-Information Bounds for Differentially Private Learning Algorithmscited by 0
  4. 2026ContinuousBench: Can Differentially Private Synthetic Text Improve Capabilities?cited by 0