Auditing $f$-Differential Privacy in One Run

## Abstract

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

## 1 Introduction

Differentially private machine learning Chaudhuri et al. (); Abadi et al. () has emerged as a principled solution to learning models from private data while still preserving privacy. Differential privacy Dwork () is a cryptographically motivated definition, which requires an algorithm to possess certain properties: specifically, a randomized mechanism is differentially private if it guarantees that the participation of any single person in the dataset does not impact the probability of any outcome by much.

Enforcing this guarantee requires the algorithm to be carefully designed and rigorously analyzed. The process of designing and analyzing such algorithms is prone to errors and imperfections as has been noted in the literature Tramer et al. (). A result of this is that differentially private mechanisms may not perform as intended, either offering less privacy than expected due to flaws in mathematical analysis or implementation, or potentially providing stronger privacy guarantees that are not evident through a loose analysis.

Empirical privacy auditing (Ding et al., ; Nasr et al., ; Jagielski et al., ) has emerged as a critical tool to bridge this gap. By experimentally assessing the privacy of mechanisms, empirical auditing allows for the verification of privacy parameters. Specifically, an audit procedure is a randomized algorithm that takes an implementation of a mechanism $M$, runs it in a black-box manner, and attempts to test a privacy hypothesis (such as, a differential privacy parameter). The procedure outputs 0 0 if there is sufficient evidence that the mechanism does not satisfy the hypothesized guarantees and $1$ otherwise. The audit mechanism must possess two essential properties: 1) it must have a *provably* small false-negative rate, ensuring that it would not erroneously reject a truly differentially private mechanism, with high probability; 2) it needs to *empirically* exhibit a "reasonable" false positive rate, meaning that when applied to a non-differentially private mechanism, it would frequently reject the privacy hypothesis. The theoretical proof of the false positive rate is essentially equivalent to privacy accounting (Abadi et al., ; Dong et al., ; Mironov, ), which is generally thought to be impossible in a black-box manner Zhu et al. ().

The prior literature on empirical audits of privacy consists of two lines of work, each with its own set of limitations. The first line of work (Ding et al., ; Jagielski et al., ; Tramer et al., ; Nasr et al., ) runs a differentially private algorithm multiple times to determine if the privacy guarantees are violated. This is highly computationally inefficient for most private machine learning use-cases, where running the algorithm a single time involves training a large model.

Recent work (Steinke et al., ) remove this limitation by proposing an elegant auditing method that runs a differentially private training algorithm a single time. In particular, they rely on the randomness of training data to obtain bounds on the false negative rates of the audit procedure. A key limitation of the approach in Steinke et al. () is that their audit procedure is sub-optimal in the sense that there is a relatively large gap between the true privacy parameters of mainstream privacy-preserving algorithms (e.g., Gaussian mechanism) and those reported by their auditing algorithm.

In this work, we propose a novel auditing procedure that is computationally efficient and accurate. Our method requires only a single run of the privacy mechanism and leverages the $f$-DP curve Dong et al. (), which allows for a more fine-grained accounting of privacy than the traditional reliance on $\epsilon,\delta$ parameters.
By doing so, we provide a tighter empirical assessment of privacy.

We experiment with our approach on both simple Gaussian mechanisms as well as a model trained on real data witth DP-SGD. Our experiments show that our auditing procedure can significantly outperform that of Steinke et al. () (see Figure 1). This implies that better analysis may enable relatively tight auditing of differentially privacy guarantees in a computationally efficient manner in the context of large model training.

#### Technical overview:

We briefly summarize the key technical components of our work and compare it with that of Steinke et al. (2023). Their auditing procedure employed a game similar to a membership inference process: the auditor selects a set of canaries and, for each canary, decides whether to inject it into the training set with independent probability 0.5. Once model training is completed, the auditor performs a membership inference attack to determine whether each canary was included. The number of correct guesses made by the adversary in this setting forms a random variable. The key technical contribution of Steinke et al. was to establish a tail bound on this random variable for mechanisms satisfying $(\epsilon)$-DP. Specifically, they demonstrated that the tail of this random variable is bounded by that of a binomial distribution, $\mathbf{binomial}(n,p)$, where $n$ is the number of canaries and $p=\frac{e^{\epsilon}}{e^{\epsilon}+1}$. To extend this analysis to approximate DP mechanisms, they further showed that the probability of the adversary’s success exceeding this tail bound is at most $O(n\cdot\delta)$.

Steinke et al. identified a limitation of their approach in auditing specific mechanisms, such as the Gaussian mechanism. To address this, we focus on auditing the entire privacy curve of a mechanism, rather than just auditing $(\epsilon,\delta)$. Our solution comprises three key technical steps:

- 1.
We derive an upper bound on the adversary’s success in correctly guessing a specific canary for mechanisms satisfying $f$-DP. This bound is an improved version of the result by Hayes et al. () for bounding training data reconstruction in DP mechanisms. However, this is insufficient, as the adversary’s guesses could be dependent, potentially leading to correlated successes (e.g., correctly or incorrectly guessing all samples).
- 2.
To address the issue of dependency, we refine our analysis by defining $p_{i}$ as the probability of the adversary making exactly $i$ correct guesses. We derive a recursive relation that bounds $p_{i}$ based on $p_{1},\dots,p_{i-1}$. This recursive bound is the main technical novelty of our work. To derive this bound, we consider two conditions: the adversary correctly guesses the first canary or not. In the first case, we use our analysis from Step 1 to bound the probability of making $i-1$ correct guesses given that the first guess was correct. For the incorrect guess case, we perform a combinatorial analysis to eliminate the condition. This analysis uses the fact that shuffling of the canaries does not change the probabilities of making $i$ correct guesses. We note that it is crucial not to use the analysis of Step 1 for both cases. This is because the analysis of Step 1 cannot be tight for both cases at the same time. Finally, leveraging the convexity of trade-off functions and applying Jensen’s inequality, we derive our final recursive relation. To the best of our knowledge, This combination of trade-off function with shuffling is a new technique and could have broader applications.
- 3.
Finally, we design an algorithm that takes advantage of the recursive relation to numerically calculate an upper bound on the tail of the distribution. The algorithm is designed carefully so that we do not need to invoke the result of step 2 for very small events.

We also generalize our analysis to a broader notion of canary injection and membership inference. Specifically, we utilize a reconstruction game where the auditor can choose among $k$ options for each canary point, introducing greater entropy for each choice. This generalization allows for auditing mechanisms with fewer canaries.

In the rest of the paper, we first introduce the notions of $f$-DP and explain what auditing based on $f$-DP entails. We then present our two auditing procedures, which are based on membership inference and reconstruction attacks (Section 2). In Section 3, we provide a tight analysis of our audit’s accuracy based on $f$-DP curves. Finally, in Section 4, we describe the experimental setup used to compare the bounds.

## 2 Auditing f 𝑓 f italic_f - differential privacy

Auditing privacy involves testing a "privacy hypothesis" about an algorithm $M$. Different mathematical forms can be used for a "privacy hypothesis," but they all share the common characteristic of being about an algorithm/mechanism $M$. For example, one possible hypothesis is that applying SGD with specific hyperparameters satisfies some notion of privacy. With this in mind, the privacy hypothesis are often mathematical constraints on the sensitivity of the algorithm’s output to small changes in its input. The most well-known definition among these is (approximate) differential privacy.

###### Definition 1 .

A mechanism $M$ is $(\epsilon,\delta)$-DP if for all neighboring datasets $\mathcal{S},\mathcal{S}^{\prime}$ with $|\mathcal{S}\Delta\mathcal{S}^{\prime}|=1$ and all measurable sets $T$, we have
$\Pr[M(\mathcal{S})\in T]\leq e^{\epsilon}\Pr[M(\mathcal{S}^{\prime})\in T]+\delta.$

In essence, differential privacy ensures that the output distribution of the algorithm does not depend heavily on a single data point. Based on this definition, one can hypothesize that a particular algorithm satisfies differential privacy with certain $\epsilon$ and $\delta$ parameters. Consequently, auditing differential privacy involves designing a test for this hypothesis. We will later explore the desired properties of such an auditing procedure. However, at present, we recall a stronger notion of privacy known as $f$-differential privacy.

###### Definition 1 .

#### Notation

For a function $f\colon X\to\mathbb{R}$ we use $\bar{f}$ to denote the function $\bar{f}(x)=1-f(x)$.

###### Definition 2 .

A mechanism $\mathcal{M}$ is $f$-DP if for all neighboring datasets $\mathcal{S},\mathcal{S}^{\prime}$ and all $|\mathcal{S}\Delta\mathcal{S}^{\prime}|=1$ measurable sets $T$ we have

$$ $\Pr[M(\mathcal{S})\in T]\leq\bar{f}\big{(}\Pr[M(\mathcal{S}^{\prime})]\in T] \big{)}.$ $$

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

###### Proposition 3 .

A mechanism is $(\epsilon,\delta)$-DP if it is $f$-DP with respect to $\bar{f}(x)=e^{\epsilon}\cdot x+\delta$.

Although the function $f$ could be an arbitrary function, without loss of generality, we only consider a specific class of functions in this notion.

###### Remark 4 .

Whenever we say that a mechanism satisfies $f$-DP, we implicitly imply that $f$ is a valid trade-off function . That is, $f$ is defined on domain $[0,1]$ and has a range of $[0,1]$. Moreover, $f$ is a decreasing and convex with $f(x)\leq 1-x$ for all $x\in[0,1]$. We emphasize that this is without loss of generality. That is, if a mechanism is $f$-DP for a an arbitrary function $f:[0,1]\to[0,1]$, then it is also $f^{\prime}$-DP for valid trade-off function $f^{\prime}$ with $f^{\prime}(x)\leq f(x)$ for all $x\in[0,1]$ (See Proposition 2.2 in Dong et al. ()).

###### Definition 5 (Order of $f$ -DP curves) .

For two trade-off functions $f_{1}$ and $f_{2}$, we say $f_{1}$ is more private than $f_{2}$ and denote it by $f_{1}\geq f_{2}$ iff $f_{1}(x)\geq f_{2}(x)$ for all $x\in[0,1]$. Also, for a family of trade-off functions $F$, we use $maximal(F)$ to denote the set of maximal elements w.r.t to the privacy relation. Note that $F$ could be a partial ordered set, and the set of maximal points could have more than a single element.

Now that we have defined our privacy hypothesis, we can turn our attention to auditing these notions.

###### Definition 6 (Auditing $f$ -DP) .

