Privacy Amplification

This is the most common form of privacy amplification. When a differentially private mechanism is applied to a random subset (e.g., a mini-batch) of the data, the effective privacy cost is reduced. Intuitively, an adversary is uncertain if a particular individual's data was included in the analyzed subset. The amplification factor depends on the sampling rate (q). For Poisson sampling, a mechanism with parameters (ε, δ) applied to a subset sampled with probability q amplifies to approximately (qε, qδ). This is foundational to DP-SGD, where training on random mini-batches provides stronger privacy than full-batch training.

This mechanism inserts a trusted shuffler between clients and the analyst. Clients send their locally privatized data (e.g., via Local Differential Privacy) to the shuffler, which randomly permutes the reports before passing them to the server. This breaks the link between any output record and the specific client that generated it. The shuffle provides an amplification boost because the analyst only sees a randomly ordered set of reports, obscuring individual contributions. This can convert a weak local DP guarantee into a much stronger central DP guarantee, enabling high-utility analytics with strong privacy.

Privacy amplification in federated learning is typically analyzed at the client-level. The guarantee ensures that the participation (or data) of any single device/user cannot be inferred. When each client's local dataset contains multiple examples, amplification by subsampling occurs at the client level (selecting which devices participate in a round). This is distinct from example-level DP, which protects individual data points within a client's dataset. Client-level DP is the standard for cross-device FL, as it aligns with the real-world threat model of a curious server trying to identify participating users.

Privacy amplification works synergistically with secure aggregation (SecAgg). SecAgg is a cryptographic protocol that allows a server to compute the sum of client updates without seeing any individual update. While SecAgg provides input privacy, it does not provide formal output privacy guarantees against inference from the aggregated result. By combining SecAgg with a differentially private noisy aggregation mechanism, the system achieves both. The subsampling of clients for each round provides amplification, reducing the amount of noise needed to achieve a target client-level (ε, δ) guarantee, thus improving final model utility.

Precisely tracking the amplified privacy loss requires advanced composition theorems. Simple sequential composition would overestimate the loss. Key accounting methods include:

• Advanced Composition Theorems: Provide bounds for adaptive composition of (ε, δ)-DP mechanisms.
• Moment Accountant / RDP: Rényi Differential Privacy (RDP) and the associated moment accountant used in DP-SGD provide tight bounds for the composition of subsampled Gaussian mechanisms. They track the Rényi divergence between outputs, yielding a much tighter final (ε, δ) guarantee than basic composition after hundreds of training rounds.
• Privacy Filters: Dynamic tools that enforce a total privacy budget across adaptive, subsampled queries.

While powerful, privacy amplification has important constraints:

• Dependence on Randomness: The guarantee holds only if the sampling or shuffling is truly random and unpredictable by an adversary. Any bias breaks the amplification.
• Diminishing Returns: The amplification factor is proportional to the sampling rate. Very low participation rates in FL provide strong amplification but may slow convergence.
• Not a Substitute for Core DP: Amplification improves an existing DP guarantee; it cannot create one from a non-private base mechanism.
• Accounting Complexity: As shown in the DP-FedAvg algorithm, correctly implementing and accounting for amplification requires careful integration of clipping, noise addition, and subsampling logic.

Amplification by sampling is the foundational technique that enables privacy amplification. It states that applying a differentially private mechanism to a random subset (sample) of the data provides a stronger privacy guarantee than applying it to the full dataset. The privacy parameters (ε, δ) are effectively reduced.

• Core Principle: Analyzing a 10% random sample with a mechanism of ε=1.0 can yield an effective ε < 1.0 for the full population.
• Formal Bounds: Governed by theorems like the Privacy Amplification by Subsampling lemma, which provides exact formulas for the amplified (ε_amp, δ_amp).
• Critical Application: The cornerstone of DP-SGD, where gradients are computed on random mini-batches, not the full training set.

Rényi Differential Privacy is a variant of DP defined using Rényi divergence. It is the preferred analytical framework for proving tight privacy amplification bounds, especially for compositions of Gaussian mechanisms like those used in federated learning.

• Tighter Composition: RDP often yields much smaller cumulative ε values after many training rounds compared to basic (ε, δ)-DP composition.
• Amplification Analysis: The conversion from RDP to (ε, δ)-DP after subsampling is mathematically cleaner and leads to stronger final guarantees.
• Practical Tool: Libraries like Google's TensorFlow Privacy use RDP accountants for tracking privacy loss in DP-SGD and DP-FedAvg.

Zero-Concentrated Differential Privacy is a relaxation of DP that sits between pure DP and RDP. It is particularly well-suited for analyzing the privacy of mechanisms that add Gaussian noise, making it highly relevant for amplification proofs in federated settings.

• Gaussian Mechanism Focus: zCDP captures the subgaussian tail of the privacy loss random variable from Gaussian noise addition.
• Clean Subsampling Bounds: Amplification by sampling has a simple, multiplicative form under zCDP: applying a ρ-zCDP mechanism to a γ-fraction sample yields ~(γ²ρ)-zCDP.
• Bridge to (ε, δ): zCDP guarantees can be converted to strong (ε, δ)-DP guarantees for any chosen δ > 0.

The moment accountant is an advanced privacy accounting algorithm used to tightly track the cumulative privacy loss (ε, δ) across many iterations of a randomized mechanism, such as multiple rounds of federated averaging with DP.

• Function: It bounds the moments (log moments) of the privacy loss random variable, which is key for composition.
• Enables Amplification: It is the practical implementation tool that computes the amplified privacy parameters after each subsampled training step in DP-SGD or DP-FedAvg.
• Industry Standard: The moment accountant method is what allows production systems to declare a final, total (ε, δ) after thousands of training steps.

The shuffle model is a distributed privacy architecture where client data is anonymized and randomly permuted (shuffled) by a trusted intermediary before analysis. This shuffling can provide privacy amplification, strengthening local DP guarantees to approach central DP levels.

• Architecture: Clients apply Local Differential Privacy (LDP), send reports to a shuffler, which mixes them before forwarding to the analyst.
• Amplification Effect: The shuffler breaks the link between an individual report and its sender. This randomness can reduce the effective ε required from each client's LDP mechanism.
• Federated Learning Link: Conceptual parallel to secure aggregation in FL, where the server sees only the sum of updates, not individual contributions.

Client-level differential privacy defines the unit of privacy protection in federated learning: the entire data contribution of a single client (user or device). Privacy amplification techniques are applied to achieve this guarantee.

• Granularity: The guarantee ensures that an adversary cannot confidently determine if any specific client participated in the training, based on the final model.
• Mechanism: In DP-FedAvg, each client's model update is clipped and noised. When client participation in a round is random (subsampling), privacy amplification occurs.
• Formal Goal: The output of the federated learning process satisfies (ε, δ)-DP, where the "neighboring datasets" differ by the addition or removal of one client's entire dataset.