Composition Theorems

The simplest and most conservative rule. It states that the privacy parameters add up linearly when mechanisms are applied sequentially.

• Sequential Composition: For k mechanisms each satisfying (εᵢ, δᵢ)-DP, their k-fold adaptive composition satisfies (Σεᵢ, Σδᵢ)-DP.
• Use Case: Provides a straightforward, worst-case upper bound on privacy loss. It is often used for initial design or when mechanisms are very different.
• Limitation: The linear growth of ε is overly pessimistic for many practical algorithms, leading to wasted privacy budget.

A seminal theorem that provides a square-root dependency on the number of compositions, offering a much tighter bound for high composition counts.

• Theorem (Dwork, Rothblum, Vadhan): For k mechanisms each satisfying (ε, δ)-DP, their k-fold adaptive composition satisfies (ε′, δ′)-DP where ε′ = ε√(2k log(1/δ′)) + kε(e^ε - 1). For small ε, this approximates ε√(2k log(1/δ′)).
• Use Case: The standard analysis for DP-SGD and other iterative algorithms before the advent of Rényi DP. It demonstrates that privacy degrades sub-linearly.
• Key Insight: Allows for k compositions with an overall ε that grows with √k rather than k, enabling more queries or training steps.

Rényi Differential Privacy provides a clean, composable framework where composition is simple addition of the RDP orders.

• Additive Composition: If mechanism M₁ satisfies (α, ε₁)-RDP and M₂ satisfies (α, ε₂)-RDP, their adaptive composition satisfies (α, ε₁ + ε₂)-RDP for the same order α.
• Use Case: The de facto standard for tight privacy accounting in modern libraries like TensorFlow Privacy and Opacus. It is the backbone for analyzing DP-SGD.
• Advantage: After composition in the RDP domain, the final (ε, δ)-DP guarantee is obtained by converting the composed RDP parameters, which yields significantly tighter bounds than advanced composition.

Zero-Concentrated Differential Privacy is closely related to RDP and offers elegant composition rules tailored for Gaussian noise mechanisms.

• Linear Composition: If mechanism M₁ satisfies ξ₁-zCDP and M₂ satisfies ξ₂-zCDP, their adaptive composition satisfies (ξ₁ + ξ₂)-zCDP.
• Use Case: Provides a particularly simple and intuitive analysis for mechanisms based on the Gaussian mechanism, which is native to zCDP.
• Relationship: zCDP can be viewed as a guarantee on the privacy loss random variable requiring it to be subgaussian. It often enables cleaner proofs than working directly with (ε, δ)-DP.

This is not a composition theorem per se, but a crucial related result: applying a DP mechanism to a random subset of the data amplifies (strengthens) the privacy guarantee.

• Poisson Subsampling: If a mechanism M satisfies (ε, δ)-DP, then applying M to a Poisson sample of the dataset with sampling rate q yields a mechanism satisfying (ε′, δ′)-DP with ε′ ≈ qε (for small ε).
• Use Case: Fundamental to DP-SGD, where each step operates on a random mini-batch. The amplification effect is what makes training deep models with DP feasible.
• Impact: Allows for a larger effective privacy budget per iteration or a stronger final guarantee for the same number of steps.

In federated learning with client-level DP, composition occurs across both training rounds and within each round across participating clients.

• Cross-Round Composition: The server's view of model updates over T rounds is a composition of T private release mechanisms (e.g., noisy aggregation in DP-FedAvg).
• Within-Round Amplification: The secure aggregation of many clients' noised updates can provide privacy amplification, analogous to subsampling, as the server only sees the sum.
• Accounting Challenge: Tracks the cumulative privacy loss for any individual client across all rounds they may have participated in, requiring careful use of the above composition theorems.

A privacy budget is a finite allocation of the privacy parameters epsilon (ε) and delta (δ) that is consumed over multiple queries or training steps. It acts as a resource to be spent, enforcing a hard limit on total privacy loss.

• Epsilon (ε): The primary parameter quantifying the maximum allowable privacy loss. A smaller ε indicates a stronger guarantee.
• Delta (δ): A secondary parameter representing a small probability of the privacy guarantee failing, often set to a value less than the inverse of the dataset size.
• In federated learning, a global budget is allocated per training round or for the entire training process, and composition theorems track its expenditure.

Privacy accounting is the algorithmic process of tracking the cumulative privacy loss (ε, δ) across sequential, adaptive applications of differentially private mechanisms. Its goal is to ensure the total loss does not exceed the pre-defined privacy budget.

• Methods: Basic composition (linear), advanced composition (square root), and tighter methods like the moment accountant or Rényi DP.
• Role in FL: In DP-FedAvg, accounting tracks the privacy cost across communication rounds as clients repeatedly send noised updates.
• Output: Produces a proven guarantee, e.g., 'The final model satisfies (ε=4.0, δ=1e-5)-DP after 100 rounds.'

Rényi Differential Privacy is a relaxation of differential privacy defined using Rényi divergence. It provides a more convenient and often tighter analysis of privacy loss under composition, especially for iterative algorithms like DP-SGD.

• Mechanism: It defines privacy via the Rényi divergence of order α between the output distributions on neighboring datasets.
• Advantage for Composition: RDP parameters compose linearly, making the analysis of complex, multi-step mechanisms significantly simpler and tighter than basic (ε, δ)-composition.
• Conversion: RDP guarantees can be losslessly converted back to standard (ε, δ)-DP guarantees for final reporting.

Zero-Concentrated Differential Privacy is a variant of differential privacy that provides a clean, streamlined analysis of composition for Gaussian-based mechanisms by focusing on the privacy loss random variable's subgaussian tail.

• Core Idea: It bounds the Rényi divergence of all orders α, leading to a single parameter ρ (rho) that controls the privacy guarantee.
• Composition: zCDP parameters compose linearly: applying mechanisms with guarantees ρ₁ and ρ₂ results in a total guarantee of ρ₁ + ρ₂.
• Common Use: The Gaussian mechanism naturally satisfies zCDP, making it the preferred accounting framework for many DP deep learning and federated learning implementations.

The moment accountant is an advanced privacy accounting method, central to the DP-SGD algorithm, that tracks a bound on the moments (log moments) of the privacy loss random variable to compute tight overall (ε, δ) guarantees under composition.

• Process: It calculates the log moment generating function of the privacy loss for each training step (mini-batch).
• Composition: These moments are summed across all steps, and the overall (ε, δ) guarantee is derived using the tail bound of the privacy loss distribution.
• Benefit: It yields significantly tighter privacy bounds compared to basic or advanced composition theorems, allowing for more utility per unit of privacy budget.

Amplification by sampling is a technique where the privacy guarantee of a mechanism is strengthened (amplified) because it is applied only to a randomly chosen subset of the data, such as a mini-batch in SGD or a cohort of clients in a federated learning round.

• Principle: Analyzing a random sample provides inherent privacy, as any individual's data has a probability less than 1 of being included.
• Formal Result: A mechanism satisfying (ε, δ)-DP, when applied to a Poisson sample with probability q, satisfies (ε', δ')-DP with ε' ≈ qε (for small ε). This is a key composition theorem.
• Impact in FL: It justifies random client selection in each round, providing a privacy benefit on top of mechanisms like DP-FedAvg.