Rényi Differential Privacy
Differential privacy, specifically I-differential privacy, gives strong privacy guarantees, but it can be overly cautious by focusing on worst-case scenarios. The generalization (I, I)-differential privacy was introduced to make I-differential privacy more flexible.
Ri(C)nyi differential privacy (RDP) is a new generalization of I-differential privacy by Ilya Mironov that is comparable to the (I, I) version but has several advantages. For instance, RDP is easier to interpret than (I, I)-DP and composes more simply.
Ri(C)nyi divergenceMy previous post discussed Ri(C)nyi entropy. Ri(C)nyi divergence is to Ri(C)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 Ri(C)nyi divergence of X from Y is defined by
for I > 0 and not equal to 1. The definition extends to I = 0, 1, or a by taking limits.
As I converges to 1, DI converges to the Kullback-Leibler divergence.
Ri(C)nyi differential privacyA 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 I-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 Ri(C)nyi divergence of order a between A(D) and A(D') is less than I. That is,
where I = a. The idea of Ri(C)nyi differential privacy (RDP) is to allow the possibility that I could be finite [1]. That is, an algorithm is (I, I)-RDP if the Ri(C)nyi divergence of order I between any two adjacent databases is no more than I.
One of the nice properties of RDP is how simply algorithms compose: The composition of an (I, I1)-RDP algorithm and an (I, I2)-RDP algorithm is a (I, I1 + I2)-RDP algorithm. This leads to simple privacy budget accounting.
Comparison to (I, I)-differential privacyThe composition of I-DP algorithms is simple: just substitute I = a in the result above for composing RDP algorithms. However, the resulting bound may be overly pessimistic.
The composition of (I, I)-DP algorithms is not as simple: both I and I change. With RDP, the order I does not change, and the I values simply add.
Mironov proves in [1] that every RDP algorithm is also (I, I)-DP algorithm. Specifically, Proposition 3 says
If f is an (I, I)-RDP mechanism, it also satisfies
differential privacy for any 0 < I < 1.
This tells us that Ri(C)nyi differential privacy gives us privacy guarantees that are somewhere between I-differential privacy and (I, I)-differential privacy.
Related posts[1] Ilya Mironov, Ri(C)nyi Differential Privacy. arXiv 1702.07476