To Shuffle or not to Shuffle: Auditing DP-SGD with Shuffling

To Shuffle or not to Shuffle: Auditing DP-SGD with Shuffling

Speakers: Meenatchi Sundaram Muthu Selva Annamalai

Conference: NDSS Symposium 2026

YouTube: https://www.youtube.com/watch?v=yDk0rY-Ools

Overview

Differentially Private Stochastic Gradient Descent (DP-SGD) is the standard approach for training machine learning models with formal privacy guarantees. A critical implementation detail is how training data is subsampled into batches: Poisson subsampling has well-understood theoretical privacy guarantees, but shuffling is far more efficient and widely used in practice. The problem is that tight theoretical privacy bounds for shuffling-based DP-SGD are unknown, yet most implementations use Poisson-based theoretical bounds while actually implementing shuffling. This talk presents the first empirical audit of DP-SGD with shuffling, training approximately 1 million models across multiple datasets. The results demonstrate that shuffling-based implementations violate their reported theoretical privacy guarantees -- the empirical privacy leakage exceeds the claimed upper bounds. The finding has immediate implications for deployed privacy-preserving ML systems: organizations using DP-SGD with shuffling may be providing weaker privacy protections than they believe.

Background

▶ Watch: DP-SGD overview: subsampling, gradient clipping, noise addition (1:30)

Differential privacy (DP) provides a mathematical guarantee that the output of an algorithm does not reveal whether any specific individual's data was included in the input. The privacy parameter epsilon quantifies this guarantee: smaller epsilon means stronger privacy. DP-SGD applies this to model training by subsampling batches, computing gradients, clipping them to bound individual influence, and adding calibrated noise.

Subsampling is where the implementation diverges from theory. Poisson subsampling samples each record independently with a given probability (following a Poisson distribution), providing well-understood privacy amplification guarantees. Shuffling randomly permutes the dataset and sequentially selects B records per batch. Shuffling is dramatically faster because it allows sequential access and benefits from hardware optimizations like XLA fixed-batch-size optimization, whereas Poisson requires random access to the entire dataset.

The gap is that existing theoretical privacy proofs use Poisson subsampling, but real-world implementations increasingly use shuffling for efficiency. Prior theoretical work analyzed shuffling only for highly simplified versions of DP-SGD that are not used in practice, leaving a gap between what is proven and what is deployed.

DP auditing is a technique that empirically estimates privacy guarantees by launching membership inference attacks -- adversaries that try to determine whether a specific record was used to train a model. The success rate of these attacks (quantified through false positive and false negative rates) is converted to an empirical epsilon that can be compared against the theoretical bound.

Key Findings

▶ Watch: The gap: Poisson bounds used in theory, shuffling used in practice (5:30)

Shuffling violates theoretical privacy bounds: Under worst-case adversary assumptions, the empirical epsilon consistently exceeds the theoretical epsilon derived from Poisson-based proofs. This means the actual privacy leakage is greater than what is claimed, and DP-SGD implementations using shuffling are providing weaker privacy than reported.

Adversarial power matters: Under a weaker target canary adversary, violations are not detected. However, under stronger adversaries -- particularly those who can inject gradients into individual batches or all records -- the violations become clear. Since differential privacy is a worst-case guarantee that should hold against pathologically strong adversaries, the violation under strong adversaries is a genuine problem.

Partial shuffling variants also have issues: Variants like partial shuffling and bot-and-shuffle also exhibit privacy violations, some even under weaker adversary models.

Pseudo-random number generation is a common bug source: The researchers reference related work that found PRNG bugs in differentially private synthetic data ML models, including submissions to a NIST competition. Fixing PRNG implementation bugs can reduce model utility, so there is no free fix.

Technical Deep Dive

▶ Watch: DP auditing via membership inference attacks and empirical epsilon (7:00)

The auditing methodology follows the framework from prior work (Nasr et al.), adapted and extended for shuffling-specific analysis. The approach involves generating neighboring datasets (differing in exactly one record), training the model repeatedly on both datasets, and launching membership inference attacks using a likelihood ratio test to determine whether the target record was included.

The adversarial power is modulated across three levels: (1) target canary -- the weakest adversary who can only observe the model output, (2) partially informed adversary -- with some knowledge of other training data, and (3) worst-case adversary -- who can inject gradients of the target record into specific or all batches.

The empirical epsilon is computed from the attack success rates and compared against the theoretical epsilon that implementations report based on Poisson subsampling privacy amplification theorems. The experiments use datasets including FMNIST, Purchase-100, and CIFAR-10 with different model architectures, training approximately 1 million models total.

The results show a clear pattern: under Poisson subsampling, the empirical epsilon stays below the theoretical bound (as expected). Under shuffling with the same theoretical bounds, the empirical epsilon exceeds the bound, demonstrating that the Poisson-based bounds do not transfer to shuffling. The gap is not marginal -- the researchers present animated visualizations showing the empirical epsilon climbing above the theoretical line.

Demo / Proof of Concept

▶ Watch: Partial shuffling variants also show privacy violations (11:00)

The experimental results across multiple datasets and adversary models demonstrate consistent privacy bound violations when shuffling is used with Poisson-based theoretical guarantees. The violations are most pronounced under worst-case adversary models, which is the appropriate threat model for differential privacy guarantees. Additional experiments with partial shuffling variants reveal further violations, sometimes even under weaker adversary models. The researchers trained approximately 1 million models total across all configurations, providing strong statistical confidence in the results.

Defensive Implications

▶ Watch: PRNG bugs as an additional common source of privacy violations (13:30)

For organizations deploying DP-SGD in production, this is an immediate action item. If your privacy-preserving ML pipeline uses shuffling (which most do for efficiency), the privacy guarantees you report to users, regulators, and data protection authorities may be overstated. The theoretical epsilon computed using Poisson-based proofs does not hold for shuffling implementations.

For ML framework developers (PyTorch, TensorFlow, JAX with Opacus/tensorflow-privacy), this research highlights the need to either: (1) implement Poisson subsampling despite its performance overhead, (2) derive tight theoretical bounds for shuffling (an open theoretical problem), or (3) adopt alternative sampling schemes like balls-in-bins that have emerged as promising alternatives with better-understood guarantees.

For privacy regulators and compliance teams, the finding underscores the importance of auditing privacy implementations, not just privacy claims. A system that reports epsilon=1 based on theoretical analysis but actually provides epsilon=3 in practice is misleading, and regulatory frameworks should encourage empirical auditing alongside theoretical proofs.

For privacy researchers, the auditing tools and methodology extended for shuffling are available for follow-up work. The paper also identifies PRNG-related bugs as a common source of privacy violations in implemented systems.

Key Takeaways

• DP-SGD implementations using shuffling violate their reported privacy bounds derived from Poisson subsampling theory
• Shuffling is used in practice for efficiency despite lacking tight theoretical privacy proofs
• Approximately 1 million models were trained to empirically demonstrate the privacy gap
• Violations are detectable under worst-case adversary models, which is the appropriate standard for DP guarantees
• Partial shuffling variants also exhibit privacy violations
• Recommendation: avoid shuffling in real-world DP-SGD deployments with sensitive data; consider alternative sampling schemes like balls-in-bins
• PRNG implementation bugs are a common additional source of privacy violations in ML systems

About the Speaker(s)

Meenatchi Sundaram Muthu Selva Annamalai is a researcher whose work focuses on differential privacy auditing and privacy-preserving machine learning. The research is a collaboration with students and Jamie Hayes at Google DeepMind. The team has prior work on auditing differentially private synthetic data models and identifying implementation bugs in privacy technologies, including findings in NIST competition submissions.