Auditing $f$-differential privacy in one run
Authors: Saeed Mahloujifar
Luca Melis
Kamalika Chaudhuri
Venue: ICML 2025 oral (2025)
Keywords: Empirical privacy
Auditing
Differential Privacy
Primary area: social_aspects->privacy
TL;DR: We perform tests to audit whether a privacy mechanism satisfies $f$-differential privacy. We only invoke the privacy mechanism once.

Abstract: Empirical auditing has emerged as a means of catching some of the flaws in the implementation of privacy-preserving algorithms. Existing auditing mechanisms, however, are either computationally inefficient -- requiring multiple runs of the machine learning algorithms —- or suboptimal in calculating an empirical privacy. In this work, we present a tight and efficient auditing procedure and analysis that can effectively assess the privacy of mechanisms. Our approach is efficient; Similar to the recent work of Steinke, Nasr and Jagielski (2023), our auditing procedure leverages the randomness of examples in the input dataset and requires only a single run of the target mechanism. And it is more accurate; we provide a novel analysis that enables us to achieve tight empirical privacy estimates by using the hypothesized $f$-DP curve of the mechanism, which provides a more accurate measure of privacy than the traditional $\epsilon,\delta$ differential privacy parameters. We use our auditing procure and analysis to obtain empirical privacy, demonstrating that our auditing procedure delivers tighter privacy estimates.

Auditing SoattinggfDiffeeee f-Differential Privacy in One Run
Saeed Mahloujifar Luca Melis Kamalika Chaudhuri!
Empirical auditing has emerged as a means of catching some of the flaws in the implementation of privacy preeeccirnn algorithms. Existing auditing mechanisms, however, are either computationally inefficient - requiring multiple runs of the machine learning algorithms - or suboptimal in calculating an empirical privacy. In this work, we present a tight and efficient auditing procedure and analysis that can effectively assess the privacy of mechanisms. Our approach is efficient; similar the recent work of Steinke, Nasr, and Jagielski (2023), our auditing procedure leverages the randomness of examples in the input dataset and requires only a single (training) run of the target mechanism. And it is more accurate; we provide a novel analysis that enables us to achieve tight empirical privacy estimates by using the hypothesized f-DP curve of the mechanism, which provides more accurate measure of privacy than the traditional c, 5 differential privacy parameters. We use auditing procure and analysis to obtain empirical privacy, demonstrating that our auditing procedure delivers tighter privacy estimates.
tation, or potentially providing stronger privacy guarantees that are not evident through a loose analysis.
Empirical privacy auditing (Ding et al., 2018; Nasr et al., 2023; Jagielski et al., 2020) has emerged as a critical tool to bridge this gap. By experimentally assessing the privacy of mechanisms, empirical auditing allows for the verification of privacy parameters. Specifically, an audit procedure is randomized algorithm that takes implementation of mechanism M, runs it in a black-box manner, and attempts to test privacy hypothesis (such as, a differential privacy parameter). The procedure outputs O if there is sufficient ev- idence that the mechanism does not satisfy the hypothesized guarantees and I otherwise. The audit mechanism must possess two essential properties: 1) it must have a provably small false-negative rate, ensuring that it would not erro- neously reject a truly differentially private mechanism, with high probability; 2) it needs to empirically exhibit a "rea- sonable" false positive rate, meaning that when applied to a non-differentially private mechanism, it would frequently reject the privacy hypothesis. The theoretical proof of the false positive rate is essentially equivalent to privacy ac- counting (Abadi al., 2016; Dong et al., 2019; Mironov, 2017), which is generally thought to be impossible in black-box manner (Zhu et al., 2022).
1. Introduction
Differentially private machine learning (Chaudhuri et al., 2011; Abadi et al., 2016) has emerged principled so- lution to learning models from private data while still pre- serving privacy. Differential privacy (Dwork, 2006) is a cryptographically motivated definition, which requires an algorithm to possess certain properties: specifically, a ran- domized mechanism differentially private if it guarantees that the participation of any single person in the dataset does not impact the probability of any outcome by much.
The prior literature on empirical audits of privacy consists of two lines of work, each with its own set of limitations. The first line of work (Ding et al., 2018; Jagielski et al., 2020; Tramer et al., 2022; Nasr et al., 2023) runs a differentially private algorithm multiple times to determine if the privacy guarantees are violated. This is highly computationally in- efficient for most private machine learning use-cases, where running the algorithm involves training a large model.
Enforcing this guarantee requires the algorithm to be care- fully designed and analyzed. The process of designing and analyzing such algorithms is prone to errors and imperfec- tions as has been noted in the literature (Tramer et al., 2022). result of this is that differentially private mechanisms may not perform as intended, either offering less privacy than expected due to flaws in mathematical analysis or implemen-
Recent work (Steinke et al., 2023) remove this limitation by proposing an elegant auditing method that runs a differ- entially private training algorithm a single time. In particu- lar, they rely on the randomness of training data to obtain bounds the false negative rates of the audit procedure. A key limitation of the approach in (Steinke et al., 2023) is that their audit procedure is sub-optimal in the sense that there is a relatively large gap between the true privacy parameters of mainstream -weeeccereeeeiingggg algorithms (e.g.. Gaussian mechanism) and those reported by their auditing algorithm.
'Meta. Correspondence to:
Saeed Mahloujifar
<sacedm @ meta.com?>
Proceedings of the 4hnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
In this work, we propose novel auditing procedure that is

---

