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.

## Rényi divergence

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 *p*_{i} and *q*_{i} 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

Asatisfies ε-differential privacy if for everytin the range ofA, and for every pair of neighboring databasesDandD’,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 [1]. 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 [1] that every RDP algorithm is also (ε, δ)-DP algorithm. Specifically, Proposition 3 says

If

fis an (α, ε)-RDP mechanism, it also satisfiesdifferential 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.

## Related posts

[1] Ilya Mironov, Rényi Differential Privacy. arXiv 1702.07476