The RDP to (epsilon, delta)-DP conversion is a key result from MIRONOV2017 (Proposition 3) that bridges the Renyi differential privacy framework with standard epsilon-delta differential privacy. It provides the mechanism by which privacy guarantees tracked in the RDP framework — where composition is clean and analysis of the Gaussian mechanism is particularly tight — can be translated into interpretable (epsilon, delta) guarantees.
The conversion lemma states: if a mechanism f is (alpha, epsilon)-RDP, then it also satisfies (epsilon_delta, delta)-differential privacy for any 0 < delta < 1, where:
epsilon_delta = epsilon + log(1/delta) / (alpha - 1).
The proof proceeds by analyzing two cases. For a subset S of the output range with Pr[f(D’) in S] = Q, one shows Pr[f(D) in S] ⇐ max(e^{epsilon_delta} * Q, delta) using a key inequality from Proposition 10: Pr[f(D) in S] ⇐ {e^epsilon * Pr[f(D’) in S]}^{(alpha-1)/alpha}. In Case I where e^epsilon * Q > delta^{alpha/(alpha-1)}, one directly bounds Pr[f(D) in S] ⇐ exp(epsilon + log(1/delta)/(alpha-1)) * Q. In Case II where e^epsilon * Q ⇐ delta^{alpha/(alpha-1)}, one uses Pr[f(D) in S] ⇐ {e^epsilon * Q}^{1-1/alpha} ⇐ delta.
This conversion is the final step in Koloskova et al.’s certified unlearning pipeline: the entire privacy analysis is conducted in the RDP framework (tracking the Renyi divergence between the unlearned and retrained model distributions across iterations via privacy amplification by iteration), and then the resulting (alpha, epsilon)-RDP guarantee is converted to a user-facing (epsilon, delta)-unlearning certificate via this lemma. The alpha parameter is optimized post hoc to give the tightest possible (epsilon, delta) guarantee for the desired delta.
Key Details
- The bound is optimized by choosing alpha to minimize epsilon + log(1/delta)/(alpha-1), which for the Gaussian mechanism’s linear budget curve epsilon(alpha) = alpha/(2*sigma^2) gives an explicit optimal alpha
- For the Gaussian mechanism with sensitivity 1 and noise sigma, converting from (alpha, alpha/(2sigma^2))-RDP to (epsilon, delta)-DP by optimizing over alpha recovers sigma ~ sqrt(2ln(1.25/delta)) / epsilon, matching the direct analysis in DWORK2014 up to constants
- The conversion is a one-way reduction: given an RDP guarantee, one obtains a family of (epsilon, delta) guarantees by sweeping over delta (or alpha)
- In practice, one evaluates the conversion at a grid of alpha values (e.g., alpha in {1.5, 2, 3, 4, …, 64, inf}) and takes the tightest (epsilon, delta) bound
- The conversion introduces some looseness: the RDP curve contains more information than any single (epsilon, delta) pair, which is why analysis is best done in RDP with conversion only at the end
- Balle et al. (2020) provide a tighter conversion using the hockey-stick divergence and optimal transport, but Mironov’s Proposition 3 remains the standard reference