Rényi Differential Privacy (RDP)

The Rényi divergence of order α is the fundamental mathematical quantity underpinning RDP. It measures the information difference between the probability distributions of an algorithm's outputs on two neighboring datasets (differing by one record).

• Formal Definition: For two distributions P and Q, the Rényi divergence is D_α(P || Q) = (1/(α-1)) log E_{x∼Q}[(P(x)/Q(x))^α].
• Privacy Interpretation: A randomized algorithm M satisfies (α, ε)-RDP if for all neighboring datasets D, D', the Rényi divergence D_α(M(D) || M(D')) ≤ ε.
• Key Property: It generalizes other divergence measures; for α → 1, it converges to the Kullback–Leibler (KL) divergence used in some privacy definitions.

RDP's primary advantage is its tight composition theorem, which allows for a precise calculation of total privacy loss when the same data is used in multiple, possibly adaptive, queries or training steps.

• Sequential Composition: If mechanism M1 satisfies (α, ε1)-RDP and M2 satisfies (α, ε2)-RDP, then their sequential composition satisfies (α, ε1 + ε2)-RDP.
• Analytical Advantage: This linear composition is often much tighter (i.e., yields a smaller cumulative privacy loss) than advanced composition theorems for pure (ε,0)-DP or (ε,δ)-DP.
• Federated Learning Application: Each training round (client update release) consumes a portion of the privacy budget. RDP composition allows for more training rounds within a fixed total budget compared to traditional DP analysis.

RDP guarantees are typically converted to the more familiar (ε, δ)-Differential Privacy for final interpretation and comparison, using a well-defined mathematical conversion formula.

• Conversion Formula: If a mechanism satisfies (α, ε)-RDP, then for any δ > 0, it also satisfies (ε + log(1/δ)/(α-1), δ)-DP.
• Optimization: The privacy parameters (ε, δ) are obtained by optimizing over all possible orders α > 1. This optimization is a key step in privacy accounting tools like Google's TensorFlow Privacy library.
• Practical Outcome: This conversion allows system designers to state a final, comprehensible privacy guarantee (e.g., ε=3.0, δ=1e-5) after hundreds of training rounds, backed by the tighter RDP accounting.

The Gaussian Mechanism is the canonical noise-adding procedure used to achieve RDP when the function to be privatized is a vector-valued query, such as a gradient or model update in federated learning.

• Mechanism Definition: For a function f with L2-sensitivity Δ₂f, the Gaussian mechanism outputs f(D) + N(0, σ²I).
• RDP Guarantee: Adding Gaussian noise calibrated to σ = Δ₂f * sqrt(2ε/α) provides (α, ε)-RDP.
• Why Gaussian?: The Gaussian distribution's properties lead to clean RDP bounds and are naturally suited for the high-dimensional, iterative updates common in machine learning. It is the standard mechanism for differentially private stochastic gradient descent (DP-SGD).

The Moments Accountant is an advanced privacy accounting method built on RDP that tracks the privacy loss distribution across all composition steps, providing the tightest known bounds for iterative algorithms like DP-SGD.

• Core Idea: Instead of tracking a single ε, it tracks the moment generating function of the privacy loss random variable for all orders α.
• Implementation: For each training step (e.g., a gradient release with Gaussian noise), it computes the RDP guarantee (α, ε_step(α)) for a list of α values. The total RDP bound is the sum of these ε_step(α) values.
• Result: This method, formalized by Abadi et al. (2016), is the reason RDP became the standard for deep learning with differential privacy, enabling non-trivial utility with formal guarantees.

RDP provides clean bounds for privacy amplification by subsampling, a critical technique where the privacy guarantee is strengthened because the mechanism is applied to only a random subset of the data in each iteration.

• Process: In each training round (e.g., a federated learning communication round or a mini-batch step in DP-SGD), only a random sample of clients or data points is selected.
• RDP Bound: If a mechanism M is (α, ε)-RDP, then applying M to a Poisson subsample with rate q yields a new mechanism that is (α, ε')-RDP, where ε' is a function of α, ε, and q that is typically much smaller than ε.
• Impact: This allows for significantly more noise reduction or more training iterations for the same overall privacy budget, dramatically improving the utility-privacy trade-off.

The Gaussian Mechanism is a fundamental technique for achieving differential privacy by adding calibrated Gaussian noise to a function's output. It is defined for (ε, δ)-DP but is a core building block for implementing Rényi Differential Privacy (RDP).

• How it works: Noise scaled to the function's L2-sensitivity (maximum change a single data point can cause) and the desired privacy parameters is added.
• Link to RDP: The RDP guarantee of the Gaussian Mechanism has a simple, closed-form expression (α, ε=αΔ²/2σ²), making it the preferred analytical tool for privacy accounting when this mechanism is used iteratively.
• Application: The primary method for noising model updates (gradients) in differentially private federated learning.

Privacy Accounting is the systematic process of tracking the cumulative privacy loss across multiple queries or training iterations in a differentially private system. RDP is particularly powerful for this task.

• The Challenge: In federated learning, each training round consumes a portion of the total privacy budget. Simple composition (adding ε) leads to overly conservative, loose bounds.
• RDP's Advantage: RDP provides tighter composition bounds. The Rényi divergence composes additively: R_α(P||Q) + R_α(Q||R) = R_α(P||R). This allows for precise calculation of total (ε, δ)-DP loss after many rounds.
• Tools: Frameworks like Google's TensorFlow Privacy and OpenMined's PySyft use RDP accountants for efficient budget tracking.

Secure Aggregation is a cryptographic protocol that allows a federated learning server to compute the sum of client model updates without learning any individual client's update. It complements RDP by providing a different layer of protection.

• Core Principle: Uses Multi-Party Computation (MPC) or Homomorphic Encryption. Clients mask their updates with secret shares that cancel out when summed across all clients.
• Privacy vs. RDP: Secure Aggregation protects against a curious-but-honest server, preventing it from inspecting individual updates. RDP protects the final aggregated model from leaking information about any training sample, even if the aggregated result is revealed.
• Synergy: Using both provides defense in depth: Secure Aggregation hides individual contributions during transmission, while RDP provides a mathematical guarantee on the final output.

Byzantine Robust Aggregation refers to algorithms designed to produce a correct global model update even when a fraction of participating clients are malicious (Byzantine faults) and send arbitrary or adversarial updates. It addresses security, while RDP addresses privacy.

• Common Algorithms: Krum, Trimmed Mean, Median, and Bulyan. These algorithms statistically filter out outlier updates.
• Interaction with RDP: Adding DP noise can interfere with robust aggregation. Malicious clients may try to exploit the noise to hide their attacks. Research focuses on designing robust and private aggregation schemes that are resilient to both threats.
• Goal: Ensure the model's integrity and correctness in the presence of attackers, which is orthogonal to RDP's goal of ensuring confidentiality.

Gradient Clipping is a preprocessing step that bounds the L2-norm (magnitude) of an individual client's model update before applying noise for differential privacy. It is a prerequisite for the Gaussian Mechanism and RDP analysis.

• Purpose: Clipping controls the sensitivity of the learning algorithm. If a single data point can cause an unboundedly large gradient, no finite amount of noise can provide DP.
• Process: Each client's update vector g is transformed to g / max(1, ||g||_2 / C), where C is the clipping threshold.
• Impact on RDP: The chosen clipping norm C directly scales the noise required by the Gaussian Mechanism and is a critical parameter in the RDP privacy cost formula: ε(α) = αC²/2σ².