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