Three composition theorems for differential privacy

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

1. The composition of an I₁-differentially private algorithm and an I₂-differentially private algorithm is an (I₁+I₂)-differentially private algorithm.
2. The composition of an (I₁, I₁)-differentially private algorithm and an (I₂, I₂)-differentially private algorithm is an (I₁+I₂, I₁+I₂)-differentially private algorithm.
3. The composition of an (I, I₁)-Ri(C)nyi differentially private algorithm and an (I, I₂)-Ri(C)nyi differentially private algorithm is an (I, I₁+I₂)-Ri(C)nyi differentially private algorithm.

The three composition rules can be summarized briefly as follows:

I₁ ∘ I₂ a' (I₁ + I₂)
(I₁, I₁) a (I₂, I₂) a' (I₁+I₂, I₁+I₂)
(I, I₁) a (I, I₂) a' (I, I₁+I₂)

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

The first form of differential privacy proposed was I-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 (I, I)-differential privacy. The I term is hard to interpret. Roughly speaking you could think it as the probability that I-differential privacy fails to hold. Unfortunately with (I, I)-differential privacy the epsilons add and so do the deltas. We would prefer that I didn't grow with composition.

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