Auditing /-Differential Privacy in One Run
computationally efficient and accurate. Our method requires only single run of the privacy mechanism and leverages the f-DP curve (Dong et al., 2019), which allows for more fine-grai fine-grained accounting of privacy than the traditional reliance on 6, 6 parameters. By doing so, we provide a tighter empirical assessment of privacy,
satisfying f-DP. This bound is an improved version of the result by (Hayes et al., 2023) for bounding train- ing data reconstruction in DP mechanisms. However, this is insufficient, as the adversary's 's guesses could be dependent, potentially leading to correlated successes (e.g.. correctly or incorrectly guessing all samples).
We experiment with our approach on both simple Gaussian mechanisms as well as a model trained on real data with DP-SGD. Our experiments show that our auditing procedure can significantly outperform that of (Steinke et al., 2023) (see Figure 1). This implies that better analysis may enable relatively tight auditing of differentially privacy guarantees in a computationally efficient manner in the context of large model training.
2. To address the issue of dependency, we refine our anal- ysis by defining pa as the probability of the adversary making exactly i correct guesses. We derive recursive relation that bounds p; based on .i..... Pi-i. This re- cursive bound is the main technical novelty of our work. To derive this bound, we consider two conditions: the adversary correctly guesses the first canary or not. In the first case, we use our analysis from Step I to bound the probability of making i 1 correct guesses given that the first guess was correct. For the incorrect guess case, we perform combinatorial analysis to eliminate the condition. This analysis uses the fact that shuffling of the canaries does not change the probabilities of making i correct guesses. We note that it is crucial not to use the analysis of Step for both cases. This is because the analysis of Step 1 cannot be tight for both cases at the same time. Finally, leveraging the convexity of trade-off functions and applying Jensen's 's inequality, we derive our final recursive relation. To the best of our knowledge, This combination of trade-off function with shufflig is a new technique and could have broader applications.
Technical overview: We briefly summarize the key tech- nical components of our work and compare it with that of Steinke al. (2023). Their auditing procedure employed game similar to membership inference process: the ditor selects set of canaries and, for each canary, decides whether to inject it into the training set with independent probability 0.5. Once model training is completed, the au- ditor performs a memhership inference attack to determine whether each canary was included. The number of correct guesses made by the adversary in this setting forms a ran- dom variable. The key technical contribution of Steinke et al. was to establish tail bound on this random variable for mechanisms satisfying (c)-DP. Specifically, they demon- strated that the tail of this random variable is bounded by that of a binomial distribution, binomial (n. p). where n is the number of canaries and p = e++1' To extend this anal- ysis to approximate DP mechanisms, they further showed that the probability of the adversary's success exceeding this tail bound is at most O(n 8).
Finally, we design an algorithm that takes advantage of the recursive relation to numerically calculate an upper bound on the tail of the distribution. The algorithm is designed carefully so that we do not need to invoke the result of step 2 for very small events.
ex
Steinke et al. highlighted a limitation in their approach in auditing specific mechanisms, such as the Gaussian mech- anism. They correctly argue that simplifying the mecha- nism's 's behavior to just two parameters, (c,8), results in sub- optimal auditing of specific mechanisms. In other words, the effectiveness of membership inference attacks against the Gaussian mechanism differs significantly from predic- tions based solely on the (c, () parameters. To overcome this limitation, we propose auditing the entire privacy curve of a mechanism, rather than focusing solely on (e, 5). Our solution involves three key technical steps:
We also generalize our analysis to broader notion of canary injection and membership inference. Specifically, we utilize a reconstruction game where the auditor can choose among k options for each canary point, introducing greater entropy for each choice. This generalization allows for auditing mechanisms with fewer canaries.
In the rest of the paper, we first introduce the notions of f-DP and explain what auditing based on f-DP entails. We then present our two auditing procedures based on mem- bership inference and reconstruction attacks (Section 2). In Section 3, we provide tight analysis of our audit's 's accuracy based on f-DP curves. Finally, in Section 4, we describe the experimental setup used to compare the bounds.
1. We derive an upper bound on the adversary's s success in correctly guessing a specific canary for mechanisms
II the context of preneccireseving training of machine Iearn- ing models, the privacy mechanism refers to the training algorithm. Therefore, when we mention a single run, we specifically re- ferring single execution of the training algorithm, not the inference algorithm.
2. Auditing f- differential privacy
Auditing privacy involves testing a "privacy hypothesis" about an algorithm M. Different mathematical forms can be
2

---

Auditing f-Differential Privacy in One Run
used for "privacy hypothesis," " but they all share the com- mon characteristic of being about an algorithn/mechanism M. For example, one possible hypothesis is that applying SGD with specific hyperparameters satisfies some notion of privacy. With this in mind, the privacy hypothesis are often mathematical constraints on the sensitivity of the al- gorithm's 's output to small changes in its input. The most well-known definition among these is differential privacy.
[0, 1]. Also, for a family of trade-off functions F, we use marimall (F) to denote the set of maximal elements w.r.t the privacy relation. Note that F could be a partial ordered set, and marimal( ()) may have multiple elements.
Now that we have defined our privacy hypothesis, we can turn our attention to auditing these notions.
Definition 2.6 (Auditing f-DP). An audit procedure takes the description of mechanism M, a trade-off function f. and outputs a bit that determines whether the mechanism satisfies f-DP or not. We define it as a two-step procedure.
Definition 2.1. A mechanism M (c, 6)-DP if for all neigh- boring datasets S,8' with |SAS|| = 1 and all measurable sets T, we have (S(M(S) E 7] S e (S" E T] + 6.
In essence, differential privacy ensures that the output distri- bution of the algorithm does not heavily depend on a single data point. Based on this definition, one can hypothesize that a particular algorithm satisfies differential privacy with certain and 6 parameters. Consequently, auditing differen- tial privacy involves designing a test for this hypothesis. We will later explore the desired properties of such an auditing procedure. However, at present, we recall a stronger notion of privacy known as f f-differential privacy.
game: M - O, In this step, the auditor runs a po- tentially randomized experiment/game using the de- scription of mechanism M E M and obtains some observation o E O.
evaluate O x F - {0, 1]. In this step, the auditor will output a bit b based on an observation o and a trade-off function f. This audit operation tries to infer whether the observation is "likely" for a mechanism that satisfies f-DP.
Notation For function f: [0, 1] + [0. we use f to denote the function f(x) 1 - f(x).
The audit procedure is vi-accurate if for all mechanism M that satisfy f-DP, we have
Definition 2.2. A mechanism .M is f-DP if for all neigh- boring datasets S,S' and all |SAS'| measurable sets T we have
Pr [evaluate(o, = 2 v). o gM
Pr(M(S) E ET ((PMM((S)) E T
Note that we are defining the accuracy only for positive cases. This the only guarantee we can get from attacks. For guarantees in negative cases, we need to perform privacy accounting for the mechanism (Wang et al., 2023).
Note that this definition generalizes the notion of approx- imate differential privacy by allowing a more complex re- lation between the probability distributions of M()) and (S*). The following proposition shows how one can ex- press approximate DP as an instantiation of f-DP.
Next, we formally define the notion of empirical pri- vacy (Nasr et al., 2021) based on an auditing procedure. This notion provides the best privacy guarantee that is not violated by auditors' observation from a game setup.
Proposition 2.3. A mechanism is (DP if it is f-DP with respect to fxx = c x + 5.
Definition 2.7 (Empirical Privacy). Let (game, evaluate) be an audit procedure. We define the empirical privacy random variable for mechanism M, w.r. family F of trade-off functions, to be the output of the following process. We first run the game to obtain observation o = [game We then construct
Although the function f could be an arbitrary function, without loss of generality, we only consider a specific class of functions in this notion.
Remark 2.4. Whenever we say that a mechanism satisfies f- DP, we implicitly imply that ff is a valid trade-off function. That is, f is defined on domain J0, 1] and has a range of [o, 1]. Moreover, J is a decreasing and convex with (xx) S 1 1-a xr for all E [0, 1]. We emphasize that this is without loss of generality. That is, if mechanism is f-DP for a arbitrary function f [0, 1] + [0, 1]. then it is also DD for valid trade-off function f' with f'(x)= < ((x for all I E [0, 1] (See Proposition 2.2 in (Dong et al., 2019)).
F. mazimal([f e F; evaluate(o, f) = 1})
where the maximal set constructed according to Definition 2.5. Then, the empirical privacy of the mechanism at a particular å is defined as
<()) min max log( 1- fx) 5 TeFoxEl0.11
x
Definition 2.5 (Order of f-DP curves). For two trade-off functions fi and fe. we say fi is more private than fa and denote it by fi 2 fz iff fxx 2 fa(x) for all x E
Note that the empirical privacy c(8) is a function of the observation o. Since, o itself is a random variable, then e(6) is also a random variable.
3

---

Auditing (-Differential Privacy in One Run
How to choose the family of trade-off functions? The family of trade-off functions should be chosen based on the expectations of the true privacy curve. For example, if one expects the privacy curve of a mechanism to be similar to that of a Gaussian mechanism, then they would choose the set of all trade-off functions imposed by a Gaussian mechanism as the family. For example, many believe that in the hidden state model of privacy (Ye & Shokri, 2022), the final model would behave like Gaussian mechanism with higher noise than what is expected from the accounting in the white-box model (where we assume we release all the intermediate models). Although we may not be able to prove this hypothesis we can use our framework to calculate the empirical privacy, while assuming that the behavior of the final model would be similar that of Gaussian mechanism.
the method of (Steinke al., 2024b). We observe that this improves the performance over the plain method but there it still has large gap with direct f-DP auditing. The details and results of this experiment are reported in Section 4.2.
2.1. Guessing games
Here, we introduce the notion of guessing games which is generalization of membership inference attacks (Nasr et al., 2023), and closely resembles the reconstruction setting in- troduced in (Hayes et al., 2023).
Definition 2.8. Consider a mechanism M: : [ - θ In a guessing game we first sample an input dataset u E [A]]* from an arbitrary distribution. We run the mechanism to get 0 (u). Then guessing adversary A O + ([A) U {1)) tries to guess the input to the mechanism from the output. We define
Auditing f-DP vs DP: f-DP can be viewed as a collec- tion of DP parameters, where instead of considering (c as fixed scalars, we treat e as a function of 5. For any 5 [0, 1), there exists <(ō) such that the mechanism satisfies (c(6),5) 5)DPP. The f-DP curve effectively represents the entire privacy curve rather than single (e,5) pair. Thus, auditing f-DP can be expected to be more effective, as there are more constraints that need to be satisfied. A naive approach for auditing f-DP is to perform an audit for ap- proximate DP at each (e, 6) value along the privacy curve, rejecting if any of the audits fail. However, this leads to sub- optimal auditing performance. First, the auditing analysis involves several inequalities that bound the probabilities of various events using differential privacy guarantees. The probability of these events could take any number between [0, 1]. Using a single (c, d) value to bound the probability of all these events cannot be tight because the linear ap- proximation of privacy curve is tight in at most single point. Hence, the guarantees of (e, 0DP cannot be simul- tancously tight for all events. However, with f-DP, we can obtain tight bounds on the probabilities of all events simulta- neously. Second, For each (e, 5) we have a small possibility of incorrectly rejecting the privacy hypothesis. So if we audit privacy for (E()). 5) independently, we will reject any privacy hypothesis with probability 1.0. This challenge can be potentially resolved by using correlated randomness.
the number of guesses by d d'= ΣT m I((()) + 1)
. and the number of correct guesses by =
E T(A0), = uu)
Then we output (c, c') the output of the game.
These guessing games are integral to our auditing strategies. We outline two specific ways to instantiate the guessing game. The first procedure is identical to that described in the work of (Steinke et al., 2023) and resembles membership inference attacks. The second auditing algorithm is based on the reconstruction approach introduced by (Hayes et al., 2023). In Section 3. we present all of our results in the context of the general notion of guessing games, ensuring that our findings extend to both the membership inference and reconstruction settings.
Auditing by membership inference: Algorithm 1 de- scribes a game setup based on membership inference at- tacks. In this setup, we have a fixed training set T and a set of canaries C. We first sample a subset S of the canaries using poisson sampling. Then we run the mechanism M on T U S to get a model 0 ~ ~MTT U S). Then the adversary A inspects 0 and tries to find examples that were present in S. Observe that this procedure is a guessing game with h = 2 and m = [C]. This is simply because the adversary is guessing between two choices for each canary, it is either included or not included. Note that this procedure is modu- lar, we can use any T and C for the training set and canary set. We can also use any attack algorithm A.
To demonstrate this key difference, we try a baseline for d auditing f-DP based on the work of (Steinke et al., 2024b)?. In this baseline, we consider a gaussian mechanism with noise a. Then, we audit the privacy curve at various values of 6. For this, we need to make sure that we run the attack once (the correlated randomness mentioned above), so we fix the number of guesses to be the optimal choice for 8 = 10-5, Then we observe the attack's 's performance and apply
We note that membership inference attacks have received a lot of attention recently (Homer et al., 2008; Shokri et al., 2017; Leino & Fredrikson, 2020; Bertran et al., 2024; Hu et al., 2022; Matthew et al., 2023; Duan et al., 2024; Zarifzadeh et al., 2023). These attack had key difference
This experiment was suggested by our anonymous reviewer. We than the reviewer for their suggestion.
4

---

Auditing /-Differential Privacy in One Run
from our attack setup and that is the fact that there is only single example that the adversary is trying to make the inference for. Starting from the work of (Shokri et al., 2017), researchers have tried to improve attacks in various settings (Ye et al., 2022; Zarifzadeh et al., 2023). For example, using calibration techniques has been an effective way to improve membership inference attacks (Watson et al., 2021; Carlini et al., 2022). Researchers have also changed their focus from average case performance of the attack to the tails of the distribution and measured the precision at low recall values (Ye et al., 2022; Nasr et al., 2021).
canary sets (8) E [m]] where each S contains k distinct examples. Before training, we construct set Sg of size m by uniformly sampling an example from each St Then, the adversary tries to find out which examples were sampled from each canary set S by inspecting the model. We recog- nize that this might be different from what one may consider true "reconstruction attack", because the adversary is only performing a selection. However, if you consider the set size to be arbitrary large, and the distribution on the set be arbitrary, then this will be general enough to cover various notions of reconstruction. We also note that (Hayes et al., 2023) use the same setup to measure the performance of the reconstruction attacks.
A substantial body of research has also explored the relation- ship between membership inference attacks and differential privacy (Sablayrolles et al., 2019; Mahloujifar et al., 2022:
Algorithm 2 Reconstruction in one run game
Balle et al., 2022; Bhowmick et al., 2018; Stock et al., 2022:
input Oracle access to a mechanism M(.), A training
Balle et al., 2022; Guo et al., 2022: Kaissis et al., 2023;
dataset T, number of canaries m, number of options for each canary &, a matrix of canaries C = {ay h (e())))))) an attack algorthm A.
2024), using this connection to audit differential privacy (Steinke et al., 2024a; Pillutla et al., 2024; Jagielski et al., 2020; Ding et al., 2018; Bichsel et al., 2018; Nasr et al., 2021; 2023; Steinke et al., 2024b; Tramer et al., 2022; Bich- sel et al., 2021; Lu et al., 2022: Andrew et al., 2023; Cebere et al., 2024; Annamalai & De Cristofaro, 2024; Chadha et al., 2024). Some studies have investigated empirical methods to prevent membership inference attacks that do not rely on differential privacy (Hyland & Tople, 2019; Jia et al., 2019; Chen & Pattabiraman, 2023; Li et al., 2024; Tang et al., 2022; Nasr et al., 2018). An intriguing avenue for future research is to use the concept of empirical privacy to compare the performance of these empirical methods with provable methods, such as DP-SGD.
1: Let u = (u), (u1,..., Um) be a vector uniformly sampled from [k]m.
2: Let S = fat,, heemm]
3: Run mechanism M on S SUT to get output 0.
4: Run a reconstruction attack A on @ to get a vector v =
(UI,..., vm) which is a vector in ([k] U {1))_.. Count e the number of coordinates where u, = us and d the number of coordinates where e F 1.
return c).
Algorithm 1 Membership inference in one run game
3. Implications of f-DP for guessing games
input Oracle access to a mechanism MM-), A training dataset T, An indexed canary set C = ( E [m]], An attack algorithm A.
In this section. we explore the implications of f-DP for guessing games. Specifically, we focus bounding the probability of making more than e correct guesses for adver- saries that make at most c' guesses. We begin by stating our main theorem, followed by an explanation of how it can be applied to audit the privacy of a mechanism.
1: Set m = |C]
2: Sample u (u....., um) ~ (0.),, a bi-
nary vector where u; = 1 with probability 0.5.
3: Let S = [Clu.]; uq 1 he]mj. the subset of selected
Theorem 3.1. [Bounds for adversary with bounded guesses] Let M [K|Th - be a f-DP mechanism. Let be random variable uniformly distributed on [k]m Let A: θ
elements in C.
4: Run mechanism M on TUS to get output 6.
5: Run membership inference attack A on to get set of membership predictions e = (v),..., vm) which is supported on (0, 1, 11
[[K] U {1})m be guessing adversary which always makes at most d' guesses, that is
m
6: Count c, the number of correct guesses where ut i
AA E O,
(2
(A((), + +)) > =0.
and c' the total number of guesses where vi # 1. return (c,
and let = A(M())) Define p. Pr [[ I(u;
vz) i For all subset of indices T C [c'), we have
Auditing by reconstruction: We also propose an alter- native way to perform auditing by reconstruction attacks. This setup starts with a training set S,, similar to the mem- bership inference setting. Then, we have a family of m
Σ ET
p: 5 k
Σ
- iiit
1)-
k-1
m
iET
5

---

Auditing [-Differential Privacy in One Run
This Theorem, which we consider to be our main technical contribution, provides a nice invariant that bounds the prob- ability pi (probability of making exactly i correct guesses) based on the value of other Pys. Imagine Py to be set of could vectors p= (p1...., Per) that could be realized for an attack on a f-D mechanism. Theorem 3.1 significantly confines this set. However, this still does not resolve the auditing task. We are interested in bounding ma Line Pi. the maximum probability that an adversary can make more than e correct guesses for an f-DP mechanism. Next, we show how we can algorithmically leverage the limitations imposed by Theorem 3.1 and calculate an upper bound on maxpery EizP Pi-
[ k, m,,,e e. and 5, then for any S-DP mechanism M: [M]m + O any guessing adversary A: O + ([) {-))a² with at most c' guesses, defining to be uni-
form over [k]m. and setting v = (uM(),), we have
Pr[ t I(u, = v.)) 2d S..
In nutshell, this algorithm tries to obtain an upper bound on the sum Pe + Pc+1 ..... P We assume this probability is greater than T, and we obtain lower bound on Pc-1 + Pe Pe + +... Pe based on this assumption. We keep doing this recursively until we have lower bound on pa + +... + Per. If this lower bound greater than 1, then we have a contradiction and we return true. The detailed proof of this Theorem is involved and requires careful analysis. We defer the full proof of Theorem to appendix.
3.1. Numerically bounding the tail
When auditing the fDD for a mechanism, we assume we have injected m canaries, and ran an adversary that is allowed to make e' guesses and recorded that the adversary have made correct guesses. In such scenario, we will reject the hypothesized privacy of the mechanism if the probability of this observa- tion is less than a threshold r. which we by default set to 0.05. To this end, we just call Algorithm with parameters c, d', m, 7 = 0.05 and f. Then if the algorithm returns True, we will reject the privacy hypothesis and approve it otherwise.
Auditing f-DP with Algorithm 3:
In this subsection, we specify our procedure for bounding the tail of the distribution and hence the accuracy of our auditing procedure. Our algorithm needs oracle access to f and f and decides an upper bound on the probability of an adversary making correct guesses in a guessing game with alphabet size k and mechanism that satisfies f-DP. This algorithm relies on the confinement imposed by Theorem 3.1. Note that Algorithm 3 is decision algorithm, it takes a value r and decide if the probability of making more than e correct guesses is less than or equal to r. We can turn this algorithm to a estimation algorithm by performing a binary search on the value of т. However, for our use cases, we are interested in fixed T. This is because we (similar to (Steinke et al., 2023)) want set the accuracy of our audit to be fixed value such as 0.95.
Empirical privacy: Although auditing in essence is hy- pothesis testing, previous work has used auditing algorithms to calculate empirical privacy as defined in definition 2.7. In this work, we follow the same route. For simplicity, we only consider an ordered set of privacy hypotheses hi...., hw as our family of f-DP curves. These sets are ordered in their strength, meaning that any mechanism that satisfies lt, would also satisfy hy for all < i. Then, we would report the strongest privacy hypothesis that passes the test as the empirical privacy of the mechanism.
Algorithm 3 Numerically deciding an upper bound proba- bility of making more than correct guesses
input Oracle access to f and f-',, number of guesses c', number of correct guesses e, number of samples m, alphabet size k. probability threshold (default is T 0.05).
4. Experiments
1: VO < i S set h[i] 0, and r[:] = O.
2: set r(c] = T m
Most of our experiments are conducted in an idealized set- fing, similar that used in (Steinke al., 2023), unless otherwise stated. In this setting, the attack success rate is automatically calculated to simulate the expected number of correct guesses by an optimal adversary (details of the ideal- ized setting are provided in Algorithm 4 in Appendix). We then use this expected number as the default value for the number of correct guesses to derive the empirical e. More specifically, as specified in Detinition 2.6, we instantiate our auditing with game and evaluation setup. We use Al- gorithm 4 in Appendix as our game setup. This algorithm returns the number of guesses and the number of correct guesses as the observations from the game. Then, we use Algorithm as our evaluation setup to audit an f-DP curve based on the observation from Algorithm Note that in our
3: set hlc] = T d'mc
m
4: for i E 'c L......) 0] do
5: hi]] = (k- -1)f (rli 1])
6: r[i] = rii + 1|+
hli + 11). (hli)
7: end for
8: if r[0] + A[0] 2 then
9:
Return True; (Probability of e correct guesses (out of
c') is less than T).
10:
else
11:
Return False; (Probability of having e correct guesses (out of c)) could be more than r).
12:
end if
Theorem 3.2. If Algorithm returns True on inputs
6

---

Auditing /-Differential Privacy in One Run
comparison with the auditing of Steinke al., we always use the same membership inference game setup (k = 2) as defined in their work. This ensures that our comparison is only on the evaluation part of the audit procedure.
(Zagoruyko & Komodakis, 2016) architecture, which sub- stitutes batch normalization with group normalization. We follow the setting proposed by (Sander et al., 2023), which use custom augmentation multiplicity (i.e., random crop around the center with 20 pixels padding with reflect, ran- dom horizontal flip and jitter) and apply an exponential moving average of the model weights with a decay param- eter of 0.9999. We run white-box membership inference attacks by following the strongest attack used in the work of (Steinke et al., 2023), where the auditor injects multiple canaries in the training set with crafted gradients. More precisely, each canary gradient is set to zero except at a single random index ("Dirac canary" (Nasr et al., 2023)). Note that in the white-box attack, the auditor has access to all intermediate iterations of DP-SGD. The attack scores are computed as the dot product between the gradient update during consecutive model iterates and the aggregated gra- dients from dp-sgd. As done in the work of (Steinke et al.,
In all experiments, we use empirical 6 as the primary metric for evaluating our bounds.
f-DP candidates: As described in Section 3.1, , we need an ordered set of f-DP curves to obtain empirical privacy. In our experiments, we use f-DP curves for Gaussian mech- anisms with varying standard deviations (this forms or- dered set because the f-DP curve of a Gaussian mechanism with a higher standard deviation dominates that of a lower standard deviation). For sub-sampled Gaussian mechanisms, the ordered set consists of f-DP curves for sub-sampled Gaussian mechanisms with fixed sub-sampi sub-sampling rates and number of steps, and various noise stds.
2023), we audit CIFAR-IO model with m = 5, 000 canaries and all training points from CIFAR- 10 n = 50, 000 for the attack. We set the batch size to 4, 096, using augumented multiplicity of K = 16 and training for 2, 500 DP-SGD steps. For 8.0, 5 10-5, we achieved 77% accuracy when auditing, compared to 80% without injected canaries. Figure 2 shows the comparison between the auditing scheme by (Steinke et al., 2023) with ours for different values of theoretical E. We are able to achieve tighter empirical lower bounds. We also report the performance of the black-box at- tack, where the auditor does not control the training pipeline and can only compute membership scores (losses) from the final model. Figure 3 shows how achieve tighter lower bounds compared to Steinke et al. (2023) where we set m = 1, 000 and all training samples are used for auditing (m = n). This corresponds to the stronger setup for the black-box auditor in Steinke et al. (2023).
4.1. Comparison with (Steinke et al., 2023)
In this section, we evaluate our auditing method for mem- bership inference in an idealized setting, using the work of (Steinke et al., 2023) as our main baseline. We compare our approach directly to their work, which operates in the same setting as ours.
Simple Gaussian Mechanism: In the first experiment (Figure 1), we audit a simple Gaussian mechanism, varying the standard deviations from [0.5, 1.0, 2.0, 4.0). resulting in different theoretical c values. We vary the number of ca- naries (m) from 102 to 10" for auditing, set the bucket size to k = 2, and adjust the number of guesses (c') for each number of canaries. For each combination of m, c', and each standard deviation, we calculate (c) using Algorithm 4 (the idealized setting in appendix). This algorithm calculates the expected number of correct guesses for an adversary who observes the output of an mnddimensional gaussian mecha- nism, V -N"0", o), with V being a uniform sample from f0, 1m The adversary's ' goal is to guess d' coordinates in V. c is calculated to be the expected number of correct guesses by the optimal adversary. Note that this setup is designed as the worst-case scenario for the gaussian mecha- nism. After obtaining c, we then audit all tuples of (m, c, c') using the f-DP curves of the Gaussian mechanism. Then we find the e that achieves the highest empirical and then report that as the empirical e. We audit the exact same setup with the auditing method of (Steinke et al., 2024b). Figure I demonstrates that our approach outperforms the empirical privacy results from Steinke et al. Interestingly, while the bound in Steinke et al. (2023) degrades as the number of canaries increases, our bounds continue to improve.
Finally, we report the results of auditing the robust mem- bership inference attack (Zarifzadeh et al., 2023) (RMIA), which to the best of our knowledge, represents the State- The-Thtrrt (SoTA) black-box membership inference attack on CIFAR-10 10 from the literature. We reproduce the results in (Zarifzadeh et al., 2023) with a non-private WedeRes.Net model (with depth 28 and width 2) for 100 training epochs on half of the dataset chosen at random resulting on a test accuracy of 92.2%. We run the low-cost black-box member- ship inference attack using 2 reference models in the offline setting (Zarifzadeh et al., 2023). We audit with m 5, 000 canaries and report in Figure 4 the comparison between our scheme and (Steinke et al., 2023) with different abstention values. Our auditing method elearly outperforms Steinke et al. for all bounded guesses settings, with higher empirical epsilon for larger abstention values (i.e., fewer guesses).
Experiments on CIFAR-10: We also run experiments on CIFAR-10 on a modified version of the WRN16
7

---

Auditing /-Differential Privacy in One Run
Noise-0.50
Ncise=1.00
Noisem2.00
Noisem4.00
Impiital
28
15-
32-
18-
Legincal Raam
Amprica (019)
38
bypince (10
Mumber Canaries
Number
Number Catarite
Nammerr Cenaries
Figure 1. Comparison between empirical privacy lower bounds and that of (Steinke et al., 2023) at 5 = 10-3,
Empirical Lower Dounds ve. Thecretical Cosilon
Black box MIA from Zenfizedch et al224 (Offline, Reference models)
Stoinke al.
this
Theorstical
Empiica EmgncclEysiinn Exstin
Empinca spalon
Thooretical Spo
2000
4030
6000
0000
10000
Figure 2. Comparison with auditing procedure of (Steinke et al., 2023) on CIFAR-I0 white-box setting using gradient- based membership inference. Empirical is reported at 10-5
Figure 4. Comparison with auditing procedure of (Steinke al., 2023) on non-private model trained on CIFAR-I0 against black- box RMIA method (Zarifzadeh al., 2023). Empirical reported at 5 = 10-5
Thés puper
Theorebcol
available. For the case of 5 = O, their bound is tight. For the case of 5 however, they need to define a set of undesirable events and bound their collective probability, This incurs additional O(m 5) in the probability. The reason why their bounds start to degrade when we increase m is this very fact. The m 8 term starts to dominate and causes the empirical epsilon estimation to become worse. The reason we do not observe this behavior is that we do not use (e, 8) to approximate the privacy curve, we use the exact curve as is. As we know, the linear approximation of privacy curve is optimal only in single point for mechanisms that we are interested in (e.g. the Gaussian mechanism). Namely, there is only single probability p' E [0, where we have
Emoinca Easton
Thoonetical Epsiio
Figure 3. Comparison with Steinke et al. (2023) for CIFAR-10 10 in black-hox setting. Empirical is reported at 10
p = Pr(M(D) E) and e" p P E E).
Why is our bound better better than (Steinke et al., 2023)? The bounds in Steinke et al. audit approximate DP. That is, they take DP parameters (c, 8) and prove an upper bound on the probability of any adversary obtaining correct guesses out of e total guesses, given m canaries
Our bound is designed to avoid this issue. We derive bound that uses the exact f-DP curve, which ensures that for all probabilities p E [0, 1] the upper bound on the blow-up of events of size p is tight. Moreover, the way we invoke our Theorem 3.1 in our numerical estimation designed to
8

---

Auditing /-Differential Privacy in One Run
Noise
# Canaries
Theoretical
Steinke et al.
Steinke et al. (pointwise)
Ours
σ = 0.5
10
9.99
4.99
5.01
8,16
о 1.0
10s
4.37
2.61
2.71
3,61
σ 2.0
105
1.99
1,33
1.35
1.59
a = 4.0
106
0.92
0.61
0.67
0.82
Table 1. Comparison of empirical privacy Gaussian noise levels. The reported numbers of are empirical at å = 10
apply the bound events that can be simultancously tight. This way, our bound does not have the problem of getting worse as the number of samples increases.
game. Using (m, c, c'c we can now auditing (es, 8)-DP for large range of values of ó (8 10- for 60 different values of x linearly spread between 3 to 9), where is the privacy of a gaussian mechanism with a given noise at 6. Then, we reject the privacy hypothesis for gaussian- if any of the individual tests are rejected. Using this auditing procedure, we obtain empirical epsilon values.
Note that this does not mean that there is no way to improve our bound. We still see some gap between the empirical epsilon and the true epsilon. The reason for this, we believe, is in the way numerical tail bound in Algorithm 3.2 is de- signed. In this algorithm, we make some relaxations that can be a source of sub-optimality. Specifically, our analysis benefits from the fact that the expectation of correct guesses, conditioned on the correct guesses being greater than c di- vided by the expectation incorrect guesses conditioned on the same event greater than e/c. This step is not tight as we cannot have a mechanism where the adversary makes exactly correct guesses with probability greater than O, while making more than correct guesses with probability exactly O. For a more interested reader, Equations 6 and 7 in the proof of Theorem 3.2 is a source of sub-optimality that future work can resolve.
Table 1 shows the results of our experiments. We can that there is still large gap between our auditing and the multiple run of the approach of previous work as described above. As discussed in Section 2, the reason for the multiple testing method being inferior to our direct f-DP auditing is that in the multiple DP-auditing approach, each auditing procedure is oblivious other points on the f-DP curve and can only observe single point on the curve. Whereas for our method, the audit procedure observes the entire curve. This point has also been discussed by the authors of (Steinke et al., 2024b) as a limitation on of their approach.
5. Conclusions and limitations
4.2. Improving (Steinke et al., 2024b) by testing multiple hypothesis.
We introduce a new approach for auditing the privacy of algorithms in single run using f-DP curves. This method enables more accurate approximations of the true privacy guarantees, addressing the risk of a "false sense of privacy" that may arise from previous approximation techniques. By leveraging the entire f-DP curve, rather than relying solely on point estimates, our approach provides a more nuanced understanding of privacy trade-offs. This allows practition- ers to make more informed decisions regarding privacy- utility trade-offs in real-world applications. However, our approach does not provide a strict upper bound on privacy guarantees but instead offers an estimate of the privacy pa- rameters that can be expected in practical scenarios. We also recognize that, despite the improvements over prior work, we still observe a gap between the empirical and theoretical privacy reported in the "one run" setting. Future work could focus on closing this gap to further enhance the reliability of empirical privacy estimations.
In this section, we describe a method that uses the method of (Steinke et al., 2024b) to audit S-DP. We use the idea that if a mechanism satisfies f-D,, then for all d E [o, 1] it should pass the DP audit for (ca, 5), where cs is the optimal e obtained from / for 8. A key issue here is that auditing in one run will always suffer from probabilistic error. There is a small chance t that the audit mechanism rejects the privacy hypothesis incorrectly. When doing the test multiple times, then we have to multiply the the failure probability by the number of trials.
However, we can avoid this by using shared randomness between trials. Specifically, if we only run the privacy game once and use the output of the game to audit privacy for different values of (c. 8), we can potentially avoid this mul- tiplication. Here, we design an experiment that shows even with this this approach, the bounds of previous work cannot mathh ours. We try auditing Gaussian DP. First we in- stantiate membership inference game with fixed number of canaries (m) and fixed number of guesses (c'). This is optimized to achieve the best e at d = 10-5, We collect the number of correct guesses (c) in the membership inference
9

---

Auditing /-Differential Privacy in One Run
Impact Statement
ciples. In 2022 IEEE Symposium on Security and Privacy (SP), pp. 1897-1914. IEEE, 2022.
This paper aims to advance the empirical measurement of algorithmic privacy. By improving our ability to evaluate the privacy risks associated with machine learning and data processing systems, this work contributes to the develop- ment of more trustworthy and accountable Al technologies. The main socictal benefit is positive: practitioners and pol- icymakers will be better equipped to assess and mitigate potential privacy harms, leading to safer deployment of data-driven systems.
Cebere, T., Bellet, A., and Papernot, N. Tighter privacy
auditing of dp-sgd in the hidden state threat model. arXiv preprint arXiv:2405. 144557....44,, 2024.
Chadha, K., Jagielski, M., Papernot, N., Choquette- Cheoo,,teeCho, C., and Nasr, M. Auditing private prediction. arXiv preprint WxXiv2442.099033 2024.
Chaudhuri, K., Montelconi, C., and Sarwate, A. D. Differ- entially private empirical risk minimization. Journal of Machine Learning Research, 12(3), 2011.
References
Abadi, M., Chu, A., Goodfellow, I., McMahan, H. B., Mironov, I., Talwar, K., and Zhang, L. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference computer and communications security, pp. 0088-11,222 2016.
Chen, Z. and Pattabiraman, K. Overconfidence dan- gerous thing: Mitigating membership inference attacks by enforcing less confident prediction. arXiv preprint drXiv:2307.016110 2023.
Ding, Z., Wang, Y., Wang. G., Zhang, D., and Kifer, D. De- tecting violations of differential privacy. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, pp. 475-489, 2018.
Andrew, G., Kairouz, P., Oh, S., Oprea, A., McMahan, H. B., and Suriyakumar, V. One-shot empirical pri- vacy estimation for federated learning. arXiv preprint arXiv:2302.03009. 2023.
Dong, J., Roth, A., and Su, W. J. Gaussian differential privacy. arXiv preprint arXiv: 000.1/00500000 00.390330...,..0. 2019.
Annamalai, M. S. M. S. and De Cristofaro, E. Nearly tight black-box auditing of differentially private machine learn- ing. arXiv preprint arXiv:2405. 11022440..111..... 14106, 2024.
Duan, M., Suri, A., Mireshghallah, N., Min, S., Shi, W., Zettlemoyer, L., Tsvetkov, Y., Choi, Y., Evans, D., and Hajishirzi, H. Do membership inference attacks work on large language models? arXiv preprint arXiv:2402.07841, 2024.
Balle, B., Cherubin, G., and Hayes, Reconstructing train- ing data with informed adversaries. In 2022 IEEE Sympo- sium on Security and Privacy (SP), pp. 1 1138-1156. IEEE, 2022.
Dwork, C. Differential privacy. In International colloquium automata, languages, and programming, pp. 1-12. Springer, 2006.
Bertran, M., Tang, S., Roth, A., Kearns, M., Morgenstem, H., and Wu, S. 7. Scalable membership inference attacks via quantile regression. Advances in Neural Infor- mation Processing Systems, 36, 2024.
Guo, C., Karrer, B., Chaudhuri, K., and van der Maaten, Bounding training data reconstruction in private (deep) learning. In International Conference Machine Learn- ing, pp. 8056-80711 PMLR, 2022.
Bhowmick, A., Duchi, J.. Freudiger, J., Kapoor, G., and Rogers, R. Protection against reconstruction and its ap- plications in private federated learning. arXiv preprint arXiv: 1812.0044 2018
Hayes, J., Mahloujifar, S., and Balle, B. Bounding training data reconstruction in dp-sgd. arXiv preprint arXhv:2302.07225. 2023.
Bichsel, B., Gehr, T., Drachsler-Cohen D., Tsankov, P., and Vechev, M. Dp-finder: Finding differential privacy violations by sampling and optimization. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, pp. 508-524, 2018
Homer, N., Szelinger. S., Redman, M., Duggan, D., Tembe, W. Muchling J., Pearson, J. V.. Stephan, D. A., Nelson, S. F., and Craig, D. W. Resolving individuals contributing trace amounts of dna to highly complex mixtures using high-density snp genotyping microarrays. PLoS genetics, 2008
Bichsel, B., Steffen, S., Bogunovic, I., and Vechev, M. Dp- sniper: Black-box discovery of differential privacy vio- lations using classifiers. In 202/ IEEE Symposium Security and Privacy (SP), pp. 391 499.409.10 IEEE, 2021.
Hu, H., Salcie, Z., Sun, L., Dobbie, G., Yu, S., and Zhang, X. Membership inference attacks on machine learning: A survey. ACM Computing Surveys (CSUR), 54(1 (1)):111177 2022.
Carlini, N., Chien, S., Nasr, M., Song, S., Terzis, A., and Tramer, Membership inference attacks from first prin-
10

---

Auditing /-Differential Privacy in One Run
Hyland, S. L. and Tople, S. On the intrinsic privacy of stochastic gradient descent. Preprint https://arxiv. org/pd//1912.02919, pdf. 2019.
In Proceedings of the 2018 ACM SIGSAC conference on computer and communications security, pp. 634-646-6 2018.
Jagielski, M., Ullman, J., and Oprea, A. Auditing differ- entially private machine learning: How private private sgd? Advances in Neural Information Processing Sys- tems, 33:22205-22216 2020.
Nasr, M., Songi. S., Thakurta, A., Papernot, N., and Carlin, N. Adversary instantiation: Lower bounds for differen- tially private machine learning. In 202/ IEEE Symposium security and privacy (SP). pp. 866-882. IEEE, 2021.
Jia, J., Salem, A., Backes, M., Zhang, Y., and Gong, N. 7.. Memguard: Defending against black-box membership in- ference attacks via adversarial examples. In Proceedings of the 2019 ACM SIGSAC conference computer and communications security, pp. 259-2744 2019.
Nasr, M., Hayes, J., Steinke, T., Balle, B., Tramèr, F., Jagiel- ski, M., Carlini, N., and Terzis, A. Tight auditing of differentially private machine learning. arXiv preprint arXiv:2302.07956, 2023.
Pillutla, K., Andrew, G., Kairouz, P., McMahan, H. B., Oprea, A., and Oh, S. Unleashing the power of random- ization in auditing differentially private ml. Advances in Neural Information Processing Systems, 2024.
Kaissis, G., Hayes, J., Ziller, A., and Rueckert, D. Bound- ing data reconstruction attacks with the hypothesis test- ing interpretation of differential privacy. arXiv preprint arXiv:2307.03392, 2023.
Sablayrolles, A., Douze, M., Schmid, C., Ollivier, Y., and Jégou, H. White-box vs black-box: Bayes optimal strate- gies for membership inference. In International Con- ference Machine Learning, pp. 5558-5567 PMLR, 2019.
Kaissis, G., Ziller, A., Kolek, S., Riess, A., and Rueckert, D. Optimal privacy guarantees for relaxed threat model: Addressing sub-optimal adversaries in differentially pri- vate machine learning. Advances in Neural Information Processing Systems, 36, 2024.
Sander, T., Stock, P., and Sablayrolles, A. Tan without a burn: Scaling laws of dp-sgd. In International Conference on Machine Learning. PMLR, 2023.
Leino, K. and Fredrikson, M. Stolen memories: Leveraging model memorization for calibrated "WhiteBoxx mem- bership inference. In 29th USENIX security symposium (USENIX Security 20), pp. 1605-1622, 2020.
Shokri, R., Stronati, M., Song, C., and Shmatikov, V. Mem- bership inference attacks against machine learning mod- els. In 2017 IEEE symposium on security and privacy (SP), pp. 3-18. IEEE, 2017.
Li, J., Li, N.,, and Ribeiro, {MIST):
Defending against membership inference attacks through {Membership- Invariant subspace training. In 33rd USENIX Security Symposium (USENIX Security 24), pp. 2387-2404 2024.
Steinke, T. Nasr, M., and Jagielski, M. Privacy au- diting with one (I) training run. arXiv preprint arXiv:2305. 08846, 2023.
Lu, F., Munoz, J.. Fuchs, M., LeBlond, T., Zaresky- Williams, E., Raff, E., Ferraro, F., and Testa, B. A gen- eral framework for auditing differentially private machine learning. Advances in Neural Information Processing Sys- tems, 15:4115-4477,, 2022.
Steinke, T., Nasr, M., Ganesh, A., Balle, B., Choquette- Choo, C. A., Jagielski, M., Hayes, J., Thakurta, A. G., Smith, A., and Terzis, A. The last iterate advantage: Em- pirical auditing and principled heuristic analysis of dif- ferentially private sgd. arXiv preprint arX1v:2410.06186. 2024a.
Mahloujifar, S., Sablayrolles, A., Cormode, G., and Jha, S. Optimal membership inference bounds for adaptive composition of sampled gaussian mechanisms. arXiv preprint arXiv:2204.06100 2022.
Steinke, T., Nasr, M., and Jagielski, M. Privacy auditing with one (1) training run. Advances in Neural Information Processing Systems, 36, 2024b.
Matthew, J., Milad, N., Christopher, C.-C., Katherine, L., and Nicholas, C. Students parrot their teachers: Mem- bership inference on model distillation. arXiv preprint arXiv: 2303.03446. 2023.
Stock, P., Shilov, I., Mironov, I., and Sablayrolles, A. De- fending against reconstruction attacks with r\ 'enyi differ- ential privacy. arXiv preprint
20l::2222.0622 2022.
Mironov, I. Rényi differential privacy. In 2017 IEEE 30th computer security foundations securityfoundation symposium (CSF), pp. 263- 275. IEEE, 2017.
Tang, X., Mahloujifar, S., Song, I.., Shejwalkar, V., Nasr, M., Houmansadr, A., and Mittal, P. Mitigating member- ship inference attacks by {Self-Distillation) through a novel ensemble architecture. In 31st USENIX Security Symposium (USENIX Security 22), pp. 1433-1450, 2022.
Nasr, M., Shokri, R., and Houmansadr, A. Machine learning with membership privacy using adversarial regularization.

---

Auditing /-Differential Privacy in One Run
Tramer, F., Terzis, A., Steinke, T., Song, S., Jagielski, M., and Carlini, N. Debugging differential privacy: A case study for privacy auditing. arXiv preprint arXiv:2202.12211 2022.
Wang, J. T., Mahloujifar, S., Wu, T., Jia, R., and Mittal, P. A randomized approach for tight privacy accounting. arXiv preprint arXiv:2304.07927 2023.
Watson, I.., Guo, C.,, Cormode, G., and Sablayrolles, A. On the importance of difficulty calibration member- ship inference attacks. arXiv preprint arXiv:2111.08440 2021.
Ye, and Shokri, R. Differentially private learning needs hidden state (or much faster convergence). Advances in Neural Information Processing Systems, 35:703-715, 2022.
Ye, J., Maddi, A., Murakonda, K., Bindschaedler, V., and Shokri, R. Enhanced membership inference attacks against machine learning models. Proceedings of the 2022 ACM SIGSAC Conference Computer and Com- munications Security, pp- 3093-3106, 2022.
Zagoruyko, S. and Komodakis, N. Wide residual networks. arXiv preprint arXiv:1605.07146 2016.
Zarifzadeh, S., Liu, P. C.-J. M., and Shokri, R. Low-cost high-power membership inference by boosting relativity. 2023.
Zhu, Y., Dong, J., and Wang, Y.-X. Optimal accounting of differential privacy via characteristic function. In Interna- tional Conference on Artificial Intelligence and Statistics, pp. 4782 4817. PMLR, 2022.
12

---

Auditing /-Differential Privacy in One Run
A. Proofs
A.I. Proof outline for Theorem 3.1
In this subsection, we outline the main ingredients we need to prove our Theorem 3.1. We also provide a warm up proof for simplified version of Theorem 3.1 without abstentions and then we focus on the proof of the main theorem. First, we have Lemma that bounds the probability of any event conditioned on correctly guessing single canary.
Lemma A.1. Let M [k| - θ be mechanism that satisfies f-DP. Also let A: θ - ([k] U {+))" be a guessing attack. Let u be a random variable uniformly distributed over [Kim and let = (MM( Then for any subset E C O we have
fh' Pr [ [M(u)= E
F = Pr [M(u) E E and in = m] S S Pr [M()) EF])
where
= sup)a;
- a f( k - )
= and (B (1 1
This Lemma which is a generalization and an improvement over the main Theorem of (Hayes et al., 2023), shows that the probability an event cannot change too much we condition on the success of adversary on one of the canaries. Note that this Lemma immediately implies a bound on the expected number of correct guesses by any guessing adversary (by just using linearity of expectation). However, here are not interested in expectations. Rather, need to derive tail bounds. The proof of Theorem 3.1 relies on some key properties of the f' and f" functions defined in the statement of Lemma A.I. These properties are specified in the following Proposition and proved in the Appendix.
Proposition A.2. The functions S' as defined in Lemma A. is increasing and concave. The function f& as defined in Lemma 1 is increasing and convex.
Now, we are ready to outline the proof of simplified variant of our Theorem 3.1 for adversaries that make guess on all canaries. This makes the proof much simpler and enables us to focus more on the key steps in the proof.
Theorem A.3 (Special case of 3.1). Let M [k|" θ be a f-DP mechanism. Let be a random variable uniformly distributed on [k:].. Let A: O [ be a guessing adversary and let v A(M())). Define pi Pr {(je((m) I(u
vz)) :]
For all subset of indices T S [m], we have
Σ E
m +
S
Pi-1)
Proof. Let us define a random variable t = (ti,..., tm) which is defined as t; I(u; =v;) We have
Pa Pr
c
Pr
t 1 and t2 1] + Pr
and t 0]
1=1
2=2
T Now by Lemma A.I we have Pr 2 4; c- and t 1] fk 2 t c- 1). This is nice invariant that we can
use but E t. c- - 1 could be really small depending on how large m is. To strengthen the bound we sum all pe 's for e E T, and then apply the lemma on the aggregate. That is
ΣP,-
=
V Pr
=
Σ
Pr
t = and t1 = 0 + Σ Pr
t = and t₁ = 1]
JET
JET
1=1
JET
JET
1=2
Pr
t T and = 0) + Pr[1 +
Σ t T and t=2
1]
2=2
Now we only use the inequality from Lemma A. for the second quantity above. Using the inequality for both probabilities not ideal because they cannot be tight at the same time. So we have,
Σ
Pj <
Σ E T and t 0] [Ar
Σ t, E TT).
JET
1=2
13

