Rényi Differential Privacy (RDP)

RDP is defined using the Rényi divergence of order α between the output distributions of a mechanism on neighboring datasets. A mechanism M satisfies (α, ε)-RDP if:

• Dα(M(D) || M(D')) ≤ ε
• The parameter α > 1 controls the moment order being tracked
• As α → ∞, RDP converges to pure ε-differential privacy
• For α = 1, it reduces to the KL divergence

This divergence-based definition captures the entire privacy loss distribution rather than just its tail bound, enabling significantly tighter composition.

The Gaussian mechanism achieves a clean RDP guarantee that scales naturally with sensitivity. For a query with L2 sensitivity Δ₂, adding noise with variance σ² yields:

• (α, α·Δ₂²/(2σ²))-RDP for all α > 1
• This linear dependence on α makes composition analysis straightforward
• Contrasts with (ε, δ)-DP where the Gaussian mechanism requires the tail bound approximation via δ

This property makes RDP the natural accounting framework for DP-SGD, which applies the Gaussian mechanism at each training step.

RDP's primary advantage is its simple additive composition. For k adaptive mechanisms M₁, M₂, ..., Mₖ where each Mᵢ satisfies (α, εᵢ)-RDP:

• The composed mechanism satisfies (α, Σ εᵢ)-RDP
• No advanced composition theorem or δ accumulation is needed
• This exact additivity avoids the looseness of standard composition theorems

In DP-SGD with T training steps, the total RDP cost is simply T × ε_step(α), where ε_step depends on the noise multiplier and sampling rate. This tight accounting allows more training iterations under a fixed privacy budget.

RDP guarantees can be converted to standard (ε, δ)-DP for interpretability and compliance reporting. For an (α, ε_RDP)-RDP mechanism:

• It satisfies (ε_RDP + log(1/δ)/(α-1), δ)-DP for any δ ∈ (0, 1)
• The optimal conversion finds the α that minimizes ε for a target δ
• This conversion is tight — it achieves the best possible (ε, δ)-DP bound from the RDP characterization

This property allows practitioners to use RDP for internal accounting while reporting final guarantees in the more widely recognized (ε, δ)-DP framework.

RDP interacts elegantly with Poisson subsampling, the standard technique in DP-SGD where each example is included with probability q. The amplified RDP guarantee is:

• ε'(α) = (1/(α-1)) · log(1 + q²·(α choose 2)·min{4(e^{ε(2)}-1), 2e^{ε(2)}} + ...)
• For small q, this provides a ~q² reduction in privacy cost
• The exact RDP analysis captures the amplification more tightly than (ε, δ)-DP composition

This tight subsampling analysis is critical for deep learning, where large datasets and small batch sizes yield substantial amplification gains.

RDP generalizes and formalizes the moments accountant technique introduced by Abadi et al. (2016) for DP-SGD. The relationship:

• The moments accountant tracks the log-moment generating function of the privacy loss
• RDP at order α corresponds exactly to the α-th moment bound
• RDP provides a unified framework that simplifies the analysis
• The moments accountant can be seen as computing RDP bounds numerically

This connection means RDP provides the theoretical foundation for the empirical privacy accounting used in production DP-SGD implementations like TensorFlow Privacy and Opacus.

The predecessor to RDP-based accounting that tracks higher-order moments of the privacy loss random variable. While RDP provides a cleaner functional formulation, the moments accountant introduced the core idea of bounding the moment-generating function to achieve tighter composition bounds than basic strong composition theorems. It computes the log-moment of privacy loss at each training step and sums them linearly, enabling practical DP-SGD implementations.

A formal rule quantifying how the total privacy budget degrades when multiple differentially private mechanisms are applied to the same dataset. RDP's primary advantage is its simple linear composition: the RDP parameters (α, ε) sum directly across sequential queries. This avoids the exponential overhead of naive composition and the looseness of advanced composition theorems, making it the preferred accounting method for iterative algorithms with thousands of steps.

The phenomenon where randomly sampling a subset of data before applying a differentially private mechanism yields a stronger overall privacy guarantee. In RDP accounting, subsampling amplifies the privacy parameters through a closed-form bound on the Rényi divergence between the subsampled mechanism's output distributions. This amplification is critical for DP-SGD, where each step operates on a random mini-batch, dramatically reducing the per-step privacy cost.

A preprocessing step in DP-SGD that bounds the L2 norm of per-example gradients to a fixed threshold C. This directly limits the sensitivity of the training update before noise is added. In RDP analysis, clipping ensures each individual data point's contribution to the gradient has bounded norm, enabling the application of the Gaussian mechanism with calibrated noise. The clipping threshold is a critical hyperparameter balancing privacy and utility.

The core noise injection mechanism used with RDP, adding noise drawn from a Gaussian distribution calibrated to the L2 sensitivity. RDP provides an exact analytical expression for the Rényi divergence of the Gaussian mechanism: ε(α) = (α · Δ²) / (2σ²), where Δ is sensitivity and σ is noise scale. This clean relationship enables precise privacy budget tracking across thousands of iterations without the slack introduced by approximate composition theorems.

The approximate differential privacy definition that RDP ultimately converts to for interpretability. While RDP tracks privacy loss in the Rényi divergence framework, practitioners convert the final RDP parameters back to (ε, δ)-DP using the conversion lemma: any (α, ε)-RDP mechanism satisfies (ε + log(1/δ)/(α-1), δ)-DP for any δ ∈ (0,1). This provides the familiar ε budget that policymakers and auditors understand.