Privacy Auditing with One (1) Training Run

Introduction

Differential privacy (DP) [DMNS06] provides a quantifiable privacy guarantee by ensuring that no person’s data significantly affects the probability of any outcome. Formally, a randomized algorithm $M$ satisfies $(\varepsilon,\delta)$-DP if, for any pair of inputs $x,x^{\prime}$ differing only by the addition or removal of one person’s data and any measurable $S$, we have

A DP algorithm is accompanied by a mathematical proof giving an upper bound on the privacy parameters $\varepsilon$ and $\delta$. In contrast, a privacy audit provides an empirical lower bound on the privacy parameters. Privacy audits allow us to assess the tightness of the mathematical analysis [JUO20, NHSBTJCT23] or, if the lower and upper bounds are contradictory, to detect errors in the analysis or in the algorithm’s implementation [TTSSJC22].

Can we perform privacy auditing using a single run of the algorithm M?

This is the question we address in our work.

Our approach (§2): The DP definition (1) considers adding or removing a single person’s data to or from the dataset. We consider multiple people’s data and the dataset independently includes or excludes each person’s data point. Our analysis exploits the parallelism of multiple independent data points in a single run of the algorithm in lieu of multiple independent runs.

Our auditing procedure operates as follows. We identify $m$ data points (i.e., training examples or “canaries”) to either include or exclude and we flip $m$ independent unbiased coins to decide which of them to include or exclude. We then run the algorithm on the randomly selected dataset. Based on the output of the algorithm, the auditor “guesses” whether or not each data point was included or excluded (or it can abstain from guessing for some data points). We obtain a lower bound on the privacy parameters from the fraction of guesses that were correct.

Intuitively, if the algorithm is $(\varepsilon,0)$-DP, then the auditor can correctly guess each inclusion/exclusion coin flip with probability at most $\frac{e^{\varepsilon}}{e^{\varepsilon}+1}$. Thus DP implies a high-probability upper bound on the fraction of correct guesses and, conversely, a large fraction of correct guesses implies a high-probability lower bound on the privacy parameters.

Our analysis (§5): Naïvely, analyzing the addition or removal of multiple data elements would rely on group privacy; but this does not exploit the fact that the data items were included or excluded independently. Instead, we leverage the connection between DP and generalization [DFHPRR15a, DFHPRR15, BNSSSU16, RRST16, JLNRSMS19, SZ20]. Our main theoretical contribution is an improved analysis of this connection that is tailored to yield nearly tight bounds in our setting.

Informally, if we run a DP algorithm on i.i.d. samples from some distribution, then, conditioned on the output of the algorithm, the samples are still “close” to being i.i.d. samples from that distribution. There is some technicality in making this precise, but, roughly speaking, we show that including or excluding $m$ data points independently for one run is essentially as good as having $m$ independent runs (as long as $\delta$ is small).

Our results (§6): We implement our new auditing framework to audit DP-SGD training on a WideResNet model, trained on the CIFAR10 dataset across multiple configurations. Our approach successfully achieves an empirical lower bound of $\varepsilon\geq 1.8$, compared to a theoretical upper bound of $\varepsilon\leq 4$ in the white-box setting. The $m$ examples we insert for auditing (known in the literature as “canaries”) do not significantly impact the accuracy of the final model (less than a $5\%$ decrease in accuracy) and our procedure only requires a single end-to-end training run. Such results were previously unattainable in the setting where only one model could be trained.

Our Auditing Procedure

We now present our auditing procedure in Algorithm 1. We independently include each of the first $m$ examples with 50% probability and exclude it otherwise.Alternatively, we could also consider a different probability of inclusion; our theoretical results can handle this (see Proposition 5.7). However, this seems unlikely to be useful, as it intuitively lowers the signal-to-noise ratio. Another alternative is to non-independently choose which points to include to ensure $x_{\text{IN}}$ has a fixed size; see Appendix A. Our approach is applicable to both white-box auditing in the sense that the adversary has access to all intermediate values of the model weights and black-box auditing in the sense that the adversary only sees the final model weights (or can only query the final model). In both cases we compute a “score” for each example and “guess” whether the example is included or excluded based on these scores. Specifically, we guess that the examples with the $k_{+}$ highest scores are included and the examples with the $k_{-}$ lowest scores are excluded, and we abstain from guessing for the remaining $m-k_{+}-k_{-}$ auditing examples; the setting of these parameters will depend on the application.

Note that we only randomize the first $m$ examples $x_{1},\cdots,x_{m}$ (which we refer to as “auditing examples” or “canaries”); the last $n-m$ examples $x_{m+1},\cdots,x_{n}$ are always included and, thus, we do not make any guesses about them. To get the strongest auditing results we would set $m=n$, but we usually want to set $m<n$. For example, computing the score of all $n$ examples may be computationally prohibitive, so we only compute the scores of $m$ examples. Also we may wish to artificially construct $m$ examples to be easy to identify (i.e., canaries), but still include $n-m$ “real” examples to ensure that $\mathcal{A}$ still produces a useful model. (I.e., having more training examples improves the performance of the model.)

Intuitively, the vector of scores $Y$ should be correlated with the true selection $S$, but too strong a correlation would violate DP. This is the basis of our audit. Specifically, the auditor computes $T$ from $Y$ which is a “guess” at $S$. By the postprocessing property of DP, the guesses $T$ are a differentially private function of the true $S$, which means that they cannot be too accurate.

To obtain a lower bound on the DP parameters, in Section 5, we show that DP implies a high-probability upper bound on the number of correct guesses $W:=\sum_{i}^{m}\max\{0,T_{i}\cdot S_{i}\}$. The observed value of $W$ then yields a high-probability lower bound on the DP parameters. To be more precise, we have the following guarantee.

If we ignore $\delta$ for the moment, Theorem 2.1 says that the number of correct guesses is stochastically dominated by $\mathsf{Binomial}\left(r,\frac{e^{\varepsilon}}{e^{\varepsilon}+1}\right)$, where $r=k_{+}+k_{-}$ is the total number of guesses. This binomial distribution is precisely the distribution of correct guesses we would get if $T$ was obtained by independently performing $(\varepsilon,0)$-DP randomized response on $r$ bits of $S$. In other words, the theorem says that $(\varepsilon,0)$-DP randomized response is the worst-case algorithm in terms of the number of correct guesses. In particular, this means the theorem is tight (when $\delta=0$)

The binomial distribution is well-concentrated. In particular, for all $\beta\in(0,1)$, we have

There is an additional $O(\delta)$ term in the guarantee (2). The exact expression for this term is somewhat complex. It is always $\leq 2m\delta$, but it is much smaller than this for reasonable parameter values. In particular, for $v$ as in Equation 3 with $\beta\leq 1/r^{4}$, this term is $\leq O(\tfrac{m}{r}\delta)$.

Theorem 2.1 gives us a hypothesis test: If $\mathcal{A}$ is $(\varepsilon,\delta)$-DP, then the number of correct guesses $W$ is $\leq\frac{r\cdot e^{\varepsilon}}{e^{\varepsilon}+1}+O(\sqrt{r})$ with high probability. Thus, if the observed number of correct guesses $v$ is larger than this, we can reject the hypothesis that $\mathcal{A}$ satisfies $(\varepsilon,\delta)$-DP. We can convert this hypothesis test into a confidence interval (i.e., a lower bound on $\varepsilon$) by finding the largest $\varepsilon$ that we can reject at a desired level of confidence; see Section 4.3.

Related Work

The goal of privacy auditing is to empirically estimate the privacy provided by an algorithm, typically to accompany a formal privacy guarantee. Early work on auditing has often been motivated by trying to identify bugs in the implementations of differentially private data analysis algorithms [DWWZK18, BGDCTV18].

