Rényi Differential Privacy (RDP)

Rényi differential privacy is formally defined using the Rényi divergence of order α (alpha) between the output distributions of a randomized mechanism on two adjacent datasets. A mechanism M satisfies (α, ε)-RDP if for all adjacent datasets D, D', the Rényi divergence R_α(M(D) || M(D')) ≤ ε. This provides a privacy loss profile across different moments α, rather than a single worst-case bound.

A primary advantage of RDP is its clean composition theorem. When composing k mechanisms each satisfying (α, ε_i)-RDP, the composition satisfies (α, Σ ε_i)-RDP. This linear composition in the RDP parameter ε is simpler and often yields tighter final (ε, δ) guarantees after conversion than directly using advanced composition for (ε, δ)-DP. This is critical for iterative algorithms like DP-SGD which involve thousands of composition steps.

The order α is a key parameter in RDP, taking values α > 1. It controls which moment of the privacy loss random variable is bounded.

• Low α (e.g., α → 1): Approximates pure ε-DP.
• High α: Provides tighter bounds on the tail of the privacy loss distribution, which is crucial for strong (ε, δ) guarantees after conversion. Analyzing a mechanism's RDP guarantee for multiple values of α creates a complete profile used for optimal privacy accounting.

RDP guarantees can be converted to the more familiar (ε, δ)-differential privacy framework for any chosen δ > 0. The conversion formula finds the best ε for a given δ using the RDP profile: ε(δ) = min_α [ ε_α + (log(1/δ) / (α - 1)) ]. This allows practitioners to leverage RDP's tight composition for analysis but still report guarantees in the standard (ε, δ)-DP model required by many regulations and audits.

The Gaussian mechanism has a particularly simple and optimal RDP characterization. Adding Gaussian noise with variance σ² to a function with L2 sensitivity Δ yields (α, ε)-RDP where ε = (αΔ²) / (2σ²). This closed-form expression for all α makes accounting for compositions of Gaussian-based mechanisms (like DP-SGD) straightforward and exact, unlike the more complex tail bounds used in traditional (ε, δ)-DP analysis.

RDP is closely related to zero-concentrated differential privacy (zCDP). A mechanism satisfying ρ-zCDP satisfies (α, αρ)-RDP for all α > 1. zCDP can be seen as a special case of RDP where the ε parameter scales linearly with α. RDP is a strictly more general and expressive framework, as it can capture privacy profiles that are not linear in α, providing even tighter accounting for some mechanisms.

RDP is the de facto standard for privacy accounting in Differentially Private Stochastic Gradient Descent (DP-SGD). Because DP-SGD applies the Gaussian mechanism repeatedly over thousands of training steps, naive composition of (ε, δ)-DP guarantees leads to overly pessimistic, unusable privacy bounds. RDP's composition rule for the Gaussian mechanism is additive in the Rényi divergence order (α), yielding a much tighter final (ε, δ) conversion. This allows practitioners to train models with provable, meaningful privacy guarantees that would be impossible to derive with basic DP composition.

• Key Benefit: Enables training of useful deep learning models with formal privacy, as demonstrated in foundational papers and libraries like TensorFlow Privacy.

In Federated Learning with Differential Privacy (DP-FedAvg), RDP provides the analytical backbone for client-level privacy guarantees. Each client's local update is clipped and noised. The server's aggregation of these updates across many training rounds is a complex composition of mechanisms. Using RDP for accounting allows the server to:

• Precisely track the cumulative privacy cost across communication rounds.
• Optimize the privacy-utility trade-off by selecting optimal noise scales and participation rates.
• Generate a tight, final (ε, δ) certificate for the released global model, which is crucial for compliance reporting in regulated industries like healthcare and finance.

RDP offers a particularly elegant and tight analysis of privacy amplification techniques, which are vital for making DP practical. The two most important are:

• Amplification by Subsampling: When a DP mechanism is applied to a random subset (e.g., a mini-batch) of the data, the privacy guarantee is strengthened. The RDP guarantee of a subsampled Gaussian mechanism has a closed-form expression, allowing for exact calculation of the amplified privacy parameters.
• Amplification by Shuffling: In distributed settings like federated learning, applying a local DP mechanism followed by a secure shuffle of reports can amplify privacy. RDP-based analyses provide state-of-the-art bounds for this architecture, enabling very low ε values for aggregate statistics.

This makes RDP indispensable for designing efficient, low-noise algorithms.

RDP serves as a unified analytical framework for comparing the privacy guarantees of different mechanisms and algorithm variants. Because RDP provides a continuum of guarantees parameterized by α, it creates a more informative profile than a single (ε, δ) point.

• Engineers can plot the RDP function ε(α) for two different training algorithms (e.g., DP-SGD with Poisson vs. uniform sampling) and determine which provides strictly better privacy for all α, a concept known as RDP order dominance.
• This allows for principled algorithm selection and hyperparameter tuning to minimize the privacy cost for a target model utility, moving beyond heuristic choices.