An audit procedure takes the description of a mechanism $\mathcal{M}$, a trade-off function $f$, and outputs a bit that determines whether the mechanism satisfies $f$-DP or not. We define the audit procedure as a two-step procedure.

- •
$game\colon M\to O$, In this step, the auditor runs a potentially randomized experiment/game using the description of mechanism $\mathcal{M}\in M$ and obtains some observation $o\in O$.
- •
$evaluate:O\times F\to\{0,1\}$, In this step, the auditor will output a bit $b$ based on an observation $o$ and a trade-off function $f$. This audit operation tries to infer whether the observation $o$ is “likely” for a mechanism that satisfies $f$-DP.

The audit procedure is $\psi$-accurate if for all mechanism $\mathcal{M}$ that satisfy $f$-DP, we have

$$ $\Pr_{o\leftarrow game(\mathcal{M})}[evaluate(o,f)=1]\geq\psi.$ $$

Note that we are defining the accuracy only for positive cases. This is the only guarantee we can get from running attacks. For guarantees in negative cases, we need to perform a proper accounting of the mechanism Wang et al. ().

###### Definition 2 .

###### Proposition 3 .

###### Remark 4 .

###### Definition 5 (Order of f 𝑓 f italic_f -DP curves) .

###### Definition 6 (Auditing f 𝑓 f italic_f -DP) .

#### Auditing f 𝑓 f italic_f -DP vs DP:

$f$-DP can be viewed as a collection of DP parameters, where instead of considering $(\epsilon,\delta)$ as fixed scalars, we treat $\epsilon$ as a function of $\delta$. For any $\delta\in[0,1]$, there exists an $\epsilon(\delta)$ such that the mechanism satisfies $(\epsilon(\delta),\delta)$-DP. The $f$-DP curve effectively represents the entire privacy curve rather than a single $(\epsilon,\delta)$ pair. Thus, auditing $f$-DP can be expected to be more effective, as there are more constraints that need to be satisfied. A naive approach for auditing $f$-DP is to perform an audit for approximate DP at each $(\epsilon,\delta)$ value along the privacy curve, rejecting if any of the audits fail. However, this leads to suboptimal auditing performance. First, the auditing analysis involves several inequalities that bound the probabilities of various events using differential privacy guarantees. The probability of these events could take any number between $[0,1]$. Using a single $(\epsilon,\delta)$ value to bound the probability of all these events cannot be tight because the linear approximation of privacy curve is tight in at most a single point. Hence, the guarantees of $(\epsilon,\delta)$-DP cannot be simultaneously tight for all events. However, with $f$-DP, we can obtain tight bounds on the probabilities of all events simultaneously. Second, For each $(\epsilon,\delta)$ we have a small possibility of incorrectly rejecting the privacy hypothesis. So if we audit privacy for $(\epsilon(\delta),\delta)$ independently, we will reject any privacy hypothesis with probability $1.0$. This challenge can be potentially resolved by using correlated randomness, but that requires a new analysis.

Next, we formally define the notion of empirical privacy Nasr et al. () based on an auditing procedure.
This notion essentially provides the best privacy guarantee that is not violated by auditors’ observation from a game setup.

###### Definition 7 (Empirical Privacy) .

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

$$ $F_{o}=maximal(\{f\in F;evaluate(o,f)=1\})$ $$

where the maximal set is constructed according to Definition 5. Then, the empirical privacy of the mechanism at a particular $\delta$ is defined as

$$ $\epsilon(\delta)=\min_{f\in F_{o}}\max_{x\in[0,1]}\frac{1-f(x)-\delta}{x}.$ $$

Note that the empirical privacy $\epsilon(\delta)$ is a function of the observation $o$. Since, $o$ itself is a random variable, then $\epsilon(\delta)$ is also a random variable.

###### Definition 7 (Empirical Privacy) .

#### How to choose the family of trade-off functions?

The family of trade-off functions should be chosen based on the expectations of the true privacy curve. For example, if one expects the privacy curve of a mechanism to be similar to that of a Gaussian mechanism, then they would choose the set of all trade-off functions imposed by a Gaussian mechanism as the family. For example, many believe that in the hidden state model of privacy Ye and Shokri (), the final model would behave like a Gaussian mechanism with higher noise than what is expected from the accounting in the white-box model (where we assume we release all the intermediate models). Although we may not be able to prove this hypothesis , we can use our framework to calculate the empirical privacy, while assuming that the behavior of the final model would be similar to that of a Gaussian mechanism.

### 2.1 Guessing games

Here, we introduce the notion of guessing games which is a generalization of membership inference attacks Nasr et al. (), and closely resembles the reconstruction setting introduced in Hayes et al. ().

###### Definition 8 .

Consider a mechanism $M:[k]^{m}\to\Theta$. In a guessing game we first sample an input dataset $\mathbf{u}\in[k]^{m}$ from an arbitrary distribution. We run the mechanism to get $\theta\sim M(\mathbf{u})$. Then a guessing adversary $A:\Theta\to([k]\cup\{\bot\})^{m}$ tries to guess the input to the mechanism from the output. We define

- •
The number of guesses by
$c^{\prime}=\sum_{i=1}^{m}\mathbf{I}\big{(}A(\theta)_{i}\neq\bot\big{)}.$
- •
The number of correct guesses by
$c=\sum_{i=1}^{m}\mathbf{I}\big{(}A(\theta)_{i}=\mathbf{u}_{i}\big{)}.$

Then we output $(c,c^{\prime})$ as the output of the game.

These guessing games are integral to our auditing strategies. We outline two specific ways to instantiate the guessing game. The first procedure is identical to that described in the work of Steinke et al. () and resembles membership inference attacks. The second auditing algorithm is based on the reconstruction approach introduced by Hayes et al. (). In Section 3, we present all of our results in the context of the general notion of guessing games, ensuring that our findings extend to both the membership inference and reconstruction settings.

###### Definition 8 .

#### Auditing by membership inference:

Algorithm 1 describes the auditing procedure that is based on membership inference. In this setup, we have a fixed training set $\mathcal{T}$ and a set of canaries $\mathcal{C}$. We first samples a subset $\mathcal{S}$ of the canary examples using Poisson sampling and then use the mechanism $\mathcal{M}$ once to get a model $\theta\sim\mathcal{M}(\mathcal{T}\cup\mathcal{S})$. Then the adversary $A$ inspects $\theta$ and tries to find examples that were present in $\mathcal{S}$. Observe that this procedure is a guessing game with $k=2$ and $m=|\mathcal{C}|$. This is simply because the adversary is guessing between two choices for each canary, it is either included or not included.
Note that this procedure is modular, we can use any $\mathcal{T}$ and $\mathcal{C}$ for the training set and canary set. We can also use any attack algorithm $A$.

We note that membership inference attacks have received a lot of attention recently (Homer et al., ; Shokri et al., ; Leino and Fredrikson, ; Bertran et al., ; Hu et al., ; Matthew et al., ; Duan et al., ; Zarifzadeh et al., ). These attack had a key difference from our attack setup and that is the fact that there is only a single example that the adversary is trying to make the inference for. Starting from the work of (Shokri et al., ), researchers have tried to improve attacks in various settings (Ye et al., ; Zarifzadeh et al., ). For example, using calibration techniques has been an effective way to improve membership inference attacks (Watson et al., ; Carlini et al., ). Researchers have also changed their focus from average case performance of the attack to the tails of the distribution and measured the precision at low recall values (Ye et al., ; Nasr et al., ).

A substantial body of research has also explored the relationship between membership inference attacks and differential privacy (Sablayrolles et al., ; Mahloujifar et al., ; Balle et al., ; Bhowmick et al., ; Stock et al., ; Balle et al., ; Guo et al., ; Kaissis et al., , ), using this connection to audit differential privacy (Steinke et al., ; Pillutla et al., ; Jagielski et al., ; Ding et al., ; Bichsel et al., ; Nasr et al., , ; Steinke et al., ; Tramer et al., ; Bichsel et al., ; Lu et al., ; Andrew et al., ; Cebere et al., ; Chadha et al., ). Some studies have investigated empirical methods to prevent membership inference attacks that do not rely on differential privacy (Hyland and Tople, ; Jia et al., ; Chen and Pattabiraman, ; Li et al., ; Tang et al., ; Nasr et al., ). An intriguing avenue for future research is to use the concept of empirical privacy to compare the performance of these empirical methods with provable methods, such as DP-SGD.

Figure: Algorithm 1 Membership inference in one run game

#### Auditing by reconstruction:

We also propose an alternative way to perform auditing by reconstruction attacks. This setup starts with a training set $\mathcal{S}_{t}$, similar to the membership inference setting. Then, we have a family of $m$ canary sets $\{\mathcal{S}_{c}^{i};i\in[m]\}$ where each $\mathcal{S}_{c}^{i}$ contains $k$ distinct examples. Before training, we construct a set $\mathcal{S}_{s}$ of size $m$ by uniformly sampling an example from each $\mathcal{S}_{c}^{i}$. Then, the adversary tries to find out which examples were sampled from each canary set $\mathcal{S}_{c}^{i}$ by inspecting the model. We recognize that this might be different from what one may consider a true “reconstruction attack”, because the adversary is only performing a selection. However, if you consider the set size to be arbitrary large, and the distribution on the set to be arbitrary, then this will be general enough to cover various notions of reconstruction. We also note that Hayes et al. () use the same setup to measure the performance of the reconstruction attacks.

Figure: Algorithm 2 Reconstruction in one run game

## 3 Implications of f 𝑓 f italic_f -DP for guessing games

In this section, we explore the implications of $f$-DP for guessing games. Specifically, we focus on bounding the probability of making more than $c$ correct guesses for adversaries that make at most $c^{\prime}$ guesses.
We begin by stating our main theorem, followed by an explanation of how it can be applied to audit the privacy of a mechanism.

###### Theorem 9 .

[Bounds for adversary with bounded guesses]
Let $M:[k]^{m}\to\Theta$ be a $f$-DP mechanism. Let $\mathbf{u}$ be a random variable uniformly distributed on $[k]^{m}$. Let $A\colon\Theta\to([k]\cup\{\bot\})^{m}$ be a guessing adversary which always makes at most $c^{\prime}$ guesses, that is

$$ $\forall\theta\in\Theta,\Pr\Big{[}\Big{(}\sum_{i=1}^{m}I\big{(}A(\theta)_{i} \neq\bot\big{)}\Big{)}>c^{\prime}\Big{]}=0,$ $$

