Research map / Federated learning and privacy / Differential privacy
Differentially Private Stochastic Gradient Descent with Fixed-Size Minibatches: Tighter RDP Guarantees with or without Replacement
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.
Derives a holistic RDP accountant for DP-SGD with fixed-size minibatches, without replacement (add/remove and replace-one adjacency) and with replacement, via a Taylor expansion of the subsampled Gaussian divergence.
Problem
Existing computable RDP accountants for DP-SGD with fixed-size subsampling are loose or do not cover both add/remove and replace-one adjacency, and fixed-size with replacement lacks non-asymptotic analysis.
Approach
Decompose fixed-size without-replacement subsampling into Gaussian mixtures via an auxiliary-variable construction, then bound the resulting Rényi divergence with a Taylor expansion having an explicit computable remainder; extend to with-replacement with matching upper and lower bounds.
Key results
- FSwoR replace-one RDP bound improves on the best prior computable bound (Wang et al.) by a factor of about 4 at leading order in q and 1/sigma^2.
- On CIFAR10 with 250 epochs, FSwoR-RDP reaches 63.87% average accuracy vs 61.57% for Opacus Poisson subsampled RDP, with tighter epsilon than Wang et al.
- FSwoR under replace-one adjacency matches Poisson subsampling privacy to leading order in q; fixed-size memory usage stays constant (14,826 MB) while Poisson varies from 7,984 to 23,280 MB.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed FSwoR-RDP accountant instead of the best current computable bound | DP-SGD under replace-one adjacency · Fixed-size minibatches without replacement | RDP bound tightness: by a factor of 4 | Helped |
| Use fixed-size without-replacement subsampling instead of Poisson subsampling | DP-SGD with the CNN · CIFAR10, 250 epochs | test accuracy: 61.57% -> 63.87% | Helped |
| Use fixed-size subsampling instead of Poisson subsampling | DP-SGD with the CNN · CIFAR10, 100 epochs | GPU memory usage: 14,826 MB vs. 7,984 MB to 23,280 MB | Helped |
| Use fixed-size without-replacement subsampling instead of Poisson subsampling | DP-SGD under replace-one adjacency · Leading-order privacy comparison | RDP privacy guarantee | No clear effect |
| Use fixed-size subsampling instead of Poisson subsampling | DP-SGD gradient estimator · Gradient variance comparison | gradient variance | Helped |
| Use fixed-size subsampling with replacement instead of without replacement | DP-SGD gradient estimator · Gradient variance comparison | gradient variance | Hurt |
| Use Poisson subsampling instead of fixed-size subsampling | DP-SGD under add/remove adjacency · Leading-order privacy comparison | RDP privacy guarantee: approximately a factor of 2 | Helped |
| Use Poisson subsampling instead of FSwoR | DP-SGD under replace-one adjacency · Higher-order privacy comparison | privacy guarantee | Helped |
Surprising findings
- Poisson subsampling retains a slight privacy advantage over FSwoR under replace-one adjacency once higher-order terms are included, despite equal leading-order privacy.
- Fixed-size with replacement exhibits a phase transition in RDP lower bounds as batch size grows, so it needs much smaller minibatches than FSwoR to keep privacy.
Limitations
- Replace-one bounds require higher Taylor order m (often m=4) and are more complex formulas.
- Empirical evaluation limited to a small CNN on CIFAR10 with a single setting of noise and batch size.
- FSwR is only bounded non-asymptotically with upper and lower bounds that are not fully tight.
Experimental setup
Datasets: CIFAR10 CIFAR100
Benchmarks: CIFAR10
Metrics: epsilon (privacy guarantee) at fixed delta RDP epsilon as function of alpha test accuracy gradient variance GPU memory usage
Baselines: Wang et al. (2019) fixed-size RDP bound Poisson subsampled RDP in Opacus Opacus RDP accountant f-DP accountant PRV accountant
Builds on: DP-SGD subsampled Gaussian mechanism RDP (Mironov et al.) Wang et al. subsampling RDP for fixed-size sampling Opacus
Closest papers by meaning
- Scalable DP-SGD: Shuffling vs. Poisson Subsampling (NeurIPS 2024 · similarity 0.92)
- Subsampling is not Magic: Why Large Batch Sizes Work for Differentially Private Stochastic Optimisation (ICML 2024 · similarity 0.91)
- Shifted Interpolation for Differential Privacy (ICML 2024 · similarity 0.90)
- The importance of feature preprocessing for differentially private linear optimization (ICLR 2024 · similarity 0.89)
- Differentially Private SGD Without Clipping Bias: An Error-Feedback Approach (ICLR 2024 · similarity 0.89)
- How Private are DP-SGD Implementations? (ICML 2024 · similarity 0.89)
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.