AI Paper Atlas

Research map / Federated learning and privacy / Differential privacy

Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergences

Borja Balle, Gilles Barthe, Marco Gaboardi

NeurIPS 2018 · Federated learning and privacy › Differential privacy · approach: Private data analysis frameworks · 154 citations (OpenAlex)

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 changedWhereMeasuredEffect
Apply Poisson subsampling with rate γA mechanism private under remove/add-one adjacency · Poisson subsampling, remove/add-oneprivacy profile bound: δ_{M'}(ε') ≤ γ δ_M(ε), where ε' = log(1 + γ (e^ε-1))Improved
Sample m records uniformly without replacementA mechanism private under substitute-one adjacency · Sampling without replacement, substitute-oneprivacy profile bound: δ_{M'}(ε') ≤ (m/n) δ_M(ε), where ε' = log(1 + (m/n)(e^ε-1))Improved
Sample m records with replacement and account for group-privacy profilesA mechanism private under substitute-one adjacency · Sampling with replacement, substitute-oneprivacy 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 adjacencyA mechanism with substitute-one group-privacy profiles · Sampling with replacement, remove/add-oneprivacy 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 adjacencyA mechanism private under substitute-one adjacency · Poisson subsampling, substitute-oneprivacy profile bound: δ_{M'}(ε') ≤ γ β δ_M(ε) + γ (1 - β) (∑_{k=1}^{n-1} γ̃_k δ_M(ε_k) + γ̃_n)Improved
Use randomized membership to attain the general subsampling boundNatural subsampling mechanisms · Randomized membership mechanismprivacy profile: δ_{M_{v,p}^S}(ε') = η ψ_p(ε)Improved
Analyze Poisson subsampling under substitute-one adjacency using the standard distance-compatible coupling methodThe general coupling-based amplification analysis · Poisson subsampling, substitute-oneavailability of a distance-compatible couplingHurt

Closest papers by meaning

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.

Open scime draft

Get the next scime Dispatch and a monthly field update

Free. We send a confirmation link first; every email has a one-click unsubscribe. Privacy