Subsampling Amplification

The core theorem states that if a mechanism M is (ε, δ)-differentially private on a fixed dataset, then applying M to a random q-sampled subset of the dataset yields a mechanism that is approximately (qε, qδ)-differentially private on the full dataset. This multiplicative reduction in privacy loss parameters is the foundation of subsampling amplification. The effect is strongest when the sampling probability q is small, meaning each individual has a low probability of being included in any single training batch or iteration.

Poisson subsampling is the standard method for achieving amplification in DP-SGD. Each example is independently included in a batch with probability q = B/N, where B is the batch size and N is the total dataset size. This independence is critical for tight privacy accounting because it allows the use of Rényi Differential Privacy (RDP) composition. Unlike fixed-size shuffling, Poisson sampling creates a well-defined probabilistic distance between the output distributions on adjacent datasets, enabling precise tracking of the privacy loss random variable.

When subsampling is combined with multiple iterations of a private mechanism, a secondary amplification effect occurs. Even if each step provides a modest privacy guarantee, the composition of many subsampled steps yields a privacy loss that scales with O(q√T) rather than O(qT), where T is the number of iterations. This is due to the advanced composition theorem and is further tightened by privacy loss distribution analysis. This property makes training deep neural networks with DP-SGD feasible, as models often require thousands of iterations.

Subsampling amplification is the primary reason Differentially Private Stochastic Gradient Descent (DP-SGD) achieves meaningful privacy guarantees. In DP-SGD:

• Per-sample gradients are computed and clipped to bound sensitivity
• Gaussian noise is added to the aggregated batch gradient
• The random batch selection via Poisson subsampling amplifies the privacy guarantee Without subsampling, the noise required to achieve a target epsilon would be prohibitively large, destroying model utility. The amplification allows DP-SGD to train accurate models while maintaining ε < 10 privacy budgets.

Rényi Differential Privacy (RDP) provides a tighter analysis of subsampling amplification than standard (ε, δ)-DP composition. The RDP parameter α captures higher-order moments of the privacy loss distribution. Under Poisson subsampling, the RDP of the subsampled mechanism can be bounded using the moments accountant technique, which tracks the log of the moment-generating function. This yields significantly smaller ε values for the same noise scale compared to basic composition theorems, enabling more efficient use of the privacy budget.

Subsampling amplification is not a universal privacy panacea:

• Deterministic sampling (e.g., shuffling and partitioning) provides weaker amplification than Poisson sampling and complicates accounting
• Large sampling probabilities (q → 1) negate the amplification effect, as nearly all records are included
• Correlated data violates the independence assumption; if records are not independent, the amplification factor degrades
• Adaptive adversaries who can influence the sampling process may reduce the effective amplification
• The amplification applies to the mechanism, not the data—if the underlying mechanism has high base sensitivity, amplification may be insufficient

A specific sampling method where each data point is independently included in a batch with a fixed probability q. This is the standard approach for amplifying privacy in DP-SGD because it induces a specific privacy loss distribution that is analytically tractable.

• Produces variable-sized batches, unlike uniform shuffling
• Enables tight privacy accounting via the Moments Accountant
• The amplification factor is approximately O(q) for small q
• Example: With q=0.01, the privacy loss epsilon is roughly 100x smaller than without subsampling

A subsampling method where a fixed-size subset of m records is drawn uniformly from a dataset of n records without duplication. This provides a stronger amplification effect than Poisson sampling for the same expected batch size.

• Guarantees exact batch cardinality for vectorized computation
• Amplification is governed by the hypergeometric distribution
• Tighter privacy bounds than Poisson in the Rényi DP framework
• Commonly used in the Opacus library for PyTorch

A distributed privacy model where a trusted shuffler randomly permutes user reports before the analyzer sees them. The shuffling action amplifies local differential privacy guarantees to a central model level.

• Each user applies local DP noise (e.g., randomized response)
• The shuffler breaks the link between users and their reports
• Achieves central-model privacy without a trusted data curator
• Amplification factor scales as O(1/√n) where n is the number of users

The process of computing precise, non-overestimated privacy bounds when subsampling is applied. Naive composition theorems overestimate privacy loss; advanced accountants like Rényi DP and Privacy Loss Distribution (PLD) accounting capture the true amplification.

• Moments Accountant: Tracks moment-generating function of privacy loss
• Fourier Accountant: Uses characteristic functions for numerical composition
• Privacy Buckets: Discretizes PLD for efficient convolution-based accounting
• Reduces reported epsilon by 2-5x compared to strong composition theorems

The core building block of DP-SGD that combines random subsampling with Gaussian noise addition. The mechanism first selects a random subset of data, computes a function on that subset, then adds noise calibrated to the function's sensitivity.

• Privacy loss is characterized by the trade-off between q (sampling rate) and σ (noise multiplier)
• Dominating pairs analysis provides exact privacy profiles
• The mechanism satisfies (ε, δ)-DP with δ typically set to 1/n
• Foundation for all production differentially private ML systems