Amplification by Sampling

The technique's power originates from random subsampling. When a differentially private mechanism with parameters (ε, δ) is applied to a random sample of the dataset (e.g., a mini-batch in SGD), the effective privacy guarantee for the entire dataset is stronger than if the mechanism were applied to the full dataset. This is because an adversary's ability to infer the presence of any single data point is diluted by the randomness of the selection process.

• Formal Foundation: Governed by privacy amplification theorems.
• Typical Sampler: Poisson sampling, where each data point is included independently with probability p, is commonly analyzed for clean theoretical bounds.

The amplification effect is quantifiable. For a mechanism M satisfying (ε, δ)-DP applied to a Poisson sample with rate p, the subsampled mechanism often satisfies approximately (O(pε), pδ)-DP for small ε. This represents a linear reduction in the effective privacy parameter.

• Key Implication: Allows the use of a larger epsilon (ε) in the base mechanism while achieving a smaller effective epsilon overall, improving the utility-privacy trade-off.
• Example: A base DP-SGD step with ε=1.0 applied to a 5% sample (p=0.05) can yield an effective ε closer to 0.05 for that step, significantly strengthening the guarantee.

Amplification by sampling is intrinsically linked to Differentially Private Stochastic Gradient Descent (DP-SGD), where it provides the primary source of privacy amplification.

• Standard Practice: In DP-SGD, each training step processes a randomly sampled mini-batch. The Gaussian mechanism is applied to the clipped gradients of this batch.
• Accounting: Advanced privacy accountants like the Moment Accountant or Rényi DP (RDP) framework are specifically designed to tightly track the amplified privacy cost across thousands of such subsampled steps.
• Result: Enables the training of deep neural networks with non-trivial privacy guarantees that would be infeasible if analyzing the full dataset every iteration.

The degree of amplification is a direct function of the sampling probability p. A smaller p (a smaller batch size relative to the dataset) yields a stronger amplification effect.

• Trade-off: While a smaller p improves privacy, it can increase variance in the stochastic gradients, potentially slowing convergence or harming final model utility.
• Hyperparameter Tuning: The batch size (which determines p) becomes a critical hyperparameter balancing privacy, utility, and computational efficiency.

While related, amplification by sampling is distinct from privacy amplification by shuffling. Both are powerful techniques, but they operate in different models:

• Sampling: Focuses on randomly selecting a subset of data before applying a private mechanism. Central to the central DP model (e.g., DP-SGD on a centralized dataset).
• Shuffling: Assumes local DP reports from many users are collected and then randomly permuted (shuffled) by a trusted shuffler before analysis. This shuffling can amplify weak local DP guarantees into stronger central DP-like guarantees.
• Federated Context: In cross-device federated learning, client sampling (selecting a random subset of devices each round) provides a form of client-level amplification.

In Federated Learning (FL), amplification by sampling is operationalized through client sampling. Each training round selects a random subset of available devices/clients.

• Client-Level DP: This provides client-level differential privacy guarantees. The privacy assurance is that the participation (or data) of any single client is protected.
• DP-FedAvg: In algorithms like DP-FedAvg, client sampling is combined with local gradient/model update clipping and noisy aggregation on the server. The sampling amplification allows for less noise to be added per client while achieving the same overall privacy budget.
• System Constraint: Client sampling is often a necessity due to device availability and network constraints, making its privacy benefits a key advantage of the FL architecture.

The formal mathematical framework for quantifying and bounding the privacy loss incurred when an individual's data is used in a computation. It provides a rigorous, worst-case guarantee that is immune to post-processing and robust against auxiliary information.

• Core Promise: The output distribution of an algorithm should be nearly indistinguishable whether any single individual's data is included or excluded.
• Parameters: Defined by (ε, δ), where ε (epsilon) bounds the multiplicative privacy loss and δ is a small probability of the guarantee failing.

A general phenomenon where applying a differentially private mechanism to a randomly subsampled portion of a dataset yields a stronger privacy guarantee than if it were applied to the full dataset. The randomness of the sampling process itself provides an additional layer of uncertainty.

• Key Insight: Analyzing a 10% random sample with a given (ε, δ) can result in an effective privacy guarantee of (~ε/10, ~δ) for the full population.
• Formal Proofs: Established via privacy amplification by subsampling theorems, which are central to the analysis of DP-SGD and private federated averaging.

The canonical algorithm that operationalizes amplification by sampling for centralized model training. It modifies standard stochastic gradient descent to provide differential privacy.

• Mechanism: For each training step:
  1. Sample a random mini-batch.
  2. Clip the L2 norm of each per-example gradient.
  3. Add calibrated Gaussian noise to the averaged batch gradient.
• Amplification Link: The privacy cost is analyzed at the lot level (the sampled batch), not the example level, leveraging the subsampling probability for amplification.

The specific granularity of protection in federated learning, where the privacy guarantee ensures the participation of any single client (device or user) cannot be reliably inferred from the final model or aggregated updates.

• Distinction: Protects the entire local dataset of a client as a single unit, rather than individual data points within it.
• Amplification by Sampling: In federated learning, client sampling (selecting a random subset of devices per round) provides client-level privacy amplification, analogous to example-level subsampling in DP-SGD.

A variant of differential privacy defined using Rényi divergence. It often provides tighter, more composable privacy loss accounting for iterative algorithms like DP-SGD and DP-FedAvg, making it the preferred analytical tool for amplification analyses.

• Advantage: RDP parameters compose linearly and cleanly, allowing for precise tracking of privacy loss across many training rounds.
• Workflow: Mechanisms are often first analyzed and composed in the RDP framework, then converted to a final (ε, δ)-DP guarantee for interpretation.

An advanced privacy accounting method used to compute tight overall (ε, δ) bounds for compositions of Gaussian-based mechanisms, such as those in DP-SGD. It tracks a bound on the moments (log moments) of the privacy loss random variable.

• Role in Amplification: The moment accountant is specifically designed to tightly bound the privacy cost of subsampled Gaussian mechanisms, making it the standard tool for quantifying the amplification-by-sampling benefit in iterative training.