Optimal Guarantees for Auditing Rényi Differentially Private Machine Learning

Unknown

Conceptio › Archive › arXiv CS

arXiv CSopen access

Optimal Guarantees for Auditing Rényi Differentially Private Machine Learning

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

cryptography cybersecurity privacy security

cryptography, security, privacy, cybersecurity

Optimal Guarantees for Auditing Rényi Differentially Private Machine Learning Benjamin D. Kim1 , Lav R. Varshney2 , and Daniel Alabi3 1,2,3

University of Illinois Urbana-Champaign Massachusetts Institute of Technology 2 Stony Brook University

arXiv:2605.21938v1 [cs.LG] 21 May 2026

Abstract We study black-box auditing for machine learning algorithms that claim Rényi differential privacy (RDP) guarantees. We introduce an auditing framework, based on hypothesis testing, that directly estimates Rényi divergence between neighboring executions using the Donsker–Varadhan (DV) variational estimator. Our analysis yields explicit and non-asymptotic confidence intervals for RDP auditing via classrestricted DV estimators, separating statistical estimation error from algorithmic privacy leakage. We prove matching minimax lower bounds showing that, up to logarithmic factors, our sample-complexity guarantees are information-theoretically optimal, thereby establishing the first optimal guarantees for auditing RDP via DV estimators. Empirically, we instantiate our framework for auditing DP-SGD in a fully black-box setting. Across MNIST and CIFAR-10, and over a wide range of privacy regimes, our auditors produce a strong overall improvement on empirical RDP lower bounds compared to prior state-of-the-art black-box methods especially at small and moderate Rényi orders where accurate auditing is most challenging.

Introduction

Differential privacy (DP) has become the de facto standard for providing rigorous privacy guarantees in machine learning [16, 14]. Modern private learning algorithms, most notably differentially private stochastic gradient descent (DP-SGD), are routinely deployed with privacy guarantees, expressed in terms of Rényi differential privacy (RDP), due to its tight composition guarantees and its central role in state-of-the-art privacy accounting [1, 30]. Yet, as DP systems transition from theory to practice, a fundamental question has become increasingly urgent: How can we reliably verify, from finite empirical observations, that a learning algorithm actually satisfies its claimed privacy guarantees? This question has given rise to a rapidly growing literature on privacy auditing [19, 34]. Empirical audits are used to estimate privacy leakage by distinguishing outputs of a learning algorithm on neighboring datasets, thereby producing lower bounds on the true privacy parameters [11]. Such audits play a critical role in diagnosing implementation bugs, assessing how tight the theoretical analysis is, and building trust in deployed private learning systems [15, 3]. However, despite this progress, theoretical foundations of privacy auditing remain incomplete, particularly for RDP. The gap between empirical auditing and RDP guarantees Most existing auditing methods are tailored to the original (pure and approximate) DP definitions and rely on specific attack constructions such as membership inference and data poisoning [11, 19]. While effective, these approaches could lack finite-sample guarantees that cleanly separate estimation error from algorithmic privacy leakage. In particular, it is currently unclear how accurately RDP parameters can be estimated from finite Preprint.

Figure 1: Auditing procedure in Algorithm 3.

samples, whether existing methods are optimal, and how auditing error should scale with model complexity. Black-box privacy auditing Tight audits for DP-SGD exist in the white-box auditing setting where an adversary can observe and update intermediate gradients [32]. In contrast, in this work we consider a black-box auditing setting, where an adversary can only insert an input canary and observe a (post-processing of a) final trained model. We achieve tighter audits than previous works, [19, 32, 34, 31]. We follow the method in [31] of crafting worst-case initial model parameters, since DP-SGD’s privacy is unaffected by the choice of initial parameters before private training and is still considered black-box DP auditing. The approach to doing so by pretraining on a separate part of the dataset is described in Section 4. In short, this worst-case initialization makes training as sensitive as possible to whether the canary is present, leading to a greater Rényi divergence in model outputs trained with and without the canary for us. Our approach: Hypothesis testing via the variational Rényi divergence In this work, we introduce a new framework for auditing Rényi differentially private mechanisms based on hypothesis testing. We utilize the Donsker-Varadhan (DV) variational representation of the Rényi divergence. We view privacy auditing as a statistical estimation problem: given samples from the output distributions of a mechanism evaluated on neighboring datasets, the auditor seeks to estimate (or certify a lower bound on) the corresponding Rényi divergence using the DV representation. This perspective allows us to directly connect empirical auditing to formal definitions of RDP, without relying on specific attacks or asymptotic approximations. Our analysis yields explicit, non-asymptotic confidence intervals for class-restricted Rényi divergence estimates obtained via DV-based variational objectives. These guarantees hold uniformly over parameterized critic classes and make precise the dependence on sample size, Rényi order, and function-class complexity. We can obtain statistically valid RDP audits with controlled Type-I error, converting empirical evidence into privacy violation certificates. This paper develops a rigorous, non-asymptotic framework for auditing RDP using variational (DV-based) estimators. Our contributions are summarized as follows: (i) We are the first to directly audit Rényi differential privacy, establishing a state-of-the-art black-box privacy auditing method to estimate the Rényi divergence between neighboring dataset mechanism outputs. Our Rényi divergence estimation methods between loss distributions trained with and loss distributions trained without a canary use a variational representation approach with neural networks to estimate a lower bound. (ii) We introduce a framework, based on hypothesis testing, for auditing RDP via variational Rényi divergence (Section 3.1). We derive explicit, non-asymptotic confidence intervals for DV-based Rényi divergence estimators over restricted critic classes (Theorem 3.2 and Corollary B.5). We provide matching lower bounds, establishing the optimality of our auditing guarantees (Theorem 3.3), showing that, up to logarithmic and constant factors, the sample complexity in Theorem 3.2 is minimax optimal. (iii) We validate our theory empirically on private machine learning systems, demonstrating accurate and robust RDP audits in practice (Section 4). Compared to state-of-the-art black-box auditors, our work yields empirical estimates that significantly improve over prior work. 1.1

Related Work

A growing body of work studies how to empirically audit DP machine learning algorithms by estimating privacy leakage from observed outputs of the algorithms [33, 5, 31, 11, 18, 36, 24]. Earlier work introduced data poisoning attacks as a way to audit DP-SGD, demonstrating empirical lower bounds on the privacy parameters can substantially exceed naive theoretical analysis [19]. 2

Subsequent works refined this line of research by improving tightness, reducing the number of required training runs, or adapting to different threat models: [32] proposed tight auditing schemes that exploit knowledge of the underlying DP mechanism to dramatically reduce sampling complexity whereas [34, 28] showed that meaningful DP audits can be performed using a single training run by exploiting connections between DP and generalization. While these approaches can be effective in practice, they primarily focus on pure or approximate DP guarantees. In contrast, our work targets Rényi differential privacy and develops a principled distribution-free statistical framework that yields finite-sample confidence intervals and minimax-optimal guarantees for auditing Rényi divergence directly. Several works aim to detect DP violations or compute empirical lower bounds on privacy parameters [11, 18, 36]. [11] extend previous formulations of DP in terms of hypothesis tests [21, 20] in order to detect counterexamples to DP, whereas DP-Finder [7] is used to search for DP violations as a sampling-and-optimization problem. These tools are powerful for debugging and falsifying incorrect implementations, but they are not designed to provide tight, sample-valid confidence bounds for correct algorithms, nor do they address RDP auditing or optimality guarantees. Our approach is complementary: rather than searching for explicit counterexamples, we characterize the best possible accuracy of any auditor via information-theoretic lower bounds, thereby establishing fundamental limits for RDP auditing. There have been several previous works on variational representations of information-theoretic divergences [13, 4] and more recently on approximating a lower bound via neural networks with the most prominent being mutual information neural estimation (MINE) [6]. Recent applications [17, 23, 22] use these networks to perform security and privacy analyses. Our work is the first to not only perform an empirical DP audit using these divergences, but also validate the findings with theoretical confidence bounds for both the DP estimate and lower bound estimate through neural networks.

Preliminaries and Background

2.1

Rényi Divergence Definition and Estimation

Definition 2.1 (Rényi divergence). The Rényi divergence of order α >h1 between i two probability 1 distributions P and Q defined over R is Dα (P ∥ Q) = α−1 log Ex∼Q

P (x) Q(x)

, where all loga-

rithms are natural; P (x) and Q(x) denote densities with respect to a common reference measure. Measuring the Rényi divergence and other information-theoretic divergences (such as KullbackLeibler) has presented a challenge in high-dimensional random variables until recently. The previous work of[13] presented a variational form of the KL divergence as a supremum over functions, later extended to the Rényi divergence by [4]. The idea here is to use neural networks to approximate the supremum of the class of functions, and use that approximation to calculate a lower bound of divergences [6, 8]. Definition 2.2 (Variational representations of Rényi divergence). Let P and Q be probability measures on (Ω, M), Q ≪ P , and α ∈ R, α ̸= 0, 1. Then for any set of functions, Γ, with Mb (Ω) ⊂ Γ ⊂ M(Ω) (where M(Ω) measurable n denotesRthe set of all real-valued R αg o 1 1 (α−1)g functions on Ω) we have Rα (Q∥P ) = supg∈Γ α−1 log e dQ − α log e dP or (α−1)g(X) 1 αg(Y ) 1 = supg∈Γ { α−1 log EX∼Q e − α log EY ∼P e }. To convert to the traditional Rényi divergence, the measure must be scaled by α so Dα (P ||Q) = αRα (P ||Q). Throughout the work we refer to the variational expression above as Rα and the true Rényi divergence as Dα . Much like [8], we parameterize the variational function class with a neural network and optimize the resulting sample-based objective via stochastic gradient descent. For improved numerical stability, we use mini-batching and exponential moving average (EMA) from MINE [6]. EMA is a running average that mixes the current observation with a previous EMA providing stronger stability and less variance. Mini-batching allows us to optimize using Monte Carlo estimates of expectations, but can have bias and high variance due to the exponential terms in the loss functions. This issue is even more prevalent if one estimates the Rényi divergence with an 3

