The advanced composition theorem is a fundamental result in differential privacy theory that provides a tighter bound on the cumulative privacy loss under repeated application of differentially private mechanisms, compared to the naive linear composition bound. It was first proved by Dwork, Rothblum, and Vadhan (2010) and is presented as Theorem 3.20 in DWORK2014.
The theorem states: for all epsilon, delta, delta’ >= 0, the class of (epsilon, delta)-differentially private mechanisms satisfies (epsilon’, k*delta + delta’)-differential privacy under k-fold adaptive composition, where:
epsilon’ = sqrt(2k * ln(1/delta’) * epsilon) + k * epsilon * (e^epsilon - 1).
The key insight is that cumulative privacy loss grows as O(sqrt(k)) rather than O(k) under composition. The naive basic composition theorem (Theorem 3.16) simply adds up all the epsilon and delta values: k mechanisms with (epsilon, delta)-DP compose to (kepsilon, kdelta)-DP. The advanced composition theorem achieves the sqrt(k) scaling by exploiting the fact that the privacy loss at each step is a bounded random variable with controlled expectation, enabling the use of concentration inequalities (specifically Azuma’s inequality for supermartingales).
The proof proceeds by decomposing the total log-likelihood ratio ln(Pr[V^0 = v] / Pr[V^1 = v]) into a sum of per-step privacy loss variables c_i, each bounded by epsilon with expectation at most epsilon*(e^epsilon - 1) (by Lemma 3.18). Applying Azuma’s inequality to this sum yields Pr[sum c_i > epsilon’] < exp(-z^2/2) = delta’, giving the desired result.
This theorem has been largely superseded for practical use by the RDP composition theorem from MIRONOV2017, which provides even tighter bounds by tracking the full Renyi divergence curve rather than individual (epsilon, delta) pairs. However, the advanced composition theorem remains conceptually important and is still used when direct (epsilon, delta)-DP analysis is preferred.
Key Details
- For small epsilon, the bound simplifies to epsilon’ ~ 2epsilonsqrt(k*ln(1/delta’)), giving square-root scaling
- The theorem handles adaptive composition: the adversary can choose which mechanism to apply at step i based on the outputs of steps 1, …, i-1
- The proof uses the approximate max-divergence characterization of (epsilon, delta)-DP (Lemma 3.17) to reduce the approximate DP case to the pure DP case
- The delta’ parameter is a “composition failure probability” that is chosen by the analyst; smaller delta’ gives larger epsilon’ but higher confidence
- A practical choice is delta’ = delta, giving overall (epsilon’, (k+1)*delta)-DP
- For the Gaussian mechanism specifically, RDP composition (Corollary 3 in MIRONOV2017) gives a strictly tighter bound by exploiting the mechanism’s structure
- The result is tight up to constant factors: lower bounds show that O(sqrt(k)) composition is unavoidable for general (epsilon, delta)-DP mechanisms