Privacy Auditing with One (1) Training Run
Authors: Thomas Steinke
Milad Nasr
Matthew Jagielski
Venue: NeurIPS 2023 oral (2023)
Keywords: Differential privacy
membership inference attacks
privacy auditing
TL;DR: We show how to compute lower bounds on the privacy parameters of an algorithm with only one run of that algorithm.

Abstract: We propose a scheme for auditing differentially private machine learning systems with a single training run. This exploits the parallelism of being able to add or remove multiple training examples independently. We analyze this using the connection between differential privacy and statistical generalization, which avoids the cost of group privacy. Our auditing scheme requires minimal assumptions about the algorithm and can be applied in the black-box or white-box setting. We demonstrate the effectiveness of our framework by applying it to DP-SGD, where we can achieve meaningful empirical privacy lower bounds by training only one model. In contrast, standard methods would require training hundreds of models.

Privacy Auditing with One (1) Training Run
Thomas Steinke" Google Deep steinke@roogle.com com
Milad Nasr" Google DeepMind erxzr@google com
Matthew Jagielski" Google DeepMind jagielski@googlee
Abstract
We propose a scheme for auditing differentially private machine learning systems with single training run. This exploits the parallelism of being able to add remove multiple training examples independently. We analyze this using the con- nection between differential privacy and statistical generalization, which avoids the cost of group privacy. Our auditing scheme requires minimal assumptions about the algorithm and can be applied in the black-box or white-bos setting, We demonstrate the effectiveness of our framework by applying it to DP-SGD, where we can achieve meaningful empirical privacy lower bounds by training only one model. In contrast, standard methods would require training hundreds of models.
Introduction
Differential privacy (DP) [DMNS06) provides a quantifiable privacy guarantee by ensuring that no person's data significantly affects the probability of any outcome. Formally, randomized algorithm M satisfies (e, 8D-DP if, for any pair of inputs xr differing only by the addition or removal of one person's 's data and any measurable S, we have
([M(2) e
E S
(1)
DP algorithm is accompanied by mathematical proof giving an upper bound on the privacy parameters E and d. In contrast, privacy audil provides an empirical lower bound the privacy parameters. Privacy audits allow us to assess the tightness of the mathematical analysis (JUO20; NHSBTJCT23] or, if the lower and upper bounds contradictory, detect errors in the analysis or in the algorithm's 's implementation [DWWZK 8; BGDCTVI6, 18; TTSSJC22].
Typically, privacy audits obtain lower bound on the privacy parameters directly from the DP def- inition (1). That is, we construct a pair of inputs 2, x' and a of outcomes S and we estimate the probabilities P (x) E S] and P [Mx') E S). However, estimating these probabilities requires running M hundreds of times. This approach privacy auditing computationally expensive, which raises the question Can perform privacy auditing using a single run of the algorithm M?
1.1 Our Contributions
The DP definition (1) considers adding or removing single person's 's data to from the dataset. We consider multiple people's s data and the dataset independently includes or excludes each person's data point. Our analysis exploits the parallelism of multiple independent data points in single run of the algorithm in lieu of multiple independent runs. This approach is commonly used an unproven heuristic in prior work [MEMPST21: ZBWTSRPNK22].
Our approach:
Our auditing procedure operates as follows. We identify m data points (i.e., training examples or "canaries"") to either include exclude and flip m independent unbiased coins to decide which of them to include or exclude. We then run the algorithm on the randomly selected dataset. Based
Reverse alphabetical author order. Full version: https://aaadv..r/abb//////
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

on the output of the algorithm, the auditor "guesses" whether or not each data point was included or excluded (or it can abstain from guessing for some data points). We obtain a lower bound on the privacy parameters from the fraction of guesses that were correct.
Intuitively, if the algorithm is (c, D)-DP, then the auditor can correctly guess each inclusion/exclusion
coin flip with probability S _ T5.T. That is, the highest possible accuracy is attained by random- ized response [War65]. Thus DP implies high-probability upper bound the fraction of correct guesses and, conversely, the fraction of correct guesses implies a high-probability lower bound on the privacy parameters.
Naively, analyzing the addition or removal of multiple data elements would rely on group privacy: but this does not exploit the fact that the data items were included excluded independently. Instead, we leverage the connection between DP and generalization [DFHPRR 15b; DFHPRR BNSSSU16; RRST16; JLNRSMS19; SZ20]. Our main theoretical contribution is an improved analysis of this connection that is tailored to yield nearly tight bounds in our setting.
Our analysis:
Informally, if we run a DP algorithm on i.i.d. samples from some distribution, then, conditioned on the output of the algorithm, the samples are still "close" to being i.i.d. samples from that distribution. There is some technicality in making this precise, but, roughly speaking, we show that including or excluding m data points independently for one run essentially as good as having m independent runs (as long as 8 is small).
As an application of our new auditing framework, we audit DP-SGD training on WideResNet model, trained on the CIFARIO dataset across multiple configurations. Our approach successfully achieves an empirical lower bound of æ 2 1.8, compared to a theoretical upper bound of = S 4 in the white-bos box setting. The m examples we insert for auditing (known in the literature as "canaries") do not significantly impact the accuracy of the final model (less than 5% decrease in accuracy) and our procedure only requires single end-to-end training run. Such results were previously unattainable the setting where only one model could be trained.
Our results:
2 Our Auditing Procedure
Algorithm 1 Auditor with One Training Run
Data: x E X" consisting of m auditing examples (a.k.a, canaries) " Fm ,7m and n m non-auditing examples Zm+1. ... In.
2: Parameters: Algorithm to audit A, number of examples to randomize m, number of positive k4 and negative k_ guesses.
3: For i E [m]], sample S, E (11,+1} uniformly and independently. Set S = for all i
[n] \ [m].
4: Partition x into TIN E aM and zoUT E X according to S, where nIn + noUT = n. Namely,
if S, = 1. then 2; is in TIN; and, if S, -1, then z, is in ZoUT-
5: Run A on input FIN with appropriate parameters, outputting w.
6: Compute the vector of scores Y = (ScORE(I;; w) : E [m]) RR
7: Sort the scores Y. Let T E {-1,0, -11 be +1 for the largest k4 scores and -1 for the
smallest k_ scores. (Le.. T E {-1,0, +1}" maximizes Σ T, Y, subject to Σ [T]
t2 T. = h4 k_.) k4 + h_ and E.T
8: Return: S E [-1,--1 +13" indicating the true selection and the guesses T 011""
We present our auditing procedure in Algorithm 1. We independently include each of the first m examples with 50% probability and exclude it otherwise. ? When applied to DP-SGD is applicable to both "white-box" auditing, where the adversary can access to all intermediate values of the model weights (as in the federated learning setting), and "black-box" auditing, where the adversary only sees the final model weights (or can only query the final model, as in the centralized setting). In both cases simply compute "score" for each example and "guess" whether the example is included or excluded based on these scores. Specifically, we guess that the examples with the k4 highest scores are included and the examples with the k_ lowest scores are excluded,
approach
We consider the add/remove notion of DP, so changing one S, results in neighbouring inputs ZIN. Our methods readily extend to the replacement notion of DP; see the full version.

---

and we abstain from guessing for the remaining m - h4 - k- auditing examples; the setting of these parameters will depend on the application.
Note that we only randomize the first m examples T1," J.m (which we refer to as "auditing examples" "canaries"); the last m examples 3m+1,"' Fn always included and, thus, we do not make any guesses about them. To get the strongest auditing results we would set m n, but we usually want to set m < n. For example, computing the score of all n examples may be computationally prohibitive, so we only compute the scores of m examples. We may wish to artificially construct m examples to be easy to identify (i.e., canaries), but also include n m "real" examples to ensure that A still produces a useful model. (I.e., having more training examples improves the performance of the model.)
The score function is arbitrary and will depend on the application. For black-box auditing, we use the loss of the final model auditing, SCORE(æ,, w) = Σx (wo-1 w wos--oosssw''' of updates with the (clipped) gradients of the loss on the example.
the example I; i.e., SCORF( w)) - (os v.). For white-box
is the sum of the inner products
Intuitively, the vector of scores should be correlated with the true selection S, but too strong a correlation would violate DP. This is the basis of our audit. Specifically, the auditor computes I from Y which "guess" at S. By the postprocessing property DP, the guesses I' are a differentially private function of the true S, which means that they cannot be too accurate.
Why abstain from guessing? The guesses are binary (T; 1 for IN, T; -1 for OUT). Abstain- ing (7; 0) allows us to capture uncertainty. That is, on some examples we will not be sure whether they are IN or OUT. By abstaining on these uncertain examples, we can ensure higher accuracy for the remaining guesses. This yields better auditing results in practice.
3 Theoretical Analysis
To obtain lower bound on the DP parameters we show that DP implies high-probabilltyy upper bound on the number of correct guesses W == E." ma S.} of our auditing procedure (Algorithm 1). Note that max(0, T; S is simply 1 if the guess was correct - i.e,, T; = S and 0 otherwise. The observed value of W then yields a high-probability lower bound on the DP parameters. To be more precise, we have the following guarantee.
Theorem 3.1 (Main Result), Let (S, E [-1,+11]
{ { 1-1, +1]" TM be the output of Algorithm
I. Assume the algorithu to audit A satisfies (E. Let r == K4 + k- = ||T be the number of guesses. Then, for all R,
m
PP
Σ
max (0, Tj (..S.) 2 v
S
[ 2 r) +m.m- a,
(2)
W Vinomiaaal
where
2 i W Binomian (r.
a
max iE m
v W 2
(3)
If ignore for the moment, Theorem 3.1 says that the number of correct guesses is stochasti- cally dominated by Binomial (r) where r r= k4 + k is the total number of guesses. This binomial distribution is precisely the distribution of correct guesses we would get if was obtained by independently performing (e, 0)-DP randomized response on bits of S. In other words, the theorem says that (s, DD randomized response is exactly the worst-case algorithm in terms of the number of correct guesses. In particular, this means the theorem is tight (when d = 0).
The binomial distribution is well-concentrated. In particular, for all B E (0, 1), we have
W 2 e e +1 + V2 r- log (1/()
P
I 3.
(4)
W Binomia (1
There is an additional O6)) term in the guarantee (2). The exact expression (3) is somewhat complex. always & 2nd, since a S 2, but it is much smaller than this for reasonable parameter values. In particular, for as in Equation 4 with B < 1/7". we have O(1/r).
3

---

Theorem 3.1 gives us a hypothesis test: If A is (E, 6)-DP, then the number of correct guesses W is S re + ((rr) with high probability. Thus, if the observed number of correct guesses is larger than this, we can reject the hypothesis that A satisfies (s, DDDP. We can convert this hypothesis test into a confidence interval (i.e., a lower bound on E) by finding the largest E that we can reject at a desired level of confidence.
ef41
Proof Theorem 3.1: Due to space limitations, the proof is deferred to the full version. But we outline the main ideas: First note that 5 E {-1, +1 is uniform and T is a DP function of S. Con- sider the distribution the conditional distribution using Bayes' law that each guess has probability S c= of being correct. Furthermore, this holds even if we condi- tion on the other guesses, which allows us to inductively prove that the number of correct guesses
is pure (e, 0)-D,, then we can easily analyze conditioned on [DFHPRRISaL RRST16; JLNRSMS19 to conclude
stochastically dominated by Binomial (r, of Handling approximate DP (6 > 0) introduces additional complexity some outputs T are "bad" in the sense that the conditional distribution of Sş could be arbitrary. Fortunately, such bad outputs are rare [KS14]. What we can show is that the num-
ber of correct guesses stochastically dominated by W FT).. where W Binomial e
as before and F(T) {0, not know the exact distribution of (T)). but we do know E [F(T)] ] < 2mno, which suffices to prove our result. Equation 3 comes from looking for the worst-case FTT); essentially the worst is 2mm/ for some E [m]]
... 1,...
m indicates how many of these bad events happened. We do
P (F((T) = = 2mó6i and (FF(T) = 0]
5
3.5
6-0
95% g Lower Bound
5 10
95% Lower Bound
3.0
6 0.001
5 10
0.01
Ideal
Ideal
50
100
Ideal
fraction correct guesses
Correct Guesses (100 total, 0 abstentions)
Figure I: Lower bound on the privacy pa- rameter given by Theorem 3.1 with 95% confidence as the number of correct guesses changes. The total number of examples and guesses is 100. For comparison, we plot the ideal that gives 100 T correct guesses.
Figure 2:
Lower bound on the privacy pa- rameter & given by Theorem 3.1 with 95% confidence as the number of correct guesses changes. The total number of examples and guesses is 1000 (with no abstentions), Here we plot the ideal e on the horizontal axis, so that the number of correct guesses is 1000 25
Our theoretical analysis also gives novel implications for generalization from DP, improving on the results of Jung, Ligett, Neel, Roth, MalvjjiMalvajjrrdi, and Shenfeld [JLNRSMS19] In addition, we obtain bounds on the mutual information ((S; M (S)) < 3 g22m log ôm log where S E {0, 1)"h is uniformly random and M (0.1)a + y' satisfies (e, 8)-DP, which improves on the results of Steinke and Zakynthinou [SZ20]. See the full version for more details.
Experiments
Experiment Setup Our contributions are focused improved analysis of existing privacy at- tack, and are therefore orthogonal to the design of an attack. As a result, we rely on the experimental setup of the recent auditing procedure of Nasr, Hayes, Steinke, Balle, Tramer, Jagielski, Carlini, and Terzis [NHSBTJCT23].
We run DP-SGD on the CIFAR-10 dataset with Wide ResNet (WRN-16) [ZK 16), following the experimental setup of Nasr al. [NHSBTICT23]. Our experiments reach 76% test accuracy at (a 8, 10-3)-DP, which is comparable with the state-of-the-ar [DBHSB22]. Unless specified

---

Theoretical
Theoretical
Empirical Epsilon
m=5000
Empirical Epsilon
5
m=
4 m=1000
n - = 10
4
m=100
10
3
m=50
3
2 100
2
0
Theoretical Epsilon
Theoretical Epsilon
Figure 3: Effect of the number of auditing ex- amples (m) the white-box setting. By in- creasing the number of the auditing examples we are able to achieve tighter empirical lower bounds.
Figure 4: Effect of the number of additional ex- amples (n - m) in the white-box setting. Im- portantly, adding additional examples does not impact the auditing results in the white-box set- ting.
otherwise, all lower bounds are presented with 95% confidence. Following prior work, we refer to the setting where the adversary has access to all intermediate steps as "white-box" and when the adversary can only see the last iteration "black-box." " We experiment with both settings.
Algorithm summarizes our approach for auditing DP-SGD. The results are converted into lower bounds on the privacy parameters using Theorem 3.1.
We also experiment with both the gradient and input attacks proposed by Nasr et al. [NHSBTJCT23], In particular, for the gradient attack we use the strongest attack they proposed the "Dirac canary" approach which sets all gradients to zero except at a single random index. In our setting where make
need create multiple auditing examples (canaries) experiments do not have any repetitions. To compute the score for gradient space attacks, we use the dot product between the gradient update and auditing gradient. When auditing in input space, we leverage two different types of injected examples as:
the indices selected in our
1. Mislabeled example: We select random subset of the and randomly relabel them (ensuring the new label is not the same as the original label).
In-distribution example: We select random subset of the test set.
For input space audits, we use the loss of the input example as the score. In our experiments report the attack with the highest lower bound.
In our experiments, we evaluate different values of k4 and k_ and report the best auditing results. Since changing the number of guesses r h4 + versus number of abstentions m-r is potentially testing multiple hypothesis on the same data, we should reduce the reported confidence value of our results. However, common practice
simply ignore this minor issue [ZBTTSRPNK22; MSS22].
Fortunately, our main theorem can be extended to account for the dynamic choice of the number of guesses (see Corollary 5.8 in the full version).
4.1 Gradient Space attacks
We start with the strongest attack: We assume white-box access - i.c., the auditor sees all interme- diate iterates of DP-SGD (which is a reasonable assumption in the federated learning setting) and that the auditor can insert examples with arbitrary gradients into the training procedure. First, we evaluate the effect of the number of the auditing example on the tightness. Figure demonstrates that as the number of examples increases, the auditing becomes tighter. However, the impact of the additional examples eventually diminishes. Intriguingly, adding more non-auditing training exam- ples (resulting in larger compared to m) does not seem to influence the tightness of the auditing, as depicted in Figure This can be primarily due to the fact that gradient attacks proposed in prior studies can generate hear-worst-cal datasets, irrespective of the presence of other data points.
5

---

8
Theoretical
Theoretical
Emprical Epsilon
One Step
Empirical Epsilon
7
Empirical
100 Steps
6
4
500 Steps
3
1000 Steps
4-
2-
3
2
1-
1
3
Theoretical Epsilon
Theoretical Epsilon
Figure 5: Effect of number of iterations in the white-box setting. Increasing the number of the steps (while keeping the same overall privacy by increasing the added noise) will not effect the auditing results.
Figure 6: Auditing CIFARIO SoTA in white- box setting using gradient attacks. Our audit- ing framework can achieve meaningful empiri- cal privacy lower bounds for SoTA models.
Another parameter that might affect the auditing results the number iterations the DP- SGD algorithm. As shown in Figure we compare the extreme setting of having one iteration to multiple iterations and we do not observe any significant difference in the auditing when auditing for the equivalent privacy guarantees (by increasing the noise). The results confirm the tightness of composition and that the number of iterations does not have significant effect on auditing in white-box setting.
Now we directly use the parameters used in the training CIFARIO models. Figure 6 summarizes results for the CIFARIO models. We used m 5000 and all of the training dataset from CIFARIO (n = 50, 000) for the attack. We were able to achieve 76% accuracy for 8 8 (8 10-3 compared to 78% when not auditing). We are able achieve empirical lower bound of 0.7, 1.2, 1.8, 3.5 for theoretical epsilon of 1, 4, respectively. While our results are not as tight as the prior works, we only require single run of training which is not possible using the existing techniques. In the era of exponentially expanding machine learning models, the computational and financial costs of training these colossal architectures even once significant. Expecting any individual or entity to shoulder the burden of training such models thousands of times for the sake auditing or experimental purposes is both unrealistic and economically infeasible. Our method offers unique advantage by facilitating the auditing of these models, allowing for an estimation privacy leakage in a white-box setting without significantly affecting performance.
4.2 Input Space Attacks
Now we evaluate the effect of input space attacks the black-box setting. In this attack, the auditor only insert actual images into the training procedure and cannot control any of the aspects of the training. Then, the adversary can observe the final model as mentioned in Algorithm This the weakest attack setting.
For simplicity we start with the setting where m = nı; other words, all of the examples used to train the model are randomly included or excluded and can be used for auditing. Figure 7 illustrates the result this setting. As we see from the figure, unlike the white-box attack we do not observe a monotonic relationship between the number of auditing examples and the tightness of the auditing. Intuitively, when the number auditing examples are low then we do not have enough observations to have high confidence lower bounds for epsilon. On the other hand, when the number of auditing examples are high, the model does not have enough capacity to "memorize" all of the auditing examples which reduces the tightness of the auditing. However, this can be improved by designing better black-box box attacks which we reiterate in the next section.
We also evaluate the effect of adding additional training data to the auditing in Figure 8. We see that adding superfluous training data significantly reduces the effectiveness auditing. The observed reduction in auditing effectiveness with the addition of more training data could be attributed to

---

8
Theoretical m 500
Theoretical
Empirical Epsilon
7
Empirical Epsilon
7
m =
6
6
m 1000
1000
5
10000
5
10000
4
4
3
3
2
2
1
1
0
3
5
2
Theoretical Epsilon
Theoretical Epsilon
Figure 7: Effect of the number of auditing ex- amples (m) in the black-box setting. Black-box auditing is very sensitive to the number of au- diting examples.
Figure 8: Effect of the number of additional ex- ample on auditing (n - m) the black-box set- ting. By increasing the number of additional examples, the auditing results get significantly looser.
several factors. One interpretation could be that the theoretical privacy analysis in black-box setting tends to be considerably more loose when the adversary is constrained to this setting. This could potentially result in overestimation of the privacy bounds. Conversely, it also plausible that the results are due to the weak black-box attacks and can be improved in the future.
5 Related Work
The goal of privacy auditing is to empirically estimate the privacy provided by algorithm, typ- ically to accompany a formal privacy guarantee. Early work on auditing has often been moti- vated by trying to identify bugs in the implementations of differentially private data analysis al- gorithms [DWWZK18; BGDCTV18).
Techniques for auditing differentially private machine learning typically rely on conducting some form of membership inference attack [SSSS17];² these attacks are designed detect the presence or absence of an individual example in the training set. Essentially, membership inference attack which achieves some true positive rate (TPR) and false positive rate (FPR) gives lower bound on the privacy parameter & 2 log, (TPR/FPR) (after ensuring statistical validity of the TPR and FPR estimates).
Jayaraman and Evans [JE19] use standard membership inference attacks to evaluate different privacy analysis algorithms. Jagielski, Ullman, and Oprea [JUO20] consider inferring membership worst- case "poisoning" examples to conduct stronger membership inference attacks and understand the tightness of privacy analysis. Nasr, Song. Thakurta, Papernot, and Carlini [NSTPC21] measure the tightness of privacy analysis under a variety of threat models, including showing that the DP-SGD analysis tight the threat model assumed by the standard DP-SGD analysis.
Improvements to auditing have been made in a variety of directions. For example, Nasr, Hayes, Steinke, Balle, Tramèr, Jagielski, Carlini, and Terzis [NHSBTJCT23] and Maddock. Sablayrolles, and Stock [MSS22] take advantage of the iterative nature of DP-SGD, auditing individual steps to understand privacy of the end-to-end algorithm. Improvements have also been made the basic statistical techniques for estimating the & parameter, for example by using Log-Katz confidence intervals [LMF222RRT22),, Bayesian techniques [ZBWTSRPNK22), or auditing algorithms in different privacy definitions [NHSBTJCT23].
Andrew, Kairouz, Oh, Oprea, McMahan, and Suriyakumar [AKOOMS23] build the observation that, when performing membership inference, analyzing the case where the data is not included does
'Shokri, Stronati, Song, and Shmatikov [SSSS17] coined the term "membership inference attack" and were the first to apply such attacks to machine learning systems. However, similar attacks were developed for applications genetic data [HSRDTMPSNCOU. SOJH09; DSSUV15] and in cryptography [BS98; Tar08j.

---

not require re-running the algorithm; instead we can sa-saeple the excluded data point; if the data points are i..d. from a nice distribution, this permits closed-form analysis of the excluded case. This gives a method for estimating the privacy parameters of an algorithm in single run, but it does not guarantee that the estimate is either a lower or upper bound. In similar vein, independent and concurrent work by Pillutla, Andrew, Kairouz, McMahan, Oprea, and Oh [PAKMO023] provides a rigorous privacy auditing scheme that re-uses training runs to improve efficiency. Rather than consider a single pair of inputs differing by single example, they consider multiple pairs of neigh- bouring inputs, but these pairs are overlapping in the sense that a single input dataset may appear in multiple pairs. Thus each training run can be re-used to estimate the privacy parameters of multiple pairs simultaneously or, rather, a single lower bound on the privacy parameters is computed over a (random) combination of the pairs. This is significantly more efficient than the naive approach, but still requires more than one run.
A recent heuristic proposed to improve the efficiency of auditing is performing membership in- ference on multiple examples simultaneously. This heuristic was proposed by Malek Esmaeili, Mironov, Prasad, Shilov, and Tramer [MEMPST21], and evaluated more rigorously by Zanella- Béguelin, Wutschitz, Tople, Salem, Rühle, Paverd, Naseri, and Köpf [ZBWTSRPNK22). However, this heuristic is not theoretically justified, as the TPR and FPR estimates are not based on indepen- dent samples. In our work, we provide a proof of the validity of this heuristic. In fact, with this proof, show for the first time that standard membership inference attacks, which attack mul- tiple examples per training run, can be used for auditing analysis; prior work using these attacks must make an independence assumption. As result, auditing can take advantage of progress in the membership inference field [CCNSTT22; WBKBGGG22).
Our theoretical analysis builds on the connection between DP and generalization [DFHPRR 155;;RR15b; DFHPRRI5a: BNSSSU16; RRSTI6; JLNRSMS19; SZ20J. Our approach can be viewed as a con- trapositive to "privacy implies generalization." That is, "failure to generalize implies non-privacy." Our auditing scheme can also be viewed as a "reconstruction attack" [DN03; DSSU17J. That is, the auditor's s guesses T can be viewed reconstruction of the private coins S. And it is known that DP prevents reconstruction [De12]
Discussion
Our main contribution is showing that we can audit the differential privacy guarantees of an algo- rithm with a single run. In contrast, prior methods require hundreds if not thousands of runs, which is computationally prohibitive for all but the simplest algorithms and machine learning mod- els. Our experimental results demonstrate that in practical settings our methods are able to give meaningful lower bounds on the privacy parameter e.
However, while we win on computational efficiency, we lose on tightness of our lower bounds. We now illustrate the limitations of our approach and discuss the extent to which this is inherent, and what lessons we can learn.
But, first, we illustrate that our method can give tight lower bounds. In Figure 9, we consider an idealized setting where the number of guesses changes and the fraction that correct is fixed at e+II for 4 - i..., 98.2% of guesses are correct. This is the maximum expected fraction of correct guesses compatible with (4, D)- In this setting the lower bound on ε does indeed come close to 4. With 10,000 guesses we get e 2 3.87 with 95% confidence.
Note that the lower bound in Figure 9 improves we increase the number of guesses. This is simply accounting for sampling error- - to get a lower bound with 95% confidence, we must underestimate to account for the fact that the number of correct guesses may have been inflated by chance. As get more guesses, the relative size of chance deviations reduces.
Next we consider a different idealized setting one that is arguably more realistic where our method does not give tight lower bounds. Suppose S, E {-1++1} indicates whether example i E [n] is included or excluded. In Figure 10, we consider Gaussian noise addition. That is, we release a sample from (S,,, 4). (In contrast, Figure considers randomized response on S..) A tight analysis of the Gaussian mechanism [8,18, Theorem 8] gives an upper bound of
Limitations:
'The number of correct guesses is rounded down to an integer (which results in the lines being jagged). There abstentions.
8

---

4.0
3.5
3.0
Lawer Bound
Ideal
Upper Bound (Gaussian)
0.5
95% Lower Bound = 10-5)
01
95% Lower Bound
161
10"
10
10
10
10
10a
10"
10
10a
Number Guesses (98% correct)
Number Guesses (out 100000 exa xxamples)
Comparison of upper and lower bounds for idealized setting with varying num- ber of guesses. The fraction of correct guesses is always ef = 0.982 for e = 4.
Figure 9:
Comparison of upper and lower bounds for idealized setting with varying num- ber of guesses. For each example E [m]]. we release S; + E.s where & + _N 4) and S; E {-1, +1} is independently uniformly random and indicates whether the sample is included/excluded. For the upper bound, compute the exact (4.38, 1- guarantee for the Gaussian mechanism. For the lower bound, we plot the bound of Theorem 3.1 with 95% confidence for varying numbers of guesses т. Total of m = 100, 000 randomized exam- ples; guess T; +1 for the largest r/2 scores and T; = for the smallest r/2 scores; we guess T;
Figure 10:
Upper Bound (Gaussian)
99% Lower Bound
95% Lower Bound
75% Lower Bound
10-7
10-0
10
10-1
for the remaining m ex- amples. The number of correct guesses is set to r [S: +1|S, & > d]. where e threshold such that P [S; + Ea > cl 2m
Figure 11:
Same setting as Figure 10 with varying 6 and confidence, but number of guesses fixed to r =1,500 of which 1.429 are correct out of m 100,000 auditing examples.
(4.38, 10 10-5)-DP. Unlike for randomized response, abstentions matter here. We consider 100,000 examples, each of which has a score sampled from (SS,, 4), where S; E {-1. is uniformly random. We pick the largest r/2 scores and guess smallest r/2 scores. We abstain for the remaining 100, 000 examples. If we make more guesses (i.e., increase r), then we start making guesses on examples which are less "in the tails" of each distribution, which provide less signal for the attack, making the attack accuracy go down along with our lower bound. We must trade off between more guesses being less accurate on average and more guesses having smaller relative sampling error.
1. Similarly we guess S, 1 for the
In Figure 10, the highest value of the lower bound is : 2 2.675 for 5 10-5, which is attained by 1439 correct guesses out of 1510. In contrast, the upper bound is e 4.38 for 5 = 10-5 To get matching upper bound of < 2.675 we would need to set 5 0.0039334. In other words, the gap between the upper and lower bounds is a factor of x93x in 8.
Figure 11 considers the same idealized setting Figure 10, but we fix the number of guesses to 1,500 out of 100,000 (of which 1,429 are correct); instead we vary ò and the confidence level.
Are these limitations inherent? Figures 10 & 11 illustrate the limitations of our approach. They also hint at the cause: The number of guesses versus abstentions, the parameter, and the confidence all have a large effect the tightness of our lower bound.
Our theoretical analysis is fairly tight; there little room improve Theorem 3.1. We argue that the inherent problem is mismatch between "realistic" DP algorithms and the "pathological" DP algorithms for which our analysis is nearly tight. This mismatch makes our lower bound much more sensitive to than it "should" be.

---

To be concrete about what we
Algorithm 2 Pathological Algorithm
consider pathological, consider
1: Input: & E [-1,+1jm
M
{-1,0, +1 pm
2: Parameters: E [m]] 8, 2 0. [0, As-
defined by Algorithm This algorithm
sume 0 < mn S r,9.
satisfies (c, 8D- and makes guesses case.
Select U C [m]] with |U] uniformly random.
with m abstentions. In the the expected fraction of correct guesses is
4: Set 72 0 for all i & U.
Sample X Bernoulli(3).
e'+1 This is higher than the average fraction of correct guesses. but if we want confidence - B in our lower bound, we must consider this case, as =1 happens with probability B3.
ms (1- m8
6: if X = 1 then
for E do
8:
Independently sample T; E (-1,+11
with
P 8:] end for
má r3
e1+I
9:
Intuitively, the contribution from the fraction of correct guesses should be negli- gible. However, we see that ō is multiplied by m/rB. That is to say, in the settings we consider, d is multiplied by factor on the order of x or 1000x, which means 8 10 makes a non-negligible contri- bution to the fraction of correct guesses.
10:
else if X 0 then
11:
for E U do
12:
Independently sample T₃ E (-11 with PP T.: s,l e++1
13: end for
14:
end if
15:
Output: T (-1,0,++1)
It is tempting to try to cireumvent this problem by simply setting to be very small. However, as shown in Figure 11, the corresponding upper bound on also increases as ō + 0.
Unfortunately, there is no obvious general way to rule out algorithms that behave like Algorithm 2. The fundamental issue that the privacy losses of the m examples are not independent; nor should expect them to be, but they shouldn' 't be pathologically dependent either.
Directions for further work: Our work highlights several questions for further exploration:
Improved attacks:
Our experimental evaluation uses existing attack methods. Any im- provements to membership inference attacks could be combined with our results to yield improved privacy auditing.
One limitation of our attacks is that some examples may be "harder" than others and the scores we compute do not account for this. When we have many runs, we can account for the hardness of individual examples [CCNSTT22), but in our setting it is not obvious how to do this.
Algorithm-specific analyses: Our methods are generic - they can be applied to essentially any DP algorithm. This is strength, but there is also the possibility that could obtain stronger results by exploiting the structure of specific algorithms.
natural example of view one run of DPD
such structure is the iterative nature of DP-SGD, That is, as the composition of multiple independent DP algorithms which are run sequentially.
Multiple runs & multiple examples: Our method performs auditing by including or ex- cluding multiple examples in single training run, while most prior work performs multiple training runs with single example example included or excluded. Can we get the best of both worlds? If we use multiple examples and multiple runs, we should be able to get tighter results with fewer runs.
Our theoretical analysis tailored the standard definition of differential privacy. But there are other definitions of differential privacy such as Rényi DP. And, particular, many of the upper bounds are stated this language. Hence would make sense for the lower bounds also to be stated in this language.
Other measures of privacy:
Beyond lower bounds: Privacy auditing produces empirical lower bounds on the privacy parameters. In contrast, mathematical analysis produces upper bounds. Both are necessar- ily conservative, which leaves large gap between the upper and lower bounds. A natural question is find some middle ground an estimate which is neither lower nor upper bound, but provides some meaningful estimate of the "true" privacy loss. However, it is unclear what kind of guarantee such an estimate should satisfy, or what interpretation the estimate should permit.
10

---

References
[AKOOMS23]
G. Andrew, P. Kairouz, S. Oh, A. Oprea, H. B. McMahan, and V. Suriyaku- mar. "One-shot Empirical Privacy Estimation for Federated Learning". In: arXiv preprint arXiv:2302.03000 (2023). URL: pettps://arxer org/abs/ /abs/
2302. 03098 (cit. p. 7).
[BGDCTV18]
B. Bichsel. T. Gehr, D. Drachsler-Cohent P. Tsankov, and M. Vechev. "Dp- finder: Finding differential privacy violations by sampling and optimization", In: Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communicaations Security. 2018, pp. 308-524 (cit. on pp. 7).
[BNSSSU16]
R. Bassily, K. Nissim, A. Smith, T. Steinke, U. Stemmer, and J. Ullman. "Al- gorithmic stability for adaptive data analysis". . In: Proceedings of the forty- eighth annual ACM symposium
Theory of Computing. 2016, pp. 1046- 1059. URL: https: / http//avv....aabaaaaae.. httgg/ab//aaa 1111. 02513 (cit. on pp. 2, 8).
[BS98]
D. Boneh and J. Shaw. "Collusion-secure fingerprinting for digital data". In: IEEE Transactions on Information Theory 44.5 (1998), pp. 1897-1905 (cit. on p. 7).
[BW18]
B. Balle and Y.-X. Wang. "Improving the gaussian mechanism for differen- tial privacy: Analytical calibration and optimal denoising". In: International Conference Machine Learning. PMLR. 2018, pp. 394-403, URL: https: //arxiv.. perxiv.org// org/ abs/ 1805. 06530 (cit. on p. 8).
[CCNSTT22]
N. Carlini, S. Chien, M. Nasr, S. Song, A. Terzis, and F. Tramer. "Mem- bership inference attacks from first principles". In: 2022 IEEE Symposium on Security and Privacy (SP). IEEE. 2022, pp. 1897-1914. URL: https
// //arxiv..oo orgo abs/ 2212. 03570 (cit. on pp. 8, 10).
[DBHSB22]
Smith, and B. Balle. "Unlocking high- accuracy differentially private image classification through scale". In: arXiv preprint arXiv:2204. 13650 (2022) (cit. on p. 4).
De, L.. Berrada, J. Hayes,
[De12]
A. De. "Lower bounds in differential privacy". In: Theory of Cryptogra- phy: 9th Theory of Cryptography Conference, TCC 2012, Taormina, Sicily, Italy, March 19-21, 2012, Proceedings 9. Springer. 2012, pp. 321-338, URL: https:/ /ttps///axiv..ee org/ aa/aab///11/ 1111 2183 (cit. on p. 8).
[DFHPRRI 55]
C. Dwork, V. Feldman, M. Hardt, T. Pitassi, O. Reingold, and A. Roth. "Gen- eralization in adaptive data analysis and holdout reuse". In: Advances in Neu- ral Information Prucessing Systems 28 (2015). URL: httph:tt/////ttt http:://axxvvvoo/o abs/ abs/1506 150660262999... (cit. pp. 2, 4, 8).
[DFHPRR155] 15b]
C. Dwork, V. Feldman, M. Hardt, T. Pitassi, O. Reingold, and A. L. Roth. "Preserving statistical validity in adaptive data analysis". In: Proceedings of the forty-seventh annual ACM symposium on Theory of computing. 2015, (cit. on pp. 2,
pp. 117-126. URL: https: aaxiv.v org/ hatg//ba//// 0als/14: 1411. 2664
8).
[DMNS06]
C. Dwork, F. McSherry, K. Nissim, and A. Smith. "Calibrating noise to sen- sitivity in private data analysis". In: Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3. Springer. 2006, pp. 265-284, URL: https //ww. /Tw0/20066//7770226/766666222222
iacr. org/
pdf (cit. on p. 1).
[DN03]
I. Dinur and K. Nissim. "Revealing information while preserving privacy". In: Proceedings of the twenty-second ACM SIGMOD-SIGACT--IIC SIGACT-SIGART sym- posium on Principles of database systems. 2003, pp. 202-210 (cit. on p. 8).
[DSSU17]
C. Dwork, A. Smith, T. Steinke, and J. Ullman. "Exposed! survey of attacks on private data". In: Annual Review of Statistics and Its Application (2017). pp. 61-84. URT.: https doi. org/ 10. 1146/ annurev -tteev-sstttiissss 060116- 0046--05423 (cit. on p. 8). C. Dwork, A. Smith, T. Steinke, J. Ullman, and S. Vadhan. "Robust traceabil- ity from trace amounts". In: 2015 IEEE 56th Annual Symposium on Founda- tions of Computer Science. IEEE, 2015, pp. 650-669 (cit. on 7).
3146/anuree/
[DSSUVI5]
11

---

[DWWZKING
Z. Ding, Y. Wang. G. Wang. D. Zhang, and D. Kifer. "Detecting violations of differential privacy". In: Proceedings of the 2018 ACM SIGSAC Confer- ence Computer and Communications Security. 2018, pp. 475-489 (cit. on pp. 7)
[HSRDTMPSNCO8]
N. Homer, S. Szelinger, M. Redman, D. Duggan, W. Tembe, J. Muehling, J. V. Pearson, D. A. Stephan, S. F. Nelson, and D. W. Craig. "Resolving indi- viduals contributing trace amounts of DNA to highly complex mixtures using high-density SNP genotyping microarrays". In: PLoS genetics 4.8 (2008), e1000167 (cit. on p. 7).
[JE19]
B. Jayaraman and D. Evans. "Evaluating differentially private machine learn- ing practice", In: USENIX Security Symposium. 2019 (cit. on p. 7).
[ 19]
C. Jung, K. Ligett, S. Neel, A. Roth, S. -aalvii- and M. Shen- feld. "A new analysis of differential privacy's generalization guarantees", In: arXiv preprint arXiv: (a0i:::/990003777. (2019). URL: https:://aartt /ttp///xxvvvvvv////v////./aa.ava www.aaawwi.....aaaaeeeeeae org/oboa /bs/ 1909. 03577 (cit. pp. 2, 4, 8).
[JUO20]
M. Jagielski, J. Ullman, and A. Oprea. "Auditing differentially private ma- chine learningg How private is private sgd?" In: Advances in Neural Infor- mation Processing Systems 33 (2020). pp. 22205-22216 (cit. on pp. 7). P. Kasiviswanathan and A. Smith. "On the semanties'
[KS14]
differential pri- vacy: A bayesian formulation". In: Journal of Privacy and Confidentiality 6.1 (2014). URL: https: /arxiv.vvv. org/ htg//bb///e wabs/003. 3946 (cit. on p. 4).
[LMFLZWRFT22]
F. Lu, J. Munoz, M. Fuchs, T. LeBlond, E. Zaresky-Wiil Williams, E. Raff, F. Ferraro, and B. Testa. "A General Framework for Auditing Differentially Private Machine Learning". . In: arXiv preprint arXiv:22 2tdiv:2210.00m 10.08643 (2022) (cit. on p. 7).
[MEMPST21]
M. Malek Esmaeili, Mironov, Prasad, Shilov, and Tramer. "An- tipodes of label differential privacy: Pate and alibi". In: Advances in Neural Information Processing Systems 34 (2021), pp. 6934-6945 (cit. on pp. 1, 8). S. Maddock, A. Sablayrolles, and P. Stock. "CANIFE: Crafting Canaries for Empirical Privacy Measurement in Federated Learning". In: arXiv preprint 2YXi:2220000212 (2022) (cit. on pp. 5, 7).
[MSS22]
[NHSBTJCT23]
M. Nasr, J. Hayes, T. Steinke, B. Balle, F. Tramèr, M. Jagielski, N. Carlini, and A. Terzis. "Tight Auditing of Differentially Private Machine Learning". In: arXiv preprint arXiv:2302. 2302.00956 (2023). URL: https: // arxiv. org/ abs/ 2202..302.co0 07956 (cit. on pp. 1, 4, 5, 7).
[NSTPC21]
M. Nasr, S. Song, A. Thakurta, N. Papernot, and N. Carlini. "Adversary instantiation: Lower bounds for differentially private machine learning". In: 2021 IEEE Symposium on security and privacy (SP). IEEE. 2021, pp. 866-
882. URL: https::tp///.. arxiv. org/ aaa/a////// 22011 04535 (cit. on p. 7).
[PAKMO023]
K. Pillutla, G. Andrew, P. Kairouz, H. B. McMahan, A. Oprea, and S. Oh. "Unleashing the Power of Randomization in Auditing Differentially Private ML". In: arXiv preprint arXiv:2305. /8447 (2023). URL: https://arxii: org/ abs abaaabaa/355 /2005. 18447 (cit. on p. 8).
[RRST16]
R. Rogers, A. Roth, A. Smith, and O. Thakkar. "Max-information, differen- tial privacy, and post-selection hypothesis testing". In: 2016 IEEE 57th An- nual Symposium on Foundations of Computer Science (FOCS). IEEE. 2016, pp. 487-494. URL: https: : / arxiv. org/ wwg//b//////oooooooooooooo.aeert 1604. 03924 (cit. on pp. 2, 8).
[SO]HO9]
Sankararaman, G. Obozinski, M. Jordan, and Halperin. "Genomic privacy and limits of individual detection in pool". In: Nature genetics 41.9 (2009), pp. 965-967 (cit. on p. 7).
[SSSS17]
R. Shokri, M. Stronati, C. Song, and V. Shmatikov. "Membership inference attacks against machine learning models". In: 2017 IEEE symposium curity and privacy (SP). IEEE. 2017, pp. 3-18 (cit. on p. 7).
12

---

[SZ20]
T. Steinke and L. Zakynthinou. "Reasoning about generalization via con- ditional mutual information". In: Conference on Learning Theory. PMLR. 2020, pp. 3437-3452. URL: /ttps/////xxv.ooo////////0000 09122 (cit. on pp. 4).
[Tar08]
G. Tardos. "Optimal probabilistic fingerprint codes". In: Journal of the ACM (JACM) 55.2 (2008), pp. 1-24 (cit. p. 7).
[TSSJC22]]
Tramer. A. Terzis, Steinke, S. Song, M. Jagielski, and N. Carlini. "De- bugging differential privacy: A case study for privacy auditing". In: arXiv preprint arXiv:220..12211 (2022). URL: https / /arxiv. org abs 2202. 12219 (cit. on p. 1).
[War65]
S. L. Warner. "Randomized response: A survey technique for eliminating evasive answer bias". In: Journal of the American Statistical Association 60.309 (1965), pp. 63-69, URL: https: / www. jstor org / stable/ 2283137 (cit. on p. 2).
[WBKBGGG22]
Y. Wen, A. Bansal, H. Kazemi, E. Borgnia, M. Goldblum, J. Geiping, and T. Goldstein. "Canary Coalmine: Better Membership Inference with En- sembled Adversarial Queries". In: arXiv preprint arXiv:2210.1077 (2022) (cit. on p. 8).
[ZBWTSPPNK22]
Zanella-Béguelin, L. Wutschitz, S. Tople, A. Salem, V. Rühle, A. Paverd, M. Naseri, and B. Köpf. "Bayesian estimation of differential privacy". In: arXiv preprint arXiv:2206.05// 2599905999999 (2022) (cit. on pp. 1, 5, 8)..
[ZK16]
S. Zagoruyko and N. Komodakis. "Wide residual networks". In: arXiv preprint arXiv:1605.07140 07146 (2016) (cit. on p. 4).
13


Reviews:
[{"review_id": "guZ0xCntTL", "reviewer": "Reviewer_D1TM", "summary": "The paper studies the problem of auditing differentially private machine learning systems. They propose a procedure which does so in one training run -- the key is the ability to include/exclude multiple data items in the run, as well as a novel analysis via leveraging connections between DP and generalization. They conduct experiments auditing DP-SGD obtaining meaningful empirical privacy lower bounds. ", "questions": "1. Why the particular choice of score function for white-box attacks? Did the authors try other choices before settling on this?\n2. What is the intuition behind allowing abstention? ", "limitations": "I greatly appreciate that the authors provided an extensive discussion of the limitations. However, as suggested above, the writing is too dense in these parts. ", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. The topic of the paper is important and timely.  As the authors put, a privacy audit allows to assess the tightness of mathematical analysis and detect errors in analysis and implementation. As differentially private machine learning systems are being deployed increasingly, the research has potential to be impactful in these areas.\n\n2. The authors make interesting contributions, with strong theoretical underpinnings which directly lead to improved results in practice. In my limited experience, such results aren't are rather rare and I greatly enjoyed this aspect of the paper. Moreover, the idea of membership inference with multiple inclusion/exclusion of data items, has been used as a heuristic in the past, so this paper gives a mathematical justification for the heuristic.\n\n3. The paper is very well-written -- it is insightful and to the point. The paper also contains an extended discussion (Section 6) on the limitation of this work (and related approaches).", "weaknesses": "1. In some parts of the paper, I found the writing to be too dense. This is especially true for Section 6. I encourage the authors to revise this part.\n\n2. While the authors provide extensive experimental results testing various aspects of the procedure, I found the section to be poorly organized. I encourage the authors to provide an overview of what is to come in the beginning of the experiments section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time in reading and reviewing our submission!\n\n**Writing:** We will edit the paper, and especially Section 6 for clarity.\n\n**Why this score function:** This is the same score function as used in the prior work, previous works showed it achieves tight results. Our approach works with any score function and it is an interesting direction for further work to devise new score functions. \n\n**Why abstention:** As shown by Carlini et al. (2022), membership inference attacks frequently perform much better on some “hard” examples than on others. Abstaining allows us to focus on only those “hard” examples which are easiest to perform membership inference on. In addition, the hardness of the examples also has an element of chance due to the noise added for privacy; any given example may be harder or easier depending on how the noise happens to affect its score.\n"}, {"review_id": "ab6rdWSDWP", "reviewer": "Reviewer_ZoZd", "summary": "This paper presents a one shot approach for auditing privacy. Their approach is as follows: given n independent input samples and a (dp) algorithm to audit, they divide the $n$ input samples into two groups $X$ and $Y$ of size $m$ and $n-m$ respectively. Then they randomly select a partition of the first part $(X_1,X_2)$, and only use $X_1 \\cup Y$ as the input of the dp algorithm. After that, they choose / design an application dependent score function that helps decide if each member of $X$ appeared in the input of the algorithm or not. The accuracy of this decision function implies a lower bound on the privacy of the algorithm. \n\nTheir main technical observation is that if $X$ is partitioned through a poisson sampling procedure, then running the auditing algorithm for one run is as good having $m$ independent runs. Their algorithm works both in the case where the final result of the algorithm is released and in the case where the intermediate steps are also released. In the end they decide whether the algorithm could be $(\\varepsilon, \\delta)$-dp or not by observing that the number correct guesses has to be less than $r \\cdot e^\\varepsilon / (e^\\varepsilon+1) + O(\\sqrt{r})$ with high probability, where $r< m$ is the total number of guesses.", "questions": "In line 51 to 57, the authors mention that such results were previously unattainable in the setting where only one model could be trained. On a conceptual level, what do you think was the roadblock that previous work could not overcome and is overcome in this work?\n\nIt's not clear to me in the experiments whether the \"meaningful\" metric to consider is $n-m$ or $n / m$.\n\nThere's no other auditing baseline presented to compare to in Figure 6. How do your results compare to previous work?\n\nYour empirical results suggest that the lower bounds converge to analytical bounds in some cases if delta is sufficiently small and the number of examples go to infinity. Is there an analytical explanation for this?\n\nSomething that's a bit confusing to me is that in Figure 10, the empirical lower bound on epsilon decays after some point. Can you explain why this is happening?", "limitations": "The authors have discussed the limitations of their work adequately.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The experiments for gradient space attack suggest that their lower bounds are within constant factor of the theoretical upper bounds, in both the case where the adversary has access to all of the model iterates and in the case where the adversary only has access to the final model.\n\nThe review of related work is very good and well written.\n\nTheir empirical lower bounds converge to analytical bounds in some cases if delta is sufficiently small and the number of examples goes to infinity.", "weaknesses": "Their approach does not seem to extend well to the case where delta is not very small.\n\nIn the setting where the adversary only can audit the input space (as opposed to the gradient space), their results do not seem to be very strong. This is important because in practice the algorithm has to be private with respect to the input space and not the gradient space. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and comments. We respond below.\n\n**Not small delta:** Our approach works well for reasonable values of delta. E.g. delta=10^-3 in Figures 1 & 2. Handling larger delta is difficult even with multiple runs.\n\n**Conceptual roadblock:** The fact that multiple examples was previously considered as an unproven heuristic shows that people had the right intuition. The high-level key to analyzing this seems to be framing it in terms of generalization. The DP=>generalization literature provides the right toolkit to analyze multiple examples, but we still needed to do a lot of technical analysis to obtain tight results.\n\n**Comparisons for Figure 6:** Please note that none of the previous works can provide guarantees for the single run setting that we are considering in this work, as a result there are no previous works that we can directly compare to. To attempt a comparison to prior work, we tried auditing the Gaussian mechanism with a single example and multiple runs. To obtain results comparable to Figure 10 (i.e. eps>=2.8 when the sensitivity and standard deviation are equal), we require at least 100 runs using prior methods in comparason to a single run using our method.\n\n**Why n-m:** The main point that we want to mention in these experiments is that by increasing the number of non auditing examples the auditing becomes harder. Therefore, it doesn’t make much difference if we use m/n or n-m. Moreover, machine learning models have limited capacity and the number of examples seems to be more important than the ratio. For example as we see in Figure 7 by increasing the number of auditing example significantly we see worse auditing performance. \n\n**Convergence of lower bound to upper bound:** Figure 9 shows that our empirical lower bound does converge to the theoretical upper bound as the number of examples increases and accuracy is held constant. This simply demonstrates that our main theorem is tight. The gap between the bounds is due to statistical uncertainty, which decreases as we add more samples.\n\n**Lower bound decays in Figure 10:** This simulation shows the effect of abstentions. I.e., abstaining on some examples allows us to focus on the clearest examples, which results in higher accuracy. In Figure 10 we increase the number of guesses by making fewer abstentions, which results in lower accuracy. (In contrast, the accuracy in Figure 9 remains constant as we add more guesses.)\n"}, {"review_id": "t0fJMb3IR9", "reviewer": "Reviewer_icCj", "summary": "The authors propose a scheme for auditing differentially private machine learning models with a single training run (instead of thousands as have been used so far).", "questions": "1.  in ll 123 f., the authors say that the design of the attack is orthogonal to the analysis of the privacy attack. I wonder whether this claim is necessarily always true. Design methodology introduced for attacks with 1000s of runs might suffer from a high variance that could be maybe be highly detrimental for a single training run?\n2. Do the authors believe that the methodology could be extended to multiple training runs to have a tradeoff between either 1000 or 1 runs?", "limitations": "the limitations have been adequately addressed and illustrated", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. limitations clearly explained and illustrated\n2. paper is really well structured (except for related work; see weaknesses)\n3. important impact within DP auditing", "weaknesses": "1. It would help the reader if the related work was moved to before the empirical evaluation. Methods from the empirical evaluation are adapted from related work so more explanations earlier on might help with understanding\n2. the comparison with related work falls a bit short. it would be nice to whether and when the heuristic proposed by MEMPST21 is not practically applicable. If they provide a better bound that holds true in most scenarios (even if there is no mathematical guarantee for it), it might be preferable to a loose bound with mathematical guarantee.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments, particularly the suggestions regarding the related work section.\n\n**1. Line 123:** We will clarify that there may be overlap between the design of attacks and our analysis. But, conceptually, most auditing attack design considerations are the same in our setting and in the setting of prior work. That is, we are focused on creating examples that have a high effect on the training procedure and then detecting that effect. Nevertheless, we will make it clear in the text. \n\n**2. Multiple runs:** Extending our analysis to handle both multiple runs and multiple examples is a very interesting topic for future work and something that should be possible. However, we do want to emphasize that, for large models, training a single model is very expensive, and we think it is also important to improve the single model setting. \n"}, {"review_id": "EIX0sSKBdD", "reviewer": "Reviewer_x3UA", "summary": "The paper gives a simple version of a differential privacy (DP) auditing, and the proposed method is related to the recent works (G. Andrew, P. Kairouz, S. Oh, A. Oprea, H. B. McMahan, and V. Suriyaku- mar. “One-shot Empirical Privacy Estimation for Federated Learning”, 2023 and S. Zanella-Beguelin, L. Wutschitz, S. Tople, A. Salem, V. Ruhle, A. Paverd, M. Naseri, and B. Kopf. “Bayesian estimation of differential privacy”, 2022). There is also a theoretically rigorous analysis for the proposed method.\n\nAndrew et al. (2023) work seems very much related (does also one shot auditing) however more heuristic. This paper provides confidence intervals for the epsilons, whereas it seems to be an open problem whether the empirical epsilons by Andrew et al. (2023) can be rigorously connected to the theoretical guarantees.\n\nThe idea in the proposed method is simple: certain amount of data (canaries) is held out for auditing such that each sample is randomly included in the training, and in the end the total number of correct guesses (whether sample was or wasn't in the training data) will give the empirical epsilons (high-probability lower bounds). This ratio can be connected to the theoretical guarantees via Theorem 3.1. The main result is the analysis of the method (Theorem 3.1). The experiments are very similar to those used in the recent auditing paper by Nasr, Hayes, Steinke, Balle, Tram`er, Jagielski, Carlini, and Terzis.\n\nA pathological example in the shows the tightness of the epsilons give by this auditing method, and also includes some discussion about the looseness of the bounds in realistic situations.", "questions": "In the white box setting, your experiments show that increasing number of data samples increases the epsilon lower bound. In Figure 3 you have Cifar-10 results up to $m=5000$ samples. Did you try for $m>5000$? How close can you get? Why not to report results for $m>5000$?\n\nIn the white box setting, where you insert the canaries and get the best results:  how expensive is the attack itself? I mean if you construct the canaries at each step, how expensive it is compared to the model training? \n\nThis approach is for auditing an ML system, and then it seems reasonable to use a small amount of samples and report the epsilon lower bounds. What if the protection gets really strong for realistic training data sizes, are those epsilons meaningful anymore? Would there be a way to make the method dataset/model specific?\n\nTypo, p.5:\n\"First, we evaluate the effect of the number of the auditing example\"", "limitations": "Yes, there is an extensive discussion in the end about the limitations of this approach. The extended version (supplements) has also a discussion about possible directions for future work.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The idea is simple, the analysis sound and the paper is easy to read. All in all I think fits well to NeurIPS\n- The analysis is tight in a sense that there are pathological DP algorithms for which the empirical epsilons are tight.\n- Contribution seems clear: puts one shot auditing on a more rigorous footing (more rigorous than the previously proposed approaches)", "weaknesses": "\n\n- It remains a bit unclear from the paper, how does it compare to other auditing methods? It would be nice to see how it compares to e.g. to the empirical epsilons given in [NHSBTJCT23]. Especially in case of black box attacks there seems to be a big gap. Also would be interesting to see how the result compare to the results given by the one shot method of [AKOOMS23]. Even if the epsilons reported here are on a more rigorous footing than those of [AKOOMS23], I would guess that in practice one might end up using the method of [AKOOMS23] if it tends to give much more realistic epsilons.\n\n- It still remains a bit unclear how useful this would be in practice. Especially in the black box setting the results look weak: already with 10000 samples (all used for auditing) or small amount of additional samples (not used for auditing), the empirical epsilons are really far from the theoretical ones. \n\n- One small weakness is perhaps certain lack of originality: the main contribution is the mathematical analysis, the main ideas behind this auditing method seem to be laid out already in the recent works [ZBWTSRPNK22] and [AKOOMS23].", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments, which we respond to now.\n\n**On comparison with previous works:** Nasr et al. [NHSBTJCT23]  uses multiple runs and, as a result, they achieve tighter bounds than we do for the same algorithm; however, we are not sure if there is any meaningful comparison that we can do here as their method cannot analyze our setting and vice versa. \nAndrew et al. [AKOOMS23] propose an epsilon estimation technique which may not be a lower bound; their results in Table 1 show an estimate of epsilon that is larger that the provable epsilon upper bound. In the version that was available before the NeurIPS deadline their estimated epsilon actually significantly overestimated the true epsilon i.e. the theoretical upper bound was 50 and the estimate was 78. Given that their approach does not produce lower bounds on epsilon, a direct comparison is not very meaningful. An interesting direction for further work is to combine our methods with their approach.\n\n**On weakness of the black-box results:** We agree that in the black-box setting our results are weak, as is the case in all previous work. The black-box setting is very challenging, and there is a need to develop better attacks. We note that our analysis can then be applied to better attacks that are developed in the future.\n\n**On novelty:** The idea of using multiple canaries to audit DP mechanisms has been mentioned for years now; the first paper on auditing DP-SGD by Jagielski et al. [JUO'20] introduced multiple examples and used group privacy to analyze their results. The main novelty of the work is in creating a framework to theoretically analyze the setting and to provide a tight mathematical analysis. \n\n**Experiments with $m>5000$:** We didn’t experiment with more canaries due to memory limitations. In Figures 9 & 10 we simulated results for up to 1,000,000 and 100,000 examples, respectively.\n\n**Cost of the attack:** In the whitebox setting, creating canaries is very simple as they are simple gradient vectors that have large value on a single coordinate. The main cost is computing the score function, which requires comparing each gradient update vector with all of the canaries, which is a dot product between two large vectors. This cost can be reduced in future by only focusing on a specific layer in the network or small set of parameters. In the black-box setting, the canaries are simply examples and we only need to evaluate the final loss, which is much easier than computing inner products.\n\n**Would there be a way to make the method dataset/model specific?** The choice of auditing examples/canaries and the score function can be tailored to the dataset/model. \n\n"}, {"review_id": "l1Z4qnerAw", "reviewer": "Reviewer_U5hR", "summary": "The paper improves the computational efficiency of auditing differentially private machine learning systems by connecting differential privacy and statistical generalization. The authors propose the first 1-round scheme compared to the standard solutions with hundreds of training rounds. \n\nThe auditing procedure operates as follows. 1) Randomly identify $m$ data points to either include or exclude. 2) Run the algorithm on the randomly selected dataset. 3) Given the algorithm's output, the auditor “guesses” whether or not each data point was included or excluded. \n\nThe main theoretical contribution is an improved analysis that is tailored to yield tight bounds. The auditing scheme requires minimal assumptions. The authors theoretically justified the improved efficiency of auditing via membership inference on multiple examples simultaneously. The paper shows that standard membership inference attacks can be used for auditing analysis, i.e., exploiting the parallelism of multiple independent data points in a single run of the algorithm in lieu of multiple independent runs.\n\n\nIn experiments, the authors audited DP-SGD training on a WideResNet model, trained on the CIFAR10 dataset across multiple configurations. The experiments contain both gradient and input attacks. The experimental results confirm the contributions claimed by the authors before.\n", "questions": "The paper is self-contained. The details in the supplementary are very sufficient.", "limitations": "The authors studied the limitation comprehensively.", "rating": 9, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "+ The paper gives the first scheme of one-round privacy auditing, which is computationally efficient. This is a totally new perspective, jumping out of prior literature.\n+ Theoretical foundation has been well built, i.e., Theorem 3.1. The formulation of privacy auditing bridges guess and privacy, which can be adopted in future instantiations/applications.\n+ The experimental results are convincing, i.e., confirming the paper's contribution.\n+ The writing is excellent. The authors clearly introduce the scheme, and meantime, show their deep insights and creative knowledge. At least, I feel I learned a lot in this paper.\n+ Personally speaking, I think this paper will motivate many future works. \n ", "weaknesses": "I did not find the weakness. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your review!"}]

Author rebuttal:

Meta-review: The authors propose an efficient approach (that uses a single training run) for auditing private ML systems. All of the reviewers are very positive about this paper. This is one of the rare submission where the authors' (neat) theoretical contributions is expected to have practical significance too.
Decision: Accept (oral)