Research map / Federated learning and privacy / Differential privacy
Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergences
Borja Balle, Gilles Barthe, Marco Gaboardi
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Apply Poisson subsampling with rate γ | A mechanism private under remove/add-one adjacency · Poisson subsampling, remove/add-one | privacy profile bound: δ_{M'}(ε') ≤ γ δ_M(ε), where ε' = log(1 + γ (e^ε-1)) | Improved |
| Sample m records uniformly without replacement | A mechanism private under substitute-one adjacency · Sampling without replacement, substitute-one | privacy profile bound: δ_{M'}(ε') ≤ (m/n) δ_M(ε), where ε' = log(1 + (m/n)(e^ε-1)) | Improved |
| Sample m records with replacement and account for group-privacy profiles | A mechanism private under substitute-one adjacency · Sampling with replacement, substitute-one | privacy profile bound: δ_{M'}(ε') ≤ ∑_{k=1}^m binom(m,k) (1/n)^k (1 - 1/n)^{m-k} δ_{M,k}(ε) | Improved |
| Use with-replacement sampling under remove/add-one adjacency | A mechanism with substitute-one group-privacy profiles · Sampling with replacement, remove/add-one | privacy profile bound: sup_{x ∈ 2_n^U, x ≃_r x'} D_{e^{ε'}}(M'(x) || M'(x')) ≤ ∑_{k=1}^m binom(m,k) (1/n)^k (1 - 1/n)^{m-k} δ_{M,k}(ε) | Improved |
| Use Poisson subsampling under substitute-one adjacency | A mechanism private under substitute-one adjacency · Poisson subsampling, substitute-one | privacy profile bound: δ_{M'}(ε') ≤ γ β δ_M(ε) + γ (1 - β) (∑_{k=1}^{n-1} γ̃_k δ_M(ε_k) + γ̃_n) | Improved |
| Use randomized membership to attain the general subsampling bound | Natural subsampling mechanisms · Randomized membership mechanism | privacy profile: δ_{M_{v,p}^S}(ε') = η ψ_p(ε) | Improved |
| Analyze Poisson subsampling under substitute-one adjacency using the standard distance-compatible coupling method | The general coupling-based amplification analysis · Poisson subsampling, substitute-one | availability of a distance-compatible coupling | Hurt |
Closest papers by meaning
- Unified Mechanism-Specific Amplification by Subsampling and Group Privacy Amplification (NeurIPS 2024 · similarity 0.93)
- Privacy amplification by random allocation (NeurIPS 2025 · similarity 0.91)
- A Generalized Shuffle Framework for Privacy Amplification: Strengthening Privacy Guarantees and Enhancing Utility (AAAI 2024 · similarity 0.91)
- Privacy Amplification Persists under Unlimited Synthetic Data Release (NeurIPS 2026 · similarity 0.90)
- Leveraging Randomness in Model and Data Partitioning for Privacy Amplification (ICML 2025 · similarity 0.89)
- Sampling-Free Privacy Accounting for Matrix Mechanisms under Random Allocation (NeurIPS 2026 · 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.
