# auditing_fdifferential_privacy_in_one_run__6928fa45.pdf

Auditing f-Differential Privacy in One Run

Saeed Mahloujifar 1 Luca Melis 1 Kamalika Chaudhuri 1

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 (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 a more accurate measure of privacy than the traditional ϵ, δ differential privacy parameters. We use our auditing procure and analysis to obtain empirical privacy, demonstrating that our auditing procedure delivers tighter privacy estimates.

1. Introduction

Differentially private machine learning (Chaudhuri et al., 2011; Abadi et al., 2016) has emerged as a principled solution to learning models from private data while still preserving privacy. Differential privacy (Dwork, 2006) is a cryptographically motivated definition, which requires an algorithm to possess certain properties: specifically, a randomized mechanism is 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.

Enforcing this guarantee requires the algorithm to be carefully designed and analyzed. The process of designing and analyzing such algorithms is prone to errors and imperfections as has been noted in the literature (Tramer et al., 2022). A 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-

1Meta. Correspondence to: Saeed Mahloujifar <saeedm@meta.com>.

Proceedings of the 42 nd International Conference on Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

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 a randomized algorithm that takes an implementation of a mechanism M, runs it in a black-box manner, and attempts to test a privacy hypothesis (such as, a differential privacy parameter). The procedure outputs 0 if there is sufficient evidence that the mechanism does not satisfy the hypothesized guarantees and 1 otherwise. The audit mechanism must possess two essential properties: 1) it must have a provably small false-negative rate, ensuring that it would not erroneously reject a truly differentially private mechanism, with high probability; 2) it needs to empirically exhibit a reasonable 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 accounting (Abadi et al., 2016; Dong et al., 2019; Mironov, 2017), which is generally thought to be impossible in a black-box manner (Zhu et al., 2022).

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 inefficient for most private machine learning use-cases, where running the algorithm involves training a large model.

Recent work (Steinke et al., 2023) remove this limitation by proposing an elegant auditing method that runs a differentially private training algorithm a single time. In particular, they rely on the randomness of training data to obtain bounds on 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 privacy-preserving algorithms (e.g., Gaussian mechanism) and those reported by their auditing algorithm.

In this work, we propose a novel auditing procedure that is

Auditing f-Differential Privacy in One Run

computationally efficient and accurate. Our method requires only a single run of the privacy mechanism 1 and leverages the f-DP curve (Dong et al., 2019), which allows for a more fine-grained accounting of privacy than the traditional reliance on ϵ, δ parameters. By doing so, we provide a tighter empirical assessment of privacy.

We experiment with our approach on both simple Gaussian mechanisms as well as a model trained on real data witth 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.

Technical overview: We briefly summarize the key technical components of our work and compare it with that of Steinke et al. (2023). Their auditing procedure employed a game similar to a membership inference process: the auditor selects a 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 auditor performs a membership inference attack to determine whether each canary was included. The number of correct guesses made by the adversary in this setting forms a random variable. The key technical contribution of Steinke et al. was to establish a tail bound on this random variable for mechanisms satisfying (ϵ)-DP. Specifically, they demonstrated 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ϵ eϵ+1. To extend this analysis to approximate DP mechanisms, they further showed that the probability of the adversary s success exceeding this tail bound is at most O(n δ).

Steinke et al. highlighted a limitation in their approach in auditing specific mechanisms, such as the Gaussian mechanism. They correctly argue that simplifying the mechanism s behavior to just two parameters, (ϵ, δ) , results in suboptimal auditing of specific mechanisms. In other words, the effectiveness of membership inference attacks against the Gaussian mechanism differs significantly from predictions based solely on the (ϵ, δ) parameters. To overcome this limitation, we propose auditing the entire privacy curve of a mechanism, rather than focusing solely on (ϵ, δ). Our solution involves three key technical steps:

1. We derive an upper bound on the adversary s success in correctly guessing a specific canary for mechanisms

1In the context of privacy-preserving training of machine learning models, the privacy mechanism refers to the training algorithm. Therefore, when we mention a single run, we are specifically referring to a single execution of the training algorithm, not the inference algorithm.

satisfying f-DP. This bound is an improved version of the result by (Hayes et al., 2023) for bounding training data reconstruction in DP mechanisms. However, this is insufficient, as the adversary s guesses could be dependent, potentially leading to correlated successes (e.g., correctly or incorrectly guessing all samples).

2. To address the issue of dependency, we refine our analysis by defining pi as the probability of the adversary making exactly i correct guesses. We derive a recursive relation that bounds pi based on p1, . . . , pi 1. This recursive 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 1 to bound the probability of making i 1 correct guesses given that the first guess was correct. For the incorrect guess case, we perform a 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 1 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 inequality, we derive our final recursive relation. To the best of our knowledge, This combination of trade-off function with shuffling is a new technique and could have broader applications.

3. 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.

We also generalize our analysis to a 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 membership inference and reconstruction attacks (Section 2). In Section 3, we provide a tight analysis of our audit s accuracy based on f-DP curves. Finally, in Section 4, we describe the experimental setup used to compare the bounds.

2. Auditing fdifferential privacy

Auditing privacy involves testing a privacy hypothesis about an algorithm M. Different mathematical forms can be

Auditing f-Differential Privacy in One Run

used for a privacy hypothesis, but they all share the common characteristic of being about an algorithm/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 algorithm s output to small changes in its input. The most well-known definition among these is differential privacy.

Definition 2.1. A mechanism M is (ϵ, δ)-DP if for all neighboring datasets S, S with |S S | = 1 and all measurable sets T, we have Pr[M(S) T] eϵ Pr[M(S ) T] + δ.

In essence, differential privacy ensures that the output distribution 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 δ parameters. Consequently, auditing differential 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-differential privacy.

Notation For a function f : [0, 1] [0, 1] we use f to denote the function f(x) = 1 f(x).

Definition 2.2. A mechanism M is f-DP if for all neighboring datasets S, S and all |S S | = 1 measurable sets T we have

Pr[M(S) T] f Pr[M(S )] T] .

Note that this definition generalizes the notion of approximate differential privacy by allowing a more complex relation between the probability distributions of M(S) and M(S ). The following proposition shows how one can express approximate DP as an instantiation of f-DP.

Proposition 2.3. A mechanism is (ϵ, δ)-DP if it is f-DP with respect to f(x) = eϵ x + δ.

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 f is a valid trade-off function . That is, f is defined on domain [0, 1] and has a range of [0, 1]. Moreover, f is a decreasing and convex with f(x) 1 x for all x [0, 1]. We emphasize that this is without loss of generality. That is, if a mechanism is f-DP for a an arbitrary function f : [0, 1] [0, 1], then it is also f -DP for valid trade-off function f with f (x) f(x) for all x [0, 1] (See Proposition 2.2 in (Dong et al., 2019)).

Definition 2.5 (Order of f-DP curves). For two trade-off functions f1 and f2, we say f1 is more private than f2 and denote it by f1 f2 iff f1(x) f2(x) for all x