and let $\mathbf{v}\equiv A(M(\mathbf{u}))$. Define $p_{i}=\Pr[\sum_{j\in[m]}\mathbf{I}(\mathbf{u}_{j}=\mathbf{v}_{j})=i]$. For all subset of values $T\subseteq[c^{\prime}]$, we have

$$ $\sum_{i\in T}\frac{i}{m}p_{i}\leq\bar{f}(\frac{1}{k-1}\sum_{i\in T}\frac{c^{ \prime}-i+1}{m}p_{i-1}).$ $$

This Theorem, which we consider to be our main technical contribution, provides a nice invariant that bounds the probability $p_{i}$ (probability of making exactly $i$ correct guesses) based on the value of other $p_{j}$s. Imagine $P_{f}$ to be a set of vectors $p=(p_{1},\dots,p_{c^{\prime}})$ that could be realized for an attack on a $f$-DP mechanism. Theorem 9 significantly confines this set. However, this still does not resolve the auditing task. We are interested in bounding $\max_{p\in P_{f}}\sum_{i=c}^{c^{\prime}}{p_{i}}$, the maximum probability that an adversary can make more than $c$ correct guesses for an $f$-DP mechanism. Next, we show how we can algorithmically leverage the limitations imposed by Theorem 9 and calculate an upper bound on $\max_{p\in P_{f}}\sum_{i=c}^{c^{\prime}}{p_{i}}$.

###### Theorem 9 .

### 3.1 Numerically bounding the tail

In this subsection, we specify our procedure for bounding the tail of the distribution and hence the accuracy of our auditing procedure. Our algorithm needs oracle access to $f$ and $\bar{f}$ and decides an upper bound on the probability of an adversary making $c$ correct guesses in a guessing game with alphabet size $k$ and a mechanism that satisfies $f$-DP. This algorithm relies on the confinement imposed by Theorem 9. Note that Algorithm 3 is a decision algorithm, it takes a value $\tau$ and decide if the probability of making more than $c$ correct guesses is less than or equal to $\tau$. We can turn this algorithm to a estimation algorithm by performing a binary search on the value of $\tau$. However, for our use cases, we are interested in a fixed $\tau$. This is because we (similar to (Steinke et al., )) want to set the accuracy of our audit to be a fixed value such as $0.95$.

Figure: Algorithm 3 Numerically deciding an upper bound probability of making more than $c$ correct guesses

###### Theorem 10 .

If Algorithm
3 returns True on inputs $\bar{f},k,m,c,c^{\prime}$ and $\tau$, then for any $f$-DP mechanism $M\colon[k]^{m}\to\Theta$, any guessing adversary $A\colon\Theta\to([k]\cup\{\bot\})^{m}$ with at most $c^{\prime}$ guesses, defining $\mathbf{u}$ to be uniform over $[k]^{m}$, and setting $\mathbf{v}\equiv A\big{(}M(\mathbf{u})\big{)}$, we have
$\Pr[\big{(}\sum_{i=1}^{m}\mathbf{I}(\mathbf{u}_{i}=\mathbf{v}_{i})\big{)}\geq c
]\leq\tau.$

In a nutshell, this algorithm tries to obtain an upper bound on the sum $p_{c}+p_{c+1}+\dots,p_{c^{\prime}}.$ We assume this probability is greater than $\tau$, and we obtain lower bound on $p_{c-1}+p_{c}+\dots+p_{c^{\prime}}$ based on this assumption. We keep doing this recursively until we have a lower bound on $p_{0}+\dots+p_{c^{\prime}}$. If this lower bound is greater than $1$, then we have a contradiction and we return true. The detailed proof of this Theorem is involved and requires careful analysis. We defer the full proof of Theorem to appendix.

###### Theorem 10 .

#### Auditing f 𝑓 f italic_f -DP with Algorithm 3 :

When auditing the $f$-DP for a mechanism, we assume we have injected $m$ canaries, and ran an adversary that is allowed to make $c^{\prime}$ guesses and recorded that the adversary have made $c$ correct guesses. In such scenario, we will reject the hypothesized privacy of the mechanism if the probability of this observation is less than a threshold $\tau$, which we by default set to $0.05$. To this end, we just call Algorithm 3 with parameters $c$, $c^{\prime}$, $m$, $\tau=0.05$ and $f$. Then if the algorithm returns True, we will reject the privacy hypothesis and otherwise accept.

#### Empirical privacy:

Although auditing in essence is a hypothesis testing, previous work has used auditing algorithms to calculate empirical privacy as defined in definition 7. In this work, we follow the same route. Specifically, we consider an ordered set of privacy hypotheses $h_{1},\dots,h_{w}$ as our family of $f$-DP curves. These sets are ordered in their strength, meaning that any mechanism that satisfies $h_{i}$, would also satisfy $h_{j}$ for all $j<i$. Then, we would report the strongest privacy hypothesis that passes the test as the empirical privacy of the mechanism.

### 3.2 Proof outline

In this subsection, we outline the main ingredients we need to prove our Theorem 9. We also provide the full proof for a simplified version of Theorem 9 using these ingredients. First, we have a Lemma that bounds the probability of any event conditioned on correctly guessing a single canary.

###### Lemma 11 .

Let $M:[k]^{m}\to\Theta$ be a mechanism that satisfies $f$-DP. Also let $A\colon\Theta\to([k]\cup\{\bot\})^{m}$ be a guessing attack. Let $\mathbf{u}$ be a random variable uniformly distributed over $[k]^{m}$ and let $\mathbf{v}\equiv A\big{(}M(\mathbf{u})\big{)}$. Then for any subset $E\subseteq\Theta$ we have

$$ $f^{{}^{\prime\prime}}_{k}\Big{(}\Pr\big{[}M(\mathbf{u})\in E\big{]}\Big{)}\leq \Pr\big{[}M(\mathbf{u})\in E\text{\leavevmode\nobreak\ and\leavevmode\nobreak \ }u_{1}=v_{1}\big{]}\leq f^{{}^{\prime}}_{k}\Big{(}\Pr\big{[}M(\mathbf{u})\in E \big{]}\Big{)}$ $$

where

$$ $f^{\prime}_{k}(x)=\sup\{\alpha;\alpha+f(\frac{x-\alpha}{k-1})\leq 1\}\text{ \leavevmode\nobreak\ \leavevmode\nobreak\ and\leavevmode\nobreak\ \leavevmode \nobreak\ \leavevmode\nobreak\ }f^{\prime\prime}_{k}(x)=\inf\{\alpha;(k-1)f( \alpha)+x-\alpha)\leq 1\}.$ $$

This Lemma which is a generalization and an improvement over the main Theorem of (Hayes et al., ), shows that the probability of an event cannot change too much if we condition on the success of adversary on one of the canaries. Note that this Lemma immediately implies a bound on the expected number of correct guesses by any guessing adversary (by just using linearity of expectation). However, here we are not interested in expectations. Rather, we need to derive tail bounds. The proof of Theorem 9 relies on some key properties of the $f^{\prime}$ and $f^{\prime\prime}$ functions defined in the statement of Lemma 11. These properties are specified in the following Proposition and proved in the Appendix.

###### Proposition 12 .

The functions $f^{\prime}_{k}$ as defined in Lemma 11 is increasing and concave. The function $f^{\prime\prime}_{k}$ as defined in Lemma 11 is increasing and convex.

Now, we are ready to outline the proof of a simplified variant of our Theorem 9 for adversaries that make a guess on all canaries. This makes the proof much simpler and enables us to focus more on the key steps in the proof.

###### Theorem 13 (Special case of 9 ) .

Let $M:[k]^{m}\to\Theta$ be a $f$-DP mechanism. Let $\mathbf{u}$ be a random variable uniformly distributed on $[k]^{m}$. Let $A\colon\Theta\to[k]^{m}$ be a guessing adversary and let $\mathbf{v}\equiv A(M(\mathbf{u}))$. Define $p_{i}=\Pr\Big{[}(\sum_{j\in[m]}\mathbf{I}\big{(}\mathbf{u}_{j}=\mathbf{v}_{j})
\big{)}=i\Big{]}$. For all subset of values $T\subseteq[m]$, we have

$$ $\sum_{i\in T}\frac{i}{m}p_{i}\leq\bar{f}(\frac{1}{k-1}\sum_{i\in T}\frac{m-i+1 }{m}p_{i-1})$ $$

###### Proof.

Let us define a random variable $\mathbf{t}=(\mathbf{t}_{1},\dots,\mathbf{t}_{m})$ which is defined as $\mathbf{t}_{i}=\mathbf{I}(\mathbf{u}_{i}=\mathbf{v_{i}})$ We have

$$ $\displaystyle p_{c}$ $\displaystyle=\Pr[\sum_{i=1}^{m}\mathbf{t}_{i}=c]=\Pr[\sum_{i=2}^{m}\mathbf{t} _{i}=c-1\text{\leavevmode\nobreak\ and\leavevmode\nobreak\ }\mathbf{t}_{1}=1]+ \Pr[\sum_{i=2}^{m}\mathbf{t}_{i}=c\text{\leavevmode\nobreak\ and\leavevmode \nobreak\ }\mathbf{t}_{1}=0]$ $$

Now by Lemma 11 we have
$\Pr[\sum_{i=2}^{m}\mathbf{t}_{i}=c-1\text{\leavevmode\nobreak\ and\leavevmode
\nobreak\ }\mathbf{t}_{1}=1]\leq f^{\prime}_{k}(\sum_{i=2}^{m}\mathbf{t}_{i}=c
-1).$
This is a nice invariant that we can use but $\sum_{i=2}^{m}\mathbf{t}_{i}=c-1$ could be really small depending on how large $m$ is. To strengthen the bound we sum all $p_{c}$’s for $c\in T$, and then apply the lemma on the aggregate. That is

$$ $\displaystyle\sum_{j\in T}p_{j}$ $\displaystyle=\sum_{j\in T}\Pr[\sum_{i=1}^{m}\mathbf{t}_{i}=j]=\sum_{j\in T} \Pr[\sum_{i=2}^{m}\mathbf{t}_{i}=j\text{\leavevmode\nobreak\ and\leavevmode \nobreak\ }\mathbf{t}_{1}=0]+\sum_{j\in T}\Pr[\sum_{i=2}^{m}\mathbf{t}_{i}=j-1 \text{\leavevmode\nobreak\ and\leavevmode\nobreak\ }\mathbf{t}_{1}=1]$ $\displaystyle=\Pr[\sum_{i=2}^{m}\mathbf{t}_{i}\in T\text{\leavevmode\nobreak\ and\leavevmode\nobreak\ }\mathbf{t}_{1}=0]+\Pr[1+\sum_{i=2}^{m}\mathbf{t}_{i} \in T\text{\leavevmode\nobreak\ and\leavevmode\nobreak\ }\mathbf{t}_{1}=1]$ $$

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

