Rényi Differential Privacy — Aevum Encyclopedia

Rényi Differential Privacy (RDP) is a relaxation of the standard differential privacy framework introduced by Ilya Mironov in 2017. It replaces the traditional worst-case privacy loss metric with Rényi divergence, a family of statistical divergences parameterized by an order \(\alpha > 1\). This substitution enables significantly tighter privacy accounting, particularly for iterative algorithms and subsampled mechanisms, making it a cornerstone of modern private machine learning pipelines.

💡 Why it matters

RDP simplifies the mathematical analysis of privacy composition. While standard \((\epsilon, \delta)\)-DP suffers from loose composition bounds, RDP's additive nature under composition allows practitioners to track exact privacy budgets across thousands of training steps.

Mathematical Formulation

Let \(X\) and \(X'\) be adjacent datasets. A randomized mechanism \(\mathcal{M}\) satisfies (\alpha, \varepsilon)-Rényi Differential Privacy if for all adjacent \(X, X'\):

Definition (Rényi DP) D_{\alpha}(\mathcal{M}(X) \| \mathcal{M}(X')) \leq \varepsilon

where \(D_\alpha(P \| Q)\) is the \(\alpha\)-Rényi divergence between probability distributions \(P\) and \(Q\):

Rényi Divergence D_{\alpha}(P \| Q) = \frac{1}{\alpha - 1} \log \left( \mathbb{E}_{x \sim Q} \left[ \left(\frac{P(x)}{Q(x)}\right)^\alpha \right] \right)

The parameter \(\alpha \in (1, \infty)\) controls the sensitivity to tail probabilities. As \(\alpha \to \infty\), RDP converges to standard pure differential privacy. As \(\alpha \to 1\), it approaches Kullback-Leibler divergence.

Key Properties

Rényi DP inherits and extends several foundational properties of differential privacy:

Closure under post-processing: If \(\mathcal{M}\) satisfies \((\alpha, \varepsilon)\)-RDP, any function \(f(\mathcal{M}(X))\) also satisfies \((\alpha, \varepsilon)\)-RDP.
Sequential composition: If \(\mathcal{M}_1\) satisfies \((\alpha, \varepsilon_1)\)-RDP and \(\mathcal{M}_2\) satisfies \((\alpha, \varepsilon_2)\)-RDP, their joint mechanism satisfies \((\alpha, \varepsilon_1 + \varepsilon_2)\)-RDP.
Subsampling advantage: When only a fraction \(q\) of the dataset is used per step, RDP tightens the privacy cost by approximately \(O(q^2)\), far superior to standard DP's \(O(q)\) bound.

Comparison with Standard DP

Standard \((\epsilon, \delta)\)-DP bounds the probability that the privacy loss random variable exceeds \(\epsilon\) by \(\delta\). RDP instead bounds the \(\alpha\)-th moment of the privacy loss, which often yields much tighter analytical guarantees.

Any \((\alpha, \varepsilon)\)-RDP mechanism can be converted to \((\epsilon', \delta)\)-DP via the conversion formula:

RDP to (ε, δ)-DP Conversion \varepsilon' = \varepsilon + \frac{\log(1/\delta)}{\alpha - 1}

This conversion allows RDP to be used as an internal accounting tool while reporting results in the widely understood \((\epsilon, \delta)\) format.

Practical Applications

Rényi DP has become the default privacy accountant in several major frameworks due to its computational tractability and tight bounds:

Private Stochastic Gradient Descent (PSGD): Used in federated learning to track privacy budgets across millions of gradient updates with minimal over-approximation.
Google's TensorFlow Privacy: Employs RDP as its primary accounting mechanism for DP-SGD training pipelines.
Apple's Core ML: Leverages RDP for on-device model personalization while guaranteeing strict data leakage bounds.
Differentially Private Optimization: Enables fine-grained budget allocation in iterative convex optimization and bandit algorithms.

Advantages & Limitations

Advantages:

Significantly tighter composition bounds, especially under subsampling
Clean mathematical composition rules (additive in \(\varepsilon\) for fixed \(\alpha\))
Easy conversion to standard \((\epsilon, \delta)\)-DP for reporting

Limitations:

Requires choosing an optimal \(\alpha\), which can vary by algorithm
Less intuitive interpretation compared to worst-case \(\epsilon\)
Not closed under parallel composition without additional transformations