[0, 1]. Also, for a family of trade-off functions F, we use maximal(F) to denote the set of maximal elements w.r.t to the privacy relation. Note that F could be a partial ordered set, and maximal(F) 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 a 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.

game: M O, In this step, the auditor runs a potentially randomized experiment/game using the description of mechanism M M and obtains some observation o O.

evaluate : O 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 o is likely for a mechanism that satisfies f-DP.

The audit procedure is ψ-accurate if for all mechanism M that satisfy f-DP, we have

Pr o game(M)[evaluate(o, f) = 1] ψ.

Note that we are defining the accuracy only for positive cases. This is 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).

Next, we formally define the notion of empirical privacy (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.

Definition 2.7 (Empirical Privacy). Let (game, evaluate) be an audit procedure. We define the empirical privacy random variable for a mechanism M, w.r.t a family F of trade-off functions, to be the output of the following process. We first run the game to obtain observation o = game(M). We then construct

Fo = maximal({f F; evaluate(o, f) = 1})

where the maximal set is constructed according to Definition 2.5. Then, the empirical privacy of the mechanism at a particular δ is defined as

ϵ(δ) = min f Fo max x [0,1] log(1 f(x) δ

Note that the empirical privacy ϵ(δ) is a function of the observation o. Since, o itself is a random variable, then ϵ(δ) is also a random variable.

Auditing f-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 a 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 to that of a Gaussian mechanism.

Auditing f-DP vs DP: f-DP can be viewed as a collection of DP parameters, where instead of considering (ϵ, δ) as fixed scalars, we treat ϵ as a function of δ. For any δ [0, 1], there exists an ϵ(δ) such that the mechanism satisfies (ϵ(δ), δ)-DP. The f-DP curve effectively represents the entire privacy curve rather than a single (ϵ, δ) 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 approximate DP at each (ϵ, δ) value along the privacy curve, rejecting if any of the audits fail. However, this leads to suboptimal 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 (ϵ, δ) value to bound the probability of all these events cannot be tight because the linear approximation of privacy curve is tight in at most a single point. Hence, the guarantees of (ϵ, δ)-DP cannot be simultaneously tight for all events. However, with f-DP, we can obtain tight bounds on the probabilities of all events simultaneously. Second, For each (ϵ, δ) we have a small possibility of incorrectly rejecting the privacy hypothesis. So if we audit privacy for (ϵ(δ), δ) independently, we will reject any privacy hypothesis with probability 1.0. This challenge can be potentially resolved by using correlated randomness.

To demonstrate this key difference, we try a baseline for d auditing f-DP based on the work of (Steinke et al., 2024b)2. In this baseline, we consider a gaussian mechanism with noise σ. Then, we audit the privacy curve at various values of δ. 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 δ = 10 5. Then we observe the attack s performance and apply

2This experiment was suggested by our anonymous reviewer. We than the reviewer for their suggestion.

the method of (Steinke et 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 a generalization of membership inference attacks (Nasr et al., 2023), and closely resembles the reconstruction setting introduced in (Hayes et al., 2023).

Definition 2.8. Consider a mechanism M : [k]m Θ. In a guessing game we first sample an input dataset u [k]m

from an arbitrary distribution. We run the mechanism to get θ M(u). Then a guessing adversary A : Θ ([k] { })m tries to guess the input to the mechanism from the output. We define

the number of guesses by c = Pm i=1 I A(θ)i =

and the number of correct guesses by c = Pm i=1 I A(θ)i = ui .

Then we output (c, c ) as 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 describes a game setup based on membership inference attacks. 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 S to get a model θ M(T S). Then the adversary A inspects θ and tries to find examples that were present in S. Observe that this procedure is a guessing game with k = 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 modular, we can use any T and C for the training set and canary set. We can also use any attack algorithm A.

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 a key difference

Auditing f-Differential Privacy in One Run

from our attack setup and that is the fact that there is only a 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).

A substantial body of research has also explored the relationship between membership inference attacks and differential privacy (Sablayrolles et al., 2019; Mahloujifar et al., 2022; Balle et al., 2022; Bhowmick et al., 2018; Stock et al., 2022; Balle et al., 2022; Guo et al., 2022; Kaissis et al., 2023; 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; Bichsel 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.

Algorithm 1 Membership inference in one run game input Oracle access to a mechanism M( ), A training dataset T , An indexed canary set C = {xi; i [m]}, An attack algorithm A.

1: Set m = |C| 2: Sample u = (u1, . . . , um) Bernoulli(0.5)m, a binary vector where ui = 1 with probability 0.5. 3: Let S = {C[ui]; ui = 1}i [m], the subset of selected elements in C. 4: Run mechanism M on T S to get output θ. 5: Run membership inference attack A on θ to get set of membership predictions v = (v1, . . . , vm) which is supported on {0, 1, }m. 6: Count c, the number of correct guesses where ui = vi and c the total number of guesses where vi = . return (c, c ).

Auditing by reconstruction: We also propose an alternative way to perform auditing by reconstruction attacks. This setup starts with a training set St, similar to the membership inference setting. Then, we have a family of m

canary sets {Si c; i [m]} where each Si c contains k distinct examples. Before training, we construct a set Ss of size m by uniformly sampling an example from each Si c. Then, the adversary tries to find out which examples were sampled from each canary set Si c by inspecting the model. We recognize that this might be different from what one may consider a 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 to 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.

Algorithm 2 Reconstruction in one run game input Oracle access to a mechanism M( ), A training dataset T , number of canaries m, number of options for each canary k, a matrix of canaries C = {xi j}i [m],j [k], an attack algorthm A.

1: Let u = (u1, . . . , um) be a vector uniformly sampled from [k]m. 2: Let S = {xi ui}i [m]. 3: Run mechanism M on S T to get output θ. 4: Run a reconstruction attack A on θ to get a vector v = (v1, . . . , vm) which is a vector in ([k] { })m. 5: Count c the number of coordinates where ui = vi and c the number of coordinates where vi = . return (c, c ).

3. Implications of f-DP for guessing games

In this section, we explore the implications of f-DP for guessing games. Specifically, we focus on bounding the probability of making more than c correct guesses for adversaries 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. Theorem 3.1. [Bounds for adversary with bounded guesses] Let M : [k]m Θ be a f-DP mechanism. Let u be a random variable uniformly distributed on [k]m. Let A: Θ ([k] { })m be a guessing adversary which always makes at most c guesses, that is

θ Θ, Pr h m X

i=1 I A(θ)i = > c i = 0,

and let v A(M(u)). Define pi = Pr h P

j [m] I(uj =

vj) = i i . For all subset of indices T [c ], we have

i mpi f( 1 k 1

Auditing f-Differential Privacy in One Run

This Theorem, which we consider to be our main technical contribution, provides a nice invariant that bounds the probability pi (probability of making exactly i correct guesses) based on the value of other pjs. Imagine Pf to be a set of vectors p = (p1, . . . , pc ) that could be realized for an attack on a f-DP mechanism. Theorem 3.1 significantly confines this set. However, this still does not resolve the auditing task. We are interested in bounding maxp Pf Pc

i=c pi, the maximum probability that an adversary can make more than c 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 maxp Pf Pc

3.1. Numerically bounding the tail

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 c correct guesses in a guessing game with alphabet size k and a mechanism that satisfies f-DP. This algorithm relies on the confinement imposed by Theorem 3.1. Note that Algorithm 3 is a decision algorithm, it takes a value τ and decide if the probability of making more than c correct guesses is less than or equal to τ. 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 a fixed τ. This is because we (similar to (Steinke et al., 2023)) want to set the accuracy of our audit to be a fixed value such as 0.95.

Algorithm 3 Numerically deciding an upper bound probability of making more than c correct guesses input Oracle access to f and f 1, number of guesses c , number of correct guesses c, number of samples m, alphabet size k, probability threshold τ (default is τ = 0.05). 1: 0 i c set h[i] = 0, and r[i] = 0. 2: set r[c] = τ c

3: set h[c] = τ c c

m . 4: for i [c 1, . . . , 0] do 5: h[i] = (k 1) f 1 r[i + 1]

6: r[i] = r[i + 1] + i c i h[i] h[i + 1] . 7: end for 8: if r[0] + h[0] c

m then 9: Return True; (Probability of c correct guesses (out of c ) is less than τ). 10: else 11: Return False; (Probability of having c correct guesses (out of c ) could be more than τ). 12: end if

Theorem 3.2. If Algorithm 3 returns True on inputs

f, k, m, c, c and τ, then for any f-DP mechanism M : [k]m Θ, any guessing adversary A: Θ ([k] { })m with at most c guesses, defining u to be uniform over [k]m, and setting v A M(u) , we have Pr[ Pm i=1 I(ui = vi) c] τ.

In a nutshell, this algorithm tries to obtain an upper bound on the sum pc +pc+1 +. . . , pc . We assume this probability is greater than τ, and we obtain lower bound on pc 1 + pc + + pc based on this assumption. We keep doing this recursively until we have a lower bound on p0 + + pc . If this lower bound is 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. Auditing f-DP with Algorithm 3: When auditing the f-DP for a mechanism, we assume we have injected m canaries, and ran an adversary that is allowed to make c

guesses and recorded that the adversary have made c correct guesses. In such scenario, we will reject the hypothesized privacy of the mechanism if the probability of this observation is less than a threshold τ, which we by default set to 0.05. To this end, we just call Algorithm 3 with parameters c, c , m, τ = 0.05 and f. Then if the algorithm returns True, we will reject the privacy hypothesis and approve it otherwise. Empirical privacy: Although auditing in essence is a hypothesis 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 h1, . . . , hw as our family of f-DP curves. These sets are ordered in their strength, meaning that any mechanism that satisfies hi, would also satisfy hj for all j < i. Then, we would report the strongest privacy hypothesis that passes the test as the empirical privacy of the mechanism.

4. Experiments

Most of our experiments are conducted in an idealized setting, similar to that used in (Steinke et 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 idealized 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 ϵ. More specifically, as specified in Definition 2.6, we instantiate our auditing with a game and evaluation setup. We use Algorithm 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 3 as our evaluation setup to audit an f-DP curve based on the observation from Algorithm 4. Note that in our

Auditing f-Differential Privacy in One Run

comparison with the auditing of Steinke et 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.

In all experiments, we use empirical ϵ 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 mechanisms with varying standard deviations (this forms an ordered 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-sampling rates and number of steps, and various noise stds.

4.1. Comparison with (Steinke et al., 2023)

In this section, we evaluate our auditing method for membership 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 ϵ values. We vary the number of canaries (m) from 102 to 107 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 m-dimensional gaussian mechanism, V + N(0m, σ), with V being a uniform sample from {0, 1}m. The adversary s goal is to guess c 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 mechanism. 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 c that achieves the highest empirical ϵ and then report that as the empirical ϵ. We audit the exact same setup with the auditing method of (Steinke et al., 2024b). Figure 1 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.

Experiments on CIFAR-10: We also run experiments on CIFAR-10 on a modified version of the WRN16-

4 (Zagoruyko & Komodakis, 2016) architecture, which substitutes 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, random horizontal flip and jitter) and apply an exponential moving average of the model weights with a decay parameter 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 gradients from dp-sgd. As done in the work of (Steinke et al., 2023), we audit CIFAR-10 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, δ = 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 ε. We are able to achieve tighter empirical lower bounds. We also report the performance of the black-box attack, where the auditor does not control the training pipeline and can only compute membership scores (losses) from the final model. Figure 3 shows how we 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).

Finally, we report the results of auditing the robust membership inference attack (Zarifzadeh et al., 2023) (RMIA), which to the best of our knowledge, represents the Stateof-The-Art (So TA) black-box membership inference attack on CIFAR-10 from the literature. We reproduce the results in (Zarifzadeh et al., 2023) with a non-private Wide Res 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 membership 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 clearly outperforms Steinke et al. for all bounded guesses settings, with higher empirical epsilon for larger abstention values (i.e., fewer guesses).

Auditing f-Differential Privacy in One Run

102 103 104 105 106 107

Number of Canaries

Empirical (SNJ)

Empirical (Ours)

Theoretical

102 103 104 105 106 107

Number of Canaries

Empirical (SNJ)

Empirical (Ours)

Theoretical

102 103 104 105 106 107

Number of Canaries

Empirical (SNJ)

Empirical (Ours)

Theoretical

102 103 104 105 106 107

Number of Canaries

Empirical (SNJ)

Empirical (Ours)

Theoretical

Figure 1. Comparison between our empirical privacy lower bounds and that of (Steinke et al., 2023) at δ = 10 5.

Figure 2. Comparison with auditing procedure of (Steinke et al., 2023) on CIFAR-10 in white-box setting using gradient-based membership inference. Empirical ϵ is reported at δ = 10 5.

Figure 3. Comparison with Steinke et al. (2023) for CIFAR-10 in black-box setting. Empirical ϵ is reported at δ = 10 5.

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 (ϵ, δ) and prove an upper bound on the probability of any adversary obtaining c correct guesses out of c total guesses, given m canaries

Figure 4. Comparison with auditing procedure of (Steinke et al.,

2023) on non-private model trained on CIFAR-10 against blackbox RMIA method (Zarifzadeh et al., 2023). Empirical ϵ is reported at δ = 10 5.

available. For the case of δ = 0, their bound is tight. For the case of δ > 0, however, they need to define a set of undesirable events and bound their collective probability. This incurs an additional O(m δ) in the probability. The reason why their bounds start to degrade when we increase m is this very fact. The m δ 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 (ϵ, δ) 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 a single point for mechanisms that we are interested in (e.g. the Gaussian mechanism). Namely, there is only a single probability p [0, 1] where we have

p = Pr[M(D) E] and eϵ p + δ = Pr[M(D ) E].

Our bound is designed to avoid this issue. We derive a bound that uses the exact f-DP curve, which ensures that for all probabilities p [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 3 is designed to

Auditing f-Differential Privacy in One Run

Noise # Canaries Theoretical Steinke et al. Steinke et al. (pointwise) Ours σ = 0.5 105 9.99 4.99 5.01 8.16 σ = 1.0 105 4.37 2.61 2.71 3.61 σ = 2.0 105 1.99 1.33 1.35 1.59 σ = 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 5.

apply the bound on events that can be simultaneously tight. This way, our bound does not have the problem of getting worse as the number of samples increases.

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 designed. 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 divided by the expectation incorrect guesses conditioned on the same event is greater than c/c . This step is not tight as we cannot have a mechanism where the adversary makes exactly c correct guesses with probability greater than 0, while making more than c correct guesses with probability exactly 0. 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.

4.2. Improving (Steinke et al., 2024b) by testing multiple hypothesis.

In this section, we describe a method that uses the method of (Steinke et al., 2024b) to audit f-DP. We use the idea that if a mechanism satisfies f-DP, then for all δ [0, 1] it should pass the DP audit for (ϵδ, δ), where ϵδ is the optimal ϵ obtained from f for δ. A key issue here is that auditing in one run will always suffer from probabilistic error. There is a small chance τ 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 (ϵ, δ), we can potentially avoid this multiplication. Here, we design an experiment that shows even with this this approach, the bounds of previous work cannot match ours. We try to auditing Gaussian DP. First we instantiate a membership inference game with a fixed number of canaries (m) and a fixed number of guesses (c ). This is optimized to achieve the best ϵ at δ = 10 5. We collect the number of correct guesses (c) in the membership inference

game. Using (m, c, c ) we can now auditing (ϵδ, δ)-DP for a large range of values of δ (δ = 10 x 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 δ. Then, we reject the privacy hypothesis for gaussian-DP if any of the individual tests are rejected. Using this auditing procedure, we obtain empirical epsilon values.

Table 1 shows the results of our experiments. We can see that there is still a 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 to other points on the f-DP curve and can only observe a 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

We introduce a new approach for auditing the privacy of algorithms in a 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 practitioners to make more informed decisions regarding privacyutility 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 parameters 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.

Auditing f-Differential Privacy in One Run

Impact Statement

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 development of more trustworthy and accountable AI technologies. The main societal benefit is positive: practitioners and policymakers will be better equipped to assess and mitigate potential privacy harms, leading to safer deployment of data-driven systems.

Abadi, M., Chu, A., Goodfellow, I., Mc Mahan, H. B., Mironov, I., Talwar, K., and Zhang, L. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pp. 308 318, 2016.

Andrew, G., Kairouz, P., Oh, S., Oprea, A., Mc Mahan, H. B., and Suriyakumar, V. One-shot empirical privacy estimation for federated learning. ar Xiv preprint ar Xiv:2302.03098, 2023.

Annamalai, M. S. M. S. and De Cristofaro, E. Nearly tight black-box auditing of differentially private machine learning. ar Xiv preprint ar Xiv:2405.14106, 2024.

Balle, B., Cherubin, G., and Hayes, J. Reconstructing training data with informed adversaries. In 2022 IEEE Symposium on Security and Privacy (SP), pp. 1138 1156. IEEE, 2022.

Bertran, M., Tang, S., Roth, A., Kearns, M., Morgenstern, J. H., and Wu, S. Z. Scalable membership inference attacks via quantile regression. Advances in Neural Information Processing Systems, 36, 2024.

Bhowmick, A., Duchi, J., Freudiger, J., Kapoor, G., and Rogers, R. Protection against reconstruction and its applications in private federated learning. ar Xiv preprint ar Xiv:1812.00984, 2018.

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.

Bichsel, B., Steffen, S., Bogunovic, I., and Vechev, M. Dpsniper: Black-box discovery of differential privacy violations using classifiers. In 2021 IEEE Symposium on Security and Privacy (SP), pp. 391 409. IEEE, 2021.

Carlini, N., Chien, S., Nasr, M., Song, S., Terzis, A., and Tramer, F. Membership inference attacks from first prin-

ciples. In 2022 IEEE Symposium on Security and Privacy (SP), pp. 1897 1914. IEEE, 2022.

Cebere, T., Bellet, A., and Papernot, N. Tighter privacy auditing of dp-sgd in the hidden state threat model. ar Xiv preprint ar Xiv:2405.14457, 2024.

Chadha, K., Jagielski, M., Papernot, N., Choquette-Choo, C., and Nasr, M. Auditing private prediction. ar Xiv preprint ar Xiv:2402.09403, 2024.

Chaudhuri, K., Monteleoni, C., and Sarwate, A. D. Differentially private empirical risk minimization. Journal of Machine Learning Research, 12(3), 2011.

Chen, Z. and Pattabiraman, K. Overconfidence is a dangerous thing: Mitigating membership inference attacks by enforcing less confident prediction. ar Xiv preprint ar Xiv:2307.01610, 2023.

Ding, Z., Wang, Y., Wang, G., Zhang, D., and Kifer, D. Detecting violations of differential privacy. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, pp. 475 489, 2018.

Dong, J., Roth, A., and Su, W. J. Gaussian differential privacy. ar Xiv preprint ar Xiv:1905.02383, 2019.

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? ar Xiv preprint ar Xiv:2402.07841, 2024.

Dwork, C. Differential privacy. In International colloquium on automata, languages, and programming, pp. 1 12. Springer, 2006.

Guo, C., Karrer, B., Chaudhuri, K., and van der Maaten, L. Bounding training data reconstruction in private (deep) learning. In International Conference on Machine Learning, pp. 8056 8071. PMLR, 2022.

Hayes, J., Mahloujifar, S., and Balle, B. Bounding training data reconstruction in dp-sgd. ar Xiv preprint ar Xiv:2302.07225, 2023.

Homer, N., Szelinger, S., Redman, M., Duggan, D., Tembe, W., Muehling, 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. PLo S genetics, 4(8):e1000167, 2008.

Hu, H., Salcic, Z., Sun, L., Dobbie, G., Yu, P. S., and Zhang, X. Membership inference attacks on machine learning: A survey. ACM Computing Surveys (CSUR), 54(11s):1 37, 2022.

Auditing f-Differential Privacy in One Run

Hyland, S. L. and Tople, S. On the intrinsic privacy of stochastic gradient descent. Preprint at https://arxiv. org/pdf/1912.02919. pdf, 2019.

Jagielski, M., Ullman, J., and Oprea, A. Auditing differentially private machine learning: How private is private sgd? Advances in Neural Information Processing Systems, 33:22205 22216, 2020.

Jia, J., Salem, A., Backes, M., Zhang, Y., and Gong, N. Z. Memguard: Defending against black-box membership inference attacks via adversarial examples. In Proceedings of the 2019 ACM SIGSAC conference on computer and communications security, pp. 259 274, 2019.

Kaissis, G., Hayes, J., Ziller, A., and Rueckert, D. Bounding data reconstruction attacks with the hypothesis testing interpretation of differential privacy. ar Xiv preprint ar Xiv:2307.03928, 2023.

Kaissis, G., Ziller, A., Kolek, S., Riess, A., and Rueckert, D. Optimal privacy guarantees for a relaxed threat model: Addressing sub-optimal adversaries in differentially private machine learning. Advances in Neural Information Processing Systems, 36, 2024.

Leino, K. and Fredrikson, M. Stolen memories: Leveraging model memorization for calibrated {White-Box} membership inference. In 29th USENIX security symposium (USENIX Security 20), pp. 1605 1622, 2020.

Li, J., Li, N., and Ribeiro, B. {MIST}: Defending against membership inference attacks through {Membership Invariant} subspace training. In 33rd USENIX Security Symposium (USENIX Security 24), pp. 2387 2404, 2024.

Lu, F., Munoz, J., Fuchs, M., Le Blond, T., Zaresky Williams, E., Raff, E., Ferraro, F., and Testa, B. A general framework for auditing differentially private machine learning. Advances in Neural Information Processing Systems, 35:4165 4176, 2022.

Mahloujifar, S., Sablayrolles, A., Cormode, G., and Jha, S. Optimal membership inference bounds for adaptive composition of sampled gaussian mechanisms. ar Xiv preprint ar Xiv:2204.06106, 2022.

Matthew, J., Milad, N., Christopher, C.-C., Katherine, L., and Nicholas, C. Students parrot their teachers: Membership inference on model distillation. ar Xiv preprint ar Xiv: 2303.03446, 2023.

Mironov, I. R enyi differential privacy. In 2017 IEEE 30th computer security foundations symposium (CSF), pp. 263 275. IEEE, 2017.

Nasr, M., Shokri, R., and Houmansadr, A. Machine learning with membership privacy using adversarial regularization.

In Proceedings of the 2018 ACM SIGSAC conference on computer and communications security, pp. 634 646, 2018.

Nasr, M., Songi, S., Thakurta, A., Papernot, N., and Carlin, N. Adversary instantiation: Lower bounds for differentially private machine learning. In 2021 IEEE Symposium on security and privacy (SP), pp. 866 882. IEEE, 2021.

Nasr, M., Hayes, J., Steinke, T., Balle, B., Tram er, F., Jagielski, M., Carlini, N., and Terzis, A. Tight auditing of differentially private machine learning. ar Xiv preprint ar Xiv:2302.07956, 2023.

Pillutla, K., Andrew, G., Kairouz, P., Mc Mahan, H. B., Oprea, A., and Oh, S. Unleashing the power of randomization in auditing differentially private ml. Advances in Neural Information Processing Systems, 2024.

Sablayrolles, A., Douze, M., Schmid, C., Ollivier, Y., and J egou, H. White-box vs black-box: Bayes optimal strategies for membership inference. In International Conference on Machine Learning, pp. 5558 5567. PMLR, 2019.

Sander, T., Stock, P., and Sablayrolles, A. Tan without a burn: Scaling laws of dp-sgd. In International Conference on Machine Learning. PMLR, 2023.

Shokri, R., Stronati, M., Song, C., and Shmatikov, V. Membership inference attacks against machine learning models. In 2017 IEEE symposium on security and privacy (SP), pp. 3 18. IEEE, 2017.

Steinke, T., Nasr, M., and Jagielski, M. Privacy auditing with one (1) training run. ar Xiv preprint ar Xiv:2305.08846, 2023.

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: Empirical auditing and principled heuristic analysis of differentially private sgd. ar Xiv preprint ar Xiv:2410.06186, 2024a.

Steinke, T., Nasr, M., and Jagielski, M. Privacy auditing with one (1) training run. Advances in Neural Information Processing Systems, 36, 2024b.

Stock, P., Shilov, I., Mironov, I., and Sablayrolles, A. Defending against reconstruction attacks with r\ enyi differential privacy. ar Xiv preprint ar Xiv:2202.07623, 2022.

Tang, X., Mahloujifar, S., Song, L., Shejwalkar, V., Nasr, M., Houmansadr, A., and Mittal, P. Mitigating membership inference attacks by {Self-Distillation} through a novel ensemble architecture. In 31st USENIX Security Symposium (USENIX Security 22), pp. 1433 1450, 2022.

Auditing f-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. ar Xiv preprint ar Xiv:2202.12219, 2022.

Wang, J. T., Mahloujifar, S., Wu, T., Jia, R., and Mittal, P. A randomized approach for tight privacy accounting. ar Xiv preprint ar Xiv:2304.07927, 2023.

Watson, L., Guo, C., Cormode, G., and Sablayrolles, A. On the importance of difficulty calibration in membership inference attacks. ar Xiv preprint ar Xiv:2111.08440, 2021.

Ye, J. 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, S. K., Bindschaedler, V., and Shokri, R. Enhanced membership inference attacks against machine learning models. In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, pp. 3093 3106, 2022.

Zagoruyko, S. and Komodakis, N. Wide residual networks. ar Xiv preprint ar Xiv: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 International Conference on Artificial Intelligence and Statistics, pp. 4782 4817. PMLR, 2022.

Auditing f-Differential Privacy in One Run

A.1. 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 a simplified version of Theorem 3.1 without abstentions and then we focus on the proof of the main theorem. First, we have a Lemma that bounds the probability of any event conditioned on correctly guessing a single canary. Lemma A.1. Let M : [k]m Θ be a mechanism that satisfies f-DP. Also let A: Θ ([k] { })m be a guessing attack. Let u be a random variable uniformly distributed over [k]m and let v A M(u) . Then for any subset E Θ we have

f k Pr M(u) E Pr M(u) E and u1 = v1 f k Pr M(u) E

where f k(x) = sup{α; α + f(x α

k 1 ) 1} and f k (x) = inf{α; (k 1)f(α) + x α) 1}.

This Lemma which is a generalization and an improvement over the main Theorem of (Hayes et al., 2023), shows that the probability of an event cannot change too much if 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 we are not interested in expectations. Rather, we 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.1. These properties are specified in the following Proposition and proved in the Appendix. Proposition A.2. The functions f k as defined in Lemma A.1 is increasing and concave. The function f k as defined in Lemma A.1 is increasing and convex.

Now, we are ready to outline the proof of a simplified variant of our Theorem 3.1 for adversaries that make a 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]m Θ be a f-DP mechanism. Let u be a random variable uniformly distributed on [k]m. Let A: Θ [k]m be a guessing adversary and let v A(M(u)). Define pi = Pr h (P

j [m] I uj =

vj) = i i . For all subset of indices T [m], we have

i mpi f( 1 k 1

Proof. Let us define a random variable t = (t1, . . . , tm) which is defined as ti = I(ui = vi) We have

i=1 ti = c] = Pr[

i=2 ti = c 1 and t1 = 1] + Pr[

i=2 ti = c and t1 = 0]

Now by Lemma A.1 we have Pr[Pm i=2 ti = c 1 and t1 = 1] f k(Pm i=2 ti = c 1). This is a nice invariant that we can use but Pm i=2 ti = c 1 could be really small depending on how large m is. To strengthen the bound we sum all pc s for c T, and then apply the lemma on the aggregate. That is

i=1 ti = j] = X

i=2 ti = j and t1 = 0] + X

i=2 ti = j 1 and t1 = 1]

i=2 ti T and t1 = 0] + Pr[1 +

i=2 ti T and t1 = 1]

