Source-linked AI summary
Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergences
Borja Balle, Gilles Barthe, Marco Gaboardi
TL;DR
Privacy amplification by subsampling had been analyzed mainly with strategy-specific tools, despite its importance for private data analysis. The paper develops a general divergence- and coupling-based method with privacy profiles and advanced joint convexity, obtaining prior, new, and tight amplification results across settings. It also identifies a boundary: the method does not extend to Poisson subsampling under substitution relations, although a more cumbersome bound remains possible.
Problem
Existing privacy-amplification analyses are specific to particular subsampling forms, while understanding amplification across sampling techniques and neighbouring relations remains important for private algorithms.
Method
The paper analyzes subsampled mechanisms through α-divergences, privacy profiles, probabilistic couplings, advanced joint convexity, and group-privacy profiles.
Results
The method recovers existing results, derives novel amplification bounds, and in most cases provides optimal constants proved tight by a generic lower bound.
Takeaways & Limitations
A single toolkit can analyze privacy amplification across many dataset representations, neighbouring relations, and subsampling types, while supporting lower-bound analyses.
Takeaways & Limitations
The method cannot be extended to Poisson subsampling under the substitution relation because distance-compatible couplings are unavailable; a more cumbersome bound is still possible.
Abstract
from arXiv · showhide
Differential privacy comes equipped with multiple analytical tools for the design of private data analyses. One important tool is the so-called "privacy amplification by subsampling" principle, which ensures that a differentially private mechanism run on a random subsample of a population provides higher privacy guarantees than when run on the entire population. Several instances of this principle have been studied for different random subsampling methods, each with an ad-hoc analysis. In this paper we present a general method that recovers and improves prior analyses, yields lower bounds and derives new instances of privacy amplification by subsampling. Our method leverages a characterization of differential privacy as a divergence which emerged in the program verification community. Furthermore, it introduces new tools, including advanced joint convexity and privacy profiles, which might be of independent interest.
1 Introduction
Subsampling is important for differentially private mechanism design, especially in machine learning and black-box deployments. The paper addresses limitations in existing, strategy-specific analyses by developing a general framework for tight privacy amplification results.
- Subsampling can amplify the privacy guarantees of a differentially private mechanism by applying it to a small random subset of records.
- Sampling operations in stochastic optimization and Bayesian inference make privacy amplification results relevant to differentially private machine learning.
- Black-box subsampling provides a practical way to obtain privacy amplification when privacy parameters are hard-coded and cannot be modified by users.
- Existing amplification tools generally target specific subsampling forms and provide cumbersome proofs without information about bound tightness.
- The paper develops a general framework for tight amplification analyses using α-divergences, advanced joint convexity, and privacy profiles.
2 Problem Statement and Methodology Overview
The paper formalizes privacy amplification as a relation between the privacy profiles of a mechanism and its subsampled composition. Its methodology represents differential privacy with α-divergences and analyzes mixture distributions using couplings, joint convexity, and group-privacy profiles.
- A mechanism maps an input to a probability distribution over outputs, while a subsampling mechanism maps a database to a finitely supported distribution over datasets.
- Differential privacy is equivalent to bounding the α-divergence between mechanism outputs on neighbouring inputs, motivating privacy profiles and group-privacy profiles.
- The amplification problem relates the privacy profiles of M and MS, where MS applies M to a random subsample and should have better privacy parameters.
- A complete specification includes dataset representation, neighbouring relations, and the subsampling method with its parameters.
- The central analytical challenge is that subsampled outputs are mixtures whose privacy must be compared across neighbouring input datasets.
- The unified method combines divergence and privacy-profile properties with advanced joint convexity, coupling-based bounds, and group-privacy profiles to recover, extend, and tighten amplification results.
3 Tools: Couplings, Divergences and Privacy Profiles
This section develops couplings, α-divergences, and privacy profiles as the analytical tools underlying the paper’s privacy-amplification framework. It introduces advanced joint convexity and distance-compatible couplings for deriving bounds tied to mechanism and group-privacy profiles.
- Divergences: Differential privacy is characterized by bounding the α-divergence between outputs on adjacent datasets.For α=e^ε, the supremum of the divergence over adjacent inputs equals the corresponding δ guarantee.
- Couplings: Couplings relate distributions through a joint distribution with specified marginals, and maximal couplings attain the total variation distance.The maximal coupling decomposes distributions into a shared component and residual components weighted by total variation distance.
- Advanced Joint Convexity: Advanced joint convexity bounds divergence between mixtures sharing a common component, using α′ = 1 + η(α − 1) and β = α′/α.Writing α=e^ε and α′=e^ε′ yields ε′=log(1+η(e^ε−1)); direct joint convexity gives a weaker amplification bound for ε.
- Applying the Tools: Maximal-coupling decompositions of subsample distributions produce canonical mixture decompositions whose shared and residual parts can be analyzed through advanced joint convexity.The construction uses the Markov kernel of the mechanism and residual components with disjoint supports.
- Examples and Further Consequences: For Laplace output perturbation, the privacy profile recovers pure differential privacy when ε reaches the sensitivity-to-noise threshold and gives approximate-DP guarantees below it.The profile is expressed using global sensitivity Δ and noise parameter b.
- Examples and Further Consequences: Privacy profiles can characterize privacy-loss moment generating functions, while white-box group-profile analyses improve standard black-box bounds for Laplace and Gaussian mechanisms.The moment-generating-function connection applies broadly, with symmetry supplying an example condition for equal forward and reverse divergences.
- Privacy Profiles: Privacy profiles record the supremum α-divergence over adjacent datasets as a function of ε and separate parameter values satisfying differential privacy from those that do not.Group-privacy profiles extend this description to datasets at path-distance at most k.
- Distance-Compatible Coupling: Distance-compatible couplings enable optimal bounds that depend only on the input distribution and the mechanism’s group-privacy profiles.Applying the resulting theorem yields most of the paper’s concrete privacy-amplification results.
4 Privacy Amplification Bounds
The paper gives explicit privacy-amplification bounds for common subsampling methods and neighboring relations, including tight results and a new hybrid setting. It also identifies an incompatibility that prevents the coupling method from extending to Poisson subsampling under substitution.
- Poisson Subsampling: For Poisson sampling under remove/add-one, the subsampled mechanism samples each record independently with probability γ, and the paper analyzes its privacy profile.The sampling distribution is supported on subsets y⊆x with probability γ^|y|(1−γ)^(|x|−|y|).
- Sampling Without Replacement: For sampling without replacement under substitution, δM′(ε′) ≤ (m/n)δM(ε), with ε′ = log(1 + (m/n)(e^ε − 1)).This is the tight amplification bound for samples of size m from datasets of size n.
- Sampling With Replacement: For sampling with replacement under substitution, ε′ = log(1 + (1 − (1 − 1/n)^m)(e^ε − 1)), and the bound has optimal constants.When m=γn, the sampling factor 1−(1−1/n)^m is approximately γ.
- Hybrid Neighbouring Relations: The framework also analyzes hybrid neighboring relations, motivated by mechanisms restricted to fixed-size inputs such as GPU-limited mini-batches.The example studies sampling with replacement when the base mechanism uses substitution but the subsampled mechanism is evaluated under remove/add.
- Incompatible Relations: The coupling method cannot extend to Poisson subsampling under substitution because the relevant factor distributions are not distance-compatible.A more cumbersome bound remains possible without distance-compatible couplings.
5 Lower Bounds
The paper establishes tightness for many amplification bounds by constructing a randomized membership mechanism. A general lemma relates tightness to the total variation distance between subsampling distributions.
- Tightness Construction: The lower-bound construction uses a randomized membership mechanism to attain the upper bounds from the preceding section.The construction is stated for tuples and then specialized to sets and multisets.
- General Lemma: For a natural subsampling mechanism, η is the supremum total variation distance between subsampling distributions on neighboring inputs.The lemma assumes neighboring inputs differ in whether a selected record v is present.
- General Lemma: The tightness lemma uses ε′ = log(1 + η(e^ε − 1)) for every ε≥0.This gives the amplification form in terms of the subsampling distributions’ total variation distance.
- Tightness Construction: The randomized membership mechanism Mv,p attains the bounds in Theorems 8, 9, and 10 for any p and η.The result connects the general construction to the first three amplification theorems.
6 Conclusions
The paper presents a general method for reasoning about privacy amplification by subsampling, combining advanced joint convexity with privacy profiles. It applies across existing and new settings, while extensions to other privacy notions remain future work.
- Conclusions: The paper develops a general method for reasoning about privacy amplification by subsampling.This is the central conclusion of the work.
- Conclusions: The method applies to previously studied settings and to new subsampling and neighboring-relation settings.Its technical tools include advanced joint convexity and privacy profiles.
- Future Work: The paper identifies extending the tools to concentrated DP, zero-concentrated DP, Rényi DP, and truncated concentrated DP as future work.These privacy notions are proposed as directions for obtaining concrete amplification bounds.
A Proofs from Section 3
The proofs derive privacy-amplification identities and bounds by manipulating α-divergences, privacy-loss integrals, and compatible couplings. The arguments use changes of variables and coupling support properties to connect divergence terms to neighboring distances.
- Laplace Mechanism: For the Laplace mechanism, the divergence is zero when ε>∆/b because the privacy-loss difference is bounded by the sensitivity-to-noise ratio.For ε≤∆/b, the relevant integration region is (−∞,(∆−εb)/2].
- Privacy-Loss Analysis: A change of variables introduces the moment-generating function of the privacy-loss random variable into the proof.The substitution dt′ = t^(1/s)dt is used to rewrite the second integral.
- Divergence Manipulation: The proof rewrites terms that are not divergences for t∈(0,1) using a reversed α-divergence, enabling the integral to be split into two analyzable parts.This transformation replaces Dt^(1/s)(µ∥µ′) with an expression involving Dt^(−1/s)(µ′∥µ).
- Privacy-Loss Analysis: The proof obtains the desired equation through successive substitutions t′=1/t, α=t^(1/s), and α=e^ε.These substitutions connect the integral representation to the privacy parameter ε.
- Couplings: For a distance-compatible coupling, every supported pair satisfies d(y,y′)=d(y,supp(ν′)), which converts a coupling bound into the desired divergence equality.The argument first establishes a lower bound for arbitrary couplings and then uses compatibility for equality.
B Proofs from Section 4
The proofs analyze subsampled mechanisms by decomposing sampling distributions and constructing compatible couplings, then applying divergence inequalities to derive privacy-profile bounds. This framework yields bounds for multiple subsampling and neighboring-dataset settings.
- Remove/add-one neighbors: For remove/add-one neighboring datasets, the proof constructs compatible couplings by replacing differing elements or adding sampled elements, yielding δM′(ε′) ≤ ηδM(ε).The worst-case direction is identified when one dataset contains one additional element, with η = 1 − (1 − 1/n)^m for sampling without replacement.
- Subsampling without replacement: For substitution sampling without replacement, the proof decomposes distributions using maximal coupling and bounds the resulting component divergences via advanced joint convexity.The total variation weight is η = m/n, and the analysis reduces to divergences between coupled mixture components.
- Subsampling with replacement: For substitution sampling with replacement, the proof uses η = 1 − (1 − 1/n)^m and couplings that replace each differing element in sampled multisets.The construction supports compatible couplings for the shared and differing mixture components before applying the theorem’s divergence bound.
- Poisson subsampling: For Poisson subsampling, the proof manually decomposes distributions by sample size because no compatible coupling exists for one component, then applies advanced joint convexity to each size-conditioned pair.The resulting parameters include ε′ = log(1 + γ(e^ε −1)) and εk = ε + log((γ/(1−γ))(n/k −1)).
- Privacy-profile bounds: The derived bounds are summarized as privacy-profile results for subsampling mechanisms, with parameters expressed through the original mechanism’s privacy profile and related mixture weights.The theorem statements and proof conclusion connect the constructions to privacy profiles under the specified neighboring relation.
C Proofs from Section 5
The Section 5 proof represents the subsampled mechanism’s output as a two-component mixture and applies advanced joint convexity to compare neighboring datasets. Monotonicity then yields a privacy-profile bound based on the mixture weight.
- Mixture decomposition: Each subsampled output distribution is expressed as µ = (1 − θ)ν0 + θν1, because the mechanism has only two possible outputs depending on whether v belongs to the sample.Neighboring datasets produce analogous mixtures with weights θ and θ′.
- Divergence comparison: Advanced joint convexity compares neighboring mixtures and uses ε′ = log(1 + θ(e^ε −1)) with β = e^ε′/e^ε.The argument assumes without loss of generality that θ ≥ θ′.
- Tightness condition: When v is absent from the neighboring dataset, θ′ = 0 and the joint-convexity inequalities become equalities.This condition corresponds to the natural subsampling mechanism’s specific neighboring-data configuration.
- Monotonicity: Monotonicity of θ 7→ θψp(log(1 + (e^ε′ −1)/θ)) completes the bound and supports tightness analysis for the resulting privacy profile.The proof uses the increasing behavior of this function after establishing the mixture inequality.
D Plots of Privacy Profiles
Figure 1 plots privacy profiles to illustrate the paper’s privacy-profile notion and the different subsampling bounds derived in the paper.
- Figure contents: The figure contains plots of privacy profiles.The caption identifies privacy profiles as the plotted object.
- Interpretation: The plots illustrate the notion of privacy profile.The caption describes this as one purpose of the results shown.
- Interpretation: The plots also illustrate the different subsampling bounds derived in the paper.The caption identifies the bounds as another focus of the figure.