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

- The composition of an ε
_{1}-differentially private algorithm and an ε_{2}-differentially private algorithm is an (ε_{1}+ε_{2})-differentially private algorithm. - The composition of an (ε
_{1}, δ_{1})-differentially private algorithm and an (ε_{2}, δ_{2})-differentially private algorithm is an (ε_{1}+ε_{2}, δ_{1}+δ_{2})-differentially private algorithm. - The composition of an (α, ε
_{1})-Rényi differentially private algorithm and an (α, ε_{2})-Rényi differentially private algorithm is an (α, ε_{1}+ε_{2})-Rényi differentially private algorithm.

The three composition rules can be summarized briefly as follows:

ε_{1} ∘ ε_{2} → (ε_{1} + ε_{2})

(ε_{1}, δ_{1}) ∘ (ε_{2}, δ_{2}) → (ε_{1}+ε_{2}, δ_{1}+δ_{2})

(α, ε_{1}) ∘ (α, ε_{2}) → (α, ε_{1}+ε_{2})

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.