$$ $\displaystyle\sum_{j\in T}p_{j}\leq\Pr[\sum_{i=2}^{m}\in T\text{\leavevmode \nobreak\ and\leavevmode\nobreak\ }\mathbf{t}_{1}=0]+f^{\prime}_{k}(\Pr[1+\sum _{i=2}^{m}\mathbf{t}_{i}\in T]).$ $$

Now we use a trick to make this cleaner. We use the fact that this inequality is invariant to the order of indices. So we can permute $\mathbf{t_{i}}$’s and the inequality still holds. We have,

$$ $\displaystyle\sum_{j\in T}p_{j}$ $\displaystyle\leq\operatorname*{E}_{\pi\sim\Pi[m]}[\Pr[\sum_{i=2}^{m}\mathbf{t }_{\pi(i)}\in T\text{\leavevmode\nobreak\ and\leavevmode\nobreak\ }\mathbf{t}_ {\pi(1)}=0]]+\operatorname*{E}_{\pi\sim\Pi[m]}[f^{\prime}_{k}(\Pr[1+\sum_{i=2} ^{m}\mathbf{t}_{\pi(i)}\in T])]$ $\displaystyle\leq\operatorname*{E}_{\pi\sim\Pi[m]}[\Pr[\sum_{i=2}^{m}\mathbf{t }_{\pi(i)}\in T\text{\leavevmode\nobreak\ and\leavevmode\nobreak\ }\mathbf{t}_ {\pi(1)}=0]]+f^{\prime}_{k}(\operatorname*{E}_{\pi\sim\Pi[m]}[\Pr[1+\sum_{i=2} ^{m}\mathbf{t}_{\pi(i)}\in T]]).$ $$

Now we perform a double counting argument. Note that when we permute the order $\sum_{i=2}^{m}\mathbf{t}_{\pi(i)}=j\text{\leavevmode\nobreak\ and\leavevmode
\nobreak\ }\mathbf{t}_{\pi(1)}=0$ counts each instance $t_{1},\dots,t_{m}$ with exactly $j$ non-zero locations, for exactly $(m-j)\times(m-1)!$ times. Therefore, we have

$$ $\operatorname*{E}_{\pi\sim\Pi[m]}[\Pr[\sum_{i=2}^{m}\mathbf{t}_{\pi(i)}\in T \text{\leavevmode\nobreak\ and\leavevmode\nobreak\ }\mathbf{t}_{\pi(1)}=0]]= \sum_{j\in T}\frac{m-j}{m}p_{j}.$ $$

With a similar argument we have,

$$ $\displaystyle\operatorname*{E}_{\pi\sim\Pi[m]}[\Pr[1+\sum_{i=2}^{m}\mathbf{t}_ {\pi(i)}\in T]]$ $\displaystyle=\sum_{j\in T}\frac{m-j+1}{m}p_{j-1}+\frac{j}{m}p_{j}.$ $$

Then, we have

$$ $\displaystyle\sum_{j\in T}p_{j}$ $\displaystyle\leq\sum_{j\in T}\frac{m-j}{m}p_{j}+f^{\prime}_{k}(\sum_{j\in T} \frac{j}{m}p_{j}+\frac{m-j+1}{m}p_{j-1}).$ $$

And this implies

$$ $\displaystyle\sum_{j\in T}\frac{j}{m}p_{j}\leq f^{\prime}_{k}(\sum_{j\in T} \frac{j}{m}p_{j}+\frac{m-j+1}{m}p_{j-1}).$ $$

And this, by definition of $f^{\prime}_{k}$ implies

$$ $\displaystyle\sum_{j\in T}\frac{j}{m}p_{j}\leq\bar{f}(\frac{1}{k-1}\sum_{j\in T }\frac{m-j+1}{m}p_{j-1}).$ $$

∎

###### Lemma 11 .

###### Proposition 12 .

###### Theorem 13 (Special case of 9 ) .

###### Proof.

## 4 Experiments

Most of our experiments are conducted in an *idealized setting*, similar to that used in Steinke et al. (), unless otherwise stated. In this setting, the attack success rate is automatically calculated to simulate the expected number of correct guesses by an optimal adversary (Details of the idealized setting are provided in Algorithm 4
in Appendix). We then use this expected number as the default value for the number of correct guesses to derive the empirical $\epsilon$. More specifically, as specified in Definition 6, we instantiate our auditing with a game and evaluation setup. We use Algorithm 4 in Appendix as our game setup. This algorithm returns the number of guesses and the number of correct guesses as the observation from the game. Then, we use Algorithm 3 as our evaluation setup to audit an $f$-DP curve based on the observation from Algorithm 4. Note that in our comparison with the auditing of Steinke et al., we always use the same membership inference game setup ($k=2$) as defined in their work. This ensures that our comparison is only on the evaluation part of the audit procedure.

In all experiments, we use empirical $\epsilon$ as the primary metric for evaluating our bounds. As described in Section 3.1
, we need an ordered set of $f$-DP curves to obtain empirical privacy. In our experiments, we use $f$-DP curves for Gaussian mechanisms with varying standard deviations (this forms an ordered set because the $f$-DP curve of a Gaussian mechanism with a higher standard deviation dominates that of a lower standard deviation). For sub-sampled Gaussian mechanisms, the ordered set consists of $f$-DP curves for sub-sampled Gaussian mechanisms with the given sub-sampling rate and number of steps and different noise standard deviations.

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

In this section, we evaluate our auditing method for membership inference in an idealized setting, using the work of Steinke et al. () as our main baseline. We compare our approach directly to their work, which operates in the same setting as ours.

#### Simple Gaussian Mechanism:

In the first experiment (Figure 1), we audit a simple Gaussian mechanism, varying the standard deviations from $[0.5,1.0,2.0,4.0]$, resulting in different theoretical $\epsilon$ values. We vary the number of canaries $(m)$ from $10^{2}$ to $10^{7}$ for auditing, set the bucket size to $k=2$, and adjust the number of guesses $(c^{\prime})$ for each number of canaries. For each combination of $m$, $c^{\prime}$, and each standard deviation, we calculate the expected number of correct guesses ($c$) using Algorithm 4
(the idealized setting). We then audit all tuples of $(m,c,c^{\prime})$ using the $f$-DP curves of the Gaussian mechanism, selecting the $c$ that achieves the highest empirical $\epsilon$ as the reported empirical $\epsilon$ for $m$ canaries at a given standard deviation.

We also apply the same setup for the auditing procedure of Steinke et al. (2023), differing only in the way empirical privacy is calculated. Figure 1 demonstrates that our approach outperforms the empirical privacy results from Steinke et al. Interestingly, while the bound in Steinke et al. (2023) degrades as the number of canaries increases, our bounds continue to improve.

Figure: Figure 1: Comparison between our empirical privacy lower bounds and that of Steinke et al. ()
Refer to caption: x1.png

#### Experiments on CIFAR-10:

Figure: Figure 2: Comparison with auditing procedure of Steinke et al. () on auditing CIFAR-10 in white-box setting using gradient-based membership inference attacks.
Refer to caption: extracted/5959940/figs/cifar10_audit.png

We also run experiments on CIFAR-10 on a modified version of the WRN16-4 (Zagoruyko and Komodakis, ) architecture, which substitutes batch normalization with group normalization. We follow the setting proposed by Sander et al. (), which use custom augmentation multiplicity (i.e., random crop around the center with 20 pixels padding with reflect, random horizontal flip and jitter) and apply an exponential moving average of the model weights with a decay parameter of 0.9999.
We run white-box membership inference attacks by following the strongest attack used in the work of Steinke et al. (), where the auditor injects multiple canaries in the training set with crafted gradients. More precisely, each canary gradient is set to zero except at a single random index (“Dirac canary” Nasr et al. ()). Note that in the white-box attack, the auditor has access to all intermediate iterations of DP-SGD.
The attack scores are computed as the dot product between the gradient update between consecutive model iterates and the clipped auditing gradients. As done in the work of  Steinke et al. (), we audit CIFAR-10 model with $m=5,000$ canaries and all training points from CIFAR-10 $n=50,000$ for the attack. We set the batch size to $4,096$, use augumented multiplicity of $K=16$ and train for $2,500$ DP-SGD steps.
For $\varepsilon=8.0,\delta=10^{-5}$, we achieved 77% accuracy when auditing, compared to 80% without injected canaries.
Figure 2 shows the comparison between the auditing scheme by Steinke et al. () with ours for different values of theoretical $\varepsilon$. We are able to achieve tighter empirical lower bounds.

### 4.2 Ablations

Figure: Figure 3: Effect of bucket size on the empirical lower bounds for reconstruction attack (Gaussian mechanism with standard deviation 0.6). Left: 10,000 canaries with bucket size up-to 5000. Right: 100 canaries with bucket-size up-to 50.
Refer to caption: extracted/5959940/figs/buckets_5k.png

#### Reconstruction attacks:

To show the effect of the bucket size ($k$) on the auditing performance, in Figure 3, we change the number of examples in the two different setups. In first setup we use 10,000 canaries and change the bucket size from 50 to 5000. In the other setup we only use 100 canaries and change the bucket-size from 3 to 50. Note that in these experiments, we do not use abstention and only consider adversaries that guess all examples.

Figure: Figure 4: Effect of number of guesses (Gaussian mechanism with standard deviation $1.0$)
Refer to caption: extracted/5959940/figs/guesses_dev1.0.png

Figure: Figure 8: Idealized setting for different values of $\delta$ and confidence levels for bounds of Steinke et al. ().
Refer to caption: extracted/5959940/figs/snj_deltas.png

#### Effect of number of guesses

In Figures 7–7, we compare the theoretical upper bound, our lower bound and the bound of Steinke et al. lower bound with varying number of guesses.
In total, we have $m=10^{7}$ canaries. The number of correct guesses is determined by using Algorithm 4
(the idealized setting). Then we use our and Steinke et al. ()’s auditing with the resulting numbers and report the empirical $\epsilon$. As we can see, both our and Steinke et al’s auditing procedure achieve the best auditing performance for small number of guesses. This shows the importance of abstention in auditing.

