Rényi Differential Privacy (RDP)

RDP is built on Rényi divergence of order α, a measure of dissimilarity between probability distributions. For two distributions P and Q, the Rényi divergence Dα(P||Q) quantifies how distinguishable they are. An algorithm satisfies (α, ε)-RDP if the Rényi divergence between outputs on adjacent datasets is bounded by ε. This formulation provides a natural composition property: the privacy loss parameters simply add across sequential mechanisms, avoiding the complex accounting required in pure DP.

The primary advantage of RDP over standard (ε, δ)-DP is significantly tighter composition analysis. In iterative algorithms like DP-SGD, where thousands of steps accumulate privacy loss, standard composition theorems produce loose, overly conservative bounds. RDP tracks privacy loss in the Rényi space and converts to (ε, δ)-DP only at the end, yielding privacy budgets up to 2-5x smaller for the same noise level. This enables stronger privacy guarantees without sacrificing model utility.

The order α in RDP acts as a tunable knob controlling the trade-off between privacy accounting precision and conversion flexibility:

• α → 1: RDP approaches pure ε-DP, recovering the standard definition
• α → ∞: Captures worst-case privacy loss, similar to concentrated DP
• Typical values: α ∈ [2, 64] for DP-SGD, with higher orders providing tighter bounds for large compositions
• Moments Accountant connection: RDP generalizes the moments accountant by considering all moments simultaneously through the Rényi divergence

RDP guarantees can be converted to standard (ε, δ)-DP using the optimal conversion formula:

ε = εRDP(α) + log(1/δ) / (α - 1)

This conversion is performed once at the end of training, after accumulating RDP costs across all iterations. The tightness of this conversion depends on choosing the optimal α order. For a given δ, one sweeps over α to find the minimal ε, yielding the strongest possible DP guarantee from the RDP accounting.

When combined with Poisson subsampling (each example included with probability q), RDP enjoys privacy amplification analogous to the subsampled Gaussian mechanism. The amplified RDP parameter ε'(α) is computed from the base mechanism's ε(α) and the sampling rate q. This amplification is critical for DP-SGD, where small batch sizes relative to dataset size provide substantial privacy amplification. RDP handles this amplification cleanly, maintaining tight bounds through the composition of many subsampled steps.

The Gaussian mechanism—adding N(0, σ²) noise to a query with sensitivity Δ—has a particularly clean RDP characterization:

ε(α) = α · Δ² / (2σ²)

This linear relationship in α makes RDP especially convenient for DP-SGD, where Gaussian noise is added to clipped gradients. The scale parameter σ directly controls the per-step RDP cost, and the total privacy loss accumulates additively across training iterations, enabling precise privacy budget tracking throughout the training process.

The algorithmic component that tracks cumulative privacy loss across iterative training steps. In the context of RDP, the accountant converts per-step Rényi divergence bounds into a final (ε, δ)-differential privacy guarantee using tight composition theorems.

• Tracks the moments of the privacy loss random variable
• Converts RDP bounds to standard DP via Lemma 3.2 of the RDP paper
• Enables precise budgeting for DP-SGD over thousands of iterations

A privacy framework that characterizes privacy loss using hypothesis testing and f-divergences. GDP provides a dual perspective to RDP, offering tight composition bounds for subsampled mechanisms.

• Defines privacy via the trade-off between Type I and Type II errors
• The subsampled Gaussian mechanism satisfies μ-GDP
• Can be converted to and from RDP bounds for interoperability

The phenomenon where randomly sampling a subset of data before applying a differentially private mechanism yields a stronger privacy guarantee than processing the full dataset. RDP is particularly well-suited to tightly analyze this amplification.

• Poisson sampling amplifies privacy by a factor proportional to the sampling rate
• RDP provides exact analytical expressions for the amplified privacy loss
• Critical for achieving practical ε values in DP-SGD

The differentially private variant of stochastic gradient descent that clips per-sample gradients and adds Gaussian noise to the aggregated batch gradient. RDP is the standard privacy accounting method for DP-SGD.

• Per-sample gradient clipping bounds the sensitivity of each individual contribution
• Gaussian noise calibrated to the clipping norm and noise multiplier
• RDP tracks the privacy cost across tens of thousands of training steps

A class of privacy attacks that recover sensitive input data by inverting the mathematical relationship between a model's parameters and its loss gradient. RDP-based defenses bound the success rate of these attacks.

• Deep Leakage from Gradients (DLG) reconstructs images from shared gradients
• Attackers minimize the cosine similarity loss between dummy and real gradients
• RDP noise injection provides provable protection against exact reconstruction

The quantified parameter bounding maximum privacy loss, where smaller ε values enforce stronger guarantees. RDP enables tighter composition than basic strong composition theorems, preserving more utility for a given budget.

• Pure ε-DP (δ=0) vs approximate (ε, δ)-DP
• RDP converts to (ε, δ)-DP with exponentially better bounds than advanced composition
• Typical production values: ε ∈ [2, 8] for training