🔢 mathematics

Optimal Guarantees for Auditing Rényi Differentially Private Machine Learning

This paper introduces an optimal black-box auditing framework for Rényi differential privacy that uses Donsker-Varadhan estimators to provide non-asymptotic confidence intervals and achieves information-theoretically optimal sample complexity, demonstrating superior empirical performance over state-of-the-art methods in auditing DP-SGD.

Original authors: Benjamin D. Kim, Lav R. Varshney, Daniel Alabi

Published 2026-05-22

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Benjamin D. Kim, Lav R. Varshney, Daniel Alabi

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you hire a chef to cook a meal for a large group of people, promising that the recipe is "secret." The chef claims, "I used a special technique called Rényi Differential Privacy (RDP) to ensure that no one can figure out if a specific ingredient (like a pinch of saffron) was in the pot or not."

Now, you want to verify this claim. You can't see the chef's secret notebook (that would be "white-box" auditing). You only get to taste the final soup (this is "black-box" auditing). Your goal is to figure out: How likely is it that the chef actually kept the secret?

This paper introduces a new, highly accurate "tasting test" to audit these privacy claims. Here is how it works, broken down into simple concepts:

1. The Problem: Guessing the Secret

Previous methods of testing privacy were like trying to guess the recipe by looking at the soup's color or texture. They were often too vague or relied on specific tricks (like trying to poison the soup to see if the chef noticed). These methods were good at finding big mistakes, but they struggled to give a precise, mathematical guarantee that the privacy was actually tight, especially when the privacy promise was very strong.

2. The Solution: The "Taste-Test" Hypothesis

The authors propose a new framework based on Hypothesis Testing. Think of it like a blind taste test between two soups:

Soup A: Made with the secret ingredient (the "Canary").
Soup B: Made without the secret ingredient.

If the chef's privacy technique is perfect, Soup A and Soup B should taste exactly the same. If the technique is weak, there will be a detectable difference in flavor.

The paper uses a mathematical tool called the Donsker–Varadhan (DV) estimator. Imagine this as a super-smart "flavor detector" (a neural network) that is trained to find the tiniest, most subtle differences between the two soups. Instead of just saying "they taste different," this detector calculates a precise number representing how different they are. This number is the Rényi Divergence.

3. The "Gold Standard" Guarantee

The biggest breakthrough in this paper isn't just the taste test; it's the mathematical guarantee behind it.

The Old Way: "We think the privacy is good, but we aren't 100% sure how much error our test might have."
The New Way: The authors proved that their method is information-theoretically optimal.

The Analogy: Imagine you are trying to measure the distance between two cities.

Some rulers are stretchy and give you a range of "maybe 10 miles, maybe 20."
The authors built a ruler that is mathematically proven to be the shortest possible ruler that can still give you a correct answer. They proved that no other method can measure this distance more accurately with the same amount of data. They separated the "noise" of the measurement from the actual "leakage" of the secret.

4. How They Tested It

They tested their "flavor detector" on real-world machine learning models (like those that recognize handwritten numbers or cats in photos).

They created a "worst-case scenario" by pre-training the models in a way that made them extremely sensitive to the secret ingredient.
They ran their audit and compared it to the current best methods (the "State-of-the-Art").
The Result: Their method found much tighter (more accurate) privacy bounds. It was especially good at detecting leaks when the privacy promise was very strict (small privacy budgets), which is usually the hardest time to audit.

5. What This Means (According to the Paper)

The paper claims three main things:

First of its kind: It is the first method to directly audit Rényi Differential Privacy using this specific mathematical approach.
Proven Optimal: They didn't just guess it worked; they used heavy math to prove that their method is the best possible way to do this audit, up to a tiny mathematical factor.
Better in Practice: When they actually ran the tests on computers, their method gave much stronger, more accurate lower bounds on privacy leakage than previous methods.

In short: The authors built a new, mathematically perfect ruler to measure how well AI models keep secrets. They proved that no one can build a better ruler, and they showed that their ruler works better than any existing one when tested on real AI models.

Technical Summary: Optimal Guarantees for Auditing Rényi Differentially Private Machine Learning

1. Problem Statement

As differentially private (DP) machine learning systems transition from theory to practice, a critical challenge remains: how to reliably verify, using finite empirical observations, that a learning algorithm actually satisfies its claimed privacy guarantees. While extensive literature exists on auditing pure and approximate $(\epsilon, \delta)$ -DP, theoretical foundations for auditing Rényi Differential Privacy (RDP) remain incomplete.

Existing black-box auditing methods often rely on specific attack constructions (e.g., membership inference, data poisoning) or asymptotic approximations. These approaches frequently lack finite-sample guarantees that cleanly separate statistical estimation error from algorithmic privacy leakage. Consequently, it is unclear how accurately RDP parameters can be estimated from finite samples, whether existing methods are optimal, and how auditing error scales with model complexity. This paper addresses the gap in providing rigorous, non-asymptotic, and information-theoretically optimal guarantees for auditing RDP in a black-box setting.