---

Auditing /-Differential Privacy in One Run
Now trick make this cleaner. We use the fact that this inequality is invariant the order of indices. So can permute t; ts and the inequality still holds. We have,
Σp3 jET
Pj
S
E mm
Pr
(1) E T and En(1) 0]]
E x~illim]
[M] +
Σ
T))
2=2 m
i=2
E mmI
Pr
7() T and tx(1) = +]] f/(
Pr[[
+ Σ
#(1 T]]).
a~Ilm
Now we perform double counting argument. Note that when we permute the order Ei= ba(() = j and (1) 0 counts each instance .,...., fm with exactly j non-zero locations, for exactly (m - j) x (m 1)! times. Therefore, we have
Pr [mm
E
t m())
E T and (()) = 0] = Σ
Pj. jET
m - j
1=2
With a similar argument we have,
E [~[mm
Pr(1 + Σ
m
xx)) E
Σ
m
m-j+1
P--1
+ Pj
j
m
m
1=2
JET
Then, have
Σ
Pj S Σ
m j
Pj
+
f/
Σ
Pj +
m j
Pj 1j-1).
JET
jET
JET
And this implies
Σ
Σ
j
PJ
S f1
Σ
Pj
+1
Pj P--
SET
m
jET
m
m
And this, by definition J implies
Σ jET
i
f(
1
Σ
m
j
P 11-1).
k k-
m
jET
A.2. Proof of Main Lemmas and Theorems
Proof of Lemma A.I. Let Pu) E and #1 v1 and q Pr[M(n) E E.. We have
14

---

Auditing /-Differential Privacy in One Run
(u) E E and u1 =1 i]
(E(K]
Σ Pr[M(u) E and 01 = un =
Σ
E Pr(M(() E E and 0n = - ún =()
h:
k
KE|
(By definition of (-DP)
h Σ
Σ (-M(Pr(M(u) and 2z = us -])
iE|ki
(E(M)((S)
(By convexity of f)
< 11-f
Σ Pr[M(() E and = -l 11 -1)
k
iE[k)
jENAMM
=1- /
Σ
Σ
1 Pr[M(u) E E and 0 = i -1)
k
iE[R]
JE(A)())
=1- f
Σ
Σ Pr[M(u) E E and 01 = i and 21 = i1)
KE[K]
1
1 f(
(u) e and u1 + v1)
1 - f( 1 P
k-1
Similarly we have.
p
Pr[M(() E E and = 01 =
Σ
Pr[M(() E and U1 = U1 =]]
h
SE(R
Σ
Σ Pr(M(u)= Fand vs =i 11 1))
h
ER(
jE(A
(By definition of f-DP)
1
Σ
1
Σ
(11 Pr(M(u) E E and 2 il un = .1)
k
JEA
(By convexity of f)
Σ
Σ Pr[M(u) E E and 01 = = =11)
h
k-
iE|k
jE(A)((
h: 1
Σ
(1 Pr[M() e E and 01 11 = =1))
SE
JE(A]\(()
Σ
Σ Pr(M(u) E and i1 i and 41 =1))
h:
KE[R]
(1 (r( e E and in + vil))
1
9 +P
1
15

---

Auditing /-Differential Privacy in One Run
This implies that,
f(p) (k - - -
Proof of Proposition A.2. The function is increasing simply because f is decreasing, We now prove concavity. Let an = (x1) and 02 = =x(2)) By definition of fk we have
-1-
31 01
O1 + f(
1
k -
and
+
f( --1
02
1
Averaging these two get,
01 + 02
f( + ((12
S
2
2
By convexity of f we have
01 + 02
21
01402
+
S1
2
h:
Therefore, by definition of f/. we have f/( =2)
2
01002
Similarly, f in increasing just because f is decreasing. And
assuming 01 = (21) and a2 = (x2) we have
I1 +
12
01 +
fk
2
2
which implies JK is convex.
Proof of Theorem 3.1. Instead of working with an adversary with c' guesses, we assume we have an adversary that makes a guess on all m inputs, however, it also submits a vector q E {0, 1]mm, with exactly Is and m c' Os. the output of this adversary vector [k]" and vector q {0, 13"h. Then, only correct guesses that are locations that is non-zero counted. That if we define random variable (ti,..., tm) as I(u; vj) then have
m
Pe Pr
t; qi =d c]
m
Pr
t; 1 and and qı 1] + Pr
t; and qi = 0]
2m2
2m2
Now by Lemma A. we have
Pr
= and t and qı = 1] < f
t: = = and qı = -1).
2=2
1=2
This is a nice invariant that we can use but Dm t = could be really small depending on how large m is. To strengthen the bound we sum all pe 's for e E T, and then apply the lemma on the aggregate. That
ΣΦ =
Σ
t; = 5l
JET
JET
1=1
Σ>
Pr
t j and
qi =
Σ Pr
=j and t and qı =
JET
1=2
JET
2=2
Pr
T and qi 0] Pr|1 Σ
t, T and t and q1
16

---

Auditing /-Differential Privacy in One Run
Now we only the inequality from Lemma A.I I for the second quantity above. Using the inequality for both probabilities not ideal because they cannot be tight at the same time. So have,
m
E T and t qı 0] (. JET
Σ t, T and q1 1]).
Now we use trick to make this cleaner. We use the fact that this inequality is invariant to the order of indices. So we can permute t; is and the inequality still holds. We have,
ΣpS jeT
Ps
S
E xmll(m
Pr
7(() E T and tx(1) 97(1) = =0] +
E [[[PP[]+ +
Σ =()) E T])]
2=
1=2
E [
Pr
t ((t) T and (=(1) 0]] + f [=]]m]]
E
Pr[1
+
x()
T and 9m(1) 1]]).
2=2
Now we perform a double counting argument. Note that when we permute the order Σ 7()) = j and (1) counts each instance ,j...., fm with exactly j non-zero locations, for exactly (m - j) x (m 1)! times. Therefore, we have
m Pj. 0]] = Σ
Pr [
E
700
9=(1) E T and ((1) 9m(i)
jET
With a similar argument we have,
m
c'
d
E x~1][|]
Pr[1
x0))
Am()) E T and ax(1)
1]] 1|]= = Σ
Dj
+ Pj.
m
m
i=
JET
Then, have
d' d-j+1
Pj S Σ
Pj
+x())
1 jET
Pj +
Pj-1)
m
m
m
JET
JET
m
j
Pj
+
fk!
j
Pj
+
C --j+
Pj 11-1).
JET
JET
And this implies
Σ
i
Pj S
M
P Pj +
j
è' - -j+h +
Pj Pÿ-1).
m
JET
nET
And this, by definition of S implies
d
Σ
S
Σ
Dj Dÿ-1). 1).
m
k-1
m
JET
JET
Proof of Theorem 3.2. To prove Theorem 3.2, first state and prove lemma which consequence of Theorem 3.1. Lemma A.4. For all S c' [m] let define
c' i B.
ae
Ps
and
pj
m
m
i=
We also define a family of functions r = {rij : [0,1] x [0, 1] + [0, 1]]sse[m) and h = {ha.s : [0, 1] + [0, 1]} that are defined recursively as follows.
17

