Bridging the Privacy Accounting Gap in DP-SGD

Lynn Chua, Badih Ghazi, Charlie Harrison, Ethan Leeman, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Amer Sinha, Chiyuan ZhangJournal of Privacy and Confidentiality 2025 · DOI

Abstract

Differentially Private Stochastic Gradient Descent (DP-SGD) is one of the most widely used algorithms for private machine learning. Due to its efficiency, most practical implementations of DP-SGD shuffle the training examples and divide them into fixed-size mini-batches during training. However, the privacy accounting typically assumes that Poisson subsampling was used, wherein each example is included in each mini-batch independently with some probability. Our first contribution is to show that there can be a substantial gap between these two versions of DP-SGD; specifically, the privacy accounting implies much stronger privacy guarantees than the implementations actually provide. As our second contribution, we propose two approaches to address this gap: (i) an implementation of Poisson subsampling using the Map-Reduce framework that can scale to large datasets that do not fit in memory and (ii) a novel Balls-and-Bins sampling that achieves the “best of both” sampling approaches. Namely, its implementation is similar to shuffling, and it leads to similar utility for DP-SGD training with similar-or-better privacy compared to Poisson subsampling in practical regimes of parameters.

Introduction

Differentially Private Stochastic Gradient Descent (DP-SGD) has become the standard for training machine learning models with formal privacy guarantees. The algorithm operates by clipping individual gradients and adding Gaussian noise to the aggregate. A critical component of the privacy analysis is the "batch generator"—the mechanism used to select data for each training step.

In theory, most privacy analyses assume Poisson Subsampling, where each data point is included in a batch independently with a fixed probability $q$. While mathematically convenient, this approach results in variable batch sizes, which is incompatible with high-performance computing frameworks like XLA/JAX that require fixed tensor shapes. Consequently, practitioners typically implement Shuffling, where the dataset is randomly permuted and split into fixed-size batches.

This paper addresses a dangerous "accounting gap": the common practice of implementing Shuffling while reporting privacy metrics calculated for Poisson Subsampling. We demonstrate that Shuffling often provides significantly weaker privacy than the Poisson analysis suggests, potentially leading to over-reported privacy guarantees.

Methodology

To bridge this gap, the authors propose two primary solutions and a refined accounting framework.

Truncated Poisson Subsampling

To reconcile Poisson subsampling with fixed-shape hardware (e.g., TPUs), the researchers introduce a truncated version. They cap the batch size at a maximum $B$ and pad smaller batches with "dummy" examples (zero-weight). To handle industry-scale datasets, they provide a parallel implementation using the Map-Reduce framework (via Apache Beam), enabling processing of datasets that exceed system memory.

Balls-and-Bins Sampling

They introduce Balls-and-Bins sampling, a novel batching strategy designed to combine the benefits of both worlds. In this approach, each training example is assigned to one of $T$ batches uniformly at random. Like shuffling, each example appears exactly once per epoch, ensuring high utility. Crucially, it is more amenable to privacy analysis than standard shuffling.

Advanced Privacy Accounting

Since the privacy loss for these samplers lacks simple closed-form solutions, the authors developed a specialized Monte Carlo estimation method. To efficiently handle training runs with thousands of steps, they introduced "Order Statistics Sampling," which significantly accelerates the estimation of privacy loss compared to naive simulations.

Experimental Evaluation

The methods were evaluated on two large-scale advertising datasets representative of industrial DP-SGD deployments:

  • Criteo Display Ads pCTR: ~46 million examples for predicting ad click-through rates.
  • Criteo Sponsored Search Conversion Log: ~16 million examples for predicting binary sales conversions.

Key Results

Quantifying the Privacy Gap

The analysis reveals a substantial discrepancy between the assumed Poisson privacy and the actual privacy provided by shuffling. For a fixed noise level, the privacy cost ($\epsilon$) for Shuffling can be significantly higher than for Poisson.

Privacy loss (ε) vs. noise multiplier (σ) comparing Poisson subsampling (ε_P) and Shuffling lower bounds (ε_S).

As shown in the figure above, for a noise multiplier $\sigma = 0.4$, the Poisson analysis might suggest an $\epsilon$ around 5-7, while the actual lower bound for Shuffling ($\epsilon_S$) exceeds 14. This highlights the risk of overestimating privacy when using mismatched accounting.

Utility and Performance

Experiments on the Criteo datasets demonstrate that Balls-and-Bins and Shuffling produce models with nearly identical AUC (Area Under the Curve). This confirms that the "Balls-and-Bins" approach provides the necessary "privacy amplification" benefits of random subsampling without sacrificing the model utility typically associated with shuffling.

Conclusion

This work exposes and addresses a critical flaw in current DP-SGD implementations. By providing a scalable Poisson implementation and the novel Balls-and-Bins sampler, the authors offer practitioners tools to achieve rigorous, hardware-efficient privacy. Future work includes developing deterministic, provably tight accounting for Balls-and-Bins and extending the analysis to multi-epoch training regimes where privacy composition becomes more complex.

Summary updated

Abstract

Differentially Private Stochastic Gradient Descent (DP-SGD) is one of the most widely used algorithms for private machine learning. Due to its efficiency, most practical implementations of DP-SGD shuffle the training examples and divide them into fixed-size mini-batches during training. However, the privacy accounting typically assumes that Poisson subsampling was used, wherein each example is included in each mini-batch independently with some probability. Our first contribution is to show that there can be a substantial gap between these two versions of DP-SGD; specifically, the privacy accounting implies much stronger privacy guarantees than the implementations actually provide. As our second contribution, we propose two approaches to address this gap: (i) an implementation of Poisson subsampling using the Map-Reduce framework that can scale to large datasets that do not fit in memory and (ii) a novel Balls-and-Bins sampling that achieves the “best of both” sampling approaches. Namely, its implementation is similar to shuffling, and it leads to similar utility for DP-SGD training with similar-or-better privacy compared to Poisson subsampling in practical regimes of parameters.
BibTeX
@article{chua2025bridging,
  author = {Lynn Chua and Badih Ghazi and Charlie Harrison and Ethan Leeman and Pritish Kamath and Ravi Kumar and Pasin Manurangsi and Amer Sinha and Chiyuan Zhang},
  title = {{Bridging the Privacy Accounting Gap in DP-SGD}},
  journal = {Journal of Privacy and Confidentiality},
  year = {2025},
  doi = {10.29012/jpc.998},
}
Figure