Privacy Amplification by Subsampling

The subsampled Gaussian mechanism is the workhorse of privacy amplification. It operates by first selecting a random subset of records from the dataset, then applying Gaussian noise to the query result computed on that subset. The randomness of the sampling process itself introduces uncertainty about whether any given individual's data was even included in the computation, effectively amplifying the base privacy guarantee of the noise addition step.

The method of subsampling critically impacts the privacy analysis. Poisson sampling includes each data point independently with probability q, which simplifies privacy accounting and yields tight composition bounds. Uniform sampling without replacement selects a fixed batch of size B from N records. While practically common, uniform sampling requires more complex analysis using Rényi differential privacy or privacy loss distributions to avoid loose bounds.

In iterative algorithms like DP-SGD, privacy amplification compounds across training steps. The privacy accountant tracks the cumulative privacy loss. Because each step operates on a fresh random subsample, the total privacy cost grows sublinearly with the number of iterations. This is formalized through strong composition theorems and moments accountant techniques, which provide tight bounds on the overall epsilon after T steps.

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

• Smaller q (e.g., 0.001): Stronger amplification, lower epsilon per step, but slower convergence and higher variance.
• Larger q (e.g., 0.1): Weaker amplification, higher privacy cost per step, but faster learning. The optimal q balances the total privacy budget against model accuracy, often requiring hyperparameter tuning under a fixed epsilon constraint.

Rényi Differential Privacy (RDP) provides a natural framework for analyzing subsampled mechanisms. The RDP parameters of a subsampled Gaussian mechanism compose cleanly across iterations. After T steps with sampling rate q and noise multiplier σ, the RDP order α can be converted to a standard (ε, δ)-DP guarantee. This approach avoids the looseness of basic composition and is the standard in modern DP-SGD implementations.

In cross-device federated learning, privacy amplification by subsampling is a free lunch. Because only a fraction of devices participate in each training round, the server's view of any individual user's contribution is inherently probabilistic. This means that even without adding large amounts of noise, the random participation pattern provides a baseline level of privacy, which can be further strengthened by combining with secure aggregation or local differential privacy.

The standard subsampling method in DP-SGD where each data point is independently included in a batch with a fixed probability q. This 'sampling without replacement' property is critical because it enables tight privacy amplification bounds via the subsampled Gaussian mechanism. Unlike uniform shuffling, Poisson sampling creates the randomness necessary to prove that the mechanism hides individual participation.

A foundational theorem stating that if a mechanism M satisfies (ε, δ)-differential privacy on a dataset, then applying M to a random subset sampled with probability q yields a mechanism satisfying (q·ε, q·δ)-DP (approximately). This linear amplification is the intuitive basis, though modern accountants like Rényi DP and Gaussian DP provide much tighter numerical bounds for composition.

A distinct but related phenomenon where the iterative nature of gradient descent itself provides privacy amplification, even without explicit noise. The key insight: releasing only the final model checkpoint rather than all intermediate gradients limits the adversary's ability to reconstruct inputs. When combined with subsampling, this effect compounds, yielding stronger guarantees than either technique alone.