---

Auditing /-Differential Privacy in One Run
Vi [m] 3,,(a, 33 = a and ()) and all i < we have
14. 3) = (lc (6--1)5 1-1)--1 (1411((e
Tis B) = r1t1 (), - d (a, 3) (ha h1t1,(a, 8))
Then for all i S J we have
a; 2 31)( and Bg 2 hag
Moreover, for i < j. Ta.j and h are increasing with respect to their first argument and decreasing with respect to their second argument.
Proof of Lemma A.4. We prove this by induction on j j- i. For j i = 0, the statement is trivially correct. We have
he.s(a,, B;) =(k: - 11-11)----a- (ran)((s,,8)).
By induction hypothesis, we have (1 3g) I 0++1- Therefore have
h4 By) S (k- (as+)).
(I)
Now by invoking Theorem 3.1, we have
a#+1 S f( B k - 1
Now since f is increasing, this implies
(k: Now putting, inequalities and 2 together we have (aj, (5) S Br This proves the first part of the induction hypothesis for the function h. Also note that hi, is increasing in its first component and decreasing in the second component by invoking induction hypothesis and the fact that f-1 is increasing. Now we focus on function rty. First note that there an =-1 We have.
B.
(2)
alternative form for ri,j by opening up the recursive relation. Let c= d=241
j-1
j-1
=
B) c-i 1=,,,,
c d-i+1 13,l,,)),
Σ 72, 3)
2=1+1
- has 3) ha, Σ rehe B)
= =ryb(a, B)
c' - (a, 3) c d-j
(a, Σ (a 3).
(3)
s=i+1
Now we show that for all we have
m
ai c' -
8
(4)
#=
This is because we have
i(c - 2)
05
3, Σ
}p=-
c' - #=141
m (d' - i)m
18

---

Auditing /-Differential Privacy in One Run
On the other hand we have
m
C
7x
m
2=1+1
z/=it1
m
c'
ps
2
d
m
m
i(d 2)
P=
m
(c' m
and this shows that Equation 4 is correct. Therefore for all i < j
we have
i
j
aj C¹
31
3 +
Y2P
C¹
2mi+1
Now, using the induction hypothesis for h we have,
04 2 aj c Mal B,) mala,, c' J-
Σ (
(5)
d-
2=1+1
Now verify that the right hand side of Equation 5 is equal to ri.j (ay, 33)) by the formulation of Equation 3
Also, using the induction hypothesis, we can observe that the right hand side of 3 is increasing in aj and decreasing in 3 because all terms there are increasing in ay and decreasing in By.
This lemma enables us prove that algorithm 3 is deciding valid upper bound on the probability correctly guessing examples out of c' guesses. To prove this, assume that the probability of such event is equal to r', Note that this means Oe + Be <' Also note that
(6)
Be
therefore, we have
C 0g
(7)
m
and B. < <'=ey'. Therefore, using Lemma A.1 we have ag 2 To,el G d=c7') and 30 2 ( (( m
m
m
Now we prove lemma about the function (T. = has C <=sT) + rigl d=sT).
<==T) is increasing in T for i < j S. Lemma A.5. the function $ic (T) = -hi. ( T, E'=ET) + Tii ( m
Proof. To prove this, we show that for all i < I both re ( <=-r) and his TT, d d=cT) are increasing in We prove this by induction on j - i. For j - = 1, we have
C _T T,
d - (I: -k-11)
ha
m m
d=r7) is increasing in as well. For ri,41 we have We know that f-1 is increasing, therefore 1i,44 ( (, m
T1,411 [T, - 7) c (h4 C_ c' C'-CT) c' --0
m
So we have
19

---

Auditing /-Differential Privacy in One Run
C d c cec - 1) - iic- -c) m(d' -i)
d m1.t11 c d-c
(-T, 11,441(
=T,
m
(c i)d T + d' d'
C d h4,t11
TT,
T).
mlc' -i
m
We already proved that 1 nT, T, <'=eT) is increasing in r. We also have (c-i)e m(c'-1t
> 0, since i < c. Therefore
Ti,+1 - c C-Cr) m m
increasing in т. So the base of induction is proved. Now we focus on j -jii > 1. For his we have
C c'-c 116-1) _T, d-c
higl LT,,
By the induction hypothesis, we know that 1s41. ( TT, <==eT) is increasing in and we know that f-1 is increasing, therefore, he.r( ( T, <==7) is increasing in 7. For Fzyj. note that rewrite it as follows
m
j-1 hes 3)
rt,(a, =
j
B
Σ
Ae
c' j
2=1
where 2₂
(
2 O. Therefore, have
To.l T,
C c' - r) T( c (c' - [c)}
m(c - () )+ + Σ X2 hzn (
j-1
7) C c' cC-c7)
c
c
z=i
d(c - 5)
j-1
Σ X
has
m(c j)
m
m
Now we can verify that all terms in this equation are increasing in т, following the induction hypothesis and the fact that Ag > 0 and also < c.
Now using this Lemma, we finish the proof. Note that we have as + Bo m
So assuming that 7' 2 then we have
c' ag + 3o 2 s0,((7') So.c(T).
m
The last step of algorithm checks if 80.e E and it concludes that 7' S that's the case, because 8p.a is increasing T. This means that the probability of having more than guesses cannot be more than T.
B. Ablation Experiments
Reconstruction attacks: To show the effect of the bucket size (k) on the auditing performance, in Figure 5, we change the number of examples in the two different setups. first setup we use 10,000 canaries and change the bucket size from 50 to 5000. In the other setup we only use 100 canaries and change the bucket-size from 3 to 50. Note that in these experiments, we do not use abstention and only consider adversaries that guess all examples.
20

---

Auditing /-Differential Privacy in One Run
8-
8.0
7-
7.5
Epsilon
Empirical lower bound privacy different bucket sizes Theoretical
Epsilon
6.5
4-
6.0
3-
Empirical lower bound privacy with different bucket sizes
2-
Theoretical
1000
2000
3000
4000
5000
10
20
30
40
50
Number of examples in each reconstruction bucket
Number of examples in each reconstruction bucket
Figure 5. Effect of bucket size on the empirical lower bounds for reconstruction attack (Gaussian mechanism with standard deviation 0.6), Left: 10,000 canaries with bucket size up-to 5000. Right: 100 canaries with bucket-size up-to 50, Empirical is reported 10 10-3
Effect of number of guesses In Figures 6-9, we compare the theoretical upper bound, our lower bound, and the lower bound Steinke et al. with varying number of guesses. total, we have m = 10 canaries. The number of correct guesses determined using Algorithm 4 (the idealized setting). Then we use our and (Steinke et al.. 2023)'s auditing with the resulting numbers and report the empirical 6. As best auditing performance for small number of guesses. This shows the importance of abstention in auditing.
see, both our and Steinke al.'s auditing procedure achieve the
A curious reader might wonder why the number of guesses has such a big impact on empirical privacy. Essentially, our analysis involves estimating how many correct guesses an adversary can make when given a certain number of attempts. We focus on specific percentiles of these distributions. The accuracy of our empirical privacy estimates can vary significantly based on how much the number correct guesses fluctuates, which influenced by how many guesses we allow adversary make. To explain further, consider random variable representing the ratio of correct guesses (c) total guesses (c'). If we reduce the number of guesses, the variance of this ratio tends to decrease because the ratio approaches I (the adversary make more correct guesses when decrease c'). Conversely, if we increase the number of guesses, the variance can also decrease because having more guesses generally leads to more stable average, owing to the law of large numbers. This balance makes the number of guesses crucial factor in optimizing for the best estimate of empirical privacy.
Varying and confidence levels: We also examine the effect of 6 on the obtained empirical 6. We fix the number of canaries to 10" and the number of guesses to 1, 5,5 and the number of correct guesses are set to 1, 429, suggested by the idealized setting. We use a Gaussian mechanism with standard deviation 1.0, we vary the value of 8 and the confidence level to observe how they affect the results. Figures 10 and 11 shows the bound (Steinke al., 2023) and our bound, respectively. Note that our lower bounds represent the true behavior of 5 independent of the confidence level, in contrast the bound of (Steinke et al., 2023).
C. Other datasets
We also report in Figure 12 our privacy analysis method in the black-box attack setting on the tabular dataset shopping records Purchase (Shokri et al., 2017). We replicate the same setup in (Zarifzadeh al., 2023), on a non-private MLP model trained on 25000 samples for 50 epochs. We outperform Steinke al. method for all numbers of guesses
21

---

Auditing /-Differential Privacy in One Run
2.9
Heeeet
Orgasale 5S@)
Theret ca orpacate (O0)
Orrpncale (um)
0.0
Smpaizzt 10ust
puesssss lout cananes)
1.
Figure 7. Effect of number of guesses (Gaussian mechanism with standard deviation 2.0). Empirical e is reported at 10-3.
Figure 6. Effect of number of guesses (Gaussian mechanism with standard deviation 1.0). Empirical is reported at 10-3.
sical briik c1MB
Empincal (SN)
Emplnoal
Empir c10un)
Nurbbr GUIDSES tout 3.0E-03 cancree)
Number of quesses oout of 1.00+27 canaries)
Figure 8. Effect of number of guesses (Gaussian mechanism with
Figure Effect of number of guesses (Gaussian mechanism with standard deviation 0.5). Empirical is reported at = 10-5.
standard deviation 4.0). Empirical is reported at d = 10-5.
D. Experimental details
Idealized setting: In the idealized setting, work with toy version of the mechanism to calculate the expected number of correct guesses for the ideal adversary. For Gaussian mechanism, the ideal setting for an adversary when we have a Gaussian mechanism that used to calculate the sum of vectors. In this setting, each canary represents unit vector that orthogonal all other canary vectors. Then, given the noisy sum, the adversary will calculate the likelihood of the canary being used in the sum, and then decides on the guesses based these likelihoods. For the setting that the adversary has more than 2 guesses (A: > 2), we use a slightly different idealized setting. In all settings, we run the attack 100 times and average the result to get the expected number of correct guesses. Algorithm shows how we calculate the number of correct guesses in the idealized setting.
Purchase Black box RMIA
This paper
Steinke
Empirical epsiion
2-
5000
10000
15000
20000
25000
Number of guesses (out of 25000 examples)
Figure 12. Comparison with auditing procedure of (Steinke et al..
2023) on non-private model trained on Purchase against black-box RMIA method (Zarifzadeh et al., 2023). Empirical is reported at 10 -
22