Now we only use the inequality from Lemma A.1 for the second quantity above. Using the inequality for both probabilities is not ideal because they cannot be tight at the same time. So we have,

i=2 T and t1 = 0] + f k(Pr[1 +

i=2 ti T]).

Auditing f-Differential Privacy in One Run

Now we use a trick to make this cleaner. We use the fact that this inequality is invariant to the order of indices. So we can permute ti s and the inequality still holds. We have,

j T pj E π Π[m][Pr[

i=2 tπ(i) T and tπ(1) = 0]] + E π Π[m][f k(Pr[1 +

i=2 tπ(i) T])]

E π Π[m][Pr[

i=2 tπ(i) T and tπ(1) = 0]] + f k( E π Π[m][Pr[1 +

i=2 tπ(i) T]]).

Now we perform a double counting argument. Note that when we permute the order Pm i=2 tπ(i) = j and tπ(1) = 0 counts each instance t1, . . . , tm with exactly j non-zero locations, for exactly (m j) (m 1)! times. Therefore, we have

E π Π[m][Pr[

i=2 tπ(i) T and tπ(1) = 0]] = X

With a similar argument we have,

E π Π[m][Pr[1 +

i=2 tπ(i) T]] = X

Then, we have

m pj + f k( X

j mpj + m j + 1

And this implies

j mpj f k( X

j mpj + m j + 1

And this, by definition of f k implies

j mpj f( 1 k 1

A.2. Proof of Main Lemmas and Theorems

Proof of Lemma A.1. Let p = Pr[M(u) E and u1 = v1] and q = Pr[M(u) E]. We have

Auditing f-Differential Privacy in One Run

i [k] Pr[M(u) E and u1 = v1 = i]

i [k] Pr[M(u) E and v1 = i | u1 = i]

j [k]\{i} Pr[M(u) E and v1 = i | u1 = i]

(By definition of f-DP) 1

j [k]\{i} 1 f Pr[M(u) E and v1 = i | u1 = j]

(By convexity of f) 1 f

j [k]\{i} Pr[M(u) E and v1 = i | u1 = j])

1 k Pr[M(u) E and v1 = i | u1 = j])

j [k]\{i} Pr[M(u) E and v1 = i and u1 = j])

