Research map / Federated learning and privacy / Differential privacy
Scalable DP-SGD: Shuffling vs. Poisson Subsampling
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives multi-epoch lower bounds on the privacy loss of shuffled-batch DP-SGD (persistent and dynamic shuffling), and a scalable MapReduce implementation of truncated Poisson subsampling, then compares utility of DP-SGD under each sampler on Criteo pCTR.
Problem
Shuffling-based DP-SGD is commonly implemented but its privacy is reported as if Poisson subsampling were used; the correct multi-epoch privacy of shuffling is unknown, and Poisson subsampling is rarely implemented at scale.
Approach
Extends the single-epoch lower-bound technique for shuffled ABLQ to multiple epochs via dominating pairs and discretized PLD accounting for persistent and dynamic shuffling, and implements truncated Poisson subsampling at scale with Apache Beam-style MapReduce.
Key results
- For epsilon=5, delta=2.7e-8 and 1 or 5 epochs, lower bounds on the noise scale for dynamic and persistent shuffling are significantly larger than the Poisson subsampling noise scale, showing a privacy gap.
- Truncated Poisson subsampling performs similarly to dynamic shuffling at the same sigma on Criteo AUC.
- With a fixed batch size of 65,536, shuffling with the lower-bound accounting performs worse than truncated Poisson subsampling at low epsilon but slightly better at high epsilon.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use truncated Poisson subsampling instead of dynamic shuffling at the same noise scale | DP-SGD · Criteo Display Ads pCTR | AUC | No clear effect |
| Use truncated Poisson subsampling instead of dynamic shuffling with the respective privacy accounting | DP-SGD · Criteo Display Ads pCTR, high privacy (low ε) | AUC | Helped |
| Use dynamic shuffling instead of truncated Poisson subsampling with the respective privacy accounting | DP-SGD · Criteo Display Ads pCTR, low privacy (high ε) | AUC | Helped |
| Use truncated Poisson subsampling instead of dynamic or persistent shuffling | SGD without clipping or noise · Criteo Display Ads pCTR, non-private training | AUC | Hurt |
Surprising findings
- Privacy amplification by shuffling bounds are vacuous for batch sizes 2,048 and above, being no better than the unamplified Gaussian noise scale.
- Truncated Poisson subsampling is worse than shuffling for non-private training, attributed to a substantial fraction of examples never being seen.
Limitations
- Only provides lower bounds on the privacy loss of shuffling; tight upper bounds remain open.
- Experiments use a single dataset (Criteo) and a single model architecture (~78M parameter MLP with embeddings).
Experimental setup
Datasets: Criteo Display Ads pCTR Dataset
Benchmarks: Criteo Display Ads pCTR Dataset
Metrics: AUC noise scale sigma
Baselines: deterministic batches truncated Poisson subsampling persistent shuffling dynamic shuffling privacy amplification by shuffling
Builds on: DP-SGD dominating pairs privacy loss distribution single-epoch shuffling lower bound (Feldman et al.) privacy amplification by shuffling
Closest papers by meaning
- How Private are DP-SGD Implementations? (ICML 2024 · similarity 0.97)
- Differentially Private Stochastic Gradient Descent with Fixed-Size Minibatches: Tighter RDP Guarantees with or without Replacement (NeurIPS 2024 · similarity 0.92)
- The Last Iterate Advantage: Empirical Auditing and Principled Heuristic Analysis of Differentially Private SGD (ICLR 2025 · similarity 0.88)
- A Generalized Shuffle Framework for Privacy Amplification: Strengthening Privacy Guarantees and Enhancing Utility (AAAI 2024 · similarity 0.88)
- Shifted Interpolation for Differential Privacy (ICML 2024 · similarity 0.87)
- Unified Mechanism-Specific Amplification by Subsampling and Group Privacy Amplification (NeurIPS 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.