Rényi Differential Privacy (RDP)

RDP measures privacy loss using the Rényi divergence of order α between the output distributions of a mechanism on adjacent datasets. Unlike pure DP which uses a worst-case max divergence, Rényi divergence provides a continuous spectrum of privacy loss measurements parameterized by α > 1. This allows the accountant to track the moment-generating function of the privacy loss random variable, capturing the full distribution rather than just a single tail bound.

The primary advantage of RDP is its tight composition theorem. When composing k mechanisms, the RDP parameters simply add: (α, ε)-RDP composed k times yields (α, kε)-RDP. This linear additivity avoids the advanced composition theorem's sublinear degradation and provides significantly tighter bounds than standard moment accountant methods. For DP-SGD training over thousands of iterations, RDP can save 30-50% of the privacy budget compared to classical composition.

RDP guarantees can be converted to standard (ε, δ)-differential privacy through a tight conversion lemma. For any (α, ε)-RDP mechanism, it satisfies (ε + (log 1/δ)/(α - 1), δ)-DP for any δ ∈ (0, 1). This conversion is lossy by design—the optimal α is chosen to minimize the resulting ε for a target δ. The conversion preserves the tighter accounting benefits while providing the universally understood DP guarantee.

RDP is particularly well-suited for the Gaussian mechanism, the workhorse of DP-SGD. For a Gaussian mechanism with noise multiplier σ, the RDP parameter is ε(α) = α / (2σ²). This clean closed-form expression enables efficient privacy accounting during training. The relationship reveals that larger α values capture higher-order moments of the privacy loss, providing a more complete characterization than the single ε of pure DP.

RDP naturally accommodates privacy amplification by subsampling, a critical property for DP-SGD where each step operates on a random mini-batch. The amplified RDP guarantee for a subsampled Gaussian mechanism follows a precise analytical bound. This amplification is multiplicative—subsampling with probability q reduces the effective ε by approximately a factor of q²—providing substantial privacy savings that compound over training epochs.

The choice of Rényi order α presents a fundamental trade-off. Small α values (close to 1) approximate pure DP and provide tighter bounds for single mechanisms, while larger α values better capture the tail behavior of the privacy loss distribution during composition. Modern accountants optimize over a discrete set of α values (typically 1.5 to 32) and select the order that minimizes the final converted (ε, δ)-DP guarantee for the target δ.

The foundational mathematical framework that RDP relaxes. DP provides an absolute worst-case privacy guarantee defined by the parameter ε (epsilon). A mechanism satisfies ε-DP if the probability of any output changes by at most a factor of e^ε when a single record is added or removed. While pure DP offers ironclad semantics, its composition bounds are loose, motivating the development of RDP for iterative algorithms.

Differentially Private Stochastic Gradient Descent is the primary algorithm where RDP accounting is applied. The process involves three steps:

• Per-sample gradient clipping: Bound the L2 norm of each individual gradient to limit sensitivity.
• Gaussian noise addition: Inject calibrated noise into the aggregated gradient.
• RDP composition: Track the cumulative privacy cost over thousands of training iterations using RDP's tight composition theorem before converting to a final (ε, δ)-DP guarantee.

A phenomenon where randomly sampling a subset of data (e.g., a mini-batch) for each training step amplifies the privacy guarantee. The uncertainty of whether a specific record was included in the batch provides an additional layer of deniability. RDP provides a clean mathematical framework to quantify this amplification effect, yielding a multiplicative reduction in the privacy cost per iteration proportional to the sampling rate.

The primary threat that RDP-based training aims to defeat. An MIA determines whether a specific record was in the training set by analyzing the model's output behavior. Attackers exploit overfitting signals such as higher confidence on training samples. RDP provides a provable upper bound on the advantage an attacker can gain, directly linking the privacy budget ε to the maximum achievable true positive rate and false positive rate of any MIA.

The quantifiable parameter ε that controls the maximum allowable information leakage. In RDP, the privacy loss is tracked in terms of the Rényi divergence of order α, producing a curve of (α, ε)-pairs. This curve is then converted to a standard (ε, δ)-DP guarantee using the conversion lemma. A smaller ε indicates a stronger guarantee, with typical production values ranging from 1 to 8 for training useful models.