Three composition theorems for differential privacy

This is a brief post, bringing together three composition theorems for differential privacy.

1. The composition of an ε₁-differentially private algorithm and an ε₂-differentially private algorithm is an (ε₁+ε₂)-differentially private algorithm.
2. The composition of an (ε₁, δ₁)-differentially private algorithm and an (ε₂, δ₂)-differentially private algorithm is an (ε₁+ε₂, δ₁+δ₂)-differentially private algorithm.
3. The composition of an (α, ε₁)-Rényi differentially private algorithm and an (α, ε₂)-Rényi differentially private algorithm is an (α, ε₁+ε₂)-Rényi differentially private algorithm.

The three composition rules can be summarized briefly as follows:

ε₁ ∘ ε₂ → (ε₁ + ε₂)
(ε₁, δ₁) ∘ (ε₂, δ₂) → (ε₁+ε₂, δ₁+δ₂)
(α, ε₁) ∘ (α, ε₂) → (α, ε₁+ε₂)

What is the significance of these composition theorems? In short, ε-differential privacy and Rényi differential privacy compose as one would hope, but (ε, δ)-differential privacy does not.

The first form of differential privacy proposed was ε-differential privacy. It is relatively easy to interpret, composes nicely, but can be too rigid.

If you have Gaussian noise, for example, you are lead naturally to (ε, δ)-differential privacy. The δ term is hard to interpret. Roughly speaking you could think  it as the probability that ε-differential privacy fails to hold. Unfortunately with (ε, δ)-differential privacy the epsilons add and so do the deltas. We would prefer that δ didn’t grow with composition.

Rényi differential privacy is a generalization of ε-differential privacy that uses a family of information measures indexed by α to measure the impact of a single row being or not being in a database. The case of α = ∞ corresponds to ε-differential privacy, but finite values of α tend to be less pessimistic. The nice thing about the composition theorem for Rényi differential privacy is that the α parameter doesn’t change, unlike the δ parameter in (ε, δ)-differential privacy.