Techniques for auditing differentially private machine learning typically rely on conducting some form of membership inference attack [SSSS17];[SSSS17] coined the term “membership inference attack” and were the first to apply such attacks to machine learning systems. However, similar attacks were developed for applications to genetic data [HSRDTMPSNC08, SOJH09, DSSUV15] and in cryptography [BS98, Tar08]. these attacks are designed to detect the presence or absence of an individual example in the training set. Essentially, a membership inference attack which achieves some true positive rate (TPR) and false positive rate (FPR) gives a lower bound on the privacy parameter $\varepsilon\geq\log_{e}(\text{TPR}/\text{FPR})$ (after ensuring statistical validity of the TPR and FPR estimates).

[JE19] use standard membership inference attacks to evaluate different privacy analysis algorithms. [JUO20] consider inferring membership of worst-case “poisoning” examples to conduct stronger membership inference attacks and understand the tightness of privacy analysis. [NSTPC21] measure the tightness of privacy analysis under a variety of threat models, including showing that the DP-SGD analysis is tight in the threat model assumed by the standard DP-SGD analysis.

Improvements to auditing have been made in a variety of directions. For example, [NHSBTJCT23] and [MSS22] take advantage of the iterative nature of DP-SGD, auditing individual steps to understand privacy of the end-to-end algorithm. Improvements have also been made to the basic statistical techniques for estimating the $\varepsilon$ parameter, for example by using Log-Katz confidence intervals [LMFLZWRFT22], Bayesian techniques [ZBWTSRPNK22], or auditing algorithms in different privacy definitions [NHSBTJCT23]. [AKOOMS23] build on the observation that, when performing membership inference, analyzing the case where the data is not included does not require re-running the algorithm; instead we can re-sample the excluded data point; if the data points are i.i.d. from a nice distribution, this permits closed-form analysis of the excluded case.

A recent heuristic proposed to improve the efficiency of auditing is performing membership inference on multiple examples simultaneously. This heuristic was proposed by [MEMPST21], and evaluated more rigorously by [ZBWTSRPNK22]. However, this heuristic is not theoretically justified, as the TPR and FPR estimates are not based on independent samples. In our work, we provide a proof of the validity of this heuristic. In fact, with this proof, we show for the first time that standard membership inference attacks, which attack multiple examples per training run, can be used for auditing analysis; prior work using these attacks must make an independence assumption. As a result, auditing can take advantage of progress in the membership inference field [CCNSTT22, WBKBGGG22].

Background

We briefly review some standard background material. Readers may wish to skip to the next section and revisit this only if necessary.

They We recite the definitions of differential privacy and some relevant relaxations. For detailed background, see the tutorial by [Vad17] or the textbook by [DR14].

Let $M:\mathcal{X}^{*}\to\mathcal{Y}$ be a randomized algorithm, where $\mathcal{X}^{*}=\bigcup_{n\geq 0}\mathcal{X}^{n}$. We say $M$ is $(\varepsilon,\delta)$-differentially private ($(\varepsilon,\delta)$-DP) if, for all $x,x^{\prime}\in\mathcal{X}^{*}$ differing only by the addition or removal of one element, we have

We say $M:\mathcal{X}^{*}\to\mathcal{Y}$ is $(\alpha,\check{\varepsilon})$-Rényi differentially private ($(\alpha,\check{\varepsilon})$-RDP) if, for all $x,x^{\prime}\in\mathcal{X}^{*}$ differing only by the addition or removal of one element, we have

We say $M:\mathcal{X}^{*}\to\mathcal{Y}$ is $\rho$-zero concentrated differentially private ($\rho$-zCDP) if, for all $x,x^{\prime}\in\mathcal{X}^{*}$ differing only by the addition or removal of one element, we have

In this paper, we focus on to the addition or removal notion of DP, rather than replacement. (In Appendix A, we consider replacement.) Note that, in our theoretical analysis, we consider DP algorithms of the form $M:\{0,1\}^{m}\to\mathcal{Y}$. In this case, DP is with respect to flipping one of the input bits, as each bit indicates whether some example is included or excluded.

The main property of DP that we use is invariance under postprocessing. That is, if $M:\mathcal{X}^{*}\to\mathcal{Y}$ satisfies DP and $F:\mathcal{Y}\to\mathcal{Z}$ is an arbitrary function, then $F\circ M:\mathcal{X}^{*}\to\mathcal{Z}$ also satisfies DP with the same parameters.

A common method for achieving DP is Gaussian noise addition. The following gives the optimal DP guarantee for the Gaussian mechanism.

2 DP-SGD – Differentially Private Stochastic Gradient Descent

The algorithm whose privacy we are most interested in auditing is Differentially Private Stochastic Gradient Descent (DP-SGD, Algorithm 2). This is the workhorse of private machine learning both in theory [BST14] and in practice [ACGMMTZ16].

DP-SGD satisfies differential privacy. Much ink has been spilled precisely quantifying its privacy properties [MTZ19, WBK19, KJH20, GLW21, ZDW22, etc.]. A simple guarantee is the following.

DP-SGD (Algorithm 2) satisfies $(2,\check{\varepsilon})$-RDP for

If $\check{\varepsilon}\leq 1$, then DP-SGD should provide meaningful privacy protection. In particular, $(2,\check{\varepsilon})$-RDP implies that membership inference has a maximum accuracy (in the balanced case) of

3 Hypothesis Testing & Statistical Estimation

Our goal is to estimate the privacy parameters of the algorithm that we are auditing. As prior work has noted [DWWZK18, JUO20], this task can be framed as statistical estimation, with a goal of outputting a statistical lower bound on the privacy parameters. These lower bounds will have a corresponding confidence level, roughly representing the probability that the lower bound could have been produced even when analyzing an algorithm with perfect privacy. As empirical methods, it is impossible to have 100% confidence in our methods, so we will generally use 95% confidence in our experiments, comparable to the use of $p<0.05$ in science literature.

To be precise, our auditor runs the algorithm $M$ and outputs $\varepsilon_{\text{LB}}\geq 0$ with the following guarantee. If $M$ satisfies $(\varepsilon_{\text{true}},\delta)$-DP, then, with probability at least $1-\beta$, we have $\varepsilon_{\text{LB}}\leq\varepsilon_{\text{true}}$. Here $1-\beta$ is the confidence level and $\delta\geq 0$ is fixed. Note that this is a frequentist guarantee, rather than a Bayesian guarantee. That is, the probability is with respect to our auditing procedure, rather than a statement about our beliefs about $M$.

We can also view this in terms of hypothesis testing. Here we start with a “null hypothesis” that $M$ satisfies $(\varepsilon_{\text{null}},\delta)$-DP and the auditor’s goal is to test this hypothesis by running $M$. If the auditor rejects this null hypothesis, then this gives us a lower bound $\varepsilon_{\text{LB}}=\varepsilon_{\text{null}}$.

The difference between hypothesis testing and statistical estimation is that a hypothesis test starts with a given $\varepsilon_{\text{null}}$ and outputs a binary decision to reject or not, while an estimator outputs a number $\varepsilon_{\text{LB}}$. However, we can convert between these:

Further suppose that, if $\varepsilon_{1}\leq\varepsilon_{2}$, then $T_{\varepsilon_{1},\beta}\supset T_{\varepsilon_{2},\beta}$. Then, for all $M$ and all $\beta>0$,

Fix a realization of $A_{M}$ and suppose $P_{M}<\sup\left\{\varepsilon>0:A_{M}\in T_{\varepsilon,\beta}\right\}$. Then there exists some $\varepsilon\geq P_{M}$ with $A_{M}\in T_{\varepsilon,\beta}$ and, hence,

