Course contentsShow
← Security
Lesson 2918 of 3,05254. Privacy EngineeringFree lesson

Composition Theorems

How privacy budgets degrade with multiple queries, sequential and parallel composition, and managing cumulative privacy loss.

Composition Theorems

What you'll learn: How privacy budgets degrade when you run multiple differentially private queries, and how to track cumulative privacy loss.

The Privacy Budget Problem

When you apply differential privacy to a single query, you consume part of your privacy budget (epsilon, ε). But real systems rarely run just one query. Every additional query leaks a bit more information, and composition theorems tell us exactly how much total privacy we've lost.

Think of your privacy budget like a bank account: each query makes a withdrawal. Composition theorems are the accounting rules that tell you your remaining balance.

Sequential Composition

When you run multiple differentially private mechanisms one after another on the same dataset, privacy budgets add up:

  • Query 1 with ε₁-DP + Query 2 with ε₂-DP = (ε₁ + ε₂)-DP total
  • Run 10 queries each with ε=0.1? You've spent ε=1.0 total
  • This is the basic composition theorem: worst-case, budgets accumulate linearly

This simple addition is pessimistic but safe—it assumes each query could maximally degrade privacy.

Parallel Composition

If queries operate on disjoint subsets of your data (different users, different rows), you only pay the maximum individual budget, not the sum:

  • Query 1 on users A-M with ε₁-DP + Query 2 on users N-Z with ε₂-DP = max(ε₁, ε₂)-DP

Parallel composition is powerful: you can run unlimited queries without privacy loss if they never touch the same records.

Advanced Composition

More sophisticated theorems (beyond sequential addition) show that with careful analysis, privacy degrades sublinearly—slower than simple addition—when using advanced composition bounds.

Key Takeaway: Privacy budgets degrade with every query; sequential composition adds budgets linearly, parallel composition takes the maximum across disjoint data, and careful tracking prevents privacy budget exhaustion.