# Balls-and-Bins Sampling for DP-SGD

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

## Key facts

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

## Builds on (most cited first, 24 of 24)

- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Opacus: User-Friendly Differential Privacy Library in PyTorch](https://mlsanity.com/paper/2109.12298/) (2021)
- [The Composition Theorem for Differential Privacy](https://mlsanity.com/paper/1311.0776/) (2013)
- [Unlocking High-Accuracy Differentially Private Image Classification through Scale](https://mlsanity.com/paper/2204.13650/) (2022)
- [Improving the Gaussian Mechanism for Differential Privacy: Analytical Calibration and Optimal Denoising](https://mlsanity.com/paper/1805.06530/) (2018)
- [Practical and Private (Deep) Learning without Sampling or Shuffling](https://mlsanity.com/paper/2103.00039/) (2021)
- [How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy](https://mlsanity.com/paper/2303.00654/) (2023)
- [Concentrated Differential Privacy](https://mlsanity.com/paper/1603.01887/) (2016)
- [Differentially Private Diffusion Models](https://mlsanity.com/paper/2210.09929/) (2022)
- [Large-Scale Differentially Private BERT](https://mlsanity.com/paper/2108.01624/) (2021)
- [Optimal Accounting of Differential Privacy via Characteristic Function](https://mlsanity.com/paper/2106.08567/) (2021)
- [Exploring the Limits of Differentially Private Deep Learning with Group-wise Clipping](https://mlsanity.com/paper/2212.01539/) (2022)
- [Private Fine-tuning of Large Language Models with Zeroth-order Optimization](https://mlsanity.com/paper/2401.04343/) (2024)
- [Privacy Amplification via Random Check-Ins](https://mlsanity.com/paper/2007.06605/) (2020)
- [How Private are DP-SGD Implementations?](https://mlsanity.com/paper/2403.17673/) (2024)
- [Reacting to Variations in Product Demand: An Application for Conversion Rate (CR) Prediction in Sponsored Search](https://mlsanity.com/paper/1806.08211/) (2018)
- [Near Exact Privacy Amplification for Matrix Mechanisms](https://mlsanity.com/paper/2410.06266/) (2024)
- [Scalable DP-SGD: Shuffling vs. Poisson Subsampling](https://mlsanity.com/paper/2411.04205/) (2024)
- [Avoiding Pitfalls for Privacy Accounting of Subsampled Mechanisms under Composition](https://mlsanity.com/paper/2405.20769/) (2024)
- [A Randomized Approach for Tight Privacy Accounting](https://mlsanity.com/paper/2304.07927/) (2023)
- [It's Our Loss: No Privacy Amplification for Hidden State DP-SGD With Non-Convex Loss](https://mlsanity.com/paper/2407.06496/) (2024)
- [DP-NMT: Scalable Differentially-Private Machine Translation](https://mlsanity.com/paper/2311.14465/) (2023)
- [To Shuffle or not to Shuffle: Auditing DP-SGD with Shuffling](https://mlsanity.com/paper/2411.10614/) (2024)
- [Efficient and Scalable Implementation of Differentially Private Deep Learning without Shortcuts](https://mlsanity.com/paper/2406.17298/) (2024)

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

- [Privacy amplification by random allocation](https://mlsanity.com/paper/2502.08202/) (2025)
- [Back to Square Roots: An Optimal Bound on the Matrix Factorization Error for Multi-Epoch Differentially Private SGD](https://mlsanity.com/paper/2505.12128/) (2025)
- [The Hitchhiker's Guide to Efficient, End-to-End, and Tight DP Auditing](https://mlsanity.com/paper/2506.16666/) (2025)
- [Fundamental Limitations of Favorable Privacy-Utility Guarantees for DP-SGD](https://mlsanity.com/paper/2601.10237/) (2026)
- [Sampling-Free Privacy Accounting for Matrix Mechanisms under Random Allocation](https://mlsanity.com/paper/2601.21636/) (2026)
- [DP-λCGD: Efficient Noise Correlation for Differentially Private Model Training](https://mlsanity.com/paper/2601.22334/) (2026)
- [Efficient privacy loss accounting for subsampling and random allocation](https://mlsanity.com/paper/2602.17284/) (2026)
- [JAX-Privacy: A library for differentially private machine learning](https://mlsanity.com/paper/2602.17861/) (2026)
- [Less Random, More Private: What is the Optimal Subsampling Scheme for DP-SGD?](https://mlsanity.com/paper/2605.07072/) (2026)
- [PREAMBLE: Private and Efficient Aggregation via Block Sparse Vectors](https://mlsanity.com/paper/2503.11897/) (2025)
- [Trade-off Functions for DP-SGD with Subsampling based on Random Allocation: Tight Upper and Lower Bounds](https://mlsanity.com/paper/2605.06259/) (2026)
- [From Privacy to Generalization: Linear Max-Information Bounds for Differentially Private Learning Algorithms](https://mlsanity.com/paper/2605.26222/) (2026)
- [Dithered Gaussian Mechanism for Randomness-Efficient Differential Privacy](https://mlsanity.com/paper/2607.06320/) (2026)
- [Can R'enyi Accountants Beat Lossless Accountants for DP-SGD?](https://mlsanity.com/paper/2610.17120/) (2026)

## 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.