Research map / Optimization / Optimizers
Subsampling is not Magic: Why Large Batch Sizes Work for Differentially Private Stochastic Optimisation
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.
Proves that in the infinite-composition limit the effective DP noise variance of Poisson-subsampled DP-SGD is invariant to batch size, so larger batches reduce total gradient variance, and gives a numerically checked sufficient condition for the single-iteration case.
Problem
Explain theoretically why large batch sizes help DP-SGD, given that subsampling should reduce gradient variance in non-private SGD but the effect of subsampling rate on DP noise variance under Poisson subsampling is unclear.
Approach
Decomposes DP-SGD gradient variance into subsampling-induced and effective DP noise parts; shows that as T goes to infinity the subsampled Gaussian mechanism approaches a Gaussian mechanism with sigma(q,T) approximately q*sigma(1,T), making effective noise variance invariant to q, while the subsampling variance decreases with q.
Key results
- Proves sigma(q,T)/(q sigma(1,T)) -> 1 as T grows, so effective DP noise variance is asymptotically invariant to subsampling rate while subsampling-induced variance decreases with q.
- For T=1, shows sigma(q)/q is decreasing in q whenever a sufficient condition a<b holds; this condition is verified numerically for delta=1e-5 over a broad grid, not proven analytically.
- Empirically, the asymptotic relation sigma_eff approaches sigma(1,T) quickly for small epsilon, and outside the asymptotic regime sigma_eff decreases further with larger q.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase the subsampling rate q (use a larger batch) | Poisson subsampled DP-SGD in the infinite-iteration limit · Poisson subsampled DP-SGD, T→∞ | total gradient variance | Helped |
| Increase the subsampling rate q | Poisson subsampled Gaussian mechanism · Poisson subsampled Gaussian mechanism, T→∞ | effective noise variance | No clear effect |
| Increase the subsampling rate q (use a larger batch) | Poisson subsampled DP-SGD · Poisson subsampled DP-SGD | subsampling-induced gradient variance | Helped |
| Increase the subsampling rate q | Poisson subsampled Gaussian mechanism · Poisson subsampled Gaussian mechanism, finite T | effective noise standard deviation | Helped |
| Increase the subsampling rate q | Poisson subsampled Gaussian mechanism · Poisson subsampled Gaussian mechanism, T=1 and a < b | effective noise standard deviation | Helped |
| Use a larger subsampling rate q | Poisson subsampled Gaussian mechanism · T=1, numerically evaluated parameter range with δ=10^-5 | effective noise variance | Helped |
| Use smaller epsilon values | Poisson subsampled Gaussian mechanism · Composed mechanism, varying T | convergence to the asymptotic effective-noise regime | Helped |
| Use smaller subsampling rates q | Poisson subsampled Gaussian mechanism · Composed mechanism, finite T | effective DP-induced variance | Hurt |
| Use a larger batch size | DP-SGD convergence bound · Non-asymptotic regime | convergence-rate constant | Helped |
| Use a larger batch size | DP-SGD · Asymptotic regime | convergence rate | No clear effect |
| Use a larger subsampling rate (less subsampling) | Poisson subsampled DP-SGD · Privacy-utility trade-off | utility | Helped |
Surprising findings
- With a single iteration (T=1), smaller subsampling rates can incur a proportionally larger effective noise variance, so subsampling can be harmful in that regime.
Limitations
- The T=1 monotonicity result relies on a conjecture (a<b) verified only numerically, not proven.
- Finite-T behaviour between T=1 and the asymptotic regime is not theoretically characterised.
- Analysis is of privacy accounting and gradient variance only, not of end-to-end model utility or convergence.
Experimental setup
Metrics: effective noise standard deviation sigma/q total gradient variance epsilon-delta privacy bounds
Builds on: DP-SGD privacy loss random variable accounting dominating pairs PLD accountant
Closest papers by meaning
- Differentially Private Stochastic Gradient Descent with Fixed-Size Minibatches: Tighter RDP Guarantees with or without Replacement (NeurIPS 2024 · similarity 0.91)
- On the Generalization Benefit of Noise in Stochastic Gradient Descent (ICML 2020 · similarity 0.89)
- On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima (ICLR 2017 · similarity 0.88)
- Disentangling the Mechanisms Behind Implicit Regularization in SGD (ICLR 2023 · similarity 0.88)
- Special Properties of Gradient Descent with Large Learning Rates (ICML 2023 · similarity 0.88)
- Scalable DP-SGD: Shuffling vs. Poisson Subsampling (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.