Sequentially Auditing Differential Privacy
Authors: Tomás González
Mateo Dulce Rubio
Aaditya Ramdas
Mónica Ribero
Venue: NeurIPS 2025 poster ()
Keywords: Differential privacy
testing by betting
Primary area: social_and_economic_aspects_of_machine_learning
TL;DR: We propose a sequential test for auditing differential privacy that detects violations with sample sizes that are orders of magnitude smaller than existing methods.

Abstract: We propose a practical sequential test for auditing differential privacy guarantees of black-box mechanisms. The test processes streams of mechanisms' outputs providing anytime-valid inference while controlling Type I error, overcoming the fixed sample size limitation of previous batch auditing methods. Experiments show this test detects violations with sample sizes that are orders of magnitude smaller than existing methods, reducing this number from 50K to a few hundred examples, across diverse realistic mechanisms. Notably, it identifies DP-SGD privacy violations in \textit{under} one training run, unlike prior methods needing full model training.

Sequentially Auditing Differential Privacy
Tomás González
Mateo Dulce Rubio New York Universiy mateo. d@nyu edu
Carnegie Mellon University tcgonzal Gandrew..n cmu. edu
Aaditya Ramdas Carnegie Mellon University ar arandasocs. cmu. edu
Mónica Ribero
Google Research mribero@google. com
Abstract
We propose a practical sequential test for auditing differential privacy guarantees of black-box mechanisms. The test processes streams of mechanisms' outputs providing anytime-valid inference while controlling Type error, overcoming the fixed sample size limitation of previous batch auditing methods. Experiments show this test detects violations with sample sizes that are orders of magnitude smaller than existing methods, reducing this number from 50K a few hundred examples, across diverse realistic mechanisms. Notably, it identifies DP-SGD privacy violations in under one training run, unlike prior methods needing full model training.
Introduction
Auditing privacy guarantees of algorithms that process sensitive data, prevalent in domains like finance, healthcare, and users' behavior on the web, is crucial for building and deploying reliable and trustworthy software. While rigorous privacy protections like Differential Privacy (DP) [15] have been adopted by industry [3, 20, 41] and government agencies [48], the promised theoretical guarantees rely on both correct algorithmic design (e.g., avoiding flaws errors mathematical proofs, like those demonstrated with the Sparse Vector Technique [30]) and correct implementation, where subtle bugs can compromise privacy (e.g., missing constants, incorrect sampling, or fixed seeds). Furthermore, theoretical privacy parameters and ó often represent worst-case upper bounds, motivating the need for empirical privacy auditing to assess practical privacy leakage and gain intuition about algorithms' vulnerabilities [33].
Auditing privacy be framed statistical hypothesis test: distinguishing the null hypothesis Ho: "the algorithm satisfies claimed privacy guarantec", from the alternative H1; "the algorithm violates the claimed privacy guarantee". Current approaches this testing problem generally fall into two categories, each with significant drawbacks. First, parametric tests can achieve high statistical power but rely strong, often unverifiable, assumptions about the specific workings and output distribution of the mechanism or the specific flaw [33, 16]. Second, black-box tests, where the auditor observes only the mechanism's 's outputs without knowledge of internal functioning, make fewer assumptions but requires an unknown and typically large number of samples to draw statistically meaningful conclusions [5, 26). This makes them impractical for auditing complex, resource-intensive algorithms such as differentially private stochastic gradient descent (DP-SGD), where obtaining even one sample often requires significant computation (e.g., backpropagation through millions of model parameters).
In this paper, we propose a new framework for approximate DP auditing that leverages recent advances in sequential hypothesis testing to overcome these limitations. Our approach uses e-values
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

[39], non-negative random variables that (when multiplied) sequentially accumulate evidence against the null hypothesis. Under the null Ho, the expectation of an e-value is bounded by 1; under the alternative H1. well-designed (products of) e-values can grow exponentially fast, allowing for early stopping and efficient detection of privacy violations. This sequential methodology allows testing to proceed adaptively: samples are collected and evaluated iteratively, and the test stops as soon as significance level a is reached. Notably, sequential tests automatically adapt to the unknown sample complexity of the problem, eliminating the need to fix the test's sample size priori and avoiding unnecessary computation.
Our specific test statistics are built upon the Maximum Mean Discrepancy (MMD) [19]. powerful kernel-based metrie for comparing probability distributions. MMD is particularly well-suited for the two-sample tests emerging in privacy auditing, as bounds on MMD can be easily translated to approximate DP parameters [26]. Further, MMD highly flexible. It can incorporate prior knowledge in white-box settings-with access to intermediate gradients or the noise distribution family-on or, as our experiments show, operate effectively in a black-box manner.
The main contributions of this work are summarized as follows:
We introduce new general MMD-based one-sided sequential testing framework. As key application, we instantiate this framework for auditing approximate DP mechanisms (see Section 3). Our method enables anytime valid inference while controlling Type I error, eliminating the need for pre-defined test sample sizes, and ensuring a bounded expected stopping time under the alternative. We establish these theoretical guarantees in Theorems 3.2 and 3.3.
We present a new connection between MMD and Hockey-Stick divergence in Theorem 3.1 that allows for the translation of MMD-based hypothesis tests to approximate DP auditing tests. The connection presented is tighter than previous bounds, increasing test power. Our experiments show that previous tests requiring hundreds of thousands of samples while still failing to reject, now reject with under a thousand samples.
We validate our methods on common DP mechanisms with Gaussian and Laplace noise. We further demonstrate efficacy auditing benchmark algorithms [26, 5] and provide results for the challenging case of DP-SGD [1, 46), showcasing the practical benefits of early failure detection enabled by our sequential approach.
Related work. At the core of approximate DP auditing is the estimation of the effective privacy loss from samples of the mechanism. There is substantial prior work on this, primarily situated within the batch setting, where fixed number of samples drawn [18, 12, 14, 11, 35, 28, 29]. Also in the batch setting, a significant body of work specializes on auditing machine learning models, particularly those trained with DP-SGD. This includes membership inference attacks (MIA) [24, 37, 7, 23, 33] and data reconstruction attacks [21, 4, 31].
Our approach relies sequential testing with kernel methods, specifically the Maximum Mean Discrepancy (MMD) [19], to construct test statistics. Prior work on privacy auditing has also used kernel methods, such estimating regularized kernel Rényi divergence [13], but often requires strong assumptions (e.g., knowledge of covariance matrices) impractical in black-box settings or for mechanisms beyond Gaussian Laplace.
To the best of our knowledge, applying modern sequential hypothesis testing techniques, particularly those based on e-values test supermartingales [43, 38], to the general problem of black-box DP auditing is novel. However, sequential testing by betting ideas have been successfully applied for auditing in other settings like elections [52], finance [45], fairness [8], and language models [40]. The most closely related work is [40] as they also propose a one-sided test, although for detecting distribution shifts in language models. While their setting is similar, their testing procedure differs from ours in key ways, allowing us to establish results they do not such as bounds on the expected number of samples until rejection under the alternative. We elaborate on these differences in Section 3.2.
In Appendix H we discuss in detail more references and how they compare to our work.

---