= 1 f( 1 k 1 Pr[M(u) E and u1 = v1])

Similarly we have,

i [k] Pr[M(u) E and u1 = v1 = i]

i [k] Pr[M(u) E and v1 = i | u1 = i]

j [k]\{i} Pr[M(u) E and v1 = i | u1 = i]

(By definition of f-DP) 1

j [k]\{i} f 1 1 Pr[M(u) E and v1 = i | u1 = j]

(By convexity of f) f 1

j [k]\{i} 1 Pr[M(u) E and v1 = i | u1 = j])

1 k (1 Pr[M(u) E and v1 = i | u1 = j]))

j [k]\{i} Pr[M(u) E and v1 = i and u1 = j])

= f 1( 1 k 1(1 Pr[M(u) E and u1 = v1]))

= f 1(1 q + p

Auditing f-Differential Privacy in One Run

This implies that,

f(p) (k 1) + q p 1

Proof of Proposition A.2. The function is increasing simply because f is decreasing. We now prove concavity. Let α1 = fk(x1) and α2 = fk(x2). By definition of fk we have

α1 + f(x1 α1

and α2 + f(x2 α2

Averaging these two we get,

2 + f( x1 α1

k 1 ) + f( x2 α2

By convexity of f we have α1 + α2

Therefore, by definition of f k, we have f k( x1+x2

2 . Similarly, f k in increasing just because f is decreasing. And assuming α1 = fk(x1) and α2 = fk(x2) we have

f k (x1 + x2

2 ) α1 + α2

2 which implies f k 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 {0, 1}m, with exactly c 1s and m c 0s. So the output of this adversary is a vector v [k]m and a vector q {0, 1}m. Then, only correct guesses that are in locations that q is non-zero is counted. That is, if we define a random variable t = (t1, . . . , tm) as ti = I(ui = vi) then we have

i=1 ti qi = c]

i=2 ti = c 1 and t1 = 1 and q1 = 1] + Pr[

i=2 ti = c and t1 q1 = 0]

Now by Lemma A.1 we have

i=2 ti = c 1 and t1 = 1 and q1 = 1] f k(

i=2 ti = c 1 and q1 = 1).

This is a nice invariant that we can use but Pm i=2 ti = c 1 could be really small depending on how large m is. To strengthen the bound we sum all pc s for c T, and then apply the lemma on the aggregate. That is

i=1 ti = j]

i=2 ti = j and t1 q1 = 0] + X

