Poisson Sampling

In Poisson sampling, each example in a dataset is independently included in a batch with a fixed probability q. This contrasts with uniform random shuffling, where batch membership is correlated. The independence of the coin flips is the critical property that enables tight privacy accounting. A batch is formed by iterating over the entire dataset and accepting each record with probability q, resulting in variable batch sizes with an expected size of qN.

The core value of Poisson sampling is privacy amplification. A mechanism that is (ε, δ)-differentially private becomes significantly more private when applied to a random subset. Specifically, applying a Gaussian mechanism to a Poisson-sampled batch yields an amplified privacy guarantee of roughly O(qε, qδ). This means an adversary is uncertain whether a specific record's influence came from its inclusion in the batch or from the random noise, as the record might not have been sampled at all.

Modern privacy accountants like Rényi Differential Privacy (RDP) and Gaussian Differential Privacy (GDP) are essential for Poisson sampling. They provide tight, closed-form expressions for the privacy loss of a subsampled Gaussian mechanism. Unlike basic composition theorems, these frameworks precisely track the moment accountant's bounds, preventing overestimation of the privacy budget (ε). This allows for more training iterations under a fixed privacy spend.

Unlike fixed-size batching, Poisson sampling produces variable batch sizes following a binomial distribution. This variance is a feature, not a bug, as it adds another layer of uncertainty for an adversary. However, it requires the DP-SGD implementation to handle dynamic tensor shapes. The expected batch size qN is the primary tuning knob, balancing privacy amplification (lower q) against training stability and convergence speed (higher q).

Standard SGD with uniform random shuffling (sampling without replacement) creates dependent batches where the presence of one example excludes another. This correlation complicates privacy analysis and yields looser bounds. Poisson sampling (sampling with replacement) ensures complete independence between all inclusion events, which is the mathematical property that unlocks the tightest privacy amplification theorems and is the standard for state-of-the-art DP-SGD implementations.

The combination of Poisson sampling and Gaussian noise addition is formally known as the Subsampled Gaussian Mechanism. It is the foundational building block of DP-SGD. The process follows a strict sequence:

• Step 1: Sample a batch using independent Bernoulli trials with probability q.
• Step 2: Compute per-sample gradients for the sampled batch.
• Step 3: Clip each gradient to an L2 norm bound C.
• Step 4: Sum the clipped gradients and add Gaussian noise with scale σC. This sequence provides the formal (ε, δ) guarantee.

The core phenomenon that makes Poisson sampling powerful. When a differentially private mechanism is applied to a random subset of the data rather than the full dataset, the privacy guarantee is amplified—the effective epsilon becomes significantly smaller. This occurs because an adversary cannot be certain whether a specific record's information appeared in the output, as the record may not have been sampled at all. The amplification factor is approximately proportional to the sampling rate q, enabling much stronger privacy for the same noise level.

The formal name for the privacy analysis of applying Gaussian noise to a randomly sampled batch. In DP-SGD, Poisson sampling selects each example with probability q = B/N (batch size over dataset size), and Gaussian noise is added to the aggregated gradient. The privacy guarantee is computed by analyzing the worst-case privacy loss across all possible neighboring datasets under this subsampled noise injection. Tight accounting for this mechanism is essential for accurate privacy budget tracking.

A relaxation of pure differential privacy based on Rényi divergence that provides tight composition bounds for iterative algorithms. RDP is commonly used to track privacy loss in DP-SGD with Poisson sampling because it handles the subsampled Gaussian mechanism elegantly. The privacy accountant computes the RDP guarantee at each order alpha, then converts to a standard (ε, δ)-DP bound at the end of training.

An alternative amplification approach where a trusted shuffler randomly permutes user submissions before the aggregator processes them. Shuffling provides privacy amplification comparable to subsampling: if each user applies local differential privacy with epsilon ε₀, the shuffler amplifies the total guarantee to approximately O(ε₀/√n). This model bridges the gap between local and central DP, and can be combined with Poisson sampling for layered amplification.