Privacy Amplification by Subsampling

At each training step, a batch of examples is drawn uniformly at random from the full dataset without replacement. A differentially private mechanism (such as DP-SGD) is then applied only to this subset. Because an adversary cannot know whether a specific record was included in the sampled batch, the effective privacy loss is reduced. Formally, if a mechanism M satisfies (ε, δ)-DP, applying M to a random subset sampled with probability q yields a mechanism satisfying approximately (q·ε, q·δ)-DP under the subsampling amplification theorem.

• Poisson sampling: Each record is independently included with probability q, providing the strongest amplification guarantees
• Uniform sampling without replacement: A fixed-size batch is drawn, yielding slightly weaker but still substantial amplification
• The amplification effect is most pronounced when the sampling rate q is small relative to the dataset size

When subsampling is applied repeatedly over T training iterations, the privacy guarantees compose according to advanced accounting methods. The Privacy Loss Distribution (PLD) approach tracks the exact distribution of privacy loss random variables, yielding significantly tighter bounds than simple linear composition. Under Rényi Differential Privacy (RDP), the subsampled Gaussian mechanism's RDP parameters compose additively across iterations, enabling precise privacy budget tracking.

• Moments Accountant: The classical method introduced with DP-SGD that computes tight bounds on the privacy loss of subsampled mechanisms
• Privacy amplification by iteration: Even without explicit subsampling, the iterative nature of SGD provides inherent privacy amplification when the dataset is accessed sequentially
• The effective epsilon after T iterations scales roughly as O(q·ε·√T) under advanced composition theorems

A related but distinct form of amplification occurs when data is shuffled before being partitioned into batches. In the shuffle model of differential privacy, each user's data is first locally randomized, then a trusted shuffler permutes all submissions before the analyzer processes them. The shuffling operation amplifies the local privacy guarantee: if each user applies an ε₀-local randomizer, the shuffled output satisfies approximately O(e^{ε₀}·√(log(1/δ)/n))-DP centrally.

• Shuffle amplification bridges the gap between local DP (weak per-user guarantees) and central DP (strong aggregate guarantees)
• Requires an honest-but-curious shuffler that does not collude with the analyzer
• Enables strong privacy for federated learning without trusting a central aggregator with raw data

Modern privacy accounting for subsampled mechanisms relies on privacy loss distributions (PLDs) rather than moment-based approximations. The PLD of a subsampled Gaussian mechanism is computed by convolving the PLD of the base mechanism with the sampling distribution. This approach, implemented in libraries like Google's DP Accounting and Opacus, yields numerically tight (ε, δ) guarantees by directly computing the tail probabilities of the composed privacy loss.

• Fourier accountants: Leverage fast Fourier transforms to efficiently convolve PLDs across many iterations
• Privacy loss random variable: A single scalar that captures the entire privacy loss incurred on a specific outcome
• The tightness of PLD-based accounting can reduce the reported epsilon by 2-5× compared to the Moments Accountant for the same actual privacy protection

Privacy amplification by subsampling creates a utility-privacy tradeoff governed by the sampling rate q. Smaller sampling rates provide stronger amplification but require more iterations to converge, increasing the total computational cost. In practice, typical DP-SGD training uses sampling rates of 0.1% to 1% (e.g., batch sizes of 256-1024 on datasets of 50k-1M examples). The amplified privacy guarantee allows models to achieve useful accuracy at meaningful epsilon values (ε = 1-8) that would be impossible without subsampling.

• Large batch training: Using larger batches reduces the effective sampling rate, improving amplification at the cost of increased memory and compute
• Epoch accounting: The number of passes over the dataset interacts with the sampling rate to determine total privacy expenditure
• Empirical studies show that subsampling amplification is the single most important factor enabling practical deep learning with differential privacy

In federated learning, subsampling occurs at two levels: client-level and example-level. Client-level subsampling randomly selects a subset of participating devices in each round, providing amplification against adversaries who might compromise the central server. Example-level subsampling within each client further amplifies the guarantee. The combination of both levels, analyzed through federated privacy accounting, yields end-to-end differential privacy guarantees that protect individual user contributions across the entire training process.

• Cross-device FL: Millions of devices with small local datasets, where client sampling is the dominant amplification mechanism
• Cross-silo FL: Tens to hundreds of organizations, where example-level subsampling within each silo provides the primary amplification
• The DP-FedAvg algorithm combines federated averaging with subsampled Gaussian mechanisms at both levels

The standard method for achieving amplification in DP-SGD. Unlike shuffling and partitioning data into fixed batches, Poisson subsampling flips an independent coin for each data point to determine its inclusion in a mini-batch. This is critical because:

• It creates a non-zero probability that any single record is excluded from a training step.
• This uncertainty of inclusion is the mathematical source of the privacy amplification lemma.
• It provides tighter privacy bounds than uniform sampling with replacement.

A formal theorem stating that if a mechanism M is (ε, δ)-differentially private, applying M to a random subset of the data obtained via Poisson sampling with probability q yields a mechanism that is (O(qε), qδ)-DP.

• The privacy loss scales multiplicatively with the sampling rate q.
• A smaller q (e.g., 0.01) drastically reduces the per-step epsilon.
• This lemma is the bridge between the base mechanism's guarantee and the amplified guarantee enjoyed by the overall training procedure.

Rényi Differential Privacy (RDP) is the standard accountant for tracking the composed privacy loss of a subsampled mechanism.

• RDP provides tight composition bounds for Gaussian mechanisms under Poisson subsampling.
• It computes the Rényi divergence of the subsampled Gaussian mechanism analytically.
• The final (ε, δ)-DP guarantee is obtained by converting the accumulated RDP budget back to standard DP.
• This method is significantly more accurate than the basic strong composition theorem, allowing for more training iterations under a fixed budget.

Subsampling directly undermines membership inference attacks (MIAs) by introducing deniability.

• An attacker cannot be certain if a high-confidence prediction is due to memorization or because the target record was simply not in the sampled batch.
• Combined with gradient clipping and noise, subsampling ensures that even if a record is included, its influence is bounded and obscured.
• This creates a stochastic privacy barrier that reduces the attack's true positive rate, forcing it toward random guessing.