The equality above follows from our monotonicity assumption on $T$. Thus

To interpret Lemma 4.7, $M$ is an algorithm and $P_{M}$ is the “true” privacy parameter $\varepsilon$ that it satisfies. (We’re considering $\delta$ to be fixed.) The random variable $A_{M}$ is the output of our auditing procedure applied to $M$. (This is our test statistic in the language of hypothesis testing.) The hypothesis test’s rejection set is $T_{\varepsilon,\beta}$ and Equation 5 guarantees that, if $M$ is indeed $(\varepsilon,\delta)$-DP (i.e., the null hypothesis is true), then the probability that we reject the null hypothesis is at most $\beta$. Equation 6 then shows how to estimate the true privacy parameter $P_{M}$ from $A_{M}$; we simply take the largest $\varepsilon$ for which we can reject the corresponding null hypothesis.

Note that Lemma 4.7 needs to make a technical monotonicity assumption. In our setting this simply means that, if a given realization of the test statistic $A_{M}$ allows us to reject the null hypothesis that $M$ is $(\varepsilon_{2},\delta)$-DP and $\varepsilon_{1}\leq\varepsilon_{2}$, then we can also reject the null hypothesis that $M$ is $(\varepsilon_{1},\delta)$-DP.

4 Stochastic Dominance

In our theoretical analysis we use the concept of stochastic dominance. Specifically, we use this to formalize the “worst-case” DP algorithm for auditing.

Stochastic dominance is preserved under sums/convolutions:

Theoretical Analysis

To analyze the results of our audit, we leverage the connection between DP and generalization [DFHPRR15a, DFHPRR15, BNSSSU16, RRST16, JLNRSMS19, SZ20]. Unfortunately, directly applying the existing results from the literature is unlikely to yield meaningful results, as the constants are not optimal. Thus we provide an analysis of DP’s generalization guarantees that is suitable for our application and which has sharp constants.

The algorithm $M$ represents both the “real” algorithm (e.g., DP-SGD) and the auditor which postprocesses the output of the real algorithm into guesses. In this formalism, the examples themselves are considered fixed and not part of the input – i.e., the examples are “hardcoded” into $M$. The algorithm $M$ is an abstraction for our analysis, rather than a realistic system.

where $S$ is uniform on $\{-1,+1\}^{m}$ and $T=M(S)$. If $T_{i}$ and $S_{i}$ disagree in sign (i.e., the guess is wrong), then $\max\{0,T_{i}\cdot S_{i}\}=0$; if they agree (i.e., the guess is right), then $\max\{0,T_{i}\cdot S_{i}\}=|T_{i}|$. That is, $W$ increases when we guess correctly and the increase is proportional to how much “weight” we placed on that guess. The auditor seeks to maximize $W$ and then we compare it to a baseline that is consistent with DP. (The analysis in this section focuses on computing this baseline.) Incorrect guesses do not increase $W$, but they do increase the baseline. Note that we can guess $T_{i}=0$, which amounts to abstaining from making a guess; this doesn’t increase $W$, but also doesn’t increase the baseline.

Our formalism is inspired by that of [SZ20], who also restrict to binary inputs. In contrast, most of the work connecting DP and generalization does not do this. The benefit of restricting to binary inputs which represent inclusion or exclusion of a data point is that it simplifies our analysis.

We first consider the pure DP ($\delta=0$) case, as it is considerably simpler than the general case. We follow the analysis of [JLNRSMS19] with some refinement. Specifically, rather than relying on a Hoeffding bound, we show that it is stochastically dominated by a Binomial distribution. This result is tight – i.e., if $M$ independently performs a randomized response for each input bit, then the inequality becomes an equality.

Proposition 5.1 is Bayesian: We condition on the output and then consider the probability that each guess was right. The vector $\check{S}$ should be seen as indicating whether each guess was right. The proposition says that, in the worst case, each guess is correct independently with probability $\frac{e^{\varepsilon}}{e^{\varepsilon}+1}$.

How do we use this result? Suppose we have conducted an audit and observed $s$ and $t$ as the output of Algorithm 3. Let $v=\sum_{i}^{m}\max\{0,s_{i}\cdot t_{i}\}$. Following Lemma 4.7, we choose a desired confidence $1-\beta<1$ (e.g., $\beta=0.05$) and then we choose $\varepsilon\geq 0$ so that $\beta(m,\varepsilon,v,t)=\beta$. Then this value of $\varepsilon$ is our lower bound.

2 Approximate DP Analysis

Our analysis most closely resembles that of [RRST16]. Essentially, we repeat the analysis for the pure DP case, but add some failure events, and carefully account for how much they can distort the results.

In particular, if we substitute $v=\frac{e^{\varepsilon}}{e^{\varepsilon}+1}r_{1}+r_{2}\cdot\sqrt{\frac{1}{2}\log(1/\beta)}$ into Equation 11, we get

Since $\check{W}^{*}$ stochastically dominates $\check{W}(t)$ for all $t$ in the support of $T$, we can apply Theorem 5.2 to obtain the first part of the result (10).

Setting $c=\frac{1}{2}\left(v-\frac{e^{\varepsilon}}{e^{\varepsilon}+1}r_{1}\right)$ yields the second part of the result (11) ∎

In the next corollary we restrict $M$ to ternary outputs, so it must either guess ($T_{i}=\pm 1$) or abstain ($T_{i}=0$). We bound the number of guesses by $r$. In this case the dominating distribution $\check{W}^{*}$ is a binomial distribution, which is relatively easy to compute. This is the form of Theorem 5.2 that we use in all of our experimental results. We provide pseudocode in Appendix D.

Now we delve into the proof of Theorem 5.2. We use a decomposition result of [KOV15] (see also [MV15] & [Ste22, Corollary 24]).

Let $P$ and $Q$ be probability distributions over $\mathcal{Y}$. Fix $\varepsilon,\delta\geq 0$. Suppose that, for all measurable $S\subset\mathcal{Y}$, we have $P(S)\leq e^{\varepsilon}\cdot Q(S)+\delta$ and $Q(S)\leq e^{\varepsilon}P(S)+\delta$.

Then there exist $\delta^{\prime}\in[0,\delta]$ and distributions $P^{\prime}$, $Q^{\prime}$, $P^{\prime\prime}$, and $Q^{\prime\prime}$ over $\mathcal{Y}$ such that the following three properties are all satisfied. First, we can express $P$ and $Q$ as convex combinations:

Second, for all measurable $S\subset\mathcal{Y}$, we have $e^{-\varepsilon}P^{\prime}(S)\leq Q^{\prime}(S)\leq e^{\varepsilon}P^{\prime}(S)$. Third, there exist measurable $S,T\subset\mathcal{Y}$ such that $P^{\prime\prime}(S)=1$, $Q^{\prime\prime}(T)=1$, $\forall S^{\prime}\subset S~{}P(S^{\prime})\geq Q(S^{\prime})$, and $\forall T^{\prime}\subset T~{}Q(T^{\prime})\geq P(T^{\prime})$.

This proof follows that of [Ste22]. We begin with some formalities: Fix some base measure such that $P$ and $Q$ are absolutely continuous with respect to the base measure. (If $P$ and $Q$ are discrete distributions, this can be the counting measure. If they are continuous distributions, this can be the Lebesgue measure. In general, $P+Q$ serves as such a measure.) For $y\in\mathcal{Y}$, let $P(y)$ and $Q(y)$ denote the Radon-Nikodym derivative of $P$ and, respectively, $Q$ with respect to this base measure.