i=2 ti = j 1 and t1 = 1 and q1 = 1]

i=2 ti T and t1 q1 = 0] + Pr[1 +

i=2 ti T and t1 = 1 and q1 = 1]

Auditing f-Differential Privacy in One Run

Now we only use the inequality from Lemma A.1 for the second quantity above. Using the inequality for both probabilities is not ideal because they cannot be tight at the same time. So we have,

i=2 T and t1 q1 = 0] + f k(Pr[1 +

i=2 ti T and q1 = 1]).

Now we use a trick to make this cleaner. We use the fact that this inequality is invariant to the order of indices. So we can permute ti s and the inequality still holds. We have,

j T pj E π Π[m][Pr[

i=2 tπ(i) T and tπ(1) qπ(1) = 0]] + E π Π[m][f k(Pr[1 +

i=2 tπ(i) T])]

E π Π[m][Pr[

i=2 tπ(i) T and tπ(1) = 0]] + f k( E π Π[m][Pr[1 +

i=2 tπ(i) T and qπ(1) = 1]]).

Now we perform a double counting argument. Note that when we permute the order Pm i=2 tπ(i) = j and tπ(1) = 0 counts each instance t1, . . . , tm with exactly j non-zero locations, for exactly (m j) (m 1)! times. Therefore, we have

