Biostatistics · Advanced

Advanced Composition

Written by SignalsLab

Early edition: these lessons are being reviewed.

Content

Summary

Advanced composition provides a rigorous framework for analyzing cumulative privacy loss when multiple adaptive mechanisms are applied sequentially to the same dataset. Unlike naive linear summation, it yields a tighter bound where the privacy parameter epsilon grows sublinearly with the number of queries k. This approach is essential for iterative programs and large-scale multi-query settings.

Intuition

When you run multiple differentially private mechanisms on the same data, the total privacy loss accumulates. A naive approach simply adds up the privacy budgets, leading to a linear growth of k times ϵ. However, advanced composition recognizes that privacy losses do not always add up perfectly in the worst-case scenario. Instead, the dominant term scales with the square root of k, meaning the privacy degradation is much slower than linear addition would suggest. This sublinear growth makes it feasible to perform many queries, provided the failure probability δ is managed carefully, as it grows linearly with k.

Key equations

ϵ′=2kln⁡(1/δ′)⋅ϵ+kϵ(eϵ−1)
(1)

The exact bound for the composed privacy parameter epsilon prime, accounting for both Gaussian-like accumulation and approximate DP properties.

ϵ′≈2kln⁡(1/δ′)⋅ϵ
(2)

Simplified approximation for small epsilon values, highlighting the square-root dependence on k.

Derivation

  1. Identify a sequence of k mechanisms, each satisfying (ϵ,δ)-differential privacy.
  2. Apply the Advanced Composition Theorem to determine the cumulative privacy loss.
  3. Recognize that the total failure probability becomes kδ+δ′, growing linearly with k.
  4. Calculate the new epsilon prime using the formula involving a square root term for the dominant error and a second term for approximate DP specifics.
  5. Simplify the equation for small epsilon by neglecting the insignificant second term, resulting in a bound proportional to the square root of k.

Worked example

Problem

Compare the privacy cost for k=500 queries using naive composition versus advanced composition with ϵ=0.1 and δ=10−5.

  1. Naive composition sums the budget linearly: total epsilon = k * epsilon = 500 * 0.1 = 50.
  2. For advanced composition, use the simplified approximation since ϵ is small: ϵ′≈2×500×ln⁡(1/10−5)×0.1.
  3. Calculate ln(1/10^-5) = ln(10^5) approx 11.51.
  4. Compute 1000×11.51=11510≈107.3.
  5. Multiply by epsilon: 107.3 * 0.1 = 10.73.
  6. The advanced composition bound (approx 10.73) is significantly lower than the naive bound (50).

Answer Naive cost is 50; Advanced composition cost is approximately 10.73.

Common mistakes

  • Assuming advanced composition is always better than naive composition.
  • Ignoring that the failure probability δ grows linearly with k.
  • Using the simplified square-root approximation for large epsilon values.
  • Applying advanced composition for small k (less than 37) where naive composition is tighter.

Animation

Animation coming soon

The animated version of this lesson is being prepared for the web. In the Signals AI app, lessons are drawn step by step.

Code

This is a text lesson: it has no animation code yet.

ccBYNC© 2026 SignalsLab. Lesson text shared as is under CC BY-NC 4.0.