If $e^{-\varepsilon}\cdot Q(S)\leq P(S)\leq e^{\varepsilon}\cdot Q(S)$ for all measurable $S$, then the result follows trivially by setting $\delta^{\prime}=0$, $P^{\prime}=P$ and $Q^{\prime}=Q$, and choosing $P^{\prime\prime}$ and $Q^{\prime\prime}$ to be arbitrary distributions supported on $S=\{y\in\mathcal{Y}:P(y)\geq Q(y)\}$ and $T=\{y\in\mathcal{Y}:P(y)\leq Q(y)\}$ respectively. Thus we assume that this is not the case and, hence, that $\delta>0$ and $d_{\text{TV}}\left(P,Q\right)>0$.

Similarly, if $\delta\geq 1$ and $d_{\text{TV}}\left(P,Q\right)=1$, then the result follows trivially by setting $\delta^{\prime}=1$, $P^{\prime\prime}=P$, $Q^{\prime\prime}=Q$, and $P^{\prime}=Q^{\prime}$ arbitrary. Thus we assume that $\min\{\delta,d_{\text{TV}}\left(P,Q\right)\}<1$.

Fix $\varepsilon_{1},\varepsilon_{2}\in[0,\varepsilon]$ to be determined later. Define distributions $P^{\prime}$, $P^{\prime\prime}$, $Q^{\prime}$, and $Q^{\prime\prime}$ (in terms of their Radon-Nikodym derivatives) as follows. For all points $y\in\mathcal{Y}$,

where $\delta_{1},\delta_{2}\in(0,1)$ are appropriate normalizing constants. (We will choose $\varepsilon_{1}$ to avoid $\delta_{1}\in\{0,1\}$ and, likewise, we will choose $\varepsilon_{2}$ to avoid $\delta_{2}\in\{0,1\}$.)

By construction, $(1-\delta_{1})P^{\prime}+\delta_{1}P^{\prime\prime}=P$ and $(1-\delta_{2})Q^{\prime}+\delta_{2}Q^{\prime\prime}=Q$, so the first property is satisfied. Note that $P^{\prime\prime}$ is supported on $S=\{y\in\mathcal{Y}:P(y)>e^{\varepsilon_{1}}\cdot Q(y)\}$ and $Q^{\prime\prime}$ is supported on $T=\{y\in\mathcal{Y}:Q(y)>e^{\varepsilon_{2}}\cdot P(y)\}$, which implies the third property.

If $0<\delta_{1}=\delta_{2}\leq\delta$, then we have the appropriate decomposition (with $\delta^{\prime}=\delta_{1}=\delta_{2}$) and, for all $y\in\mathcal{Y}$, we have

It only remains to show that we can ensure that $0<\delta_{1}=\delta_{2}\leq\delta$ by appropriately setting $\varepsilon_{1},\varepsilon_{2}\in[0,\varepsilon]$. We have

where $S=\{y\in\mathcal{Y}:P(y)\geq e^{\varepsilon_{1}}\cdot Q(y)\}$. If $\varepsilon_{1}=\varepsilon$, then $\delta_{1}\leq\delta$ by assumption. If $\varepsilon_{1}=0$, then $\delta_{1}=d_{\text{TV}}\left(P,Q\right)>0$. By decreasing $\varepsilon_{1}$, we continuously increase $\delta_{1}$. Thus, by starting at $\varepsilon_{1}=\varepsilon$ and decreasing $\varepsilon_{1}$ until either $\varepsilon_{1}=0$ or $\delta_{1}=\delta$, we can pick $\varepsilon_{1}\in[0,\varepsilon]$ such that $\delta_{1}=\min\{\delta,d_{\text{TV}}\left(P,Q\right)\}\in(0,1)$. Similarly, we can pick $\varepsilon_{2}\in[0,\varepsilon]$, such that $\delta_{2}=\min\{\delta,d_{\text{TV}}\left(P,Q\right)\}$. ∎

We need a Bayesian version of this decomposition. I.e., suppose we observe a sample from either $P$ or $Q$ and we have a prior on these two possibilities, what is the posterior distribution on possibilities? The following gives such a result. However, it introduces an event $E_{P,Q}$. Intuitively, when $E_{P,Q}(Y)=1$, then we get the result we would get under pure DP. But $E_{P,Q}(Y)=0$ with probability $\delta$, in which case things can fail arbitrarily.

[KS14, Lemma 3.4] provide a similar result. Ours improves the constant factors and is also stated slightly differently.

Let $P$ and $Q$ be probability distributions over $\mathcal{Y}$. Fix $\varepsilon,\delta\geq 0$. Suppose that, for all measurable $S\subset\mathcal{Y}$, we have $P(S)\leq e^{\varepsilon}\cdot Q(S)+\delta$ and $Q(S)\leq e^{\varepsilon}P(S)+\delta$.

Then there exists a randomized function $E_{P,Q}:\mathcal{Y}\to\{0,1\}$ with the following properties.

Fix $p\in$ and suppose $X\leftarrow\mathsf{Bernoulli}(p)$. If $X=1$, sample $Y\leftarrow P$; and, if $X=0$, sample $Y\leftarrow Q$. Then, for all $y\in\mathcal{Y}$, we have

We apply the decomposition from Lemma 5.5: There exist distributions $P^{\prime}$, $Q^{\prime}$, $P^{\prime\prime}$, and $Q^{\prime\prime}$ over $\mathcal{Y}$ and $\delta^{\prime}\in[0,\delta]$ such that

and, for all $y\in\mathcal{Y}$, $e^{-\varepsilon}P^{\prime}(y)\leq Q^{\prime}(y)\leq e^{\varepsilon}P^{\prime}(y)$ and $P^{\prime\prime}(y)>0\implies P(y)\geq Q(y)$ and $Q^{\prime\prime}(y)>0\implies P(y)\leq Q(y)$. (Here $P(\cdot)$ denotes the Radon-Nikodym derivative of the distribution $P$ with respect to some appropriate base measure and similarly for the other distributions.)

We define $E_{P,Q}:\mathcal{Y}\to\{0,1\}$ by

since $P^{\prime\prime}(y)>0\implies P(y)\geq Q(y)$. For any $y\in\mathcal{Y}$, we have

Now we can prove an analog of Proposition 5.1 for the $(\varepsilon,\delta)$-DP setting.

For $i\in[m]\cup\{0\}$ and $s_{\leq i}\in\{-1,1\}^{i}$, let $M(s_{\leq i})$ denote the distribution on $^{m}$ obtained by conditioning $M(S)$ on $S_{\leq i}=s_{\leq i}$. We can express this as a convex combination:

For distributions $P$ and $Q$ on $^{m}$, let $E_{P,Q}:^{m}\to\{0,1\}$ be the randomized function promised by Lemma 5.6. In our analysis, the internal randomness of $E_{P,Q}$ is independent from everything else – i.e., the only dependence is induced by its input. Specifically, for all $i\in[m]$, all $s_{<i}\in\{-1,1\}^{i-1}$, and all $t\in^{m}$, we have

Symmetrically, for all $i\in[m]$, all $s_{<i}\in\{-1,1\}^{i-1}$, and all $t\in^{m}$, we have

For simplicity, we define a symmetric event: $E_{P}^{Q}(y)=E_{Q}^{P}(y):=E_{P,Q}(y)\cdot E_{Q,P}(y)$, where the internal randomnesses are again independent. Combining these, we have, for all $i\in[m]$, all $s_{<i}\in\{-1,1\}^{i-1}$, and all $t\in^{m}$,

For $k\in[m]$, $s\in\{-1,1\}^{m}$, and $t\in^{m}$, define