---

Auditing /-Differential Privacy in One Run
Bound (Gaussian mechanism)
Lower Bound 99.0% confidence)
5-
Lower Bound (95. 0% confidence)
confidence)
1-
Upper Bound (Gaussian mechanism)
Bound confidence)
Lower Bound 95.0% confidence)
0-
Lower Bound (75.0% confidence)
10
10
10
10
100
10
10
10
10
10
10
10
10
Figure 11. Idealized setting different values â confi- dence levels for our bounds.
Figure 10. Idealized setting for different values of 6 and confi- dence levels for bounds of (Steinke et al., 2023).
23

---

Auditing /-Differential Privacy in One Run
Algorithm Simulate the Number of Correct Guesses
import numpy np
from scipy. special import softmax
from sumpy.randor import normal, binomial
def iddeliiee_seetiine (target_noise, r_guesses, n_canaries, k): n_correct_vec []
if k==2:
for range (100):
s_vector = binomial al (1, 0.5, size=n_camaries)
noise = normal (0, 2xtarget_noise, n_canaries)
noisy_s s - s_vector + noise
norted_noisy.. np. sort (noisy_s)
threshold_c sorted_ sorted_ (n (1_quesses)//2-11
n_correct = np. cp..eilllleeeecc..mccmm...c....e (n_guesses (s_vector [noisy_s > threshold_c] =
1) m)me()))
n_correct_vede append (n_correct)
else:
for in range (100):
s_recon_ves vec np random. randint (0, k, n_canaries)
s g_vec_recn_ohe ree np. ep.eye (k) [s_recon_vec]
s_recon_noisy_ sec_ohheeeeeeeeeeeeeee = s_vec_recn_ohe + normal (0,
+ np.sqrt (2) httattttttnnssstteeee
s _eec_recn_ohheeeeeeeee_oeee_e_ee shape)
idx np. argmax wpw.argaa.t.rreeoooooooa oe axis=1)
buckets softmax ott.annk....ooouuppe..e..eootttp
axis=1) (sp oeg_aanngges__ccooooooooeeee_ee shapeeee@eesee@@
shape(0]),
sorted_buckets np. no.sort (bucketts
bucket_e_thr worted_buckest (-int (n guesses)]
n_correct_rec cp.ceil(
n_guesses* (bacoon bucket_c_thr,
__tecon_roiss__ve__ohell l [buckets >
bucket_c_thr] argmax
argmax (1)) (m))n ()
n_correct_vec apped (n_correct_rec)
return int (np array co__corrett_eeeeeeeeeeee vec) mean )0))
24

