Composition Theorem

When k differentially private mechanisms are applied sequentially to the same dataset, the total privacy loss accumulates additively. If mechanism M₁ provides ε₁-DP and mechanism M₂ provides ε₂-DP, the combined release satisfies (ε₁ + ε₂)-DP. This is the fundamental accounting rule: the privacy budget is consumed linearly with each query. For example, running three queries each with ε=0.5 on the same data consumes a total budget of ε=1.5. This property forces analysts to carefully ration queries and motivates the use of advanced composition theorems that provide tighter, sublinear bounds.

When differentially private mechanisms are applied to disjoint, independent subsets of a dataset, the total privacy loss does not accumulate. If dataset D is partitioned into disjoint subsets D₁ and D₂, and mechanism M₁(ε) runs on D₁ while M₂(ε) runs on D₂, the combined release still satisfies ε-DP, not 2ε-DP. This property is critical for scalable privacy engineering: partitioning data by user ID allows running unlimited queries in parallel without consuming additional budget, as long as each individual's data appears in only one partition.

The advanced composition theorem provides a sublinear bound on cumulative privacy loss for (ε, δ)-differentially private mechanisms. For k sequential mechanisms each satisfying (ε, δ)-DP, the total guarantee is approximately (ε√(2k ln(1/δ')), kδ + δ')-DP. This is significantly tighter than naive linear composition. For example, 1000 queries each with ε=0.01 can be bounded by ε_total ≈ 0.67 rather than ε_total = 10. This theorem is the mathematical foundation that makes iterative algorithms like DP-SGD practical over many training epochs.

The Moments Accountant technique, introduced by Abadi et al. for DP-SGD, computes the exact moment-generating function of the privacy loss random variable across all mechanism executions. Instead of relying on generic bounds, it tracks higher-order moments to produce numerically tight composition guarantees. This approach yields significantly smaller ε values than advanced composition for the same number of iterations. In practice, the Moments Accountant enables training deep neural networks with meaningful privacy guarantees (e.g., ε < 8) over tens of thousands of gradient steps, where classical composition would declare the budget exhausted.

Rényi Differential Privacy (RDP) provides an alternative composition framework based on Rényi divergence of order α. For two mechanisms with RDP guarantees (α, ε₁) and (α, ε₂), sequential composition yields (α, ε₁ + ε₂)-RDP — a simple additive property. The key advantage: RDP composes exactly and cleanly without the looseness introduced by converting to (ε, δ)-DP at each step. After accumulating the total RDP budget, a single optimal conversion to (ε, δ)-DP is performed. This approach often produces tighter final guarantees than the Moments Accountant for heterogeneous mechanisms.

A subtle but powerful composition property: iterating a contractive noise process amplifies privacy. When a differentially private mechanism is applied repeatedly with noisy updates (as in DP-SGD), the inherent randomness accumulates to provide stronger guarantees than naive composition suggests. This phenomenon, formalized by Feldman et al., shows that the privacy loss after T steps of a noisy gradient descent grows only as O(ε√T) rather than O(εT). Combined with subsampling amplification, this explains why deep learning models can train for many epochs without catastrophic privacy budget exhaustion.

The finite, quantifiable limit on total privacy loss allocated across multiple queries. The Composition Theorem dictates how this budget is consumed sequentially (additively) or in parallel (maximum). Once exhausted, further access to the sensitive dataset must be denied to prevent reconstruction attacks.

• Sequential Composition: ε_total = ε_1 + ε_2 + ... + ε_k
• Parallel Composition: ε_total = max(ε_1, ε_2, ..., ε_k) for disjoint data subsets

A privacy accounting technique that tracks higher-order moments of the privacy loss random variable. Unlike simple additive composition, the Moments Accountant provides significantly tighter bounds on cumulative privacy loss, enabling more accurate training iterations under a fixed budget.

• Computes the log of the moment generating function
• Essential for tracking privacy loss in DP-SGD
• Avoids the looseness of strong composition theorems

A relaxation of differential privacy based on the Rényi divergence. RDP provides a natural framework for tracking composition, as the RDP parameters (α, ε) add up cleanly across sequential mechanisms. It is often used as an intermediate accounting layer before converting back to standard (ε, δ)-DP guarantees.

• Additive property: RDP of order α composes linearly
• Provides tighter analysis for Gaussian mechanisms
• Converts to (ε, δ)-DP via a standard lemma

The phenomenon where randomly sampling a subset of data before applying a differentially private mechanism results in a stronger overall privacy guarantee. When combined with composition, subsampling dramatically slows down budget consumption, allowing for many more training epochs.

• Poisson sampling amplifies privacy guarantees
• Crucial for enabling deep learning with DP-SGD
• Reduces the effective ε per query by a factor proportional to the sampling rate

The core mechanism used in approximate (ε, δ)-differential privacy. It adds noise drawn from a Gaussian distribution calibrated to the L2 sensitivity of a query. Its composition properties are well-studied, and it is the standard building block for iterative algorithms like DP-SGD.

• Noise scale: σ = (Δ_2 * sqrt(2 * ln(1.25/δ))) / ε
• Composes naturally under RDP and Moments Accountant
• Enables tight privacy accounting for high-dimensional queries

A resilience property guaranteeing that any arbitrary computation applied to the output of a differentially private mechanism cannot weaken the privacy guarantee. This is critical for composition, as it ensures that intermediate sanitized results can be safely processed, visualized, or transformed without consuming additional budget.

• Holds for all differential privacy variants
• Allows safe post-hoc analysis of private outputs
• Ensures composition bounds remain valid regardless of downstream processing