where, for each $i\in[k]$ independently, $\check{S}(t)_{i}\leftarrow\mathsf{Bernoulli}(\frac{p\cdot e^{\varepsilon}}{p\cdot e^{\varepsilon}+1-p})$ if $t_{i}>0$ and $\check{S}(t)_{i}\leftarrow\mathsf{Bernoulli}(\frac{(1-p)\cdot e^{\varepsilon}}{(1-p)\cdot e^{\varepsilon}+p})$ if $t_{i}<0$.

By induction and Lemma 4.9, for any $k\in[m]$ and $t\in^{m}$, the conditional distribution $(\widetilde{W}_{k}(S,t)|M(S)=t)$ where $S\leftarrow(2\mathsf{Bernoulli}(p)-1)^{m}$ is stochastically dominated by $\check{W}_{k}(t)$.

For $s\in\{-1,1\}^{m}$ and $t\in^{m}$, define

Since the conditional distribution $(\widetilde{W}_{k}(S,t)|M(S)=t)$ where $S\leftarrow(2\mathsf{Bernoulli}(p)-1)^{m}$ is stochastically dominated by $\check{W}_{k}(t)$, $W_{m}$ is stochastically dominated by the convolution $\check{W}_{m}(T)+F(S,T)$.

Finally $F(s,t)$ is supported on $\{0,1,\cdots,m\}$ and

Since $\check{W}_{m}(T)$ does not depend on $S$, the input $S$ does not contribute to the dependence between $F(S,T)$ and $\check{W}_{m}(T)$, so we can elide this input in the statement – i.e., $F(T)=F(S,T)$ for $S$ drawn from an appropriate distribution. ∎

Proposition 5.7 is rather unwieldy. It can be simplified by setting $p=\frac{1}{2}$ and identifying the optimal distribution $F(T)$, which yields Theorem 5.2.

where $\check{W}(t):=\sum_{i}^{m}\check{S}_{i}|t_{i}|$ for $\check{S}\leftarrow\mathsf{Bernoulli}\left(\frac{e^{\varepsilon}}{e^{\varepsilon}+1}\right)^{m}$.

By strong duality, the linear program above has the same value as its dual:

Any feasible solution to the dual gives an upper bound on the primal. So, in particular, we can use the solution given by

Theorem 5.2 gives a worst-case bound in terms of $T$. Specifically, $\check{W}^{*}$ must uniformly bound $\check{W}(t)$ for all $t$ in the support of $T$. Proposition 5.7 is more general than this. Thus we give another corollary that allows us to have the bound adjust to $T$. In particular, this result allows the auditing procedure (Algorithm 1 or 3) to dynamically choose the number of guesses $r=k_{+}+k_{-}$.

Let $M:\{-1,+1\}^{m}\to[-1,+1]^{m}$ satisfy $(\varepsilon,\delta)$-DP. Let $S\in\{-1,+1\}^{m}$ be uniformly random. Let $T=M(S)\in[-1,+1]^{m}$. Then, for all $\gamma\in$ and $\tau>0$,

Setting $p=\frac{1}{2}$ in Proposition 5.7 yields

By a union bound and Markov’s inequality, we have, for all $t\in^{m}$, all $\gamma\in$, and all $\tau>0$,

We combine inequalities, set $v=g_{m,\varepsilon}(t,\gamma)+\tau$, and average over $T$ to obtain

Experiments

Our contributions are focused on improved analysis of an existing privacy attack, and are therefore orthogonal to the design of an attack. As a result, we rely on the experimental setup of the recent auditing procedure of [NHSBTJCT23].

We run DP-SGD on the CIFAR-10 dataset with Wide ResNet (WRN-16) [ZK16], we followed the experimental setup from \AtNextCite\AtEachCitekey\@nocounterrmaxnames[NHSBTJCT23]. Our experiments reach $~{}76\%$ test accuracy at $(\varepsilon=8,\delta=10^{-5})$-DP, which is comparable with the state-of-the-art [DBHSB22]. Unless specified otherwise, all lower bounds are presented with $95\%$ confidence. Following \AtNextCite\AtEachCitekey\@nocounterrmaxnames[NHSBTJCT23], we refer to the setting where the adversary has access to all intermediate steps as “white-box” and when the adversary can only see the last iteration as “black-box.” We experiment with both settings.

Algorithm 3 summarizes our approach for auditing DP-SGD. The results are converted into lower bounds on the privacy parameters using Theorem 5.2 / Corollary 5.4.

We also experiment with both the gradient and input attacks proposed by \AtNextCite\AtEachCitekey\@nocounterrmaxnames[NHSBTJCT23]. In particular, for the gradient attack we use the strongest attack they proposed – the “Dirac canary” approach – which sets all gradients to zero except at a single random index. In our setting where we need to create multiple auditing examples (canaries) we make sure the indices selected in our experiments do not have any repetitions. To compute the score for gradient space attacks, we use the dot product between the gradient update and auditing gradient. When auditing in input space, we leverage two different types of injected examples as:

Mislabeled example: We select a random subset of the test set and randomly relabel them (ensuring the new label is not the same as the original label).

In-distribution example: We select a random subset of the test set.

For input space audits, we use the loss of the input example as the score. In our experiments we report the attack with the highest lower bound.

In our experiments, we evaluate different values of $k_{+}$ and $k_{-}$ and only report the highest auditing results. Since this is doing multiple hypothesis testing on the same data, we are reducing the confidence value of our results. However, this is commonly used in the previous works [ZBWTSRPNK22, MSS22] and can be easily improved by using a different set of observations to select the parameters for the auditing and another set of the data for the auditing itself (see also Corollary 5.8).

1 Gradient Space attacks

We start with the strongest attack: We assume white-box access – i.e., the auditor sees all intermediate iterates of DP-SGD – and that the auditor can insert examples with arbitrary gradients into the training procedure. First, we evaluate the effect of the number of the auditing example on the tightness. Figure 5 demonstrates that as the number of examples increases, the auditing becomes tighter. However, the impact of the additional examples eventually diminishes. Intriguingly, adding more non-auditing training examples (resulting in a larger $n$ compared to $m$) does not seem to influence the tightness of the auditing, as depicted in Figure 5. This can be primarily due to the fact that gradient attacks proposed in prior studies can generate near-worst-case datasets, irrespective of the presence of other data points.

Now we directly use the parameters used in the training CIFAR10 models. Figure 7 summarizes results for the CIFAR10 models. We used $m=5000$ and all of the training dataset from CIFAR10 ($n=50,000$) for the attack. We were able to achieve $76\%$ accuracy for $\varepsilon=8$ ($\delta=10^{-5}$, compared to $78\%$ when not auditing). We are able to achieve an empirical lower bound of $0.7,1.2,1.8,3.5$ for theoretical epsilon of $1,2,4,8$ respectively. While our results are not as tight as the prior works, we only require a single run of training which is not possible using the existing techniques. In the era of exponentially expanding machine learning models, the computational and financial costs of training these colossal architectures even once are significant. Expecting any individual or entity to shoulder the burden of training such models thousands of times for the sake of auditing or experimental purposes is both unrealistic and economically infeasible. Our method offers a unique advantage by facilitating the auditing of these models, allowing for an estimation of privacy leakage in a white-box setting without significantly affecting performance.

2 Input Space Attacks

Now we evaluate the effect of input space attacks in the black-box setting. In this attack, the auditor can only insert actual images into the training procedure and cannot control any of the aspects of the training. Then, the adversary can observe the final model as mentioned in Algorithm 3. This is the weakest attack setting.