Input: Order α > 1, minibatch size b, EMA rate β ∈ (0, 1), step size η Θ Output: Lower-bound estimate Rα (Q∥P ) θ ← initialize statistics network parameters mQ ← 0; mP ← 0 repeat Draw b minibatch samples from Q: x(1) , . . . , x(b) ∼ Q Draw b minibatch samples from P : y (1) , . . . , y (b) ∼ P Evaluate the lower-bound: V(θ) ←

b 1 X (i) 1 log e(α−1)Tθ (x ) α−1 b i=1

−

b 1 X (i) 1 log eαTθ (y ) α b i=1

Evaluate bias corrected gradients (e.g., moving average): e e θ V(θ) G(θ) ←∇ e Update the statistics network parameters (gradient ascent): θ ← θ + η G(θ) until convergence Algorithm 1: DV-Rényi Divergence Estimation

order of α. In attempts to remedy the bias and variance we follow MINE’s approach of maintaining an EMA that averages the exponent term over several mini batches and therefore stabilizes the resulting stochastic gradients. This is especially helpful when estimating at a large order of α for a Rényi divergence. Variants using this formula in [8] demonstrate a high mean squared error at larger α’s, so we limit our experimental evaluation for the auditor to α ∈ (1, 2], a regime in which the estimator remains relatively accurate. For our neural network, we choose ΓΘ := { Tθ : Ω → R : θ ∈ Θ } ⊆ Γ, parametrized by a deep neural network with parameters θ ∈ Θ, the statistics 1 network. We obtain the lower bound: Θ Θ (Q∥P ) = supθ∈Θ α−1 Rα (Q∥P ) ≥ Rα (Q∥P ), where Rα log EQ e(α−1)Tθ − α1 log EP eαTθ . The implementation for our Rényi divergence estimator is Algorithm 1. The proof for the formula can be found in [8, Section 6.2]. Theoretical properties follow those in [8, 6], with specific analysis for DP included in later sections. 2.2

Differential Privacy

We now introduce DP and RDP. We define (ε, δ)- differential privacy [16, 14] as follows. Definition 2.3 (Differential Privacy). A randomized privacy mechanism M : D → R satisfies (ε, δ)-DP if for any adjacent D, D′ ∈ D and any measurable S ⊆ R it holds that Pr M (D) ∈ S ≤ eε Pr M (D′ ) ∈ S + δ, where 0 ≤ δ ≤ 1. Definition 2.4 (Rényi differential privacy). A randomized privacy mechanism M : D → R satisfies (α, εα ) Rényi-DP [30] if for any adjacent D, D′ ∈ D it holds that Dα M (D) ∥ M (D′ ) ≤ εα . Note that as mentioned above, α → ∞ satisfies ε differential privacy. Further, we can then convert from RDP to (ε, δ)-DP using the formula provided in Proposition 3 in [30]. For a mechanism that 1/δ satisfies (α, εα ) RDP, the mechanism also satisfies (εα + log α−1 , δ)-DP for 0 ≤ δ ≤ 1. Since the Rényi Divergence is not symmetric, one takes the supremum of the divergence of all neighboring datasets mechanism outputs to see if the mechanism satisfies (α, εα )-RDP. 4

Input :x ∈ X n Model :Loss function f : Rd × X → R Parameters :number of iterations ℓ ≥ 1; clipping threshold c > 0; noise multiplier σ > 0; sampling probability q ∈ (0, 1]; learning rate η > 0 Initialize w0 ∈ Rd . for t = 1, . . . , ℓ do Sample S t ⊆ [n] with each i ∈ [n] included independently q. with probability t−1 t t t−1 f w , x Compute per-example gradients g ← ∇ for all i ∈ S . i w i o n Clip ĝit ← min 1, ∥gct ∥2

git for all i ∈ S t . Sample ξ t ∼ N 0, σ 2P c2 I . t t Aggregate g̃ ← ξ + i∈S t ĝit . Update wt ← wt−1 − η · g̃ t . end return w0 , w1 , . . . , wℓ Algorithm 2: DP-SGD — Differentially Private Stochastic Gradient Descent [1] i

2.3

Hypothesis Testing and Statistical Estimation

As shown in prior works, we would like to frame our auditing result as a statistical estimation problem with a bounded estimation on the privacy parameters. To begin, we start by viewing this in terms of hypothesis testing. Our null hypothesis is we have a privacy mechanism f : D → R that for any adjacent D, D′ ∈ D, satisfies (α, εα )-RDP if Dα M (D) ∥ M (D′ ) ≤ εα . Our audit’s goal is to test this hypothesis by running algorithm M . The bα . If M satisfies (α, εα )-RDP, with probability 1 − β we have R bα ≤ εα . output of the algorithm is R To view this in terms of hypothesis testing, start with the null hypothesis that the output of M satisfies (α, εnull )-RDP. Let the hypothesis test’s rejection set be Tε,α,β . If the null hypothesis is rejected, bα . To convert between hypothesis testing and statistical estimation, then we have a lower bound at R consider the following lemma. Lemma 2.5 (See Lemma B.9). For each M and a fixed α > 1, let AM ∈ Ω be a random variable and let PM ∈ R be a fixed number. For each ε, β > 0, let Tε,α,β ⊂ Ω satisfy ∀M PM = ε =⇒ P AM ∈ Tε,α,β ≤ β . (1) Further suppose that, if ε1 ≤ ε2 , then Tε1 ,α,β ⊃ Tε2 ,α,β . Then, for all M and all β > 0, Pr{ PM ≥ sup{ε > 0 : AM ∈ Tε,α,β }} ≥ 1 − β.

(2)

The proof can be interpreted as the following: AM is the auditing procedures output when applied to mechanism M that we are auditing, PM is the true epsilon, εtrue that the mechanism satisfies. For Eq 8, if the null hypothesis is true, that is M is (α, ε)-RDP the probability we reject it is at most β. We estimate the true privacy parameter by taking the largest ε for which the null hypothesis can still be rejected. By properties of RDP, we can make the monotonicity assumption that was used in the proof, that if we can reject ε2 and ε1 ≤ ε2 , we can also reject ε1 . 2.4

Black-Box Auditing Algorithm

In the black-box setting an adversary does not have intermediate access to a mechanism, and only can view/choose inputs and outputs. More on choosing specific model parameters and inputs can be found in our discussion. For our black-box auditing algorithm, we follow the standard algorithms shown in [32, 31]. In these works, one trains the model under DP-SGD both with and without the canary input. Lastly, we measure the Rényi divergence of the output losses either using a variational or numerical approach. The process is depicted in Algorithm 3.

Theoretical Results

In this section we present the main theoretical contributions of the paper. 5

Args: training dataset D, loss function ℓ, canary input (x′ , y ′ ), number of observations T Observations: O ← {}, O′ ← {} for t = 1 to T do θ ← DP-SGD on dataset D θ′ ← DP-SGD on dataset D ∪ {(x′ , y ′ )} O[t] ← ℓ(θ, (x′ , y ′ )) O′ [t] ← ℓ(θ′ , (x′ , y ′ )) end Using each entry from 1 to T in O, O′ and Renyi loss; bα = max{Rα (O, O′ ), Rα (O′ , O)}; Estimate for εα : R bα , α Return R Algorithm 3: Black-box auditing for DP-SGD with Renyi divergence

3.1

Hypothesis Testing

bα obtained by running Our test statistic for our auditing procedure is the empirical εα estimate, R algorithm M . We define our null hypothesis as for an ε0 > 0, α0 > 1 Dα0 M (D) ∥ M (D′ ) ≤ ε0 , ∀εα ≥ ε0 , α ≤ α0 . To put it concretely, the null hypothesis is that the Rényi divergence at order α0 satisfies (α0 , ε0 )-RDP. Consequently, is also satisfies (α, εα )-RDP, ∀εα ≥ ε0 , α ≤ α0 . This means our alternative hypothesis is for an ε1 > 0, α1 > 1 Dα0 M (D) ∥ M (D′ ) > ε1 , The alternative hypothesis is that the Rényi divergence at order α0 does not satisfy (α0 , ε0 )-RDP. Consequently, it also does not hold for (α, εα )-RDP, for all εα ≤ ε0 , α ≥ α0 . (See Lemma 2.5.) 3.2

Rényi-DP Lower Bound Analysis

In this section, we provide high-probability lower confidence bounds for the true Rényi divergence Dα (P ∥Q) based on the empirical estimator computed by our auditing procedure. In Section B.1, we also discuss upper bounds. Let X1 , . . . , Xn ∼ Q denote the under the canary-absent dataset, independent loss evaluations drawnP n p(x) 1 αL(Xi ) b Zi = e , Z = n i=1 Zi , so that the empirical and write L(x) = log q(x) , b α (P ∥Q) = 1 log Z. b Recall that µ := EQ [Zi ] = Rényi estimate returned by the auditor is D α−1 exp (α − 1)Dα (P ∥Q) , where EQ [Zi ] is with respect to Q. We now state finite-sample guarantees for estimating Dα (P ∥Q). The lower bound (Theorem 3.1) follows from a direct application of Markov’s inequality. In contrast, an upper confidence bound requires additional structural assumptions on the privacy-loss random variable; without such assumptions, no nontrivial distribution-free upper bound is possible for general nonnegative random variables. See Section B.1 for a discussion on upper bounds. Lower confidence bound. We first recall the standard lower-tail guarantee for the empirical Rényi estimator. Theorem 3.1 (Lower bound for Rényi-DP estimate). For any β ∈ (0, 1), with probability at least

b α (P ∥Q) − 1 log 1 − β, Dα (P ∥Q) ≥ D α−1

1 β

Proof. By Markov’s inequality applied to Zb and the identity µ = exp (α − 1)Dα (P ∥Q) , one b Taking logarithms, we obtain obtains Pr[Zb > µ/β] ≤ β so that with probability ≥ 1 − β, µ ≥ β Z. Dα (P ∥Q) =

1 1 1 log µ ≥ log Zb + log β α−1 α−1 α−1 b α (P ∥Q) − =D