#### Varying δ 𝛿 \delta italic_δ and confidence levels:

In figure 9 we examines the effect of $\delta$ on the obtained empirical $\epsilon.$ We fix the number of canaries to $10^{5}$ and the number of guesses to $1,500$ and the number of correct guesses are set to $1,429$, suggested by the idealized setting. We use a Gaussian mechanism with standard deviation $1.0$, we vary the value of $\delta$ and the confidence level to observe how they affect the results. Note that our lower bounds are tight regardless of the confidence level and $\delta$.

## 5 Conclusions and limitations

We introduce a new approach for auditing the privacy of algorithms in a single run using $f$-DP curves. This method enables more accurate approximations of the true privacy guarantees, addressing the risk of a "false sense of privacy" that may arise from previous approximation techniques. By leveraging the entire $f$-DP curve, rather than relying solely on point estimates, our approach provides a more nuanced understanding of privacy trade-offs. This allows practitioners to make more informed decisions regarding privacy-utility trade-offs in real-world applications. However, our approach does not provide a strict upper bound on privacy guarantees but instead offers an estimate of the privacy parameters that can be expected in practical scenarios. We also recognize that, despite the improvements over prior work, we still observe a gap between the empirical and theoretical privacy reported in the “one run” setting. Future work could focus on closing this gap to further enhance the reliability of empirical privacy estimations.

## 6 Proofs

###### Proof of Lemma 11 .

Let $p=\Pr[M(\mathbf{u})\in E\text{\leavevmode\nobreak\ and\leavevmode\nobreak\ }u_
{1}=v_{1}]$ and $q=\Pr[M(\mathbf{u})\in E]$. We have

$$ $\displaystyle p$ $\displaystyle=\sum_{i\in[k]}\Pr[M(\mathbf{u})\in E\text{\leavevmode\nobreak\ and\leavevmode\nobreak\ }u_{1}=v_{1}=i]$ $\displaystyle=\frac{1}{k}\sum_{i\in[k]}\Pr[M(\mathbf{u})\in E\text{\leavevmode \nobreak\ and\leavevmode\nobreak\ }v_{1}=i\mid u_{1}=i]$ $\displaystyle=\frac{1}{k}\sum_{i\in[k]}\frac{1}{k-1}\Big{(}\sum_{j\in[k] \setminus\{i\}}\Pr[M(\mathbf{u})\in E\text{\leavevmode\nobreak\ and\leavevmode \nobreak\ }v_{1}=i\mid u_{1}=i]\Big{)}$ (By definition of $f$ -DP) $\displaystyle\leq\frac{1}{k}\sum_{i\in[k]}\frac{1}{k-1}\Big{(}\sum_{j\in[k] \setminus\{i\}}1-f\big{(}\Pr[M(\mathbf{u})\in E\text{\leavevmode\nobreak\ and \leavevmode\nobreak\ }v_{1}=i\mid u_{1}=j]\big{)}\Big{)}$ (By convexity of $f$ ) $\displaystyle\leq 1-f\left(\frac{1}{k}\sum_{i\in[k]}\frac{1}{k-1}\Big{(}\sum_{ j\in[k]\setminus\{i\}}\Pr[M(\mathbf{u})\in E\text{\leavevmode\nobreak\ and \leavevmode\nobreak\ }v_{1}=i\mid u_{1}=j])\Big{)}\right)$ $\displaystyle=1-f\left(\frac{1}{k-1}\sum_{i\in[k]}\Big{(}\sum_{j\in[k] \setminus\{i\}}\frac{1}{k}\Pr[M(\mathbf{u})\in E\text{\leavevmode\nobreak\ and \leavevmode\nobreak\ }v_{1}=i\mid u_{1}=j])\Big{)}\right)$ $\displaystyle=1-f\left(\frac{1}{k-1}\sum_{i\in[k]}\Big{(}\sum_{j\in[k] \setminus\{i\}}\Pr[M(\mathbf{u})\in E\text{\leavevmode\nobreak\ and\leavevmode \nobreak\ }v_{1}=i\text{\leavevmode\nobreak\ and\leavevmode\nobreak\ }u_{1}=j] )\Big{)}\right)$ $\displaystyle=1-f(\frac{1}{k-1}\Pr[M(\mathbf{u})\in E\text{\leavevmode\nobreak \ and\leavevmode\nobreak\ }u_{1}\neq v_{1}])$ $\displaystyle=1-f(\frac{q-p}{k-1}).$ $$

Similarly we have,

$$ $\displaystyle p$ $\displaystyle=\sum_{i\in[k]}\Pr[M(\mathbf{u})\in E\text{\leavevmode\nobreak\ and\leavevmode\nobreak\ }u_{1}=v_{1}=i]$ $\displaystyle=\frac{1}{k}\sum_{i\in[k]}\Pr[M(\mathbf{u})\in E\text{\leavevmode \nobreak\ and\leavevmode\nobreak\ }v_{1}=i\mid u_{1}=i]$ $\displaystyle=\frac{1}{k}\sum_{i\in[k]}\frac{1}{k-1}\Big{(}\sum_{j\in[k] \setminus\{i\}}\Pr[M(\mathbf{u})\in E\text{\leavevmode\nobreak\ and\leavevmode \nobreak\ }v_{1}=i\mid u_{1}=i]\Big{)}$ (By definition of $f$ -DP) $\displaystyle\geq\frac{1}{k}\sum_{i\in[k]}\frac{1}{k-1}\Big{(}\sum_{j\in[k] \setminus\{i\}}f^{-1}\big{(}1-\Pr[M(\mathbf{u})\in E\text{\leavevmode\nobreak \ and\leavevmode\nobreak\ }v_{1}=i\mid u_{1}=j]\big{)}\Big{)}$ (By convexity of $f$ ) $\displaystyle\geq f^{-1}\left(\frac{1}{k}\sum_{i\in[k]}\frac{1}{k-1}\Big{(} \sum_{j\in[k]\setminus\{i\}}1-\Pr[M(\mathbf{u})\in E\text{\leavevmode\nobreak \ and\leavevmode\nobreak\ }v_{1}=i\mid u_{1}=j])\Big{)}\right)$ $\displaystyle=f^{-1}\left(\frac{1}{k-1}\sum_{i\in[k]}\Big{(}\sum_{j\in[k] \setminus\{i\}}\frac{1}{k}(1-\Pr[M(\mathbf{u})\in E\text{\leavevmode\nobreak\ and\leavevmode\nobreak\ }v_{1}=i\mid u_{1}=j]))\Big{)}\right)$ $\displaystyle=f^{-1}\left(\frac{1}{k-1}\sum_{i\in[k]}\Big{(}\sum_{j\in[k] \setminus\{i\}}\Pr[M(\mathbf{u})\in E\text{\leavevmode\nobreak\ and\leavevmode \nobreak\ }v_{1}=i\text{\leavevmode\nobreak\ and\leavevmode\nobreak\ }u_{1}=j] )\Big{)}\right)$ $\displaystyle=f^{-1}(\frac{1}{k-1}(1-\Pr[M(\mathbf{u})\in E\text{\leavevmode \nobreak\ and\leavevmode\nobreak\ }u_{1}\neq v_{1}]))$ $\displaystyle=f^{-1}(\frac{1-q+p}{k-1}).$ $$

This implies that,

$$ $f(p)\cdot(k-1)+q-p\leq 1$ $$

∎

###### Proof of Proposition 12 .

The function is increasing simply because $f$ is decreasing. We now prove concavity.
Let $\alpha_{1}=f_{k}(x_{1})$ and $\alpha_{2}=f_{k}(x_{2})$.
By definition of $f_{k}$ we have

$$ $\alpha_{1}+f(\frac{x_{1}-\alpha_{1}}{k-1})\leq 1$ $$

and

$$ $\alpha_{2}+f(\frac{x_{2}-\alpha_{2}}{k-1})\leq 1.$ $$

Averaging these two we get,

$$ $\frac{\alpha_{1}+\alpha_{2}}{2}+\frac{f(\frac{x_{1}-\alpha_{1}}{k-1})+f(\frac{ x_{2}-\alpha_{2}}{k-1})}{2}\leq 1$ $$

By convexity of $f$ we have

$$ $\frac{\alpha_{1}+\alpha_{2}}{2}+f(\frac{\frac{x_{1}+x_{2}}{2}-\frac{\alpha_{1} +\alpha_{2}}{2}}{k-1})\leq 1$ $$

Therefore, by definition of $f^{\prime}_{k}$, we have
$f^{\prime}_{k}(\frac{x_{1}+x_{2}}{2})\geq\frac{\alpha_{1}+\alpha_{2}}{2}.$
Similarly, $f^{\prime\prime}_{k}$ in increasing just because $f$ is decreasing. And assuming $\alpha_{1}=f_{k}(x_{1})$ and $\alpha_{2}=f_{k}(x_{2})$ we have

$$ $f^{\prime\prime}_{k}(\frac{x_{1}+x_{2}}{2})\leq\frac{\alpha_{1}+\alpha_{2}}{2}$ $$

which implies $f^{\prime\prime}_{k}$ is convex.
∎

###### Proof of Theorem 9 .

Instead of working with an adversary with $c^{\prime}$ guesses, we assume we have an adversary that makes a guess on all $m$ inputs, however, it also submits a vector $\mathbf{q}\in\{0,1\}^{m}$, with exactly $c^{\prime}$ 1s and $m-c^{\prime}$ 0s. So the output of this adversary is a vector $\mathbf{v}\in[k]^{m}$ and a vector $\mathbf{q}\in\{0,1\}^{m}$. Then, only correct guesses that are in locations that $\mathbf{q}$ is non-zero is counted. That is,
if we define a random variable $\mathbf{t}=(\mathbf{t}_{1},\dots,\mathbf{t}_{m})$ as $\mathbf{t}_{i}=\mathbf{I}(\mathbf{u}_{i}=\mathbf{v_{i}})$ then we have

$$ $\displaystyle p_{c}$ $\displaystyle=\Pr[\sum_{i=1}^{m}\mathbf{t}_{i}\cdot\mathbf{q}_{i}=c]$ $\displaystyle=\Pr[\sum_{i=2}^{m}\mathbf{t}_{i}=c-1\text{\leavevmode\nobreak\ and\leavevmode\nobreak\ }\mathbf{t}_{1}=1\text{\leavevmode\nobreak\ and \leavevmode\nobreak\ }\mathbf{q}_{1}=1]+\Pr[\sum_{i=2}^{m}\mathbf{t}_{i}=c \text{\leavevmode\nobreak\ and\leavevmode\nobreak\ }\mathbf{t}_{1}\cdot\mathbf {q}_{1}=0]$ $$

