Advanced Composition and Privacy Accounting
You'll learn how to achieve tighter privacy guarantees when applying multiple differentially private operations through advanced composition theorems and Rényi differential privacy.
Beyond Basic Composition
You already know that basic composition theorems tell us that running k mechanisms, each (ε, δ)-differentially private, gives us overall privacy of roughly (kε, kδ). While mathematically sound, this bound is often too pessimistic—it assumes worst-case accumulation of privacy loss at every step.
Advanced composition gives us tighter bounds by recognizing that privacy loss behaves more like a random variable that concentrates around its mean, rather than always hitting the worst case.
Advanced Composition Theorem
The advanced composition theorem states that if you run k mechanisms each satisfying (ε, δ)-differential privacy, the composition satisfies:
(ε', kδ + δ')-differential privacy
where ε' ≈ √(2k ln(1/δ')) · ε + kε · (e^ε - 1)
This is sublinear in k for the privacy parameter—much better than the linear kε from basic composition! Think of it like taking many small random steps: you don't travel as far as if you walked deterministically in the worst direction every time.
Rényi Differential Privacy (RDP)
RDP provides even tighter accounting by tracking privacy loss through Rényi divergence of order α. Instead of a single ε, you maintain a curve of privacy parameters across different orders.
Why it matters: RDP composes additively (privacy loss just adds up), making accounting across many steps trivial. You can convert back to (ε, δ)-DP at the end for interpretation.
This is particularly valuable in iterative algorithms like differentially private SGD, where you apply noise at every gradient step.
Key Takeaway: Advanced composition and Rényi differential privacy provide much tighter privacy accounting than basic composition, enabling more accurate models under the same privacy budget by avoiding overly conservative worst-case bounds.