When training machine learning models with Differentially Private Stochastic Gradient Descent (DP-SGD), we rely on a phenomenon known as privacy amplification. The core intuition is simple: if an algorithm only looks at a small, randomly selected subset of the data at a time, an adversary cannot be certain whether a specific individual's data was used to compute a given gradient update. This uncertainty dilutes the privacy leak, allowing us to claim a much tighter privacy budget ($\epsilon$) than if we trained on the entire dataset at once.
To calculate these mathematical guarantees, standard privacy accounting tools almost universally assume Poisson subsampling—a method where each data point independently decides whether to join a mini-batch based on a coin flip.
However, a major discrepancy exists between this theoretical assumption and real-world engineering. In practice, machine learning libraries use data shuffling: they randomly permute the dataset and partition it into fixed-size blocks. As revealed by Lei Yu et al. in Differentially Private Model Publishing for Deep Learning, this mismatch creates a significant "privacy accounting gap." Practitioners who implement data shuffling for computational efficiency but report privacy bounds derived from Poisson subsampling are systematically underestimating their models' actual privacy loss.
Why Shuffling Weakens Privacy Amplification
To understand why this gap exists, we must look at how information leaks across an entire training epoch.
In Poisson subsampling, every batch is completely independent. If a target individual's record happens to be sampled into the first mini-batch, that event has zero bearing on whether they will appear in the second, third, or final mini-batch of the epoch. The adversary must evaluate each batch with uniform uncertainty.
Data shuffling destroys this independence by introducing structural dependencies across batches:
- The Exclusion Principle: If a dataset is shuffled and split into fixed blocks, a record can only appear exactly once per epoch. If an adversary detects a user's unique influence in the first mini-batch, they instantly know with 100% certainty that the user is absent from all remaining mini-batches in that epoch.
- Positional Leakage: As analyzed by Lynn Chua et al. in Bridging the Privacy Accounting Gap in DP-SGD, the non-differing records in shuffled batches inadvertently leak information about the positions of the records that do differ.
Because the random permutation binds the batches together, the privacy amplification benefits of shuffling degrade significantly over multiple training epochs. In How Private are DP-SGD Implementations?, the authors demonstrate that this discrepancy is not just a theoretical pedantry: a system claiming a safe privacy budget of $\epsilon = 2$ or $3$ under Poisson analysis can actually suffer from a true privacy loss exceeding $\epsilon = 10$ when executed via standard shuffling.
The Engineering Bottleneck of Perfect Sampling
If Poisson subsampling provides stronger and cleaner privacy guarantees, why do practical frameworks avoid it? The obstacle stems from modern hardware acceleration.
Poisson subsampling creates mini-batches of variable sizes. In high-performance computing frameworks like JAX or TensorFlow, changing tensor shapes across training steps forces the underlying XLA compiler to constantly re-compile the execution graph. This causes massive performance penalties.
As noted by Marlon Tobaben et al. in Towards Efficient and Scalable Training of Differentially Private Deep Learning, engineers routinely choose fixed-size shuffling to maintain training speed, unknowingly invalidating the formal privacy proofs that their software tools rely on.
Bridging the Gap
To resolve this tension between mathematical rigor and hardware efficiency, recent research focuses on two parallel tracks: developing tighter privacy accounting specifically for shuffling, and designing hardware-friendly samplers that mimic Poisson properties.
Tighter Shuffling Analyses
Instead of pretending shuffling is Poisson sampling, researchers are deriving native bounds for shuffling networks. Vitaly Feldman et al. introduced an analytical framework in Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling, proving that a shuffled local mechanism can be modeled as "hiding among clones" to achieve optimal single-epoch bounds. For multi-epoch settings, Jeremiah Birrell et al. developed tighter Rényi Differential Privacy (RDP) guarantees for fixed-size minibatches in Differentially Private Stochastic Gradient Descent with Fixed-Size Minibatches: Tighter RDP Guarantees with or without Replacement, narrowing the analytical gap without altering the underlying training pipeline.
Privacy-Preserving Fixed-Size Samplers
Rather than accepting weaker shuffling bounds, another approach replaces standard shuffling with alternative batching strategies that satisfy compilers while preserving privacy. In Bridging the Privacy Accounting Gap in DP-SGD, the authors proposed a "Balls-and-Bins" sampler that maintains rigid, hardware-efficient batch sizes while delivering privacy guarantees that meet or exceed Poisson subsampling. Similarly, Lynn Chua et al. introduced a "Truncated Poisson" method in Scalable DP-SGD: Shuffling vs. Poisson Subsampling to scale true independent sampling to massive datasets without triggering compilation overhead.
Leveraging Structural Randomness
Finally, researchers are realizing that data sampling is not the only source of uncertainty in a training pipeline. Andy Dong et al. demonstrated in Leveraging Randomness in Model and Data Partitioning for Privacy Amplification that structural randomness already present in deep learning—such as dropout and model parallelism—can be formally quantified to amplify privacy. By accounting for these inherent layers of obfuscation, practitioners can achieve rigorous DP guarantees without needing to inject excessive, utility-degrading noise.
Key Foundational Work
Differentially Private Model Publishing for Deep Learning (2019) — contributed 3 concept elements to this direction.
Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling (2020) — contributed 1 concept elements to this direction.