Biostatistics · Intermediate

Sequential Composition

Written by SignalsLab

Early edition: these lessons are being reviewed.

Content

Summary

Sequential composition establishes that the total privacy cost for multiple mechanisms applied to the same dataset is bounded by the sum of their individual epsilon parameters. This additive rule allows analysts to track a precise privacy budget, though it provides a conservative upper bound that may exceed actual privacy loss.

Intuition

When an analyst runs several differentially private algorithms on a single input, the total privacy expenditure is not arbitrary; it is bounded by the sum of the individual privacy parameters. The core intuition is that each additional query exposes more information, and the total exposure is the aggregate of these exposures. This property allows researchers to design complex algorithms that query data repeatedly while providing a rigorous guarantee on the maximum privacy loss. However, this is an upper bound; the actual privacy impact can sometimes be less severe, but it will never exceed the sum of the individual epsilons.

Key equations

ϵtotal=ϵ1+ϵ2+…+ϵk
(1)

The total privacy budget for k sequential queries is the sum of individual budgets.

G(x)=(F1(x),F2(x)) satisfies (ϵ1+ϵ2)-DP
(2)

The joint release of two mechanisms satisfies the sum of their individual privacy parameters.

Derivation

  1. Identify that multiple mechanisms F1 and F2 are applied to the same dataset x.
  2. Note that F1 provides epsilon1-differential privacy and F2 provides epsilon2-differential privacy.
  3. Apply the sequential composition theorem which states that privacy costs accumulate additively.
  4. Conclude that the joint release G(x) satisfies (epsilon1 + epsilon2)-differential privacy.
  5. Generalize that for k queries, the total cost is the sum of all individual epsilons.

Worked example

Problem

Calculate the privacy guarantee for a combined mechanism F_combined that averages two Laplace mechanisms, F1 and F2, where epsilon1 = 1 and epsilon2 = 1.

  1. Identify that F1 satisfies 1-differential privacy and F2 satisfies 1-differential privacy.
  2. Apply sequential composition: the total epsilon is the sum of individual epsilons.
  3. Calculate epsilon_total = 1 + 1 = 2.
  4. Determine that F_combined satisfies 2-differential privacy.
  5. Note that while F3 = Laplace(0, 1/2) also has epsilon=2, the distribution of F_combined is 'pointier' than F1 but potentially less severe in actual loss than the worst-case bound.

Answer The combined mechanism satisfies 2-differential privacy.

Common mistakes

  • Misapplying sequential composition bounds to scenarios that qualify for parallel composition, such as disjoint data chunks.
  • Assuming the actual privacy loss always equals the sum of epsilons, ignoring that sequential composition provides a conservative upper bound.
  • Failing to verify whether mechanisms operate on overlapping or disjoint data subsets before choosing the composition theorem.

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.