For simplicity we start with the setting where $m=n$; in other words, all of the examples used to train the model are randomly included or excluded and can be used for auditing. Figure 9 illustrates the result of this setting. As we see from the figure, unlike the white-box attack we do not observe a monotonic relationship between the number of auditing examples and the tightness of the auditing. Intuitively, when the number of auditing examples are low then we do not have enough observations to have high confidence lower bounds for epsilon. On the other hand, when the number of auditing examples are high, the model does not have enough capacity to “memorize” all of the auditing examples which reduces the tightness of the auditing. However, this can be improved by designing better black-box attacks which we reiterate in the next section.

We also evaluate the effect of adding additional training data to the auditing in Figure 9. We see that adding superfluous training data significantly reduces the effectiveness of auditing. The observed reduction in auditing effectiveness with the addition of more training data could be attributed to several factors. One interpretation could be that the theoretical privacy analysis in a black-box setting tends to be considerably more loose when the adversary is constrained to this setting. This could potentially result in an overestimation of the privacy bounds. Conversely, it is also plausible that the results are due to the weak black-box attacks and can be improved in the future.

Discussion

Our main contribution is showing that we can audit the differential privacy guarantees of an algorithm with a single run. In contrast, prior methods require hundreds – if not thousands – of runs, which is computationally prohibitive for all but the simplest algorithms. Our experimental results demonstrate that in practical settings our methods are able to give meaningful lower bounds on the privacy parameter $\varepsilon$.

However, while we win on computational efficiency, we lose on tightness of our lower bounds. We now illustrate the limitations of our approach and discuss the extent to which this is inherent, and what lessons we can learn.

But, first, we illustrate that our method can give tight lower bounds. In Figure 10, we consider an idealized setting where the number of guesses changes and the fraction that are correct is fixed at $\frac{e^{\varepsilon}}{e^{\varepsilon}+1}$ for $\varepsilon=4$ – i.e., 98.2% of guesses are correct.The number of correct guesses is rounded down to an integer (which results in the lines being jagged). There are no abstentions. This is the maximum expected fraction of correct guesses compatible with $(4,0)$-DP. In this setting the lower bound on $\varepsilon$ does indeed come close to $4$. With 10,000 guesses we get $\varepsilon\geq 3.87$ with 95% confidence.

Note that the lower bound in Figure 10 improves as we increase the number of guesses. This is simply accounting for sampling error – to get a lower bound with 95% confidence, we must underestimate to account for the fact that the number of correct guesses may have been inflated by chance. As we get more guesses, the relative size of chance deviations reduces.

Limitations: Next we consider a different idealized setting – one that is arguably more realistic – where our method does not give tight lower bounds. Suppose $S_{i}\in\{-1,+1\}$ indicates whether example $i\in[n]$ is included or excluded. In Figure 11, we consider Gaussian noise addition. That is, we release a sample from $\mathcal{N}(S_{i},4)$. (In contrast, Figure 10 considers randomized response on $S_{i}$.) Lemma 4.5 gives an upper bound of $(4.38,10^{-5})$-DP. Unlike for randomized response, abstentions matter here. We consider 100,000 examples, each of which has a score sampled from $\mathcal{N}(S_{i},4)$, where $S_{i}\in\{-1,+1\}$ is uniformly random. We pick the largest $r/2$ scores and guess $S_{i}=+1$. Similarly we guess $S_{i}=-1$ for the smallest $r/2$ scores. We abstain for the remaining $100,000-r$ examples. If we make more guesses (i.e., increase $r$), then the accuracy goes down and so does our lower bound. We must trade off between more guesses being less accurate on average and more guesses having smaller relative sampling error.

In Figure 11, the highest value of the lower bound is $\varepsilon\geq 2.675$ for $\delta=10^{-5}$, which is attained by $1439$ correct guesses out of $1510$. In contrast, the upper bound is $\varepsilon=4.38$ for $\delta=10^{-5}$. To get a matching upper bound of $\varepsilon\leq 2.675$ we would need to set $\delta=0.0039334$. In other words, the gap between the upper and lower bounds is a factor of $393\times$ in $\delta$.

Figure 12 considers the same idealized setting as Figure 11, but we fix the number of guesses to 1,500 out of 100,000 (of which 1,429 are correct); instead we vary $\delta$ and consider different confidence levels.

Are these limitations inherent? Figures 11 & 12 illustrate the limitations of our approach. They also hint at the causes: The number of guesses versus abstentions, the $\delta$ parameter, and the confidence all have a large effect on the tightness of our lower bound.

Our theoretical analysis is fairly tight; there is little room to improve Theorem 5.2. We argue that the inherent problem is a mismatch between “realistic” DP algorithms and the “pathological” DP algorithms for which our analysis is nearly tight. This mismatch makes our lower bound much more sensitive to $\delta$ than it “should” be.

To be concrete about what we consider pathological, consider $M:\{-1,+1\}^{m}\to\{-1,0,+1\}^{m}$ defined by Algorithm 4. This algorithm satisfies $(\varepsilon,\delta)$-DP and makes $r$ guesses with $m-r$ abstentions. In the $X=1$ case, the expected fraction of correct guesses is $\frac{m\delta}{r\beta}+\left(1-\frac{m\delta}{r\beta}\right)\cdot\frac{e^{\varepsilon}}{e^{\varepsilon}+1}$. This is higher than the average fraction of correct guesses, but if we want confidence $1-\beta$ in our lower bound, we must consider this case, as $X=1$ happens with probability $\beta$.

Intuitively, the contribution from $\delta$ to the fraction of correct guesses should be negligible. However, we see that $\delta$ is multiplied by $m/r\beta$. That is to say, in the settings we consider, $\delta$ is multiplied by a factor on the order of $100\times$ or $1000\times$, which means $\delta=10^{-5}$ makes a non-negligible contribution to the fraction of correct guesses.

It is tempting to try to circumvent this problem by simply setting $\delta$ to be very small. However, as shown in Figure 12, the upper bound on $\varepsilon$ also increases as $\delta\to 0$.

Unfortunately, there is no obvious general way to rule out algorithms that behave like Algorithm 4. The fundamental issue is that the privacy losses of the $m$ examples are not independent; we shouldn’t expect them to be independent, but we also shouldn’t expect them to be pathologically dependent in reality.

Directions for further work: Our work highlights several questions for further exploration:

Improved attacks: Our experimental evaluation uses existing attack methods. Any improvements to membership inference attacks could be combined with our results to yield improved privacy auditing.

One limitation of our attacks is that some examples may be “harder” than others and the scores we compute do not account for this. When we have many runs, we can account for the hardness of individual examples [CCNSTT22], but in our setting it is not obvious how to do this.

Algorithm-specific analyses: Our methods are generic – they can be applied to essentially any DP algorithm. This is a strength, but there is also the possibility that we could obtain stronger results by exploiting the structure of specific algorithms. A natural example of such structure is the iterative nature of DP-SGD. That is, we can view one run of DP-SGD as the composition of multiple independent DP algorithms which are run sequentially.

Multiple runs & multiple examples: Our method performs auditing by including or excluding multiple examples in a single training run, while most prior work performs multiple training runs with a single example example included or excluded. Can we get the best of both worlds? If we use multiple examples and multiple runs, we should be able to get tighter results with fewer runs.

Other measures of privacy: Our theoretical analysis is tailored to the standard definition of differential privacy. But there are other definitions of differential privacy such as Rényi DP. And, in particular, many of the upper bounds (e.g., Proposition 4.6) are stated in this language. Hence it would make sense for the lower bounds also to be stated in this language.

Beyond lower bounds: Privacy auditing produces empirical lower bounds on the privacy parameters. In contrast, mathematical analysis produces upper bounds. Both are necessarily conservative, which leaves a large gap between the upper and lower bounds. A natural question is to find some middle ground – an estimate which is neither a lower nor upper bound, but provides some meaningful estimate of the “true” privacy loss. However, it is unclear what kind of guarantee such an estimate should satisfy, or what interpretation the estimate should permit.

