The Kullback-Leibler (KL) divergence is the Renyi divergence of order alpha = 1. This relationship, established rigorously in VANERVEN2014 (Theorem 5), is the bridge that connects Renyi differential privacy (RDP) guarantees to standard (epsilon, delta)-DP and (epsilon, delta)-unlearning guarantees.
Formal Statement
Theorem 5 (Van Erven & Harremos, 2014): Let P and Q be probability distributions on (X, F). Then:
D_1(P || Q) = D(P || Q) = integral of p * ln(p/q) d mu
where D(P || Q) is the Kullback-Leibler divergence. Moreover, if D(P || Q) = infinity, or there exists beta > 1 such that D_beta(P || Q) < infinity, then:
lim_{alpha → 1} D_alpha(P || Q) = D(P || Q)
The limit is taken from both sides: both lim_{alpha → 1^-} and lim_{alpha → 1^+} converge to D(P || Q) under the stated conditions.
Intuition
For simple orders alpha != 1, the Renyi divergence is:
D_alpha(P || Q) = (1 / (alpha - 1)) * ln(integral of p^alpha * q^{1-alpha} d mu)
As alpha → 1, both the numerator ln(integral of p^alpha * q^{1-alpha} d mu) → 0 and the denominator (alpha - 1) → 0. By L’Hopital’s rule (or a direct dominated convergence argument as in the proof), this ratio converges to integral of p * ln(p/q) d mu, which is exactly the KL divergence.
For Gaussians with equal variance sigma^2, this is particularly transparent:
- D_alpha(N(mu_0, sigma^2) || N(mu_1, sigma^2)) = alpha * (mu_1 - mu_0)^2 / (2 * sigma^2) for all alpha
- D_1(N(mu_0, sigma^2) || N(mu_1, sigma^2)) = (mu_1 - mu_0)^2 / (2 * sigma^2) = D_KL
Monotonicity Context
Since Renyi divergence is nondecreasing in alpha (Theorem 3 in Van Erven & Harremos), and D_1 is the KL divergence, we have the chain of inequalities:
D_0(P || Q) ⇐ D_{1/2}(P || Q) ⇐ D_1(P || Q) = D_KL(P || Q) ⇐ D_2(P || Q) ⇐ … ⇐ D_infinity(P || Q)
This means any bound on D_alpha for alpha > 1 automatically provides an upper bound on the KL divergence, and by Pinsker’s inequality, on total variation distance.
Role in Machine Unlearning
This relationship is critical for converting Renyi divergence bounds to practical unlearning guarantees:
-
RDP-to-DP conversion: If a mechanism satisfies (alpha, epsilon)-RDP (i.e., D_alpha(M(x) || M(x’)) ⇐ epsilon), then it satisfies (epsilon + ln(1/delta)/(alpha-1), delta)-DP for any delta > 0. This conversion relies on the ordering D_1 ⇐ D_alpha combined with tail probability bounds.
-
In Koloskova et al. (2025): The gradient clipping analysis produces bounds on Renyi divergence D_alpha between adjacent model distributions. These are converted to (epsilon, delta)-unlearning guarantees via the standard RDP-to-DP conversion, which fundamentally relies on the relationship between D_alpha and D_1 = D_KL.
-
In Chien et al. (2024): The Renyi unlearning definition directly uses D_alpha, and the practical interpretation of the guarantee comes through conversion to (epsilon, delta) form using this relationship.