Privacy Amplification by Subsampling

When a differentially private mechanism is applied to a random subset of the data rather than the full dataset, the effective privacy loss parameter (ε) is reduced. This occurs because an adversary cannot be certain whether a specific record was included in the subset that produced the observed output. The amplification factor is approximately proportional to the sampling probability q — smaller sampling rates yield stronger amplification.

• For a mechanism with guarantee ε, applying it to a q-sampled subset yields an effective guarantee of approximately O(qε)
• This effect is the primary reason DP-SGD achieves practical privacy guarantees
• The amplification is strongest when sampling is uniform and independent

The most common subsampling method in privacy-preserving machine learning is Poisson subsampling, where each record is independently included in the batch with a fixed probability q. This independence is critical for tight privacy accounting because it allows the use of the moments accountant to precisely track the privacy loss random variable.

• Each record participates in a batch with probability q, independent of all other records
• Enables the application of Rényi Differential Privacy (RDP) composition
• Provides tighter bounds than deterministic shuffling or fixed-size sampling
• The independence property is essential for the amplification by subsampling theorem

Differentially Private Stochastic Gradient Descent (DP-SGD) relies fundamentally on subsampling amplification. In each training step, a mini-batch is sampled from the full dataset, per-example gradients are clipped, and Gaussian noise is added. The privacy guarantee applies to the sampled batch, but the amplification effect ensures the guarantee extends to the full dataset with a much smaller ε.

• Without subsampling, DP-SGD would require prohibitively large noise to achieve reasonable privacy
• The moments accountant computes the precise amplified privacy loss across thousands of training steps
• Typical settings use batch sizes of 256–512 with sampling probabilities of 0.01–0.001
• The composition of many amplified steps yields the final (ε, δ) guarantee

In the shuffle model of differential privacy, a trusted shuffler randomly permutes locally randomized reports from users before they reach the analyzer. This shuffling operation provides an anonymity set that amplifies the local privacy guarantee. Each user's report is hidden among the shuffled batch, effectively creating a subsampling-like amplification effect.

• A local ε₀ guarantee can be amplified to a central ε ≈ O(ε₀/√n) guarantee after shuffling
• The amplification is proportional to the square root of the number of users
• Enables strong central privacy guarantees without a trusted central server
• Used in Prochlo and other distributed privacy architectures

A related but distinct phenomenon is privacy amplification by iteration, where the sequential nature of iterative algorithms like gradient descent inherently provides privacy protection. Each iteration only accesses a subset of the data through the gradient computation, and the noise added in each step compounds the uncertainty about any single record's influence.

• First formalized by Feldman et al. as an alternative to subsampling amplification
• Provides privacy guarantees even for full-batch gradient descent with no subsampling
• The amplification grows with the number of iterations, not the sampling rate
• Enables privacy analysis for algorithms that process the entire dataset each step

The true power of subsampling amplification emerges when combined with advanced composition theorems. The moments accountant and Rényi DP frameworks track the privacy loss distribution across thousands of amplified steps, yielding a final (ε, δ) guarantee that is significantly tighter than naive composition would suggest.

• Rényi Differential Privacy (RDP) provides composition bounds that are tight for Gaussian mechanisms under subsampling
• Privacy loss distributions enable numerical composition via Fourier accounting for exact bounds
• The combination of amplification + tight composition is what makes training deep neural networks with differential privacy feasible
• Modern privacy accounting libraries like Opacus and TF Privacy implement these techniques

The standard method for achieving privacy amplification in DP-SGD. Each example is independently included in a batch with a fixed probability q. This random process ensures that the privacy loss random variable is dominated by a mixture of distributions, providing a tight and analyzable amplification factor. The Rényi Differential Privacy (RDP) accountant specifically leverages this property to compute the precise privacy cost of each training step.

An alternative subsampling method where a fixed-size subset is drawn uniformly at random from the dataset. While conceptually simpler, its privacy amplification analysis is more complex than Poisson sampling. The privacy loss distribution under this scheme requires careful handling of negative dependencies, often leading to slightly looser privacy bounds compared to the independent inclusion model of Poisson subsampling.

A distinct but related phenomenon where the iterative nature of algorithms like Stochastic Gradient Descent itself provides a privacy amplification effect, independent of subsampling. The sequential composition of contractive (noisy) updates makes it harder for an adversary to infer the presence of a single data point, as the influence of any one record is progressively obscured by subsequent noisy steps.

A distributed privacy amplification effect achieved by inserting a trusted shuffler between users and the analyzer. Each user applies a local randomizer (e.g., Randomized Response), and the shuffler randomly permutes all reports. This anonymity set amplifies the local privacy guarantee into a stronger central differential privacy guarantee, effectively decoupling the noise generation from the final aggregation.

A technique for federated settings where clients only participate in a training round if they 'check in' and are selected. This self-sampling or server-directed selection process creates uncertainty about whether a specific client's data was used. Combined with secure aggregation, this amplifies the privacy guarantee for the entire user-level contribution, not just a single record.

The practical utility of privacy amplification is realized through advanced composition theorems. Rényi Differential Privacy (RDP) and Gaussian Differential Privacy (GDP) provide tight bounds on the total privacy loss when subsampling is applied repeatedly. These frameworks convert the per-step amplified privacy loss into a meaningful global privacy budget (ε, δ), enabling the training of deep learning models with non-vacuous guarantees.