mlsanityData to 7 Oct 2026

Balls-and-Bins Sampling for DP-SGD

arXiv 2412.16802 ↗First posted 21 Dec 2024cs.LG cs.CR cs.DScited by 13

Not on the map. Why?

Abstract (arXiv)

We introduce the Balls-and-Bins sampling for differentially private (DP) optimization methods such as DP-SGD. While it has been common practice to use some form of shuffling in DP-SGD implementations, privacy accounting algorithms have typically assumed that Poisson subsampling is used instead. Recent work by Chua et al. (ICML 2024), however, pointed out that shuffling based DP-SGD can have a much larger privacy cost in practical regimes of parameters. In this work we show that the Balls-and-Bins sampling achieves the "best-of-both" samplers, namely, the implementation of Balls-and-Bins sampling is similar to that of Shuffling and models trained using DP-SGD with Balls-and-Bins sampling achieve utility comparable to those trained using DP-SGD with Shuffling at the same noise multiplier, and yet, Balls-and-Bins sampling enjoys similar-or-better privacy amplification as compared to Poisson subsampling in practical regimes.

Key facts. Cited by 13 papers in the map (data through 7 Oct 2026). Builds on 24 of its 52 references that are in the map. First posted on arXiv 21 Dec 2024.

Builds on

24 of 52 references.

References · 24

  1. 2016Deep Learning with Differential Privacycited by 2,682
  2. 2021Opacus: User-Friendly Differential Privacy Library in PyTorchcited by 375
  3. 2013The Composition Theorem for Differential Privacycited by 290
  4. 2022Unlocking High-Accuracy Differentially Private Image Classification through Scalecited by 218
  5. 2018Improving the Gaussian Mechanism for Differential Privacy: Analytical Calibration and Optimal Denoisingcited by 216
  6. 2021Practical and Private (Deep) Learning without Sampling or Shufflingcited by 169
  7. 2023How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacycited by 150
  8. 2016Concentrated Differential Privacycited by 139
  9. 2022Differentially Private Diffusion Modelscited by 118
  10. 2021Large-Scale Differentially Private BERTcited by 117
  11. 2021Optimal Accounting of Differential Privacy via Characteristic Functioncited by 83
  12. 2022Exploring the Limits of Differentially Private Deep Learning with Group-wise Clippingcited by 52
12 more
  1. 2024Private Fine-tuning of Large Language Models with Zeroth-order Optimizationcited by 41
  2. 2020Privacy Amplification via Random Check-Inscited by 39
  3. 2024How Private are DP-SGD Implementations?cited by 22
  4. 2018Reacting to Variations in Product Demand: An Application for Conversion Rate (CR) Prediction in Sponsored Searchcited by 18
  5. 2024Near Exact Privacy Amplification for Matrix Mechanismscited by 17
  6. 2024Scalable DP-SGD: Shuffling vs. Poisson Subsamplingcited by 16
  7. 2024Avoiding Pitfalls for Privacy Accounting of Subsampled Mechanisms under Compositioncited by 12
  8. 2023A Randomized Approach for Tight Privacy Accountingcited by 11
  9. 2024It's Our Loss: No Privacy Amplification for Hidden State DP-SGD With Non-Convex Losscited by 10
  10. 2023DP-NMT: Scalable Differentially-Private Machine Translationcited by 7
  11. 2024To Shuffle or not to Shuffle: Auditing DP-SGD with Shufflingcited by 6
  12. 2024Efficient and Scalable Implementation of Differentially Private Deep Learning without Shortcutscited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 4; 2026: 9.

13 papers.

Sort:

  1. 2025Privacy amplification by random allocationcited by 13
  2. 2025Back to Square Roots: An Optimal Bound on the Matrix Factorization Error for Multi-Epoch Differentially Private SGDcited by 7
  3. 2025The Hitchhiker's Guide to Efficient, End-to-End, and Tight DP Auditingcited by 4
  4. 2026Fundamental Limitations of Favorable Privacy-Utility Guarantees for DP-SGDcited by 4
  5. 2026Sampling-Free Privacy Accounting for Matrix Mechanisms under Random Allocationcited by 3
  6. 2026Efficient privacy loss accounting for subsampling and random allocationcited by 3
  7. 2026JAX-Privacy: A library for differentially private machine learningcited by 2
  8. 2025PREAMBLE: Private and Efficient Aggregation via Block Sparse Vectorscited by 1
  9. 2026DP-λCGD: Efficient Noise Correlation for Differentially Private Model Trainingcited by 1
  10. 2026Trade-off Functions for DP-SGD with Subsampling based on Random Allocation: Tight Upper and Lower Boundscited by 1
  11. 2026Less Random, More Private: What is the Optimal Subsampling Scheme for DP-SGD?cited by 1
  12. 2026From Privacy to Generalization: Linear Max-Information Bounds for Differentially Private Learning Algorithmscited by 0
1 more
  1. 2026Dithered Gaussian Mechanism for Randomness-Efficient Differential Privacycited by 0