Now by Lemma 11 we have

$$ $\Pr[\sum_{i=2}^{m}\mathbf{t}_{i}=c-1\text{\leavevmode\nobreak\ and\leavevmode \nobreak\ }\mathbf{t}_{1}=1\text{\leavevmode\nobreak\ and\leavevmode\nobreak\ }\mathbf{q}_{1}=1]\leq f^{\prime}_{k}(\sum_{i=2}^{m}\mathbf{t}_{i}=c-1\text{ \leavevmode\nobreak\ and\leavevmode\nobreak\ }\mathbf{q}_{1}=1).$ $$

This is a nice invariant that we can use but $\sum_{i=2}^{m}\mathbf{t}_{i}=c-1$ could be really small depending on how large $m$ is. To strengthen the bound we sum all $p_{c}$’s for $c\in T$, and then apply the lemma on the aggregate. That is

$$ $\displaystyle\sum_{j\in T}p_{j}$ $\displaystyle=\sum_{j\in T}\Pr[\sum_{i=1}^{m}\mathbf{t}_{i}=j]$ $\displaystyle=\sum_{j\in T}\Pr[\sum_{i=2}^{m}\mathbf{t}_{i}=j\text{\leavevmode \nobreak\ and\leavevmode\nobreak\ }\mathbf{t}_{1}\cdot\mathbf{q}_{1}=0]+\sum_{ j\in T}\Pr[\sum_{i=2}^{m}\mathbf{t}_{i}=j-1\text{\leavevmode\nobreak\ and \leavevmode\nobreak\ }\mathbf{t}_{1}=1\text{\leavevmode\nobreak\ and \leavevmode\nobreak\ }\mathbf{q}_{1}=1]$ $\displaystyle=\Pr[\sum_{i=2}^{m}\mathbf{t}_{i}\in T\text{\leavevmode\nobreak\ and\leavevmode\nobreak\ }\mathbf{t}_{1}\cdot\mathbf{q}_{1}=0]+\Pr[1+\sum_{i=2} ^{m}\mathbf{t}_{i}\in T\text{\leavevmode\nobreak\ and\leavevmode\nobreak\ } \mathbf{t}_{1}=1\text{\leavevmode\nobreak\ and\leavevmode\nobreak\ }\mathbf{q} _{1}=1]$ $$

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

$$ $\displaystyle\sum_{j\in T}p_{j}\leq\Pr[\sum_{i=2}^{m}\in T\text{\leavevmode \nobreak\ and\leavevmode\nobreak\ }\mathbf{t}_{1}\cdot\mathbf{q}_{1}=0]+f^{ \prime}_{k}(\Pr[1+\sum_{i=2}^{m}\mathbf{t}_{i}\in T\text{\leavevmode\nobreak\ and\leavevmode\nobreak\ }\mathbf{q}_{1}=1]).$ $$

Now we use a trick to make this cleaner. We use the fact that this inequality is invariant to the order of indices. So we can permute $\mathbf{t_{i}}$’s and the inequality still holds. We have,

$$ $\displaystyle\sum_{j\in T}p_{j}$ $\displaystyle\leq\operatorname*{E}_{\pi\sim\Pi[m]}[\Pr[\sum_{i=2}^{m}\mathbf{t }_{\pi(i)}\in T\text{\leavevmode\nobreak\ and\leavevmode\nobreak\ }\mathbf{t}_ {\pi(1)}\cdot\mathbf{q}_{\pi(1)}=0]]+\operatorname*{E}_{\pi\sim\Pi[m]}[f^{ \prime}_{k}(\Pr[1+\sum_{i=2}^{m}\mathbf{t}_{\pi(i)}\in T])]$ $\displaystyle\leq\operatorname*{E}_{\pi\sim\Pi[m]}[\Pr[\sum_{i=2}^{m}\mathbf{t }_{\pi(i)}\in T\text{\leavevmode\nobreak\ and\leavevmode\nobreak\ }\mathbf{t}_ {\pi(1)}=0]]+f^{\prime}_{k}(\operatorname*{E}_{\pi\sim\Pi[m]}[\Pr[1+\sum_{i=2} ^{m}\mathbf{t}_{\pi(i)}\in T\text{\leavevmode\nobreak\ and\leavevmode\nobreak \ }\mathbf{q}_{\pi(1)}=1]]).$ $$

Now we perform a double counting argument. Note that when we permute the order $\sum_{i=2}^{m}\mathbf{t}_{\pi(i)}=j\text{\leavevmode\nobreak\ and\leavevmode
\nobreak\ }\mathbf{t}_{\pi(1)}=0$ counts each instance $t_{1},\dots,t_{m}$ with exactly $j$ non-zero locations, for exactly $(m-j)\times(m-1)!$ times. Therefore, we have

$$ $\operatorname*{E}_{\pi\sim\Pi[m]}[\Pr[\sum_{i=2}^{m}\mathbf{t}_{\pi(i)}\cdot \mathbf{q}_{\pi(i)}\in T\text{\leavevmode\nobreak\ and\leavevmode\nobreak\ } \mathbf{t}_{\pi(1)}\cdot\mathbf{q}_{\pi(i)}=0]]=\sum_{j\in T}\frac{m-j}{m}p_{j}.$ $$

With a similar argument we have,

$$ $\displaystyle\operatorname*{E}_{\pi\sim\Pi[m]}[\Pr[1+\sum_{i=2}^{m}\mathbf{t}_ {\pi(i)}\cdot\mathbf{q}_{\pi(i)}\in T\text{\leavevmode\nobreak\ and\leavevmode \nobreak\ }\mathbf{q}_{\pi(1)}=1]]$ $\displaystyle=\sum_{j\in T}\frac{c^{\prime}-j+1}{m}p_{j-1}+\frac{j}{m}p_{j}.$ $$

Then, we have

$$ $\displaystyle\sum_{j\in T}p_{j}$ $\displaystyle\leq\sum_{j\in T}\frac{m-j}{m}p_{j}+f^{\prime}_{k}(\sum_{j\in T} \frac{j}{m}p_{j}+\frac{c^{\prime}-j+1}{m}p_{j-1})$ $\displaystyle=\sum_{j\in T}\frac{m-j}{m}p_{j}+f^{\prime}_{k}(\sum_{j\in T} \frac{j}{m}p_{j}+\frac{c^{\prime}-j+1}{m}p_{j-1})$ . $$

And this implies

$$ $\displaystyle\sum_{j\in T}\frac{j}{m}p_{j}\leq f^{\prime}_{k}(\sum_{j\in T} \frac{j}{m}p_{j}+\frac{c^{\prime}-j+1}{m}p_{j-1}).$ $$

And this, by definition of $f^{\prime}_{k}$ implies

$$ $\displaystyle\sum_{j\in T}\frac{j}{m}p_{j}\leq\bar{f}(\frac{1}{k-1}\sum_{j\in T }\frac{c^{\prime}-j+1}{m}p_{j-1}).$ $$

∎

###### Proof of Lemma 14 .

We prove this by induction on $j-i$. For $j-i=0$, the statement is trivially correct.
We have

$$ $h_{i,j}(\alpha_{j},\beta_{j})=(k-1)\bar{f}^{-1}(r_{i+1,j}(\alpha_{j},\beta_{j} )).$ $$

By induction hypothesis, we have $r_{i+1,j}(\alpha_{j},\beta_{j})\leq\alpha_{i+1}$. Therefore we have

$$ $h_{i,j}(\alpha_{j},\beta_{j})\leq(k-1)\bar{f}^{-1}(\alpha_{i+1}).$ $$

Now by invoking Theorem 9, we have

$$ $\alpha_{i+1}\leq\bar{f}(\frac{\beta_{i}}{k-1}).$ $$

Now since $\bar{f}$ is increasing, this implies

$$ $(k-1)\bar{f}^{-1}(\alpha_{i+1})\leq\beta_{i}$ $$

Now putting, inequalities 6 and 6 together we have
$h_{i,j}(\alpha_{j},\beta_{j})\leq\beta_{i}.$ This proves the first part of the induction hypothesis for the function $h$. Also note that $h_{i,j}$ is increasing in its first component and decreasing in the second component by invoking induction hypothesis and the fact that $\bar{f}^{-1}$ is increasing.
Now we focus on function $r_{i,j}$. Let $\gamma_{z}=\frac{z}{c^{\prime}-z}-\frac{z-1}{c^{\prime}-z+1}$.
Verify that for all $i$ we have

$$ $\alpha_{i}=\frac{i}{c^{\prime}-i}\beta_{i}+\sum_{z={i+1}}^{m}{\gamma_{z}}\beta _{z}.$ $$

Therefore, by induction hypothesis we have $\alpha_{i}\geq\frac{i}{c^{\prime}-i}\beta_{i}+\sum_{z={i+1}}^{m}{\gamma_{z}}
\beta_{z}.$
Therefore for all $i<j$ we have

$$ $\alpha_{i}-\alpha_{j}=\frac{i}{c^{\prime}-i}\beta_{i}-\frac{j}{c^{\prime}-j} \beta_{j}+\sum_{z={i+1}}^{j}{\gamma_{z}}\beta_{z}$ $$

Now, using the induction hypothesis for $h$ we have,

$$ $\alpha_{i}\geq\alpha_{j}+\frac{i}{c^{\prime}-i}h_{i,j}(\alpha_{j},\beta_{j})- \frac{j}{c^{\prime}-j}\beta_{j}+\sum_{z=i+1}^{j}{\gamma_{z}}h_{z,j}(\alpha_{j} ,\beta_{j}).$ $$

Now verify that the 6 is equal to $r_{i,j}(\alpha_{j},\beta_{j}).$ Also, using the induction hypothesis, we can observe that the right hand side of 6 is increasing in $\alpha_{j}$ and decreasing in $\beta_{j}$.
∎

###### Proof of Theorem 14 .

To prove Theorem 10, we first state and prove a lemma which is consequence of Theorem 9.

###### Lemma 14 .

For all $c\leq c^{\prime}\in[m]$ let us define