References

Appendix A Sampling a Fixed-Size Dataset

Our auditing framework considers randomly including or excluding $m$ examples independently. This means that the size of the dataset is random. This may be undesirable.

Fortunately, we can fix this, without changing our theoretical analysis. But it does require more examples and it requires changing the definition of DP to consider pairs of datasets differing by the replacement of one person’s data, rather than the addition or removal of one person’s data (cf. Remark 4.4).

Recall that our auditing framework starts with $m$ examples $x_{1},\cdots,x_{m}$ and then samples $S\in\{-1,+1\}^{m}$ uniformly at random. Then each example $x_{i}$ is included in the dataset if $S_{i}=+1$ and excluded if $S_{i}=-1$. Thus flipping $S_{i}$ corresponds to adding or removing $x_{i}$.

Instead we can start with $2m$ examples $x_{1},\cdots,x_{2m}$ and then sample $S\in\{-1,+1\}^{m}$ uniformly. Now, if $S_{i}=+1$, we include $x_{2i}$ in the dataset and, if $S_{i}=-1$, we include $x_{2i-1}$ instead. Thus flipping $S_{i}$ corresponds to replacing $x_{2i}$ with $x_{2i-1}$ or vice versa.

This alternative approach ensures that we always include $m$ out of the $2m$ examples – i.e., the dataset size is not random. This still fits the formalism of our theoretical analysis (§5). However, the DP guarantee of the algorithm being audited (e.g., DP-SGD) must now be with respect to replacement of one example, rather than addition or removal.By group privacy, $(\varepsilon,\delta)$-DP for addition or removal implies $(2\varepsilon,(e^{\varepsilon}+1)\cdot\delta)$-DP for replacement. The auditor also needs to change slightly; rather than being given $x_{i}$ and needing to guess whether or not it is included in the datsets, the auditor is given both $x_{2i}$ and $x_{2i-1}$ and must guess which of the two is included.

Appendix B Generalization from Differential Privacy

Our analysis builds on the connection between DP and generalization [DFHPRR15a, DFHPRR15, BNSSSU16, FS17, JLNRSMS19]. We now extend our theoretical results (§5) to this setting. The main difference between our analysis in Section 5 and the prior work on DP and generalization is that we restrict to i.i.d. binary inputs with a uniform distribution, while prior work considers i.i.d. inputs from an arbitrary set with an arbitrary distribution. Thus the prior work is more general, but, as we now show, we can reduce the general case to the binary case.

where $\check{W}\leftarrow\mathsf{Binomial}\left(n,\frac{e^{\varepsilon}}{e^{\varepsilon}+1}\right)$.

The proof of Theorem B.1 relies on the following technical lemma. This is using what is known as the “ghost samples” symmetrization technique [SZ20, Footnote 2].

Let $x^{+},x^{-}\in\mathcal{X}^{n}$. For $s\in\{-1,+1\}^{n}$, define $x^{s}\in\mathcal{X}^{n}$ by $x^{s}_{i}=x^{+}_{i}$ if $s_{i}=+1$ and $x^{s}_{i}=x^{-}_{i}$ if $s_{i}=-1$. Let $A:\mathcal{X}^{n}\to\mathcal{Y}$ be $(\varepsilon,\delta)$-DP (for replacement). Let $q:\mathcal{Y}\times\mathcal{X}\to$, and denote $q(y,x)=\frac{1}{n}\sum_{i}^{n}q(y,x_{i})\in$ for $y\in\mathcal{Y}$ and $x\in\mathcal{X}^{n}$.

Let $S\in\{-1,+1\}$ be uniform. Then, for all $v,r\geq 0$,

where $\check{W}\leftarrow\mathsf{Binomial}\left(n,\frac{e^{\varepsilon}}{e^{\varepsilon}+1}\right)$.

where $\check{W}\leftarrow\mathsf{Binomial}\left(n,\frac{e^{\varepsilon}}{e^{\varepsilon}+1}\right)$. Note that Theorem 5.2 applies with any distribution $\check{W}^{*}$ satisfying

If $t\in\mathsf{support}(M(s))$, then $|t_{i}|=1$ for all $i\in[n]$, which implies $\check{W}$ satisfies this requirement. In the analysis above, we used Hoeffding’s inequality to show that the sum of randomized roundings is close to (within $r$ of) the unrounded sum with high probability and we carry this failure probability $e^{-r^{2}/2n}$ into the final result. ∎

Let $A:\mathcal{X}^{n}\to\mathcal{Y}$ be $(\varepsilon,\delta)$-DP (with respect to replacement). Let $q:\mathcal{Y}\times\mathcal{X}\to$, and denote $q(y,x)=\frac{1}{n}\sum_{i}^{n}q(y,x_{i})\in$ for $y\in\mathcal{Y}$ and $x\in\mathcal{X}^{n}$. Let $P$ be a distribution on $\mathcal{X}$. Then, for all $\gamma,\eta\geq 0$, we have

where $\check{W}\leftarrow\mathsf{Binomial}\left(n,\frac{e^{\varepsilon}}{e^{\varepsilon}+1}\right)$.

The proof relies on Lemma B.2, which considers $x^{+},x^{-}\in\mathcal{X}^{n}$ to be fixed. We now average the lemma over these being i.i.d. samples from $P$, which gives

where $\check{W}\leftarrow\mathsf{Binomial}\left(n,\frac{e^{\varepsilon}}{e^{\varepsilon}+1}\right)$. Since the samples from $P$ are independent, the coordinates of $X^{+}$ and $X^{-}$ are interchangeable, so

for $v=\gamma n\geq 0$. Setting $r=n\eta$ yields the result. ∎

Let $X,\widetilde{X}\leftarrow P^{n}$ be two independent samples. Let $Y\leftarrow A(X)$. Let $\check{W}\leftarrow\mathsf{Binomial}\left(n,\frac{e^{\varepsilon}}{e^{\varepsilon}+1}\right)$. By Proposition B.3, for all $\gamma,\eta\geq 0$, we have

By Hoeffding’s inequality, for all $\eta\geq 0$, we have

By a union bound, for all $\gamma\geq\eta\geq 0$, we have

Combining inequalities yields the result:

We now briefly compare our results to the prior work on the connection between DP and generalization [DFHPRR15a, DFHPRR15, BNSSSU16, FS17, JLNRSMS19]. We focus on the work of [JLNRSMS19] as it has the sharpest results in the literature.

Note that the prior work is focused on the setting of adaptive data analysis, while we are focused on the setting of auditing. This difference is mostly cosmetic, but there is a material difference when the prior results are applied to our setting: In addition to outputting guesses, the prior works assume that the algorithm outputs a differentially private estimate of the number of correct guesses. The guarantee then is that this differentially private estimate is close to the distributional average (i.e., only half of the guesses being correct). In contrast, for auditing, we want the true number of correct guesses to be close to the distributional average and don’t produce a DP estimate. We can convert between these two settings using the triangle inequality.

Below we state the accuracy guarantee that we compare against, followed by a corollary of Theorem B.1 that applies the triangle inequality and a union bound to ensure that it is directly comparable.

Then, for all $\gamma\geq\frac{3}{2}\eta\geq 0$, we have

where $\check{W}\leftarrow\mathsf{Binomial}\left(n,\frac{e^{\varepsilon}}{e^{\varepsilon}+1}\right)$.

Equations 13 and 14 are directly comparable, but it is not immediately obvious how they compare. By setting $\delta=0$, $\gamma=\frac{e^{\varepsilon}-1}{e^{\varepsilon}+1}+c$, $\eta=\frac{2}{5}c$, and applying Hoeffding’s inequality to $\check{W}$, we can simplify Equation 14 to