1 1 log . α−1 β

cα , We can use the result we just solved for in the following way: Say we run our audit with output R 1 cα . Following Lemma 2.5, choose a desired confidence level 0 ≤ 1 − β < 1, and add α−1 log β to R 1 b Since if ε1 ≤ ε2 , Tε ,α,β ⊃ Tε ,α,β , choose ε = Rα + log β for the lower bound. 1

3.3

α−1

DV Rényi Analysis

In this section, we solve for a non-asymptotic/finite-sample confidence bound for the DV Rényi representation and show that the bound is tight (up to polylogarithmic factors). As a corollary of the finite-sample bound, we obtain that the DV Rényi representation estimator is consistent. That is, the estimation error for our DV Rényi representation converges to 0 when using neural networks to approximate the measure. Theorem 3.2 (Consistency and finite-sample confidence interval for DV Rényi estimators (see Theorem B.4)). Let α ∈ R>0 \ {1}. Let P, Q be probability distributions on a measurable space Ω. Let {Xi }ni=1 ∼ Q and {Yi }ni=1 ∼ P be independent samples. Let Θ ⊂ Rd be a parameter set with ∥θ∥ ≤ K. Assume the critic family {Tθ : Ω → R}θ∈Θ satisfies: (i) (Uniform boundedness) supθ,z |Tθ (z)| ≤ M . (ii) (Lipschitz parameterization) For all z ∈ Ω, |Tθ (z) − Tθ′ (z)| ≤ L∥θ − θ′ ∥. Define the population DV Rényi functional 1 V (θ) := α−1 log EQ e(α−1)Tθ (X) − α1 log EP eαTθ (Y ) , and its empirical estimator Vbn (θ) := Pn (α−1)Tθ (Xi ) 1 Pn 1 1 − α log n1 i=1 eαTθ (Yi ) . i=1 e α−1 log n Θ Define Rα (Q∥P ) := supθ∈Θ V (θ),

Θ bα,n R (Q∥P ) := supθ∈Θ Vbn (θ).