2 Preliminaries
Throughout the paper we let D C URd be set of datasets; datasets D D have a finite but arbitrary number of p-dimensional records. denote by A D + X randomized mechanisms that map datasets to range X. We say that S, E 'D are neighboring datasets (denoted by ~ 5") if they differ by at most one data point. While our framework is agnostic to the definition of "neighboring", for simplicity (and in experiments) framework, where S' can be obtained by adding or removing exactly one record from Given a reproducing kernel Hilbert space (RKHS) H. let OH E H be the constant zero function.
Notation.
assume S ~ S' in the add/remove
Definition 2.1. The Hockey-Stick divergence between and Q (of order e is the f-divergence with f(z) = max (0, }.}. Specifically,
[ ((p)))
(
De (PII)) = Eq
Definition 2.2 (Approximate Differential Privacy [15]). A randomized algorithm A: D + X' is (s, 8) differrentil private if for any pair of neighboring datasets S and S and any event & C X, P[A(S) E E] & (FP((((") E] + ô. Equivalently, De (A(S) A(S') S 6.
The sequential tests we propose require estimating the wimnes function for a given divergence of interest. Intuitively, this witness function can be thought as the function that highlights the maximum difference between two distributions as measured by the underlying divergence. The definition of approximate DP uses the Hockey-Stick divergence, whose witness function is not very easy to work with as it can be highly non-smooth. Instead, we will use the MMD as a notion of the distance between the distributions A(S) and A(S'), and leverage the connection of MMD to approximate DP introduced in Theorem 3.1.
Definition 2.3. Let H. be a reproducing kernel Hilbert space with domain X and kernel K(:;) such that K (xx, x) S 1 for all x E X. Given two distributions P, Q supported on X, define
MMD(P, Q)
sup I
Exx-
The solution f* achieving the supremum called the wimess function..
Below, we introduce a definition and a theorem from the literature of supermartingales which are key to the design and analysis of our sequential tests.
Definition 2.4 (Nonnegative supermartingale). An integrable stochastic process (Ke)e20 a non- negative supermartingale if K., 2 0 and B[K,, K,,...,K,,lll S Kr-11 where the inequalities are meant in an almost sure sense.
Theorem 2.1 (Ville's inequality [49]). For any nonnegative supermartingale (Kr and a > O, P(3 0: Kr 1/a] S al[[Ko).
3 Sequential Auditing
This section formalizes the proposed auditing by betting framework. We start by formally introducing the problem statement and continue by introducing an MMDD-ased test statistic. Subsequently, we develop Algorithm 1, a sequential test for privacy auditing. We then provide formal guarantees on controlling Type I errоr uniformly over the null, and demonstrating exponential growth under the alternative, which implics a finite stopping time when detecting faulty algorithms. We conclude this section with comparative discussion of two subroutines within the main sequential algorithm.
Auditing DP can be seen as a two-step procedure: (1) identifying worst-case neighboring datasets S ~ 5" that maximize the discrepancy between the distributions A(S) and A(S"), and (2) testing whether the privacy guarantee holds for S' while controlling Type error at level a. this work we focus on the testing problem; that is, throughout the remainder of this work we assume the pair S' is fixed. While we do not require access to the worst-case pair S ~ S', the statistical power of our test increases with larger MMD(AA(S). A(S")) (see Theorem 3.3).
3

---

3.1 Problem statement
Definition 3.1. (Hockey-Stick approximate DP test) We consider an auditor that employs binary
hypothesis test & designed to evaluate whether an algorithm A satisfies the (c, apprroxiatt DP guarantee on neighboring datasets S S'. The test has access streams of i.i.d. observations
X = (X1,X2, .... ) lid A(S). Y Y2..) ~ A(S") from A evaluated on S and S', respectively. the following two hypotheses:
The goal of the test is to distinguish between the
Ho: Dec (A(S) || A(S')) S 6, H1: (A(() A(S")) 6.
The auditor rejects Ho when o(X, Y) and fails reject otherwise.
The Hockey-Stick divergence relies on the likelihood ratio of the potentially unknown distributions A(S) and A(S"); consequently, it can be very challenging in practice to develop high-power tests with reasonable number of samples [26] for the test described Definition 3.1. Theorem 3.1 below introduces tighter connection between the Hockey-Stick divergence and the MMD compared to previous bounds [26]. This tighter connection enables the development of an MMD-based hypothesis test for approximate differential privacy. The improved bound inherently increases the power of kernel-MMID-baset Hockey-Sticn tests (see Appendix A).
Theorem 3.1. (Improvement of [26] Theorem 4.13) Let H be a reproducing kernel Hilbert space with domain X and kernel ((.--) such that 0 < (xx y) S 1 for all v, E X. If mechanism A is (E, DDD,, then for any S ~ S'
MMD(A(S), S V2 11 11- 2(1 - ())
Theorem 3.1 offers a strict improvement over [26, Theorem 4.13]. Further, the new bound has the nice property of not becoming vacuous as E increases. In fact, it approaches v2 as E + oo, while the previous bound grows to infinity with ef.
Theorem 3.1 implies that if (AA)) > 22 vO(1 21--1 then A cannot be private.
In light of this, will focus the following test, which is based on the MMD instead of the Hockey-Stick divergence.
Definition 3.2. (MMD approximate DP test) Under the same conditions Desinition 3.1, let
T(,,5) == v2 (2-11-2111 2(1-6) We define the MMD-approximate DP test as the task of distinguishing
Ite'
between the following two hypotheses:
Ho: MMD(A(S) || A(S')) S T(,,)), H1: MMD(A(S) A(S)) > T(E,
Previous work on DP auditing often focuses on the fixed batch sample size case that proceeds as follows: Take n samples from on each dataset to obtain samples XI,.,, iid A(S) and Yi,.... Y, vid A(S'). Then these samples construct (1-a)-confidence interval for (
If the interval doesn't 't intersect [0, 6]. then we conclude with high probabil- ity that A is not (e, 6)-DP. This approach can be problematic: running can be computationally expensive in practice, so choosing an n that is too large can be infeasible or simply lead to wasted computational resources. Conversely, choosing an n that test, and samples often cannot be reused without decrease in statistical power.
small might result in an inconclusive
We begin by presenting abstract, potentially impractical test to build intuition, and then introduce the proposed practical sequential auditing framework in Algorithm
3.2 An abstract template for (D sequential testing
Theorem 3.2. Let f be the witness funnttion MMD(AA() A(S')) (as defined in Definition 2.3). sid
Given samples { (X,, YiJezı ~ ((S)))A(55)) and a fixed hyperparameter X > 0, define the stochastic
process (K7 (2) as follows:
- (;(A) K ( x (1 XX*(X)) (*)) T)),
where T(E, 8), defined Definition 3.2, represents the expected upper bound on MMD under the null hypothesis. Then it holds that:

---

0 ver- 1. Under the null hypothesis (Ho MMMD(A(()), - T(E, any d fo, 2 and any a E (0,1) we have P|sup:21 2 1/0] a
2. Under the alternative (H1 : MMD(A(S),
> T(e,,)). there exists a ((A2) almost surely. where
X" E 0. 814r(c.)) such that lim log (x')
4 MMD(A(()) -((,))
Theorem 3.2 suggests an algorithm that sequentially accumulates evidence to reject hypothesis Ho against H1. Unfortunately, this requires to know X and the witness function f In the following subsection, we show that X and f can be learned: X using Online Newton Step (ONS), and f from samples using Online Gradient Ascent (OGA); see Appendix E for more details on these algorithms.
Our approach builds upon the work in [44], and its application to our one-sided privacy au- diting test requires substantial and non-trivial modifications. Specifically, the test proposed in [44] inherently addresses a two-sided test with hypothesis Ho (MM
(MD((A())AA($)) > 0. Since the MMD is non-negative by definition, this ef- fectively corresponds testing Ho : (MD(A(S), = 0 against the two-sided alterna- tive H1 MMD(A(S), A(S") * O. In contrast, the privacy auditing setting needs a one- sided test against specific, non-zero threshold. A natural extension would lead to testing Ho MMD(A(S)), A(S))
sus H,
T(E,8) versus H1 MMD(A(S). A(S")) * T(E, 6), which is dif- ferent from the one-sided test with alternative H₃ MMM((((S) A(S")) > T(E,)). This distinction is critical because, unlike the zero-threshold null hypothesis, values of MMD below T(E, 6) are possi- ble and relevant to the null hypothesis. Consequently, a simple extension of the two-sided framework would result in an inappropriate two-sided alternative H1 MMD((A()) A(5") # r(e,)). 8).
Designing this one-sided test introduces significant analytical challenges. Concretely, we have to constrain À to be nonnegative to preserve the supermartingale property of the stochastic process KC; This restriction reduces the space of admissible À values and changes the analysis needed establish the existence of an optimal X that ensures that the process grows under the alternative hypothesis (part 2 of Theorem 3.2). We overcome this by proving the existence of such A within the restricted domain, which required non- con-trivial adaptations and subtle but key modifications of the original results presented in [44]. This structural modification is essential to ensure the validity and power of the one-sided sequential test. Finally, while the framework in [44] is designed for a broader class of testing problems, our focused analysis of this specific two-sample MMD test allows for the derivation of clearer and more interpretable bounds. By carefully working out the specific constants for our problem, we avoid reliance on the more abstract machinery in their general framework.
We are not the first to draw inspiration from [44] to design a one-sided test. Recently, [40] proposed one-sided test in the context of detecting behavioral shifts in language models for the hypotheses Ho: D(P Q) < versus H1 D(P, Q) > T for some T >> 0, where the distance function is defined as DIP, Q fer [Ex~P, x-) - f(Y)] and F is class of neural networks with scalar outputs in [-1/2, 1/2]. Their method also constructs a stochastic process that is a supermartingale under Ho and can grow under Hi, under several assumption on the neural network class, but it differs from ours in two key respects. First, they consider a single stochastic process &2, while we define a family KC; parameterized by À (see eq. (3)). This parameterization enables the practical test we introduce in Section 3.3 to adaptively tune À and approximate the optimal growth rate. Second, even when À is fixed, our process exhibits faster expected growth under H1. Specifically, if we were to adopt their approach for our one-sided test, we would obtain:
II
1+1/2 er/2
1
1 ((x))-(()))-
+
et/2
E=
where we denote T(E, as 7 for brevity. Under H1, the expected value of this process satisfies:
1/2 (1: eT/2
1
1
MMD
eT/2 -
7) <
MMD MMD-7) EH,
En, [Hd] =
+ 2
2 2+7
K
2+7
'Their process does not include the factors of 1/2 from our expression; we include them to standardize both settings, as work with function classes outputting in [-1, whereas theirs output in 1-1/2,
5

---

where the inequality follows from 1 + T/2 < E for > 0.
Finally, unlike our work, [40] does not analyze the expected growth of K. under H1, nor do they provide guarantees on the expected stopping time of their practical test, both of which establish in Theorems 3.2 and 3.3. We believe that these differences-namelle the design of different family of stochastic processes and the selection of x-are essential for deriving our theoretical guarantees.
3.3 Practical DP auditing
While intuitive, the test in Section 3.2 requires oracle access to and f*. We now instantiate practical algorithm inspired by the ideas developed in the previous subsection. Let's start assuming that we know f but want to learn X" we construct the process
Kp=1, - x (1 (x), - (*)) - T(E,))),
it is easy that by restricting the range of A in the proof of Theorem 3.2, KG is nonnegative supermartingale so long as X is predictable (i.e, choosen before observing X,, Y,), implying that, with high probability, Kū remains bounded over time under Ho. Next, need to choose a predictable sequence {Ae 1:21 that ensures that IC, grows rapidly under H1- This can be done by running ONS with losses e (A) log(1 (X)) (Y, =(e, o)])- The regret bound of ONS from [22],
summarized in Theorem 1. implies that for any X,
Σ
Σ & RE
EE
Noticing that Eie (A) lKg (A)), where log(KG; (A)) is the process from Equation (3) and Eien (A.) = log((G;), we have that
lim log(KCt lim 1-000
log(K; 1(AA))
t-500 t
where the last equality comes from Theorem 3.2, Part 2. Hence, learning X with ONS does not hurt asymptotically if we know f". Finally, f can be learned by running OGA with losses he(f) (f, KX,,))))) KY,, +)
f1 = 0 f + Vhe(fi))
where 11 is an operator projecting onto to the set of functions with || S 1. Incorporating these changes, on the abstract test of the previous section, we arrive at the practical test presented in Algorithm 1, whose statistical properties are presented in Theorem 3.3.
Algorithm Sequential DP Auditing
1: Input: Neighboring datasets S,S' E D, mechanism A, privacy parameters o, maximum number of iterations Nmax-
2: Set r(s, 8) = 2
2(1-6)
14e
3: Initialize XC = \ = 0, = 0z
4: for = 1,2, N do
5: Observe X, A(S), Yi ~ A(S')
6: Kc (1+ X Kf,, K K(X,,)) K(Y,))) -(C,)))
7: KG, 2 1/a then
8:
Reject Ho else
9:
Send h.(st) (Je, (J,, -KY, OGA, receive Se41
11: Send (e())) = log(1 + +e ((X,.) - -(E, to ONS, get Ae+1
12: end if
13:
end for
Theorem 3.3 (Statistical properties of Algorithm 1). Suppose OGA in Line 10 is Algorithm
initialized on input {f E H: lfll I 1), Oz and ONS in Line 11 is Algorithm 3 initialized input
00, - Let Kr, be the process constructed in Algorithm 1 and T = minft 2 1: Kc, 2 1/a} be the stopping time of the test when Nmax 30. Then,

---

1. Under Ho, P(T < 00) S a.
2. Under H1, (i) 1im log((e)) (2(22) and (ii) [[T] O (Io(11/2)
[ng(1/ (a 2)))
Theorem 3.3 mimics the guarantees in Theorem 3.2 for the practical test in Algorithm 1. Item (I) states that under Ho. the probability of rejecting Ho (which occurs if the stopping time T is finite) is upper-bounded by a, thereby controlling the Type error. Item (2) states that under H1, the process KG, grows roughly as exp(t o(t) for sufficiently large t. This behavior is similar to that of the abstract test (Theorem 3.2), though practical learning aspects, such the o(t) term due to learning X" with the Online Newton Step (ONS) algorithm, should be considered for the precise constants involved. Item (3) guarantees that the expected time to reject Hg, denoted E[T] (i.e., the expected time to detect that an algorithm does not satisfy its privacy guarantee), is bounded by 1/ Thus, the larger the MMD between the distributions generated by the mechanism on adjacent datasets (which contributes to a larger A), the faster privacy violation will be detected. Notably, our test does not need knowledge of A, it adapts automatically.
3.4 An alternative approach based on e-processes
Algorithm 1 is sequential test based the construction of a nonnegative supermartingale and an application of Ville's ' inequality. E-processes are a class of stochastic processes broader than nonnegative supermatingales that can also be combined with Ville's inequality to design sequential tests. Concretely, an e-process is a nonnegative stochastic process almost surely dominated by a nonnegative supermartingale.
In concurrent work, [51] studied a general class of e-processes. An important sub-class are the ones of the form
w.(
II (1 (E, 1)) II ((8,, 1 - B:), (E,, KE(+]
sE(+]
where for all > 1, 8 E [0, 1] and E; is an e-value for the null, meaning that E; is almost surely nonnegative and [E,] < 1. If the coefficients {3:322 are predictable, then the process above is nonnegative supermartingale under the null. We could employ ONS as in Algorithm I to approximate the fixed 5 that makes log( (W*))) grow the fastest under the alternative. However, this requires truncating the domain, since otherwise the gradients of log(1 + ((E,- - 1)) with respect to 3 explode when 1 + ((E, 1) x O. breaking the Lipschitzness property needed to obtain theoretical guarantees with ONS. [51] shows that choosing the sequence [8:) according to the Universal Portfolio (UP) algorithm [9] allows to optimize over the whole interval (0, 1] while at the same time achieving regret bound with smaller constants than ONS. Since UP difficult to implement in practice, they present an e-process W, that is upper bounded by the nonnegative supermartingale WPP which we would obtain by optimizing (3( with UP.
For our concrete problem, we can prove that for every t 2 1, E, 2+.4(x))--+0)) is e-value for 2+7 the null if {f))2) are predictable. This allows to re-write the processes K,, from the previous sections in the form of eq. (4), and noting that the optimization of } is equivalent to the optimization of (8.)221 we are able to design a slightly different sequential DP auditing procedure, Algorithm The details of the algorithm, its statistical properties, and an experimental comparison with Algorithm 1 are provided in Appendix C.
4 Experiments
Below we provide empirical validation the proposed sequential DP auditing framework in Al- gorithm 1.2 We evaluate both Type I error control and detection power of this approach across different real-world DP mechanisms. First, we assess the performance of Algorithm on both DP DP-compliant and non-DP mechanisms for computing the mean with additive noise. Moving forward, we demonstrate how DP-SGD implementations can be efficiently evaluated for privacy guarantees in under one complete training run. In Appendix F we provide additional empirical validation of
'The code to replicate our experiments is publicly available: attps:://ithhh www. coom/ooogee research/ google- httpaaarrrceeeeeeeteeeere////e// sttpeeeeeaeppeeeeeeieeeaaeaaelea
7

---

the theoretical properties of our MMD-bases tester using synthetic data with known underlying distributions, specifically Gaussian and perturbed uniform [42] distributions.
4.1 Additive-Noise Mechanisms for Mean Estimation
We evaluate our auditing methodology on mechanisms that employ additive noise when computing the mean. We analyze approaches using both Laplace and Gaussian noise distributions. Following the setup in [26], we define the following candidate DP mechanisms:
E X;
DPLaplace
+ PI:
(5)
NonDPLaplace (X) Ei=1 Xi
+ P2:
(6)
72
Ei=1 X;
NonDPLaplaco2(X) ==
+ PP1
P1.
where = max (0xx(10-2,,, 12, 77, with T Laplace(O. 2/e), P ~ Laplace(O, 2/(ñs)), and P2 ~ Laplace(0, 2/ 2/[ne)). Among these mechanisms, only DPLaplace satisfies c-DP. NonDPLaplace fails to maintain privacy guarantees by directly utilizing the private sample size n, while NonDPLaplace2 privatizes the number of samples when determining noise scale but calculates the mean using the non- privatized count. Additionally, we examine Gaussian noise Triintts-DGGauseee NonDPGaussian.. and HaDDDGausiian-whiee correspond respectively to the analogous mechanisms but use additive Gaussian noise distributions.
We use the sequential DP tester to evaluate the proposed mechanisms for = E {0.01, 0.1}. }. controlling the additive noise introduced by each mechanism. For each setting, we test the null hypothesis that the mechanism satisfies (s, 5)-DP using the characterization in Definition 3.2 against the alternative that does not. For this set of experiments, we fix the neighboring datasets to S {0} and S' = {0, 1}, although the sequential test remains agnostic of the specific choice of neighboring datasets. Morcover, we use 20 initial samples to set the bandwidth for the MMD tester using the median of the pairwise distances [17], which are then excluded from the actual testing phase to maintain statistical validity, We repeat each experiment 20 times and report the aggregated findings to ensure robust results and account for statistical variability. We report failure reject the null (no violation detected) when the test reaches 2,000 observations for E = 0.01 and 5,000 samples for E = 0.1.
Table demonstrates the effectiveness and efficiency of the sequential DP auditing approach in identifying both compliant and non-compliant DP mechanisms across different privacy regimes. For both private mechanisms Daaiiniims-nGGaarseee DPGaussian and DPLaplace- we successfully control Type error with zero rejections for both & = 0.01 and & 0.1. In contrast, all non-D> mechanisms show significant rejection rates in high-privacy regimes (e = 0.01), with DPGaussianl, NonDPLaplace and NonDPLaplace2 achieving 100% detection success using fewer than 350 observations on average, while NonDPGaussian2 reaches 85% rejection rate requiring approximately 1.150 samples. This efficiency is particularly notable when compared to the samp-samll-sszze MMD-tester recently proposed in [26]. which failed to identify violations in the NonDPLaplace2 and NonDPGaussian2 mechanisms even when using 500,000 observations for & = 0.01. The power of the sequential test decreases moderately for & 0, though it still maintains nearly perfect rejection rates for NonDPGaussianl, NonDPLaplace and NonDPLaplace mechanisms using fewer than 1,000 data points. Interestingly, NonDPGaussian2 presents the most challenging detection scenario, with rejection rates dropping to just 5% for e 0.1, suggesting its violations become more subtle as privacy constraints relax. We provide detailed comparison with the fixed- sxed-sample--ize approach from [26] in Appendix D.
4.2 DP-SGD Auditing in Less-Than-O0 Training Run
In this section, we demonstrate our sequential framework's ability to audit DP-SGD [1, 46] and iden- tify privacy violations in less than one complete training run. We adopt a white-box auditing approach that grants access to intermediate gradients. This is more efficient than black-box audits, which require re-running the entire training process to generate each sample, making them computationally intensive.
8

---

Table Algorithm sequential DP auditing performance on mean mechanisms with additive Gaus- sian and Laplace noise across privacy regimes. Rejection rates indicate the proportion of experiments (+= standard errors over 20 independent runs) where algorithm rejects the null hypothesis of (c, 8)- DP. N represents the average number of samples required to detect a violation, when it occurred (+ standard errors). Dashes (-) indicate that no violations were detected, consistent with true DP-
mechanisms.
=
0.01
& = 0.1
Mechanism
Rejection rate
N reject
Rejection rate
N to reject
DPGaussian
0,0 = 0.0
0,0 + 0.0
NonDPGaussian
1.0 + 0.0
264 + 9.3
+ 0.0
562 29.2 4776 + 219.0
NonDPGaussian2
0.85 + 0.08
1139 + 126.1
0.05 + 0.05
DPLaplace
0.0
0.0
NonDPLaplacel
1.0
331 = 14.5
1.0 0.0
920 = 61.6
NonDPLaplace2
1.0 0.0
192 18.4
0.95 + 0.05
770 + 262.3
The proposed sequential test not only detects violations but can also estimate a lower bound on the privacy parameter by finding the smallest that our the test fails to reject at fixed ō and confidence level. Crucially, if the null hypothesis is never rejected, our method is equivalent to a standard one-run MMD audit the full of gradients, ensuring is at least accurate comparable non-sequential methods while offering the potential for much faster detection.
Auditing methodology. We adopt the white-box auditing procedure introduced as Algorithm in [33]. At each training step batch B, of examples is sampled. The auditor computes two private gradients: [i(] from the standard gradient B, and V([ where a canary gradient g' was inserted with probability lc- This canary is constructed be orthogonal all other per-example gradients within its batch in expectation. The auditor collects one-dimensional samples Zt, Ut. corresponding to the dot product between g' and the gradients: norm and batch size are known by the auditor in the white-box setting, the samples are rescaled. This process yields { e drawn from Gaussian distribution Pi NO, o²) and (w: y where the canary was present, drawn from P2 = o(1, In practice, computing the canary described can be computationally intensive, Dirac canary gradients gradient with zeros everywhere except at single index- are used instead. This leads to samples {æ, J., { that are not necessarily identically distributed over time. However, note that our algorithm
(g', [(() and (g', V [d]- Since the clipping
handle time-varying distributions: the supermartingale property under the null hypothesis is preserved so long as Iy and y/ are close in distribution at every time-step t 2 1. See Section V.A in [44] for more details time-varying distributions.
To find the privacy lower bound, }e:). Each process tests a null hypothesis Ho MMD((P, P2) < T(s,,)) The empirical lower bound after steps, is the smallest candidate E; that the test fails to reject at confidence level a 0.05.
parallel auditing processes for set of candidate parameters
Experimental Results. We audit DP-SGD mechanism with 0.1 batch sampling rate. The estimated per-step lower-bound, Scanarys does not account for the composition or subsampling amplification of the final model's total privacy cost (g. defined above set to qe in our experiments).
Figure shows the results from five independent runs. For the private implementation (Figure la), our test correctly fails to reject the null hypothesis after 500 observations in all 5 runs, as expected for this confidence level, and confirming the mechanism satisfies its expected privacy of Ecanary 0.01 (corresponding to a total zs 0.03).
In contrast, for the con-vrivate implementation (Figure 1b), the audit successfully detects violations. It rejects the hypothesis Hn : Ecanary & 0.01 in an average of just 60 observations and Ho Eeanary: = 0.1 in 75 observations. After 250 observations, our method establishes a privacy lower bound of

---

0.43 for this non-pri non-private mechanism, and 0.59 after 2,500 observations (in Appendix G,
Figure 7).
Empirical lower bound E
1.0
Empirical lower bound &
1.0
0.8
0.8
0.6
0.6
0.4
0.4
0.2
0.2
Ecanary = 0.01
0.0
0.0
0
50
100
150
200
50
100
150
200
Number of observations
Number of observations
(a) Private DP-SGD (Econary 0.01).
(b) Non-private DP-SGD.
Figure 1: Sequential audit results for DP-SGD implementations during training under white-box access with canary gradient threat model over 5 independent runs. Private implementations (left) are correctly identified as satisfying the specified differential privacy guarantee, while non non-privee non-private implementations (right) are successfully detected as privacy violations for non-trivial values of s.
Discussion. While effective. MMD-based tests face challenges when auditing large values (e.g.. >> 0.6). In this regime, the MMD statistic and its rejection threshold t both approach their theoretical maximum. This makes the gap, A (see Theorem 3.3), extremely small, leading to large sample complexity, which is in the order of 1/ We show in Appendix G (Figure 8) that when auditing a mechanism with true 3, the empirical lower bound grows very slowly, confirming this limitation.
Despite this, our experiments validate that our sequential test can monitor and identify privacy viola- tions in DP-SGD dynamically during training. Unlike prior methods requiring at least one full training run, our approach provides empirical privacy bounds with only a few hundred gradient iterations. This represents a significant advancement in privacy auditing efficiency, enabling practitioners to verify privacy guarantees with substantially reduced computational cost.
5
Discussion
Our work introduces sequential test for auditing differential privacy guarantees that automatically adapts to the unknown hardness of the testing problem stated in Definition 3.2. When compared with previous batch algorithms, analysis and experiments show considerable improvements for detecting DP violations in non-private SGD and non-private mean estimation mechanisms. We also observe that auditors can efficiently characterize the privacy tradeoff function of parameterized mechanism from a single observed stream by simultaneously testing multiple privacy levels similar techniques used for estimating means of bounded random variables via betting strategies [50]. We used this idea to compute empirical lower bounds on the privacy parameters in Section 4.
A first limitation of our approach, observed for some DP-SGD audits, is the very large sample complexity required for large E privacy regimes. This an inherent limitation of MMD- auditing that also affects previous batch tests relying on this statistic. A second limitation, shared with prior work, is the reliance on a fixed pair of adjacent datasets. Ideally, we would like to combine algorithm with a procedure that adaptively finds worst-case pair.
Extending the sequential framework to audit larger privacy parameters or other important privacy definitions, such as Rényi DP or fDDP, represent valuable avenues for future investigation.
10

---

Acknowledgments and Disclosure of Funding
We thank Jamie Hayes for useful guidance on auditing DP-SGD. We thank the anonymous reviewer who pointed out the connection between MMD and Total Variation, which helped us improve the MMD bound Theorem 3.1. AR is supported by NSF grants DMS-23107 and IIS 112-2229881. TG was partially funded to attend this conference by the CMU GSA/Provost Conference Funding.
References
[1] Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. Proceedings of the ACM SIGSAC Conference Computer and Communications Security, pages 308-318, 2016.
[2] Galen Andrew, Peter Kairouz, Sewoong Oh, Alina Oprea, Hugh Brendan McMahan, and Vinith Menon Suriyakumar. One-shot empirical privacy estimation for federated learning. In The Twelfth International Conference on Learning Reprexentations, 2024.
[3] Apple Inc. Differential privacy overview. https: http://wwwpppp.....p/pp/pp com/ httm//piaayyccccc// Pererrentaal_PPvvac__eeeeee pdf.. 2017. Accessed: 2025-05-15.
[4] Borja Balle, Giovanni Cherubin, and Jamie Hayes. Reconstructing training data with informed adversaries. In 43rd IEEE Symposium on Security and Privacy (SP), pages 1138 1156. IEEE, 2022.
[5] Benjamin Bichsel, Samuel Steffen, Ilija Bogunovic, and Martin Vechev. DP-Sniper: Black-box discovery differential privacy violations using classifiers. 2021 IEEE Symposium on Security and Privacy (SP), pages 391-409. IEEE, 2021.
[6] Jeremiah Birrell, Paul Dupuis, Markos A Katsoulakis, Lue Rey-Bellet, and Jie Wang. Varia- tional representations and neural network estimation of Rényi divergences. SIAM Journal on Mathematics of Data Science, 2021.
[7] Dingfan Chen, Ning Yu, Yang Zhang, and Mario Fritz. Gan-leaks: A taxonomy of membership inference attacks against generative models. In ACM SIGSAC Conference on Computer and Communications Securily, 2020.
[8] Ben Chugg, Santiago Cortes-Gomez, Bryan Wilder, and Aaditya Ramdas. Auditing faimess by betting. Advances in Neural Information Processing Systems, 36:6070-600 2023.
[9] Thomas M Cover. Universal portfolios. Mathematical finance, 1(1):1-29, 1991.
[10] Thomas M Cover and Erik Ordentlich. Universal portfolios with side information. IEEE Transactions on Information Theory, 42(2):348-366 2002.
[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, page 475-489, 2018.
[12] Kashyap Dixit, Madhav Jha, Sofya Raskhodnikova, and Abhradeep Thakurta. Testing the Lipschitz property over product distributions with applications to data privacy. In Theory of Cryptography Conference (TCC), 2013.
[13] Carles Domingo-Eninn and Youssef Mroueh. Auditing differential privacy in high dimensions with the kernel quantum Rényi divergence. arXiv preprint arXiv:2205.13%. 2022.
[14] Vadym Doroshenko, Badih Ghazi, Pritish Kamath, Ravi Kumar, and Pasin Manurangsi. Connect the dots: Tighter discrete approximations of privacy loss distributions. Proceedings on Privacy Enhancing Technologies, 2022.
[15] Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 486-503, 2006.
11

---

[16] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity private data analysis. In Theory of Cryptography Conference (TCC), 2006.
[17] Damien Garreau, Wittawat Jitkrittum, and Motonobu Kanagawa. Large sample analysis of the median heuristic. arXiv preprint arXiv:1707.07269, 2017.
[18] Anna C Gilbert and Audra McMillan. Property testing for differential privacy. In Allerton Conference on Communication, Control, and Computing. 2018.
[19] Arthur Gretton, Karsten M Borgwardt, Malte J Rasch, Bernhard Schölkopf, and Alexander Smola. A kernel two-sample test. The Journal of Machine Learning Research, 13(1):723-773, 2012.
[20] Miguel Guevara. and advancements.
Sharing our latest differential privacy milestones sharing- -ur- lwtest-ditffeeeeee
https://devoloperss htgpss/ com/en/ -ww.ettiiia--piiiaaaammieeeeeeee and -nd--andddaaada- advancemenss/ 2024. Accessed 2025-05-15.
[21] Chuan Guo, Brian Karrer, Kamalika Chaudhuri, and Laurens van der Maaten, Bounding training data reconstruction in private (deep) learning. In International Conference on Machine Learning (ICML), 2022.
[22] Elad Hazan, Amit Agarwal, and Satyen Kale. Logarithmic regret algorithms for online convex optimization. Machine Learning, 69(2):169 192, 2007.
[23] 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.
[24] Bargav Jayaraman and David Evans. Evaluating differentially private machine learning in practice. In USENIX Security Symposium, 2019.
[25] Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The composition theorem for differential privacy. In International conference on machine learning, pages 1376-1385, PMLR, 2015.
[26] William Kong, Andres Munoz Medina, Monica Ribero, and Umar Syed. Aud large scale library for auditing differential privacy. In 2024 IEEE Symposium on Security and Privacy (SP), pages 219-219, 2024.
[27] David Levin and Yuval Peres. Markov chains and mixing times, volume 107. American Mathematical Soc., 2017.
[28] Johan Lokna, Anouk Paradis, Dimitar Dimitrov, and Martin Vechev. Group and attack: Auditing differential privacy. Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security, pages 1905-1918, 2023.
[29] Yun Lu, Yu Wei, Malik Magdon-Ismail, and Vassilis Zikas. Eureka: general framework for black-box differential privacy estimators. Cryptology ePrint Archive, 2022.
[30] Min Lyu, Dong Su, and Ninghui Li. Understanding the sparse vector technique for differential privacy. Proc. VLDB Endow., 1066)6377644, 2017.
[31] Saeed Mahloujifar, Luca Melis, and Kamalika Chaudhuri. Auditing Saaittnggddiffeee /ddiffrrential privacy in one run. arXiv preprint 2rXiv:2410.222235, 2024.
[32] Tudor Manole and Aaditya Ramdas. Martingale methods for sequential estimation of convex functionals and divergences. IEEE Transactions on Information Theory, 2023.
[33] Milad Nasr, Jamie Hayes, Thomas Steinke, Borja Balle, Florian Tramèr, Mathew 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.
[34] XuanL Long Nguyen, Martin J. Wainwright, and Michael I. Jordan. Estimating divergence functionals and the likelihood ratio by convex risk minimization. IEEE Transactions on Information Theory, 56(11), 2010.
12

---

[35] Ben Niu, Zejun Zhou, Yahong Chen, Jin Cao, and Fenghua Li. DP-Opt: identify high differential privacy violation by optimization. In International Conference on Wireless Algorithms, Systems, and Applications, pages 406-416. Springer, 2022.
[36] Francesco Orabona. A modern introduction to online learning, arXiv preprint
2019.
[37] Shadi Rahimian, Tribhuvanesh Orekondy, and Mario Fritz. Differential privacy defenses and sampling attacks for membership inference. In ACM Workshop on Artificial Intelligence and Security, 2021.
[38] Aaditya Ramdas, Johannes Ruf, Martin Larsson, and Wouter Koolen, Admissible anytime-valid sequential inference must rely on nonnegative martingales. arXiv preprint arXiv:2009.0310 2020.
[39] Aaditya Ramdas and Ruodu Wang. Hypothesis testing with e-values. arXiv preprint arXiv:2410.23614, 2024.
[40] Leo Richter, Xuanli He, Pasquale Minervini, and Matt Kusner. An auditing test to detect behavioral shift in language models. In The Thirteenth International Conference on Learning Representations, 2025.
[41] Ryan Rogers, Subbu Subramaniam, and Lin Xu. Privacy-preserving single- post analytics. https://www linkedin. com/blog/ hhaa/bloo//nginneeee anggneering/treeee taagggrruutteeeeeeeeee and-safety/ privacy-preserving--e seiiinngggt-----eeeeeeeeeeeeooee pasp-ppaasttiiceeo analytics, 2023, Accessed: 2025-05-15.
[42] Antonin Schrab, Ilmun Kim, Mélisande Albert, Béatrice Laurent, Benjamin Guedj, and Arthur Gretton. MMD aggregated two-sample test. Journal of Machine Learning Research, 24(194):1 81, 2023.
[43] Glenn Shafer. Testing by betting: A strategy for statistical and scientific communication. Journal of the Royal Statistical Society Series A: Statistics in Society, 2021.
[44] Shubhanshu Shekhar and Aaditya Ramdas. Nonparametric two-sample testing by betting. IEEE Transactions on Information Theory, 2023.
[45] Shubhanshu Shekhar, Ziyu Xu, Zachary Lipton, Pierre Liang, and Aaditya Ramdas. Risk- limiting financial audits via weighted sampling without replacement. In Uncertainty in Artificial Intelligence, pages 1932-1944 1941, 2023.
[46] Shuang Song, Kamalika Chaudhuri, and Anand D Sarwate. Stochastic gradient descent with differentially private updates. In 2013 IEEE global conference on signal and information processing, pages 245-248 IEEE, 2013.
[47] Bharath Sriperumbudur, Kenji Fukumizu, Arthur Gretton, Bernhard Schölkopf, and Gert RG Lanckriet. On the empirical estimation of integral probability metrics. Electronic Journal of Statistics, 6:1550-1599, 2012.
[48] U.S. Census Bureau.
Why the census bureau chose differential privacy. https: / //www. census. waogggooorrllalaae httpar//pbbccaatooseeeeeee c2020br-03. 00. pdf, 2021. Accessed: 2025-05-15.
census-brietee
[49] Jean Ville. Etude critique de la notion de collectif. volume 3. Gauthier- Villars Paris, 1939.
[50] Ian Waudby-Smith and Aaditya Ramdas. Estimating means of bounded random variables by betting. Journal of the Royal Statistical Society Series B: Statistical Methodology, 86(1):1-27, 02 2023.
[51] Ian Waudby-Smith, Ricardo Sandoval, and Michael I Jordan. Universal log-optimality for general classes of e-processes and sequential hypothesis tests. arXiv preprint arXivv2504.02878, 2025.
[52] Ian Waudby-Smith, Philip B Stark, and Aaditya Ramdas. RiLACS: risk limiting audits via confidence sequences. In Electronic Voting: 6th International Joint Conference, pages 124-139. Springer, 2021.
13

---

A Improvement on Lower-Bounding Hockey-Stick Divergence with the MMD
Theorem 4.13 in [26] introduces a lower bound on the MMD between two distributions that is parameterized by the order and magnitude of corresponding Hockey-Stick divergence. This connec- tion divergence enables DP auditing with the MMD. Theorem 3.1 below tightens this bound. For completeness, present first Theorem 4. in [26] and then proof of Theorem 3.1.
Lemma. ([26, Theorem 4.13J) Let H. be a reproducing kernel Hilbert space with domain X and kernel ((,)). Suppose K [ x) & for all E X. If mechanism A is (E, D.-P. then for any S S
(MD(A(()),(S))) s -++
(8)
Theorem. (Theorem 3.1 1 in the main body). Let H be a reproducing kernel Hilbert space with domain X and kernel K (:))). Suppose < (2. & for all x, y E X. If mechanism A is (E, -DD, then for any S S
MMD(A(()).A(')) & v2 1- 2(1 - -6) + ce
(9)
Proof of Theorem 3.1. Let P = A(S) and Q A(S'). It is well-known that MMD(P,Q) = ||p pollx
where μa (x(, X and lQ = Ey-p K Y)) It follows by Jensen's 's inequality that for any coupling ı between and Q
MMD(P.Q) = |[xxr K[ X)] - Ey Ey~o(K(; Y)llx
|| (K( (x)) K(, Y))l
B( (K. K(,, [)
sup [K({))) - -((,u)ll Exxr-l
x.yEx
sup |K((, 2) - K(. x((x))ll
(xxx)
First, we bound the term supa.ye [[((,x)) - K(., v) 11x. Note that for any x, E X' we have
[K(,z)) v1) K(x, x)) + K(y, y) 2K(x.))
< 2(1 K (z $ 2,
where we have used that the assumption that 0 < K(x, v) S 1 for all x, E X. We conclude that
suxx.yex (K(,,)) K K(-.// 11 < 2, which is equivalent to supz.yex || [+, v) S 2 Pluggin this into the MMD bound that we obtained above, we get that for any coupling æ between P and Q
MMD(P, Q) S (x.) *
Minimizing the right hand side over all couplings, obtain
MMD(P. s V2TV(P.Q).
since inf ( P(xyr>< [X + YJ = TV(P.Q) Q), where IT(P, Q) denotes the set of all couplings between P and Q (see, e.g., [27, Proposition 4.7l). Finally, we use that
TV(P,Q) <1 2(1 8)
1
stated in [25, Remark A.I.b].
14

---

Remark A.1. The MMD bound that we provide in Theorem 3.1 strictly improves over the one from [26, Theorem 4.13] for all privacy parameters 0, (0, 1):
v2 ( 2(1 -6)
V2 1 + e
(1 + - +
1 1+ c
S E 1+
< 1+ ô + de
E 1+ 8(1 + e e
B Proofs in Section
Theorem (Theorem 3.2 in the main body). Let f be the witness function for MMD(A(())AA(S))
(as defined in definition 2.3). Given samples {X,, Yih22 si A(S) x A(S") and a fixed hyperparam- eter X > define the stochastic process (IC (2)) as follows:
Kg =1 (A) K)) (()) -(E,8)))
where T(E, 8), defined definition 3.2, represents the expected upper bound on MMD under the null hypothesis. Then it holds that:
1. Under the null hypothesis (Hg (IMD(A()):A(S))) < T(E,8)), for any [0, 1/22+(e,,)) and any a E (0. 1), we have P(supiz1 KG(A) 2 1//a| Sa.
2. Under the alternative (H1 : MMD((((S).A(5)))
T(E, there exists X log (x = 2((A)) almost surely, where
[0, BF1t(.,) such that lim
(ND((A(S), T(e
Proof. We prove each item separately.
Part 1: To start, is easy to see that under Ho. KG supermartingale for any 2 0: letting F. = Yr...., X,, Y,) be the o-algebra generated by the samples observed up to time t,
E(G(()) | (A) ((TT(XX))))))) ff (Y)) -(E,)))) KC; (1) + (MMMD(A(S) -(ee S (G),
F--1]
since X 8)] < 0 under the null, and thus t (1-X(MMDD(ASS),(5))) T(E,8)) 1.
Furthermore, by definition f" bounded (X,) < 1, implying that
(X,) - (X) T(E, 8) [-2 T(E, 8), T(E,6)).
Hence, KG, is nonnegative long as 0 S - Consequently, Ville's inequality (theorem 2.1) indicates that for any E (0, 1). A E [0. 2+T(E.8) K,(A) remains bounded by 1/a over time with probability least 1
Part 2: For this part we need to prove that under H A MMD(A(S), A(S')) (c, al- most surely, there exists X [0, 8447(6,8) such that for sufficiently large i, (A()*) 2 exp(O((A?)).
15

---

To see this, first note that for any X E [0, 1a.22((,55 and any realization (Iz, 1hh21 of (X,, Yoh2ı. we can deterministically lower bound log(K;) as follows
(A)( = log
K
II (1 (1." - -F(E,
vE[c]
= -
Σ
log(1 + (1:) ( [(s,
ic(d
Σ \l - (w:) [(E, - Σ (2;) -(E))((E,))))
sEld
sEld
where the first equality follows from the definition of K2 and the second one from the product rule for logarithms, and the last inequality uses the bound log + x)
x² for (-1/2, 1/1)/ 1/cch can be verified finding the critical points of g(x) = log(1 + +x) -I - -x² combindd with the fact that for [0, 442+(6,)) J. \ff (v, T(E,
1-22, for all 1.
Now, define
1 t EE[U r(t)
(fa (
MMD(A(S).A((')
(10)
and suppose that r(t) + as t + cc.
It follows that
(w:) (E,
A == (8+ (T,,
8)) 5)) Eiegg [ (xx) 1 (y:) [(s Eie (x=2) (wx T(E,
(11)
satisfies x E 10, 844)(8,8) (8+47(2.0))ctd for c, d 0.
whenever Eiegglf(xx;) - (v.) - =(E, 2 0 since it has the form
But for any t,
ii - t KEjA
T(E, = r(t) MMD(A(S), - -(E, = r(t) + A.
Since we assumed r(t) + 0, there exists to such that for all 2 to. |r(t]] s 4/2, implying that [Eegglf((a.) (3:) T(=, 6'] r(t) + A A/2 /2
We conclude that rt)) + 0 as + co, then for sufficiently large
1
Σ (z.) (3.) T(E, 6)] 2 A/2.
sEid
which in particular implies that Eiegg [ (z))- 8)] > 0, and hence A E [0, 8447(c.8) It follows for any 2 to plugging this value into the lower bound for (,*())) gives that log (X*)) can be lower bounded by
(a)
E Eistg(f((:)) - f*())) 6)] + +8+ Ex f*()) T(E, 811)
(tA/2)2
4 (2E f (vs) - T(E, 8)22 + (8 + 47 8)) (tety( - fm((s) ((E,
(22
t
(t
(12)
(32t 16t)
768
Our reasoning allows to conclude that
log (o(((()))) =((A²)
lim t00
t
16

---

whenever r(t) + as - sc. Finally, the strong law of large numbers implies that the realizations of (X,, 22 that do satisfy r(t) + - oc, where r(t) defined in Equation (10), have probability measure of 0, and hence our conclusion is valid almost surely.
IT
Theorem. (Theorem 3.3 in the main body) Suppose OGA in Line 10 is Algorithm 4 initialized on inpul (J E : |1 S 11,,00 Oz and ONS in Line 11 Algorithm initialized on input [O, 2+2r(e,0)
Let Ka be the process constructed in algorithm I and T min 2 1 Ke 2 1/a) be the stopping time of the test when Nmax 0C. Then,
1. Under Ho P(T < 00)=
2. Under H1, (i) lim
log(Ke) (2(22) and (ii) B[7] 0
1oR(1/(o ((
Proof. We prove each item separately.
Part I: The proof follows directly from the arguments used in part of theorem 3.2, with the difference that X is no longer fixed. To handle this, we simply use the fact that since A is the output of ONS after observing losses f1..,,,1-11 which only depend on {X,, Yihettt-1) 1], then d is Fe-r-measurabl.
Part 2:
(i) We proceed similarly to the proof of Theorem 3.2, but now X and fa vary with t. The process K, constructed by running algorithm can be written as
Ko 1, K, = Kr-1 x (1+ (XL)),))) - ((0) - T(E,8))).
For any 2 0, define the process (A) as follows
Ko(A) 1, (G(A)) 1A) x (1 ((X(X) ((()) T(E
(13)
This is the process that we would obtain by running algorithm with fixed X, instead of computing λ1. A2...., A via ONS. As before, we can prove that for any X [0, 2427(e,5)) and any realization (Ie, Me Jez1 of {Xe, Y1h2 (A)) can be deterministically lower bounded follows:
log(KC, = log
Ko
II
X[f(xxx) - f((()) - o(E,
<E[4]
+
Σ
log(1 + ([f((x)) Se(vs) T(E,
kE(t)
(f((x;)) - f((1)) - T(E,
Σ ((())))))((()))---))) -(s)))
[E(A)
Similarly to eq. (11), define X as
(xegg(((x;)) - f((()) [(E,8))
X
(8 (T(, Evegg f((y1) +2 f((y))
(14)
It follows that X E [0, 844))1,)) whenever Eveto (fx f((vs) T(E, 8) 20. Furthermore, by the regret guarantees of OGA (Theorem E.2),
sup Σ fú, K(z,.) K K(y, )) & 6vt,
A1 (E(()
since the functions h₂() = (S, K(r,,)) :) K(n, ))H are 2-Lipschitz, since K(x, S implies that (x,, K (V,,)) ) 2, and the diameter of the optimization domain
17

---

{f: llfllx I 11 is fa llallll II - fellu = 2. Applying the reproducing
property of K implies, in partieular, the following inequality for the witness function
6
Eir(a)) - (w)) - r(e, 6)]
- E(i(a.)) fi(v)) - T(e, (15)
V
As in Equation (10), let r() be defined
r(t) Ii
f (w:)] MMDD((()))(
ie]d
inequality (15) can be re-written
6
r(() +
Σ [1(x))) f(xc) [[,, KE(A
(16)
Assume r(t) + as + cc. This also implies r(t) + as + co. Consequently, for sufficiently large t we obtain that & Li - f(y)) - T(E.8)) 2 A/2. We then lower bound the wealth for this t by substituting the value of X previously defined eq. (14).
vi
Analogously to the proof of Theorem 3.2 (see eq. (12)), we obtain
t
log(KC(AA)) 768
(17)
Finally, note that since \1 .... A chosen by running ONS with losses (A) = log(1 + ((f((z)) - f((y)) - T(2, 6)]), the regret bound of ONS (see theo-
rem 1) implies that for any x E 10,1/(4 (T, 8))]
Σ 4(A)) Σ (((A)) S 10log(t),
(18)
kE(A]
iE|A]
since (e(A) is 1-exp-concave, + 2T(e, 8)-Lipschitz:
fe(xx) fe(we) (e,
+ T(E,8)
((AA) = 1+ ([+((z)) - fe(ve) - Te,, 6)]
S
1/2
and the optimization domain an interval of length 1/(4 + (r 6)). Noticing that
Exerg (x(A) (o)( and Exen (x(2;) log(K,), have that, for sufficiently
large t,
t
log( I log((C.(A")) - log((C,) < log
768
where the first inequality follows by subtracting log(K,, both sides in equation (17).
This in turn implies that lim;- log(K!)) 12
Recall that used the fact that r(t) converges to t + co, but this occurs almost surely by the Law Large Numbers, so our conclusion also holds almost surely. This finishes the proof.
(ii) The main difference between the previous result and this one is that to bound [[ under Hi we need to carefully quantify how quickly the term r(1) from Equation (10) converges
That is, r(t) is random variable, as opposed to Equation (10), where it was defined for specific realization of {(X,, Y2) We also define F(I) = r(t) Vt
In this proof, we consider r()) = Exetg (Xx, ((()) (M))
Using the tail-sum formula
for expectation, we can expand the expectation as
T
P
1) <
P(K+ < 1/a]
21
PlK, 1/a and F(t) 4/2] + P/A/2 F(t)
P[K, 1/a and F(t) s 2/2 PIA22 < r(t).
18

---

First, we bound the term P/A/2 r(t)]. Bernstein inequality implies that
}
2ogg(t) (t) 16 log(t))
PP r(t) 2 max 201
31
[2
where o² = (X,) (*())) - (IMD(A(S),A(S) since r(t) is the average of the
i.i.d terms 71.-.. Z,, where 2 = --(X,,) - (V, MMD(A((S). A())(A()))))))))))))))))) is centered
[E[ 0) and bounded (1 v 4).
Let
2 (tg(t)
16 1og()(
to min
IEN:123, max 20 V
A/2
3/
Since 3, then max 2 2 (t)
16 log(t)
is decresing in for all to. and by
31
definition of to. max 20 /
2 2log(to)
16 log(ta)
S /2. This implies that for any t to
t0
34a
2 log(()
16 log(!)
y
1
P(r(t) 2 A/2] IP
r(t) max
20
38
For L S to we trivially upper bound P(r(() 2 A/2] < 1. Combining these bounds, we
obtain that
Σ
PIA/2 < to +
Σ 2
1/t < tu + x2/6.
21
Lemma in [44] states that for any a > 0 and (0,
M log(bn)
n <a { < max { 20, S a }
2 2log(2/a)
min
a
which implies the following inequality:
min n n
log(bn)
S a S1 max { 20,
2 log (2/a)
n
This is true if the condition log(bn) < met for n 3, since the left side is 3 and the right-hand side is at least 21; in the case where the minimum is achieved at n 2 3, the condition n 2 3 can be removed and the inequality follows directly from the original lemma.
Hence, we obtain that Ig = O (ng(A/A) A
o² Ing((4r2 (2²) A
It follows that,
Σ P(A/25((1)) 0 log(4/A) E1
0² Pogg442//A)
A
Next, let's bound PPC, < 1/a and f(t) < A/2]. Equation (16) implies that under the event
F(t) < 2/2, & Eie (X.) - f(t)) -({,6)) A/2 and hence the lower bound for log (og(K,(A*)) 2 122 768 from Equation (12) valid for any realization of ((X,, Y2)21 under this event, and so is the lower bound log( > ta? /768 10 log((t), by the regret
19

---

guarantees of ONS. From these implications, it follows that
PlK, < 1/a and f(I) - A/2
121
and P Kr 1/a and
Σ [X,) - ((0) [(c,0)] A/2
121
iE|
IP [Ke 1/a and log(KG(A')) 2 /
IP [C 1/a and K2 2 exp (tA² /766 log(t))
IP exp (tA² 768 10))g(t)) < 1/a]
121
Σ
exp ta2 10log(()) <I/a] = t
121
where t min n EN. exp
112 10
1/a), since
1Aa
100og()) is
708
increasing in t. Finally, if log(t)/t < 4²/2 then AA 10 log(t)
1 /2
Lemma
7680
708 ( ). In addition, is easy to see
768
from [44] implies that log(t)/t /2 for t ?
7680
that /2 log(1/a) for t 2 log()/a)) ) We conclude that t ? log (1/11/= ( (log(1/a))
suffices to obtain
fA2
(tA3/2) exp(log(1/o)) 1/a.
exp
10
2 exp
768
768
0 for t 22 (22(1/22)++)) ( 1/2)) ), thus
This implies that
(
(xp
taa Tor
10lo(()) <1/a}
A2
1 0 (og(1//²)) (loog(//a) A
We conclude that
log(4/A)
0² Pogg(40
log(1/A3) + logg(1/a)
E|7] < Oto +11 = 0
+
A
A
A
This completes the proof.
C Detailed Explanation of Alternative Sequential Test based on E-processes
C.1 Derivation of the alternative test
As mentioned in Section 3.4, [51] studied general class of e-processes of the form Wr(3() He (1 + (E, 1)), described in eq. (4). Recall that for every 2 1, Br E [0,1] and E, is an e-value for the null, meaning that E, is nonnegative and EH,, [Eg] < 1.
For our concrete problem, (f: (f2) are predictable. Indeed, note that since f((X,) f(()) 2 -2, then E, 2 Moreover, under the null
prove that E, (x,) is an e-value for the null if 2+T
2 + fx(X,) fY,))
E E =
2+T
2 + (X)) - S2(Y)) ((X, Yi]
2+7
Elsup [(((X,) ((() ((1,) (Dhett1]
<
2+7
2 + Sup [l)(X,) (YY)
2+7
MMD
2+7
1.
2+T
2+T
20

---

Hence, the process W that results from sequentially choosing (2ehe20 with the Universal Portfolio (UP) algorithm [9] is a nonnegative supermartingale under the null. The regret guarantees of UP (Theorem E.3) give
max log( (W((3) - log(W, S log(t + 1)/2 + log(2), 10
where Wx(3) ( (1 3(E From the equation above, it follows that
W, exp
max log (og(W,(3)) -oog(t + + +og(2))) S WtP. [ee[0.1]
(19)
Hence, We is e-process, but supermartingale because it maximizes over / after observing (Xe, Y.). The reason to consider W, instead of W is that running UP is computationally involved and W; reasonable lower bound that only requires solving a simple one-dimensional optimization problem in order to compute it. This reasoning gives rise to the following algorithm. Note that the witness function f still learned with OGA, as in Algorithm 1.
Algorithm 2 Sequential DP Auditing with an E-process
I: Input: Neighboring datasets S, E D, mechanism A, privacy parameters e, 6, maximum
number of iterations Nmax.
2: Set r(E, 0) = v
2(1-6)
Itel
3: Initialize (9) = 1, = 0zf
4: for = 1,2, ..., Nma do
5: Observe X, ~ A(5), Y1 ~ A(S')
2+ (x())) -1))
6:
Wx(3) 1 (8) 1 1
2+rla,0)
7:
W. = exp (maxse|u.J) log(W.(3)) - llog(t + 1)/2 - log(2))
8:
if W. 2 1/a then Reject Ho
9:
else
11: Send h₂(f) = (f, K(, -K(Y,))) to OGA, receive fi+1
end if
13:
end for
C.2 Statiscal properties of the alternative test
The theoretical guarantees Algorithm are similar the ones stated about Algorithm in Theorem 3.3, but we expect Algorithm 2 to perform better in practice due to the advantages of UP against ONS in particular, the facts that UP allows optimize over the interval [0, 1] instead of [0, 1/2] and that its regret bound has smaller constants. See Appendix C.3 for experiments on the practical improvements that arise from using Algorithm 2 instead of Algorithm
Theorem C.I. Suppose OGA in Line 10 is Algorithm 4 initialized on input { H 11f1lx 1), On-
Let W. be the process constructed Algorithm 2 and minft W, 2 1/a be the stopping time of the test when Nmax co. Then,
1. Under Ho, P(T < oo) S az
2. Under Hi, (i) lime-soo log(W.) (2(22) and (ii) E[T] O [og(]/A)
log(1/(aA3)) A7
where A = MMD(A((), - 6(,
Proof. We prove each item separately. For simplicity drop the dependence of 7 in (c.
Part From eq. (19) we obtain that under Ho
P(T < xo) = ((t W, > 1/a) < P(E:: WUPP > 1/a) s a.
21

---

where the last inequality follows from the fact that W is a nonnegative supermartingale under Ho and Ville's inequality (Theorem 2.1).
Part 2. We formally prove that there is a one-to-one map between the processes (A,),) with X E [0, 1/21 7)] for all 2 1 and (x())) with Br [0, 1] for all 1. This follows from choosing 3. = (2 + 7) for all i 2 1:
K,+ II (1 (.(((())) S((Y) -7))
1+++2+7) ((X))) - f((V)) )
II xe[d
2+
[((()) - -((()) -T -T -11)
II xE({)
+
2+7
2 f((()) - fc(X))
II kE(()
2+7
II sE[c]
(.))
This equivalence allows us reproduce exactly the same proof that we used for Theorem 3.3, where the only differences that arise from replacing ONS by UP are
We are able optimize K, over A [0, 1/(2 r)] for all i 2 1. Recall that in order to use ONS we constrained to X E [0, 1/(4 + 2r) so that the losses & from Algorithm were Lipschitz.
Even though we are optimizing over larger domain, the regret guarantees that we obtain are better than those of ONS. Indeed, using ONS we obtained
max XE
IAg( log(KG) < 10log(()
in (18), while the process W, by construction satisfies
max xe|o.1/(2+7]
log(KG(A)) - log(Ke) = max log(W((3)) log(W)) se/0.11
log(( + 1)/2 - log(2).
Hence, the process W; from Algorithm 2 has two advantages over the process K, from Algorithm 1: it maximizes over wider domain and has smaller regret. These two properties, combined with the fact that both algorithms learn the witness function with OGA, allow us to prove the same properties that we obtained for Algorithm 1 in Theorem 3.3, up to (slighity better) constants.
C,3 Experiments and comparison to Algorithm 1
In the following, we replicate the experiments from Section 4.1 using our alternative sequential test based on e-processes. Table presents the performance of Algorithm 2 when auditing additive-noise mechanisms for mean estimation. Our results show improved performance over Algorithm I in effectively and efficiently identifying both compliant and non-compliant DP mechanisms across the different privacy regimes studied. Specifically, we observe improved rejection rates for NonDPGaus- sian2 (e 0.01), and NonDPGaussian2. NonDPLaplace and NonDPLaplace] (e 0.1), well as a decrease in the average number of samples required to detect a violation for all the studied mechanisms, with the exception of NonDPGaussian2 when 0.1.
We also apply this sequential test based on e-processes to audit the private and non-private imple- mentations of SGD from Section 4.2. Figure 2 shows the empirical performance of Algorithm
22

---

Table 2: Algorithm 2 sequential DP auditing based on e-processes performance on mean mechanisms with additive Gaussian and Laplace noise. Rejection rates indicate the proportion of experiments (# standard errors over 20 independent runs) where Algorithm rejects the null hypothesis of (e, d)-DP. N represents the average number of samples required to detect violation, when it occurred (+: standard errors). Dashes (-) indicate that no violations were detected, consistent with true DP- mechanisms. Values in bold represent improvements over the performance of Algorithm 1.
e 0.01
= 0.1
Mechanism
Rejection rate
N to reject
Rejection rate
N to reject
DPGaussian
0.0 + 0.0
0,0 = 0.0
NonDPGaussian
1.0 0.0
92 + 6.72
1.0 + 0.0
187 16.8 4475 + 307.4
NonDPGaussian2
0.9 + 0.06
728 + 139.8
0.15 + 0.08
DPLaplace
0.0 0.0
0.0 0.0
NonDPLaplace
1.0
106 - 9.8
1.0 1.0 = 0.0
340 + 42.0
NonDPLapplac22
+
54 + 4.9
1.0 = 0.0
253 + 119.8
with faster detection rates in non-private regimes (Figure 2h), while successfully identifying private implementations (Figure 2a). detail, Algorithm 2 rejects the hypothesis Hn Ecanary 0.11 in just 18 observations on average over 5 runs, and establishes empirical lower bound of 0.79 using 250 observations in the white-box auditing regime detailed in Section 4.2.
Empirical lower bound &
1.0
1.0
Empirical lower bound
0.8
0.8
0.6
0.6
0.4
0.4
0.2
0.2
Ecanary 0.01
0.0
0.0
0
50
100
150
200
0
50
100
150
200
Number of observations
Number of observations
(a) Private DP-SGD (Ecenary 0.01).
(b) Non-private DP-SGD.
Figure 2: Sequential audit results using e-process based testing (Algorithm 2) for DP-SGD imple- mentations during training. White-box access with canary gradient threat model over 5 independent runs as 4.2. The e-process approach demonstrates faster detection rates compared Algorithm while maintaining accurate identification of privacy-preserving mechanisms.
D Comparison to DP-Auditorium
In Section 4.1, reported the performance of sequential tests at detecting privacy violations of algorithms for private mean estimation (Table 1) and commented on how these results compare to the ones reported in Audditoror [26]. The presented sequential test differs from -Pdditrtuu in many aspects, so in this section we decouple which of these aspects give the most improvement.
To make this comparison, we set () (0.01, 10-5) and report the rejection rates in Table over 10 runs of different auditing algorithms that gradually move from our sequential algorithm to the MMD-tester from [26]. Recall that the MMD-tester constructs confidence interval [L, U] for MMD from a fixed batch of samples and then rejects if L is greater than the square of the upper bound on the MMD. Below, we list key differences between this algorithms and our sequential procedure.
23

---

Our algorithms use an improved bound on the MMD (see Theorem 3.1), which is tighter than the one used [26].
the RBF kernel. However, estimate the bandwidth using the first 20 samples, which are then not used in the auditing procedure, while in DP-Auditorium the authors the bandwidth to constant. For Table we consider this constant to be 1.
Both [26] and
the median heuristic (MH) [17] to
Our algorithms are sequential, which means that they can potentially detect privacy violations with smaller number of samples. Furthermore, we estimate the witness function using OGA while the MMD-tester just uses an empirical average.
In Table 3, we evaluate the following auditing procedures. The algorithm 'Batch' is the MMD-tester from [26]: it uses a fixed number of samples, the previous MMD bound from [26] and it fixes the bandwidth to 1. The algorithm 'Batch + new MMD bound" replaces the MMD bound by the one that we obtained Theorem 3.1. The algorithm 'Batch + MH' modifies the MMDD-tester by implementing the median heuristic. Finally, 'Batch new MMD bound + MH' implements the MMD-tester along with the improved MMD bound and the median heuristic. Analogously, we define the sequential algorithms: 'Sequential" is implementation of Algorithm that uses the MMD bound from [26] and does not use the median heurstic, and so on.
From Table 3, we observe that some improvement comes from using sequential algorithm², while some also comes from using the median heuristic. We note that the improvement on the MMD bound is not very significant, since for the privacy parameters that chose both bounds are actually close; our bound is better when E is large (e.g., more than 1).
Table 3: We decouple the improvements of Algorithm over the MMD-Tester from [26] by reporting detection rate of privacy violations with different auditing algorithms. We audit the privacy of three mechanisms defined in Section 4: a (0.01, 10 -DDP mechanism (DPGaussian) and two non-DP mechanisms (NonDPGaussian., NonDPGausiin we omit 'Gaussian' from their name in the table. We observe that some improvement comes from using our sequential algorithm, while some of it also comes from using the Median Heuristic (MH). We note that the improvement on the MMD bound is not very significant, since for the privacy parameters that we chose both bounds are actually close.
Auditing Algorithm
DP
NonDP1
NonDP2
Sequential + new MMD bound MH (our Algorithm 1)
Sequential + MH
O
1
1
Sequential + new MMD bound
O
0
1
Sequential
O
0
1
Batch + new MMD bound + MH
0
I
0.1
Batch MH
0
100
0.1
Batch + new MMD bound
0
00
0.5
Batch -ester [26])
0
0.5
E
Technical Details
E.1
Online Newton Step
Below, we present the Online Newton Step algorithm. In Algorithm 1, we run ONS with losses (((A) log(1 + A(ff, K(X,,)) K(Y,, +)H 6)),
"Note that this improvement not necessarily achieved by every sequential test. For example, one could construct confidence sequence ([Le, U/]]= set of intervals such that with high probability, L. S MMD < U, for all 2 1 and reject if L, is larger than the MMD? upper bound [32]. This procedure would typically not improve the batch test.
24

---

Algorithm 3 Online Newton Step in ID
1: Input: Interval (a, bj CR
2: Set Å 0, min a)); 1}, Ao 3'b--a)
min
3: for = 1...do do
4:
Play A and observe loss function &
5: Compute gradient St (Ae(
6: Update scalar A, Ar-1 + o7
7:
A++1 = min max d 3 A, }}
8: end for
Theorem E.1 (Regret of ONS (22]). Let \1, X2... be the ONS iterates according to Algoritium Suppose the functions & (,),,6())) are L-Lipschitz and 1-exp-concave. Then, for every 2 1
EG(A) ((A)) - l((x) & 10L(b a) log(t).
AE(a,b] iE(1
E.2
Online Gradient Ascent
Below we present online gradient ascent. In Algorithm we run OGA with losses
h,() = (S. - -(Y)) ))
Algorithm Online Gradient Ascent RHKS
Input:
Feasible set 9, J1 E
for t= .... do
Play fe E 9, receive loss function he
Compute gradient St (hi(f)) Update f++ = 1lg (fr + T/(tt)
end for
Theorem F.2 (Regret of OGA [36])- Denote D sup jeg IIʃ gllu and let f1s S2,... be the OGA iterates according to Algorithum 4. Suppose that the functions h h-(-), h2(+) are convex and L-Lipschitz and Nte D/ Eieps [VV4(f))l for every 2 Then, for every > 1
Σ ha(s) h.(fa) 3D
3DL Vi.
FEG
iEit
ie(e]
E.3 OGA implementation
Note that OGA is not directly implementable. In particular the functions ft can't be stored computer. The only reason need the functions fe in Algorithm 1 calculate (fe, K(X,,)) K(Y,,)) = Vt- Below, we show how to do this. First, we find an expression for ft. Note that
lg(S) min 1 1 1... Unrolling the recursion given by running OGA with losses hy))
25

---

(f. K(,,())))) (Y,,,))) Mu and denoting M, = Eie(] [| - KY,,, -)12 we obtain
s 2(K(Xx,)) K(Y,, -)
fit1 min
f 2[,( k(Y...]
VM,
V.M.
=
ft ([ ) .(
76
VM,
f 2[K((x-11,)) (Y 31) )
-K((e,;)))))
7
7t-1
VM-1
VM,
2[K((X,,)) K( -)1
73
VM.
KE
j=i
Hence, we obtain the following expression for U/:
K(X,, K(X,,)) YJ) - K(Y, X1) KYY, Yt) 2-1
et (S, K(,, 2 Σ
7/s
VM,
(E
Since Mr = Eien || KY,, 1 Eieny K(X,, 2K(,,, Y,) + KY,,, Y2) for every f, all the terms above Kernel computations, except IT Vi. We find computable expression for these terms.
Recall that Y min 1,
so we only need compute the norm of the
2 /Mz
second term in the minimum. It follows that
fe 2[,(X...)) - -(Y,,.))
= -lfell + 40r/ / + 4(M, - Mc-1)/Mo
VMc
12
1 2[K(X1-1,;)) K(Y -
= x/-1
+ / Me +(4(M -M-1)/M
VM-i
11
2
M,
Mi 1
40r/ Alt/VMM Me + 4(M: Mc-1) 1 +4
Σ
7
VM,
M,
vE[t-1]
All of the terms U1,..., 02, MI,.., Mc, 7,, ..... h have already been computed by the time we need to compute "/. Hence, the above equality a computable expression for Yt.
E.4 Universal Portfolio
The setup for the algorithm is the following. Consider two assets. At each time step t = 1,2,..., T, the market reveals price relative vector
It = (Ir,,, 2r,2) E R
where Tr,i is the ratio of the price of asset time its price at time t- A portfolio is number E [0, 1]. where 3 represents the fraction of wealth invested in asset 1 and (1 - (3) is invested in asset 2. The portfolio is rebalanced the same allocation at each round.
The cumulative wealth achieved by a fixed portfolio 3 E [0, 1] after time steps is given by
W.(3) = II (3x,,1 + (1 - 3)),,,))
26

---

starting from initial wealth Wo(5) 1. At time t, the universal portfolio strategy [9] defines a probability distribution over portfolios E [0. 1]. weighted by their wealth up time Specifically, under prior density ((3) on [0, 1,, the time-/ portfolio is chosen
8t = fo (1-1(13)
So (3) (3)
In our case, T(3) is the Beta (1/2, density:
1 r T
for 3 E (0, 1).
v -
The optimal constant-rebalanced portfolio is
8 E arg max (5)
The cumulative wealth of the universal portfolio strategy
T
W
II [=1
(Bare,1 + (1 -1 -1,),2222))
Theorem E.3 (Regret of UP (Theorem in [10]).. Let 8r E [0, be the best fixed constant- rebalanced portfolio in hindsight:
8 arg max Wi(3).
(E(1.1]
Then the universal portfolio satisfies the regret bound:
log W3())) log W S 5 log(t + 1) + log
This holds deterministically for any sequence of market vectors 21...., Tt E R3
F Analysis of Algorithm 1 on Synthetic Data with Known Distributions
All the experiments presented in the main text and in the following subsections were conducted using
Google Colab's s standard CPU runtime environment (12.7 GB RAM) with Python
F.1 Perturbed uniform distributions
We begin by empirically demonstrating the behavior of our sequential test under two scenarios: when the null hypothesis of equal distributions is true and when false. For the former, we compare two 2-dimensional uniform distributions on the unit cube [0, 1]2 where the auditing process Kr from Algorithm remains bounded below the rejection threshold 1/a for statistical confidence level a = 0.05. Figure 3 confirms that, as expected, we successfully control the Type I error at the desired statistical level when Hg holds, across 100 simulations. For the latter scenario, we apply our test to compare a uniform distribution on [0, 1J against perturbed uniform distribution following the construction in [42] with one perturbation, across 100 simulations. In line with our theoretical predictions, the auditing process K., which measures the cunulative evidence against the null hypothesis, grows exponentially under this alternative hypothesis, as illustrated in Figure 4. The test successfully rejects Hy after, average, collecting only 108 observations.
F.2
Gaussian distributions
We then test our MMD-based sequential approach by comparing two Gaussian distributions while varying the dimensionality and separation between them. We fix one distribution as d-dimensional standard normal distribution P1 ~ (0, Ia). where La is the d-dimensional identity matrix, varying d from I to 5. Our test evaluates Ho MMD(PP,, P2) = 0 against H1 MMD(P1,, IP2) > 0. with P2 N(, Ta) where we vary the center y of the contrast distribution. We set the norm ||l|| to different values between 0 to 1 to illustrate scenarios where the two distributions have different
27

---

100
100
80
Auditing process K;
Auditing process
60
60
Rejection threshold 1/0 20
8 eccitoo fhreshold 1o
20
75 100 125 150 175
25
175 200
Number observations
Number of observations
Figure 3: Type error control in sequential test- ing. The auditing process for 100 simulations comparing two identical 2-dimensional uniform distributions on [0, 1 All trajectories remain below the rejection threshold (horizontal dashed line at 1 1/a), confirming proper Type error con- trol at the a = 0.05 significance level.
Figure Detection power under alternative hy- pothesis. We calculate the auditing process for 100 simulations comparing uniform distribu- tion on [0. 1]2 against a perturhed uniform distri- bution. The exponential growth of the auditing process leads to rejection of the null hypothesis after 108 observations on average.
degrees of separation, making it progressively harder for the test to find evidence against the null as ||д| is closer O. Note that when ||사||| = O, the null hypothesis true.
Figure shows the proportion of tests that reject the null hypothesis across these varying scenarios,
based on 20 simulations for each setting. For separation level of || 2 0.5, the test consistently
rejects Hp correctly, even in nigh-dimensiooal settings (d = 5). With minimal separation (l|şl =
0.25), the rejection rate is 62% when d = 1, degrading its power to 10% in higher dimensions. We also successfully control the Type error when Ho holds (I]иIl = 0), rejecting in fewer than 0.05 of the tests. Figure illustrates the average number of samples needed reject, further demonstrating the advantages of our proposed approach. Our sequential test correctly rejects Ho with fewer than 700 observations, even in high dimensions, when the Gaussian distributions are well-separated (|all 2 0.5), and with fewer than 1000 observations in low-separation settings.
1.0
|ulll -
0.8
||
Mean size to reject
800
||Н] 0.25
||a] - 0.25
||ul| 0.5
0.6
=155
Juull= 0.75
Rejection
600
Hulla
0.4
=|
400
0.2
0.05
200
0.0
Dimension of Mu, distribution
Dimension of Miμ, Ia) distribution
Figure Power analysis of sequential MMD test across dimensions and separation levels. The plot shows rejection rates over 20 simulations comparing (0, Ia) against (p, Ia) with vary- ing dimensionality d and mean separation μ.. Type I error is controlled when ||^|| = 0.
Figure 6: Sample efficiency of sequential MMD test. Average number of observations required for test rejection across different dimensionality (d) and separation (μ4) settings. Lower sample sizes demonstrate the test's efficiency at detect- ing distributional differences.
28

---

G
Auditing DP-SGD for Certain Privacy Regimes
Below we provide additional empirical analysis of our sequential privacy auditing framework applied to DP-SGD implementations across different privacy regimes. We examine two key scenarios that complement our main results. First, Figure audits non-private DP-SGD mechanisms over extended observation periods to demonstrate the evolution of our privacy lower bound estimates. Second, Figure study the inherent limitations of MMD-based approaches when auditing mechanisms with large privacy parameters (s 3). These experiments illustrate both the strengths and practical limitations our sequential testing methodology.
Empirical lower bound &
1.0-
0.8
0.6-
0.4-
0.2-
0.0
500
1000 1500 2000 2500
Number of observations
Figure 7: Extended sequential audit results of non-private DP-SGD implementations over 2,500 observations. The audit successfully rejects privacy hypotheses and establishes increasingly tight lower bounds on the privacy parameter.
Empirical lower bound 3
2.5
Ecanary 2.75
1.5
1.0
0.5
0.0
100
200
300
400
500
Number of observations
Figure 8: Sequential audit results for private DP-SGD implementations with large privacy parameters (Ecanery 2.75, 8 10-5). The empirical lower bound grows slowly due the small gap A between the MMD and the rejection threshold 7(c, demonstrating the sample complexity challenges in this regime.
H Detailed Comparison with Related Work
Verifying that a randomized mechanism satisfies DP guarantee involves checking that a specific divergence (related to the privacy parameters and o) remains bounded over all possible pairs of neighboring datasets. This task often divided into two sub- uub-problems: (I) identifying a "worst-case" or dominating pair of neighboring datasets, that maximizes the privacy loss, and (2) accurately estimating or bounding the divergence induced by this dominating pair. While our work focuses on the second sub- bob-problem, we start by briefly review approaches for tackling the former. Although concept sequential privacy auditing appears new to our knowledge, we then provide review of different methodologies within the field that are relevant to the second problem of divergence estimation and bounding. We finish by summarizing relevant work in the broader area of sequential hypothesis testing.
29

---

Identifying worst-case datasets has been tackled through methods like grid search over datasets [11, 5], explicit construction under strong parametric assumptions on the mechanism [14]. black- box optimization techniques that iteratively search for high-privacy-lon inputs [26], or the use of predefined canaries [33]. More recent approaches showed efficient testing relying on randomized canaries for specific mechanisms like the Gaussian mechanism in high dimensions [2]. Black- box optimization approaches treat divergence maximization as an objective but often lack formal guarantees finding the true worst case [26]. Our proposed auditing method can be paired with any technique for identifying candidate worst-case dataset pairs.
Given candidate pair of neighboring datasets, the core challenge is to estimate the resulting privacy loss or divergence. There is substantial prior work on this, primarily situated within the batch setting, where a fixed number of samples are drawn a priori.
Estimating distances or divergences between distributions is classical statistics problem [34, 47, 6]. Some methods employ optimization over function spaces, such as neural networks, to estimate f- divergences Rényi divergences. While powerful, the finite-sample guarantees provided by some of these methods can depend on estimator properties (e.g., neural network architecture) and may become vacuous for DP auditing purposes [6]. Furthermore, many provide only asymptotic guarantees, whereas DP requires strict finite-sample bounds. Our work, in contrast, leverages sequential analysis to provide anytime-vall valid results with potentially much lower sample complexity.
Our approach relies on sequential testing with kernel methods, specifically the Maximum Mean Discrepancy (1M 44), construct test statisties. Prior work on privacy auditing has also used kernel methods, such as estimating regularized kernel Rényí divergence [13], but often requires strong assumptions (e.g., knowledge of covariance matrices) impractical in black-box settings for mechanisms beyond Gaussian or Laplace.
Some auditing techniques require strong assumptions, like discrete output space [18] or access to the mechanism's 's internal randomness or probability density/mass functions [12]. Others need access to the edf of the privacy loss random variable [14]. StatDP [11] requires semi-black black-box access (e.g.. running the mechanism without noise) [11]. While our method can incorporate white-bor information to improve power, it fundamentally operates in the black- setting. The applicability of these methods that require strong assumptions is limited in the blackbox setting.
For the general black-box setting, tools like DP-Sniper [5], DP-Opt [35], Delta-Siege [28], and Eureka [29] perform black-box testing by searching for an output event maximizing the probability difference between neighboring inputs. However, DP-Sniper is specific to pure e-DP, Delta-Siege for "p-ordered mechanisms" " and all suffer from high sample complexity (millions of samples) in the batch setting.
significant body of work focuses on auditing machine learning models. particularly those trained with DP-SGD. This includes membership inference attacks (MIA) [24, 37, 7, 23] and data reconstruc- tion attacks [21, 4]. These methods often require white-box access to the model and sometimes large portions of the training data, but more importantly, work in the batch setting, requiring significant compute power. In the best case, they require training one full model end-to-end with canaries inserted every other step. For some easy to detect failures this might be wasting resources, and when the test fails, one has to start from scratch and previous samples cannot be reused for significant testing.
30

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Our contributions in the introduction are well explained in the main body and experiments in section 4.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We discuss limitations in the Discussion section and throughout the main body.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
31

---

All necessary assumptions are included in the theorem statements in the main body. All proofs can be found in the appendices.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification:
We provide all details of our experimental setup in the experiments section.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
32

---

Answer: [Yes]
We include a well-documented python notebook to reproduce all our experi- ments.
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. ec/
iiyy for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / //nips. cc/
/eliddeseCooeubinn wwisssolicccyyii for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We include all experimental settings and details in the Experiments section.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
All our results are averaged over several runs for statistical significance.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
33

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπхо rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We include the computational resources needed to reproduce our experiments in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: / hwtpp//bbic/thhhcccuuu..e...ee
Answer: [Yes]
Justification:
Our research conforms, in every respect, with the NeurIPS Code Ethics
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- cration due to laws or regulations their jurisdiction..
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our work aims advancing auditing differential privacy guarantees. There are none societal consequences of our work we feel must be specifically highlighted here.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
34

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper does not release data or models that have a high risk for misuse.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We properly cite licensed datasets and previous work.
Guidelines:
existing assets. The authors should cite the original paper that produced the code package or dataset.
The answer NA means that the paper does
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
35

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
No new assets introduced.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/codeemmodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: Our paper does not include crowdsourcing experiments or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation,
or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: Our paper does not include research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
36

---

16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: The methods in our research do not involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https: //tp:r//es...///eeee tweeurip..ccooofeeeeeeeee.e /LLM) for what should or should be described.
37


Reviews:
[{"review_id": "jXqKpqs7Gg", "reviewer": "Reviewer_7Q2v", "summary": "This paper proposes new methods for auditing differentially private\nalgorithms. Specifically, the paper focuses on approximate\ndifferential privacy and proposes to use a methodology inspired by\nrecent work on sequential hypothesis testing based on the theory of\ne-values, which are roughly nonnegative random variables\ncharacterizing the evidence for rejecting a null hypothesis, which\ncompose well adaptively. The proposed tests are based on maximum mean\ndiscrepancy and uses Online Newton Step and Online Gradient Ascent for\nlearning the needed parameters. The paper presents an experimental\nevaluation on multiple mechanisms and benchmarks.", "questions": "Your test uses OGA and ONS as black boxes. Does it means that you could obtain better tests by using similar algorithms with improved guarantees?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n\n- The paper uses a recently developed approach to sequential hypothesis\n  testing to address the problem of auditing differentially private\n  mechanisms\n\n- the tests presented in the paper improves considerably in terms of\n  performance with respect to previous approaches\n\nWeaknesses\n\n- The experimental evaluation does not provide any direct comparison with\n  previous methods,\n\n- similar to some previous work, the paper assumes that worst-case\n  adjacent databases are known.\n\nSeveral work have studied auditing methods for differentially private\nmechanism, especially in the context of differentially private\noptimization and learning. This paper brings new methods to this area\nby introducing an approach based on sequential hypothesis testing\nusing e-values. The paper combines this ideas in a test using off the\nshelf learning algorithms to learn some of the parameters needed for\ndeciding the test. The proposed tests are more adaptive than the ones\nproposed in previous work and are able to converge faster. This makes\nthem more efficient for auditing purposes than previous\napproaches. The efficiency is evaluated experimentally in the paper\nwith encouraging results. Although, to be fair, there is not concrete\nexperimental comparison of the proposed method with previous works.\nOne limitation, acknowledged by the paper, is that the paper assumes\nthe knowledge of worst-case adjacent databases. This makes the\nproposed approach more aligned with tools for auditing privacy\nparameters rather than with tools for finding privacy violations.", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the thoughtful review and helpful feedback. Below we address weaknesses and questions. \n\n# Weaknesses\n\n>`The experimental evaluation does not provide any direct comparison with previous methods (...)  The efficiency is evaluated experimentally in the paper with encouraging results. Although, to be fair, there is not concrete experimental comparison of the proposed method with previous works.`\n \t\n\nIn lines 287-290 we briefly compare our results to those of DP-Auditorium [A] in the black box setting. We will add this comparison more explicitly to our result tables. \n\nThe experiment conducted to audit DP-SGD in section 4.2 follows the auditing procedure from [B]. We will add a comparison to the lower bounds that they report in their Figure 3. \n\n\n>`One limitation, acknowledged by the paper, is that the paper assumes the knowledge of worst-case adjacent databases.`\n\nWe appreciate the reviewer's observation. While it would be ideal to have an end-to-end universal auditing pipeline, finding these databases often depends on the specific mechanism and potential bugs being tested [A]. Indeed, the assumption that worst-case adjacent databases are known is a common practice in the literature. While existing work has explored various heuristics, such as online optimization and carefully crafted canaries [A, B], a more rigorous approach with worst-case guarantees remains a challenging open problem. \n\n# Questions\n>`Your test uses OGA and ONS as black boxes. Does it means that you could obtain better tests by using similar algorithms with improved guarantees?`\n\nGreat question! The answer is yes: the faster the stochastic process considered for testing grows under the alternative, the sooner the test rejects. \n\nIndeed, two recent papers proposed to replace ONS by algorithms that allow optimizing the parameters $\\lambda$ over a larger interval and with smaller regret constants: [C] proposed to use the universal portfolio and [D] an optimistic interior point method. We empirically verified the practical benefits of using the approach from [C] and will include these new experiments in the appendix. \n\n### References\n\n[A] Kong, William, et al. \"DP-Auditorium: A Large-Scale Library for Auditing Differential Privacy.\" 2024 IEEE Symposium on Security and Privacy (SP). IEEE, 2024.\n\n[B] Nasr, Milad, et al. \"Tight auditing of differentially private machine learning.\" 32nd USENIX Security Symposium (USENIX Security 23). 2023.\n\n[C] Waudby-Smith, Ian, Ricardo Sandoval, and Michael I. Jordan. \"Universal log-optimality for general classes of e-processes and sequential hypothesis tests.\" arXiv preprint arXiv:2504.02818 (2025).\n\n[D] Chen, Can, and Jun-Kun Wang. \"Optimistic interior point methods for sequential hypothesis testing by betting.\" arXiv preprint arXiv:2502.07774 (2025)."}, {"review_id": "ZeWsOx9BOp", "reviewer": "Reviewer_pxSP", "summary": "The paper proposes a Maximum Mean Discrepancy (MMD)-based one-sided sequential test for auditing differential privacy. It enables anytime-valid inference with Type I error control, overcoming the inefficiency of prior batch tests. The authors also derive a new bound linking MMD to the Hockey-Stick divergence, which improves test power. Experiments show the method detects DP violations with far fewer samples—e.g., within a single DP-SGD training run, whereas the previous method requires a complete training round—thus making it practical and efficient for real-world use.", "questions": "It would be helpful if the authors could elaborate on how Algorithm 1 is applied to audit DP-SGD in practice. Since DP-SGD is an iterative algorithm where each update depends on previous model parameters, the gradients at different iterations are not i.i.d. samples from a fixed distribution pair. This seems to violate the assumption in Line 5 of Algorithm 1, where samples $ X_t \\sim A(S) $ and $ Y_t \\sim A(S')$ are assumed to be drawn independently from two fixed distributions.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strength:**  \nThe paper presents a novel MMD-based one-sided sequential testing framework for auditing differential privacy, introducing testing-by-betting techniques that are new to this area. A notable strength is the ability to detect violations without requiring a full training run.\n\n\n**Weakness:**  \n* The method assumes access to a fixed worst-case pair of neighboring datasets $(S, S')$. Identifying such pairs can be difficult in practice, limiting the method's applicability in fully black-box settings.\n* The method relies on estimating the function $f_t$ via online optimization (e.g., Online Newton Step), which introduces additional computational overhead.\n* It would also be helpful to include experiments comparing the accuracy of the proposed method with that of existing one-run auditing methods, to contextualize potential computation-accuracy tradeoffs.\n\n\n\n\n\n\n\n\n\n\n* It would also be helpful to include experiment comparising the accuracy against one-run auditing methods", "was_revised": true, "final_justification": "I will keep my positive score.", "rebuttal": "Thank you for the thoughtful review and helpful feedback. Below we address weaknesses and questions. \n\n## Weaknesses\n>`The method assumes access to a fixed worst-case pair of neighboring datasets. Identifying such pairs can be difficult in practice, limiting the method's applicability in fully black-box settings.`\n\nWe appreciate the reviewer's observation. While it would be ideal to have an end-to-end universal auditing pipeline, finding these databases often depends on the specific mechanism and potential bugs being tested [A]. Indeed, the assumption that worst-case adjacent databases are known is a common practice in the literature. While existing work has explored various heuristics, such as online optimization and carefully crafted canaries [A, B], a more rigorous approach with worst-case guarantees remains a challenging open problem. \n\nNote that the applicability of the method is not necessarily limited by this: our method preserves its statistical validity when run on ${\\it any}$ fixed pair of neighboring datasets, and even on time-varying pairs of datasets selected by heuristics. However, the power of the test might decrease when S and S' are not a worst-case pair of neighboring datasets. \n\n>`The method relies on estimating the function via online optimization (e.g., Online Newton Step), which introduces additional computational overhead.`\n\nThe MMD-based two sample test in requires O(n^2) kernel evaluations the batch setting. Our sequential algorithm uses O(k) kernel evaluations in step k (see equation below line 973) which still adds up to O(n^2) kernel evaluations after n steps, but it often stops sooner, making the computational overhead minimal (if one exists). We discuss further implementation details of OGA in Section C.3. \n\n>`It would also be helpful to include experiments comparing the accuracy of the proposed method with that of existing one-run auditing methods, to contextualize potential computation-accuracy tradeoffs.`\n\nWe thank the reviewer for this important question. First, it should be noted that the accuracy of the trained classifier using the DP-SGD algorithm is not affected by our auditing procedure following the white-box setting in [B].\n\nRegarding the hypothesis-test accuracy, our sequential testing framework naturally encompasses a one-run audit as a special case: when our sequential test does not reject the null hypothesis throughout the entire SGD training process, it effectively becomes equivalent to a one-run MMD-based audit using the complete gradient set. This ensures our method's accuracy is always at least as good as comparable one-run approaches while potentially allowing for faster detection rates.\n\nWe thank the reviewer again for the opportunity to clarify this important point and will ensure the revised manuscript better positions our contribution relative to one-run auditing methods. \n\n\n# Questions\n\n>`It would be helpful if the authors could elaborate on how Algorithm 1 is applied to audit DP-SGD in practice.`\n\nThis is an important point and we thank the opportunity to clarify this in detail. We will update the manuscript with this explanation.\n\nWe adopt the standard white-box auditing procedure introduced as Algorithm 2 in [B]. This procedure gives the auditor access to all training hyperparameters (in particular, clipping norm and batch size for rescaling), online access to the intermediate privatized gradient during DP-SGD training, and the ability to insert canaries (specific crafted examples) to each sampled batch. \n\nThe procedure works as follows: at  each training step $t$ a batch $B_t$ of examples is sampled. The auditor computes two private gradients: $\\tilde{\\nabla}[t]$ from the standard gradient $B_t$ and $\\tilde{\\nabla}'[t]$ where a canary gradient $g_t'$ was inserted. This canary is constructed to be orthogonal to all other per-example gradients within its batch. The auditor collects one-dimensional samples $x_t, y_t$, corresponding to the dot product between the canary $g_t'$ and the gradients: $x_t = \\langle g_t',\\tilde{\\nabla}[t]\\rangle$ and $y_t = \\langle g_t',\\tilde{\\nabla}'[t]\\rangle$.\n\nSince $\\langle g_t',g\\rangle = 0$ for all $g \\in B_t$, then $\\langle g_t',\\tilde{\\nabla}[t]\\rangle =  \\langle g_t',Z_t \\rangle$ where $Z_t$ is the i.i.d. Gaussian noise added for privacy. Similarly, for the privatized gradient with the canary included we obtain that $\\langle g_t',\\tilde{\\nabla}’[t]\\rangle=\\langle g_t',g_t’+\\nabla[t] + Z_t’ \\rangle=\\|g_t’\\|^2+\\langle g_t',\\nabla[t]\\rangle + \\langle g_t',Z_t’ \\rangle = \\|g_t’\\|^2 + 0 +\\langle g_t',Z_t’ \\rangle$. \n\nFinally, the clipping norm and batch size are known by the auditor in the white-box setting, the samples can be rescaled. This process yields $\\{x_t\\}$ drawn from a Gaussian distribution $N(0,\\sigma^2)$ and $\\{y_t\\}$ where the canary was present, drawn from $N(1, \\sigma^2)$. \n\n\n>`Since DP-SGD is an iterative algorithm where each update depends on previous model parameters, the gradients at different iterations are not i.i.d. samples from a fixed distribution pair. This seems to violate the assumption in Line 5 of Algorithm 1, where samples Xt and Yt are assumed to be drawn independently from two fixed distributions.`\n\nThe procedure above for auditing DP-SGD does satisfy the i.i.d assumption, given that it reduces to distinguishing i.i.d. samples from two Gaussian distributions. In practice, crafting time-varying canaries $g'_t$ to ensure exact orthogonality can be computationally intensive. For this reason, practitioners use a simpler static “Dirac” canary (all dimensions are set to zero and one element is set to 1). This well-established approximation is known to be highly effective and yields tight privacy bounds (see Fig. 14 in [B]). This method for generating samples for a two-sample test is widely adopted in the privacy auditing literature [A-G], but as the reviewer correctly pointed out, it does break the iid assumptions on the data. We will make sure to clarify this in the manuscript.\n\nHowever, we note that the proposed sequential auditing framework is amenable for time-varying distributions, for the two-sample test. See section 5.1. in [H]. \n\n### References\n\nLetters used for references ensure consistency accross reviewers.\n\n[A] Kong, William, et al. \"DP-Auditorium: A Large-Scale Library for Auditing Differential Privacy.\" 2024 IEEE Symposium on Security and Privacy (SP). IEEE, 2024.\n\n[B] Nasr, Milad, et al. \"Tight auditing of differentially private machine learning.\" USENIX Security Symposium. 2023.\n\n[E] Ponomareva, Natalia, et al. \"How to dp-fy ml: A practical guide to machine learning with differential privacy.\" Journal of Artificial Intelligence Research (2023).\n\n[F] Steinke, Thomas, Milad Nasr, and Matthew Jagielski. \"Privacy auditing with one (1) training run.\" NeurIPS (2023).\n\n[G] Andrew, Galen, et al. \"One-shot empirical privacy estimation for federated learning.\" ICLR (2023).\n\n[H] Shekhar, Shubhanshu, and Aaditya Ramdas. \"Nonparametric two-sample testing by betting.\" IEEE Transactions on Information Theory 70.2 (2023)."}, {"review_id": "B7L7Mq29WS", "reviewer": "Reviewer_codM", "summary": "Given two neighbouring datasets $S$ and $S’$, a mechanism $\\mathcal{A}$, and i.i.d samples $X_1, X_2, \\dots \\sim \\mathcal{A}(S)$ and $Y_1, Y_2 \\dots \\sim \\mathcal{A}(S’)$, this paper studies sequential hypothesis tests for distinguishing between:\n- $H_0$: the Hockey-stick divergence of order $e^\\epsilon$ between $\\mathcal{A}(S)$ and $\\mathcal{A}(S’)$ is smaller than $\\delta$ \n\nV.S. \n\n- $H_1$: the Hockey-stick divergence is $> \\delta$. \n\nFirst, to solve this, the paper uses the Maximum Mean Discrepancy (MMD) as a proxy for the Hockey-stick divergence. While this proxy was explored in prior work (e.g., [23]), the authors tighten the connection in Theorem 3.1. Then, the paper adapts the “two-sided” sequential MMD Test from [40] into a “one-sided” test against a specific non-zero threshold.  A practical sequential test is developed (Algorithm 1) and analysed with guarantees on Type I error, expected stopping time, and exponential growth under the alternative in Theorem 3.3.  Finally, the test is implemented to audit first some classic mean estimation DP mechanisms, then to audit DP-SGD in the white-box setting.", "questions": "- What exactly are the “non-trivial adaptations and subtle but key modifications of the original results\npresented in [ 40 ]” (Line 140)? Could you explicitly enumerate or summarise what changes were needed to adapt the two-sided test to your one-sided setting?\n\n\n- Improving further Theorem 3.1 via TV: In the proof of Theorem 3.1, it seems that you first upper bound the MMD by a Total Variation (TV). But it seems that Remark A.1.b) in the paper by Kairouz et al. (“The Composition Theorem for Differential Privacy”) provides tighter bounds on TV in terms of DP parameters. Can't you directly plug in those to yield an even tighter bound than your Theorem 3.1?\n\n- Isn’t auditing DP-SGD in the white-box setting equivalent to auditing the mean mechanism applied to gradients, and thus section 4.2 is the same as section 4.1? If not, what are the differences?\n\n- Is it possible to use your sequential test for auditing DP-SGD in the black-box model, i.e. you only have query access to the learned model and not access to gradients anymore?", "limitations": "There is no specific \"limiations\" sections in the paper, but the authors discuss them throughout the paper", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strength:\n- The paper is well-written and the problem is well-motivated\n- The idea of applying sequential hypothesis testing techniques for DP auditing is novel and interesting\n- The paper provides a practical test, with both non-trivial theoretical guarantees and good experimental results\n\nWeakness:\n- As stated multiple times in the paper, the main limitation of the test proposed is the assumption that the two neighbouring datasets $S$ and $S’$ are given as input. In most practical DP auditing settings, generating such pairs, especially worst-case ones, is the most challenging part, and this part is not addressed in the paper.\n\n- The terms \"black-box\" and \"white-box\" are used inconsistently or imprecisely. For instance, in the first part, \"black-box\" meant that the auditor does not know the inner functioning of the mechanism $\\mathcal{A}$, while in the DP-SGD auditing, “white-box” means that the auditor has access to the intermediate gradients, but still does not know the inner functioning of the mechanism $\\mathcal{A}$. A clearer definition of these terms early in the paper would help.\n\n\n- While the adaptation of the test from [40] is useful, the technical novelty compared to [40] is still unclear/incremental. The paper could do more to explicitly highlight what is technically new beyond switching from two-sided to one-sided.", "was_revised": true, "final_justification": "The authors' rebuttal addressed my questions. I kept a borderline accept recommendation due to the assumption that the two neighbouring datasets are given as input to the auditing algorithm, rather than generated. This is the main limitation for this line of work, as generating worst-case neighbouring datasets is arguably the hardest part of auditing DP.", "rebuttal": "Thank you for the thoughtful review and helpful feedback. Below we address weaknesses and questions. \n\n# Weaknesses\n\n>`As stated multiple times in the paper, the main limitation of the test proposed is the assumption that the two neighbouring datasets S and S’ are given as input. In most practical DP auditing settings, generating such pairs, especially worst-case ones, is the most challenging part, and this part is not addressed in the paper.`\n\nWe agree with the reviewer's observation and tried to make this point clear in our presentation. While it would be ideal to have an end-to-end universal auditing pipeline, finding these databases often depends on the specific mechanism and potential bugs being tested [A]. Indeed, the assumption that worst-case adjacent databases are known is a common practice in the literature. While existing work has explored various heuristics, such as online optimization and carefully crafted canaries [A, B], a more rigorous approach with worst-case guarantees remains a challenging open problem. \n\n>`The terms \"black-box\" and \"white-box\" are used inconsistently or imprecisely. For instance, in the first part, \"black-box\" meant that the auditor does not know the inner functioning of the mechanism, while in the DP-SGD auditing, “white-box” means that the auditor has access to the intermediate gradients, but still does not know the inner functioning of the mechanism. A clearer definition of these terms early in the paper would help.`\n\nWe appreciate the feedback on our use of “black-box” and “white-box” terminology. We will ensure a precise and consistent use of these terms throughout the manuscript. Specifically, we define a black-box audit as one where the auditor observes only the mechanism's outputs, without knowledge of its internal functioning. Conversely, a white-box setting, like the DP-SGD auditing approach, provides access to specific internal states, such as intermediate gradients, allowing for more granular analysis. \n\n>`While the adaptation of the test from [40] is useful, the technical novelty compared to [40] is still unclear/incremental. The paper could do more to explicitly highlight what is technically new beyond switching from two-sided to one-sided.` \n\nSee our response in the questions section below.\n\n# Questions\n\n>`What exactly are the “non-trivial adaptations and subtle but key modifications of the original results presented in [ 40 ]” (Line 140)? Could you explicitly enumerate or summarise what changes were needed to adapt the two-sided test to your one-sided setting?`\n\nTwo-sided tests – like the hypothesis tested in [A] – are fundamentally different from one-sided tests, such as the one in our paper. We address this distinction in lines 176–215 in our manuscript, especially lines 188–198, which detail the necessary changes. In summary, the algorithmic changes are following:\n\n1. First, we adapted the process $$\\prod_t (1+ \\lambda_t [f_t(X_t) - f_t(Y_t)])$$ from [A] by subtracting a term $\\tau(\\epsilon, \\delta)$, which is derived in Theorem 3.1. This resulted in the new process $$\\prod_t (1+ \\lambda_t [f_t(X_t) - f_t(Y_t) - \\tau(\\epsilon, \\delta)]).$$\n\n2. Second, we restricted $\\lambda$ to the interval $[0,1/(2+\\tau(\\epsilon,\\delta))]$, while in [A] was considered to be in [-1/2,1/2]. This restriction is essential for two reasons:\n   - $\\lambda \\ge 0$ ensures that the process is a supermartingale under the null;\n   - and $\\lambda \\leq 1/(2+\\tau(\\epsilon,\\delta))$ guarantees that the process remains nonnegative at all times.\n\n    Both of these are required for using Ville’s inequality for stopping-time guarantees.\n\nWhile seemingly minor, each of these changes is theoretically essential and not obvious a priori. Indeed, previous work attempting to adapt [A] to the one-sided setting did not provide stopping-time guarantees, and their corresponding process grew more slowly under the alternative than ours (see lines 199–215).\n\nA final difference from [A] is how we ensure fast growth under the alternative. While [A] proves that their process grows rapidly for some $\\lambda^* \\in [-1/2, 1/2]$, our analysis must guarantee that such a $\\lambda^*$ exists within the more constrained interval we consider; this needs to be taken into account in our analysis (line 893).\n\n>`Improving further Theorem 3.1 via TV: In the proof of Theorem 3.1, it seems that you first upper bound the MMD by a Total Variation (TV). But it seems that Remark A.1.b) in the paper by Kairouz et al. (“The Composition Theorem for Differential Privacy”) provides tighter bounds on TV in terms of DP parameters. Can't you directly plug in those to yield an even tighter bound than your Theorem 3.1?`\n\nThanks for the reference. Our goal was to connect MMD with Approximate DP, and in our proof we directly work with these two definitions. One could have alternatively first used a total variation (TV) bound on MMD, and continue by applying Remark A.1.b) from Kairouz et al. to the TV. We find that through both methods we arrive at the same MMD upper bounds. We will include this alternative proof in our final manuscript. \n\n>`Isn’t auditing DP-SGD in the white-box setting equivalent to auditing the mean mechanism applied to gradients, and thus section 4.2 is the same as section 4.1? If not, what are the differences?`\n\nWe appreciate the opportunity to clarify the relationship between our empirical experiments in Section 4.1 (DP mean estimation) and Section 4.2 (DP-SGD). Indeed, we agree that our general auditing framework is similarly  applied to two sets of samples, mean estimation samples and white-box DP-SGD gradients, and more broadly, to observations from any two i.i.d. distributions.\n\nHowever, Section 4.2 demonstrates a crucial distinction: the overall procedure allows for auditing a model trained with DP without training multiple models as one would need according to black-box audits in section 4.1.\n\nLeveraging white-box access delivers significant efficiency gains for complex mechanisms like DP-SGD. Specifically, while black-box audits (as in Section 4.1) require training the full model for each new sample, white-box DP-SGD auditing avoids this by leveraging intermediate gradient updates. These gains apply both to batch and sequential testing. However, sequential testing can take even more advantage by further applying the auditing method sequentially, enabling DP-SGD auditing in less than one complete training run. This represents a substantial improvement in auditing efficiency for a complex, iterative mechanism like DP-SGD, differentiating it from a simpler, black-box mean mechanism audit.\n\n\n> `Is it possible to use your sequential test for auditing DP-SGD in the black-box model, i.e. you only have query access to the learned model and not access to gradients anymore?`\n\nYes! it is possible to audit DP-SGD in a black-box setting where only query access to the learned model is available. In such a scenario, the auditing approach would effectively be the same as that presented in Section 4.1, as the entire training process would need to be run to draw each new sample for our sequential auditing framework. We will discuss this black-box DP-SGD auditing scenario and its implications in our experiments section for added clarity.\n\n### References\n\n[A] Kong, William, et al. \"DP-Auditorium: A Large-Scale Library for Auditing Differential Privacy.\" 2024 IEEE Symposium on Security and Privacy (SP). IEEE, 2024.\n\n[B] Nasr, Milad, et al. \"Tight auditing of differentially private machine learning.\" USENIX Security Symposium. 2023.\n\n[H] Shekhar, Shubhanshu, and Aaditya Ramdas. \"Nonparametric two-sample testing by betting.\" IEEE Transactions on Information Theory 70.2 (2023)."}, {"review_id": "oz3HfLTJ8l", "reviewer": "Reviewer_9SwZ", "summary": "Recently there has been a great deal of interest in \"auditing\" differential privacy guarantees of algorithms such as DP-SGD among others. The popular approach to auditing DP usually looks at sample size as static -- it runs the DP mechanism as a black-box n times with different randomness, and then provides an answer about its privacy properties. Usually, it provably accepts every DP mechanism, and empirically rejects non-private mechanisms with a certain amount of probability. \n\nThis work proposes a new framework and mechanism to audit DP mechanisms in a different, sequential way. If I understand correctly, here the number t of runs of the black-box is varying (and growing), and the algorithm either decides to terminate with a decision, or to keep asking for more samples. These tests are enabled through drawing a novel connection between differential privacy, and recent advances in sequential hypothesis testing. There is also a nice theorem on the relationship between the Hockey-stick divergence and kernel-MMD tests that is of independent interest.", "questions": "None.", "limitations": "n/a", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strengths:\n\n+ This is a very strong and novel paper. The result is strong and elegant and arises due to a novel connections between two disparate areas. I also really liked the last part about auditing DPSGD in less than one run, which is a novel advance.\n+ The paper is quite well-written, and even though the math is fairly dense it feels easy to read. Related works are well-cited and credit properly assigned. \n\nWeaknesses:\n\n- One weakness of the presentation is that this paper audits DP in a framework that is somewhat different from the standard auditing framework. It took me a while to understand this -- and I think the presentation could be even better if this were directly explained earlier on in the paper. \n- A minor point -- the first DPSGD paper was actually Song, S., Chaudhuri, K., & Sarwate, A. D. (2013, December). Stochastic gradient descent with differentially private updates. In 2013 IEEE global conference on signal and information processing (pp. 245-248). IEEE.", "was_revised": true, "final_justification": "This is a strong paper that combines novel ideas from disparate communities to prove a nice result. I strongly recommend acceptance!", "rebuttal": "Thank you for the thoughtful review and helpful feedback. Below we address weaknesses and questions. \n\n# Weaknesses\n\n>`One weakness of the presentation is that this paper audits DP in a framework that is somewhat different from the standard auditing framework. It took me a while to understand this -- and I think the presentation could be even better if this were directly explained earlier on in the paper.`\n\nThe hypothesis tested in the proposed sequential auditing framework coincides with previous work [A, B]. However, we take a different approach to testing this hypothesis: instead of fixing the sample size a priori  to construct a single confidence interval (or test), we allow $n$ to grow and run a sequential test that can be continuously monitored and adaptively stopped. We will explain this difference with prior work in more detail in the introduction.\n\n> `A minor point -- the first DPSGD paper was actually Song, S., Chaudhuri, K., & Sarwate, A. D. (2013, December). Stochastic gradient descent with differentially private updates. In 2013 IEEE global conference on signal and information processing (pp. 245-248). IEEE.`\n\nThanks for pointing out the correct first DP-SGD paper. We will update the citation.\n\n[A] Kong, William, et al. \"DP-Auditorium: A Large-Scale Library for Auditing Differential Privacy.\" 2024 IEEE Symposium on Security and Privacy (SP). IEEE, 2024.\n\n[B] Nasr, Milad, et al. \"Tight auditing of differentially private machine learning.\" USENIX Security Symposium. 2023."}]

Author rebuttal:

Meta-review: This paper proposes a sequential testing framework for auditing DP. 

All the reviewers agree the method is novel, and the results are very promising. Although some reviewers concern about the assumption of the neighbouring datasets, they believe the results are strong enough.

Therefore, I recommend the acceptance of the paper.
Decision: Accept (poster)