E π Π[m][Pr[

i=2 tπ(i) qπ(i) T and tπ(1) qπ(i) = 0]] = X

With a similar argument we have,

E π Π[m][Pr[1 +

i=2 tπ(i) qπ(i) T and qπ(1) = 1]] = X

Then, we have

m pj + f k( X

j mpj + c j + 1

m pj + f k( X

j mpj + c j + 1

And this implies

j mpj f k( X

j mpj + c j + 1

And this, by definition of f k implies

j mpj f( 1 k 1

Proof of Theorem 3.2. To prove Theorem 3.2, we first state and prove a lemma which is consequence of Theorem 3.1.

Lemma A.4. For all c c [m] let us define

i mpi and βc =

We also define a family of functions r = {ri,j : [0, 1] [0, 1] [0, 1]}i j [m] and h = {hi,j : [0, 1] [0, 1]} that are defined recursively as follows.

Auditing f-Differential Privacy in One Run

i [m] : ri,i(α, β) = α and hi,i(α, β) = β and for all i < j we have

hi,j(α, β) = (k 1) f 1 ri+1,j(α, β)

ri,j(α, β) = ri+1,j(α, β) + i c i(hi,j(α, β) hi+1,j(α, β))

Then for all i j we have αi ri,j(αj, βj) and βi hi,j(αj, βj)

Moreover, for i < j, ri,j and hi,j 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 i. For j i = 0, the statement is trivially correct. We have

hi,j(αj, βj) = (k 1) f 1(ri+1,j(αj, βj)).

By induction hypothesis, we have ri+1,j(αj, βj) αi+1. Therefore we have

hi,j(αj, βj) (k 1) f 1(αi+1). (1)

Now by invoking Theorem 3.1, we have

αi+1 f( βi k 1).

Now since f is increasing, this implies (k 1) f 1(αi+1) βi (2)

Now putting, inequalities 1 and 2 together we have hi,j(αj, βj) βi. This proves the first part of the induction hypothesis for the function h. Also note that hi,j 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 ri,j. First note that there is an alternative form for ri,j by opening up the recursive relation. Let γz = z c z z 1 c z+1. We have ,

ri,j(α, β) = rj,j(α, β) + i c ihi,j(α, β) j 1 c j + 1hj,j(α, β) +

z=i+1 γzhz,j(α, β)

= rj,j(α, β) + i c ihi,j(α, β) j c j hj,j(α, β) +

z=i+1 γzhz,j(α, β)

= α j c j β + i c ihi,j(α, β) +

z=i+1 γzhz,j(α, β). (3)

Now we show that for all i we have

αi = i c iβi +

z=i+1 γzβz. (4)

This is because we have

αi i c iβi =

Auditing f-Differential Privacy in One Run

On the other hand we have

z=i+1 γzβz =

z =i+1 γz )c z

z=i+1 ( z c z i c i)c z

and this shows that Equation 4 is correct. Therefore for all i < j we have

αi αj = i c iβi j c j βj +

Now, using the induction hypothesis for h we have,

αi αj + i c ihi,j(αj, βj) j c j βj +

z=i+1 γzhz,j(αj, βj). (5)

Now verify that the right hand side of Equation 5 is equal to ri,j(αj, βj) by the formulation of Equation 3

Also, using the induction hypothesis, we can observe that the right hand side of 3 is increasing in αj and decreasing in βj because all terms there are increasing in αj and decreasing in βj.

This lemma enables us to prove that algorithm 3 is deciding a valid upper bound on the probability correctly guessing c examples out of c guesses. To prove this, assume that the probability of such event is equal to τ , Note that this means αc + βc = c

mτ . Also note that

αc βc c c c (6)

therefore, we have

m τ . Therefore, using Lemma A.1 we have α0 r0,c( c

m τ ) and β0 h0,c( c

Now we prove a lemma about the function si,j(τ) = hi,j( c

m τ) + ri,j( c

Lemma A.5. the function si,j(τ) = hi,j( c

m τ) + ri,j( c

m τ) is increasing in τ for i < j c.

Proof. To prove this, we show that for all i < j c both ri,j( c

m τ) and hi,j( c

m τ) are increasing in τ. We prove this by induction on j i. For j i = 1, we have

m τ) = (k 1) f 1( c

We know that f 1 is increasing, therefore hi,i+1( c

m τ) is increasing in τ as well. For ri,i+1 we have

mτ + i c i(hi,i+1( c

Auditing f-Differential Privacy in One Run

m τ) = c(c i) i(c c)

m(c i) τ + i c ihi,i+1( c

m(c i)τ + i c ihi,i+1( c

We already proved that hi,i+1( c

m τ) is increasing in τ. We also have (c i)c

m(c i) > 0, since i < c. Therefore

is increasing in τ. So the base of induction is proved. Now we focus on j i > 1. For hi,j we have

m τ) = (k 1) f 1(ri+1,j( c

By the induction hypothesis, we know that ri+1,j( c

m τ) is increasing in τ, and we know that f 1 is increasing, therefore, hi,j( c

m τ) is increasing in τ.

For ri,j, note that we rewrite it as follows

ri,j(α, β) = α j c j β +

z=i λz hz,j(α, β)

where λz = ( z+1 c z 1 z c z) 0. Therefore, we have

m τ) = τ( c

z=i λz hz,j( c

= τ c (c j)

z=i λz hz,j( c

Now we can verify that all terms in this equation are increasing in τ, following the induction hypothesis and the fact that λz > 0 and also j c.

Now using this Lemma, we finish the proof. Note that we have α0 + β0 = c

So assuming that τ τ, then we have

m = α0 + β0 s0,c(τ ) s0,c(τ).

The last step of algorithm checks if s0,c c

m and it concludes that τ τ if that s the case, because s0,c is increasing in τ. This means that the probability of having more than c guesses cannot be more than τ.

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. In 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.

Auditing f-Differential Privacy in One Run

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 at δ = 10 5.

Effect of number of guesses In Figures 6 9, we compare the theoretical upper bound, our lower bound, and the lower bound of Steinke et al. with varying number of guesses. In total, we have m = 107 canaries. The number of correct guesses is 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 ϵ. As we can see, both our and Steinke et al. s auditing procedure achieve the best auditing performance for small number of guesses. This shows the importance of abstention in auditing.

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 of correct guesses fluctuates, which is influenced by how many guesses we allow the adversary to make. To explain further, consider a random variable representing the ratio of correct guesses (c) to total guesses (c ). If we reduce the number of guesses, the variance of this ratio tends to decrease because the ratio approaches 1 (the adversary can make more correct guesses when we decrease c ). Conversely, if we increase the number of guesses, the variance can also decrease because having more guesses generally leads to a more stable average, owing to the law of large numbers. This balance makes the number of guesses a crucial factor in optimizing for the best estimate of empirical privacy.

Varying δ and confidence levels: We also examine the effect of δ on the obtained empirical ϵ. We fix the number of canaries to 105 and the number of guesses to 1, 500 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 δ and the confidence level to observe how they affect the results. Figures 10 and 11 shows the bound of (Steinke et al., 2023) and our bound, respectively. Note that our lower bounds represent the true behavior of δ independent of the confidence level, in contrast to 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 of shopping records Purchase (Shokri et al., 2017). We replicate the same setup in (Zarifzadeh et al., 2023), on a non-private MLP model trained on 25000 samples for 50 epochs. We outperform Steinke et al. method for all numbers of guesses

Auditing f-Differential Privacy in One Run

Figure 6. Effect of number of guesses (Gaussian mechanism with standard deviation 1.0). Empirical ϵ is reported at δ = 10 5.

Figure 7. Effect of number of guesses (Gaussian mechanism with standard deviation 2.0). Empirical ϵ is reported at δ = 10 5.

Figure 8. Effect of number of guesses (Gaussian mechanism with standard deviation 4.0). Empirical ϵ is reported at δ = 10 5.

Figure 9. Effect of number of guesses (Gaussian mechanism with standard deviation 0.5). Empirical ϵ is reported at δ = 10 5.

D. Experimental details

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 5.

Idealized setting: In the idealized setting, we work with a 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 is when we have a Gaussian mechanism that is used to calculate the sum of vectors. In this setting, each canary represents a unit vector that is orthogonal to 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 on these likelihoods. For the setting that the adversary has more than 2 guesses (k > 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 4 shows how we calculate the number of correct guesses in the idealized setting.

Auditing f-Differential Privacy in One Run

Figure 10. Idealized setting for different values of δ and confidence levels for bounds of (Steinke et al., 2023).

Figure 11. Idealized setting for different values of δ and confidence levels for our bounds.

Auditing f-Differential Privacy in One Run

Algorithm 4 Simulate the Number of Correct Guesses import numpy as np from scipy.special import softmax from numpy.random import normal, binomial def idealized_setting(target_noise, n_guesses, n_canaries, k): n_correct_vec = [] if k==2:

for _ in range(100): s_vector = binomial(1, 0.5, size=n_canaries) * 2 - 1 noise = normal(0, 2*target_noise, n_canaries)

noisy_s = s_vector + noise

sorted_noisy_s = np.sort(noisy_s)

threshold_c = sorted_noisy_s[-int(n_guesses)//2-1] n_correct = np.ceil(n_guesses*(s_vector[noisy_s > threshold_c] ==

1).mean()) ,

n_correct_vec.append(n_correct) else:

for _ in range(100): s_recon_vec = np.random.randint(0, k, n_canaries)

s_vec_recn_ohe = np.eye(k)[s_recon_vec] s_recon_noisy_vec_ohe = s_vec_recn_ohe + normal(0, np.sqrt(2)*target_noise, s_vec_recn_ohe.shape) ,

idx_max = np.argmax(s_recon_noisy_vec_ohe, axis=1)

buckets = softmax(s_recon_noisy_vec_ohe/(2*target_noise**2), axis=1)[np.arange(s_recon_noisy_vec_ohe.shape[0]), idx_max] , sorted_buckets = np.sort(buckets) bucket_c_thr = sorted_buckets[-int(n_guesses)]

n_correct_rec = np.ceil(

n_guesses*(s_recon_vec[buckets > bucket_c_thr] ==

s_recon_noisy_vec_ohe[buckets > bucket_c_thr].argmax(1)).mean()

, ) n_correct_vec.append(n_correct_rec)

return int(np.array(n_correct_vec).mean(0))

Auditing f-Differential Privacy in One Run

Auditing code

Here we include the code to compute empirical epsilon.

from scipy.stats import norm import numpy as np

# Calculate h and r recursively (no abstentions) def rh(inverse_blow_up_function, alpha, beta, j, m, k=2):

# Initialize lists to store h and r values h = [0 for _ in range(j + 1)] r = [0 for _ in range(j + 1)] # Set initial values for h and r h[j] = beta r[j] = alpha # Iterate from j-1 to 0 for i in range(j - 1, -1, -1):

# Calculate h[i] using the maximum of h[i+1] and a scaled inverse blow-up function , h[i] = max(h[i + 1], (k - 1) * inverse_blow_up_function(r[i + 1])) # Update r[i] based on the difference between h[i] and h[i+1] r[i] = r[i + 1] + (i / (m - i)) * (h[i] - h[i + 1]) # Return the lists of h and r values return (r, h)

# Audit function without abstention def audit_rh(inverse_blow_up_function, m, c, threshold=0.05, k=2):

# Calculate alpha and beta values alpha = threshold * c / m beta = threshold * (m - c) / m # Call the rh function to get the lists of h and r values r, h = rh(inverse_blow_up_function, 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 h and r recursively (with abstentions) def rh_with_cap(inverse_blow_up_function, alpha, beta, j, m,c_cap, k=2): h=[0 for i in range(j+1)] r=[0 for i in range(j+1)] h[j]= beta r[j]= alpha for i in range(j-1,-1,-1): h[i]=max(h[i+1],(k-1)*inverse_blow_up_function(r[i+1])) r[i]= r[i+1] + (i/(c_cap-i))*(h[i] - h[i+1])

return (r,h)

# Audit function with abstentions def audit_rh_with_cap(inverse_blow_up_function, m, c,c_cap, threshold=0.05, k=2): ,

threshold=threshold*c_cap/m

Auditing f-Differential Privacy in One Run

alpha=(threshold*c/c_cap) beta=threshold*(c_cap-c)/c_cap r,h=rh_with_cap(inverse_blow_up_function, alpha, beta, c, m, c_cap, k)

if r[0]+h[0]>c_cap/m:

return False else:

return True

# Calculate the blow-up function for Gaussian noise def gaussian DP_blow_up_function(noise):

def blow_up_function(x):

# Calculate the threshold value threshold = norm.ppf(x) # Calculate the blown-up threshold value blown_up_threshold = threshold + 1 / noise # Return the CDF of the blown-up threshold value return norm.cdf(blown_up_threshold) return blow_up_function

# Calculate the inverse blow-up function for Gaussian noise def gaussian DP_blow_up_inverse(noise):

def blow_up_inverse_function(x):

# Calculate the threshold value threshold = norm.ppf(x) # Calculate the blown-up threshold value blown_up_threshold = threshold - 1 / noise # Return the CDF of the blown-up threshold value return norm.cdf(blown_up_threshold) return blow_up_inverse_function

# Define a function to calculate delta for Gaussian noise def calculate_delta_gaussian(noise, epsilon):

# Calculate delta using the formula delta = norm.cdf(-epsilon * noise + 1 / (2 * noise)) - np.exp(epsilon) *

norm.cdf(-epsilon * noise - 1 / (2 * noise)) , return delta

# Define a function to calculate epsilon for Gaussian noise def calculate_epsilon_gaussian(noise, delta):

# Set initial bounds for epsilon epsilon_upper = 100 epsilon_lower = 0 # Perform binary search to find epsilon while epsilon_upper - epsilon_lower > 0.001: epsilon_middle = (epsilon_upper + epsilon_lower) / 2 if calculate_delta_gaussian(noise, epsilon_middle) > delta: epsilon_lower = epsilon_middle else: epsilon_upper = epsilon_middle # Return the upper bound of epsilon return epsilon_upper

# Get the empirical epsilon value

Auditing f-Differential Privacy in One Run

def get_gaussian_emp_eps_ours(candidate_noises, inverse_blow_up_functions, m, c, threshold, delta, k=2): ,

# Initialize the empirical privacy index empirical_privacy_index = 0 # Iterate through candidate noises until the privacy condition fails while audit_rh(inverse_blow_up_functions[empirical_privacy_index], m, c, threshold=0.05, k=k): ,

empirical_privacy_index += 1 # Get the empirical noise and calculate the empirical epsilon empirical_noise = candidate_noises[empirical_privacy_index] empirical_eps = calculate_epsilon_gaussian(empirical_noise, delta=delta) # Return the empirical epsilon return empirical_eps

# Set target noise and generate candidate noises target_noise = 0.6

candidate_noises=[target_noise+ i*0.01 for i in range(1000)] inverse_blow_up_functions=[gaussian DP_blow_up_inverse(noise) for noise in

candidate_noises] ,