RDP acts as a flexible intermediary between pure DP (ε-DP) and other relaxations, enabling cleaner proofs and conversions. Its primary connections are:

• Zero-Concentrated DP (zCDP): zCDP is essentially a special case of RDP with a linear constraint on ε(α). Many RDP results for Gaussian mechanisms are naturally stated in terms of zCDP, which then converts to (ε, δ)-DP.
• Gaussian DP (GDP): GDP is a hypothesis testing-based formulation. RDP can be converted to GDP, and vice-versa, allowing privacy accountants to leverage the most convenient framework for different parts of an analysis.

This interoperability makes RDP a central tool in the modern differential privacy toolkit.

While RDP is used for deriving theoretical upper bounds, it also informs empirical privacy auditing methods. Auditing involves running attacks on a trained private model to estimate an empirical ε. The Rényi divergence is a direct measure that can be estimated from attack outcomes.

• By comparing the empirical RDP profile from auditing to the theoretical RDP guarantee, practitioners can validate their accounting assumptions and implementation correctness.
• This provides an additional layer of assurance for compliance officers and privacy engineers that the formal mathematical guarantees hold in practice.

The foundational mathematical framework for quantifying privacy loss. A randomized algorithm is differentially private if its output distribution is nearly indistinguishable whether any single individual's data is included or excluded from the input dataset. This provides a rigorous, worst-case guarantee against privacy leakage.

• Formal Guarantee: Protects against any auxiliary information an adversary might possess.
• Core Property: Post-processing immunity ensures any analysis on a DP output remains private.
• Primary Use: The gold standard for privacy definitions, of which RDP is a relaxation.

A variant of differential privacy that sits between pure DP and RDP, offering a particularly clean analysis of composition for Gaussian-based mechanisms. zCDP controls the Rényi divergence of order α, but requires it to be at most ρ·α for all α > 1, where ρ is the privacy parameter.

• Relationship to RDP: zCDP implies RDP guarantees for all orders α, with a linear bound. RDP offers more flexibility with a per-order bound.
• Practical Benefit: Simplifies the privacy accounting for the Gaussian mechanism, leading to tighter bounds than basic (ε, δ)-DP composition.
• Common Use: Often used as an intermediate step in privacy proofs for iterative algorithms.

An advanced privacy accounting method that tracks a bound on the moments (log moments) of the privacy loss random variable. It is the algorithmic engine that enables tight composition for mechanisms like DP-SGD.

• How it Works: Instead of using generic composition theorems, it computes the log moment of the privacy loss after each training step and uses the Chernoff bound to convert the accumulated moments into a final (ε, δ)-DP guarantee.
• Connection to RDP: The moment accountant is essentially implementing RDP composition. The bound on the α-th moment is directly related to the Rényi divergence of order α.
• Key Advantage: Delivers significantly tighter privacy bounds compared to naive sequential composition, making deep learning with DP feasible.

Mathematical rules that quantify how privacy guarantees degrade when multiple differentially private mechanisms are applied to the same dataset. RDP provides particularly elegant and tight composition bounds.

• Basic Composition: For sequential applications of mechanisms, RDP parameters simply add: ε_total(α) = Σ ε_i(α). This is tighter than the linear growth of ε in (ε, δ)-DP basic composition.
• Advanced Composition: RDP can be converted to (ε, δ)-DP, and this conversion often yields better bounds than the standard advanced composition theorem for (ε, δ)-DP.
• Critical Role: Enables the analysis of complex, multi-step algorithms like federated averaging over hundreds of training rounds.

A powerful phenomenon where applying a DP mechanism to a random subset of the data (e.g., a mini-batch) results in a stronger privacy guarantee than if applied to the full dataset. RDP provides a very clean analysis of this effect.

• Mechanism: When a data point is included in a random sample with probability q, the RDP guarantee of a subsampled mechanism is often O(q²·ε(α)) for the original guarantee ε(α).
• Impact on Training: This is why DP-SGD uses Poisson sampling or uniform sampling without replacement for batches—it drastically reduces the noise needed for a given privacy budget.
• RDP Advantage: The amplification bounds for RDP are typically tighter than those derived directly for (ε, δ)-DP.

The core probabilistic object that differential privacy definitions constrain. For two adjacent datasets, the privacy loss random variable L is defined as the log-ratio of the probability densities of the mechanism's output.

• Definition: L = ln(Pr[M(D)=o] / Pr[M(D')=o]).
• Connection to Definitions:
  • Pure DP (ε-DP): Requires |L| ≤ ε always.
  • (ε, δ)-DP: Requires Pr[L > ε] ≤ δ.
  • RDP: Bounds the moment-generating function of L, i.e., E[exp((α-1)L)] ≤ exp((α-1)ε).
• Fundamental View: RDP controls the tail behavior of the privacy loss L more finely than (ε, δ)-DP by managing its Rényi divergence.