---

Auditing /-Differential Privacy in One Run
Auditing code
Here we include the code to compute empirical epsilon.
from scipy.stats stats import norm import numpy as np
Calculate and r recursively (no abstentions)
def rh (inverse blwp__llow__pp__________ee____ee up_ up__unction, alpha, beta, j, m, 2=2):
# Initialize lists to store h and r values
[0 for in range () 1)]
[0 for in range (j 1)]
# Set initial values for h and r
h[il beta
I[il alpha
# Iterate from j-1 to
for in range (j 1, -1, -1):
f Calculate h[i] using the maximum h[i+1] and scaled inverse
4 blow-up function
h[i] max (h[1 1], (k - 1) inverse heiverseeblowwaeeeeee up
aalow_u__uunctiieneeeeeeeeeeoeee function (r[i 111)
# Update r[i] based on the difference between h[i] and h[i+1]
r[i] - rli + 1] (i / (m - i)) [h[i] - hli 11)
# Return the lists of and r values return (r, h)
Audit function without abstention def audit modit_rh(iiverse htt_iverseeblwwweeeeeeee Sww_pp__ee up__funtton, m, c, threshold-0.05, k=2)
# Calculate alpha and beta values alpha threshold
m beta = threshold (m c) / m
# Call the rh function to get the lists of h and r values r, rh blwperrse_bbow_u__ffuueee
alpha, beta, c, m, k)
Check if the differential privacy condition is satisfied
if r[0] h[0] 1.0:
return False
else:
return True
Calculate and r recursively (with abstentions)
def rh th_with. _ap (inverse wwwp_ll.wwppec_ppoele coo__up_functio,, alpha, beta, 3, m, c_c_p k=2):
h=[0 for i in range (j+1)]
r= [0 for i in range (i+1)]
h[i]= beta
r[i]= = alpha
for in range (1-1,-1,-1)
h[i]=max (i+i),, (k-1) winverse_bloowuupffucc (r[i+1)))
r[i]= r[i+1] (i/ (c/(c_cpp-))) (h[i] h(i+1])
return (r,h)
Audit function with abstentions def modit_rh_with_ce k=2): chreshold@thrrehholdkc...pp/
functioon, m, c, c,c_cap, threshold=0.05 05,
25