2. Methodology

The authors propose a new auditing framework based on hypothesis testing that directly estimates the Rényi divergence between neighboring executions of a machine learning algorithm.

2.1 Core Framework: Variational Rényi Divergence

The method utilizes the Donsker–Varadhan (DV) variational representation of Rényi divergence. Instead of relying on specific attacks, the authors frame privacy auditing as a statistical estimation problem:

Objective: Estimate (or certify a lower bound on) the Rényi divergence $D_\alpha(P \| Q)$ between output distributions $P$ and $Q$ of a mechanism evaluated on neighboring datasets.
Estimator: The authors employ a neural network-based variational estimator. They define a class of functions (critics) $\Gamma_\Theta$ parameterized by a neural network $T_\theta$ . The estimator maximizes the variational objective:
$R_\Theta^\alpha(Q \| P) = \sup_{\theta \in \Theta} \left\{ \frac{1}{\alpha-1} \log \mathbb{E}_Q[e^{(\alpha-1)T_\theta}] - \frac{1}{\alpha} \log \mathbb{E}_P[e^{\alpha T_\theta}] \right\}$
Implementation: The estimation is performed via stochastic gradient descent with mini-batching and an Exponential Moving Average (EMA) to ensure numerical stability, particularly for higher orders of $\alpha$ .

2.2 Black-Box Auditing Protocol

In the black-box setting, an adversary can only insert an input "canary" and observe the final trained model. The auditing procedure (Algorithm 3) involves:

Worst-Case Initialization: Following [31], the authors craft worst-case initial model parameters (via pre-training) to maximize the sensitivity of the training process to the presence of the canary.
Training: The model is trained twice using DP-SGD: once with the canary ( $D'$ ) and once without ( $D$ ).
Observation: The auditor collects loss values (or other outputs) for the canary from both trained models.
Estimation: The DV estimator computes the Rényi divergence between the loss distributions of the two models.

2.3 Statistical Guarantees

The paper derives explicit, non-asymptotic confidence intervals for the DV-based estimator over restricted critic classes. By treating the audit as a hypothesis test, the method converts empirical evidence into privacy violation certificates with controlled Type-I error.

3. Key Contributions

3.1 First Direct Auditing of RDP

The authors are the first to directly audit Rényi differential privacy, establishing a state-of-the-art black-box method to estimate the Rényi divergence between neighboring dataset mechanism outputs. Unlike prior works that convert between privacy notions (e.g., $\mu$ -GDP to RDP), this approach estimates the divergence directly.

3.2 Non-Asymptotic Confidence Intervals and Optimality

The paper provides rigorous theoretical guarantees:

Finite-Sample Bounds: Theorem 3.2 establishes explicit, non-asymptotic confidence intervals for the class-restricted DV Rényi estimator. These bounds separate statistical estimation error from the true privacy leakage.
Minimax Optimality: Theorem 3.3 proves matching minimax lower bounds. The authors show that, up to logarithmic factors, their sample complexity guarantees are information-theoretically optimal. No estimator can uniformly estimate the population DV objective with higher accuracy given the same sample size and critic class constraints.

3.3 Empirical Validation

The framework is instantiated for auditing DP-SGD on MNIST and CIFAR-10 datasets. The results demonstrate that the proposed auditors produce strong improvements on empirical RDP lower bounds compared to prior state-of-the-art black-box methods, particularly at small and moderate Rényi orders ( $\alpha \in (1, 2]$ ) where accurate auditing is most challenging.

4. Results

Performance: Across various privacy regimes and datasets, the DV-Rényi estimator yields tighter empirical lower bounds than the current state-of-the-art (SOTA) black-box method [31].
Sensitivity: The improvements are most pronounced at low privacy budgets (small $\epsilon_\alpha$ ), where previous methods often suffer from premature saturation or high variance.
Robustness: The method remains stable even under worst-case initializations, which are designed to maximize the detectability of privacy leakage.
Theoretical Alignment: The experimental trends align with the theoretical analysis, confirming that smaller datasets (increasing the relative impact of the canary) lead to tighter audits, while larger clipping norms (injecting more noise) reduce detectability.

5. Significance and Claims

The paper claims to establish the first optimal guarantees for auditing RDP via DV estimators. Its significance lies in:

Foundational Rigor: Moving beyond heuristic attacks to a principled statistical framework with finite-sample confidence intervals.
Information-Theoretic Limits: Characterizing the fundamental statistical limits of RDP auditing, showing that the proposed method achieves minimax optimality.
Practical Utility: Providing a tool that yields more accurate and robust privacy audits for deployed systems, particularly in regimes where accurate auditing is difficult.

The authors note that while their method is optimal up to logarithmic factors, further improvements are fundamentally limited by information-theoretic constraints. Future work directions identified include extending these guarantees to interactive and distributed settings and exploring alternative variational formulas for larger $\alpha$ values.