$$ $\alpha_{c}=\sum_{i=c}^{c^{\prime}}\frac{i}{m}p_{i}\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \text{ \leavevmode\nobreak\ and\leavevmode\nobreak\ }\leavevmode\nobreak\ \leavevmode \nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \beta_{c}=\sum_{i=c}^{c^{ \prime}}\frac{c^{\prime}-i}{m}p_{i}$ $$

We also define a family of functions $r=\{r_{i,j}:[0,1]\times[0,1]\to[0,1]\}_{i\leq j\in[m]}$ and $h=\{h_{i,j}:[0,1]\to[0,1]\}$ that are defined recursively as follows.

$\forall i\in[m]:r_{i,i}(\alpha,\beta)=\alpha$ and $h_{i,i}(\alpha,\beta)=\beta$
and for all $i<j$ we have

$$ $h_{i,j}(\alpha,\beta)=(k-1)\bar{f}^{-1}\Big{(}r_{i+1,j}(\alpha,\beta)\Big{)}$ $$

$$ $r_{i,j}(\alpha,\beta)=r_{i+1,j}(\alpha,\beta)+\frac{i}{c^{\prime}-i}(h_{i,j}( \alpha,\beta)-h_{i+1,j}(\alpha,\beta))$ $$

Then for all $i\leq j$ we have

$$ $\alpha_{i}\geq r_{i,j}(\alpha_{j},\beta_{j})\leavevmode\nobreak\ \leavevmode \nobreak\ \leavevmode\nobreak\ \text{\leavevmode\nobreak\ and\leavevmode \nobreak\ }\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \beta_{i}\geq h_{i,j}(\alpha_{j},\beta_{j})$ $$

Moreover, for $i<j$, $r_{i,j}$ and $h_{i,j}$ are increasing with respect to their first argument and decreasing with respect to their second argument.

This lemma enables us to prove that algorithm 3 is deciding a valid upper bound on the probability correctly guessing $c$ examples out of $c^{\prime}$ guesses. To prove this, assume that the probability of such event is equal to $\tau^{\prime}$,
Note that this means $\alpha_{c}+\beta_{c}=\frac{c^{\prime}}{m}\tau^{\prime}$.
Also note that $\frac{\alpha_{c}}{\beta_{c}}\geq\frac{c}{c^{\prime}-c}$, therefore, we have $\alpha_{c}\geq\frac{c}{m}\tau^{\prime}$ and $\beta_{c}\leq\frac{c^{\prime}-c}{m}\tau^{\prime}$. Therefore, using Lemma 11 we have
$\alpha_{0}\geq r_{0,c}(\frac{c}{m}\tau^{\prime},\frac{c^{\prime}-c}{m}\tau^{
\prime})$
and
$\beta_{0}\geq h_{0,c}(\frac{c}{m}\tau^{\prime},\frac{c^{\prime}-c}{m}\tau^{
\prime}).$

Now we prove a lemma about the function $s_{i,j}(\tau)=h_{i,j}(\frac{c}{m}\tau,\frac{c^{\prime}-c}{m}\tau)+r_{i,j}(
\frac{c}{m}\tau,\frac{c^{\prime}-c}{m}\tau)$.

###### Lemma 15 .

the function $s_{i,j}(\tau)=h_{i,j}(\frac{c}{m}\tau,\frac{c^{\prime}-c}{m}\tau)+r_{i,j}(
\frac{c}{m}\tau,\frac{c^{\prime}-c}{m}\tau)$ is increasing in $\tau$ for $i<j\leq c$.

###### Proof.

To prove this, we show that for all $i<j\leq c$ both $r_{i,j}(\frac{c}{m}\tau,\frac{c^{\prime}-c}{m}\tau)$ and $h_{i,j}(\frac{c}{m}\tau,\frac{c^{\prime}-c}{m}\tau)$ are increasing in $\tau$. We prove this by induction on $j-i$. For $j-i=1$, we have

$$ $h_{i,i+1}(\frac{c}{m}\tau,\frac{c^{\prime}-c}{m}\tau)=(k-1)\bar{f}^{-1}(\frac{ c}{m}\tau).$ $$

We know that $\bar{f}^{-1}$ is increasing, therefore $h_{i,i+1}(\frac{c}{m}\tau,\frac{c^{\prime}-c}{m}\tau)$ is increasing in $\tau$ as well.
For $r_{i,i+1}$ we have

$$ $r_{i,i+1}(\frac{c}{m}\tau,\frac{c^{\prime}-c}{m}\tau)=\frac{c}{m}\tau+\frac{i} {c^{\prime}-i}(h_{i,i+1}(\frac{c}{m}\tau,\frac{c^{\prime}-c}{m}\tau)-\frac{c^{ \prime}-c}{m}\tau)$ $$

So we have

$$ $\displaystyle r_{i,i+1}(\frac{c}{m}\tau,\frac{c^{\prime}-c}{m}\tau)$ $\displaystyle=\frac{c(c^{\prime}-i)-i(c^{\prime}-c)}{m(c^{\prime}-i)}\tau+ \frac{i}{c^{\prime}-i}h_{i,i+1}(\frac{c}{m}\tau,\frac{c^{\prime}-c}{m}\tau)$ $\displaystyle=\frac{(c-i)c^{\prime}}{m(c^{\prime}-i)}\tau+\frac{i}{c^{\prime}- i}h_{i,i+1}(\frac{c}{m}\tau,\frac{c^{\prime}-c}{m}\tau).$ $$

We already proved that $h_{i,i+1}(\frac{c}{m}\tau,\frac{c^{\prime}-c}{m}\tau)$ is increasing in $\tau$. We also have $\frac{(c-i)c^{\prime}}{m(c^{\prime}-i)}>0$, since $i<c$. Therefore

$$ $r_{i,i+1}(\frac{c}{m}\tau,\frac{c^{\prime}-c}{m}\tau)$ $$

is increasing in $\tau$. So the base of induction is proved. Now we focus on $j-i>1$. For $h_{i,j}$ we have

