To Shuffle or not to Shuffle: Auditing DP-SGD with Shuffling
Meenatchi Sundaram Muthu Selva Annamalai
Network and Distributed System Security (NDSS) Symposium 2026 · Day 3 · Connectivity & Privacy
**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.
AI review
Empirical demonstration that DP-SGD implementations using shuffling violate their claimed privacy bounds, training 1 million models to prove the gap. Not offensive security, but genuinely important for anyone relying on differential privacy guarantees -- which increasingly includes organizations deploying ML on sensitive data.