Privacy Amplification by Subsampling

In each training step, a random subset of examples is drawn from the full dataset via a Poisson sampling or uniform sampling without replacement process. Because an adversary cannot determine if a specific record was included in the sampled batch or simply omitted by chance, the uncertainty inherently masks individual contributions. This probabilistic exclusion provides a privacy amplification effect, reducing the effective epsilon (ε) of the overall mechanism.

The privacy amplification effect is formally quantified by amplification by subsampling theorems. For a mechanism with privacy guarantee (ε, δ), applying a sampling rate q before the mechanism tightens the overall guarantee to approximately (O(qε), qδ). Key properties include:

• Stronger amplification with lower sampling probabilities (smaller q)
• Tight composition with Rényi Differential Privacy (RDP) accounting
• Optimal rates achieved via Poisson subsampling over fixed-size batches

Two dominant subsampling strategies yield different amplification profiles:

• Poisson Subsampling: Each data point is independently included with probability q. This provides the strongest theoretical amplification but results in variable batch sizes.
• Uniform Subsampling: A fixed-size batch of m examples is drawn uniformly from a dataset of size N. This guarantees consistent compute loads but yields slightly weaker amplification bounds. The choice depends on infrastructure constraints versus privacy budget optimization.

Subsampling amplifies the privacy guarantee of any downstream differentially private mechanism. When combined with the Gaussian mechanism in DP-SGD, the effective noise multiplier is magnified. The amplified standard deviation scales as σ_effective ≈ σ / q for small q. This means:

• A 1% sampling rate can amplify privacy by two orders of magnitude
• Less additive noise is required to achieve a target epsilon
• Model utility improves because gradient distortion is minimized

Modern privacy accountants like Rényi Differential Privacy (RDP) and privacy loss distribution (PLD) frameworks precisely track the amplified privacy expenditure across thousands of training iterations. The Moments Accountant algorithm computes tight bounds on the overall privacy loss by composing the amplified guarantees of each subsampled mechanism. This enables accurate reporting of the final (ε, δ) values after training completes.

Deploying subsampling amplification requires balancing competing objectives:

• Smaller sampling rates improve privacy but increase training time due to more iterations needed for convergence
• Larger datasets naturally enable lower sampling rates without sacrificing model quality
• Non-IID client data in federated settings complicates amplification analysis because local subsampling distributions diverge
• Adversarial knowledge of the sampling schedule can partially degrade amplification benefits if not randomized per round

The privacy amplification effect arises because an adversary cannot determine if a specific record was processed. When a random subset is sampled, the probability of inclusion is less than 1. This uncertainty masks individual contributions, providing a tighter privacy guarantee than processing the full dataset. The effective privacy loss parameter (ε) is reduced proportionally to the sampling rate (q), often achieving an ε_effective ≈ q * ε_base.

A standard method where each data point is independently included in a training batch with a fixed probability q. This is preferred over shuffling and batching because the independent coin flips enable a precise, closed-form analysis of the privacy amplification effect. It is a cornerstone of the DP-SGD (Differentially Private Stochastic Gradient Descent) algorithm.

Privacy loss accumulates over multiple training steps, but subsampling provides a non-linear benefit. The moments accountant technique tracks the precise privacy cost across iterations. By composing the amplified guarantees of each subsampled step, the total privacy budget (ε) grows much slower than linearly, enabling practical deep learning with strong formal privacy bounds.

Privacy amplification by subsampling is the primary driver of privacy in Differentially Private Stochastic Gradient Descent. The process works as follows:

• Subsampling: Select a random mini-batch with probability q.
• Gradient Clipping: Bound the influence of each example in the batch.
• Noise Addition: Add calibrated Gaussian noise to the aggregated gradient. The subsampling step amplifies the privacy guarantee of the subsequent noise injection.

Subsampling provides an average-case privacy amplification. While the worst-case guarantee over all possible datasets remains bounded by the base mechanism, the expected privacy loss for a randomly selected dataset is significantly lower. This distinction is crucial for interpreting the practical security of a deployed system against adversaries with partial background knowledge.

The sampling rate q directly controls the privacy-utility trade-off:

• Lower q (e.g., 0.001): Stronger amplification, lower ε, but slower model convergence due to fewer data points per step.
• Higher q (e.g., 0.1): Faster convergence, but weaker amplification and a higher privacy cost. Optimal tuning requires balancing the total number of iterations against the per-step privacy guarantee.