$$ $h_{i,j}(\frac{c}{m}\tau,\frac{c^{\prime}-c}{m}\tau)=(k-1)\bar{f}^{-1}(r_{i+1,j }(\frac{c}{m}\tau,\frac{c^{\prime}-c}{m}\tau).$ $$

By the induction hypothesis, we know that $r_{i+1,j}(\frac{c}{m}\tau,\frac{c^{\prime}-c}{m}\tau)$ is increasing in $\tau$, and we know that $\bar{f}^{-1}$ is increasing, therefore, $h_{i,j}(\frac{c}{m}\tau,\frac{c^{\prime}-c}{m}\tau)$ is increasing in $\tau$.

For $r_{i,j}$, note that we rewrite it as follows

$$ $r_{i,j}(\alpha,\beta)=\alpha-\frac{j}{c^{\prime}-j}\beta+\sum_{z=i}^{j-1} \lambda_{z}\cdot h_{z,j}(\alpha,\beta)$ $$

where $\lambda_{z}=(\frac{z+1}{c^{\prime}-z-1}-\frac{z}{c^{\prime}-z})\geq 0$. Therefore, we have

$$ $\displaystyle r_{i,j}(\frac{c}{m}\tau,\frac{c^{\prime}-c}{m}\tau)$ $\displaystyle=\tau(\frac{c}{m}-\frac{(c^{\prime}-c)j}{m(c^{\prime}-j)})+\sum_{ z=i}^{j-1}\lambda_{z}\cdot h_{z,j}(\frac{c}{m}\tau,\frac{c^{\prime}-c}{m}\tau)$ $\displaystyle=\tau\frac{c^{\prime}(c-j)}{m(c^{\prime}-j)}+\sum_{z=i}^{j-1} \lambda_{z}\cdot h_{z,j}(\frac{c}{m}\tau,\frac{c^{\prime}-c}{m}\tau).$ $$

Now we can verify that all terms in this equation are increasing in $\tau$, following the induction hypothesis and the fact that $\lambda_{z}>0$ and also $j\leq c$.
∎

Now using this Lemma, we finish the proof.
Note that we have
$\alpha_{0}+\beta_{0}=\frac{c^{\prime}}{m}$.

So assuming that $\tau^{\prime}\geq\tau$, then we have

$$ $\frac{c^{\prime}}{m}=\alpha_{0}+\beta_{0}\geq s_{0,c}(\tau^{\prime})\geq s_{0, c}(\tau).$ $$

The last step of algorithm checks if $s_{0,c}\geq\frac{c^{\prime}}{m}$ and it concludes that $\tau^{\prime}\leq\tau$ if that’s the case, because $s_{0,c}$ is increasing in $\tau$. This means that the probability of having more than $c$ guesses cannot be more than $\tau$.
∎

See pages - of [arxiv_appendix.pdf](arxiv_appendix.pdf)

###### Proof of Lemma 11 .

###### Proof of Proposition 12 .

###### Proof of Theorem 9 .

###### Proof of Lemma 14 .

###### Proof of Theorem 14 .

###### Lemma 14 .

###### Lemma 15 .

###### Proof.

## Peer Reviews

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
questions: -Can you discuss more how the design of the set of canaries impact the reconstruction games?

-Apart from the classical example of differential privacy, can you provide a few other examples of function f that could be audited using your framework?

-Can the approach be used on classifiers for other types of data such as for example tabular data?
soundness: 3
strengths: -The existing literature on privacy auditing is clearly reviewed as well as the main limitations of existing approaches. 

-The paper is well-written and easy to read. The authors have also provide a clear introduction of the notions necessary to the understanding of their work such as the f-DP curve.

-The proposed approach has the benefit of only requiring a single run of the mechanism. The relationship with the method of Steinke at al. is also clearly explained. One of the main novelty of the approach is also to connect the privacy auditing procedure with previous works bounding the accuracy of reconstruction attacks.

-The experiments conducted demonstrate that the approach proposed performed better in terms of the tightness of the bound estimated when the noise added is a a low to high regime.
summary: This paper proposes an approach for auditing the guarantees of a differentially-private algorithm, which in contrast to other existing auditing schemes, does not require re-training of the model. In addition, the approach provides tighter bounds that the related work by Steinke et al.
weaknesses: -Some notions such as the concept of empirical privacy could have been more formally defined. Other important details are missing such as the relationship between the way canaries are designed and the quality of their possible reconstruction as well as the design of the function f that should be considered for the auditing. 

-The number of canaries needed for the experiments is very high and is likely to have a significant impact on the utility of the classifier learnt. While an experiment has been conducted with CIFAR-10 to measure the impact of the introduction of 5000 canaries more experiments should be conducted by varying the number of canaries to observe in a more fine-grained manner the impact of the introduction of canaries.

-The approach has been validated empirically only on one dataset. Additional experiments at least two other datasets should be conducted to validate how well the approach generalizes to other settings. 

-There are some minor typos that could be corrected in a future revised version. For instance, "(e.g., [1])." seems to refer to a different bibliography style. Other typos : "an attack algorthm A" should be "an attack algorithm A", "in Essene" should be "in essence" and "augumented multiplicity" should be "augmented multiplicity"

---

confidence: 5
contribution: 3
initial_rating: 3
presentation: 1
questions: Questions:
* You claim that your approach achieves tighter results as the number of canaries increases, outperforming the empirical privacy results from Steinke et al. (2023), suggesting that the results can be tight as we increase the number of canaries. Could you elaborate on why your bounds continue to improve with more canaries while the bounds in previous work degrade? What underlying mechanisms in your algorithm contribute to this improvement? Citing the authors: ” Figure 1 demonstrates that our approach outperforms the empirical privacy results from Steinke et al. Interestingly, while the bound in Steinke et al. (2023) degrades as the number of canaries increases, our bounds continue to improve.”
* What potential sources contribute to any lack of tightness in your lower bounds? Are there specific aspects of the f-DP framework or your implementation that introduce looseness? How might these be addressed in future work to enhance the tightness of the bounds?
* How does your algorithm perform in the black-box setting compared to the white-box setting? Can you provide detailed experimental results illustrating this performance?
soundness: 3
strengths: * **Advancement of f-DP Tools**: The paper contributes to the understanding and practical application of f-DP, which could be of independent interest.
* **Interesting Problem**: Auditing DP mechanisms in a one-run scenario is interesting for practical implementations (particularly in the black-box scenario, see the weakness section), and the paper makes significant progress in this area.
* **Experimental Validation**: The experimental results are compelling and demonstrate the effectiveness of the proposed approach.
* **Versatility in Adversarial Models**: Extending the auditing algorithm to handle different adversaries, such as reconstruction attacks.
summary: The paper presents a novel algorithm for auditing differential privacy (DP) mechanisms in a single run, building upon and extending the work of Steinke et al. (2023). By leveraging the theoretical framework of f-Differential Privacy (f-DP), the authors provide tighter lower bounds on privacy leakage, thereby enhancing the existing toolbox for f-DP analysis. Notably, their auditing algorithm can be applied to various adversaries beyond the standard membership inference, such as reconstruction attacks.
weaknesses: The authors investigate exciting problems and provide interesting results. I encourage the authors to continue working on these results, as they are sound and exciting to the DP community. However, I don’t think the work is ready to be published in its current form, as it is somewhat rushed. I sketch my main concerns below.
* **Writing and Presentation Quality**: The manuscript contains several errors and unclear explanations. The authors should revise it before publication, as there are plenty of writing errors and bad citing style.
* **Unreferenced Figures and Results**: Some results, particularly those in Figure 7, need to be adequately referenced or explained within the text, leading to confusion about their significance.
* **Incomplete Explanation of Gaps**: The paper needs to explain the gaps between theoretical and lower bounds. Possible reasons for these gaps should be analysed, such as limitations of the f-DP framework, assumptions made in the analysis, or practical considerations in implementation.
* **Insufficient Experimental Details**: There are no experiments in the black-box setting for which we are compelled to use one-shot auditing. The white-box setting enjoys a tight and efficient auditing algorithm (Nasr et al., 2023), while the black-box algorithms are rather expensive.

---

confidence: 3
contribution: 3
initial_rating: 8
presentation: 2
questions: - On the section “Empirical Privacy” line no 307, why do the trade off curves need to be ordered? If you have a set of trade off curves $f_i$ that pass couldn’t you build a new trade off curve $f(x) = \min_i f_i(x)$ 
- In what sense are the empirical results tight in Fig 7 and why is that not also evident in Fig 1?
- Can you explain why abstentions are important in this algorithm?
soundness: 3
strengths: - Valuable Contribution to Existing Research: There has been extensive work on auditing differential privacy guarantees. This paper distinguishes itself by offering a solution that enhances both computational efficiency and the precision of empirical privacy guarantees. The reliance on multiple runs of the mechanism has been a major obstacle to the widespread application of auditing methods. Their approach, requiring only a single run, makes auditing significantly more practical, especially for complex machine-learning algorithms involving extensive model training.
- Using the $f$-DP framework is a particularly strong aspect of this work. $f$-DP offers a more general and accurate representation of a mechanism's privacy compared to traditional approximate differential privacy. This choice allows for a more fine-grained and robust analysis of privacy. The authors convincingly demonstrate that auditing $f$-DP leads to tighter empirical privacy assessments. By performing the analysis in a single training run, the paper achieves a more comprehensive understanding of the privacy implications within a practical computational framework.
summary: The paper presents a novel algorithm designed to audit $f$-DP guarantees within a single execution of a mechanism.
This area of research has become increasingly significant within the privacy community, particularly due to the limitations of existing auditing mechanisms.
Existing empirical auditing methods are either computationally expensive (requiring multiple runs of the machine learning algorithm) or fall short in providing a tight empirical privacy guarantee.
The need to run the mechanism multiple times has hindered practical applications.
Steinke et al. (2023) introduced a pioneering approach that balances the number of runs with the tightness of the audit.
This present work enhances this trade-off further by auditing $f$-DP guarantees, which provide a more precise representation of a mechanism's privacy compared to traditional approximate DP parameters.
weaknesses: - The main weakness of this paper is its presentation. The write-up seems very rushed which at times hinders the flow of the reader. Many references are broken e.g. reference to Algorithm B. Lines 300-312 contain many typos and incomplete sentences. These are issues that can be addressed quickly but in the current state I would argue that the presentations limits the value of this work to the community.
- The authors have not provided a code artifact. While the contributions of this work are mostly theoretical, the implementation of the algorithm requires care and it would help reproducibility if a code artifact were supplied.

---

confidence: 3
contribution: 3
initial_rating: 8
presentation: 2
questions: 1) What do you mean by "gubernatorial analysis"? (Line 95)
2) Do you have an intuition why the bound in Steinke et al. (2023) degrades with higher numbers of canaries while your bounds continue to improve?
soundness: 3
strengths: The paper is well-motivated and, for the most part, clearly written. It provides a notable improvement over prior privacy auditing techniques.
summary: This paper proposes a computationally efficient privacy auditing procedure by leveraging the f-DP curve, and shows that the resulting lower bounds are tighter than those of previous work.
weaknesses: The paper contains some ambiguities and cosmetic errors that should be addressed to improve clarity and overall presentation.
1) clarify that by "one run" you mean a training run (rather than an inference run)
2) explicitly state the limitation of Steinke et al. (2023) that you are addressing (in Line 80-82)
3) change the references to algorithm 3.1 to algorithm 3 (given that that is what the algorithm is called)
4) remove double mentions of Steinke et al. by just using the reference instead (e.g., in Line 420)
5) fix the reading flow in Definition 6 (second bullet point is not a full sentence)
6) correct typos (e.g., Line 194/195, 307, 466, 505/506) and wrong capitalizations in the middle of sentences (e.g., Line 100)

Meta-review: ## Summary of Contributions

This paper studies auditing of differential privacy (DP) with one run of the algorithm. Previous work (e.g. (Steinke et al., 2023)) studies the setting where we wish to test whether the algorithm satisfies $(\epsilon, \delta)$-DP for a single pair of $(\epsilon, \delta)$. This work extends the test to the setting of *$f$-DP*, which--roughly speaking--gives an entire curve for the values of $(\epsilon, \delta)$. By deriving sharper bounds on the accuracy of the guessing game assuming $f$-DP (Theorem 9), the authors show that $f$-DP allows for a better auditing compared to $(\epsilon, \delta)$-DP; this (partially) answers an open question from (Steinke et al., 2023). The authors also demonstrate this numerically, showing improvements in auditing the Gaussian mechanism and DP-SGD.

## Strengths

- The paper makes a clear contribution towards privacy auditing in one run, using an additional concept of $f$-DP. This is novel as previous works have only consider a single $(\epsilon, \delta)$ pair when auditing. Furthermore, $f$-DP is an important concept that has led to tight numerical privacy accounting in recent years and, thus, this is a well motivated and important setting.

- Empirically, the method has shown to significantly improve the empirical privacy from auditing compared to previous work.

## Weaknesses

- **Presentation**: Multiple reviewers find the presentation qualities to be inadequate. Some central concepts (e.g. empirical privacy) and details were not defined in the original version of the submission. Discussions on the experiment details and effects of different parameters were also insufficient.

- **Significant Changes in the revision**: Although these have been added in the revision, the changes are quite significant (as can be seen by the diff in the latest supplementary material; perhaps ~30% of the main text). Some of the potential issues--which are only apparent after the change--are listed below. Due to this, it might be best if the paper is re-submitted and fully reviewed again rather than accepted as is.

- **Possible Flaw in Empirical Privacy**:  The "empirical privacy" (Definition 7) used in this paper might be flawed and incomparable with previous work e.g. Steinke et al. (2023). To explain this, let us assume that the accuracy is 100% and consider the scenario where the test fails; what Steinke et al. (2023) works say is that the algorithm is *not $(\epsilon, \delta)$-DP*. However, what the test in this paper shows is that the algorithm is *not $f$-DP*. In this latter scenario, we do *not* know where the failure comes from; it could be that it fails for $\delta = 10^{-5}$ or at $\delta = 10^{-7}$ etc. As a result, we cannot simply pick a single $\delta$ and report the $\epsilon$ at that $\delta$, because the violation might not happen there. Due to this, it is unfair to compare to previous work in a manner done in Section 4.1 (and this is not discussed at all in the paper).

- **Practicality / Limitations**: Related to the above, this also highlights the fact that we need to pick the $f$ curve very carefully to get any meaningful result from such a testing at all. This will likely limit the practicality of the algorithm significantly since, for more complicated algorithms other than Gaussian mechanism, the $f$ curve is not well understood and computing them can be numerically challenging. (The choice of $f$ is mentioned briefly before Section 4.1 but the discussion does not dive into such subtlety.)

## Recommendation

Although auditing $f$-DP is an important direction and this paper provides some interesting initial work, more investigation / clarification should be done before the paper is ready for publication. Furthermore, it would be useful for the paper to get another proper full end-to-end review it deserves, given the significant changed during rebuttal. Due to these, we recommend rejection.

Decision: Reject