Course contentsShow
← Machine Learning and Deep Learning
Lesson 3343 of 3,53873. Privacy in Machine LearningFree lesson

Composition Theorems

How privacy budget degrades when multiple differentially private queries are performed sequentially.

Composition Theorems

What you'll learn: How your privacy budget degrades when you run multiple differentially private queries on the same dataset.

The Cumulative Cost of Privacy

You've learned that differential privacy provides formal guarantees through parameters ε (privacy loss) and δ (failure probability). But what happens when you don't run just one private query—what if you need to train a model with thousands of gradient updates, or answer multiple analytical questions about your data?

Composition theorems tell us how privacy guarantees degrade when we perform multiple differentially private operations sequentially on the same dataset.

Basic Sequential Composition

The simplest composition theorem is straightforward but pessimistic:

If you perform k queries, each satisfying (ε, δ)-differential privacy, the combined sequence satisfies (k·ε, k·δ)-differential privacy.

Analogy: Think of your privacy budget like a bank account. Each query "spends" some privacy. Basic composition says if you make 100 transactions of 1each,you′vespent1 each, you've spent 100 total—linear accumulation.

Why This Matters

This is critical for machine learning! Training a neural network with differentially private SGD might involve 10,000 gradient steps. If each step consumes ε=0.01, basic composition gives you a final ε=100—essentially no privacy guarantee at all!

Fortunately, advanced composition theorems (which you'll learn next) provide tighter bounds, showing that privacy doesn't degrade quite this badly in practice. But the fundamental principle remains: every access to private data has a cost, and those costs add up.

Key Takeaway: Composition theorems quantify how privacy budgets accumulate across multiple queries—basic composition gives a total privacy loss of (k·ε, k·δ) for k operations, making privacy-preserving ML challenging without more sophisticated analysis.