Differential privacy, specifically ε-differential privacy, gives strong privacy guarantees, but it can be overly cautious by focusing on worst-case scenarios. The generalization (ε, δ)-differential privacy was introduced to make ε-differential privacy more flexible.
Rényi differential privacy (RDP) is a new generalization of ε-differential privacy by Ilya Mironov that is comparable to the (ε, δ) version but has several advantages. For instance, RDP is easier to interpret than (ε, δ)-DP and composes more simply.
My previous post discussed Rényi entropy. Rényi divergence is to Rényi entropy what Kullback-Leibler divergence is to Shannon entropy.
Given two random variables X and Y that take on n possible values each with positive probabilities pi and qi respectively, the Rényi divergence of X from Y is defined by
for α > 0 and not equal to 1. The definition extends to α = 0, 1, or ∞ by taking limits.
As α converges to 1, Dα converges to the Kullback-Leibler divergence.
Rényi differential privacy
A couple weeks ago I wrote an introduction to differential privacy that started by saying
Roughly speaking, a query is differentially private if it makes little difference whether your information is included or not.
The post develops precisely what it means for a query to be differentially private. The bottom line (literally!) was
An algorithm A satisfies ε-differential privacy if for every t in the range of A, and for every pair of neighboring databases D and D’,
Here it is understood that 0/0 = 1, i.e. if an outcome has zero probability under both databases, differential privacy holds.
It turns out that this definition is equivalent to saying the Rényi divergence of order ∞ between A(D) and A(D‘) is less than ε. That is,
where α = ∞. The idea of Rényi differential privacy (RDP) is to allow the possibility that α could be finite . That is, an algorithm is (α, ε)-RDP if the Rényi divergence of order α between any two adjacent databases is no more than ε.
One of the nice properties of RDP is how simply algorithms compose: The composition of an (α, ε1)-RDP algorithm and an (α, ε2)-RDP algorithm is a (α, ε1 + ε2)-RDP algorithm. This leads to simple privacy budget accounting.
Comparison to (ε, δ)-differential privacy
The composition of ε-DP algorithms is simple: just substitute α = ∞ in the result above for composing RDP algorithms. However, the resulting bound may be overly pessimistic.
The composition of (ε, δ)-DP algorithms is not as simple: both ε and δ change. With RDP, the order α does not change, and the ε values simply add.
Mironov proves in  that every RDP algorithm is also (ε, δ)-DP algorithm. Specifically, Proposition 3 says
If f is an (α, ε)-RDP mechanism, it also satisfies
differential privacy for any 0 < δ < 1.
This tells us that Rényi differential privacy gives us privacy guarantees that are somewhere between ε-differential privacy and (ε, δ)-differential privacy.
More differential privacy posts
- Adding Laplace or Gaussian noise for privacy
- US Census Bureau embraces differential privacy
- Differential privacy benefits
 Ilya Mironov, Rényi Differential Privacy. arXiv 1702.07476
2 thoughts on “Rényi Differential Privacy”
Thanks a lot for this blog. It has been very helpful yo understand a little about differential privacy and its different versions. Please, Mr. Cook, explain briefly about the concept of privacy budget accounting. Thanks a lot in advance again.
Thanks. I was thinking earlier today that I should blog about what a privacy budget is.