How Well Can Differential Privacy Be Audited in One Run?
Authors: Amit Keinan
Moshe Shenfeld
Katrina Ligett
Venue: NeurIPS 2025 spotlight ()
Keywords: differential privacy
privacy auditing
Primary area: social_and_economic_aspects_of_machine_learning
TL;DR: We characterize the capabilities of one-run privacy auditing and its inherent limitations and present new approaches to mitigate them.

Abstract: Recent methods for auditing the privacy of machine learning algorithms have improved computational efficiency by simultaneously intervening on multiple training examples in a single training run. Steinke et al. prove that one-run auditing indeed lower bounds the true privacy parameter of the audited algorithm, and give impressive empirical results. Their work leaves open the question of how precisely one-run auditing can uncover the true privacy parameter of an algorithm, and how that precision depends on the audited algorithm. In this work, we characterize the maximum achievable efficacy of one-run auditing and show that the key barrier to its efficacy is interference between the observable effects of different data elements. We present new conceptual approaches to minimize this barrier, towards improving the performance of one-run auditing of real machine learning algorithms.

How Well Can Differential Privacy Be Audited in One Run?
Amit Keinan
Moshe Shenfeld Katrina Ligett
Department of computer science and engineering
The Hebrew University of Jerusalem {amit. keinan2,, moshe.. shenfeldd katrina, (maail..mmma...... ac..aac.... il
Abstract
Recent methods for auditing the privacy of machine learning algorithms have improved computational efficiency by simultaneously intervening on multiple training examples in single training run. Steinke et al. [I] prove that one-run auditing indeed lower bounds the true privacy parameter of the audited algorithm, and give impressive empirical results. Their work leaves open the question of how precisely one-run auditing can uncover the true privacy parameter of an algorithm, and how that precision depends on the audited algorithm. In this work, we characterize the maximum achievable efficacy one-run auditing and show that the key barrier its efficacy is interference between the observable effects of different data elements. We present new conceptual approaches to minimize this barrier, towards improving the performance of one-run auditing of real machine learning algorithms.
Introduction
Differential privacy (DP) is increasingly deployed protect the privacy of training data, including in large-scale industry machine learning settings. As DP provides a theoretical guarantee about the worst-case behavior of machine learning algorithm, any DP algorithm should be accompanied by proof of an upper bound on its privacy parameters. However, such upper bounds can be quite loose. Worse, analyses and deployments of differential privacy can contain bugs that render those privacy upper bounds incorrect. As result, there is growing interest in privacy auditing methods that can provide empirical lower bounds on an algorithm's 's privacy parameters. Such lower bounds can help detect whether the upper bounds in proofs are unnecessarily loose, or whether there are analysis or implementation errors that render those bounds incorrect.
Differential privacy constrains how much a change in one training point is allowed to affect the resulting distribution over outputs (e.g., trained models). Hence, natural approach auditing DP, which we term "classic auditing," simply picks pair of training datasets that differ one entry and runs the learning algorithm over each of them repeatedly in order discover differences in the induced output distributions. Estimating these distributions reasonably well (and hence obtaining meaningful lower bounds on the privacy parameters) requires hundreds or thousands of runs of the learning algorithm, which may not be practical. In response, there has been increasing interest in more computationally feasible auditing approaches that change multiple entries of the training data simultaneously. In particular, Steinke et al. [I] study privacy auditing with one training run (one-run auditing) and show impressive empirical results on DP-SGD.
Classic auditing is not only valid (informally: with high probability, the lower bounds on the privacy parameters it returns indeed higher than the true privacy parameters); it is also asymptotically tight (informally: there exists a pair of training datasets such that, auditing is run for enough rounds, the resulting lower bounds approach the privacy parameters). Steinke et al. [ show that
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

one-run auditing (ORA) is also valid, but their work leaves open the question of how close ORA's lower bounds are to the true privacy parameters, and what aspects of the audited algorithm determine how tightly it can be audited in one run. We explore these questions in this work. Steinke et al. []] empirically demonstrate that one-run auditing of specific algorithms seems to not be asymptotically tight. Indeed, our work confirms this suspicion.
We study guessing-based auditing frameworks, where lack of privacy is demonstrated by guesser's ability to correctly guess, based on an algorithm's 's output, which input training points (from a set of known options) generated the output. As such, we are interested in the efficacy of auditors (informally, their expected ratio of correct guesses to guesses overall) as a measure of their ability to uncover an algorithm's true privacy parameters. Auditors are allowed abstain from guessing about some points. We study auditors both with and without abstentions to pinpoint the role of abstentions.
The performance of all auditing methods is influenced by the choice of the auditing datasets and the guessing method, and sub-optimal choices lead to loose lower bounds. We focus on the inherent limitations of ORA, even under optimal choice of these parameters.
We focus on auditing pure E-D.. Steinke et al. [ also study auditing approximate (e, 6)-DP (bounding given some 5). We choose this simpler setting to zoom in on the fundamental limitations of ORA that appear even when 5 = 0; we expect our findings to remain relevant for approximate DP. In the common regime where 8 is very small, the observed behavior of approximate DP algorithm is very similar to a pure DP counterpart with a similar E and in particular the efficacy of an auditor for the approximate DP algorithm is very similar to that for its pure counterpart. Moreover, observed high privacy loss of an approximate DP algorithm could result from the 6-tail of the privacy loss distribution, weakening the bounds on that an approximate DP auditor can infer. Thus, auditing approximate DP may only create an additional gap (compared to auditing pure DP) for all auditing methods. Steinke al. [] Section 7] discuss this gap for ORA and explore empirically (Section 7).
1.1 Our Contributions
we show that ORA's efficacy is fundamentally limited-ther are three fundamental gaps between what it can discover and the true privacy parameters, which we illustrate by three simple algorithms. ORA fails to detect the true privacy parameters if: (1) the algorithm provides poor privacy to small subset of the input elements, (2) the algorithm only rarely produces outputs that significantly degrade privacy, or (3) the algorithm's 's output inextricably mixes multiple input elements, making it difficult to isolate individual effects when multiple elements are being audited simultaneously. In Theorem 5.2 we give a characterization of the optimal efficacy of ORA, formalizing the three gaps and showing that they are exactly the gaps of ORA. In Theorem 5.3 we use this result to characterize the algorithms for which ORA is asymptotically tight. These are the algorithms that sufficiently often realize their worst-case privacy loss way that can be isolated per training point. In addition, we show parallel characterizations of optimal efficacy and asymptotic tightness for guessers that are required to guess for every element, clarifying the role of abstention (see Theorems 5.1 and C.10).
In Section 4
In Section o we explore, both theoretically and empirically auditing of the most important DP algorithm for learning. DP-SGD, as a case study of ORA. While versions of gaps (1) and (2) exist for DP-SGD, gap (3h-which we refer to as the interference gap-in in particular still looms large. We explore the common approach mitigate this gap and two new conceptual approaches we propose, including a new adaptive variant of ORA, to further mitigate it and improve one-run auditing.
1.2 Related Work
Privacy auditing is often applied to privacy-preserve machine learning algorithms using membership inference attacks [3], where differences in the induced distributions over outputs under differing training data enable an auditor guess some of the training points 33 Jagielski et al. [6] suggest a membership inference attack that is based on the loss of the model on the element. Nasr et al. 7
Kasiviswanathhn and Smith ( state and prove such a claim formally (Lemma 3.3, Part 2) (note that the journal version had typo in the claim, which was corrected in the arXiv version). The lemma is stated for a pure counterpart with privacy level of 2s. but can be extended to arbitrary privacy level > with different blow-up term in ó.
"Code for running the experiments is available at https://githut www.ooommmma...... aainninnnnn/ exploring- one- run- audiiiininnnng. dp

---

suggest exploiting the gradients from the training process to conduct stronger attacks. Jagielski et al. 66] introduce such methods lower-bound the privacy level of an algorithm, and demonstrate it for DP-SGD g. This method achieves asymptotically tight bounds when equipped with optimal datasets and attacks, but computationally burdensome.
Malek Esmacili et al. [9] suggest a significantly more efficient auditing method that conducts a mem- bership inference attack on multiple examples simultaneously in a single run of the algorithm, later evaluated more rigorously by Zanella-Beguelin et al. 10] Steinke et al. M prove that this method valid. They show that this method produces asymptotically tight bounds for local randomized response, and suggest it may be inherently limited for other algorithms.
Some works use the notion of f-DP (a generalization of differential privacy) for tighter auditing [ In a contemporaneous work, Xiang et al. [12 also develop an f-DP-based method for auditing in one run which uses an nntommtiiontthoreetie perspective. Their work also takes note of the interference gap that we study (we have adapted their term "interference"), ) but does not provide the complete characterization of the gaps of ORA or ways to handle this gap as we do.
2 Preliminaries
We study the auditing of algorithms that operate on ordered datasets consisting of n elements from some universe X xF Given a randomized algorithm M X - O, any dataset 1) induces distribution over outputs M (D) of the algorithm. Differential privacy [13] bounds the max-divergence (see Definition C.2p between output distributions induced by neighboring datasets; datasets D, D' E X are neighboring if (i E [n] : D; * D(H S 1. In this case, we write D = D'.
Definition 2.1 (Differential Privacy (DP) [I3). The differential privacy level of a randomized algorithm M : X + O is (MM ;= sup
Doo (M((D))[M M is e-differentially private
D=D'EX"
its privacy level is bounded by e, that is, if eMM S.e.
For simplicity, we focus our analysis on algorithms for which the supremum is a maximum there exist D ~ D' E X such that D
i..e.
= <(M).
One-run auditing D bounds the privacy level of a given algorithm according to the success in a guessing game. The one-run auditor (see Algorithm [ gets oracle access to an algorithm M X - O to audit, and takes as input a pair vector and a guesser that define its strategy. The pair vector Z = Vi...... Un) X 2n is pair of options for each entry of the dataset on which will audit M and the guesser G O - (-1, 0, 13mh is a function that defines how the auditor makes guesses based on the algorithm's 's output.
The one-run auditor runs a game in which it samples a random vector E {-1, 13"h uniformly, and uses it to choose one element from each pair in Z to define the dataset D. Then, it feeds D to M to get an output o. Based on the output o, the auditor uses the guesser G to output a vector of guesses T for the random bits of S, where T; is the guess for the value of S; and value T; = 0 is interpreted as an abstention from guessing the ith element. The auditor outputs a pair of numbers r): the number of correct guesses (that is, the number of indexes in which the guesses in T are equal to the random bits in S: 0 : {i E [x] T, = St)) and the number of taken guesses (that is, the number of non-zero indexes := Hi E [m] T, & 0.1 When the algorithm to audit and the strategy are clear from context, we denote the random variables for (v,r) as (Vn, R.))
Steinke et al. 1 prove that these two counts yield a lower bound with confidence level 1 - 8 on the true privacy level e (M) of ('g( r) == sup( (E E R++ Pr[Bin (r. p (E)) 2 u| S $}), where p the e
standard logistic function p (x) ;= e* (extended with p (0))) == 0 and p (oc) == 1).
Notice that algorithms over ordered datasets are more general than algorithms over unordered datasets. 'Notice that even if the supremum is not achieved for M, for every a O, there exist D = D' E X" such that (MM( [D]] (D))) 2 s(M) a, and hence this assumption does not weaken our results.
"Steinke et al. 1 focus on the ORA variant where Z is a vector of elements to include or exclude, while we consider the variant where Z is a vector of pairs of options (this allows the analysis of algorithms over ordered more general than algorithms other variant). In Steinke et al. [... the adversary can choose fix some rows (to allow simultaneously auditing and training on real data); our analysis covers this option by considering the fixed rows as part of the algorithm.
datasets which
unordered datasets;
results naturally extend to the
We assume that because an auditor cannot benefit from not making any guesses.
3

---

Problem Setting
In this section, we lay the formal foundation for analyzing the efficacy and tightness of ORA. Appendix A extends this to general guessing-basee based audit methods.
We say that ORA is asymptotically tight for an algorithm if there exists strategy such that the number taken guesses approaches oc and the bounds approach the privacy level the algorithm.
Definition 3.1 (ORA Asymptotic Tightness). ORA asymptotically tight for a randomized algorithm
M : O if there exists strategy {(Z,,: GR)NneN with unlimited guesses, i.c., R, _ e(M). where s(M) the n-0c
such that for every confidence level differential privacy level of M
1, (V Ba)
The counts (v, r) also yield privacy level estimation p (+). For every e N. the lower bound on the privacy level is a lower bound on the privacy estimation with the required confidence interval. Thus, the aceuracy determines the lower bound, up to the effect of the statistical correction that decreases as the number of taken guesses increases. Notice that if the accuracy converges to some value a, the resulting bounds converge p-1 (a). Hence, we define the efficacy of ORA using the expected accuracy.
Definition 3.2 (ORA Efficacy). The efficacy of ORA with pair vector Z. a guesser G, and number of elements E N with respect to randomized algorithm M is E,, = E
V,
R..
We show that asymptotic tightness can be characterized as optimal asymptotic efficacy.
Lemma 3.3 (ORA Asymptotic Tightness and Efficacy). ORA asymptotically light for a randomized algorithm M X* + O if and only if there exists sequence of adversary strategies {(Zn, Gn))neN with unlimited guesses such that EM,2,G. n=000 p (E(M))
4 The Gaps
In this section, we show that ORA is not asymptotically tight for certain algorithms; that is, even with an optimal adversary, the bounds it yields do not approach the algorithm's true privacy level. This is in contrast to classic auditing (Algorithm 2 which is asymptotically tight for all algorithms (Lemma A8.
We first consider local algorithms, which, as we will see, are amenable to ORA by analogy to classic auditing. Local algorithms operate at the element level without aggregating different elements.
Definition 4.1 (Local Algorithm). An algorithm M X O is local if there exists sub-algorithm M' X + O' such that for every D E X", M(D) (M"( ..., (D.)..)
Steinke et al. 1 prove asymptotic tightness of ORA for one s-DP algorithm (see Proposition B. Definition 4.2 (Local Randomized Response (LRR) (4).. LRR
: 111,13 + 1)1, is local algorithm whose sub-algorithm is randomized response: (Re(x)
x w.p. p (E)
-x
w.p. 1 pe)
When ORA is not asymptotically tight, the gap results from three key differences between the threat model underlying the definition of differential privacy and the ORA setting. For each difference, we give an example of an algorithm that is not differentially private (i.e., {MM) = oc) and therefore can be tightly audited only if there exists an adversary whose efficacy approaches the perfect efficacy of 1. However, we show that for these algorithms, even with an optimal adversary, the efficacy of ORA close to the efficacy of random guessing. More details appear Appendix B
"The notation
P. refers convergence probability. For a random variable A, we say that
11+000
converges in probability to and denote A P co, if for every M E R, Pr[A> M] m 1.
'The definition requires only the existence of an adversary strategy for which the condition holds. We stress that the adversary strategy may depend on the algorithm, and even on its privacy level. We use this definition because we reason about the inherent limitations of ORA, with the most powerful adversary.

---

(1) Non-worst-case privacy for elements (Proposition B.3 The differential privacy level is deter- mined by the worst-case privacy loss of any database element. However, in order to guess frequently enough, ORA may need to issue guesses on elements that experience with respect to the current output. Consider the Name and Shame algorithm AS) [15], which randomly selects an element from its input dataset and outputs it. The optimal efficacy of ORA with respect to N AS approaches 1/2 when its number of guesses must approach infinity, since the auditor will need to issue guesses on many elements about which it received no information.
worsooot-eas privacy loss
(2) Non-worst-case outputs (Proposition B.6 Differential privacy considers worst-case outputs, whereas in ORA the algorithm is run only once, and the resulting output may not be worst-case in terms of privacy. Consider the All or Nothing algorithm (AONp). which outputs its entire input with some probability p and otherwise outputs null. The optimal efficacy of ORA with respect to AON, is 2 + 5. If p small, the probability of "bad" events (in terms of privacy) is low, and hence the efficacy gap of ORA with respect to AONN is large. (Notice that this issue is inevitable in any auditing method that runs the audited algorithm a limited number of times.)
(3) Interference (Proposition B.9 If an algorithm's 's output aggregates across multiple inputs, there is interference between their effects, and any of them can be guessed well only using knowledge about the others. Differential privacy protects against an adversary that has full knowledge of all inputs except one, whereas in ORA the adversary may have little or no such information. Consider the XOR algorithm, which takes binary input and outputs the XOR of the input bits. For every n 2 2, the optimal efficacy of ORA with respect to XOR $. This uncertainty of the adversary is inherent to ORA, since the auditor first samples a database, and this sampling adds a layer of uncertainty.
To summarize: DP bounds the privacy loss every element from any output against an adversary with full knowledge. In contrast, ORA captures a more relaxed privacy notion that only protects the average element from the typical output against an adversary with partial knowledge.
5 Efficacy and Asymptotic Tightness of ORA
In this section, we formally show that the gaps described in Section 4 bound the efficacy of ORA. We characterize the optimal efficacy of ORA and the conditions for the asymptotic tightness of ORA.
ORA is Markovian process: The auditor samples a vector of bits S ~ U == Uniform (f (111, 1)"). then uses the fixed pair vector Z and S to define the dataset D = Z(S), where Z is the mapping from bit vectors to datasets that the pair vector Z induces. Next, it uses the algorithm M and D to get the output ~ M (D). Finally, it uses the guesser and to obtain the guess vector T = G(O).
For each pair of elements in the pair vector Z, guessing which element was sampled is a Bayesian hypothesis testing problem, where there are two possible elements with equal prior probabilities. and each induces an output distribution. The guesser receives an output and guesses from which distribution was sampled. By linearity of expectation, the efficacy is determined by the mean success rate of the elements, so guessers that are optimal at the element level have optimal efficacy.
When considering guessers that do not abstain from guessing, since the prior is uniform, maximum likelihood guessers are optimal. However, in ORA guessers are allowed to abstain from guessing, so we also consider guessers that guess only if the likelihood crosses some threshold. We analyze the efficacy of these guessers using the distributional privacy loss, which is the log-likelihood ratio between the output distributions that the different elements induce. It measures the extent which an output o distinguishes between elements, extending the notion of the privacy loss [16] to account for uncertainty about the dataset.
In the general setting of a randomized algorithm M : X + O and a product distribution θ Q .... x O,, over its domain X", the distributional privacy loss with respect to index i E [m] Pr [0=o| D. ==a]]
and elements x, y E X is (.M.e....vo)) == In D-..0-MM.))
In the context of ORA.
( [0=]|
we consider the algorithm Mz : M
(-1,1)" + O that takes the sampled vector as input, selects elements based on 2, and runs M on the resulting dataset / (M o 2 is restriction of M and hence e(Mz) S e(M)). and the uniform distribution U* We identify the distributional privacy loss the quantity that captures all sources of uncertainty in the ORA process, and use
5

---

Pr (0-
[==|S:==11
the shorthand (M,z,((0) = (M02,00,6.11100) In
Maximum [=
Pr
8wtr .are,o-Arree (=))))
likelihood guessers first set a threshold 7 which might depend on o and make a decision only for indexes where (()) 2 T, in which case T, sign(fM,z,:(o)
We show that the optimal efficacy ORA can be characterized using a series of relaxations of differential privacy that capture the efficacy gaps we discuss in Section 4 distributional differential
privacy (DDP) (based on noiseless privacy ED(M, 0E
sup
l....i... (0)
average-case distributional differential privacy (AC-DDP),
EAC (M, =
E
sup (iel)),a.veX
p (l (O)I)
O~M(O)
and average-element average-case distributional differential privacy (AE-AC-DDP), (ABAC 0) =
Σ sup (((MM.kaa REEX
E O~M((e)
DDP is a relaxation of DP to the case where the adversary knows only the distribution from which the data is sampled, and is closely related to the interference gap. AC-DDP further relaxes DDP by averaging over outputs; it relates to the non-worst-case outputs gap. AE-AC-DDP relaxes further by averaging over elements; it relates the non-worst-case privacy for elements gap. Notice that in ORA, due to the binary domain X = {-1,1) 1} and the anti-symmetry of the privacy loss, these definitions can be simplified by considering M, without taking the supremum over 2, y X.
5.1 Efficacy
We first consider ORA without abstentions; that is, the guesser must guess for every element. this setting, the guesser's 's success rate is determined by the average distinguishability of an element in the presence of uncertainty about the other elements, so AF-AC-DDP captures the optimal efficacy. Theorem 5.1 (Optimal Efficacy Without Abstentions). For every algorithm M and a pair vector Z,
EM.z. = EAE-Ac(M2, U*) 2 Esc(M2, UT) S ((E U*)) S (E(M)))
(2)
(3)
where EM denotes the efficacy of the maximum likelihood guesser that takes all guesses.
This shows that the gap between AE-AC-DDP and DP is precisely the combination of the three gaps discussed in the previous section. Fach inequality in the theorem statement corresponds to one of them: (1) corresponds to the non-worst-case privacy for elements gap, (2) to the non-worst-case outputs gap, and (3) to the interference gap.
In Appendix C.I.I we show that the optimal efficacy can be characterized using total-variation, in contrast to the max-divergence that characterizes DP (see Proposition C.4.
Abstentions allow the guesser to make only high nigh-confidence guesses, rather than having to guess about every example, increasing the efficacy. There is a tradeoff between the number of guesses and the efficacy: issuing only the highest-confidence guesses increases efficacy but decreases the statistical significance. To handle this tradeoff, we consider guessers that commit to guess least l guesses for some k E [n]. and denote the optimal efficacy under this constraint by E F. Z..kk.." In this case, the maximum likelihood guesser that first sorts the distributional privacy losses by absolute value (., and sets T to the kth largest is optimal.
We define a privacy notion which is similar to AE-AC-DDP, but averages only over the k elements with the highest absolute value of the distributional privacy loss,
AA-AC (M-Ac(M,0) (M,0)= = E
Σ sup p ((MM,e =.Exx
O~M(()
(E)
Forr simplicity, we assume the loss is computationally feasible, though this might be source of an additional gap in all auditing methods.
This the definition for the discrete case. In the continuous case, we use mivediverge
11 (x) ;= - defined in Section 2

---

where I (o) is the set of k indices with the highest absolute value of the distributional privacy loss for an output o. Theorem 5.2 (Optimal Efficacy). For every algorithm M and pair vector Z.
1 M, EAB, (Mc U*) S p(En(Mz, S D(e(MM)))
(2)
This result formalizes the importance of abstentions- thhy mitigate the non-worst-case privacy for elements gap, they allow the efficacy to be determined only by the k highest privacy losses.
We use these results to analyze ORA of key families of algorithms and calculate the optimal efficacy for concrete algorithms. In Appendix C.5 we analyze local algorithms and focus on the classic Laplace noise addition mechanism, showing significant auditing gap for ORA due the non- worst-case outputs gap (see Theorem C.13 and F). In Appendix D.2.1] we analyze symmetric algorithms and focus on counting queries, showing that the efficacy of ORA for such queries approaches the efficacy of random guessing, due to a combination of the non-worst-case outputs gap and the interference gap (see Proposition
Figures 1 3 demonstrate the effect of the ratio of issued guesses & the auditing results of the DP-SGD algorithm. The experimental setting is described in Section 6.2 As the number of issued guesses increases, the efficacy and the closely related estimation of (i.e., p (+)) decrease, as expected from Theorem 5.2, since the guesser is forced to guess in cases where less confident. However, the statistically corrected bounds on illustrate the tradeoff: issuing less-confident guesses decreases the efficacy but increases the statistical power.
5.2 Asymptotic Tightness
Next we the efficacy characterization and Lemma 3.3 to characterize the conditions for asymptotic tightness.
In Appendix C.3
we focus ORA without abstentions and characterize the algorithms for which there is no efficacy gap and ORA is asymptotically tight. show these are the algorithms that can be post-processed to an algorithm that approaches Local Randomized Response (LRR) with their privacy level, where by "approaches LRRR" we mean that w.h.p. (over Z and M) the post-processed output's 's distribution is close to Randomized Response for nearly all elements (see Theorem C.
When the guesser is allowed to abstain, it suffices that enough elements, for example constant fraction of them, are sufficiently exposed, and hence the guesser can accurately guess them. We show that ORA is asymptotically tight for an algorithm if and only if the number of elements whose distributional privacy loss is close to e(M) is unlimited.
Theorem 5.3 (Condition for Asymptotic Tightness of ORA). ORA is asymptotically tight for a randomized algorithm M X* + O and sequence of pair vectors {Zn E X >22) JueN if and only if for every e' < <e(M),
Hi E [m] 1LM.Z.
e')l
oc.
R-+00
As corollary, ORA is asymptotically tight for all local algorithms (Definition 4.1 This also follows from the asymptotic tightness of classic auditing (Algorithm[2 and Lemma A.18j. by the observation that one-run auditing of local algorithm can simulate classic auditing the sub-algorithm.
Corollary 5.4 (ORA is Asymptotically Tight for Local Algorithms), ORA is asymptotically tight with respect to every local randomized algorithm M X + O.
Local algorithms process each element separately, eliminating the concern of interference, and thus the distributional privacy loss equals the privacy loss the sub-algorithm. Even if the sub-algorithm has non- worst-case outputs when the number of elements increases, the number of elements that experience worst-case outputs is unlimited. Hence, local algorithms do not suffer from the gaps, and ORA is asymptotically tight for them.
We extend the analysis to partially-local algorithms operating separately on subsets of elements in Appendix D.2.2] where we use Theorem 5.3 to relate the auditing tightness to the algorithm's "degree of locality" (Theorem D.5). The next section discusses a special case of this setting in the context of DP-SGD.
7

---

6 DP-SGD: A Case Study of ORA and Mitigating Interference
In this section, we step beyond general characterization theorems to consider how well the workhorse algorithm of private learning, DP-SGD, can be audited in one run. DP-SGD is presented in Ap- pendix [.I] it differs from traditional SGD by adding noise to the gradients computed at each update after clipping their norm. We it as a case study illustrate our theoretical insights, focusing on the interference gap (introduced in Section and further explored in Section 5), and propose approaches to mitigate the gap.
We audit the DP-SGD algorithm in the white box access with gradient canaries threat model. This is the strongest setting that Steinke al. [1] consider, and thus the most interesting for revealing ORA's limitations. In this threat model, the adversary can insert arbitrary auditing gradients into the training process and observe all intermediate models. Since using some "real" training examples alongside the auditing examples would only decrease the performance of the auditing, we consider ORA where all the examples are auditing examples, matching our definition of ORA. The auditing elements are d-dimensional vectors, each included or not according to S (equivalently, one element of each pair in pair vector is the zero vector). Each update step of DP-SGI is noisy multi-dimensional sum of random batch of the auditing "gradients."
The multi-dimensione a concern about how effectively ORA can audit DP-SGD. The Dirac canary attack, first introduced by Nasr et al. 77. is one possible response this concern. The attack is an approach to ORA that limits the number of auditing gradients to the dimension of the model, and sets each gradient to be zero in all indices except its distinct coordinate, which it sets to the clipping radius. While the interference between random gradients is already small in high dimensions, the Dirac canary approach completely eliminates it, and with high enough dimension, it allow for meaningful ORA of DP-SGD.
sum aggregates the gradients, creating interference between them, which raises
Prior to our work, it seems that the possibility that including multiple elements per coordinate could be beneficial to ORA was overlooked. However, limiting the number of auditing elements to the dimension of the model comes at a cost: it limits the number of elements experiencing high privacy loss and thus the number of high-confidence guesses. This effeec is especially severe if the dimension is low or the probability of worst-case outputs is low. Our theoretical and empirical analyses below show that assigning more than element per coordinate element per coordinate, by optimizing the tradeoff between the benefit of more potentially accurate guesses and the added interference.
outperform ORA with only one
To further mitigate the effects of interference when assigning multiple elements per coordinate, in Section 6.3 we propose Adaptive ORA (AORA), new variant of ORA in which the guesser is allowed to use the true value the sampled bits from S that it has already guessed to better guess the values of subsequent elements. We also show that this adaptivity has benefits, both theoretically and empirically.
6.1 Theoretical Analysis
The adversary observes the intermediate model weights and knows the learning rate, so it can compute the noisy gradient sum at each step. Since take each gradient to be non-negative in a single coordinate, auditing DP-SGD is equivalent to auditing a multi-iteration noisy version of an algorithm call Count-In-Sets, on random batches of the inputs. The Count-In-Sets algorithm releases multiple counting queries of disjoint subsets of size sn) of its input (in the case of DP-SGD, the sets are composed of identical gradients).
Definition 6.1 (Count-In-Setee The Count-in-Sets algorithm CTS 10, + {o.....){13 s][5)
groups its input elements by their order into sets of size (at most) s(n) and outputs the number of ones in each set.
While the noise addition and the sampling of the batches are the randomness sources that make DP-SGD differentially private, the aggregation of the gradients does not contribute to formal privacy guarantees but limits the efficacy of ORA. Hence the Count-In In-S-s algorithm distills the interference gap in DP-SGD for theoretical analysis.
In the case of s(n) 1, which corresponds to one element per coordinate, Count-In-Seri simply outputs each input element; ORA, even without abstentions, audits this algorithm tightly. At the other
8

---

Mean Empirical Epsilon
1.0
Bound
Estimation
Mean Empirical Epsilon
1.0
Estimattion Bound
0.8
0.6
0.6
0.4
0.4
0.2
0.0
0.0
0.0
0.2
0.4
0.6
0.8
1.0
0
10 20
30
40
50
Ratio of Taken Guesses
Number of Elements per Coordinate
Figure 1: Effect of the fraction of taken guesses & on ORA's results for n = 5000 elements. While taking only the best guesses increases the privacy estimations, the statisti- cally corrected bounds experience a tradeoff.
Figure 2: Effect of the number of elements per coordinate on ORA's results when making k = 100 guesses. The increased number of elements creates a tradeoff, and is optimized with more than element per coordinate.
extreme, when s(n) = n., we get a single counting query, so the interference is maximal and the optimal efficacy of ORA approaches the minimal efficacy; in particular, ORA is not asymptotically tight (see Proposition D.2). However, we notice that effective auditing is possible with s(n) > which corresponds multiple elements per coordinate. If s(n) for algorithm and hence ORA is asymptotically tight for it. In Proposition D.5] we extend this observation and show that ORA is tight so long s(n) o(log(n)) (n)), showing that one-run auditing is possible with multiple elements per coordinate, and potentially benefits from the additional elements.
N, it is local
6.2 Experiments
Our experiments are designed to empirically illustrate the theoretical insights and provide additional intuition, not to serve comprehensive evaluation in realistic settings. We audit DP-SGD with dimension = 1000 for T 100 steps, with sample rate TO parameters, the values of the clipping threshold and the learning rate do not affect the auditing. We fix e 2 and 8 = 10-5, and use an RDP accountant to compute the noise scale We set the auditing gradients described above: each of them is nonzero in exactly no overlap between them, and when n > we choose an equal number of elements for each index. Our guesser sorts the elements by the value of the update's gradient at the coordinate in which the auditing gradient is non-zero; when committed taking k guesses, it guesses for the highest & elements, and for the lowest elements.
_ Since the adversary knows the
index. When S d there is
We plot the bounds on the privacy level that the auditing method outputs; i.e., (', u) with = 0.05 corresponding to confidence level of 95%, as "Bound," and the estimations of the privacy level without statistical correction, i.e., p (#), as "Estimation" In Figures aann each point the mean of 200 experiments, and the shaded area represents the standard error the mean
In Figure 2 we evaluate the effect of the number of elements per coordinate on the auditing results. Steinke et al. [ experiment with one element per coordinate, and observe that as the number of elements increases, their auditing results improve. We extend this result and show that assigning multiple elements to each coordinate can further improve auditing. For example, with element per coordinate the mean bound on is (0.00), and with 8 elements per coordinate it is 0.62(10.01), As predicted by our theoretical results, after a certain point, the statistical benefits more elements guesses) outweighed by the interference.
(and hence
Since the DP-SGD algorithm is (c. DP. we use the (e. 8D-DP variant of ORA. We choose small value of 5 and hence the results essentially identical to those for c-DP ORA.
13 Figures 5 and show similar behavior the empirical efficacy (mean accuracy) in same experiments. "In some cases, the error is small that this area is not visible.

---

6.3 Adaptive ORA
We next consider the new AORA method (see Defini- tion E.3 which is identical to ORA except that lets the guesser know the true values of the previously guessed elements. In Appendix E we further dis- cuss this method and prove that it is valid despite the additional information the guesser receives (Proposi- tion E.5
Mean Empirical Epsilon
0.8
This adaptivity significantly improve auditing,
we show in Section E.3 For some algorithms, the im- provement is maximal- AORA tightly audits them
0.2
ORA Bound
while ORA completely fails, and we demonstrate this with variant of the XOR algorithm (Section EE.31
AORA
Bound
0.0
15
This adaptivity substantially improves auditing of the Count-In-Setis algorithm- to the interference with multiple elements per co- ordinate, but also allows taking advantage the in- creased number of potential guesses, as we show both theoretically and empirically (Section E.3.2).
Number of Elements per Coordinate
not only immune
Figure 3: Comparison of the effect of the num- ber of elements per coordinate " on the re- sults of ORA and AORA of DP-SGD. AORA outperforms ORA thanks to its resilience to increased interference.
We compare ORA and AORA of DP-SGD and show that the improvement from adaptivity also signif- icant for this important algorithm. For simplicity, we experiment with a single-step. full-batch (T' and
sample rate is 1) version of DP-SGD which can be seen noisy version of Count-In-Sets (we leave a comprehensive exploration of auditing of DP-SGD for future work). We set 1000, 5 = 10 as in the previous experiments. To allow for consistent comparison, the guessers for both methods are maximum likelihood guessers with a pre-defined threshold on the privacy loss t 1 (unlike the previous experiments in which we fixed the number of guesses). The non-adaptive guesser uses the distributional privacy loss and the adaptive guesser extends it by conditioning on the sampled bits revealed so far.
and
Figure compares the mean bounds obtained by the methods. Each point is the mean of 200 experiments. The bounds that AORA produces are higher than those obtained by ORA, thanks to the additional information of the adaptive guesser that allows Moreover, while the bounds that ORA produces decrease with more than 5 elements per coordinate, AORA only benefits from adding elements. As the effect of interference increases with the number of elements, the non-adan -on-adaptive guesser has fewer high- nigh-confidence guesses to issue. The adaptive guesser may similarly need abstain from guessing the first elements, it collects information about these elements that eliminates the effect of the additional interference, allowing it to issue high-confident guesses of later elements. These results confirm that the trends from our simplistic Count-In-See analysis (see Section E.3.2 and Figure 9 remain similar in a more complex setting, with noise addition and using a finite threshold on the privacy loss.
make more high-confidence guesses.
Conclusions
This work characterizes the capabilities of one-run privacy auditing and shows that it faces funda- mental gaps. We formalize the three sources of these gaps: con-worst-case privacy for elements, non-worst-cass outputs, and interference between elements. These insights clarify the use cases for efficient auditing and can lead to more informed interpretation of auditing results, preventing auditing from being used as a fig leaf for algorithms with poor privacy guarantees. We also introduce new approaches of auditing multiple elements per coordinate and Adaptive ORA to improve auditing by mitigating the effect of interference. Future work can include designing adaptive attacks to leverage the potential of AORA realistic settings, and exploring the trade-off between the efficiency and effectiveness of privacy auditing, seeking new methodological approaches to optimize it.
10

---

Acknowledgments
This work was supported in part by a gift to the McCourt School of Public Policy and Georgetown University, Simons Foundation Collaboration 733792, Israel Science Foundation (ISF) grant 2861/20, a gift from Apple, and ERC grant 101 125913. In addition, Keinan was supported in part by the Federmann Cyber Security Center, and Shenfeld was supported in part by an Apple Scholars in AIML fellowship. Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency, Neither the European Union nor the granting authority can be held responsible for them.
References
[1] Thomas Steinke, Milad Nasr, and Matthew Jagielski. Privacy auditing with one (1) training run. Advances in Neural Information Processing Systems, 36:49268-4999 492880, 2023.
[2] Shiva P Kasiviswanathan and Adam Smith. On the' semantics' of differential privacy: A bayesian formulation. Journal of Privacy and Confidentiality, 6(1), 2014.
[3] Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. Membership inference attacks against machine learning models. In 2017 IEEE symposium on security and privacy (SP), pages 3-18. IEEE, 2017.
[4] Zeyu Ding, Yuxin Wang, Guanhong Wang, Danfeng Zhang, and Daniel Kifer. Detecting violations of differential privacy. In Proceedings of the 2018 ACM SIGSAC Conference Computer and Communications Security, pages 475-489, 2018
[5] Bargav Jayaraman and David Evans. Evaluating differentially private machine learning in practice. In 28th USENIX Security Symposium (USENIX Security 19), pages 1895-1912, 2019.
[6] Matthew Jagielski, Jonathan Ullman, and Alina Oprea. Auditing differentially private machine learning: How private is private sgd? Advances in Neural Information Processing Systems, 33: 22205-222 22201, 2020.
[7] Milad Nasr, Jamie Hayes, Thomas Steinke, Borja Balle, Florian Tramèr, Matthew Jagielski, Nicholas Carlini, and Andreas Terzis. Tight auditing of differentially private machine learning. In 32nd USENIX Security Symposium (USENIX Security 23), pages 1631-1648, 2023.
[8] Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pages 308-318, 2016.
[9] Mani Malek Esmaeili, Ilya Mironov, Karthik Prasad, Igor Shilov, and Florian Tramer, Antipodes of label differential privacy: Pate and alibi. Advances in Neural Information Processing Systems, 34:6934-6945, 2021.
[10] Santiago Zanella-
Beguelin, Lukas Wutschitz, Shruti Tople, Ahmed Salem, Victor Rühle, Andrew Paverd, Mohammad Naseri, Boris Köpf, and Daniel Jones. Bayesian estimation of differential privacy. In International Conference on Machine Learning, pages 40624-40636. PMLR, 2023.
[11] Saeed Mahloujifar, Luca Melis, and Kamalika Chaudhuri. Auditing f fddifferential privacy in one run. arXiv preprint arXiv:2410.22235 2024.
[12] Zihang Xiang, Tianhao Wang, and Di Wang. Privacy audit as bits transmission:(im) possibilities for audit by one run. arXiv preprint arXiv:2501. 17750 2025.
[13] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity 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, pages 284. Springer, 2006.
[14] Stanley I. Warner. Randomized response: A survey technique for eliminating evasive answer bias. Journal of the American statistical association, 606399))63-69, 1965.
11

---

[15] Adam D. Smith. Lectures and 10. http:://ttiW..gggll...o///llll/
Gf h.gp://ooAAAAlllk2PPPTmnooooooo /view 2020.
[16] Irit Dinur and Kobbi Nissim. Revealing information while preserving privacy. In Proceedings of the twenty-second ACM SIGMOD-SIGACT-SSGARRT symposium Principles of database systems, pages 202-210, 2003.
[17] Raghay Bhaskar, Abhishek Bhowmick, Vipul Goyal, Srivatsan Laxman, and Abhradeep Thakurta. Noiseless database privacy. In Advances in Crypology-ASIACRRPP 2011: 17th International Conference on the Theory and Application of Cryptology and Information Security, Seoul, South Korea, December 4-8, 2011. Proceedings 17, pages 215-232. Springer, 2011.
[18] Michael Aemi, Jie Zhang, and Florian Tramèr. Evaluations of machine learning privacy defenses are misleading. In Proceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security. pages 127 1271-1284, 2024.
[19] Colin Blyth. Expected absolute error of the usual estimator of the binomial parameter. The American Statistician, 34(3):155-157, 1980.
12

---

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

---

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

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: We provide the code for the experiments in the supplementary material, and will publicly release also via GitHub in the camera-ready, un-anonimized version. Our experiments do not use data.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cr cc/
haagli/c/guides//deeebbbm.... hww.eeeuuubssiiooooooooooo. for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
gewiis/gguee//eeeeeeeieiiieiseee CodeeSumieee onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Our experiments do not involve "real" data. We specify the hyperparameters and discuss their choice in Section 6.2
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to a level detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: In all the empirical plots, the standard error of the mean is displayed (as shaded area). Notice that in some of them the errors are so small that is not visible in the plot.
Guidelines:
The answer NA means that the paper does not include experiments.
15

---

The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eπror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: No such information is needed since the experiments do not require any special resources and can be executed on standard personal laptop (we do not train MI. models).
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental rums well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics httpp/////naaipp..c/cubb/////a/a
Answer: [Yes]
Justification: The research conducted in the paper conforms with the code of ethics. It has potential harm, negative societal impact, potential harmful consequences.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative socictal impacts of the work performed?
Answer: [Yes]
16

---

Justification: The paper presents work on auditing the differential privacy guarantees of machine learning algorithms. better understanding of the capabilities of privacy-auditing techniques could contribute to wider adoption of auditing, leading to better privacy proofs and fewer analysis and implementation bugs in deployed algorithms trained on sensitive data. A better understanding of the limitations of privacy-auditing could also help ensure that privacy auditing is not used as a fig Ieaf for algorithms with poor privacy guarantees that are difficult to audit. We choose to discuss this positive impact in this checklist, due to the page limit, and do not see negative societal impact or the work.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g.. deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper does not publish models or data.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
17

---

Justification: The paper explores the ORA method introduced by Steinke et al. [. We use short code piece that was published in the appendix of their paper to compute the lower bound on e. Their paper was published under the CC-BY 4.0 license. We cite their paper in our paper, in the README of our code, and in the code where their functions are used.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g.. website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, snnerswwthcode com/co//caaoooocoo con/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethies, workers involved data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
Institutional review board (IRB) approvals or equivalent for research with human subjects
18

---

Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non non-standard components.
Please refer to our LLM policy //npur:////urraie cc. Cc//oonferencee/22255///// for what should or should not be described.
19

---

A Problem Setting
In this section, we generalize the ideas and definitions presented in Section ORA wider family of auditing methods, which we call guessing- based auditing methods. We generalize Le3ma and prove In addition, we present classic auditing and show it is valid and asymptotically tight.
A.1 Guessing-Based Auditing Methods
Guessing-burd -aaeed auditing methods bound the privacy level of a given algorithm according to the success of an adversary gets oracle access to an algorithm M X - to audit, and takes as input an adversary strategy f. which defines how the adversary selects datasets and how it makes guesses based on the algorithm's 's outputs, and a number of potential guesses e E (if it is not determined by the size of input dataset n.).
guessing game. Such auditing methods defined by auditor A that
Algorithm One-Run Auditor
1: Input: algorithm M X O, pair vector Z (I1, 0i,,,....... Ini Vno X2n such that for all + (-1, 1)".
E [n]. I2 * yi guesser
2: for 1 to do
3: Sample S; E (-1,+11] uniformly.
4: end for
5: Define a dataset D E X" by Dj = {xi [a S; = Mi if =1
6: Compute = (D).
7: Guess T' (i E 1,
8: Count the numbers of correct guesses v == Hi [n] : T, = =SHH and taken guesses == Ki
[n] Ti * 0}/-
9: Return: v,
Algorithm Classic Auditor
1: Input: randomized algorithm M X - O, dataset Donse E X", index E [ni]. elements x, y E X, guesser G ::0 + 0, 1). number of potential guesses c.
2: for i = 1 to do
3: Sample S; E {-1, 11,,,,11 +1} uniformly.
4: Define d = x if S = -
if S = and define D as the resulting dataset from replacing the j'th
element the base dataset Druse with the element d.
5: Compute (D).
6: Guess T; = G(o) 1
7: end for
8: Count the numbers of taken guesses r = Ki [c] 7 + 0}} and accurate guesses := Ki E
[c] T, = S.Y--
9: Return: r.v
Both classic auditing and one-run auditing are guessing-based auditing methods. In classic auditing, a variant of the auditing method that Jagielski et al. [6] introduce (Algorithm an adversary strategy is a base dataset Drase E X",, an index E [n]. a pair of clements x * y E X, and a guesser G. In ORA, strategy is pair vector Z (I1, /1, .i.... En. Vn) 2 and guesser G. In classic auditing, the number of potential guesses e is an input to the auditor, whereas in ORA c n.
In these auditing methods, similarly to the description of ORA in Section 2 The auditor A samples random vector E 1-1, 1 uniformly, defines datasets according to and the adversary strategy f. and feeds the resulting data to M to get outputs. The auditor then uses the outputs and f to produce vector of guesses E (- 0, 1)c for the random bits of S. It then computes the number of correct guesses and the number of taken guesses r. When the adversary strategy f is clear from the context, we denote the corresponding random variables by V. and R.. These counts yield a privacy level estimation p (#) and corresponding lower bound e's (v, r), which are defined as for ORA.
20

---

We say that an auditing method is valid if its outputs always yield lower bounds on the privacy level of the audited algorithm with the required confidence level.
Definition A.I (Validity). An auditor valid if for every randomized algorithm M X O, adversary strategy (JeJCEN. 3 E (0, 1), and e E N.
PV Re) S {(M) 2 1 3-
If the number of accurate guesses V. is stochastically dominated (see Definition A.6) by the Binomial distribution with R. trials and success probability of p (e(M)) the auditing method valid (see Lemma A.7). Both Classic Auditing and ORA are proven to be valid (see Proposition A.8 and Proposition A.9).
If the number of guesses that A takes approaches oo as increases, the lower bounds converge to the privacy estimations. Hence, to analyze the asymptotic behavior of the bounds we can ignore the statistical correction effect and focus on the asymptotic behavior of the privacy level estimations (see L for a formal treatment). We say that an auditing method is asymptotically valid its privacy estimations asymptotically lower bound the privacy level of the algorithm.
Definition A.2 (Asymptotic Validity). An auditor A is asymptotically valid if for every randomized algorithm M X* + O and adversary strategy (Jo)cEN, for every a >>
Ve Rr
Pr
p
S < +
c
Validity implies asymptotic validity (see Proposition A.14).
We say that auditor is asymptotically tight for algorithm if there exists adversary strategy such that the number of guesses it takes approaches do and its estimations asymptotically upper bound the privacy level of the algorithm.
Definition A.3 (Asymptotic Tightness). An auditor A is asymptotically tight for a randomized algorithm M : X* + O there exists an adversary strategy {SeJceN with unlimited guesses, i.e.,
R. 00000
oc, such that for every O,
Ve R
Pr
p
2 (M) -a
Since the asymptotic behavior of the privacy estimations and the privacy bounds is identical, for valid auditors, asymptotic tightness is equivalent to the requirement that for large enough number of guesses, with high probability, the lower bounds that the corresponding auditing method outputs approach the algorithm's 's privacy level. Hence, the definition above is consistent with Definition 3.] (see Proposition A.15 for formal treatment).
The efficacy of an auditor A is defined as in Definition 3.2
as the expected accuracy
V.
EM. ==
R
We extend Lemma 3.3 to general guessing- based auditing methods and prove it in Section A.5
Lemma A.4 (Efficacy and Asymptotic Tightness). For every asymptotically valid auditor A with unlimited guesses, asympiotically light for a randomized algorithm M X + O if and only if there exists an adversary strategy {febceN such that EM,e..
6-000, (s((M))
Lemma A. uses the above lemma to show that classic auditing is asymptotically tight with respect to every algorithm.
A.2 Validity
We define the lower bound of the Clopper-Pearsee confidence interval. This is the function that converts the number of taken guesses and the number of accurate guesses to lower bound on the success probability.
21

---

Definition A.5 (Clopper-Pearson Lower Bound). The Clopper-Pearson lower bound CPL(r, v, 1- of a number of trials r E N, number of successes v E N such that s r. and confidence level 1 - B E (0, 10,1) is
CPL(r, 8, :- sup(p E [0, 1] Pr[Bin (r, p) 2 2) < 53.
We show a condition on the distribution of the outputs the auditor that implics validity of the auditing method. First, present stochastic dominance, partial order between random variables. Definition A.6 (Stochastic Dominance). A random variable X R is stochastically dominated by random variable E IR if for every E R
Pr|X> > >1.
In this case, we denote X Y.
Lemma A.7 (Condition for Validity). For every auditor A, randomized algorithm M X - O. adversary strategy f, 3 E (0, 1), and number of guesses Ve a Binomiia (=(M))), then A is valid.
Proof. Fix a randomized algorithm : X" + O, adversary strategy f. B (0, and c E N, and denote V ~ Bin (Re, (E(M))). We have that
Prieg(Vo, Re) <<(M) Pr[CPL(Re, Vo) S <(((M)) (By the monotonicity of p)
Pr(CPI V') S (c(M)) (By stochastic domination and monotonicity of CPL))
= - 3 (By the CPL definition and the continuity a binomial's CDF in p).
Therefore, .A is valid.
Differential privacy can be characterized as a requirement on the classic auditing game: for every adversary strategy, the probability to guess correctly when a guess made is bounded by p (=(M)). Since in classic auditing, the rounds are independent of each other, the number of accurate guesses stochastically dominated by Bin (r, p (e)). Hence, Jagielski et al. [6] show for their version of classic auditing, the version we present here is valid: that is, the output of classic auditing yields lower bound on the privacy level.
Proposition A.8 (Classic Auditing is Valid). Classic auditing is a valid guessing-buat based auditing method.
Proof.
Pr[S: = 1|, Pr(T, = t|S; = Pr|s = -1] (Bayes' law) Pr(T t]
Pr(T: 1|8: = -1]
(S; sampled uniformly)
Pr[T" =
Pr[T:= = =|S: -1]
(Law of total probability)
Pr = t| -1] Pr t|S,
Pr[Zi = t|S -1//Pr(T
=
= =
(algebra)
Pr(T. U11 = = =
- (((M)
e e-aMM) +1 (5(M) +1
[1 (((M))) (e(M)))
where the second-to-last line holds because the guess T. is post-processing of the output of the e(M) diffeerrrretttially private M.
Therefore, for every taken guess Tj * 0, the success probability is bounded by p (e). The rounds are independent so the number of accurate guesses stochastically dominated as V < Binomial Rt (=(M))).
22

---

Steinke et al. [ show that the probability of success in every guess is bounded by (E), even if one conditions on the previous sampled bits of S. We use their result formally show that ORA is valid. Proposition A.9 (One-Run Auditing is Valid), One-run auditing is valid guessing guessing-based based auditing method.
Proof. Steinke et al. [ show that for every randomized algorithm M X + O and t E (-1,0,13 VI(T = t) & Bin ([|e]l, (P (P(M))) By the law of total probability, < Bin (ITTIl, .P (e(M)) Bin (R,, (R, (s(M)))
A.3 Asymptotic Validity
We show that the Clopper-Pearte Pearson bounds converge the ratio of successful guesses, and that the distance between these quantities is bounded by the number of trials.
Lemma A.10 (Convergence of Clopper- Pearson Lower). For every number of trials r N, number of successes N such that v: S r, and confidence level 1 - 3 E 10,
v ---(L,,,,, S
In 3 2r
Proof. We denote V Bin (r, Cr, v, v) and use Hoeffding's inequality to bound the probabil- ity of Y to be greater than or equal to u:
8 Pr(V's 2 v] Pr(V' - r C,,(,,, 20-r-CPL(,,
S erp -2 -U,0-rCCPL,, CPL(,,,,))
where the first equality follows from the property of the Clopper- Pearson lower bound and the continuity of the binomial distribution's PMF with respect to the success probability, the second equality follows from algebraic manipulation, and the last inequality an application of Hoeffding's inequality. Further algebraic manipulation yields
_F CPL(r, S
In 8 2r
We show that in the setting where the numbers of trials and successes are random variables, the number of trials approaches oo, the difference between the success ratio and the Clopper- Plopper-Pearson bounds converges to
Lemma A.11 (Convergence of Clopper- Clopper-Pearson Pearson Lower for Random Variables), Given probability
space (2, F,P,, for every pair of sequences of random variables over Ω (Ve : Ω + [) N)eeN
and {Re Ω N)aeN such that for every N, Ve R., and confidence level B (0.1),
Re c-
oc, then
V. CPL(Bo Vo.8)
~ O.
Proof. Let e > and O. From Lemma A.10 and since for every 8 E (0, 1), V there exists N E N such that for every > N and E N such that S
r-000 0.
2r
CPL(,, v, Se.
Since Rg
P xo, there exists C E N such that for every C.
0-400
PlR. > M
Hence, for every C,
V.
p
CPL(Re, Vo. Se 2 1
R.
23

---

Therefore,
Ve Rs
CPL( Vol 8)
p P+0. 0400
We show that asymptotic validity can be characterized as condition over the privacy lower bounds rather than the privacy estimations.
Lemma A.12 (Privacy Estimations and Bounds), For every auditor A with unlimited guesses, ran- domized algorithm M x O, adversary strategy {So)CEN and B E (0, 1).
Ve Rs
p-
-Eg(VV, Ro) _ 0.
Proof.
Ve
1
- cV Re)
Re
Ve
sup(ta ER:: Pri 2 Vil S <B)) (by definition)
P₂.
Ve
p- (sup((a E IR. Pr[Binomial(Re.d) 2 V.J & 8))
(monotonicity of p p!)
Re
Ve
-P- (CPL(Re, Vor B)) (by definition)
R₂
0 (By Lemma
A.ll because A has unlimited guesses).
6-+00
Proposition A.13. An auditor A with unlimited guesses is asymptotically valid if and only for
every randomized algorithm M X* + O, adversary strategy [JeJeeN, and B E (0, 1), for every
Pr (Ve, Re) S <((M)
c-000 1.
Proof. By Lemma A.12 the difference between the privacy estimations and the privacy bounds approach 0, and thus
Va > 0: 0: Pr
[P'(VV R.) S <((M) + +a]
00000
Vo
Va 0: Pr
p-1
$ <((M)
0000 1,
Re
and the claim follows.
Proposition A.14 (Validity implies Asymptotic Validity). Every valid auditor A asymptotically valid.
Proof. Let A be valid auditor and assume by contradiction that it is asymptotically valid, that is, there exist an algorithm M, an adversary strategy {Se)CEN, > and > 0 such that for infinitely many values of
Ve R.
Pr
e(M) + +a > 6.
From Lemma A.1l and the continuity of p for every $ (0, 1). for sufficiently large
Pr
E's (V. Rd) 2F
2
R
Hence, for every 8 > 0 there exists such that
Pr [e R.) > e eM)]
2
For 3 $ this is contradiction to validity, completing the proof.
24

---

A.4 Asymptotic Tightness
Proposition A.15 (Characterization of Asymptotic Tightness of Valid Auditors). For every valid auditor A, A is usymptotically light if and only if there exists strategy {JeJeeN with unlimited guesses, i.e,, Rs
P
oc, such that for every confidence level 0 < 1 - 8 < 1,
c-400
(Ve, Ra))
P. e(M).
6-700
Proof. Let (feteEN be strategy. A is valid, by Proposition A.14 it is asymptotically valid, that is,
Ve Ro
Ya 0: Pr
p-
S (MMM) +
Therefore,
Ve
Va > 0: Pr
p
2 e (M)
a
Re
and only if
Ve
p
e(M).
Re
0-000
By Lemma A.12 this occurs if and only if
vB E (0, : : Re)
P P+ e(M),
ct00
which completes the proof.
A.5
Efficacy and Asymptotic Tightness
Lemma A.16. Let a, E R and E b). for every sequence of random variables {Xx]neN S [a,
if
Ve > 0: Pr(X,, S <1+ n=x, 1,
then
Ve 0: Pr(X, 2 n=x, 1
if and only if
E E{X,] 2-000
1, then E[X,] n=000 Using the union bound, for every c 0, Pr[ - S X, S c] x=20 1, that is X, n-000
Proof. First, we show that if Vc > 0: Pr X, 2
1. For bounded
random variables, convergence in probability implies convergence in expectation, so E[X,]
n-000 I.
It remains show that if [[,,,]
1, then Ve > 0: Pr 2 1 - d n n=000 1. For every n E N and > O. we denote (c) = X,, < 1- c) and pH = Pr[X, 1+ c) and we have that for every cL H..H 0,
R 2
E[X,] (1((t) (1 (1- Pr(1 -
S1+ (1 H t -
- - (1=)") (1+b-1)
$ -
-P(cc) .ccc),++ p (c (b-
Given a > 0 and e > 0, take ! = act
Then for every n E N.
3
1
pl(()) < c.
(cH
+ I +
+ pH (c (b 1))
acl
1 1- E(X,]
pH a
ac' ((b 1)
+
+
3el
el
el
25

---

By the convergence of expectation, for sufficiently large n,
L_
3. By the given upper
p as
(b-1))
boundedness of Xa, for sufficiently large n,
Hence, for sufficiently large n,
et
3
( +
3
3
ar.
Therefore, for every d' > O, (c(( n and hence Pr[X,, 21 21- 1
Lemma A.17 (Efficacy and Tightness). (Lemma A.4) For every asymptotically valid auditor A with unlimited guesses, it asymptotically tight for a randomized algorithm M X + O if and only if there exists an adversary strategy {feJOE such that EM.
<-200 p (s(M)).
Proof. Let f be an adversary strategy == (Je)EEN. We show that A is asymptotically tight with and only if its efficacy with it converges in probability to p (e(M)
Define (-ee the sequence of the random variables of the accuracy for each number of potential guesses, that is, Va where Vo, Re (M).
Re
We have that (Xe)cEN C [0, 1]. and using the asymptotic validity and the continuity of p we have that
Ya > 0: Pr[X. S (s(M)) a] 20000 1.
Hence, we can use Lemma 1. 1 to show that
Va > 0: Pr(X, 2 ((((M) - 1-00
if and only if
B[X,] p(e(M))
Using the continuity of p and p p-1
Va 0: Pr(p (Xx) 2 e(M) -a] ~000
and only if
B[X.] SX p (c))
By the definitions of asymptotic tightness and efficacy we get that A is asymptotically tight with f if and only if its efficacy with it converges in probability to (s(M)).
Classic auditing is asymptotically tight with respect to every algorithm.
Lemma A.18 (Classic Auditing is Asymptotically Tight). Classic auditing is asymptotically tight with respect to every randomized algorithm M : X + O.
Proof. By Definition 2.1 there exist x, E X such that D (M'(z)))AM(v))) <(M) and p == Pro-M(x) [LM', , > O. Consider the guesser G that guesses 1 if LM = and otherwise abstains from guessing. The rounds are independent, so the number of guesses of distributed
binomially VT Bin (T)
and hence it has unlimited guesses. By the definition of G, T-+x
its probability to accurately guess taken guess is using the weak law of large numbers and the fact it has unlimited guesses, its efficacy converges to e. Using Lemma A.4 classic auditing is asymptotically tight for M.
B Gaps
Proposition B.1 (ORA is Asymptotically Tight for Local Randomized Response). For every [0, co), ORA without abstentions is asymptotically tight with respect to E-Local Randomized Response.
Proof. Consider any pair vector Z and the guesser that guesses the output, G(O) = and never
abstains. The guess for the ith pair is accurate if and only if O, D., which happens with probability p (e) for each element. For every n E N. the efficacy is p (e), so using Lemma A.4 ORA is asymptotically tight for Local Randomized Response.
26

---

B.1 Number of Elements Expased
We use the Name and Shame algorithm 15 to demonstrate the low efficacy of algorithms for which only limited number of the elements experience high privacy loss
Definition B.2 (Name And Shame (NAS) [3]. The Name and Shame algorithm NAS X - X is the algorithm that randomly selects an element and outputs it.
Name And Shame exposes one of its input elements, and hence is not differentially private.
Proposition B.3 (ORA Efficacy for NAS). For every adversary strategy {fn = (Zn, Gn]IneN with unlimited guesses, the optimal efficacy of ORA with respect to N AS approaches 1. +=000
2: that is,
ENA
Proof. For every pair vector Z and guesser G, the success probability in guessing any element except one that was exposed 2. If the guesser guesses that the value of the exposed element the output, its success probability in guessing this element is 1. Using the law of total probability and the linearity of expectation, and since the adversary has unlimited guesses, the optimal efficacy ORA with respect to N AS approaches 5.
We deduce that ORA not asymptotically tight for NAS. Corollary B.4 (ORA Not Asymptotically Tight for NAS). ORA not asymptotically tight for NAS.
Proof. Using Lemma A.4. since for every adversary strategy (fa)neN, ENAS (co) = 1.
7-000
Name and Shame completely exposes one of its elements, but since ORA requires unlimited guesses (see Lemma A.4 it does not affect the asymptotic efficacy.
B.2
Outputs
We the All Or Nothing algorithm demonstrate how non-worst-case outputs decrease the efficacy of ORA.
Definition B.5 (All Or Nothing (AON)). The All Or Nothing algorithm AON, : X + U (null} an algorithm parametrized by p that either outputs its input outputs null.
D null
with probability p
AON,
otherwise
AON, may expose its input, and hence is not differentially private.
Proposition B.6 (ORA Efficacy for AON). For every n E N. 0 < < 1, and adversary strategy (7, G), the optimal efficacy of ORA with respect AON, +
Proof. For every pair vector Z, guesser G, and element, the success probability when the output O null < 1. For the guesser that guesses the output G(O) = O, the success probability when the output O is not null is 1. Using the law of total probability and the linearity of expectation, the optimal efficacy of ORA with respect to AON, is
2 2 + p
p. p p)
We deduce that ORA is asymptotically tight for AON. Corollary B.7 (ORA is Not Asymptotically Tight for AON), For every 0 < < 1, ORA is not asymptotically tight for AON,
Aemii et al. 18 use another variation of the algorithm to demonstrate non non-optimal usage of privacy estimation methods. We point out that ORA this gap is inherent to the method.
27

---

Proof. Using Lemma A.4 since for every adversary strategy f and n E N, EMG = 2 p (00)
p is small, the probability of "bad" events (in terms of privacy) is low, and hence the efficacy gap of ORA with respect to AON, is big.
B.3 Interference
We use the XOR algorithm illustrate the decrease in efficacy due the interference between the elements 16
Definition B.8 (XOR). The "XOR" algorithm XOR: {0, + {0, 1} is the algorithm that takes binary input and outputs the XOR of the input bits.
XOR(D) Dı e... .......... DipI-
For every N, the XOR algorithm is deterministic and not constant, and hence not differentially private.
For every 2 the optimal efficacy of ORA with respect to XOR is 1. which is the same in random guessing.
Proposition B.9 (ORA Efficacy for XOR). For every n 2 2 and adversary strategy (Z, G), the efficacy of ORA with respect to XOR is 2-
Proof. For every n 2 2, pair vector Z and index i [n], the output O of XOR is independent the ith input bit D, and hence also from the ith sampled bit S;. Therefore, for every guesser G, every guess independent of the sampled bit, and the success probability every taken guess is 1. that is, Pr[S, = T. + 0] = 1.4 so the efficacy 2"
deduce that ORA not asymptotically tight for XOR.
Corollary B.10 (ORA is Not Asymptotically Tight for XOR). ORA is not asymptotically tight for XOR.
Proof. Using Lemma A.4. since for every adversary strategy {fr)nEs EMAfa.n p (Do) =
n0000
2
The adversary's 's uncertainty about the other elements significantly reduces the efficacy of ORA with respect to XOR. Given output of the algorithm, if the adversary has full knowledge of the other elements, can determine the value of the specific element, On the other hand, if the adversary has only uniform prior belief about the other elements, the clement cannot be guessed better than at random.
Generally, the uncertainty of the adversary about the other elements may decrease the efficacy. The whole ORA process an algorithm that first samples a database D 0z, and then runs the algorithm M on this sampled dataset. The sampling adds another layer of privacy, so the privacy level of this algorithm may better than that M.
C Efficacy and Asymptotic Tightness of ORA
Throughout this section we consider the probability distributions induced by the process S ~ UT O M(Z(S)),T C(O), where G is maximum likelihood guesser (possibly with threshold), and omit them from notation when clear from the context.
16 Bhaskar et al. [7 show that XOR noiseless private which implies this gap.
28

---

C.1 Efficacy Without Abstentions
Theorem C.1 (Optimal Efficacy Without Abstentions). (Theorem 5.1 For every algorithm M and a pair vector Z,
E 2,n EAB-AC(MZ, U*) S (M, D(ED(M,, U*)) S (M
where EM N, denotes the efficacy of the maximum likelihood guesser that takes all guesses.
Proof. We consider auditing with the maximum likelihood guesser. From Bayes' law and the fact that Pr(S; = 1) = Pr(S; = -1) we have for any E O, i E [n].
Pr Pr S 1) (s 110 - o) Pr0-00|-=1)+P:(==005-==
and
P=(0=088:=0
0 S -1] -
Pr =))
Using this identity we get
Pr (S; = T. 0= =
(guesser definition)
= -, (previous identity)
p((eM.z.(0)) (Lemma
Using this identity we get
Vn
F.
Rn
1
Pr [S, Ti]
vE(N)
1
Σ
[Pr T; 1 O']] (Law of total expectation)
n
O' (U
vE(m)
E O Mz(Un))
[I((M,,,((O')) (previous identity)
vE(N]
[((MMaz..000))) n JE|m
(Linearity of expectation)
('~M
EAB-AC(Mz )*),
which completes the proof of the equality part.
The inequalities are because the privacy notions are ordered from the most relaxed to the strictest. All relaxations boil down to the fact that the average is bounded by the maximum. In the case of the first inequality the average is over i, in the second it is over and in the third it is over the sampling of other elements.
C.1.1 Connection to Total Variation
We present the max-divergence and the total variation distance, The max divergence measures the highest value of the log-likellne likeliioddo ratio, and the total variation distance measures the total distance between the probability mass functions.
29

---

Definition C.2 (Max Divergence, Total Variation Distance), Let P and Q be distributions over discrete set X represented by their probability mass functions The max divergence of P from Q is
P(z) ((x)
Do (PIIQ)
max In xEX
The total variation distance between P and Q is
Drv(PIIQ) = 1
Σ
-
=EX
We prove two simple identities.
Lemma C.3. Given distributions P, Q over some domain O we have
P(I((o:P.Q)) max ((()
+(o)+((())
and
E Omp
(1(1
+ E (1(( = Pry(P1Q)) onQ
where E(o; P,Q) = log
P(a) @(o))
is the log probability ratio.
Proof. We have
((aP.)))
P(o)
P(o) > Q(o) max(
p (1((a: (.: +1
P(o
Q(oi p(o
P(o) S Q(o)
Combining this identity with the fact that |r - yl + + y = 2 (2, v) we get
- b0 (, P,Q)D]+ - o P,Q))] / (P(o) + +Q())) p p(e(o P,Q))) do
max (P()), Q(1)) P(o) + P(o) Q(o) do
max)(P())((())))
2 J. P(o) + Q(o) + PP(o) - Q(o)
1
= (Pl())
Proposition C.4. For every algorithm M and pair vector Z,
E3,2, 1
Σ
Drv (M
IIM (U% (UB,=:)):
iE(n]
where UDD=-- is the distribution U conditioned on the event D, = - (and similarly for 1).
For simplicity. we present the definitions for the discrete case, but they can be extended to the continuous case by replacing probability mass functions with probability density functions, replacing sums with integrals, handling zero- probabbbbbblly issues. We address this issue where it implications.
For the divergence definitions we define the log likelihood ratio as above if both P(x) * 0 and Q(x) * 0.
only ((x) 0, then (z)) co. and if ((x) 0, then L LPljQ (x)
30

---

Proof. We use the characterization of the optimal efficacy from the proof of Theorem C.1 and the special case of the uniform prior obtain
Lemma C.3
2
11 O~ (z(n) I0 ((,M, (from the proof of Theorem
E
iE(m)
1
Σ
Pr[D: = =
Io ((MM...((O)))
11
O ( (T
(c(m)
+ Pr[D: = 11
E
(e [(((eM.2:00111]
(Law of total probability)
O-M 1T,1=11
1
E (UM((UT
P (IM,,,,(000]
E
lo (IEM,,,,
(the prior is uniform)
2
iE(n)
O (U%),11)
1
Σ
(1 Drv (M (UB, II (Ub, (Lemma C.3
2 71
iE(n)
1
1 1
Σ
Drv M (U |M (UB (Ub..)))
+
2
2
EE(M)
C.2 Efficacy With Abstentions
Theorem C.S (Optimal Efficacy). (Theorem 5.2) For every algorithm M and a pair vector Z,
(3) (3) & ((en(M2, S (e((2)))
F, = & EAEEA UT) EAc(M2, Un)
Proof. The proof follows similar structure to the without abstentions, this time using the fact that l guesses were made, and that S: = T; implies [T.] =1.
Vn Rn
E 2.
E O Mz("m)
Σ VE(M)
Pr Pr(S Pr 0 09|
(Guesser definition)
Ko
E (z(
Σ Pris = 01
(Definition of Ie)
k iElz(0")
E O'(MM((U))
Σ p((emzz(00')) (ETa(0')
(Lemma C.3
K
(M U*)
The inequalities follow from the same argument in the proof of Theorem C.I
C.3 Asymptotic Tightness Without Abstentions
We show that ORA without abstentions asymptotically tight for an algorithm if and only if there exist pair vectors such that selecting the elements according to the pair vector and then applying the algorithm is "asymptotically post-process-able to local randomized response.
Lemma C.6 (Efficacy is mean of success probabilities). For every randomized algorithm M X O, pair vector Z (I1, 121391.. "i.,..,,,,, Vn) 2 and guesser G,
EM.2,G.n
1
Σ
Pr sc-D!
TT = 8;]
n i=
8-
TwA(S_
31

---

where A, = Gn Mz.
Proof.
V
E
(by definition)
Rn
[Vr]]
(no abstentions, linearity of expectation)
n
1 a
Pr
T Si] (counting accurate guesses by indexes)
n
S-U2
T (.)
a
[ = si] (split to indexes, definition of sampling)
11
S-00 (T)
1 a
Pr
[Ti= = si] (Law of total probability, using independence)
n
a TwAn(S_1.1))
C.3.1 The Case of Fixed
We show that an algorithm with a fixed-size input can be audited by ORA without abstentions with perfect efficacy if and only if there exists pair vector under which it can be post-processed to act like local randomized response.
Lemma C.7. For every randomized algorithm M X O, pair vector 7 (I1, U1, -.. T. Fnz Un) 2 and guesser G. .....G.. (ss(M)) if and only if A = LRR
Proof. Notice that (AA) I <(M2) I E(M), where the first inequality is from the post- prosessocsssing property of differential privacy, and the second is because for every E [n]. the ith element in the output of Z is determined by the ith element of its input.
For every index i E [n]] and S_; E (-1,1)"-1 let Pijs_,
Pr 8:021
[0,
s;] denote the
O~A(S_..e))
success probability in guessing the ith index conditioned on the values of the other indices S
Using Lemma C.6 EM = - -~ [r]s_.]- Using differential privacy, for every
index E [m] and S-, {-1,1]=-1, Pajs_, is bounded by p (e(A)). Therefore, as mean of bounded terms, EM..,G. = (s((M) if and only if s(A) = s(M) and for every i E [n]] and S-, E (-1,1)"-1 Piss = (e(M)).
Using differential privacy, for every E [n] and S_, E (-1,1)"-1 Pijs_, = p(((MM) and only if for every 8; E (-1,1), A(S s;) d (RR, that is, for every S E (-1,1)%, A(S) d (S.)
For every i E [n). let X, == LA(S):=S, denote the random variable indicating whether the ith element in the output of A's output matches the ith element of its input. For every i [n]], X2 Ber (p (e(A)). Using differential privacy, for every E [n] and Izz E {0, Pr = 1
Jei] S p (e(M)). Hence, XI...., X,, iid. Ber (p (=(A))), so = LRR
Proposition C.8 (ORA has perfect efficacy iff Local Randomized Response Equivalent). For every n E N, randomized algorithm M X - O, and pair vector 7 E 2 E = p (E(M)) and only if there exists some f such that f o Mz LRRg(M)
+ (-1,1} such that EM,z,G, = (E((M)) if and only if there exists randomized function f O - (-1,1) such that, fo Mz A I.RRe By identifying guessers with such post-procsssing randomized functions, it is enough to show that for
Proof. We show that there exists a guesser
32

---

every randomized function G : - E..z,G. p (e(M)) if and only if A = LRR Lemma C.7 shows that and completes the proof.
C.3.2 The Asymptotic Case
We extend proposition C.8 to the asymptotic case.
We say that e-differentially private randomized algorithm A 1-1, + {-1,1}" is (p. a)- probably approximately RR, in the ith index if under uniform distribution the input, the probability of the ith entry of the output to equal the ith entry of the input is close to the maximal probability
achieved by RR::
Pr swim-1
Pr dor T~A(S-L.88)
[T. = 8:) 2
- a
2 p. and we denote this condition
by A, P. R.g.
We say that sequence of randomized algorithms {A, + (-1,1)) [- JUEN approaches
LRR, if the ratio of indexes for which it behaves like RR, approaches that is, if for every p <
and 0, 1 { [m]:
RR,
12-000 1, denote this by A, -0000, LRR.
Lemma C.9. For every randomized algorithm M : x + (-1,1)" sequence pair vectors 22 E 2 INEN, and sequence of randomized functions functionn {Gn O 1-1,1)"]nee EM p (=(M if and only if fn Mz.. n-000, LRReaMy
10000
Proof. (=) We assume that fn Mz.
72 20
LRR Let < pc(M))) We define m.p.a
m. = ple(M))-6
Me(M):- 32 and == 3. There exists N E N such that for every n > N, fa o Mz,
(M)) and hence
EM EMInn.fan n
Pr SNy
10 S,] (counting accurate guesses by indexes)
O= (8)
Pr 10:=8i) SoUt O~A(S-102))
(Law of total probability, using independence)
71
1=1
-mmple (e(M)) a) (Since fn o Mz.
m.p.a
LRRe(M)
"
(e(M) - (p(e(M)) - 2)
(substituting the values)
(((((M) - 35
4
((((M)) 2
(p (E(M)) 8) (algebra)
(E(MM) 36
4
(((M)) 8 (the factor lesser than 1).
Therefore, EM, Zn.nnn
p (E(M))
(+) We show that if - fa o Mz. mge LRRe(M)) then EM n
(s((M)).
G o Mz. m.p.a LRRg(M) that is, there exist m < 1, < 1, and a > 0 and a sequence (nx heeN such that for every &o E M,
i E [ne]
Pr s-ndii-
Pr s O~A(S-188)
10, =;=s,]a <p) > 1 -
(1 m)na. (1)
33

---

Therefore, for every & E N,
1 nk
E
Pr
[0: =s] (similarly above)
n
(NA(S_LAA)
smp (c(M)) (1 (1-m)(p p (c(M)) (1 p)(p(c(M)) a)) (using Equation
I
= =p(E(M)) - (1-m) (1)11-11) - p)a (algebra)
<p(E(M)))
and hence- EM,Zn.Ja.. R- p (E(())
C.3.3 Condition For Tightness Without Abstentions
Theorem C.10 (ORA is asymptotically tight iff Approaches Local Randomized Response). ORA without abstentions is asymptotically tight for randomized algorithm M : :X* - with sequence of pair vectors {Zn, X²" JnEN if and only if there exists sequence of randomized functions {fn :0:00 (-1,,,,111) IEEN such that
fn Mz.. ~ LRBe(M)
where Zn is the function that maps a bit to its corresponding element in the pair vector Zn,
Proof. Using Lemma A.4 ORA without abstentions is asymptotically tight for M with {Z, E X22 JUEN if and only if there exists sequence of guessers {G, : O [-1, such that F..... n n=000, p (e(M)). We show happens if and only if there exist a sequence of randomized functions {fr : {-1,1)" INEN such that fn o Mz. _= LRR By identifying guessers with such post-processing randomized functions, it is enough to show that for every sequence of
guessers {G, O + (-1, [ Ea....G.... n=20, p (s(M) if and only if Gn Mz. n-
LRRg(M) Lemma C.9 shows that and completes the proof.
C.4 Asymptotic Tightness With Abstentions
Theorem C.11 (Condition for Asymptotic Tightness of ORA). (Proposition 5.3) ORA is asymptoti- cally fight for a randomized algorithm M X* -> O and sequence of pair vectors {Zn E $2n)net if and only if for every ex < (MM)
Hi E [n] 16M,z... 2 s')l
cc.
Proof. Using Lemma A.44 ORA is asymptotically tight for M if and only if there exists an adversary strategy with unlimited guesses such that the efficacy approaches (=(M)). It is enough consider maximum likelihood guessers that commit guess least k<(n) n=000 oc guesses and check under which condition there exists such guesser whose efficacy approaches p (e(M)). That is because any guesser with unlimited guesses can be converted guesser that commits to guess at least k(n) 2=000 oo guesses and its guesses distribution is arbitrarily close to the the original guesser's distribution.
E (,,kk((
p (c(())
E OnM)(Un)
Σ
P p((eM,2.:((1))
22+00
p (c(M)) (using Theorem 5.2
k(n) sElmm)(()
ba <<((M))) (~M)((")
Pr
Σ
p ((eM....;())) 2 n--00 1 (p (IEM.Z.: is bounded)
k(n)
's (OT
Vq <({((M) Ki E [n]
2 /
P oo (using k(n) m+000, x0
n-000
AAA <<(M): (ii 1MM. ..., (0)) 2 E'}l
P
(using the monotonicity of p).
オー00
34

---

C.5 Local Algorithms
The Laplace algorithm [33 a popular rrvaac--pessevve algorithm. We calculate the optimal effi- cacy of ORA without abstentions for the algorithm that applies the Laplace algorithm independently each element of a dataset, and show it displays significant auditing gap for ORA due to the non-worst-case outputs gap.
Definition C.12 (Local Laplace [3).. The Local Laplace algorithm LLP: : {-1,1)" - R" is an algorithm parametrized by > 0 that takes elements in {-1, 1) as ipput and adds Laplace- Laplace-distriutted noise to each one.
LLP(D)) (TP(()), ...,,,......... IP((D)))
where
LP(x) = x + Laplace ( (n=2)
2
We calculate the optimal efficacy of ORA without abstentions for the Local Laplace algorithm. Proposition C.13. For every > 0, the optimal efficacy of ORA without abstentions for LLP& is 1 eepp (-
Proof. The size of the domain of the algorithm is 2, and hence all of the pair vectors are equivalent. We consider the pair vector Z (-1,1,... -1,1) E {-1,1]an The optimal efficacy without abstentions for Z is achieved by the maximum likelihood guesser Gi.PP,, It guesses as follows.
if Pr(LP(-1) = 0) Pr(LP(1) = =0] (Maximum likelihood guesser)
Gi..p.(()):
else
1
if 0
(using Laplace distribution's PMF).
else
For every i E [n]. the probability of LLP,22 to accurately guess the ith element is
Pr[T. = S, 0 = Pr(T: S:] (no abstentions)
Pr[S, Pr[T 5, = 1] Pr[S, Pr|T S, 1] (Law of total probability)
2 (Pr([T = S,SS; =11+ Pr[f; S; 1]) (uniform sampling)
(PF/L(-11 < 0] + PL( > 0]) (by the behavior of the maximum likelihood guesser)
Pr(L(-1) < 0] (using the symmetry of Laplace distribution)
2
Pr
-1 Lap
b <
(using the Laplace algorithm definition)
3
exp
(using the Laplace distribution's 's CDF formula).
Using the linearity of expectation, the efficacy is eep (-
Figure shows p- p
(FiLP,) for multiple values of e. Since this a local algorithm, the bounds of the privacy level converge to this quantity (see Lemma C.14).
Lemma C.14 (Bounds Approach Privacy Level Corresponding to Efficacy for Local Algorithms)..
For every local randomized algorithm M X O, x, X, and B (0. 1), the resulting bounds from ORA of M with Z = (x. V....,,., y) E 2 and a maximum likelihood guesser without abstentions converge in probability to the privacy level corresponding the efficacy,
(eg(Vn, Rn) -p- (EM.Z,,..))
21-000 0.
Proof. By the locality of M, the events accurately guessing different elements have equal proba- bilities and are independent. Hence, there exists q E [0, 1] such that V,, ~ Bin (7i, g). The guesser does not abstain the accuracy is distributed V. Bin (n2, q).
35

---

6
Theoretical Epsilon
Bounds
Empirical Epsilon
3
2
1
0
0
1
2
3
4
5
6
Theoretical Epsilon
Figure 4: Bounds of ORA without abstentions of Local Laplace for multiple values of
Therefore,
Vn
lp (e's(Vn, Rn)) -E M.
CPL (R,, 3)
Rn
Vn
V
V
CPL (Rm, Vn,
+
E
Rn
R
R.
Vn
Vn
CPL (Rng Vn,
+
R.
n
0 + 0 (using Lemma
A.1I
and the weak law of large numbers)
0.
Using the continuity of p-
E's(Vn, Ry) p11 (EM,2
P 0.
12000
D
DP-SGD: Case Study of ORA
D.1
DP-SGD
Algorithm is pseudocode of the DP-SGD algorithm.
D.2
Theoretical Analysis
D.2.1
Count and Symmetric Algorithms on {0, 13
We bound the efficacy of ORA for symmetric binary algorithms {0, 1)". This is fundamental family of algorithms that includes any counting algorithm.
First, we consider the count algorithm that outputs the number of ones in the dataset. Counting queries serve as a basic building block in many algorithms. Un-noised counting queries are not differentially private for any finite e. We show that ORA is not asymptotically tight for such queries. Moreover, we show that the optimal efficacy of ORA with respect such queries, even with abstentions, approaches the minimal & efficacy.
36

---

Algorithm 3 DP-SGD Differentially Private Stochastic Gradient Descent
1: Input: Training data X X², loss function 1: R X + R
2: Parameters: Number of steps T N, sample rate E (0. 1], clipping threshold 0, noise scale o > 0, learning rate >
3: Initialize model weights wn IRd.
4: for ,,..., do
5: Sample batch B from X with sampling probability r.
6: Compute the batch gradients 91, .... BiB] E R of with respect to w
7: Clip each gradient 9: min 11, 1lall 9i-
8: Compute a noisy multi-dimenssonal sum of the clipped gradients ğ -
9: Update the model weights wy = W - 77
10: end for
11:
Return: All intermediate model weights Wo, wr.
Consider the count algorithm C 10, (o......) which outputs the number of ones in the dataset, C(D),.., Da) = I(i: = 1} The efficacy gap of ORA for the count algorithm is due combination of the non-worst-case outputs and the interference gaps; namely, because with high probability, the output of the counting query does not reveal much about each element without knowing the true values of the other elements. With high probability, the output of the algorithm is close to 5. and in this case, the probability of an optimal guesser to accurately guess any particular element is close to We show that the expected efficacy is the normalized mean absolute deviation from the expectation of the binomial distribution.
We use the following lemma about the mean absolute deviation of the binomial distribution to show that the optimal efficacy approaches when n co.
Lemma D.1 (Bound on the mean absolute deviation of a binomial 19 For every n E N and p E 10.
E O-Bin(n.p))
|10 [0-np]] S /np(1 p).
Proposition D.2 (ORA optimal efficacy for count approaches 2)) For every sequence of pair vectors 7, (nn X2n) nue, and number of guesses k E N, the optimal efficacy of ORA with abstentions for the count algorithm C approaches b; that is, E 22nkk n=0,, 2
Proof. Since XX| 2, all pair vectors induce the same dataset distribution, the optimal efficacy
does not not depend on the pair vector. Hence, it suffices to prove the claim for = (0, 1, 1..,....... 0, 1) E X For every E [n|] and E n]. the number of ones in the dataset except D; is distributed as C' ~ Bin (n - 1, 1), and hence
1}})
(((M.2,(0)))
(using Lemma C,3
-
- = = 1}})
PrCC P
37

---

For every E fl...., n/,
max(1
(-=)) (g)=113)
(using the binomial distribution' 's PMF)
(" m
max(1 (mr))
("7)
max ol
(n-1);
n n
[n-1M
DI
0l(n 1j1
-mar maa o}) (by algebraic manipulation)
n1
n
+
0
2
2
0 2
n
Also for = 0, p((MM,,,(o))) p ((()) 1 1
=
0 x
Thus, for every E {o. nJ.
Therefore, for any number of guesses the optimal efficacy is
Σ
p (((M.z.((1))
(using Theorem 5.2
Z,nkk OmBin(n.z))
(O)
1
E
+
0
(using the calculation above)
(n.
2
1
n 2
+
E
2
OmBin
1
1
n
2
+
n
V
(using Lemma D.I
+
2 2/n
1
20000
2
For every number of elements and number of guesses, the optimal efficacy E Z.n.k &s is at least 2. so using the bound from above, the optimal efficacy with & guesses approaches 2, that is.
E Z.nkk
10000
We deduce that the optimal efficacy of ORA with respect to any symmetric algorithm approaches 3. Using Lemma A.4 A.4 it follows that ORA is not asymptotically tight for any such algorithm with non-trivial privacy guarantees.
Corollary D.3. For every symmetric algorithm M 10, O, sequence of pair vectors Z = (Zn E 22m) Inen and number of guesses k E N, the optimal efficacy of ORA with abstentions for M approaches 2, that is, E 2,2.k.n
1
3.
Proof. Every symmetric algorithm M {0, 1) O is post-processing of the count algorithm, and hence the efficacy of ORA for is less than or equal its efficacy for count.
D.2.2 Count in Sets
We analyze auditing of the Count-In-Sets algorithm (see Definition 6.1 enable us to capture the essence of auditing DP-SGD, and show a condition for the tightness of ORA for it.
simplistic algorithm that
38

---

First, we prove lemma about the distribution of the privacy loss of the Count algorithm which we use in the proof of the condition for asymptotic tightness of ORA of Count-Ins In-tss
Lemma D.4 (Privacy Loss of Count). For every sequence of pair vectors Z = {2n E X²m INEN, index i E [n]] and threshold privacy loss at the ith index to be at least can be characterized using the probability of deviation of the output from its mean as
0, in ORA of Count with Z, the probability of the distributional
Prllec 2.1 2 a) Pr 10
11 2
c 1
2 + 1)
Proof. Since |X| = 2, all pair vectors induce the same dataset distribution, so the distribution of the distributional privacy loss does not depend on the pair vector. Therefore it is enough to prove the claim for Z = (0, .,.,, 0, 1) X2n For every E [n] and o E {o......)) n.. the number of ones in the dataset except D. is distributed as C' ~ Bin (n 1, 2). We evaluate the absolute value of the distributional privacy loss.
For every o + 0,
Pr|O D; 0
(o))
In
Pr(0 = ol D; =
Pr|C = o|
Pr|C = (2)))(2²-11
In
(())--11
(n 1)1(0 1)!(n o)! o) on(n
In
1)!(n - 1)!
In
and for o = 0, 2,0)1 = In (ri(==011)
oo, which is consistent with the result above by
defining - := 20.
For every > O, since O Bin (n, 1
Pr[[(om,z;(0)) 2 = Pr
In
N a
(the calculation above)
0
n
Pr
e
N
ca
(In's monotonicity)
O
n
Pr
0 <
0
(algebra)
ea
e +1
O n
= Pr
+ +1)" n
(algebra).
2 e
We characterize the condition for asymptotic tightness of ORA for Count-In-Sets; namely, find threshold on the size of the sets sn) that determines whether ORA is tight. Proposition D.5 (Condition for Asymptotic Tightness of ORA for Count-in-Sets). ORA is asymptoti- cally tight for C1S if and only if s()) = (l)))
Proof. Since XX| = 2, all pair vectors induce the same dataset distribution, so the optimal efficacy does not depend on the pair vector. Therefore, it is enough to prove the claim for ZZn E 1,.,
Throughout the proof, we assume for convenience without loss of generality that n a multiple of s(n).
For every > 0 and E [n), CIST is deterministic algorithm and E(CIS)) = co. Using ORA is asymptotically tight for CTS with Z if and only for every < oc,
Theorem 5.3
Kii [n] 14M.2,1 2 all
00.
n
39

---

We fix a threshold a > 0 on the privacy loss. In each set there are s(n) elements and for every output, their privacy losses are equal. We denote by Aj the event in which the elements in the jth set have
privacy loss of at least a. Notice that for every j.J' E [((n) Aj and Ay are independent and have equal probabilities, we denote this probability by g(n)..
The number of sets whose elements have privacy loss of at least a is distributed as Bin n
((m)) s(mj
and hence the number of elements with privacy loss of at least a is distributed as s(n) Bin (())). Using the weak law of large numbers,
Hii E [m] 1MM.z.l 2 20)
P oc - s(n) Bin s(n)
q((i)
P 00
n-000
n
s(n)
s(n) q(n) n 20
D0
n ((n) Dc.
Using the previous lemma, since the Count-In In-Sets algorithm is composed of multiple independent instances of the Count algorithm, each with input of s(n) elements, for every j E
s(m)
Oj ((n) = Pr In (((n) (s(m)- 2 2)))) 2a = Pr [ s(n)
2 ea s(n)
=
2
2(E + 1)
where the counts of the sets are distributed as O n
iid
Bin (s(n), 2)-
We use Hoeffding's inequality to bound g(n) from above
2a 2e +1
(n) S 2erp
2(c2a + 20 + 1) s(ni)
We bound the term from below
q(n) 2 Pr 0, s(n)
2 2 (m)
Pr[O, (0,
= 2 11(
Hence, for every > O,
22a_ -2e" +
2 (s(m)))1) s (()) S 2eap
2(c20 + 2ea + 1) s(n))
-og[(((()) ((s(n)).
We find the condition for the convergence
1
nn(n) x
+> q(n) =
11
2 2=((n) w
1
s(n) = (llog
s(n) = (1))
Hence, ORA is asymptotically tight for CIST if and only if s(n) o(log(n)).
40

---

Empirical Efficacy Random Guessing
Empirical Efficacy
Random Guessing
Empirical Efficacy
0.9
Empirical Efficacy
0.9
0.8
0.8
0.6
0.5
0.5
0.0
0.2
0.4
0.6
0.8
10 20
40
50
Ratio of Taken Guesses
Number of Elements per Coordinate
Figure 5: Effect of the fraction of taken guesses on ORA's empirical efficacy for 5000 elements.
Figure Effect of the number of elements per coordinate on ORA's empirical efficacy when making l 100 guesses.
D.3 Experiments
Figures and show the empirical efficacy in the same experiments as Figures respectcicctivllly. Figure || shows that the efficacy decreases the ratio of taken guesses increases. Figure o shows the efficacy tradeoff as the number of elements per coordinate varies. As expected, the trend in each figure is similar the trend of the privacy estimations in the corresponding figure.
Figures and show results of experiments for multiple values of to allow better comparison with the results of Steinke et al. [ Figure shows the effect of the number of taken guesses and Figure shows the effect of the number of elements. these figures, each point represents the mean of the bounds in 20 experiments.
k=50
6
n=200
Mean Empirical Epsilon
k=250
Mean Empirical Epsilon
n=1000
1000
5-
4000
k=5000
n=20000
Theoretical Epsilon
4-
Theoretical Epsilon
3
2-
2-
1
2
Theoretical Epsilon
Theoretical Epsilon
Figure 7: Effect of the number of taken guesses k on ORA's results for multiple values of for ORA's results for multiple values of æ for 100.
Figure 8: Effect of the number of elements n on
5000.
E
Adaptive ORA
In this section, we introduce Adaptive ORA (AORA), valid and more effective variant of ORA in which the guesser G guesses adaptively by using the true value of the sampled bits from S it has already guessed. The AORA guesser has more knowledge about the other elements so the interference gap is reduced and the efficacy increases.
41

---

In Section 4 we discuss the interference gap, that is, we see that the efficacy of ORA is limited because the guesser lacks information about the other elements when it guesses one of them. We demonstrate this gap via the XOR algorithm .for which ORA has minimal efficacy even though the algorithm not differentially private. In Section we formalize this idea by reasoning about the noiseless privacy loss, which models the adversary's uncertainty using distribution over datasets. We show two variants of ORA that aim to improve this gap; the first, full-knowledge ORA, completely resolves this gap but it is not valid and hence not useful, and the second, Adaptive ORA, reduces the gap and valid. We demonstrate the efficacy-gain using the crafted Xor-in-Pairy algorithm, for which ORA has minimal efficacy, while Adaptive ORA has perfect efficacy and unlimited guesses. In addition, we show the ad advantage of AORA for a more realistic algorithm, discussing AORA of Count-In- In-Ses,, which provides simple model of auditing DP-SGD.
E.1 Knolednoweedge ORA (an Invalid Auditing Method)
For exposition, consider Knoll-Knowledge ORA," variant of ORA in which the guesser is exposed to all the other elements when it guesses one of them. In this variant, in each round E [rl], the guesser guesses the ith element based not only the output O, but also the values of the other elements D- == Di,.., D;-1. Di+1,--. .... Dn- This auditing method perfectly matches the knowledge of the adversary in the differential privacy threat model, and so the interference gap is entirely resolved.
However, full-knowledge ORA is not valid (see Definition A.. and Lemma A.7p. Even though for every e-differentially private algorithm, the success probability of each guess is bounded by p (s). the dependence between the successes is not limited and hence the number of accurate guesses V not stochastically dominated by Binomial (e)), where r is the number of taken guesses. Therefore, the validity proof of ORA which is based on this stochastic domination (see Lemma A.7 does not hold here.
We show an algorithm that demonstrates the invalidity of "Full- Full-Knowledge ORA."
Definition E.1 (XOR Randomized Response (XRR)). The "XOR Randomized Response" algorithm X RR {0, 1 > {0, }} is the algorithm that computes the XOR of the bits it takes as input, and outputs an e-randomized response of the XOR.
XRR = { D1 0 Dr
with probability p(s)
11 (Di (Di ... @ Dr.)
with probability (6)
X RRR; is e-differentially private. We show a guesser for which dependence between the successes of the different elements is maximal.
Proposition E.2. In full-knowledge ORA, the number of accurate guesses V with the pair vector = (0, 1..,, 0) E (0, 1)2n and the guesser
=
is distributed follows:
V ==
fn
with probability (s)) > Bin (n. p (E)).
otherwise
Proof. This follows from the fact that for every index E [n], G succeeds in guessing the ith element if and only if the output was the XOR.
We conclude that full-knowledge ORA not valid. We might nonetheless hope to find another method that reduces the interference gap, while limiting the dependence between the successes in guessing the different elements.
E.2 Adaptive ORA is Valid
We introduce Adaptive ORA, an auditing method that reduces the interference gap and increases the efficacy of one-run auditing, and prove its validity.
42

---

Definition E.3 (Adaptive ORA (AORA)). Adaptive ORA works similarly to ORA, where the only difference in the guessing phase. In ORA, for every h E [n). G selects an index 4& [n] that it still has not guessed, takes the output O and the true values of the elements it already guessed Si,:-.,, - as input, and outputs TI.-
We present a claim presented by Steinke et al. [ This claim is used in the induction step of the validity proof of ORA.
Lemma E.4 (Stochastic Dominance of Sum M. For every set of random variables X1, X2, Y1, and Y2 if X2 is stochastically dominated by Y1, and for every x E IR, X2 X1 = x is stochastically dominated by Y2, then X1 + X2 is stochastically dominated by Y1 + Y-2
We show that the number of accurate guesses in Adaptive ORA is stochastically dominated by Bin (n, p (E)), and hence it is valid. The proof is very similar to the analogous proof for ORA by I because the original proof bounds the success probability of every guess conditioned on the previously sampled bits.
Proposition E.5 (Adaptive ORA is valid), Adaptive ORA is a valid guessing- auditing method.
Proof. We follow the proof of the validity of ORA by Steinke et al. [ and modify it slightly to allow the guesser to choose the guessing order.
Fix some n E N. We prove by induction on the number of guesses made that the number of accurate guesses until the k'th guess conditioned the guess, the indexes chosen, and the sampled bits revealed so far is stochastically dominated by a binomial distribution, V&IT = t x Bin (lltige P (e(M)) where for any vector a, we denote by aicx and digar ai ..., 02.- and diis... oig. respectively. The claim trivially holds for k = 0 because no guesses have been made up to this point. We prove the induction step; that is, if the claim holds for a k E (O...., n - 1}. also holds for k + 1.
We fix a guessing step E [n] and calculate the sampled bit Si, distribution given guess E 11 an ordering of guessing = (f1,...,%, in) S [n] chosen, and the sampled bits revealed so far 8izk E 11,,11 The probability of the sampled bit to be -
Pr[S,, = 1 = =t, =i, S. 5t.ze
Pr[T = I 1.lI=18.. :/Si:- = -i, = Sicc Pr(Ss = 1|Sict = Sizel (Bayes' law)
Pr[ tt, =i|Ster =sicel
Pr[T'= =1 = i/S122 -1, S1ct= = =iicel
(the bits in S are sampled independently uniformly)
= -,|T=t,1== i|S = 1, 11c. = [tcck]
Pr[T = st, = i) = - Stct = St
(Law of total probability)
] = -, ilS = - -1cs = 8121 + 2 Pr = =t, I = = -1, S,c. = sicel
Pr(T = t,, iS, -1, =Sical
(Law of total probability)
Pr[T'=t,1 = i/ = -1, Sick = Sicul + Pr[T = f, = i,S;; = 11, 11, = 3ick
Pr[T== = = i/5 = Stc, = 8 Pr = t, = i|S,, = 1, Siar = Stcal
(algebra)
Pr[T- = =11 S8 = -1, Sici = 8izul/ Pr(T 1, iSS = 1, Sict 8iccd
é (M))
(M)
(T' and I are functions of Siza and O) [1 ((((M) P (E(M)) (algebra).
E ce(M +1' (M) +1
Hence, the probability of this bit to be conditioned on the same events is bounded in the same way. Pr[S,. = 1/T = t, I = i, Sizu = Sizz. E [1 p (E(M) p (c(M)) Therefore, for any guess for the ith sampled bit the success probability conditioned on the guesser's outputs and the previously sampled bits is bounded, Pr(S, 4, = 1, -= Sick = si S Sp (MM).. Therefore, if T; & 0, Pr(S, = 1,/T 1, = i, i sica) S (e(M),, and since if T: 0, S, * T,, the random variable 17=s; [T' = t, i, Stek Sict is stochastically dominated by Ber (p (E(M)
43

---

We prove the induction step.
Vi+1 (T =) Vil(T - -T, -T=)) =
Bin (1 (Ittga)l.. + Ir (p (c(M)) (by Lemma E.4
Bin (l.
Therefore, V < Bin (1 (e(M)) and hence using A.7 Adaptive ORA is valid auditing method.
E.3
Adaptive ORA Improves ORA
In Adaptive ORA, the guesser has more information about the other elements, and hence the efficacy increases.
E.3.1 Xor-in-Pairs
We show the "Xor-in-Pairs" algorithm as example of an algorithm for which this efficacy gain is maximal. Notice that this efficacy gain varies significantly across different algorithms.
The efficacy of ORA for Kor-in-Pairg is minimal, but Adaptive ORA has perfect efficacy and unlimited guesses with respect to it.
Definition E.6 (Xor-in-Paine For every even n, the "Xor-in- Pann-aair" algorithm XIP": {0, 1]" + {0, 1} gT 1 is the algorithm that groups the elements to pairs by their order and outputs the XOR value of each pair.
XIP" = D1 + Dz...., Dn-1 1 Dr-
Similarly to the XOR algorithm, the Kor-in-Paine is deterministic and it is not differentially private, but ORA is not asymptotically tight for it. In ORA, for every guesser and element i E [ni]. the success probability of G in the ith element is 2.2 However, in Adaptive ORA the optimal accuracy for this algorithm is 1, and hence Adaptive ORA is asymptotically tight for
Proposition E.7, For every even n, Adaptive ORA is asymptotically tight for XIPm
Proof. The guesser that guesses the elements by their order, and guesses
/ is odd otherwise,
T: S 0
that is, abstains from guessing the elements in the odd indexes, and guesses the elements in the even indexes based on the true values of those in the odd indexes, has perfect accuracy and unlimited guesses.
E.3.2 Count-In-Sets
In this section, we discuss auditing of the Count-In-Sets algorithm both with ORA and with AORA. We do not provide a comprehensive analysis of optimal guessers, but rather show an example to demonstrate the advantage of AORA. For this demonstration, we consider auditing with maximum- likelihood guessers that guess only when they have full certainty.
First, consider auditing of the Count algorithm (see Section D.2.1 with guessers that guess only elements for which they have full certainty; that is, a maximum eixiimum-likelhhor guesser with threshold for the absolute value of the privacy loss т All of the taken guesses of these guessers accurate, and we are interested in the expected number of guesses they take, E [.,.
We begin with the non-adaptive ORA. The Count algorithm is symmetric so the distributional privacy loss is the same for all elements, and is infinite if and only all of the elements D1,..., D, have the same value, either 1, and it happens if and only if {0, n2 (it can be verified by the proof of
44

---

Proposition D.2) Therefore,
E Rm = Pr E [0,
o-Binn (1
= 2--11-1),
Notice that for every R 1, and that it monotonically decreases 0.
Now consider Adaptive ORA of Count with a Maxiium--lkelihenn guesser that guesses the ele- ments from the last to the first (the order does not matter for symmetric algorithms) with the same threshold r = co, but now over the distributional privacy loss with the distribution conditioned on its observations so far.
When the adaptive guesser guesses the ith element already knows the true values of the previously guessed elements D Dn. so it can compute the sum of the remaining elements, and use only this sum for the current guess. Therefore, it accurately guesses the element in the ith index if and only if all the elements D....., D; have the same value, either 0 or 1. Therefore, the number of guesses Rt the largest index i such that D1 =... D.. Therefore, Rs ~ mniinGeeometri (5) n2), and
1
E RR
= E
min
Geometric
2
Σ
+
2
1=1
1=
2 (n-1)
Notice that R1 1, and that it monotonically increases to 2.
Consider auditing of the Count-In-Sets algorithm (see Definition with similar maximum- likelihood guessers with r = co. Since the different sets do not affect each other, this algorithm is composed of multiple instances of Count, each with s(n) elements. Therefore, if s(n) 1, both the ORA guesser and AORA guesser have one guess per set in expectation. However, for larger values of s(n), the AORA guesser has more guesses than the ORA guesser. For example, with s(n) 10, AORA guesser has about 1.998 expected guesses per set, whereas the ORA guesser has only 0.002 expected guesses per set. This example highlights the improvement of AORA over ORA for more realistic algorithms.
We ran an empirical simulation of ORA and AORA of Count-In-Sod Figure 9 displays the results as function of the size of the sets s(n). We plot the bounds on the privacy level that the auditing method outputs, i.e., (r, e) with 8 0.05 corresponding to confidence level 95%, with a curve maximum-likellbonn
guessers with co, described above. The number of sets is fixed to be 100, and each point represents 100 experiments.
for each auditing method. We
AORA produces tighter bounds than ORA when s(n) > 1. As predicted by the theoretical discussion. both methods have the same results for s(n) = 1, but as s(n) increases the AORA bounds tighten со yields perfect guessing accuracy, the bounds
while those of ORA loosen. Since setting fully determined by the statistical power of the number of taken guesses. Therefore, the trend of the bounds exactly matches the trend of the number of taken guesses.
45

---

4.0
Mean Empirical Epsilon
3.5
3.0
2.5
2.0
1.5
1.0
ORA Bound
0.5
AORA Bound
0.0
2
4
8
10
Number of Elements per Set
Figure 9: Comparison of the effect of the size of sets s(n) on the results of ORA and AORA of Count-In-Sets. AORA outperforms ORA thanks its resilience to increased interference.
46


Reviews:
[{"review_id": "SiPQpijP3q", "reviewer": "Reviewer_pJ8q", "summary": "The authors investigate the challenge of auditing the privacy guarantees of a mechanism using just one training run. This approach has gained popularity in recent years because traditional auditing methods, which require running the mechanism multiple times, can be computationally expensive. While single-run auditing makes the process more cost-effective, it also comes with the trade-off of potentially weaker lower bounds on the privacy estimates. This means practitioners may not always have a clear understanding of how accurate these estimates are. The paper sheds light on the factors that contribute to these weaker bounds and introduces the concept of \"efficacy\" to analyze the accuracy of privacy estimates in popular mechanisms like DP-SGD. They identify three main factors that contribute to these weaker lower bounds: interference between canaries, the presence of non-worst-case canaries, and non-worst-case outputs.", "questions": "The authors mention that the Dirac canary introduced by Nasr et al. is particularly effective at minimizing interference between canaries. However, I wonder if this advantage is as significant as suggested. In high-dimensional settings, which are typical for DP-SGD, the inner product between a random canary and the noise-added batch gradient is likely to be close to zero with high probability, leading to minimal interference. This would also apply to random canaries, not just Dirac canaries. Could the authors elaborate on the specific advantage of using Dirac canaries over random canaries in this context?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\nOne of the key strengths of this paper is that it addresses a highly important and timely problem. As single-run auditing methods become increasingly popular among practitioners due to their efficiency, understanding the limitations of these methods is crucial. The paper provides valuable insights into when and why these privacy estimates may be less trustworthy, helping practitioners make more informed decisions. Another strength lies in the paper’s introduction of the concept of \"efficacy,\" which is explored with a solid level of mathematical rigor. Despite the theoretical depth, the authors also ensure the work remains highly applicable by focusing on practical mechanisms like DP-SGD, demonstrating the real-world relevance of their findings.\n\nWeaknesses:\n\nMy main concern about the paper lies in its presentation. The authors attempt to condense a substantial amount of information into the limited nine-page format, which unfortunately impacts readability. Essential concepts are often introduced in the appendix, resulting in numerous forward references that disrupt the flow of the main text. For instance, in Section 6.1, the function s(n), which plays a central role in that part of the analysis, is not clearly defined within the main body of the paper. While the constraints of the conference page limit are understandable, the heavy reliance on the appendix for critical definitions and explanations can hinder the reader's ability to fully grasp the material in a seamless manner.", "was_revised": true, "final_justification": "After the rebuttal phase, I remain at my score. I believe that this paper produces meaningful new insights into an important problem (privacy auditing in a single run).", "rebuttal": "Thank you for taking the time to read our work and share your feedback! \n\nYour point about the challenges of squeezing so much content into the conference format is well-taken. Thanks to your comment, we have been working on streamlining the content of the main body so that the reader will not need to turn to the appendix for essential definitions. (For example, we have moved the definition of the “Count-In-Sets” algorithm (including the $s(n)$ notation) to the main text.) These changes have significantly improved readability, so thanks!\n\nYou are correct that in the typical high-dimensional settings, the interference between random canaries is small. Dirac canaries simply completely eliminate this interference and therefore have a small advantage (as studied by Nasr et al. in their Appendix B.1), and hence we (and Steinke et al.) focus on this model. It’s a nice point, though, and we have added a brief mention of it. The approaches we introduce and the phenomena we analyze, such as the tradeoff when increasing the number of elements beyond the dimension, generalize beyond DP-SGD and beyond this specific attack, and will have similar consequences if one were to use random canaries in a high-dimensional setting."}, {"review_id": "4OvGKXVqK2", "reviewer": "Reviewer_YJxk", "summary": "This paper analyzes the capabilities and limitations of one-run auditing (ORA), a method for estimating the privacy loss of differentially private algorithms using a single execution. The authors identify three key obstacles to ORA's accuracy—non-worst-case elements, non-worst-case outputs, and interference between multiple perturbed inputs—and formally characterize their impact on auditing efficacy. They show that ORA is asymptotically tight only under specific conditions, such as for local algorithms. A case study on DP-SGD illustrates these limitations and proposes new strategies, such as multi-element assignments per dimension and adaptive ORA, to further improve auditing performance.", "questions": "The paper is well-written, and the technical details are clearly presented. I have no further questions.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\nThe paper provides a thorough theoretical analysis of the efficacy of one-run auditing (ORA) and rigorously identifies three key scenarios where ORA fails to be asymptotically tight. These limitations are formalized with clear proofs. Additionally, the paper proposes Adaptive ORA and multi-element assignments to improve ORA's performance, supported by both theoretical justification and empirical results.\n\n**Weaknesses**\nThe evaluation is limited to the white-box setting. Extending the experiments to black-box scenarios and comparing performance would offer a more comprehensive understanding of ORA’s practical applicability and the advantage of the two proposed methods.", "was_revised": true, "final_justification": "I will keep my positive score", "rebuttal": "Thank you for taking the time to read our work and share your feedback! \n\nWe agree that, following on from this paper, larger-scale empirical studies of one-run auditing, including in the black-box setting, are an important avenue for future work.\n\nA few brief thoughts on these directions:\n- We expect that ideas we have explored in the white-box auditing model will also prove relevant in the black-box model. For example, similar phenomena when increasing the number of canaries were empirically observed in the black-box setting by Steinke et al. Furthermore, our theoretical analysis of the sum of the gradients should also be relevant for black-box auditing. (Black-box membership inference attacks using the gradient [1] or Hessian [2] at the final model are known to be stronger than attacks that use only the model predictions [1, 2], and under the KKT conditions the model can be represented as a weighted sum of the gradients of the loss w.r.t. the training points [3].)\n- A thorough investigation of Adaptive ORA for the black-box setting will require the development of more sophisticated black-box attacks designed to exploit partial knowledge about other elements, a challenging (and fascinating) future direction.\n\n\n[1] Pang, Yan, et al. \"White-box Membership Inference Attacks against Diffusion Models.\" Proceedings on Privacy Enhancing Technologies (2025).\n\n[2] Suri, Anshuman, Xiao Zhang, and David Evans. \"Do Parameters Reveal More than Loss for Membership Inference?\" Transactions on Machine Learning Research.\n\n[3] Smorodinsky, Guy, Gal Vardi, and Itay Safran. \"Provable Privacy Attacks on Trained Shallow Neural Networks.\" arXiv preprint arXiv:2410.07632 (2024)."}, {"review_id": "vcH2vkvhLP", "reviewer": "Reviewer_UhJV", "summary": "The paper addresses the problem related to how accurately one can audit differential-privacy guarantees from a single execution of an algorithm, a technique called One-Run Auditing (ORA). The authors show that ORA’s precision is fundamentally limited by three sources of errors: 1) non-worst-case elements; 2):non-worst-case outputs; 3) interference among the many perturbed records injected at once. In this paper, the authors attempt to (i) derive tight upper bounds on the best accuracy any ORA scheme can reach, (ii) present necessary and sufficient conditions for ORA to become approximately tight, and (iii) demonstrate how these limits are achieved for Differentially Private Stochastic Gradient Descent (DP-SGD). They further propose practical tweaks, such as planting several canary elements per gradient dimension and an Adaptive ORA that refines its guesses iteratively, regaining some of the accuracy lost to interference. Overall, the work rigorously advances our understanding of the inherent limits and attainable power of privacy auditing.", "questions": "1. How would ORA behave on realistic DP-SGD workloads—e.g. CIFAR-10, Fashion-MNIST, AG-News, or Purchase-100—evaluated at privacy budgets typical of deployments? Do you plan to add such experiments, or can you argue why the current synthetic setting is sufficient to establish generality?\n2. Can you quantify, on full-scale models, the accuracy gains and computational costs of your two heuristics (multiple canaries per gradient dimension and Adaptive ORA)? A small-scale demonstration would help readers gauge their real-world feasibility.", "limitations": "The authors run gradient-canary audits on a 1,000-dimensional DP-SGD synthetic dataset. Experiments on larger datasets would have been more interesting.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strenghts\n\n1. The paper clearly explains its main idea through the gap decomposition and inequalities (From Theorems 5.1–5.2), offering a simple way to understand ORA. Theorem 5.3 clearly identifies when ORA matches traditional auditing, resolving a previously open issue; for example, the question of whether a single-run audit could ever achieve the same asymptotic accuracy as traditional multi-run differential-privacy auditing, given that empirical results often show that ORA often fails to do so in practice.\n\n2. The authors present a nice case study on auditing DP-SGD with one-run auditing (ORA) and pinpoint how its gradient aggregation produces a severe interference gap that muffles privacy signals. Then the authors embed multiple canary gradients per coordinate to increase high-signal elements, and deploy an Adaptive ORA that conditions guesses made at later stages on earlier ones to further cut through interference. This approach is interesting.\n\n3. Overall, the paper delivers a complete theoretical account of one-run auditing: it proves that three precisely-defined gaps bound the best efficacy any ORA method can ever reach (Theorems 5.1–5.2) and pinpoints the exact condition: an unbounded supply of near–worst-case elements, under which ORA attains the same asymptotic tightness as multi-run audits (Theorem 5.3). It then shows how these limits manifest for DP-SGD and proposes two concrete mitigations (multiple canaries per dimension and Adaptive ORA) to narrow the interference gap. \n\nWeaknesses\n\n1. There are some limitations on experiments; tests are done on a simple 1,000-dimensional synthetic model. If the author could include more realistic scenarios (vision, NLP, lower-dimensional tabular models) with practical privacy levels, it would further strengthen the results. For stronger external validity, it would have been nice to see real-world DP-SGD workloads: e.g., Fashion-MNIST or CIFAR-10 (Jagielski et al., 2020; Nasr et al., 2023), Purchase-100 (Jagielski et al., 2020; Nasr et al., 2023), or AG-News text classification (Steinke et al., 2023) evaluated at realistic privacy budgets. Extending such experiments further would enhance the scalability and practicality of the solution. \n\n2. Adaptive ORA is briefly analyzed, with minimal experimental validation, even though it’s highlighted as an important improvement.\n\n3. The authors characterize in Theorem 5.3 that ORA is tight whenever “the number of elements whose |l| is arbitrarily close to \\epsilon is unbounded”, and the authors mention the idea on DP-SGD with two heuristics: 1. adding multiple canaries per gradient dimension; 2. the adaptive ORA variant. But they state that their experiments are meant only to “illustrate theoretical insights … not to serve as a comprehensive evaluation in realistic settings” and state that the entire audit “can be executed on a standard laptop (we do not train ML models)”. So while the theoretical aspects are strong, the practical realization is somewhat unclear/uncertain.\n\n4. Possible ways authors can further enhance the paper without losing rigor:\n  (1) Perhaps the authors can use an overview diagram that shows how the three gaps map to their respective relaxed privacy notions and inequalities.\n (2): Proof relocation: it is perhaps enough to keep high-level proof sketches in the main text, and move algebraic or complicated details to the appendix. This would enhance the readability of the paper for a broader audience.\n (3): It would be helpful to collect all symbols and their meanings in one place so readers do not search across sections.\n\n5. The analysis is limited to pure \\epsilon-DP. Because most deployed systems use (\\epsilon, \\delta)-DP it would help to either (i) extend Theorems 5.1–5.3 to the approximate setting, or (ii) empirically quantify how the \\delta-tail degrades auditing bounds. Given its absence, the practical relevance of the theory remains uncertain.", "was_revised": true, "final_justification": "The authors have addressed my concerns, and I am comfortable changing my rating.", "rebuttal": "Thank you for taking the time to read our work and share your feedback!\n\nWe completely agree that our paper, which maps one-run auditing’s fundamental capabilities and limitations, highlights the importance of future work that will further explore the empirical performance of one-run auditing in a range of real-world settings. While this is out of scope for our paper, we think you lay a good roadmap for what some of that future work could do.\n\nWe also agree that there is room for future research extending our formal results to approximate DP. That said, our results should already have strong relevance to the approximate DP setting, since for reasonable values of delta, the reasons for the gaps still apply and similar results will hold. For example, consider the Name and Shame algorithm that randomly selects an element and outputs it. When applying ORA, the auditor can guess only one element better than random, and hence for any reasonable value of $\\delta << \\frac{1}{n}$ that one sets as input for auditing, ORA would discover a bound on epsilon close to $0$ (despite the true value being infinity). More generally, for very small delta, an $(\\epsilon, \\delta)$-DP algorithm \"most of the time’’ must behave \"similarly\" to an $(\\epsilon, 0)$-DP algorithm with respect to any element of its input, which doesn’t leave much opportunity for ORA to leverage.\n\nOn the empirical side, in our DP-SGD experiments we set $\\delta=10^{-5}$. We note that for this delta, with the number of elements and guesses that we use, the \"fixing term\" (derived by Steinke et al. in \"Privacy Auditing with One (1) Training Run\") that adjusts the epsilon-DP bounds of ORA to account for delta is negligible. For example, with $1,000$ elements, and $70$ accurate guesses out of $100$ taken guesses, the difference between the resulting epsilon bounds (accounting for the delta vs. not accounting for the delta) is approximately $2.5 \\cdot 10^{-3}$. In addition, Steinke et al. (Figure 12) have empirically explored the effect of delta on their auditing results. Their results align with our observation that when $\\delta << \\frac{1}{n}$, the effect of delta is negligible.\n\nThanks for the concrete suggestion to include more on Adaptive One-Run Auditing in the main body of the paper. We would be glad to use some of the one additional page in the camera-ready version to do exactly this, moving up some of the results we have in the appendix on its validity, its maximal efficacy improvement, and on Adaptive ORA of the Count-In-Sets algorithm (the simplified algorithm that captures the essence of auditing DP-SGD). This will help the reader appreciate how AORA is not only immune to the increased interference when adding more elements per coordinate, but actually can only benefit from such added elements. We also have some additional experimental results on Adaptive ORA of DP-SGD (in the same setting as the other DP-SGD experiments) that we omitted from the submission; this felt like too much to try to squeeze into the paper to us, but if you think it is important, we can try to also fit it in.\n\nWe liked your suggestions for further enhancement and are working on implementing them. We actually already created such a diagram in slides on this work, and agree that it would be nice to include it in the paper. We agree that more algebraic details can be pushed to the appendix to improve flow and free up space for other content that is more essential to the main body. And a table of symbols is also a nice idea."}, {"review_id": "vE4japZ3q1", "reviewer": "Reviewer_q21v", "summary": "Differential privacy (DP) provides theoretical upper bounds on information leakage from machine learning models, but real-world implementations can suffer from bugs or overly conservative bounds. This motivates the need for auditing methods to empirically estimate lower bounds on privacy loss.\n\nA promising approach is one-run auditing (ORA)—auditing by running the model once over a dataset with multiple modified entries. This paper addresses a key question left open by Steinke et al. (2024):\n\nHow tight can the bounds from ORA be?\n\nKey Contributions:\n\n1. Three Fundamental Gaps that limit ORA’s efficacy:\n\n- Non-worst-case element privacy: Poor privacy for a few elements doesn’t boost overall auditing efficacy.\n\n- Non-worst-case outputs: The algorithm may not produce privacy-violating outputs often enough.\n\n- Interference: Simultaneous changes in multiple data points dilute distinguishable effects.\n\n2. Theoretical Characterization:\n\n- The efficacy of ORA is formally defined and linked to relaxed versions of DP (like average-case and distributional variants).\n\n- Theorem 5.1/5.2: Show how efficacy is bounded below the true ε depending on interference and abstention.\n\n- Theorem 5.3: Gives necessary and sufficient conditions for ORA to be asymptotically tight.\n\n3. New Auditing Strategies:\n\n- Proposes improvements to reduce interference (e.g., allowing multiple elements per model dimension).\n\n- Introduces Adaptive ORA, where guesses are made sequentially and use feedback from prior guesses.\n\n4. Empirical Analysis on DP-SGD:\n\n- Shows empirically that ORA performance initially improves with more auditing elements per dimension, but then degrades due to interference.\n\nIn essence, this is a strong theoretical paper with clear motivation, rigorous proofs, and actionable insights for the privacy auditing community.", "questions": "- Your theoretical results assume uniform sampling over pairs in the one-run auditing setup. How sensitive are your efficacy/tightness results to this assumption? Could structured or real-world data distributions affect your conclusions?\n\n- You mention a trade-off between statistical power and confidence when allowing abstentions. Have you considered formalizing a method to optimally choose the abstention threshold based on desired confidence bounds or sample budget?\n\n- You cite f-DP auditing work (Mahloujifar et al.), but your efficacy bounds use max-divergence and average-case relaxations. Could similar bounds be derived under f-DP or Rényi DP assumptions?\n\n- Could your results inform DP system designers or regulators in how to audit deployed models? Should one-run auditing be recommended only with specific caveats?\n\n- Have you considered how post-hoc privacy auditing methods under distribution shift might complement one-run auditing, especially for mitigating the non-worst-case output gap?", "limitations": "- Assumes Pure DP: Focuses on ε-DP, not (ε, δ)-DP (though the authors justify it and acknowledge this in Section 1.1 as future work).\n\n- Abstention Strategy Not Fully Executed:\nWhile the theory discusses tradeoffs with abstentions, the practical implications for choosing abstention thresholds in realistic budgets are not deeply explored.\n\n- More in-depth related work would be good. Misses relevant recent work like PANORAMIA, which could have contextualized their limitations better.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 4, "strengths_and_weaknesses": "**Strengths:**\n\n- Comprehensive analysis of theoretical and practical limitations of ORA.\n\n- Novel theoretical framework to explain when and why ORA fails.\n\n- Provides actionable auditing improvements, like Adaptive ORA and refined guessing strategies.\n\n- Empirical results align well with theory, adding credibility.\n\n**What’s Related (but not redundant):**\nSteinke et al. [1]: Proposed and empirically validated ORA; showed its validity. Mahloujifar et al. [11]: Used f-DP to improve auditing bounds. Xiang et al. [12]: Information-theoretic study of ORA with a focus on interference, but lacks the full characterization and mitigation ideas this paper offers.\n\nWhat's good is that this is not a duplication of prior work. It is a clear step forward in understanding the limitations and achievable precision of one-run privacy auditing.\n\nMentioning prior post-hoc privacy auditing frameworks such as PANORAMIA (https://arxiv.org/abs/2402.09477) would strengthen the discussion more, as while it's not a true privacy audit, it offers alternative or complementary strategies to overcome the limitations of one-run auditing under distribution shift or unknown membership settings. I believe it offers a complementary lens to the one-shot vs. multi-shot auditing tradeoff and is worth mentioning.\n\n\n\n**Weaknesses and Limitations:**\n\n- Narrow empirical scope: Evaluations are limited to synthetic settings and DP-SGD.\n\n- Exploring real-world datasets or broader ML tasks (e.g., vision/NLP) may improve the quality of the paper for the future, but is not necessary at this point. Again, as future work, the practical implementation of adaptive ORA may help; while proposed in theory and appendices, it has not been demonstrated empirically.\n\n- No exploration of abstention strategies under real-world constraints:\n\n- How would one select a threshold for abstention under budget or privacy constraints?\n\n- Assumption-heavy analysis: Focus on pure ε-DP, assumes knowledge of S vector in ORA, and abstract gradients.", "was_revised": true, "final_justification": "The authors have sufficiently answered my concerns and also agreed to incorporate my suggestions. I increase my score, this is a technically solid work", "rebuttal": "Thanks for reading our work and sharing your detailed feedback!\n\nWe completely agree that our paper, which maps one-run auditing’s fundamental capabilities and limitations, highlights the importance of future work that will further explore the empirical performance of one-run auditing in a range of real-world settings. While this is out of scope for our paper, there is clearly a lot that could be done.\n\nWe would be glad to use some of the one additional page in the camera-ready version to move up some of the results we have on Adaptive One-Run Auditing from the appendix to the main body—on its validity, its maximal efficacy improvement, and on Adaptive ORA of the Count-In-Sets algorithm (the simplified algorithm that captures the essence of auditing DP-SGD). This will help the reader appreciate how AORA is not only immune to the increased interference when adding more elements per coordinate, but actually can only benefit from such added elements. We also have some additional experimental results on Adaptive ORA of DP-SGD (in the same setting as the other DP-SGD experiments) that we omitted from the submission; this felt like too much to try to squeeze into the paper to us, but if you think it is important, we can try to also fit it in.\n\nThanks for the PANORAMIA reference; we’ll check it out and incorporate it.\n\nWe actually don’t think our modeling assumptions (focus on pure DP, case-study with arbitrary gradients) represent a weakness. Since our goal is to expose the limitations of one-run auditing, we intentionally study a setting that is favorable to one-run auditing. \n\nThe $S$ vector is randomly sampled to determine the input dataset and the guesser has no access to it, as in the ORA setting that Steinke et al. define.\n\nThanks for the formatting and notation suggestions—those are well-taken and we’ll incorporate them.\n\nRegarding your specific questions:\n\n- **Data distribution** - We follow the setting of Steinke et al. (“Privacy Auditing with One (1) Training Run”) in which the canaries are sampled independently uniformly. A recent work by Swanberg et al. (“Beyond the Worst Case: Extending Differential Privacy Guarantees to Realistic Adversaries“, Sections 3.1 and 3.2) extends their method to arbitrary product distributions. The gaps that we discuss also exist with this sampling scheme - the guesser still faces non-worst case output, non-worst-privacy for elements, and it still suffers from the uncertainty about the other elements. Therefore, our analysis can be extended to this case, taking into account the non-uniform input distribution.\n\n    Auditing with real data (as canaries or as non-canaries) does not change the sampling (the distribution of the sampled vector S) so our analysis covers this case.\n\n- **Threshold selection** - Choosing the threshold is an interesting problem, and it is a non-trivial task even in classic auditing. However, it is somewhat orthogonal to our focus on the inherent limitations of ORA. As Steinke et al. (“Privacy Auditing with One (1) Training Run”, Section 6) point out, one can use sample splitting to choose an optimal guessing threshold, that is, use a different set of observations to select the threshold and another set of the data for the auditing itself. Formalizing a way to choose the threshold without sample splitting is an interesting research direction.\n\n- **f-DP and Renyi-DP** - We analyze the ORA method of Steinke et al. (“Privacy Auditing with One (1) Training Run”), which audits pure DP and approximate DP. As we discuss in the introduction, we focus on auditing pure DP to zoom in on the limitations of ORA, as auditing approximate DP may create additional gaps. The work of Mahloujifar et al. on auditing f-DP in one run focuses on bridging these additional gaps resulting from the lack of tightness in the approximate DP analysis, and hence doesn’t speak to the pure-DP gaps that our paper studies. Our work shows that average-case relaxations characterize the efficacy of ORA, even though ORA aims to measure the pure DP level, which is characterized by the max divergence.\n\n- **Informing auditing in practice** - Great point, thanks. We will add something on this to the conclusion. Our results indeed can be used to guide a privacy auditor on when to use ORA, how to use it, and how to interpret the results:\n    - ORA should be used only if ORA has high optimal efficacy with respect to the audited algorithm. When auditing algorithms that severely suffer from the gaps of ORA (e.g., an algorithm for releasing noisy counting queries), multi-run auditing should be used. \n    - Our results can guide the choice of the canaries and the guesser, and our multiple canaries per dimension and Adaptive ORA approaches can increase the efficacy of auditing. \n    - Our results highlight that auditing results should not be treated as privacy level estimations, but rather only as lower bounds, and should be interpreted in light of the optimal efficacy.\n\n    When using ORA, we recommend reporting the number of canaries used, the optimal efficacy of ORA with respect to the audited algorithm, and other details which are important for the interpretation of the results (aligned with the “Auditing Card” approach proposed by Annamalai et al. (“The Hitchhiker’s Guide to Efficient, End-to-End, and Tight DP Auditing”, Section 7.3).\n\n- **Auditing under distribution shift** - We have not considered post-hoc privacy auditing methods under distribution shift. We will explore this complementary approach."}]

Author rebuttal:

Meta-review: The reviewers all agree that this paper provides new insights into the problem of auditing differential private algorithms. The results focus on a recent paradigm called "one-run privacy auditing," which has become popular in the differential privacy literature. The fundamental barriers highlighted in this paper can point to new directions for privacy auditing.
Decision: Accept (spotlight)