Θ Θ bα,n Then for any δ ∈ (0, 1), with probability at least 1 − δ, R (Q∥P ) − Rα (Q∥P ) ≤ q +log(1/δ) d log( K ) η + η , for any η > 0, and Cα,M = εn (δ), where εn (δ) = Cα,M n n o 1 1 O e2|α|M max |α−1| , |α| . −1/2 In ) yields h particular, choosing η = O(n i a valid (1 − δ) finite-sample confidence interval Θ Θ Θ bα,n bα,n bα,n R (Q∥P ) − εn (δ), R (Q∥P ) + εn (δ) . Moreover, the estimator R (Q∥P ) is consistent in

bΘ (Q∥P ) − RΘ (Q∥P ) → 0 as n → ∞. the sense: R α,n α Theorem 3.2 establishes that the class-restricted DV Rényi estimator converges at a rate scaling as O(d/ε2 ) (up to logarithmic factors). We now show that this dependence is unavoidable in general. Specifically, we prove an information-theoretic lower bound demonstrating that, under the same boundedness and Lipschitz assumptions on the critic class, no estimator can uniformly estimate the population DV objective θ 7→ V (θ) with accuracy ε and constant success probability unless the sample size scales as Ω(d/ε2 ). This result matches Theorem 3.2 in its leading dependence on the critic dimension and accuracy, establishing minimax-optimality up to logarithmic factors. Theorem 3.3 (Lower bound matching Theorem 3.2 up to log factors (see Theorem B.6)). Fix α ∈ R>0 \ {1}. There exist constants c, c0 , c1 > 0, depending only on α, such that the following holds. For every sufficiently large d, there exist a measurable space Ω, a parameter set Θ ⊂ Rd , a critic class {Tθ : Ω → R}θ∈Θ , and a family of distribution pairs Pd = {(P, Qu ) : u ∈ Ud } such that: ∥θ∥2 ≤ 1,

|Tθ (z)| ≤ 1,

|Tθ (z) − Tθ′ (z)| ≤ c0 ∥θ − θ′ ∥2

for all θ, θ′ ∈ Θ and all z ∈ Ω, and the following minimax lower bound holds. Let h i 1 h i 1 VP,Q (θ) = log EQ e(α−1)Tθ (X) − log EP eαTθ (Y ) . α−1 α For any estimator Vbn : Θ → R based on n i.i.d. samples from Q and n i.i.d. samples from P , 1 b inf sup Pr sup Vn (θ) − VP,Q (θ) ≥ ε ≥ P,Q bn (P,Q)∈Pd 4 θ∈Θ V 7

whenever

d , ε2 for all 0 < ε ≤ c1 . Consequently, any distribution-free confidence band that controls supθ∈Θ |Vbn (θ) − VP,Q (θ)| must have sample complexity at least Ω(d/ε2 ) in general. n≤c

Our theoretical results isolate the statistical estimation error of the class-restricted Donsker–Varadhan objective. Although Algorithm 1 introduces optimization errors, our theorem represents an estimationtheoretic guarantee for the variational objective. Since optimization error can only reduce the value attained by the learned critic relative to the empirical supremum, the resulting lower bound becomes more conservative. The optimization error can be observed in our experiments, Section 4.

Experimental Results

As discussed in Section 2.1, in our reported audits, we convert the variational objective to the standard Θ Rényi divergence normalization. Thus, whenever Algorithm 1 returns Rα (Q∥P ), the certified RDP Θ lower bound is αRα (Q∥P ). For simplicity, all experimental results report values in the standard RDP scale. In this section we evaluate our auditing procedure using image datasets commonly used to benchmark differentially private machine learning models. (Additional experimental results can be found in Section C.) We include results for audited privacy level εbemp from our neural estimation model We collect 500 loss observations for each canary in (O) and canary out (O′ ) at a privacy level for each experiment. To estimate the Rényi divergence which doubles as a εbemp , we use the DV Rényi model. We compare our black-box RDP results to [31], performing the appropriate conversions between µ−GDP [12], (ε, δ)-DP, and (α, εα )-RDP. Specifically, we start with (ε, 10−5 )-DP, convert to µ−GDP, and then to (1.25, εα ) and (2, εα )-RDP. 4.1

Datasets and Models

For our datasets (D), we use the MNIST [26] and CIFAR-10 [25] datasets. MNIST is composed of 28 × 28 grayscale images with 60,000 training samples and 10,000 testing samples. There are 10 separate classes for digits 0–9. CIFAR-10 has 50,000 training and 10,000 testing samples on 32 × 32 RGB images and also consists of 10 classes. The model that we are most interested in auditing is the convolutional neural networks (CNNs). Batch sizes are set to n to ease auditing. We assume adversaries have the option to choose the canary. Previous works have experimented with both blank samples [32] and ClipBKD [19]. The blank canary just has all values of 0, and the ClipBKD canary is calculated by taking the training set, performing a principal component analysis, and using the last principal component. For our experiments we use blank canaries for our CNN models. 4.2

Crafting Worst-Case Initial Parameters

DP-SGD’s privacy holds for both randomly initialized models as well as models with fixed parameters [32, 19]. We follow the method in [31] of crafting worst-case initial parameters. We pre-train the CNN models when analyzing the MNIST dataset on half of the full dataset for 5 epochs with a batch size of 32 and learning rate of 1e−2 . For analyzing the CNN on CIFAR-10, we pre-train the model on the CIFAR-100 dataset for 300 epochs with batch size 128 and a learning rate of 0.1. Then, we (non-privately) fine-tune the model on half of the full dataset for 100 epochs, with a batch size of 256 and a learning rate of 0.1. 4.3

Results

When privately training the model we set the batch size to the dataset size and the clipping threshold to C = 1.0. We privately train the model for 100 epochs on the other half of the dataset not used for pretraining. √ √We privately train our models calibrating the noise σ to satisfy µ−GDP with µ = [0.5, 1, 2, 2, 10], which can then be converted to (2, εα )-RDP with εα = [0.25, 1.0, 2.0, 4.0, 10.0] and (1.25, εα )-RDP with εα = [0.15625, 0.625, 1.25, 2.5, 6.25]. Note that these conversions also satisfy (ε, 10e−5 )-DP, where ε is [2.0, 4.38, 6.57, 10.0, 17.85]. For all of our results, we include the results from the auditing method of [31] (yellow on graphs), which is the current state of the art for 8

Table 1: Empirical RDP audits at α = 1.25. Dataset Target εα SOTA black-box DV-Rényi

MNIST

0.15625 0.625 1.25 2.5 6.25

0.056 ± 0.025 0.272 ± 0.020 0.588 ± 0.016 1.256 ± 0.091 3.325 ± 0.218

0.115 ± 0.080 0.469 ± 0.197 0.995 ± 0.289 2.239 ± 0.473 3.884 ± 0.327

CIFAR-10

0.15625 0.625 1.25 2.5 6.25

0.031 ± 0.004 0.289 ± 0.050 0.693 ± 0.082 1.539 ± 0.234 4.128 ± 0.336

0.118 ± 0.025 0.551 ± 0.056 1.095 ± 0.120 2.248 ± 0.344 4.577 ± 0.430

Table 2: Empirical RDP lower-bound audits at α = 2.0. Dataset Target εα SOTA black-box DV-Rényi

MNIST

0.25 1.0 2.0 4.0 10.0

0.089 ± 0.040 0.436 ± 0.032 0.940 ± 0.025 2.010 ± 0.145 5.320 ± 0.349

0.202 ± 0.142 0.867 ± 0.339 1.527 ± 0.325 2.127 ± 0.250 2.650 ± 0.159

CIFAR-10

0.25 1.0 2.0 4.0 10.0

0.050 ± 0.007 0.463 ± 0.080 1.109 ± 0.131 2.463 ± 0.374 6.605 ± 0.538

0.206 ± 0.041 0.953 ± 0.213 1.624 ± 0.178 2.250 ± 0.200 2.751 ± 0.170

black-box auditing. We showcase experimental efficiency here with additional experiments in the appendix. The results for α = 1.25 are shown in Table 1, and the results for α = 2.0 are shown in Table 2. We show an overall improvement on the current state of the art. 4.4

Discussion

Our experiments show that the proposed auditing framework yields an overall improvement on blackbox RDP audits than prior state-of-the-art methods across datasets, models, and privacy regimes. In particular, our DV-based estimator recovers larger empirical Rényi divergence values, with the most pronounced gains at low and moderate privacy parameters, where accurate auditing is typically most difficult. These improvements stem from directly auditing Rényi divergence itself, rather than relying on indirect privacy conversions or attack-specific heuristics. By framing RDP auditing as a statistical estimation problem with explicit confidence guarantees, our approach cleanly separates estimation error from true privacy leakage, avoiding premature saturation observed in earlier methods. The use of worst-case initialization further increases statistical power by amplifying the canary’s influence on training dynamics, while preserving the validity of DP-SGD’s privacy guarantees. The observed experimental trends align closely with our theoretical analysis. Smaller datasets increase the relative impact of the canary and lead to tighter audits, while larger clipping norms inject more noise and reduce detectability; both effects predicted by our finite-sample bounds. We note specifically that the DV-based estimator is flexible and provides sample-valid confidence intervals, ensuring statistical soundness. The strong empirical performance of our method is consistent with the minimax lower bounds proved in Section 3, suggesting that further improvements are fundamentally limited by information-theoretic constraints. 9

Conclusion

This work establishes a principled foundation for auditing machine learning systems that claim Rényi differential privacy. By formulating RDP auditing as a statistical estimation problem, we derived explicit, non-asymptotic confidence guarantees for black-box audits based on variational Rényi divergence estimators. Our analysis provides both finite-sample lower confidence bounds and matching minimax lower bounds, thereby characterizing the fundamental statistical limits of estimating the class-restricted DV Rényi auditing objective. Beyond theory, our empirical results demonstrate that the proposed methods yield substantial overall improvements: our black-box audits of DP-SGD outperform previous work, especially at small and moderate Rényi orders, across a range of datasets and model architectures. Several directions remain open: An important avenue for future work is extending optimal Rényi auditing guarantees to interactive and distributed settings. Another is exploring alternative variational formulas [9] that exhibit lower variance for larger values of α > 1.

References [1] Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pages 308–318, 2016. [2] Daniel Alabi. The existence of error-correcting codes implies privacy lower bounds. IEEE BITS the Information Theory Magazine, pages 1–12, 2026. [3] Daniel Alabi, Sainyam Galhotra, Shagufta Mehnaz, Zeyu Song, and Eugene Wu. Privacy and security in distributed data markets. In Companion of the 2025 International Conference on Management of Data, SIGMOD/PODS ’25, 2025. [4] Venkat Anantharam. A variational characterization of rényi divergences. IEEE Transactions on Information Theory, 64(11):6979–6989, 2018. [5] Meenatchi Sundaram Muthu Selva Annamalai, Georgi Ganev, and Emiliano De Cristofaro. "what do you want from theory alone?" experimenting with tight auditing of differentially private synthetic data generation. In Proceedings of the 33rd USENIX Conference on Security Symposium, SEC ’24, USA, 2024. USENIX Association. [6] Mohamed Ishmael Belghazi, Aristide Baratin, Sai Rajeswar, Sherjil Ozair, Yoshua Bengio, Aaron Courville, and Devon Hjelm. Mutual information neural estimation. In Proceedings of the 35th International Conference on Machine Learning (ICML). PMLR, 2018. [7] Benjamin Bichsel, Timon Gehr, Dana Drachsler-Cohen, Petar Tsankov, and Martin T. Vechev. Dp-finder: Finding differential privacy violations by sampling and optimization. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, CCS 2018, Toronto, ON, Canada, October 15-19, 2018, pages 508–524. ACM, 2018. [8] Jeremiah Birrell, Paul Dupuis, Markos A Katsoulakis, Luc Rey-Bellet, and Jie Wang. Variational representations and neural network estimation of rényi divergences. SIAM Journal on Mathematics of Data Science, 3(4):1093–1116, 2021. [9] Jeremiah Birrell, Yannis Pantazis, Paul Dupuis, Luc Rey-Bellet, and Markos Katsoulakis. Function-space regularized rényi divergences. In The Eleventh International Conference on Learning Representations, 2023. [10] Thomas M. Cover and Joy A. Thomas. Elements of Information Theory 2nd Edition (Wiley Series in Telecommunications and Signal Processing). Wiley-Interscience, July 2006. [11] Zeyu Ding, Yuxin Wang, Guanhong Wang, Danfeng Zhang, and Daniel Kifer. Detecting violations of differential privacy. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, CCS 2018, Toronto, ON, Canada, October 15-19, 2018, pages 475–489. ACM, 2018. [12] Jinshuo Dong, Aaron Roth, and Weijie J Su. Gaussian differential privacy. arXiv preprint arXiv:1905.02383, 2019. [13] Monroe Donsker and S. R. Srinivasa Varadhan. Asymptotic evaluation of certain markov process expectations for large time, IV. Communications on Pure and Applied Mathematics, 36(2):183–212, 1983. [14] Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In EUROCRYPT, 2006. [15] Cynthia Dwork, Nitin Kohli, and Deirdre Mulligan. Differential privacy in practice: Expose your epsilons! Journal of Privacy and Confidentiality, 9, 10 2019. [16] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith. Calibrating noise to sensitivity in private data analysis. In TCC, 2006. 11

[17] Homa Esfahanizadeh, William Wu, Manya Ghobadi, Regina Barzilay, and Muriel Médard. Infoshape: Task-based neural data shaping via mutual information. In ICASSP 2023-2023 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 1–5. IEEE, 2023. [18] Ji Guan, Wang Fang, Mingyu Huang, and Mingsheng Ying. Detecting violations of differential privacy for quantum algorithms. In Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security, CCS 2023, Copenhagen, Denmark, November 26-30, 2023, pages 2277–2291. ACM, 2023. [19] Matthew Jagielski, Jonathan Ullman, and Alina Oprea. Auditing differentially private machine learning: How private is private sgd? Advances in Neural Information Processing Systems, 33:22205–22216, 2020. [20] Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The composition theorem for differential privacy. In International conference on machine learning, pages 1376–1385. PMLR, 2015. [21] Peter Kairouz, Sewoong Oh, and Pramod Viswanath. Extremal mechanisms for local differential privacy. Journal of Machine Learning Research, 17(17):1–51, 2016. [22] Benjamin D Kim, Vipindev Adat Vasudevan, Rafael GL D’Oliveira, Alejandro Cohen, Thomas Stahlbuhk, and Muriel Médard. Cryptanalysis via machine learning based information theoretic metrics. arXiv preprint arXiv:2501.15076, 2025. [23] Benjamin D Kim, Vipindev Adat Vasudevan, Jongchan Woo, Alejandro Cohen, Rafael GL D’Oliveira, Thomas Stahlbuhk, and Muriel Médard. Crypto-mine: Cryptanalysis via mutual information neural estimation. In ICASSP 2024-2024 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 4820–4824. IEEE, 2024. [24] William Kong, Andrés Muñoz Medina, Mónica Ribero, and Umar Syed. Dp-auditorium: A large-scale library for auditing differential privacy. In 2024 IEEE Symposium on Security and Privacy (SP), pages 110–126, 2024. [25] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009. [26] Yann LeCun. The mnist database of handwritten digits. http://yann. lecun. com/exdb/mnist/, 1998. [27] F.J. MacWilliams and N.J.A. Sloane. The Theory of Error-Correcting Codes. North-holland Publishing Company, 2nd edition, 1978. [28] Saeed Mahloujifar, Luca Melis, and Kamalika Chaudhuri. Auditing f -differential privacy in one run. arXiv preprint arXiv:2410.22235, 2024. [29] Edward James McShane. Extension of range of functions. Bulletin of the American Mathematical Society, 40:837–842, 1934. [30] Ilya Mironov. Rényi differential privacy. In 2017 IEEE 30th Computer Security Foundations Symposium (CSF). IEEE, 2017. [31] Meenatchi Sundaram Muthu Selva Annamalai and Emiliano De Cristofaro. Nearly tight black-box auditing of differentially private machine learning. Advances in Neural Information Processing Systems, 37:131482–131502, 2024. [32] Milad Nasr, Jamie Hayes, Thomas Steinke, Borja Balle, Florian Tramèr, Matthew Jagielski, Nicholas Carlini, and Andreas Terzis. Tight auditing of differentially private machine learning. In 32nd USENIX Security Symposium (USENIX Security 23), pages 1631–1648, 2023. [33] Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. Membership inference attacks against machine learning models. In 2017 IEEE Symposium on Security and Privacy, SP 2017, San Jose, CA, USA, May 22-26, 2017, pages 3–18. IEEE Computer Society, 2017. [34] Thomas Steinke, Milad Nasr, and Matthew Jagielski. Privacy auditing with one (1) training run. In Advances in Neural Information Processing Systems (NeurIPS), volume 36, 2023. 12

[35] Hassler Whitney. Analytic extensions of differentiable functions defined in closed sets. Transactions of the American Mathematical Society, 36(1):63–89, 1934. [36] Jiayuan Ye, Aadyaa Maddi, Sasi Kumar Murakonda, Vincent Bindschaedler, and Reza Shokri. Enhanced membership inference attacks against machine learning models. In Heng Yin, Angelos Stavrou, Cas Cremers, and Elaine Shi, editors, Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, CCS 2022, Los Angeles, CA, USA, November 7-11, 2022, pages 3093–3106. ACM, 2022.

Notions of DP and their conversions

In our experiments, we convert our results from traditional (ε, δ)-DP to Gaussian DP (µ−GDP) [12] to (α, εα )-RDP. We convert with Corollary 2.13 and B6 in [12]. Corollary A.1. (2.13): A mechanism is µ-GDP if and only if it is (ε, δ(ε))-DP for all ε ≥ 0, where: ε µ ε µ δ(ε) = Φ − + − eε Φ − − . (3) µ 2 µ 2 Corollary A.2. (B6): If a mechanism is µ-GDP, then it is (α, 12 µ2 α)-RDP for any α > 1.

Additional Theoretical Results and Omitted Proofs (from Main Body)

This appendix provides supporting theoretical results that complement and strengthen the main guarantees in the main body. While the main body of the paper focuses on just stating lower confidence bounds and minimax-optimal estimation of Rényi divergence via variational (DV-based) methods, we provide proofs we could not include in the main body (due to space restrictions). In this appendix, our results clarify three important aspects: 1. What can and cannot be estimated from finite samples. We show that lower confidence bounds on Rényi divergence are available under no assumptions, whereas meaningful upper confidence bounds are impossible without additional structural constraints on the privacyloss random variable. This delineates a sharp boundary between what empirical privacy auditing can guarantee in a distribution-free manner and what requires stronger modeling assumptions. 2. How bounded privacy loss enables two-sided confidence intervals. By imposing a bounded privacy-loss assumption (exact for pure DP and a reasonable high-probability surrogate for many RDP mechanisms) we derive finite-sample upper and lower confidence bounds using classical concentration inequalities. These results justify when empirical audits can certify both privacy violations and near-tight compliance. 3. Why the DV-based estimator is statistically sound for auditing. We provide a full nonasymptotic analysis of the DV variational estimator over restricted critic classes, showing uniform convergence, explicit rates, and consistency. This formally validates the use of neural divergence estimators as statistically principled auditing tools, rather than heuristic approximations. Our results complete the theoretical foundation of our auditing framework by characterizing both its guarantees and its fundamental limitations. B.1

Rényi-DP Upper Bound Analysis

We adopt a natural bounded privacy-loss assumption, which holds exactly for (ε, 0)-DP mechanisms and serves as an effective high-probability surrogate for many RDP mechanisms in practice. Upper confidence bound under bounded privacy loss. In contrast to the lower bound, an upper bound on Dα (P ∥Q) from samples cannot be obtained without further assumptions: there exist distributions with arbitrarily large means that nevertheless produce finitely many small observations with high probability. We therefore impose the following assumption, natural for many DP mechanisms: Assumption B.1 (Bounded privacy loss). There exists B ∈ R such that L(x) ≤ B for all x in the B support of Q. Equivalently, p(x) q(x) ≤ e for all x. Under this assumption, 0 ≤ Zi = eαL(Xi ) ≤ eαB =: M

for all i.

This is exact for (ε, 0)-DP mechanisms, where B = ε, and serves as a practical high-probability truncation model for Gaussian or other mechanisms. 14

Theorem B.2 (Upper bound for Rényi-DP estimate under bounded privacy loss). Suppose Assumption B.1 holds. Then for any β ∈ (0, 1), with probability at least 1 − β, ! r 1 log(2/β) αB b + e Dα (P ∥Q) ≤ . log Z α−1 2n Equivalently, defining εbupper := α

q 1 log Zb + eαB log(2/β) , 2n α−1

we have Pr[ Dα (P ∥Q) ≤ εbupper ] ≥ 1 − β. α Proof. Under Assumption B.1, Zi ∈ [0, M ] almost surely. Hoeffding’s inequality yields h i 2nt2 b Pr Z − µ ≥ t ≤ 2 exp − 2 for all t > 0. M p Setting t = M log(2/β)/(2n) gives a deviation probability at most β, hence with probability at least 1 − β, q q b + eαB log(2/β) . µ ≤ Zb + M log(2/β) = Z 2n 2n Since µ = exp (α − 1)Dα (P ∥Q) , taking logarithms and dividing by (α − 1) gives the stated upper bound. Unlike lower confidence bounds, which follow directly from Markov-type arguments and hold for arbitrary nonnegative random variables, upper confidence bounds on Rényi divergence cannot be obtained in a fully distribution-free manner. So, a random variable may have arbitrarily large expectation while producing small empirical averages with high probability, making any finite-sample upper bound vacuous without further structure. For privacy auditing, this means that while violations of claimed RDP guarantees can always be certified from data, certifying near-tight compliance necessarily requires assumptions about the privacy-loss distribution. The bounded privacy-loss assumption introduced below captures exactly the setting of pure differential privacy and serves as a realistic approximation for many RDP mechanisms used in practice. B.2

Tighter lower bound with Hoeffding’s Inequality

We can prove a tighter lower bound for the Rényi divergence using similar assumptions to Theorem B.2. Theorem B.3 (Lower confidence bound under bounded privacy loss (Hoeffding)). Fix α > 1. Assume Assumption B.1 holds. Then for any β ∈ (0, 1), with probability at least 1 − β, ( )! r 1 log(1/β) Dα (P ∥Q) ≥ log max 1, Zb − M . α−1 2n Proof. Under the bounded privacy-loss assumption, we have 0 ≤ Zi ≤ M almost surely. Hence Pn Zb = n1 i=1 Zi is an average of i.i.d. bounded random variables. By Hoeffding’s inequality (one-sided lower tail), for all t > 0, 2nt2 Pr Zb − µ ≤ −t ≤ exp − 2 . (4) M Set

r t := M

log(1/β) . 2n

2 Then exp − 2nt = β, and (4) becomes 2 M Pr Zb − µ ≤ −t ≤ β, 15

which is equivalent to: with probability at least 1 − β, µ ≥ Zb − t.

(5)

Also, for α > 1, Rényi divergence is nonnegative, hence µ ≥ 1. Combining this deterministic fact with (5), we obtain on the same event b − t}. µ ≥ max{1, Z 1 We know that Dα (P ∥Q) = α−1 log µ, which yields

Dα (P ∥Q) = Substituting t = M B.3

1 1 log µ ≥ log max{1, Zb − t} . α−1 α−1

log(1/β) and M = eαB completes the proof. 2n

Finite-sample Confidence Intervals for DV Rényi estimators

Why Uniform Convergence of the DV Estimator Matters The DV variational representation is central to our auditing methodology, as it allows Rényi divergence to be estimated via optimization over a parameterized function class. However, for auditing purposes, pointwise convergence for a fixed critic is insufficient: the estimator must converge uniformly over the entire class to justify taking a supremum. Theorem B.4 establishes this uniform convergence under mild boundedness and Lipschitz assumptions, yielding explicit finite-sample confidence intervals and consistency guarantees. This result bridges modern neural divergence estimation techniques with classical statistical learning theory, and ensures that the resulting privacy audits admit rigorous, sample-valid interpretation. Theorem B.4 (Consistency and finite-sample confidence interval for DV Rényi estimators). Let α ∈ R>0 \ {1}. Let P, Q be probability distributions on a measurable space Ω. Let {Xi }ni=1 ∼ Q and {Yi }ni=1 ∼ P be independent samples. Let Θ ⊂ Rd be a parameter set with ∥θ∥ ≤ K. Assume the critic family {Tθ : Ω → R}θ∈Θ satisfies: 1. (Uniform boundedness) supθ,z |Tθ (z)| ≤ M . 2. (Lipschitz parameterization) For all z ∈ Ω, |Tθ (z) − Tθ′ (z)| ≤ L∥θ − θ′ ∥. Define the population DV Rényi functional h i 1 h i 1 log EQ e(α−1)Tθ (X) − log EP eαTθ (Y ) , V (θ) := α−1 α and its empirical estimator n

Vbn (θ) :=

1 1 X (α−1)Tθ (Xi ) log e α−1 n i=1

1 1 X αTθ (Yi ) − log e α n i=1

Define Θ Rα (Q∥P ) := sup V (θ),

Θ bα,n R (Q∥P ) := sup Vbn (θ).

θ∈Θ

Then for any δ ∈ (0, 1), with probability at least 1 − δ, Θ Θ bα,n R (Q∥P ) − Rα (Q∥P ) ≤ εn (δ),

where

v  u u d log K + log(1/δ) t  η + η εn (δ) = Cα,M   , n

! .

for any η > 0, and o n 1 1 , |α| . Cα,M = O e2|α|M max |α−1| In particular, choosing η = O(n−1/2 ) yields a valid (1 − δ) finite-sample confidence interval h i Θ Θ bα,n bα,n R (Q∥P ) − εn (δ), R (Q∥P ) + εn (δ) . Θ bα,n In addition, the estimator R (Q∥P ) is consistent in the following sense: Θ Rα (Q∥P ) → 0 as n → ∞.

Θ bα,n R (Q∥P ) −

Proof. The proof for the finite-sample bound proceeds in four steps. Step 1: Concentration for fixed θ.

Define n X bθ := 1 A e(α−1)Tθ (Xi ) . n i=1

Aθ := EQ [e(α−1)Tθ (X) ], Since |Tθ | ≤ M ,

e−|α−1|M ≤ e(α−1)Tθ (X) ≤ e|α−1|M . bθ is an average of i.i.d. bounded random variables. Hoeffding’s inequality implies that for all Thus A t > 0, nt2 b P |Aθ − Aθ | ≥ t ≤ 2 exp − 2|α−1|M . 2e Similarly, define n X bθ := 1 eαTθ (Yi ) , B n i=1

Bθ := EP [eαTθ (Y ) ], and obtain

b P |Bθ − Bθ | ≥ t ≤ 2 exp −

nt2 2e2|α|M

bθ ≥ e−|α−1|M , the logarithm is Lipschitz Step 2: From moment errors to log errors. Since Aθ , A |α−1|M on this interval with constant e . Thus bθ − log Aθ | ≤ e|α−1|M |A bθ − Aθ |. | log A bθ . An analogous bound holds for log B Combining both terms, e|α|M b e|α−1|M b |Aθ − Aθ | + |Bθ − Bθ |. |α − 1| |α| Therefore there exists a constant c > 0 such that P |Vbn (θ) − V (θ)| ≥ u ≤ 4 exp −c n u2 e−4|α|M . |Vbn (θ) − V (θ)| ≤

Step 3: Uniformization over Θ via covering numbers. Let Nη be an η-net of Θ in Euclidean norm. Since Θ ⊆ B(0, K) ⊂ Rd , d 3K |Nη | ≤ . η Applying a union bound, b P max |Vn (ϑ) − V (ϑ)| ≥ u ≤ |Nη | · 4 exp −c n u2 e−4|α|M . ϑ∈Nη

Choosing r u = Cα,M

d log(K/η) + log(1/δ) n

ensures the above probability is at most δ/2. 17

θ∈Θ

Step 5: Confidence interval for the supremum.

Finally, for any functions f, g,

| sup f − sup g| ≤ sup |f − g|. Applying this inequality completes the proof of the finite-sample bound. The consistency statement follows from the finite-sample bound. Corollary B.5 (DP-auditing via finite-sample DV Rényi certificates). Fix α ∈ (1, ∞) and let δCI ∈ (0, 1). Consider neighboring datasets D, D′ and let P := M(D) and Q := M(D′ ) denote the output distributions of a (possibly randomized) mechanism M. Let Θ ⊂ Rd and {Tθ }θ∈Θ satisfy the assumptions of Theorem 3.2 (boundedness and Lipschitz parameterization). iid

iid

Suppose we can draw independent samples {Yi }ni=1 ∼ P and {Xi }ni=1 ∼ Q, and compute the empirical DV Rényi estimator Θ bα,n R (Q∥P ) := sup Vbn (θ)

as defined in Theorem 3.2.

θ∈Θ

Let εn (δCI ) be the corresponding confidence radius from Theorem 3.2. Define the one-sided lower confidence bound (LCB) Θ bα,n LCBα,n := R (Q∥P ) − εn (δCI ). Then with probability at least 1 − δCI over the samples, Θ Rα (Q∥P ) ≥ LCBα,n .

Consequently, for any claimed Rényi-DP level ρ ≥ 0 (at order α), the following auditing test is valid: Θ Reject the null H0 : Rα (Q∥P ) ≤ ρ

if LCBα,n > ρ.

This test has Type-I error at most δCI : sup

P LCBα,n > ρ ≤ δCI .

Θ (Q∥P )≤ρ (P,Q): Rα

Moreover, this yields a conservative (ε, δ)-DP violation certificate: for any target δ ∈ (0, 1), define 1 1 α−1 εLCB (δ) := LCBα,n + log . α α δ Then, with probability at least 1−δCI , the mechanism M cannot satisfy (ε, δ)-DP for any ε < εLCB (δ); equivalently, if ε < εLCB (δ), then M violates (ε, δ)-DP. Proof. The first claim is immediate from Theorem 3.2: with probability at least 1 − δCI , Θ Θ bα,n R (Q∥P ) − Rα (Q∥P ) ≤ εn (δCI ), Θ Θ bα,n which rearranges to Rα (Q∥P ) ≥ R (Q∥P ) − εn (δCI ) = LCBα,n . Θ Θ For the hypothesis test, under the null H0 we have Rα (Q∥P ) ≤ ρ. On the event {Rα (Q∥P ) ≥ LCBα,n } (which holds with probability at least 1 − δCI ), the inequality LCBα,n > ρ cannot occur. Hence Θ PH0 LCBα,n > ρ ≤ P Rα (Q∥P ) < LCBα,n ≤ δCI .

For the (ε, δ)-DP violation certificate, recall the standard implication: if a mechanism is ρ-RDP at order α > 1, i.e. Rα (Q∥P ) ≤ ρ for all neighboring pairs, then it is also (ε, δ)-DP with ε=ρ+

log(1/δ) . α−1

Equivalently (contrapositive), if for some neighboring (P, Q) we have Rα (Q∥P ) > ε −

log(1/δ) , α−1

then the mechanism violates (ε, δ)-DP. Applying this contrapositive with the class-restricted diverΘ gence and the lower bound Rα (Q∥P ) ≥ LCBα,n shows that on the same high-probability event, whenever log(1/δ) , LCBα,n > ε − α−1 the mechanism cannot satisfy (ε, δ)-DP. Rearranging gives the stated threshold ε < LCBα,n +

log(1/δ) . α−1

Theorem B.6 (Lower bound matching Theorem B.4 up to log factors). Fix α ∈ R>0 \ {1}. There exist constants c, c0 , c1 > 0, depending only on α, such that the following holds. For every sufficiently large d, there exist a measurable space Ω, a parameter set Θ ⊂ Rd , a critic class {Tθ : Ω → R}θ∈Θ , and a family of distribution pairs Pd = {(P, Qu ) : u ∈ Ud } such that: ∥θ∥2 ≤ 1,

|Tθ (z)| ≤ 1,

|Tθ (z) − Tθ′ (z)| ≤ c0 ∥θ − θ′ ∥2

for all θ, θ′ ∈ Θ and all z ∈ Ω, and the following minimax lower bound holds. Let h i 1 h i 1 VP,Q (θ) = log EQ e(α−1)Tθ (X) − log EP eαTθ (Y ) . α−1 α For any estimator Vbn : Θ → R based on n i.i.d. samples from Q and n i.i.d. samples from P , 1 inf sup Pr sup Vbn (θ) − VP,Q (θ) ≥ ε ≥ bn (P,Q)∈Pd P,Q θ∈Θ 4 V whenever

Proof. We prove the result by a Fano reduction from multi-way hypothesis testing [10]. The construction is chosen so that the population DV objective θ 7→ VP,Q (θ) encodes a hidden d-bit vector, while the KL divergence between the corresponding sample distributions remains of order nε2 [2]. This yields the desired d/ε2 lower bound. Step 1: A balanced packing. Let d be even. (For odd d, apply the construction in dimension d − 1 and embed it into Rd by adding one unused coordinate; this changes constants only.) By the Gilbert–Varshamov bound restricted to the middle slice of the hypercube [27], there exists a set Ud ⊆ {−1, +1}d such that every u ∈ Ud is balanced, d X

ui = 0,

i=1

and |Ud | ≥ exp(cVG d), for a universal constant cVG > 0, and for every distinct u, v ∈ Ud , 3d d ≤ dH (u, v) ≤ . 4 4 Equivalently, writing d 1X ρ(u, v) := ui vi , d i=1 we have ρ(u, u) = 1,

ρ(u, v) ≤

1 2

for all u ̸= v.

Indeed, since 2dH (u, v) , d the lower bound dH (u, v) ≥ d/4 gives ρ(u, v) ≤ 1/2. ρ(u, v) = 1 −

Step 2: Parameter set and critic class. Let u Θ := θu := √ : u ∈ Ud ⊂ Rd . d Then ∥θu ∥2 = 1 for every u ∈ Ud . Let the sample space be Ω := {1, 2, . . . , d}. Fix a constant τ ∈ (0, 1], to be chosen sufficiently small depending only on α. For θu ∈ Θ, define Tθu (i) := τ ui , i ∈ Ω. Then |Tθu (i)| ≤ τ ≤ 1. We next verify Lipschitzness. For distinct u, v ∈ Ud , |Tθu (i) − Tθv (i)| = τ |ui − vi | ≤ 2τ. On the other hand, 2 p 1 dH (u, v) ≥ 1, ∥θu − θv ∥2 = √ ∥u − v∥2 = √ d d because dH (u, v) ≥ d/4. Therefore |Tθu (i) − Tθv (i)| ≤ 2τ ∥θu − θv ∥2 . Thus the critic class is Lipschitz on Θ with constant L = 2τ , and has K = 1, M = τ , all absolute constants. Since the theorem only needs a critic class indexed by Θ, no extension outside Θ is required. If one wants Θ to be a full subset with an extension to all of Rd , one may apply the McShane extension theorem [29, 35] pointwise in i, preserving the same Lipschitz constant and boundedness after clipping. Let P be the uniform distribution on Ω: 1 P (i) = , i = 1, . . . , d. d For each hidden vector u ∈ Ud , define Qu by 1 + δui Qu (i) := , i = 1, . . . , d, d where 0 < δ ≤ 1/2. Since u is balanced, Step 3: A family of distributions.

d X i=1

Qu (i) =

d d 1X δX (1 + δui ) = 1 + ui = 1. d i=1 d i=1

Moreover, Qu (i) > 0 for all i, so Qu is a valid probability distribution. The statistical experiment associated with u consists of n i.i.d. samples from Qu and n i.i.d. samples from the fixed distribution P . The samples from P carry no information about u, but they are included to match the DV estimation setting. 20

Step 4: Compute the DV functional. Fix u, v ∈ Ud . We evaluate the DV objective under the pair (P, Qu ) at the critic θv . Write a := (α − 1)τ. First, d h i X 1 + δui avi EQu e(α−1)Tθv (X) = e . d i=1 Because v is balanced, d ea + e−a 1 X avi e = = cosh(a). d i=1 2 Also, d d 1X 1X ui eavi = ui cosh(a) + vi sinh(a) . d i=1 d i=1 P Since u is balanced, i ui = 0, so d d 1X 1X ui eavi = sinh(a) ui vi = sinh(a)ρ(u, v). d i=1 d i=1

Therefore

h i EQu e(α−1)Tθv (X) = cosh(a) + δ sinh(a)ρ(u, v).

Similarly, with b := ατ, we have

d h i 1X EP eαTθv (Y ) = ebvi = cosh(b), d i=1 again because v is balanced. Hence 1 1 Vu (θv ) := VP,Qu (θv ) = log(cosh(a) + δ sinh(a)ρ(u, v)) − log cosh(b). α−1 α The second term is independent of both u and v. Thus separation of the DV objective is controlled by the first term.

Step 5: Separation of the correct critic. Define 1 F (r) := log(cosh(a) + δ sinh(a)r) , r ∈ [−1, 1]. α−1 For δ ≤ 1/2, the argument of the logarithm is strictly positive, provided τ is fixed. Differentiating gives δ sinh(a) F ′ (r) = . (α − 1) (cosh(a) + δ sinh(a)r) Since a = (α − 1)τ , the quantity sinh(a) α−1 is positive for every α ̸= 1. Therefore F is increasing in r. Moreover, because τ is a fixed constant depending only on α, and δ ≤ 1/2, there exists a constant cα > 0, depending only on α and τ , such that F ′ (r) ≥ cα δ for all r ∈ [−1, 1]. Indeed, the denominator is bounded above and below by positive constants depending only on α and τ. For the true index u, we have ρ(u, u) = 1. For any distinct v ∈ Ud , we have ρ(u, v) ≤ 1/2. Therefore cα Vu (θu ) − Vu (θv ) = F (1) − F (ρ(u, v)) ≥ F (1) − F (1/2) ≥ δ. 2 Let cα ∆ := δ. 2 Then, for every u ∈ Ud , Vu (θu ) ≥ max Vu (θv ) + ∆. v̸=u

Suppose an estimator Vbn : Θ → R satisfies ∆ sup |Vbn (θ) − Vu (θ)| < . 4 θ∈Θ

Step 6: Uniform estimation implies decoding.

Define the decoder

u b ∈ arg max Vbn (θv ). v∈Ud

Then u b = u. To see this, for every v ̸= u, ∆ ∆ 3∆ ∆ ≥ Vu (θv ) + ∆ − = Vu (θv ) + ≥ Vbn (θv ) + . Vbn (θu ) ≥ Vu (θu ) − 4 4 4 2 u b Thus θ is the unique maximizer of Vn over the packing points. Consequently, ∆ b Pr(b u ̸= u) ≤ Pr sup |Vn (θ) − Vu (θ)| ≥ . u u θ∈Θ 4 Step 7: KL control.

We next bound the KL divergence between two hypotheses. For u, v ∈ Ud , d X 1 + δui 1 + δui DKL (Qu ∥Qv ) = log . d 1 + δvi i=1

Since both u and v are balanced, the number of coordinates with (ui , vi ) = (1, −1) equals the number of coordinates with (ui , vi ) = (−1, 1). Let this number be m. Then dH (u, v) = 2m. Hence 1+δ m 1−δ m + (1 − δ) log . DKL (Qu ∥Qv ) = (1 + δ) log d 1−δ d 1+δ Therefore 1+δ 2mδ log . DKL (Qu ∥Qv ) = d 1−δ For 0 < δ ≤ 1/2, 1+δ log ≤ Cδ, 1−δ so m DKL (Qu ∥Qv ) ≤ Cδ 2 ≤ Cδ 2 . d Applying this coordinatewise gives dH (u, v) DKL (Qu ∥Qv ) ≤ Cδ 2 ≤ Cδ 2 . d The full observation law under u is ⊗n Pu = Q⊗n . u ⊗P Since P is the same under all hypotheses, DKL (Pu ∥Pv ) = nDKL (Qu ∥Qv ) ≤ Cnδ 2 . Step 8: Fano’s inequality. Let U be uniformly distributed on Ud , and let the samples be drawn according to PU . By the KL bound above, X 1 I(U ; samples) ≤ DKL (Pu ∥Pv ) ≤ Cnδ 2 . |Ud |2 u,v∈Ud

b, Fano’s inequality [10] gives, for every decoder U b ̸= U ) ≥ 1 − I(U ; samples) + log 2 . Pr(U log |Ud | Since log |Ud | ≥ cVG d, if 1 Cnδ 2 + log 2 ≤ cVG d, 2 then b ̸= U ) ≥ 1 . Pr(U 2 In particular, there exists a universal constant c′ > 0 such that if d n ≤ c′ 2 , δ then every decoder has error probability at least 1/2. 22

Step 9: Convert testing hardness into estimation hardness. 8ε δ := . cα

Set

For ε ≤ c1 , with c1 > 0 sufficiently small depending only on α, this choice satisfies δ ≤ 1/2. With this choice, 1 cα cα δ ∆ = · δ= = ε. 4 4 2 8 Suppose, for contradiction, that there exists an estimator Vbn such that 1 b sup Pr sup |Vn (θ) − Vu (θ)| ≥ ε < . u 4 u∈Ud θ∈Θ Then the decoder

u b ∈ arg max Vbn (θv ) v∈Ud

would satisfy sup Pr(b u ̸= u) <

u∈Ud u

1 , 4

contradicting Fano’s inequality whenever c2 d d n ≤ c′ 2 = c′ α 2 . δ 64 ε Absorbing constants into c > 0, we obtain 1 d b n ≤ c 2 =⇒ inf sup Pr sup |Vn (θ) − Vu (θ)| ≥ ε ≥ . u bn u∈Ud ε 4 θ∈Θ V This is the desired lower bound. Remark B.7 (Tightness of Theorem B.4). Theorem B.4 shows that the leading d/ε2 sample complexity in Theorem 3.2 is minimax-optimal for class-restricted DV Rényi estimation, up to logarithmic factors coming from covering/metric entropy. B.4

Group Privacy and Multiple Canaries

One can have multiple canaries in our auditing set up such that the datasets we input into the mechanism have a distance greater than one. In this case, we follow the group privacy result from [30]: Proposition B.8 (Proposition 2 in [30]). If f : D → R is (α, ε)-RDP; g : D′ → D is 2c -stable and α ≥ 2c+1 , then f ◦ g is (α/2c , 3c ε)-RDP. Lemma B.9. For each M and a fixed α > 1, let AM ∈ Ω be a random variable and let PM ∈ R be a fixed number. For each ε, β > 0, let Tε,α,β ⊂ Ω satisfy ∀M PM = ε =⇒ P AM ∈ Tε,α,β ≤ β . (6) Further suppose that, if ε1 ≤ ε2 , then Tε1 ,α,β ⊃ Tε2 ,α,β . Then, for all M and all β > 0, Pr{ PM ≥ sup{ε > 0 : AM ∈ Tε,α,β }} ≥ 1 − β.

(7)

Proof. We follow a very similar proof as outlined in Lemma 4.7 of [34], just using the monotonicity of RDP and subsequently the null hypothesis’s rejection region. Fix an output of AM and let PM < sup{ε > 0 : AM ∈ Tε,α,β }. Then there is a ε ≥ PM with AM ∈ Tε,α,β , and therefore [ AM ∈ Tε,α,β = TPM ,α,β . (8) ε≥PM

By monotonicity of the rejection region. Thus, Pr[PM < sup{ε > 0 : AM ∈ Tε,α,β }] ≤ Pr AM ∈ TPM ,α,β ≤ β. For the above to hold, we assume that α > 1 is fixed. 23

(9)

Figure 2: Graph for auditing at α = 1.25 for CIFAR-10 and MNIST datasets on a CNN

Figure 3: Graph for auditing at α = 2.0 for CIFAR-10 and MNIST datasets on a CNN

Additional Experimental Results

This section in the appendix provides additional interpretation of the experimental results reported in Section 4 (in main body) and the accompanying figures. The primary purpose of these experiments is not to propose a new attack on DP-SGD, but rather to validate the theoretical auditing guarantees developed in Section 3 and 4 under realistic machine learning workloads. In particular, the experiments are designed to answer the following questions: • Do DV-based Rényi divergence estimators produce empirically meaningful lower bounds on privacy loss [2]? • How closely do empirical audits track the theoretically claimed RDP guarantees? • How does estimator choice affect auditing accuracy, especially at small privacy budgets? Across all datasets and models, the experimental findings are consistent with the predictions of our theory. It took around 100 GPU hours on A100 to audit an model trained on MNIST data and 500 GPU hours for a model trained on CIFAR-10 data. Worst-case initializations. A recurring theme in prior work is that DP-SGD privacy guarantees must hold even for adversarially chosen initial parameters. To stress-test our auditing framework, we therefore follow the experimental protocol of [5, 31] and evaluate models initialized using worstcase pretraining strategies. All of our experiments occur in this setting. Despite the adversarial initialization, the DV-based Rényi estimator consistently produces nontrivial lower bounds that closely track the claimed theoretical privacy levels. This behavior is particularly notable at smaller values of ε, where auditing is statistically most challenging. These results empirically corroborate the distribution-free lower confidence bounds established in our theory and demonstrate that our estimator remains stable even under worst-case conditions. Comparison of estimators. We compare the following approaches to estimating Rényi divergence from observed losses: (i) our DV-based variational estimator, (ii) nearly tight black-box auditing results from prior work. 24

Table 3: Empirical RDP audits at α = 1.25. Same as in Section 4 Dataset

Target εα

SOTA black-box [31]

DV-Rényi

MNIST

0.15625 0.625 1.25 2.5 6.25

0.056 ± 0.025 0.272 ± 0.020 0.588 ± 0.016 1.256 ± 0.091 3.325 ± 0.218

0.115 ± 0.080 0.469 ± 0.197 0.995 ± 0.289 2.239 ± 0.473 3.884 ± 0.327

CIFAR-10

0.15625 0.625 1.25 2.5 6.25

0.031 ± 0.004 0.289 ± 0.050 0.693 ± 0.082 1.539 ± 0.234 4.128 ± 0.336

0.118 ± 0.025 0.551 ± 0.056 1.095 ± 0.120 2.248 ± 0.344 4.577 ± 0.430

Table 4: Empirical RDP audits at α = 1.25, with Dataset size: 100 samples. Dataset

Target εα

SOTA black-box [31]

DV-Rényi

MNIST

0.15625 0.625 1.25 2.5 6.25

0.086 ± 0.042 0.506 ± 0.124 0.875 ± 0.075 1.921 ± 0.249 4.685 ± 0.370

0.152 ± 0.061 0.184 ± 0.029 0.172 ± 0.014 0.176 ± 0.011 0.177 ± 0.006

CIFAR-10

0.15625 0.625 1.25 2.5 6.25

0.036 ± 0.010 0.323 ± 0.039 0.730 ± 0.085 1.631 ± 0.179 4.341 ± 0.368

0.147 ± 0.034 0.486 ± 0.053 0.649 ± 0.052 0.767 ± 0.045 0.848 ± 0.045

Across all experiments, the DV-based estimator achieves a favorable balance between bias and variance. While prior black-box methods can be overly conservative at small ε, the DV estimator yields tighter empirical lower bounds that remain statistically valid for low ε. This behavior is especially pronounced in the low-ε regime, where small estimation errors translate into large relative differences in privacy guarantees. These trends are consistent with our finite-sample analysis, which predicts that the DV estimator can achieve near-optimal accuracy given a sufficiently expressive critic class.

C.1

DV Rényi Model

In our auditing procedure we use a DV Rényi model to calculate a divergence estimate that serves as an empirical RDP estimate. For this model, consider a dataset (consisting of final model losses trained with DP-SGD) with size n. Our neural networks use two intermediate layers of 100 nodes. At α = 1.25, we use 750 epochs and lr = 7e-5 for CIFAR-10 and 500 epochs with lr = 2e-4 for MNIST, and a batch size of 400. We use an EMA rate of 0.99 and our neural network is structured with two intermediate layers of 100 nodes with a ReLU activation function. 400 (80%) of the loss samples are used in the training set and the last 100 (20%) of the loss samples are used in the validation set. We scale our DV estimate Rα by α so Dα = αRα . At α = 2, all the parameters are the same besides a slight decrease of the iterative learning, setting lr = 1.25e-4 for MNIST and 350 training epochs for CIFAR-10. As α increases, the model becomes increasingly sensitive and overall learning of the model needs to be decreased to avoid high MSE due to the divergence’s exponential nature. To apply our theorems to our experimental settings and results, consistency results for our neural networks satisfying Theorem 3.2, Theorem B.6 can be found in [8]. 25

Table 5: Empirical RDP audits at α = 1.25, with Dataset size: 1000 samples. Dataset

Target εα

SOTA black-box [31]

DV-Rényi

MNIST

0.15625 0.625 1.25 2.5 6.25

0.095 ± 0.057 0.493 ± 0.104 0.863 ± 0.104 1.844 ± 0.154 4.478 ± 0.310

0.155 ± 0.068 0.185 ± 0.034 0.167 ± 0.015 0.172 ± 0.009 0.174 ± 0.007

CIFAR-10

0.15625 0.625 1.25 2.5 6.25

0.031 ± 0.004 0.289 ± 0.050 0.693 ± 0.082 1.539 ± 0.234 4.128 ± 0.336

0.118 ± 0.025 0.551 ± 0.056 1.095 ± 0.120 2.248 ± 0.344 4.577 ± 0.430

Table 6: Empirical RDP audits at α = 1.25, with Max grad norm: 0.1.

C.2

Dataset

Target εα

SOTA black-box [31]

DV-Rényi

MNIST

0.15625 0.625 1.25 2.5 6.25

0.084 ± 0.044 0.340 ± 0.058 0.729 ± 0.071 1.592 ± 0.139 4.076 ± 0.357

0.147 ± 0.084 0.394 ± 0.074 0.475 ± 0.052 0.512 ± 0.036 0.524 ± 0.025

CIFAR-10

0.15625 0.625 1.25 2.5 6.25

0.046 ± 0.031 0.301 ± 0.032 0.758 ± 0.082 1.628 ± 0.126 4.342 ± 0.329

0.138 ± 0.023 0.556 ± 0.062 1.018 ± 0.130 1.369 ± 0.142 1.692 ± 0.059

Tightness lost in GDP to RDP conversions

A concern when comparing RDP audits to prior black-box auditing methods is that converting an audit through intermediate privacy notions can introduce unnecessary slack. In particular, [31] produces a binary classifier that distinguishes whether a model was trained on dataset D or its neighboring dataset D′ . This classifier is summarized by its true-positive rate TPR and false-positive rate FPR, which can then be used to estimate a µ-GDP lower bound. However, converting this estimate to GDP and then to RDP may lose tightness. Therefore, we evaluate a direct RDP baseline from the binary attack itself. The binary distinguisher induces two Bernoulli distributions: one corresponding to the attack output under D, with success probability TPR, and one corresponding to the attack output under D′ , with success probability FPR. Therefore, instead of passing through an intermediate GDP estimate, we directly compute the order-α Rényi divergence ε̂ = Dα (Bern(TPR) ∥ Bern(FPR)) . Although this provides a more direct RDP lower bound, the Bernoulli distributions from TPR and FPR are not robust to Rényi divergence estimation, shown in Table 13.

Table 7: Empirical RDP audits at α = 1.25, with Max grad norm: 10.0. Dataset

Target εα

SOTA black-box [31]

DV-Rényi

MNIST

0.15625 0.625 1.25 2.5 6.25

0.001 ± 0.001 0.033 ± 0.026 0.035 ± 0.022 0.035 ± 0.016 0.059 ± 0.028

0.006 ± 0.007 0.098 ± 0.112 0.070 ± 0.086 0.118 ± 0.074 4.764 ± 9.191

CIFAR-10

0.15625 0.625 1.25 2.5 6.25

0.002 ± 0.001 0.065 ± 0.030 0.191 ± 0.012 0.652 ± 0.035 2.445 ± 0.130

0.005 ± 0.009 0.166 ± 0.092 0.456 ± 0.118 1.657 ± 0.275 5.577 ± 2.545

Table 8: Empirical RDP audits at α = 2, same as in Section 4. Dataset

Target εα

SOTA black-box [31]

DV-Rényi

MNIST

0.25 1.0 2.0 4.0 10.0

0.089 ± 0.040 0.436 ± 0.032 0.940 ± 0.025 2.010 ± 0.145 5.320 ± 0.349

0.202 ± 0.142 0.867 ± 0.339 1.527 ± 0.325 2.127 ± 0.250 2.650 ± 0.159

CIFAR-10

0.25 1.0 2.0 4.0 10.0

0.050 ± 0.007 0.463 ± 0.080 1.109 ± 0.131 2.463 ± 0.374 6.605 ± 0.538

0.206 ± 0.041 0.953 ± 0.213 1.624 ± 0.178 2.250 ± 0.200 2.751 ± 0.170

Table 9: Empirical RDP audits at α = 2, with Dataset size: 100 samples. Dataset

Target εα

SOTA black-box [31]

DV-Rényi

MNIST

0.25 1.0 2.0 4.0 10.0

0.138 ± 0.067 0.810 ± 0.198 1.399 ± 0.120 3.074 ± 0.398 7.496 ± 0.592

0.407 ± 0.335 1.512 ± 0.662 1.910 ± 0.390 2.360 ± 0.294 2.796 ± 0.150

CIFAR-10

0.25 1.0 2.0 4.0 10.0

0.058 ± 0.015 0.517 ± 0.063 1.169 ± 0.136 2.609 ± 0.286 6.945 ± 0.589

0.257 ± 0.048 1.138 ± 0.128 1.829 ± 0.098 2.322 ± 0.146 2.845 ± 0.185

Table 10: Empirical RDP audits at α = 2, with Dataset size: 1000 samples. Dataset

Target εα

SOTA black-box [31]

DV-Rényi

MNIST

0.25 1.0 2.0 4.0 10.0

0.151 ± 0.091 0.789 ± 0.166 1.380 ± 0.166 2.950 ± 0.246 7.165 ± 0.495

0.381 ± 0.262 1.272 ± 0.427 1.822 ± 0.338 2.218 ± 0.242 2.618 ± 0.171

CIFAR-10

0.25 1.0 2.0 4.0 10.0

0.050 ± 0.007 0.463 ± 0.080 1.109 ± 0.131 2.463 ± 0.374 6.605 ± 0.538

0.206 ± 0.041 0.953 ± 0.213 1.624 ± 0.178 2.250 ± 0.200 2.751 ± 0.170

Table 11: Empirical RDP audits at α = 2, with Max grad norm: 0.1. Dataset

Target εα

SOTA black-box [31]

DV-Rényi

MNIST

0.25 1.0 2.0 4.0 10.0

0.134 ± 0.070 0.543 ± 0.094 1.166 ± 0.114 2.548 ± 0.222 6.522 ± 0.571

0.175 ± 0.070 0.265 ± 0.038 0.284 ± 0.028 0.292 ± 0.022 0.296 ± 0.012

CIFAR-10

0.25 1.0 2.0 4.0 10.0

0.073 ± 0.050 0.481 ± 0.052 1.212 ± 0.131 2.604 ± 0.202 6.947 ± 0.527

0.186 ± 0.028 0.304 ± 0.017 0.329 ± 0.011 0.342 ± 0.007 0.349 ± 0.002

Table 12: Empirical RDP audits at α = 2, with Max grad norm: 10.0. Target εα

Dataset

MNIST

CIFAR-10

SOTA black-box [31]

DV-Rényi

0.25 1.0 2.0 4.0

0.001 ± 0.002 0.052 ± 0.042 0.056 ± 0.035 0.056 ± 0.025

0.014 ± 0.011 0.164 ± 0.184 0.131 ± 0.148 0.210 ± 0.175

0.25 1.0 2.0 4.0

0.004 ± 0.002 0.104 ± 0.049 0.306 ± 0.019 1.044 ± 0.056

0.012 ± 0.019 0.324 ± 0.192 2.200 ± 2.979 6.983 ± 3.233

Table 13: Comparison of empirical RDP lower bounds at α = 2, with a direct ε̂ = Dα (Bern(TPR)∥Bern(FPR)) estimate for previous SOTA. Theor. ε at α = 2

ε̂ = Dα (Bern(TPR)∥Bern(FPR))

ε̂-RDP DV

CIFAR-10

0.25 1.0 2.0 4.0 10.0

0.097 ± 0.059 0.375 ± 0.11 0.685 ± 0.124 1.097 ± 0.134 1.446 ± 0.239

0.206 ± 0.041 0.953 ± 0.213 1.624 ± 0.178 2.25 ± 0.2 2.751 ± 0.17

MNIST

0.25 1.0 2.0 4.0 10.0

0.115 ± 0.064 0.35 ± 0.115 0.618 ± 0.135 1.022 ± 0.14 1.444 ± 0.186

0.202 ± 0.142 0.867 ± 0.339 1.527 ± 0.325 2.127 ± 0.25 2.65 ± 0.159

Dataset

Record · ID 216730 · SHA-256 fe2e588e3dce71b1
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.