---

Auditing /-Differential Privacy in One Run
alpha= (tpphestthrreeholdcc/ccaaaa
beta=threshhold (c_cap-c) p_ccappcc/c_caa /c_cap
r, h.b-rh_with_cag www.aaaeeaeeeeeee...o.u...uuppep funnctiinn, alpha, beta, c, m, c_cap, k)
if [[0]+h[0]><_cap)
return False
else: return True
Calculate the blow-up function for Gaussian noise def bhasstaanD_bbloo_u__fnoo
(noise):
def fto__up_functionla (x)
# Calculate the threshold value threshold norm.ppf (x)
# Calculate the biown-up threshold value Bloon_up_threshene
threshold
noise
# Return the CDF of the blown-up threshold value return norm. cdf (blown_up_thresholl return bluntip_
Calculate the inverse blow-up function for Gaussian noise def
(noise)
def olow.pp.itverr__fuuttiookkk (x)
# Calculate the threshold value threshold = norm. (x)
# Calculate the biown-up threshold value blown_up_thresholl # Return the CDF of the blown-up up threshold value return norm. cdf return blow_up inwerse_funeteee
threshold
noise
Define function to calculate delta for Gaussian noise def salculate_delte htl_deelaggsgssaaaaae (noise, epsilon):
# Calculate delta using the formula
delta norm. (-epsilon * noise / (2 * noise)) ep.eep *
+ norm. ( (-epsilon noise return delta
(2 noise))
Define function to calculate epsilon for Gaussian noise def ca lalaateeeslln_gattteeeee
(noise, delta): # Set initial bounds for epsilon
epsilon_upper = 100
epsilon_lower =
Perform binary search find epsilon
while epsilon_upper epsilor_lower 0.001:
epsilon_miie middle (epsilon_uppe) epsilon_lower) / 2
if diullate_delt__aassian (ncise,,, epsilon_middle) > delta: lower epsilon_middle
else:
epsilon_ _pppr_ppprr__pp epsilon_middle Return the upper bound of epsilon return epsilon_upper
Get the empirical epsilon value
26

---

Auditing /-Differrentil Privacy in One Run
def jet_geussian_emm_ess_oooo (cardidate_noises,
inverseebloo.uppffuniiioo m
e, threshold, delta, k=2):
# Initialize the empirical privacy index
ampirical__prvvae__ndee = 0
# Tterate through candidate noises until the privacy condition fails
while audit_rh hoad::inttiaresspooooou.uuoooooo org.apas.......aa.oo.oooooaoaaar
m, C,
threshold=0.05, 05, k=k):
empiricall_ptivacy_nnee.
# Get the empirical noise and calculate the empirical epsilon
empirical_noise = candidate_noises (enggriiaa_prrvvvc__nneedd laspssssslonssssaaaeeeee # Return the empirical epsilon
empirical_epe =
delta=delta)
return empirical_eps
Set target noise and generate candidate noises target_noise 0.6
cendidtte_poossssttarrgttnosss 1+0.01 for i in range (1000)
Liverreeblloouup_uucctio------- htt.://uuunuttttoeeeaeaaaaaaaaaa gaausssannDP.ooooouuuu..eeeeerr (noise) for noise in candidate_noises]
27


