Renyi differential privacy (RDP) is a relaxation of standard epsilon-delta differential privacy based on the Renyi divergence, introduced by MIRONOV2017. It provides a parameterized family of privacy definitions indexed by the order alpha, yielding tighter composition bounds and a more natural analysis of the Gaussian mechanism compared to standard (epsilon, delta)-DP.
Formally, a randomized mechanism f: D → R is said to have epsilon-Renyi differential privacy of order alpha, or (alpha, epsilon)-RDP for short, if for any adjacent inputs D, D’ (differing in one data point):
D_alpha(f(D) || f(D’)) ⇐ epsilon
where D_alpha is the Renyi divergence of order alpha >= 1. The definition coincides with pure epsilon-DP when alpha = infinity (since D_inf is the max-divergence), and by monotonicity of the Renyi divergence, (infinity, epsilon)-RDP implies (alpha, epsilon)-RDP for all finite alpha.
The fundamental advantage of RDP over (epsilon, delta)-DP is its clean composition behavior. Under standard (epsilon, delta)-DP, advanced composition requires managing a combinatorial explosion of (epsilon, delta) pairs across compositions. Under RDP, the RDP composition theorem is simply additive: if f is (alpha, epsilon_1)-RDP and g is (alpha, epsilon_2)-RDP, then their sequential composition is (alpha, epsilon_1 + epsilon_2)-RDP for any fixed alpha. This makes RDP the natural framework for analyzing iterative algorithms like SGD, where hundreds or thousands of compositions occur.
RDP connects back to standard (epsilon, delta)-DP through the RDP to epsilon-delta DP conversion lemma (Proposition 3 in MIRONOV2017): any (alpha, epsilon)-RDP mechanism satisfies (epsilon + log(1/delta)/(alpha-1), delta)-DP for any delta in (0, 1). This conversion is the final step in many privacy analyses, including Koloskova et al.’s certified unlearning proofs, where the entire privacy tracking is done in RDP and then converted to interpretable (epsilon, delta) guarantees at the end. The Renyi unlearning definition directly uses RDP to define (alpha, epsilon)-Renyi unlearning.
Key Details
- The RDP budget curve epsilon(alpha) is a non-decreasing function of alpha (by monotonicity of the Renyi divergence)
- For the Gaussian mechanism with sensitivity 1 and noise sigma: epsilon(alpha) = alpha / (2*sigma^2) — a linear function of alpha
- RDP inherits key properties from standard DP: closure under post-processing, adaptive sequential composition, group privacy (Proposition 2: if f is (alpha, epsilon)-RDP and g is 2^c-stable, then f composed with g is (alpha/2^c, 3^c*epsilon)-RDP)
- RDP is strictly stronger than (epsilon, delta)-DP: any (alpha, epsilon)-RDP mechanism also satisfies a continuum of (epsilon’, delta) guarantees, capturing the full privacy-failure tradeoff curve
- The “bad outcomes” guarantee: for (alpha, epsilon)-RDP with alpha > 1, the probability that the posterior ratio R_post(D,D’) exceeds beta * R_prior(D,D’) drops as O(1/beta^{1/(alpha-1)})
- For practical privacy accounting, one tracks the RDP curve at a discrete set of alpha values and optimizes the conversion to (epsilon, delta)-DP by choosing the best alpha for the desired delta