Research map / Federated learning and privacy / Differential privacy
Unified Mechanism-Specific Amplification by Subsampling and Group Privacy Amplification
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.
Proposes a unified optimal-transport framework for mechanism-specific amplification by subsampling covering ADP, RDP and dominating pairs, and applies it to tight group privacy amplification.
Problem
Existing subsampling amplification guarantees are mechanism-agnostic, do not extend cleanly to privacy accountants (RDP, dominating pairs), and do not jointly handle group privacy under subsampling.
Approach
Bound divergences of subsampled mechanism mixtures via optimal transport between conditional subsampling distributions (conditioned on events such as number of inserted/removed elements), with cost given by worst-case base-mechanism divergences under batch-distance constraints; this yields mechanism-specific bounds that subsume prior mechanism-agnostic ones.
Key results
- Mechanism-specific group privacy bounds are identical to mechanism-agnostic ones for group size 1 but stronger for group sizes K>=2 (e.g., Laplace mechanisms).
- With PLD accounting, group size 16 and delta=1e-6, the post-hoc analysis allows fewer than 100 DP-SGD iterations while the tight analysis allows over 1000 iterations (sigma=5, r=1e-3, eps=2).
- On MNIST with group size 2 at eps=8, delta=1e-5, post-hoc analysis needs under 200 iterations and yields 79.6% validation accuracy, versus 91.2% for the mechanism-specific analysis.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Analyze subsampling and group privacy jointly instead of applying group privacy post hoc | DP-SGD on a 2-layer CNN · MNIST validation | accuracy: 79.6% -> 91.2% | Helped |
| Use mechanism-specific rather than mechanism-agnostic bounds | Laplace mechanisms under Poisson subsampling · Group privacy, group size K >= 2 | privacy guarantee | Helped |
| Use mechanism-specific rather than mechanism-agnostic bounds | Randomized response under subsampling without replacement · RDP | rho | Helped |
| Use mechanism-specific rather than mechanism-agnostic bounds | Randomized response under Poisson subsampling · Group privacy | privacy guarantee | No clear effect |
| Analyze subsampling and group privacy jointly instead of applying group privacy post hoc | Gaussian mechanisms under Poisson subsampling · Single-iteration group privacy | privacy guarantee | Helped |
| Analyze group privacy and subsampling jointly instead of post hoc | Subsampled mechanisms under composition · PLD accounting, group size 16, delta=10^-6 | training iterations: less than 100 -> over 1000 | Helped |
| Use mechanism-specific rather than mechanism-agnostic bounds | Gaussian mechanisms under subsampling with replacement · Single-element substitutions, sigma=1, N=100, q=8, epsilon >= 2 | privacy profile: more than an order of magnitude smaller | Helped |
| Use optimal transport without conditioning instead of the conditioned approach | Gaussian mechanism under sampling without replacement · Group privacy, q / L in {0.01, 0.001} | privacy guarantee | Hurt |
| Use optimal transport without conditioning instead of the conditioned approach | Gaussian mechanism under sampling without replacement · Group privacy, q / L=0.1 and alpha between 10^1 and 10^2 | privacy guarantee | Helped |
| Use optimal transport without conditioning instead of the conditioned approach | Gaussian mechanism with singleton batches · Sampling without replacement, q=1, large alpha | privacy guarantee | Helped |
| Use mechanism-specific rather than mechanism-agnostic bounds | Gaussian and Laplace mechanisms under Poisson subsampling · Group privacy, larger group sizes | privacy guarantee | Helped |
| Use mechanism-specific rather than mechanism-agnostic bounds | Gaussian mechanism under Poisson subsampling · Group privacy RDP | rho | Helped |
Surprising findings
- Mechanism-agnostic subsampling guarantees are strictly looser than mechanism-specific ones even for group size 1, e.g., for subsampling with replacement.
- Post-hoc group privacy bounds converge to the tight joint bound for very private mechanisms and small subsampling rates.
Limitations
- Conditioning on a finite set of events may be too restrictive for continuous batch spaces.
- An automated procedure for selecting events is not provided; the number of modified elements is used manually.
- Some bounds (e.g., subsampling with replacement) are not tight due to distance-constraint relaxations.
Experimental setup
Datasets: MNIST
Benchmarks: analytic privacy curves for Gaussian, Laplace, randomized response mechanisms MNIST DP-SGD validation accuracy
Metrics: epsilon-delta privacy profile RDP rho(alpha) delta after composition (PLD accounting) validation accuracy
Baselines: mechanism-agnostic subsampling bounds (Balle et al. 2018 / Steinke-style framewo post-hoc group privacy best known RDP subsampling bound for randomized response subsampling without replacement RDP bound
Builds on: Balle et al. subsampling amplification framework Rényi differential privacy dominating pairs group privacy property DP-SGD
Closest papers by meaning
- Privacy Amplification for Matrix Mechanisms (ICLR 2024 · similarity 0.91)
- Sampling-Free Privacy Accounting for Matrix Mechanisms under Random Allocation (NeurIPS 2026 · similarity 0.90)
- Near-Exact Privacy Amplification for Matrix Mechanisms (ICLR 2025 · similarity 0.89)
- Beyond the Calibration Point: Mechanism Comparison in Differential Privacy (ICML 2024 · similarity 0.88)
- Privacy amplification by random allocation (NeurIPS 2025 · similarity 0.88)
- Privacy Amplification Persists under Unlimited Synthetic Data Release (NeurIPS 2026 · similarity 0.88)
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.