Reviews:
[{"review_id": "F1ub3ZkBxr", "reviewer": "Reviewer_cWiv", "summary": "The paper studies auditing of DP parameters $\\varepsilon$ and $\\delta$ using one training run. The goal is to find high-confidence lower bounds for the DP parameters via membership inference guessing game, similarly to the baseline method by [Steinke et al., 2023](https://proceedings.neurips.cc/paper_files/paper/2023/file/9a6f6e0d6781d1cb8689192408946d73-Paper-Conference.pdf). In this guessing game randomly selected \"auditing samples\" are included from a given \"auditing set\" to the actual training set, and then the goal is to try to correctly guess which ones of the auditing samples were included and which ones were not. Based on the number of correc guesses, lower bounds for the DP parameters can be obtained. In the baseline method by [Steinke et al., 2023](https://proceedings.neurips.cc/paper_files/paper/2023/file/9a6f6e0d6781d1cb8689192408946d73-Paper-Conference.pdf), point-wise ($\\varepsilon,\\delta$)-lower bounds are given. Here the novelty is to obtain $f$-DP lower bounds, i.e., to determine a $f$-DP curve which would be an upper bounding trade-off curve.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes, the experiments clearly show that the $f$-DP based approach leads to higher ($\\varepsilon,\\delta$)-DP lower bounds than point-wise estimates by [Steinke et al., 2023](https://proceedings.neurips.cc/paper_files/paper/2023/file/9a6f6e0d6781d1cb8689192408946d73-Paper-Conference.pdf).", "methods_and_evaluation_criteria": "Yes, I think this selection of experiments well illustrate the benefits of this approach.", "theoretical_claims": "I did not read in details all the proofs in the appendix, but I read the main text and I was able to follow it and I think everything makes sense. I have no reason to believe there are errors that would change the conclusion.", "experimental_designs_or_analyses": "I read the description of the experiments, I think everything makes sense. I could not find what is the value of $\\delta$ used for Figure 1 to 4, but I assumed it is $10^{-5}$ as that is used to illustrate the theoretical upper bounds of the experiments behind Fig. 2 to 4.", "relation_to_broader_scientific_literature": "This paper is very closely related to the paper by [Steinke et al., 2023](https://proceedings.neurips.cc/paper_files/paper/2023/file/9a6f6e0d6781d1cb8689192408946d73-Paper-Conference.pdf). Even up to the point that I would think that there is not that great novelty compared to that paper. In a sense, this paper is taking the $f$-DP auditing proposed by [Nasr et al., 2023](https://www.usenix.org/system/files/usenixsecurity23-nasr.pdf) and combining it with the point-wise lower bounding technique by [Steinke et al., 2023](https://proceedings.neurips.cc/paper_files/paper/2023/file/9a6f6e0d6781d1cb8689192408946d73-Paper-Conference.pdf).", "essential_references_not_discussed": "I cannot think of such references.", "other_strengths_and_weaknesses": "- The general idea of combining the guessing game approach by Steinke et al. and $f$-DP accounting proposed by Nasr et al. (2023) is nice and clearly improves upon the baseline method by Steinke et al. \n\nWeaknesses:\n\n- One has to of course keep in mind that the improvement relies on the assumption that the underlying method actually has a trade-off curve that belongs to the family of trade-off curves that are used here for the auditing, that is the additional contribution here. E.g., if carry out GDP auditing, i.e., the family of trade-off curves is the trade-off curves of GDP mechanisms, then it is possible that one ends up to wrong conclusions about DP lower bounds in case the underlying mechanisms trade-off curve is far from a GDP trade-off curve.\n\n- The presentation could be improved a lot. It is very difficult to follow the text sometimes and there are also typos here and there. A lot is left unsaid, e.g., about GDP auditing. I could see the GDP auditing formulas gives only in the code of the appendix.\n\n- Due to the not so clear presentation, the connection to the baseline method by Steinke et al. remains a bit unclear. My impression is that this paper is kind of repeating the analysis by Steinke et al. using the $f$-DP formalism, so that we have $f$-DP lower bound directly at hand in the end. However, I believe one can get to similar conclusions by using the point-wise lower bounds given by the method of Steinke et al., then given a family of $f$-DP curves, find lowest $f$-DP curve that is below the trade-off functions determined by these point-wise estimates. When thinking about ($\\varepsilon,\\delta)$-bounds, e.g. in case of GDP auditing, one just finds the smallest $\\mu$-GDP parameter $\\mu$ for which the privacy $\\delta(\\varepsilon)$-curve is above all the point-wise lower bounds.\n\n- After all, this is also average case analysis like the auditing method by Steinke et al. I believe this corresponds to threshold membership auditing with the median score value or something close to that.", "other_comments_or_suggestions": "Consider a quick numerical experiment for directly combining GDP auditing and the method of Steinke et al. using the code given in their [Appendix](https://arxiv.org/pdf/2305.08846) :\n\nFirst, adjust the number of correct guesses so that $\\varepsilon$-values are similar as given in your Figure 2 for the baseline method. Then, using their code, compute the $\\varepsilon$-lower bounds using different values of $\\delta$ using the same $p$-value 0.05, and find the smallest $\\mu$-GDP parameter for which the GDP $\\delta(\\varepsilon)$-curve is above those lower bounds (the touch point is somewhere near $\\delta=10^{-3}$). Then, compute the $\\varepsilon$-lower bounds for $\\delta=10^{-5}$ using the GDP curve. The resulting difference to the original point-wise estimate seems to be very close to the difference that shows up in your Figure 2. This makes me think that the improvement comes only from using $f$-DP auditing, and that the analysis here is somehow very similar to that of Steinke et al. I.e., by combining their point-wise method and the $f$-DP accounting by Nasr et al. (2023), similar differences seem to be obtainable.\n\nIf it is the case, and there are such equivalences, I think that should be clearly written out and analyzed, and the actual contributions of the paper should be stated more clearly. \n\nSomehow my overall impression is that here is some interesting contribution, but it remains unclear what it exactly is as the paper is not yet that mature.", "questions_for_authors": "Considering the above small experiment indicating that it is possible to get similar $\\varepsilon$-lower bounds directly by combinign the method of Steinke et al. and GDP auditing, what is exactly the novelty here and what are the most important contributions? Somehow your $f$-DP based analysis looks much cleaner. However, in addition to possibly simplifying the analysis of Steinke et al., is there some clear benefit in using this approach (i.e., your Theorem 3.1 and Algorithm 3) ? You also mention there are improvements in the reconstruction attack result, compared to the result of Hayes et al (2023). But does that remain just as a theoretical contribution here?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "lLH7ZnGTLb", "reviewer": "Reviewer_BXCR", "summary": "This paper looks at auditing f-DP in one run (adding to prior works like auditing DP in one run by Steinke et al) as opposed to one $\\epsilon,\\delta$-pair, providing tighter privacy leakage bounds and characterizes the privacy bounds of approximate DP mechanisms like the Gaussian mechanism better when the failure probability $\\delta$ is non-zero. The authors do this via membership inference and a quasi-reconstruction based approach and provide theoretical results that attest to the soundness of their guarantees and discuss why they surpass their baselines in terms of closing the gap between empirically determined and theoretical values of $\\epsilon$.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes they are, especially with empirical guarantees that attest to why this provides a better audit than the baseline (Steinke et al, cited in the paper) along with a detailed discussion on why they do better when $\\delta>0$. The theoretical guarantees also provides grounds for soundness.", "methods_and_evaluation_criteria": "Yes they do. The attacks selected for the audit make sense and the datasets they test on are standard datasets used widely for such investigations.", "theoretical_claims": "The authors do provide proofs for their theoretical claims, but due to their length and time constraints, I was not able to go through them. For the time being, I'll take their correctness in good faith but might revisit them later and ask any questions I may have.", "experimental_designs_or_analyses": "I did. It is decent, the experiments include experiments on a standard dataset (CIFAR-10) and model (WideResNet16-4).\n\nHowever, the setup of their results in Sec 4.1 (Subsubsection on Simple Gaussian Mechanism) is not defined well and is vague and needs to be defined.\n\nIn addition, for experimental rigor and robustness of their results, it would be advisable to have more results than for just one dataset and one model. Intuitively, I think the findings should generalize but for empirical rigor and to ensure it, I need to see those results.", "relation_to_broader_scientific_literature": "This is a neat contribution and adds to literature on efficiently auditing models for DP guarantees, building upon the popular work by Steinke et al. This, by auditing f-DP instead of $(\\epsilon,\\delta)$-DP, provides a more general and tight privacy audit, and fills the gap in the literature for finding $f$ for $f$-DP based auditing for an ML model.\n\nSteinke, Thomas et al. “Privacy Auditing with One (1) Training Run.” ArXiv abs/2305.08846 (2023): n. pag.", "essential_references_not_discussed": "I think that the authors have done a wonderful job of listing all relevant references, including all baselines and state of the art attacks.", "other_strengths_and_weaknesses": "* Strength: The authors anticipate all the questions they would need to answer while justifying their approach and take a principled and exhaustive approach to justifying their novelty, the merits of their method over the baselines, and their design choices/procedures.\n* Weakness 1: The setup for the experiment on the Simple Gaussian Mechanism in Sec 4.1 is very vaguely described and it is not clear what is going on (Which model is being used? Is the data synthetic?). Even if this subsection uses the setup from another paper, which I assume it is, then the authors should describe it here (or at least in the appendix) nonetheless for self-containment and as a good practice.\n* Weakness 2: The authors define an auditing method based on reconstruction (or an approximation of it, so to speak) but never use it in their experiments or provide results on it, as it appears.", "other_comments_or_suggestions": "* It will be helpful if the authors spend a bit more time discussing their theorem statements in a high-level manner and explain to the reader what each aspect of it does. Otherwise, it's harder to understand, especially for newcomers or not-as-much theoretically-inclined readers.", "questions_for_authors": "* Pardon me if I missed it somewhere, but where do you describe the candidates for $f$, $h_i$ rigorously? I know you mention them being curves for the Gaussian mechanism but some explicit discussion on what they look like would be very helpful. I did not find it based on my reading of the text, and that seems like an important detail to have.\n* Can you please address Weakness 1?\n* I know that this is a theoretical work but it would be really nice to have results on more than one model-dataset pair (I see results only on WideResNet and CIFAR-10). It is good practice to see that empirical results generalize across settings. I think the empirical results are the key convincing factor about the improvement over the baseline.\n\nThis is a strong work but there are some issues and I need these to be clarified. If you answer these questions satisfactorily, I *will* raise my score to an accept, if not more.\n\n* Bonus question: Can you please explain why (as it seems) that you defined a reconstruction-based approach but never used it in your experiments? What differences in the quality of $\\epsilon$ estimation will it yield over the MIA-based approach? If you do not intend to add experimental results on the reconstruction-based approach (correct me if I'm wrong), then I find the inclusion of the discussion about reconstruction-based auditing redundant; surely in that case simply talking about MIA-based auditing is sufficient and I wouldn't count the reconstruction-based auditing approach as a merit/full contribution. Please clarify.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1VODtDEcOZ", "reviewer": "Reviewer_xS1M", "summary": "This paper presents an accurate and efficient auditing procedure to assess the privacy level of mechanisms within the framework of $f$-DP. The authors utilize a more generalized and refined privacy notion, $f$-DP, and effectively solve the guessing game, a generalized framework for reconstruction and membership inference attacks. The theoretical derivations are sound and well-presented, and the experimental evaluations are well-designed and convincing.", "questions": "", "limitations": "", "rating": 5, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "The proposed methods are well-motivated and empirically validated.", "theoretical_claims": "Yes. Please refer to Question and Comments sections below.", "experimental_designs_or_analyses": "Given that this is a theoretical paper, a set of not so extensive experiments in \"idealized\" setting is convincing enough to me to illustrate the performance.", "relation_to_broader_scientific_literature": "This is a novel contribution, providing an accurate and efficient auditing procedure for privacy assessment within the $f$-DP framework. It also generalizes and refines results in the literature. Also, to my best of knowledge, it is the first work on one shot $f$-DP auditing,", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strengths:\n1. The proposed method is efficient, accurate, and theoretically elegant.\n2. To the best of my knowledge, this is the first work on one-shot $f$-DP auditing.\n3. The method generalizes/refines results in the literature and demonstrates strong empirical performance.\n\nWeaknesses: while Theorem 3.1 is an iterative-type result, which I don't quite like usually, I find its proof very cute. The utilization of this structure to derive Theorem 3.2 is particularly appealing. While a more direct bound would be interesting, the current result is already strong.", "other_comments_or_suggestions": "This is a technically rich paper, and adding more intuition and explanations in the main body would enhance clarity. For example,\n- More explanation of Definition 2.2 and Proposition 2.3 would be helpful. Initially, the connection to standard $(\\epsilon,\\delta)$-DP is clear, but the link to $f$-DP is less obvious. Perhaps explicitly stating that $\\hat{f}$ is the conjugate $f^*$ (as in Dong et al.) and that the privacy curve of an $f$-DP mechanism is given by $\\delta(\\epsilon) = 1 +f^*(-e^{\\epsilon}) = 1 + \\sup_x -e^{\\epsilon}x -f(x)$  would make this clearer.\n- More clarification on Definition 2.7 would be helpful.", "questions_for_authors": "1. regarding Def. 2.7, I assume the max over $x$ relates to the privacy curve/$f$-DP definition, while taking the min over $\\epsilon$ provides the best possible valid tradeoff function. Is that right?\n2. I also wonder (a). why use $\\epsilon(\\delta)$ instead of $\\delta(\\epsilon)$? (b) Is $\\epsilon(\\delta)$ essentially the best possible $e^{\\epsilon}$ for a given $\\delta$ in this def.?\n3. Is Theorem 3.1 general for both guessing games? I assume it is general, but the context could be clearer.\n\nTwo questions out of curiosity:\n4. Can we potentially leverage the structural property of attach methods to derive tighter bounds, i.e., attack-specific guessing game bounds instead of general bounds?\n5. Suppose we call $K$ times instead of once—how would this impact the bounds? It seems that modifying Lemma A.1 would suffice, but I don't have a good intuition on what it would look like.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "zDggNPznTK", "reviewer": "Reviewer_vgFz", "summary": "This paper considering auditing the claimed $f$-DP guarantees of a model training procedure with a single training run; prior work of Steinke et al. (NeurIPS 2023) considering the same problem but in the setting of $(\\epsilon, \\delta)$-DP. $f$-DP provides a more fine-grained view of the DP guarantees of a mechanism, instead of a crude understanding with two parameters $(\\epsilon, \\delta)$.\n\nGiven a mechanism $M$ that is claimed to satisfy a certain $f$-DP guarantee, the auditing procedure is formalized as a two-step procedure:\n* The auditor designs a randomized experiment using the description of $M$ that yields some observation $o$; this involves running $M$ on some designed input dataset.\n* The auditor then based on the observation $o$ and claimed $f$-DP, either accepts or rejects.\n\nThe guarantee that such an auditor must satisfy is that if $M$ indeed satisfies $f$-DP, then the auditor accepts with high probability.\nThe utility of the auditor is established empirically, namely if $M$ does not satisfy $f$-DP (or violates it quite significantly), then we would like to reject with high probability.\n\nSuch an auditor can be used to compute an empirical privacy guarantee by considering a family $F$ of potential $f$-DP guarantees, and given the observation, picking a maximal $f$ which the auditor accepts, and report the $(\\epsilon, \\delta)$-DP guarantee satisfied by it.\n\nThe procedure considered by Steinke et al. was to consider $m$ canaries, and insert each in the training dataset with probability $0.5$, and the auditor then uses a membership inference technique to guess if each canary was included in the training set or not.\n\nThe main contributions in the paper are:\n* It designs a variant of the auditing procedure of Steinke et al. that uses $k$ choices for each of $m$ canaries inserted, instead of just a single choice which is included or not, and\n* It provides an upper bound on the expected number of correct guesses in terms of the $f$-DP guarantee and designs a hypothesis test using this bound.\n* Experimental results are provided, on simple Gaussian mechanism, and on CIFAR dataset, that demonstrate that the proposed auditing procedure is able to provide a large empirical privacy lower bound.\n\nThe main advantage of using $f$-DP instead of $(\\epsilon, \\delta)$-DP is that in Steinke et al. handled the $\\delta$ term naively by making the bound worse by $m \\delta$, which makes the bound degrade with the number of canaries added. Using $f$-DP is able to handle this in a more fine-grained manner.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "The claims are supported by sufficient evidence in the paper.", "methods_and_evaluation_criteria": "The proposed methods are sound, and the evaluation criteria also make sense for the considered problem.", "theoretical_claims": "Proofs of theoretical claims are provided in the Appendix (unfortunately, I was not able to go through all of it in detail, but I can believe they are correct).", "experimental_designs_or_analyses": "The experimental design makes sense to me and I do not see any issues.", "relation_to_broader_scientific_literature": "The paper makes a significant contribution to the literature on differential privacy, and is likely to inspire follow-up work.", "essential_references_not_discussed": "To the best of my knowledge, essential references are adequately discussed.", "other_strengths_and_weaknesses": "The paper makes a solid contribution for auditing mechanisms that satisfy $f$-DP. It is also well-written for the most part and a pleasure to read (modulo some some parts that I found hard to read that are mentioned under \"Other Comments Or Suggestions\" below).\n\nI don't see any major weakness, but I feel there is one argument missing about handling a large family $F$ of potential $f$-DP guarantees. (See under \"Questions for Authors\".)", "other_comments_or_suggestions": "* Update `\\icmltitlerunning` command to have the title of the paper instead of “Submission and Formatting Instructions for ICML 2025”.\n* Line 132 (left column): What is $X$ in $f : X \\to \\mathbb{R}$ ? Shouldn’t it be $f : [0, 1] \\to [0, 1]$ ?\n* Line 188 (left column): Is there a $\\log$ missing in the equation for $\\epsilon(\\delta)$?\n* Perhaps move Algorithm 1 to Page 4 where it is first mentioned?\n* I found Algorithm 3 extremely hard to understand. Perhaps it is trying to perform the test in some efficient manner, but if possible, I would recommend preferring simplicity over efficiency. Is there a different procedure that could be inefficient, but is more intuitive to understand? If so, I would recommend including such a version in the main body, and defer this more efficient version to the Appendix. Or at the very least, it would be helpful to explain what $r[i]$ and $h[i]$ are supposed to intuitively stand for.\n* Figure 1: What is the value of $\\delta$? Is it the same value used for all the four noise values?\n* Figure 4: It might be better to stick to the convention of using `blue` for Steinke et al. and `orange` for “This paper” to be consistent with Figures 1-3.", "questions_for_authors": "One major confusion I have is: why it is correct to simply take the maximal $f \\in F$.\nWhy is there no price to pay for how large the family $F$ is?\n\nNaively, one could apply a union bound over all $F$ to argue that one does not accidentally pick an $f$ that the mechanism does not satisfy. But perhaps the union bound is not required if $F$ is totally ordered, since we are using the same observation $o$ in $\\mathrm{evaluate}(o, f)$ for all $f \\in F$, and perhaps it holds that for any $o$, if $f_1 \\le f_2$ (i.e. $f_2$ is more private than $f_1$) then $\\mathrm{evaluate}(o, f_1) \\ge \\mathrm{evaluate}(o, f_2)$ (this is a natural assumption on $\\mathrm{evaluate}$, and perhaps better to state explicitly).\n\nBut when $F$ is not totally ordered, how does one argue this? I see that a full union bound over $F$ is not required, but some smarter union bound is perhaps needed. As far I can tell, the main body of the paper only analyzes the case of auditing a single $f$.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The reviewers collectively recognized this paper's contribution in developing a more accurate and efficient auditing procedure for f-differential privacy that requires only a single run of the target mechanism. Reviewers highlighted the theoretical elegance of the paper, particularly its generalization of previous work and improved handling of the delta term when auditing privacy guarantees. For the camera-ready version, please clarify the experimental setup details, especially regarding the Gaussian mechanism experiments, and ensure consistent notation throughout the paper.
Decision: Accept (oral)