For comparison, setting $\delta=0$ in Equation 13 gives

Now we can compare the results more easily. The $e^{\varepsilon}-1$ term in the accuracy bound of [JLNRSMS19] is improved to $\frac{e^{\varepsilon}-1}{e^{\varepsilon}+1}$ in our result, which is an improvement by a factor of at least two. This is (arguably) the dominant term, so our result is a significant improvement. In particular, if $\varepsilon\geq\log 2$, then Equation 13 gives a vacuous bound (since the value of $q$ is always in $$anyway), while our bound can be non-vacuous for any value of$\varepsilon$(as$\frac{e^{\varepsilon}-1}{e^{\varepsilon}+1}<1$).

However, there is another term in the accuracy bound – i.e., $c$. The failure probability either has a $1/c$ multiplicative factor or a $3\cdot e^{-n\frac{2}{25}c^{2}}$ additive factor. How these compare depends on the value of $\beta$. To give a concrete comparison, suppose $\varepsilon=1/3$, $n=2000$, $\beta=\delta=10^{-5}$, and we want a final failure probability of $0.05$; then Theorem B.4 gives an error guarantee of $\alpha+0.397$, while Corollary B.5 gives $\alpha+0.308$.

Appendix C Mutual Information Bounds from DP

Our framework for the theoretical analysis (§5) is inspired by that of [SZ20]. In this appendix, we use our analysis to also improve one of their results. Specifically, they show that if $M:\{-1,1\}^{m}\to\mathcal{Y}$ satisfies $(\varepsilon,\delta)$-DP and $S\in\{-1,1\}^{m}$ is uniformly random, then

where $I(\cdot;\cdot)$ denotes the mutual information.Throughout this paper we use natural logarithms (so $\log e=1$), including when defining information-theoretic quantities like mutual information. However, it is common to use base-2 logarithms in information theory (i.e., $\log_{2}e\approx 1.44$). To avoid confusion, the statements (outside proofs) in this section are stated in a redundant way so that they would be correct regardless of the base of the logarithm, as long as we are consistent. Prior work [DFHPRR15, BS16] showed that, if $M:\mathcal{X}^{m}\to\mathcal{Y}$ satisfies $(\varepsilon,0)$-DP and $S\in\mathcal{X}^{m}$ has as product distribution, then

The latter result is numerically better than the former result, but only holds for pure DP. (The latter result is also not restricted to binary inputs. However, if we do not restrict the input at all, then it is not possible to prove bounds under approximate DP.)

We improve the bound to the following. If $M:\{-1,1\}^{m}\to\mathcal{Y}$ satisfies $(\varepsilon,\delta)$-DP and $S\in\{-1,1\}^{m}$ is uniformly random, then

Let $M:\{0,1\}^{n}\to\mathcal{Y}$ satisfy $(\varepsilon,\delta)$-DP. Let $S\in\{0,1\}^{n}$ be sampled from $\mathsf{Bernoulli}(p)^{n}$. Then

where $h(p):=p\log(1/p)+(1-p)\log(1/(1-p))$ is the binary Entropy function.

We apply the chain rule and convexity of KL divergence [FS18, Lemma 3.7]:

Fix $i\in[n]$ and fix $s_{-i}\in\{0,1\}^{n-1}$. Now we must analyze

where $Q_{t}:=tM(1,s_{-i})+(1-t)M(0,s_{-i})$ for $t\in$.

Since $M$ is $(\varepsilon,\delta)$-DP, we have $Q_{t}(S)\leq e^{\varepsilon}\cdot Q_{1-t}(S)+\delta$ for all measurable $S\subset\mathcal{Y}$ and $t\in\{0,1\}$. Thus we can apply Lemma 5.5: There exist distributions $Q_{0}^{\prime},Q_{0}^{\prime\prime},Q_{1}^{\prime},Q_{1}^{\prime\prime}$ on $\mathcal{Y}$ such that $Q_{0}=(1-\delta)\cdot Q_{0}^{\prime}+\delta\cdot Q_{0}^{\prime\prime}$ and $Q_{1}=(1-\delta)\cdot Q_{1}^{\prime}+\delta\cdot Q_{1}^{\prime\prime}$ and $e^{-\varepsilon}\cdot Q_{0}^{\prime}(S)\leq Q_{1}^{\prime}(S)\leq e^{\varepsilon}\cdot Q_{0}^{\prime}(S)$ for all measurable $S\subset\mathcal{Y}$.

so that $Q_{0}^{\prime}=\frac{e^{\varepsilon}\cdot R_{0}+R_{1}}{e^{\varepsilon}+1}$ and $Q_{1}^{\prime}=\frac{e^{\varepsilon}\cdot R_{1}+R_{0}}{e^{\varepsilon}+1}$. Hence

This decomposition (which was first used by [KOV15]) states that we can view $Q_{s_{i}}=M(s_{i},s_{-i})$ as a postprocessing of an $(\varepsilon,\delta)$-DP randomized response on the bit $s_{i}$. That is, with probability $\delta$, we output the bit $s_{i}$ with a flag indicating certainty; with probability $\frac{e^{\varepsilon}(1-\delta)}{e^{\varepsilon}+1}$, we output $s_{i}$ with an uncertain flag; and, with probability $\frac{1-\delta}{e^{\varepsilon}+1}$, we output $1-s_{i}$ with the uncertain flag. We can postprocess this to generate a sample from $Q_{s_{i}}=M(s_{i},s_{-i})$ as follows. If we receive $b\in\{0,1\}$ with the uncertain flag, then output a sample from $R_{b}$. If we receive $b\in\{0,1\}$ with the certain flag, then output a sample from $Q_{b}^{\prime\prime}$.

To be formal, define two distributions on the set $=\{1,2,3,4\}$ by

Define the a randomized postprocessing function $F:\to\mathcal{Y}$ by $F(1)=R_{0}$, $F(2)=R_{1}$, $F(3)=Q_{0}^{\prime\prime}$, and $F(4)=Q_{1}^{\prime\prime}$. Then we have $F(\widetilde{Q}_{0})=Q_{0}$ and $F(\widetilde{Q}_{1})=Q_{1}$.

Now we use the postprocessing property (a.k.a. the data processing inequality):

A tedious calculation now yields the bound:

Combining inequalities and summing over $i\in[n]$ yields the first part of the result. The final part of the result is the bound

which can be verified by showing that $g(0)=g^{\prime}(0)=0$ and $\forall\varepsilon\geq 0~{}~{}g^{\prime\prime}(\varepsilon)\leq\frac{1}{4}$ (or by plotting it). ∎

Appendix D Implementation of Theorem 5.2

On the next page is Python pseudocode implementing Corollary 5.4. Some example usage:

Suppose the auditor correctly guesses $v=75$ out of $m=r=100$ examples, with no abstentions. We have $\frac{75}{100}=\frac{3}{4}=\frac{e^{\log 3}}{e^{\log 3}+1}$. So we would expect this to correspond roughly to $\varepsilon=\log 3\approx 1.09$. Theorem 5.2 gives p-value of $0.553$ for the null hypothesis $\varepsilon\leq\log 3$ and $\delta=0$; to obtain this result call p_value_DP_audit(100,100,75,math.log(3),0) in the code below. If we want 95% confidence, we obtain the lower bound $\varepsilon\geq 0.702$ by calling get_eps_audit(100,100,75,0,0.05). If we set $\delta=10^{-4}$, we obtain the weaker lower bound $\varepsilon\geq 0.699$ by calling get_eps_audit(100,100,75,1e-4,0.05).