Privacy Amplification by Subsampling

The privacy amplification effect arises because an adversary cannot know if a specific record was included in the analysis. If a record is not sampled, it enjoys perfect privacy. If it is sampled, it receives the base privacy guarantee. The overall guarantee is a probabilistic combination of these two states, resulting in a multiplicative reduction in the privacy loss parameter ε.

• The effective ε scales roughly by the sampling rate q (where q < 1)
• A smaller sample means a stronger privacy amplification
• This is the primary reason DP-SGD achieves practical privacy in deep learning

For a mechanism M with base guarantee ε, applying it to a random q-fraction sample amplifies the guarantee to approximately O(qε) for small ε. This is formalized through the amplification by subsampling theorem.

• The privacy loss random variable is bounded by considering two cases: the differing record is sampled or not
• In Poisson subsampling, each record is included independently with probability q, yielding a tight bound of log(1 + q(e^ε - 1))
• In sampling without replacement, a fixed-size subset is drawn uniformly at random, producing a slightly different but comparable amplification

Two dominant subsampling strategies are used in practice, each with distinct analytical properties:

• Poisson Subsampling: Each data point is independently included with probability q. This yields the cleanest privacy amplification analysis and is the standard in DP-SGD with the Moments Accountant
• Uniform Subsampling (Without Replacement): A fixed batch of size m is drawn from a dataset of size n. The sampling rate is q = m/n. This is the natural batching strategy in SGD but requires more careful privacy accounting
• Poisson subsampling provides a slightly tighter privacy bound in most analyses

Privacy amplification by subsampling is the critical ingredient that makes Differentially Private Stochastic Gradient Descent (DP-SGD) practical for deep learning. Without it, the privacy cost of training would be prohibitive.

• Each training step operates on a random mini-batch (the subsample)
• Gradients are clipped to bound sensitivity, then Gaussian noise is added
• The subsampling amplifies the privacy guarantee of each step, allowing thousands of training iterations within a reasonable privacy budget
• The Moments Accountant tracks the cumulative privacy loss across all subsampled steps

Early analyses of privacy amplification used loose composition theorems. Modern privacy accountants provide significantly tighter bounds:

• The Moments Accountant (Abadi et al., 2016) tracks higher-order moments of the privacy loss random variable, exploiting the subsampling structure
• Rényi Differential Privacy (RDP) provides a natural framework for analyzing subsampled mechanisms, converting to (ε, δ)-DP via tight conversion lemmas
• Privacy Loss Distributions (PLD) and Fourier Accountant offer numerically precise accounting by directly computing the distribution of the privacy loss
• These advances can reduce the reported ε by 2-5x compared to naive composition

While powerful, privacy amplification by subsampling has important limitations:

• The amplification benefit diminishes as the sampling rate q increases; training with large batches reduces the privacy advantage
• Amplification assumes the subsampling is truly random and hidden from the adversary; deterministic or predictable sampling breaks the guarantee
• The analysis typically assumes Poisson subsampling, but practical implementations often use shuffling and fixed batches, requiring careful accounting
• At very small ε values, the δ parameter (failure probability) can become the dominant privacy concern
• Amplification does not protect against membership inference if the adversary has strong prior knowledge about the sampling distribution