Unleashing the Power of Randomization in Auditing Differentially Private ML
Authors: Krishna Pillutla
Galen Andrew
Peter Kairouz
Hugh Brendan McMahan
Alina Oprea
Sewoong Oh
Venue: NeurIPS 2023 poster (2023)
Keywords: Differential privacy auditing
multiple canaries
randomization
lifting
adaptive confidence intervals
TL;DR: We present a rigorous methodology for auditing DP with multiple random canaries, based on an equivalent "lifted" definition of DP, multiple dependent hypothesis tests, and novel adaptive confidence intervals.

Abstract: We present a rigorous methodology for auditing differentially private machine learning by adding multiple carefully designed examples called canaries. We take a first principles approach based on three key components. First, we introduce Lifted Differential Privacy (LiDP) that expands the definition of differential privacy to handle randomized datasets. This gives us the freedom to design randomized canaries. Second, we audit LiDP by trying to distinguish between the model trained with $K$ canaries versus $K-1$ canaries in the dataset, leaving one canary out. By drawing the canaries i.i.d., LiDP can leverage the symmetry in the design and reuse each privately trained model to run multiple statistical tests, one for each canary. Third, we introduce novel confidence intervals that take advantage of the multiple test statistics by adapting to the empirical higher-order correlations. Together, this new recipe demonstrates significant improvements in sample complexity, both theoretically and empirically, using synthetic and real data. Further, recent advances in designing stronger canaries can be readily incorporated in the new framework.

Unleashing the Power of Randomization in Auditing Differentially Private ML
Krishna Pillutla'
Galen Andrew!
Peter Kairouz Sewoong Oh1.3
H. Brendan McMahan'
Alina Oprea
GGoole Research
Northeastern University
University of Washington
Abstract
We present a rigorous methodology for auditing differentially private machine learning algorithms by adding multiple carefully designed examples called ca- naries. We take first principles approach based on three key components. First, we introduce Lifted Differential Privacy (LiDP) which expands the definition of differential privacy to handle randomized datasets. This gives us the freedom to de- sign randomized canaries. Second, we audit LiDP by trying to distinguish between the model trained with K canaries versus K 1 canaries in the dataset, leaving one canary out. By drawing the canaries i.i.d., LiDP can leverage the symmetry in the design and reuse each privately trained model to run multiple statistical tests, one for each canary. Third, we introduce novel confidence intervals that take advantage of the multiple test statistics by adapting to the empirical higher-order correlations. Together, this new recipe demonstrates significant improvements sample complexity, both theoretically and empirically, using synthetic and real data. Further, recent advances in designing stronger canaries can be readily incorporated into the new framework.
Introduction
Differential privacy (DP), introduced in [22], has gained widespread adoption by governments, companies, and researchers by formally ensuring plausible deniability for participating individuals. This is achieved by guaranteeing that curious observer of the output of a query cannot be confident in their answer to the following binary hypothesis test: did a particular individual participate in the dataset not? For example, introducing sufficient randomness when training model certain dataset ensures a desired level of differential privacy. This in turn ensures that an individual's sensitive information cannot be inferred from the trained model with high confidence. However, calibrating the right amount of noise can be a challenging process. It is easy to make mistakes in implementing DP mechanism due intricacies involving micro-batching, sensitivity analysis, and privacy accounting. Even with correct implementation. there are several incidents of published DP algorithms with miscaleulated privacy guarantees that falsely report higher levels of privacy [16, 34, 40, 57, 58). Data-driven approaches to auditing mechanism for violation of a claimed privacy guarantee can significantly mitigate the danger of unintentionally leaking sensitive data.
Popular approaches for auditing privacy share three common components [e.g. 31-33, 45, 69). Conceptually, these approaches are founded the definition of DP and involve producing counterex- amples that potentially violate the DP condition. Algorithmically. this leads to the standard recipe of injecting a single carefully designed example, referred to canary, and running statistical hypothesis test for its presence from the outcome of the mechanism. Analytically, a high-confidence bound on the DP condition derived by calculating the confidence intervals of the corresponding Bernouli random variables from independent trials of the mechanism.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Recent advances adopt this standard approach and focus on designing stronger canaries to reduce the number of trials required to successfully audit DP [e.g., 31-33, 39, 45, 69]. However, each independent trial can be as costly training a model from scratch; refuting a false claim of (s, 5eP with minimal number of samples is of utmost importance. In practice, standard auditing can require training on the range of thousands to hundreds of thousands of models [e.g., 60]. Unfortunately, under the standard recipe, we are fundamentally limited by the l/Vn sample dependence of the Bernoulli confidence intervals.
Contributions. We break this 1/vzi barrier by rethinking auditing from first principles.
We propose to audit an equivalent definition of DP, which we call Lifted DP in $3.1. This gives an auditor the freedom to design a counter-exampee consisting of random datasets and rejection sets. This enables adding random canaries, which is critical in the next step. Theorem shows that violation of Lifted DP implies violation of DP, justifying our framework.
Lifted DP:
2. Auditing Lifted DP with Multiple Random Canaries: We propose adding K > 1 canaries under the alternative hypothesis and comparing it against a dataset with K - canaries, leaving one canary out. If the canaries are deterministic, we need K separate null hypotheses; each hypothesis leaves one canary out. Our new recipe overcomes this inefficiency in $3.2 by drawing random canaries independently from the same distribution. This ensures the exchangeability of the test statistics, allowing us to reuse each privately trained model to run multiple hypothesis tests in a principled manner. This is critical in making the confidence interval sample efficient.
3. Adaptive Confidence Intervals:
Due to the symmetry of our design, the test statisties follow a special distribution that call eXchangeable Bernoulli (XBern). Auditing privacy boils down to computing confidence intervals on the average test statistic over the K canaries included in the dataset. If the test statistics are independent, the resulting confidence interval scales as 1 1/Vnk. However, in practice, the dependence is non-zero and unknown. We propose new and principled family of confidence intervals in $3.3 that adapts to the empirical higher-order correlations between the test statistics. This gives significantly smaller confidence intervals when the actual dependence is small, both theoretically (Proposition 4) and empirically.
4. Numerical Results: We audit an unknown Gaussian mechanism with black-box access and demonstrate (up to) 16x improvement in the sample complexity. We also show how to seamlessly lift recently proposed canary designs in our recipe to improve the sample complexity on real data.
2 Background
We describe the standard recipe to audit DP. Formally, adopt the so-called add/remove definition of differential privacy; our constructions also seamlessly extend to other choices of neighborhoods as we explain in B...
Definition 1 (Differential privacy). A pair of datasets, (Do, D1), is said to be neighboring if their
sizes differ by one and the datasets differ in one entry: D2 Dol + DD \. D₂ 1. A randomized mechanism A - R is said to be (c, -Diffefrrettially Private (DP) for some & 2 0 and 5 E [0, 1] it satisfies (A(Di) E R) S et P (A((())) E R) + 6, which is equivalent to
E 2 log (P(A(D)) E R) - 6) - ((A(D)) R),
for all pairs of neighboring datasets, (Do, D1). and all measurable sets, R C R, of the output space R. where PA over the randomness internal to the mechanism A. Here, 2" is a space of datasets.
For small E and 6, one cannot infer from the output whether particular individual is in the dataset or not with a high success probability. For a formal connection, we refer to [35]. This naturally leads to standard procedure for auditing a mechanism A claiming (e, 8)DDP present (Do, Dr. R) e Z x Z x R that violates Eq. (1) as a piece of evidence. Such a counter-example confirms that an adversary attempting to test the participation of an individual will succeed with sufficient probability, thus removing the potential for plausible deniability for the participants.
Standard Recipe: Adding a Single Canary. When auditing DP model training (using e.g. DP- SGD [1, 54]), the following recipe is now standard for designing a counter-example (Da, D1, R) [31-33, 45, 69]. A training dataset Do is assumed to be given. This ensures that the model under scrutiny matches the use-case and is called a null hypothesis. Next, under corresponding alternative hypothesis, a neighboring dataset D1 = Do U {c} is constructed by adding single carefully-designe

---

example E 2, known as a canary. Finally, Eq. (1) is evaluated with choice of R called a rejection set. For example, one can reject the null hypothesis (and claim the presence of the canary) if the loss on the canary is smaller than a fixed threshold; R is set of models satisfying this rejection rule.
Bernoulli Confidence Intervals. Once counter-example (Do: Dr: R) is selected, we are left to evaluate the DP condition in Eq. (I). Since the two probabilities in the condition cannot be directly evaluated, we rely on the samples of the output from the mechanism, e.g. models trained with DP-SGD. This is equivalent to estimating the expectation, ((((D)) E R) for D E (Do. D. of a Bernoulli random variable, I(A(D) E R), from n i..dd samples. Providing high confidence intervals for Bernoulli distributions is a well-studied problem with several off-the-shelf techniques, such as Clopper-Pearson, Jeffreys, Bernstein, and Wilson intervals. Concretely, let IP,, (A(D) E R) denote the empirical probability of the model falling in the rejection set in n independent runs. The standard intervals scale as [P((ADDo) E R) P,, (A(()) E R)] S Cone 11/2 and [P(A(D;) e R) Tp, (A)),) E R)| S Cjn-1/2 for constants Co and C₁ independent of n. If A satisfies a claimed Oe in Eq. (1), then the following finite-sample lower bound holds with high confidence:
- 6) log (A(Do) E R) + E 2 En log (A(Di) E R) C V'
Ca Vn
(2)
Auditing(s, 8DD amounts to testing the violation of this condition. This is fundamentally limited by the n 1/2 dependence of the Bernoulli confidence intervals. Our goal is to break this barrier.
Notation. While the DP condition is symmetric in (Do, D1), we use Do, D2 to refer to specific hypotheses. For symmetry, we need to check both conditions: Eq. (1) and its counterpart with Do, D2 interchanged. We omit this second condition for notational convenience. We use the shorthand We refer to random variables by boldfaced letters (e.g. D is a random dataset).
[k] :
Related Work. We provide a detailed survey in Appendix A. A stronger canary (and its rejection set) can increase the RHS of (I). The resulting hypothesis test can tolerate larger confidence intervals, thus requiring fewer samples. This has been the focus of recent breakthroughs in privacy auditing in [32, 39, 41, 45, 60]. They build upon membership inference attacks [e.g. 12, 53, 68] to measure memorization. Our aim is not to innovate on this front. Instead, our framework can seamlessly adopt recently designed canaries and inherit their strengths as demonstrated in 55 and 56.
Random canaries have been used in prior work, but for making the canary -iit----ittiittionn in a computationally efficient manner. No variance reduction is achieved by such random canaries. Adding multiple (deterministic) canaries has been explored in literature but for different purposes. [32, 39] include multiple copies of the same canary to make the canary easier to detect while paying for group privacy since the paired datasets differ in multiple entries (see $3.2 for a detailed discussion).
[42, 69] propose adding multiple distinct canaries to reuse each trained model for multiple hypothesis tests. However, each canary is stronger than a single canary case, and the resulting auditing suffers from group privacy. When computing the lower bound on e, however, group privacy is ignored and the test statistics assumed be independent without rigorous justification. [2] avoids group privacy in the federated scenario where the adversary has the freedom to return a canary gradient update of choice. The prescribed random gradient shows good empirical performance. The confidence interval is not rigorously derived. Our recipe for injecting multiple canaries without a group privacy cost with rigorous confidence intervals can be incorporated into these works to give provable lower bounds.
In an independent and concurrent work, Steinke et al. [56] also consider auditing with randomized canaries that are boisson-sampless i.c., each canary is included excluded independently with equal probability. Their recipe involves computing an empirical lower bound by comparing the accuracy (rather than the full confusion matrix as in case) from the possibly dependent guesses with the worst-case randomized response mechanism. This allows them to use multiple dependent observations from single trial to give high probability lower bound on e. Their confidence intervals, unlike the ones we give here, are non-adaptive and worst-case.
3 A New Framework for Auditing DP Mechanisms with Multiple Canaries
We define Lifted DP, a new definition of privacy that is equivalent to DP ($3.1). This allows us to define a new recipe for auditing with multiple random canaries, as opposed to a single deterministic canary in the standard recipe, and reuse each trained model to run multiple correlated hypothesis tests
3

---

in principled manner ($3.2). The resulting test statistics form a vector of dependent but exchangeable indicators (which we call an eXchangeable Bernoulli or XBem distribution), as opposed to a single Bernoulli distribution. We leverage this exchangeability to give confidence intervals for the XBern distribution that can potentially improve with the number of injected canaries ($3.3). The pseudocode of our approach is provided in Algorithm 1.
3.1 From DP to Lifted DP
To enlarge the design space of counter counter-examples, we introduce an equivalent definition of DP.
Definition 2 (Lifted differential privacy). Let P denote joint probability distribution over (Do, D1. R) where (Do, Di) E 2" x 2* is pair of random datasets that are neighboring (as in the standard definition of neighborhood in Definition 1) with probability one and let R C R denote a random rejection set. We say that a randomized mechanism A : Z + R satisfies (s, d'-Lifted Differrnniall Privacy (LiDP) for some 2 and E [0, if, for all independent of A, we have
PAP((A(D:) R) S e PAP(((((D) R) 6.
In Appendix A.3, we discuss connections between Lifted DP and other existing extensions of DP, such as Bayesian DP and Pufferfish, that also consider randomized datasets. The following theorem shows that LiDP is equivalent to the standard DP, which justifies our framework of checking the above condition; if a mechanism A violates the above condition then it violates (e, 8)-DP.
Theorem 3. randomized algorithm A is (E, LiDD iff A is (e
A proof is provided in Appendix B. In contrast to DP, LiDP involves probabilities over both the internal randomness of the algorithm A and the distribution P over (Do, D1, R). This gives the auditor greater freedom to search over a lifted space of joint distributions over the paired datasets and rejection set; hence the name Lifted DP. Auditing LiDP amounts to constructing randomized (as emphasized by the boldface letters) counter-example (Do, D1, R) that violates (3) as evidence.
3.2 From a Single Deterministic Canary to Multiple Random Canaries
Our strategy is to turn the LiDP condition in Eq. (3) into another condition in Eq. (4) below; this allows the auditor to reuse samples, running multiple hypothesis tests on each sample. This derivation critically relies on our carefully designed recipe that incorporates three crucial features: (a) binary hypothesis tests between pairs of stochastically coupled datasets containing K canaries and K - 1 canaries, respectively, for some fixed integer K, (b) sampling those canaries i.i.d. from the same distribution, and (c) choice of rejection sets, where each rejection set only depends on single left-out canary. We introduce the following recipe, also presented in Algorithm 1.
We fix given training set D and a canary distribution Peunury over 2. This ensures that the model under scrutiny is close the use case. Under the alternative hypothesis, we train model on a randomized training dataset Dj D U {cI...., ) augmented with K random canaries drawn i.i.d. from Pranary- Conceptually, this is be tested against K leave-one-out (LOO) null hypotheses. Under the hthh null hypothesis for each k [K]. we construct coupled dataset, = DU (c Ck-1, Ck+1,... ck}, J. with K- - canaries, leaving the htth canary out. This coupling of K 1 canaries ensures that (Do,e, D1) is neighboring with probability one. For each left-out canary, the auditor runs binary hypothesis test with a choice of a random rejection set RR- We restrict R2 to depend only on the canary es that is being tested and not the index k. For example, R3 can be the set of models achieving loss on the canary below predefined threshold r.
The goal of this LOO construction is reuse each trained private model to run multiple tests such that the averaged test statistic has a smaller variance for a given number of models. Under the standard definition of DP, one can still the above LOO construction but with fixed and deterministic canaries. This gives no variance gain because evaluating ((A(Do,s) E R&.) in Eq. (1) or its averaged counterpart (1/K) EK
K k= P(A((o,)) R&) requires training model get one sample from the test statistic I(A(DD,R) E RR). The key ingredient in reusing trained models is randomization.
We build upon the LiDP condition in Eq. (3) by noting that the test statistics are exchangeable for i..dd canaries. Specifically, we have for any E [K] that P(A(Do,s) E R&) (P(A(Do,k) E Rx) P((((),.)) E Rt) for any canary d, drawn ii.d. from Peanary and its corresponding
4

---

Algorithm Auditing Lifted DP
Input: Sample size nt number of canaries K, number of null tests m. DP mechanism A, training set
D, canary generating distribution Paanary. threshold 7, failure probability B, privacy E [0, 1].
1: for i = ,. 72
do
2: Randomly generate K + m canaries {el..... CalL...,CKKer CK. ,,..., .. ii.d. from Peannry.
3: Do f D U {ci..... CK- 11. D2 t D DU(e fet,....,cx''
4: Train two models 0,+ & A(o)) and 0, t A(D))
5: Record test statistics (1) < (T(Jo, (cx) < <=)) and y + (c)) < < )e(m)) B/2) and Po + XBernUpper (LV (i(m)) 8/2) 6: Set P1 XoernLower (1z) NE(M))
7: Return én <- log ((2, P)) and a guarantee that P(e < En) S 3.
rejection set RjJ that are statistically independent of Do.k. Therefore, we can rewrite the right side of Eq. (3) using m i.i.d. test canaries ci...., Crp P Cauaayy and a single trained model A(Do,)) as
# K PA=IPA(((( E R2)
PApLAA(A(DD.O) R2)+ +
(4)
Checking this condition is sufficient for auditing LiDP and, via Theorem 3, for auditing DP. For each model trained on Di, record the test statistics of K (correlated) binary hypothesis tests. This is denoted by a random vector æ = (I(A(Di) E R= E (0,, 1)x where R& is a rejection set that checks for the presence of the hith canary. Similar to the standard recipe, we train n models to obtain n i.i.d. samples (11), (n) E {0, 13x to estimate the left side of (4) using the empirical mean:
(5) where the subscript one in رi denotes that this is the empirical first moment. Ideally, if the K tests independent, the corresponding confidence interval is smaller by factor of VK. In practice, the K tests are correlated and the size of the confidence interval depends on their correlation. We derive principled confidence intervals that leverage the empirically measured correlations in 33.3. We can define y E {0, } and its mean úJ analogously for the null hypothesis. We provide pseudocode in Algorithm as an example guideline for applying our recipe to auditing DP training, where fe(z) is the loss evaluated on an example for model 0. XBernLower() and XBernUppert respectively return the lower and upper adaptive confidence intervals from 33.3. We instantiate Algorithm I with concrete examples of canary design in $5.
A 01:= - R E
E [0,
Our Recipe vs. Multiple Deterministic Canaries. An alternative with deterministic canaries would be to test between Do with no canaries and D, with K canaries such that we can get K samples from single trained model Dp, one for each of the K test statistics (T(A(Do) E Rk)) However, due to the fact that Dj and Do are now at Hamming distance K, this suffers from group privacy; required to audit for much larger privacy leakage of (Ke, ((eKs 1)/(c 1))8)-DP. Under the (deterministic) LOO construction, this translates into (1/K) EK= P(((())) E Ra) S e (1/K) K R= P(A(Dp) E R₂) + ((e - 1)/(c= - 1))5, where if one canary violates the group privacy condition then the average also violates it. We can reuse a single trained model to get K test statistics in the above condition, but each canary is distinct and not any stronger than the one from (e, 6)DDP auditing. One cannot obtain stronger counterexamples without sacrificing the sample gain. For example,
repeat the same canary K times as proposed in [32]. This makes it easier to detect the canary, making a stronger counter-example, but there is no sample gain as we only get one test statistic per trained model. With deterministic canaries, there is way to avoid this group privacy cost while our recipe does not incur it.
3.3 From Bernoulli Intervals to Higher-Order Exchangeable Bernoulli (XBern) Intervals
The LiDP condition in Eq. (4) critically relies on the canaries being sampled i.i.d. and the rejection set only depending on the corresponding canary. For such a symmetric design, auditing boils down to deriving a Confidence Interval (CI) for special family of distributions that we call Exchangeable Bernoulli (XBern). We derive the CI for the alternate hypothesis, i.e., the left side of Eq. (4). The CI under the null hypothesis is analogous.
5

---

Computing the Bersusin CJ. Row.Firdra
Loading Cociiiion of Wison vo. Berstinn
Renens
22
by 20
Witen
21 + 22
21 + 22 + o
21 + 22 + 0 o
Protabiiy
Figure 1: Bias illustration: Consider the sum query 21 + 22 with inputs. Its DP version produces point the blue circle w.h.p. due to the noise & ~ (0, I) scaled by a. When auditing with random canary it contributes additional randomness (red disc) leading smaller effective privacy parameter s.
Figure 2: Left: The Bernstein CI 1M, Toj can be found by equating the two sides of Bernstein's 's inequality in Eq. (6). Right: The asymptotic Wilson CI is tightening of the Bernstein CI with smaller 1/vn coefficient (shown here) and no 1/n term.
Recall that zy := I(A E Re) denotes the test statistic for the hthh canary. By the symmetry of design, x E {0, 1) is exchangeable random vector that is distributed as exponential family. Further, the distribution of x is fully defined by a K-dimensional parameter (.4,.... PK) where j the fhh moment of æ. We call this family XBern. Specifically, this implies permutation invariance of the higher-order moments: E|æ,, ... Tjel = Es ... [xe] for any distinet sets of indices (ix)
and [E() for any l S K. For example, μ == (1/KK) Ex=1 zyg, which is the LHS of (4).
Using samples from this XBern, we aim to derive a CI on μ1 around the empirical mean fú in (5).
Bernstein's 's inequality applied to our test statistic m, := (1/K) Σ 2 gives,
2 (2g((2 Var(m)) + 1lg(2/33) V
A - MI S
(6)
Y2
3n
w.p. at least 1 - 3. Bounding Var(m)1 S (1 M1) since m, E [0, 1] a.s. and numerically solving the above inequality for μu gives CI that scales as 1/vTi- see Figure 2 (left). We call this the 1 ooddrr Bernstein bound, as it depends only on the 1st moment μ사, Our strategy is to measure the (higher-order) correlations between 23 's to derive tighter CI that adapts to the given instance. This idea applies to any standard CI. We derive and analyze the higher order Bernstein intervals here, and experiments use Wilson intervals from Appendix C; see also Figure 2 (right).
Concretely, we can leverage the 2nd order correlation by expanding
Var(m;) -ें (m1 p22 + (p2 (4) where P2 = K[K-T En, <kye(k] E [E Tzal-
Ideally, when the second order correlation μl2 - 2 E|x || - B[x [Baa2] equals O, we have Var(mi) M1 -1--ao (1(1-1)) adapt to the actual level of correlation of æ by further estimating the 2nd moment μl from samples. Let B2 be the first-order Bernstein upper bound #2 such that P(ue S TT)) 2 1 - 8. On this event,
factor of K improvement over the worst-case. Our higher-order CIs
Var(m1) I
X (11 (2) (12 f
Combining this with (6) gives us the 2nd -order Bernstein bound on 141 valid w.p. 1 - 2,3. Since 122 S fiz + 1/vn where fá is the empirical estimate of μ22, the prder bound scales as
nk +
A2 A
(8)
n3/4
where constants and log factors are omitted. Thus, our 2nd-order CI can be as small as 1/VnK + 1/13/4 (when iA2 ~ (22) or as large as 1/vn (in the worst-case). With small enough correlations of رم - م = (1/K), this suggests a choice of K = =O(VT) to get CI of 1//2/4. In practice, the correlation is controlled by the design of the canary. For the Gaussian mechanism with random canaries, the correlation indeed empirically decays as KK, as we see in $4. Thus, the CI decreases monotonically with K. This is also true for the CI under the null hypothesis with K replaced by m.
However, there a qualitative difference between the null and alternate hypotheses. Estimation under the alternate hypothesis incurs larger bias as the number K of canaries increases this is due

---

e 220, K== vi, d=
1.0, 1006,
5. 4.0, 1006,
Empincal lower bound
2.6
Empircal lower bound 5
1.20
Empincal lower bound g
12
1.00
233
16x gain
4x gain
21
gb
Number trials
Number of canaries
Dimension
DP Wilson
LDP 1st-Order Wilson
LIDP 4. 2nd-Orda Wilson
LIDP
4th+Order Wilson
For Gaussian mechanisms, the proposed LiDP-based auditing with canaries provides a significant gain in the required number of trials to achieve a desired level of lower bound & on the privacy. Center: Increasing the number of canaries trades off the bias and the variance, with our prescribed K v achieving good performance. Right: Increasing the dimension makes the canaries less correlated, thus achieving smaller confidence intervals, and larger We shade the standard error over repetitions.
Figure Left:
to the additional randomness from adding Figure 1. The optimal choice of K balances the bias and variance. On the other hand, estimation under the null hypothesis incurs no bias and a larger number m of test canaries always helps. We return to the bias-variance tradeoff in 84.
canaries into the training process, illustrated in
Higher-order intervals. We recursively apply this method by expanding the variance of higher- order statistics, and derive higher-order Bernstein bounds. The next recursion uses empirical 3rd and 4th moments fts and fi to get the -order Bernstein bound which scales as
V A2 Ail
na/4 Pi 22 22)1//
1/4 + n7/8
(9)
nK
Ideally, when the 4th ooder correlation is small enough, |i - O(1KK) O(1/K), (along with the 2nd-order correlation, j22 2 this 4th-order CI scales as L/n2/8 with a choice of K = O(n3/4)
improving upon the 2nd-order CI of 1/n3/4, We can recursively derive even higher-order Cls, but find in $4 that the gains diminish rapidly. In general, the thh order Bernstein bounds achieve CIs scaling as 1/n (2- with choice of K ((n(E-1)/E This shows that the higher-order CI decreases in the order f of the correlations used; we refer to Appendix C for details.
Proposition 4. For any positive integer l that a power of two and == (t-(6_) suppose we have samples from K-ddmmnssional XBemn distribution with parameters (H1,.... pK) If all grth -order correlations scale as 1/K, i.e., |p2e - 12/1 = (), all E' < l and l' is power of two, then the hh -order Bernstein bound is 1141 - f = O1nn/(2111////n
Simulations: Auditing the Gaussian Mechanism
Setup. We consider a simple sum query ((D) ΣxED over the unit sphere Z = {2 E Rd ||ll2 = 17. We want to audit a Gaussian mechanism that returns ((D) of with standard Gaussian E E~ {~N(0, Ia) and calibrated ensure (e, DDP. We assume black-box access, where do not know what mechanism we are auditing and we only access it through samples of the outcomes. A white-box audit is discussed in SA.1. We apply our new recipe with canaries sampled uniformly at random from 2. Following standard methods [e.g. 23]. we declare that a canary C₁ is present c A(D) > T for a threshold learned from separate samples. For more details and additional results, see Appendix E. A broad range of values of K (between 32 and 256 in Figure 3 middle) leads to good performance in auditing LiDP. We use K = Vni (as suggested by our analysis in (8)), K test canaries, and the 2odder Wilson estimator (as gains diminish rapidly afterward) as reliable default setting.
Sample Complexity Gains. In Figure 3 (left), the proposed approach of injecting K canaries with 2nd order Wilson interval (denoted "LiDP =2dd-Order Wilson") reduces the number of trials, n, needed to reach the same empirical lower bound, é, by 4x to 16x, compared to the baseline of injecting single canary (denoted "DP+*ilson"). We achieve é, = 0.85 with n = 4096 (while the bascline requires 65536) and é, 0.67 with 1024 (while the baseline requires 4096).
7

---

1.0, a 1096, 5
2.0, i 1006 109
1.0, n 60636 W
Difference of empinicll
0.38-
Correation Maxure
Moment starisites
0.31
0:30
0.8
20
0.8
.4.0
-432
Number canaries X
Number of canaries
Dimension
K
vi
Var. Gain
Ad
1/d
Al
Blas Goin
Net Gain
jel
Figure 4: Left: Separating the effects of hias and variance in auditing LiDP; cf. definition (10). Center & The correlations between the test statistics of the canaries decrease with K and d, achieving smaller Cls.
Right:
Number of Canaries and Bias-Vars Variance Tradeoffs. In Fig. 3 (middle), LiDP auditing with 2 order Cls improve with increasing canaries up a point and then decreases. This is due bias-variance tradeoff, which we investigate further in Figure 4 (left). Let É(K, E) denote the empirical privacy lower bound with canaries using an 4hh order interval, e.g., the baseline 6(1, 1). Let the bias from injecting K canaries and the variance gain from -odder interval respectively be
ABias(K)- == 1) 1), and Var(K, = ((,E) 1)
(10)
In Figure 4 (left), the gain ABias K) from bias is negative and gets other canaries introduce more randomness that makes the test
with increasing K; when
testing for each canary, the more private and hence lowers the & (see also Figure 1. The gain A Var(K) in variance is positive and increases with before saturating. This improved "variance" of the estimate is a key benefit of of these effects. This trade-off
framework. The net improvement ě(K, e) é(1, 1) is between bias and variance explains the concave shape of é in K.
Next, from Figure 5 that larger number of test canaries always helps, i.e., it does not incur a similar bias-variance variance tradeoff. Indeed, this because larger m does not lead to any additional bias, K is reliable default, especially
discussed in $3.3. However, the gains quickly saturate, for 2 16 or so; we refer to Appendix for more plots and details.
Correlation between Canaries. Based on (8), this improvement in the variance can further be examined by looking at the term | f that leads to a narrower 2rd-rrder Wilson interval. The log-log plot of this term in Figure 4 (middle) is nearly parallel to the dotted 1/K line (slope 0.933, meaning that it decays roughly as 1/K (note that the log-log plot = cx is a straight line with slope a). This indicates that we get close to a 1/ VnK confidence interval as desired. Similarly, get that بم pá3 decays roughly 1/K (slope 1.05). However, the -tdder estimator offers only marginal additional improvements in the small regime (see Appendix E). Thus, the gain diminishes rapidly in the order of estimators.
Gaussian, 2, 4006, 64,
Laplace, 16, K 1024,
Laplace, 16, a 4006
0.00
Empirical lower baund E
Empincal lower baund E
Empircal lower bound
E:me-
6mm-
6m
8x gain
0.12
K
ex0
Number canaries
Number trials
Number of canaries
DP
Wilson
LDP Lst-Order Wilson
LDP
2nd-Order Wilson
LIPP 4th 4theOrder Wilson
Figure 5: Left: There is no bias Maasvaaiancce tradeoff with the number m test canaries: larger m always gives a better empirical& but the results saturate quickly. This experiment is for the Gaussian mechanism. Center Right: The proposed LiDP-based auditing procedure gives significant improvements similar to Figure 3 when auditing the Laplace mechanism with canaries sampled randomly from the unit & ball.

---

Effect of Dimension on the Bias and Variance. As the dimension d increases, the LiDP-based lower bound becomes tighter monotonically as we show in Figure (right). This is due to both the bias gain, as in (10), improving (less negative) and the variance gain improving (more positive). With increasing d, the variance of our estimate reduces because the canaries become less correlated. Guided by Eq. (8.9), we measure the relevant correlation measures j pi and liz - j3] in Figure 4 (right). Both decay approximate as 1/d (slope = -.006 and - 1.00 respectively, ignoring the outlier at d 10%). This suggests that, for Gaussian mechanisms, the corresponding XBern distribution resulting from our recipe behaves favorably as d increases.
Other Mechanisms. The proposed privacy mechanism. We audit a Laplace mechanism with canaries drawn uniformly at random over the unit & ball in Figure 4 (center and right). The results are qualitatively similar to those of the Gaussian mechanism, leading to an eight-fold improvement in the sample complexity over the baseline.
Auditing
auditing recipe is agnostic to the actual
5 Lifting Existing Canary Designs
Several prior works [e.g., 32, 41, 45, 60]. focus on designing stronger canaries to improve the lower bound on e. We provide two concrete examples of how to lift these canary designs to be compatible with our framework while inheriting their strengths. We refer to Appendix D for further details.
We impose two criteria on the distribution Peanary over canaries for auditing LiDP. First, the injected canaries are easy to detect, so that the probabilities on the left side of (4) are large and those on the right side are small. Second, a canary unlikely to change the membership of 0 E Re for an independent canary c' ~ Peanary. Existing canary designs already impose the first condition to audit DP using (1). The second condition ensures that the canaries are uncorrelated, allowing our adaptive CIs to be smaller, as we discussed in 33.3.
Peanany. if included in the training of a model 0 is
Data Poisoning via Tail Singular Vectors. ClipBKD [32] adds canaries the tail singular vector of the input data (e.g., images). This ensures that the canary is out of distribution, allowing for easy detection. We lift ClipBKD by defining the distribution Pranary as the uniform distribution over the p tail singular vectors of the input data. If is small relative to the dimension d of the data, then they are still out of distribution, and hence, easy to detect. For the second condition, the orthogonality of the singular vectors ensures the interaction between canaries is minimal, as measured empirically.
Random Gradients. The approach of [2] samples random vectors (of the right norm) canary gradients, assuming a grey-box access where we can inject gradients. Since random vectors are nearly orthogonal to any fixed vector in high dimensions, their presence is easy detect with a dot product. Similarly, any two i.i.d. canary gradients are roughly orthogonal, leading to minimal interactions.
6 Experiments
We compare the proposed LiDP auditing recipe relative to the standard one for DP training of machine learning models. Our code is available online.'
Setup. We test with two classification tasks: FMNIST [65] is 10-class grayscale image classification dataset, while Purchase- 100 is a sparse tabular dataset with 600 binary features and 100 classes [19, 53]. We train linear model and multi-layer perceptron (MLP) with 2 hidden layers using DP-SGD [1] to achieve (s, 10-1105.... 1110--5-DD DDPDP with varying values of E. The training is performed using cross-entropy for a fixed epoch budget and a batch size of 100. We refer to Appendix F for details.
Auditing. We audit the LiDP using the two types of canaries from $5: data poisoning and random gradient canaries. We vary the number K of canaries and the number of trials. We track the empirical lower bound obtained from the Wilson family of confidence intervals. We compare this with auditing DP, which coincides with auditing LiDP with K = 1 canary. We audit only the final model in all the experiments.
Sample Complexity Gain. Table shows the reduction in the sample complexity from auditing LiDP. For each canary type, auditing LiDP better 11 out of the 12 settings considered. The average improvement (i.e., the harmonic mean over the table) for data poisoning is 2.3x, while for random

---

C.I.
Data Poisoning Canary
Random Gradient Canary
Dataset Model
(Wilson)
==
== 8
2nd-Ord.
0.68
3.31
2.55
4.38
2.09
3.31
5.98
5.06
FMNIST Linear
4th-Ord.
0.42
2.68
2.29
3.76
2.66
2.70
7.75
4.19
2nd-Ord.
4.80
1.46
2.95
1.60
4.62
2.88
2.33
5.46
FMNIST / MLP
4th-Ord.
4.42
2.49
2.37
1.30
3.95
2.81
2.02
4.60
2nd-Ord.
3.14
1.06
1.41
9.28
1.41
0.71
4.30
2.84
Purchase/ / MLP
4th-Ord.
2.84
1.09
1.36
6.99
1.29
0.42
4.35
2.38
Table I: The (multiplicative) improvement in the sample complexity from auditing LiDP with K 16 canaries compared auditing DP with 1000 trials. We determine this factor by linearly imtepolaaing/exttpplaaain En: cf. Figure (left) for visual representation these numbers. For instance, an improvement of 3.31 means LiDP needs n x 1000/3.31 Rs 302 trials to reach the same empirical lower bound that DP reaches at r. = 1000.
Poswing
FMNIST-Urre Graleett
Parduse
Poboring
FNNITT-Leer Guderr
621
P Vaec Touns
2.60x
3314x
Mamber rikkc
Nambow cansee
Figure 6: Left two: LiDP-based auditing with > canaries achieves the same lower bound é on the privacy loss with fewer trials. Right two: LiDP auditing is robust to K; the prescribed K = v is a reliable default.
gradients, it is 3.0x. Since each trial full model training run, this improvement can be quite significant in practice. This improvement can also be seen visually in Figure 6 (left two).
Number of Canaries. We from Figure 6 (right two) that LiDP auditing on real data behaves similarly to Figure 3 in 84. We also observe the bias-variance tradeoff in the case of data poisoning (center right). The choice K /n is competitive with the best value of K, validating our heuristic. Overall, these results show that the insights from $4 hold even with the significantly more complicated DP mechanism involved in training models privately.
Additional Comparisons. We show in $F.4 that our LiDP auditing with generally outperforms the Bayesian auditing approach of Kanella-Béguehe et al. [69]. This also suggests an interesting future research direction: adapt Bayesian credible intervals for LiDP auditing to get the best of both worlds.
7 Conclusion
We introduce framework for auditing differentially private learning. Diverging from the standard practice of adding a single deterministic canary, we propose a new recipe of adding multiple i..d. random canaries. This is made rigorous by expanded definition of privacy that call LiDP. We provide novel higher-order confidence intervals that can automatically adapt to the level of correlation in the data. We empirically demonstrate that there is potentially significant gain in sample dependence of the confidence intervals, achieving a favorable bias-variance tradeoff.
Although any rigorous statistical auditing approach benefit from our framework. it is not yet clear how other popular approaches [c.g. 12] for measuring memorization can be improved with randomization. Bridging this gap is an important practical direction for future research. It is also worth considering how our approach can be adapted to audit the diverse definitions of privacy in machine learning [e.g. 28].
Broader Impact. Auditing private training involves a trade-off between the computational cost and the tightness of the guarantee. This may not be appropriate for all practical settings. For deployment in production, it is worth further studying approaches with minimal computational overhead [e.g. 2, 12].
10

---

Acknowledgements
We acknowledge Lang Liu for helpful discussions regarding hypothesis testing and conditional probability, Matthew Jagielski for help in debugging the experiments with data poisoning canaries, and Zeba Islam for help in simplifying proofs involving combinatorics.
References
[1] M. Abadi, A. Chu, I. J. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and L. Zhang. Deep Learning with Differential Privacy. In Proc. of the 2016 ACM SIGSAC Conf. on Computer and Communications Security (CCS' 16), pages 308-318, 2016.
[2] G. Andrew, P. Kairouz, S. Oh, A. Oprea, H. B. McMahan, and V. Suriyakumar, One-shot Empirical Privacy Estimation for Federated Learning. arXiv preprint arXiv:2302.03099 2023.
[3] Ö. Askin, T. Kutta, and H. Dette. Statistical Quantification of Differential Privacy: A Local Approach. In 2022 IEEE Symposium on Security and Privacy (SP), pages 402-421. IEEE, 2022.
[4] B. Balle, G. Barthe, M. Gaboardi, J. Hsu, and T. Sato. Hypothesis Testing Interpretations and Renyi Differential Privacy. In The 23rd International Conference on Artificial Intelligence and Statistics, volume 108, pages 2496-2506. PMLR, 2020.
[5] G. Barthe, B. Köpf, F. Olmedo, and S. Zanella Beguelin. Probabilistic Relational Reasoning for Differential Privacy. ACM SIGPLAN Notices, 47(1):97-110, 2012.
[6] G. Barthe, G. Danezis, B. Grégoire, C. Kunz, and Ganella-Beguee Verified Computational Differential Privacy with Applications to Smart Metering. In 2013 IEEE 26th Computer Security Foundations Symposium, pages 287-301. IEEE, 2013.
[7] G. Barthe, M. Gaboardi, E. J. G. Arias, J. Hsu, C. Kunz, and P.-Y. Strub. Proving differential privacy in Hoare logic. In 2014 IEEE 27th Computer Security Foundations Symposium, pages 411-424. IEEE, 2014.
[8] R. Bhaskar, A. Bhowmick, V. Goyal, S. Laxman, and A. Thakurta. Noiseless Database Privacy. In International Conference on the Theory and Application of Cryptology and Information Security, pages 215-232. Springer, 2011.
[9] B. Bichsel, S. Steffen, I. Bogunovic, and M. Vechev. Dn-Sniper: Black-Box Discovery of Differential Privacy Violations using Classifiers. In 2021 IEEE Symposium on Security and Privacy (SP), pages 391-409. IEEE, 2021.
[10] M. Bun and T. Steinke. Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds. In Theory of Cryptography Conference, pages 635-658. Springer, 2016.
[11] M. Bun, J. Ullman, and S. Vadhan. Fingerprinting Codes and the Price of Approximate Differential Privacy. SIAM Journal on Computing. 47(5):1888-199 2018.
[12) N. Carlini, C. Liu, Ó. Erlingsson, J. Kos, and D. Song. The Secret Sharer: Evaluating and Testing Unintended Memorization in Neural Networks. USENIX Security Symposium, volume 267, 2019.
[13] N. Carlini, F. Tramer, E. Wallace, M. Jagielski, A. Herbert-Voos K. Lee, A. Roberts, T. Brown, D. Song, U. Erlingsson, A. Oprea, and C. Raffel. Extracting Training Data from Large Language Models. In 30th USENIX Security Symposium (USENIX Security 2021), 2021.
[14] N. Carlini, S. Chien, M. Nasr, S. Song, A. Terzis, and F. Tramer. Membership Inference Attacks from First Principles. In IEEE Symposium on Security and Privacy (SP), pages 1519-1519, Los Alamitos, CA, USA, May 2022. IEBE Computer Society. doi: 10. 10.1100/SP42214.222000 2..02.2.....020090. htt.:///...1.///22.1111111 1109/SP449914440///// 2022221122222222222 00090.
URL https://doi. http://dd....eeeemmmerrrrrreeeep wwg/10..///.o
[15] N. Carlini, D. Ippolito, M. Jagielski, K. Lee, F. Tramer, and C. Zhang. Quantifying Memorization Across Neural Language Models. In The Eleventh International Conference on Learning Representations, 2023. URL httt::::///perrvvee..no wtt. _1c..

---

[16] Y. Chen and A. Machanavaijhala. On the privacy properties of variants on the sparse vector technique. arXiv preprint DrXiv:1508.07306. 2015.
[17] Z. Ding, Y. Wang, Wang, D. Zhang, and D. Kifer. Detecting violations of differential privacy. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, pages 475 489, 2018.
[18] K. Dixit, M. Jha, S. Raskhodnikova, and A. Thakurta. Testing Lipschitz Property over Product Distribution and its Applications to Statistical Data Privacy, In Theory of Cryptography Conference, pages 41 418-436. Springer, 2013.
[19] W. C. DMDave, Todd B. Acquire valued shoppers challenge, 2014. URL https//::// com/ http//ompptiiios//qquuuuee valued- shaeeddssopppss-cccce -hoppers-challeggee challenge.
[20] R. M. Dudley. Uniform Central Limit Theorems, volume 142. Cambridge university press, 2014.
[21] C. Dwork and G. N. Rothblum. Concentrated Differential Privacy. arXiv preprint arXiv:1603.01887 2016.
[22] C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating Noise to Sensitivity in Private Data Analysis. In Proc. of the Third Conf. on Theory of Cryptography (TCC), pages 265-284, 2006. URL http: /xxx doi.org//iiioeoooooooeoooo org/10 10. 1007 / /111111111111111
[23] C. Dwork, A. Smith, T. Steinke, J. Ullman, and S. Vadhan. Robust Traceability from Trace Amounts. 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 650-669, IEEE, 2015.
[24] M. Gaboardi, A. Hacberlen, J. Hsu, A. Narayan, and B. C. Pierce. Linear Dependent Types for Differential Privacy. In Proceedings of the 40th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, pages 357-370, 2013.
[25) A. C. Gilbert and A. McMillan. Property Testing for Differential Privacy. In 2018 56th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 249-258. IEEE, 2018
[26] C. Guo, Karrer, K. Chaudhuri, and L. van der Maaten. Bounding Training Data Recon- struction in Private (Deep) Learning. In Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 8076-8071, 17-23 Jul 2022.
[27] Y. Han, J. Jiao, and T. Weissman. Minimax estimation of divergences between discrete distributions. IEEE Journal on Selected Areas in Information Theory, 133):814-823, 2020.
[28] A. Hannun, C. Guo, and L. van der Maaten. Measuring Data Leakage in Machine-Learning Models with Fisher Information. In UAI, pages 760-770, 2021.
[29] Hayes, Mahloujifar, and B. Balle. Bounding Training Data Reconstruction in DP-SGD, 2023.
[30] N. Homer, S. Szelinger, M. Redman, D. Duggan, W. Tembe, J. Muehling, J. V. Pearson, D. A. Stephan, S. F. Nelson, and D. W. Craig. Resolving individuals contributing trace amounts of DNA to highly complex mixtures using high-density SNP genotyping microarrays. PLoS genetics, e 1000167, 2008
[31] S. L. Hyland and S. Tople. An Empirical Study on the Intrinsic Privacy of SGD. arXiv preprint arXiv:19/2.02919. 2019.
[32] M. Jagiclski, J. Ullman, and A. Oprea. Auditing differentially private machine learning: How private is private SGD? Advances in Neural Information Processing Systems, 33:22205-22216, 2020.
[33] B. Jayaraman and Evans. Evaluating Differentially Private Machine Learning Practice. In USENIX Security Symposium, pages 1895-1912. 2019.
12

---

[34] M. Johnson. fix prng key reuse in differential privacy example. https://github. com/ google/jax/pulI happpuul/3644. 2020.
[35] P. Kairouz, S. Oh, and P. Viswanath. The composition theorem for differential privacy. In International conference machine learning, pages 1376-1385. PMLR, 2015.
[36] D. Kifer and A. Machanavajhala. Pufferfish: A framework for mathematical privacy definitions. ACM Transactions Database Systems (TODS), 39(1):1-36, 2014.
[37] T. Kutta, Ô. Askin, and M. Dunsche. Lower Bounds for Rényi Differential Privacy in Black-Box Setting, arXiv preprint arXiv:2212.04779, 2022.
[38] X. Liu and S. Oh. Minimax Optimal Estimation of Approximate Differential Privacy on Neighboring Databases. In Advances in Neural Information Processing Systems, volume 32, 2019.
[39] F. Lu, J. Munoz, M. Fuchs, T. LeBlond, E. Maresky-Wilianyy E. Raff, F. Ferraro, and B. Testa. General Framework for Auditing Differentially Private Machine Learning. In NewrlPS, 2022.
[40] M. Lyu, D. Su, and N. Li. Understanding the sparse vector technique for differential privacy. arXiv preprint arXiv: 0000.600339999 2016.
[41] S. Maddock, A. Sablayrolles, and P. Stock. CANIFE: Crafting canaries for empirical privacy measurement in federated learning. In ICLR, 2023.
[42] M. Malek Esmaeili, Mironov, K. Prasad, Shilov, and F. Tramer. Antipodes of label differential privacy: Pate and alibi. Advances in Neural Information Processing Systems, 34: 6934-6945, 2021.
[43] F. D. McSherry. Privacy integrated queries: an extensible platform for seeracy-preservngg data analysis. In Proceedings of the 2009 ACM SIGMOD International Conference on Management of data, pages 19-30. ACM, 2009.
[44] I. Mironov. Rényi Differential Privacy. In 30th IEEE Computer Security Foundations Sympo- sium, CSF 2017, Santa Barbara, CA, USA, August 21-25, 2017, pages 263-275, IEEE Computer Society, 2017.
[45] M. Nasr, S. Songi, A. Thakurta, N. Papernot, and N. Carlini. Adversary Instantiation: Lower Bounds for Differentially Private Machine Learning. In 2021 IEEE Symposium on Security and Privacy (SP), pages 866-882. IEEE, 2021.
[46] M. Nasr, J. Hayes, T. Steinke, B. Balle, F. Tramèr, M. Jagielski, N. Carlini, and A. Terzis. Tight Auditing of Differentially Private Machine Learning. arXiv preprint 2rXiv22302.07956 2023.
[47] M. Park.
https://github. com http://w.woooooaaaoo////pp//oooo 482222666c6026617226622222222222
Bug-fix.
2018.
[48] N. Ponomareva, H. Hazimeh, A. Kurakin, Z. Xu, C. Denison, H. B. McMahan, S. Vassilvitskii, S. Chien, and Thakurta. How to DP-fy ML: A Practical Guide Machine Learning with Differential Privacy. arXiv Preprint, 2023.
[49] M. A. Rahman, T. Rahman, Laganière, N. Mohammed, and Y. Wang. Membership Inference Attack against Differentially Private Deep Learning Model. Trans. Data Priv., 11(1):61-79, 2018.
[50] J. Reed and B. C. Pierce. Distance makes the types grow stronger: a calculus for differential privacy. In ACM Sigplan Notices, volume 45, pages 157-168. ACM, 2010.
[51] I. Roy, S. T. Setty, A. Kilzer, V. Shmatikov, and E. Witchel. Airavat: Security and privacy for MapReduce. In NSDI, volume 10, pages 297-312, 2010.
[52] S. Sankararaman, G. Obozinski, M. I. Jordan, and E. Halperin. Genomic privacy and limits of individual detection in pool. Nature genetics, 41(9):965-967, 2009.
13

---

[53] R. Shokri, M. Stronati, C. Song. and V. Shmatikov. Membership inference attacks against machine learning models, In 2017 IEEE symposium on security and privacy (SP). pages 3-18. IEEE, 2017.
[54] S. Song, K. Chaudhuri, and A. D. Sarwate. Stochastic gradient descent with differentially private updates. In 2013 IEEE Global Conference on Signal and Information Processing, pages 245-248, IEEE, 2013.
[55] S. Song, Y. Wang, and K. Chaudhuri. Pufferfish privacy mechanisms for correlated data. In Proceedings of the 2017 ACM International Conference on Management of Data, pages 1291-1306, 2017.
[56] Steinke, M. Nasr, and M. Jagielski. Privacy auditing with one (1) training run. arXiv preprint arXiv:2305.0888 2023.
[57] T. Stevens, I. C. Ngong, D. Darais, C. Hirsch, D. Slater, and J. P. Near. Backpropagation Clipping for Deep Learning with Differential Privacy. arXiv preprint arXiv:2202.050003 2022.
[58] F. Tramer. Tensorflow privacy issue #153: Incorrect comparison between privacy amplifica- tion by iteration and DP-SGD. https : //g/tggtt.././//////////. cotp://ommorrloooooiavarrsssssee 2020.
[59] F. Tramèr, R. Shokri, A. San Joaquin, H. Le, M. Jagielski, S. Hong, and N. Carlini. Truth Serum: Poisoning Machine Learning Models Reveal Their Secrets. In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, CCS '22, page 2779-2792, New York. NY. USA. 2022. Association for Computing Machinery. ISBN 978 1550345505 doi: 044453354660633555555
URL https: /doi. org/10. 10..0....45555 1145/3548606 3560554.
[60] F. Tramer, A. Terzis, T. Steinke, S. Song, M. Jagielski, and N. Carlini. Debugging differential privacy: A case study for privacy auditing. arXiv preprint arXiv:2202. /2219, 2022.
[61] A. Triasteyn and B. Faltings. Bayesian Differential Privacy for Machine Learning. In Interna- tional Conference on Machine Learnin, pages 9583-9592. PMLR, 2020.
[62] M. C. Tschantz, D. Kaynar, and A. Datta. Formal verification of differential privacy for interactive systems. Electronic Notes in Theoretical Computer Science, 276:61-79, 2011.
[63] S. Vadhan. The complexity of differential privacy. In Tutorials on the Foundations of Cryptog- raphy, pages 347-450. Springer, 2017.
[64] G. Valiant and Valiant. Estimating the unseen: improved estimators for entropy and other properties. Journal of the ACM (JACM), 64(6):1-41, 2017.
[65] H. Xiao, K. Rasul, and R. Vollgraf. Fashion-MNIST: Novel Image Dataset for Benchmarking Machine Learning Algorithms. arXiv Preprint, 2017.
[66] B. Yang, I. Sato, and H. Nakagawa. Bayesian Differential Privacy on Correlated Data. In Proceedings of the 2015 ACM SIGMOD international conference on Management of Data, pages 747-762, 2015.
[67] J. Ye, A. Maddi, S. K. Murakonda, V. Bindschaedler, and R. Shokri. Enhanced Membership Inference Attacks against Machine Learning Models. arXiv preprint arXiv:2111.0 111.0997,, 2021.
(68] Yeom, Giacomelli, M. Fredrikson, and S. Jha. Privacy Risk Machine Learning: Analyzing the Connection to Overfitting. In 2018 IEEE 31st computer security foundations, symposium (CSF), pages 268 282. IEEE, 2018
[69] S. Henella-Béguelin.. L. Wutschitz, S. Tople, A. Salem, V. Rühle, A. Paverd, M. Naseri, and B. Köpf. Bayesian Estimation of Differential Privacy. arXiv preprint 22Xiv:2206.05 2022.
14

---

Appendix
Table of Contents
A Related Work
16
A.1 Auditing Private Machine Learning with Strong Canaries
16
Improving Statistical Trade-offs in Auditing
A.3 Connections Other Notions of Differential Privacy
B Properties of Lifted DP and Further Details
17
B.1 Equivalence Between DP and LiDP
17
B.2 Auditing LiDP with Different Notions of Neighborhood
18
Confidence Intervals for Exchangeable Bernoulli Means
18
Non-Asymptotic Confidence Intervals
C.2 Asymptotic Confidence Intervals
23
C33 Scaling of Higher-
Higher-Order Order Bemstein Bounds (Proposition
25
D Canary Design for Lifted DP: Details
25
D.1 Data Poisoning Random Gradients
26
D.2
27
E
Simulations with the Gaussian Mechanism: Details More Results
27
E.1
Experiment Setup
27
E.2
Additional Experimental Results
30
F
Experiments: Details and More Results
32
F.1
Training Details: Datasets, Models
32
F2 DP and Auditing Setup
33
Miscellaneous Details
33
F4
Additional Experimental Results
33
15

---

A Related Work
Prior to [17], privacy auditing required some access to the description of the mechanism. [5- 24, 43,500 50, 51, 62] provide platforms with specific set of functions to be used to implement the mechanism, where the end-to-end privacy of the source code can be automatically verified. Closest to our setting is the work of [18], where statistical testing was first proposed for privacy auditing, given access to an oracle that returns the exact probability measure of the mechanism. However, the guarantee is only for relaxed notion of DP from [8] and the run-time depends super-linearly on the size of the output domain.
The pioneering work of [17] was the first to propose practical methods to audit privacy claims given a black-box access to a mechanism. The focus was on simple queries that do not involve any training of models. This is motivated by [16, 40], where even simple mechanisms falsely reported privacy guarantees. For such mechanisms, sampling a large number, say 500, 000 in [17], of outputs is computationally easy, and no effort was made in [17] to improve the statistical trade-off. However, for private learning algorithms, training such a large number of models is computationally prohibitive. The main focus of our framework is improve this statistical trade-off for auditing privacy. We first survey recent breakthroughs in designing stronger canaries, which is orthogonal to our main focus.
A.1 Auditing Private Machine Learning with Strong Canaries
Recent breakthroughs in auditing are accelerated by advances in privacy attacks, in particular member- ship inference. An attacker performing membership inference would like to determine if a particular
data sample was part of the training set. Early work on membership inference [11, 23, 30, 52] considered algorithms for statistical methods, and more recent work demonstrates black-box attacks on ML algorithms [14, 33, 53, 67, 68]. [33] compares different notions of privacy by measuring privacy empirically for the composition of differential privacy [35], concentrated differential privacy [10, 21J, and Rényi differential privacy [44]. This is motivated by [49], which compares different DP mechanisms by measuring the success rates of membership inference attacks. [31] attempts to measure the intrinsic privacy of stochastic gradient descent (without additional noise as in DP-SGD) using canary designs from membership inference attacks. Membership inference attacks have been shown to have higher success when the adversary can poison the training dataset [59].
A more devastating privacy attack is the extraction or reconstruction of the training data, which is particularly relevant for generative models such as large language models (LLMs). Several papers showed that LLMs tend to memorize their training data [13, 15]. allowing an adversary to prompt the generative models and extract samples of the training set. The connection between the ability of an attacker to perform training data reconstruction and DP guarantees has been shown in recent work [26, 29].
When performing privacy auditing, a stronger canary design increases the success of the adversary in the distinguishing test and improves the empirical privacy bounds. The resulting hypothesis test can tolerate larger confidence intervals and requires less number of samples. Recent advances in privacy auditing have focused on designing such stronger canaries. [32] designs data poisoning canaries, in the direction of the lowest variance of the training data. This makes the canary out of distribution, making it easier to detect. [45] proposes attack surfaces of varying capabilities. For example, gradient attack canary returns gradient of choice when accessed by DP-SGD. It is shown that, with more powerful attacks, the canaries become stronger and the lower bounds become higher. [60] proposes using an example from the baseline training dataset, after changing the label, and introduces a scarch procedure to find a strong canary. More recently. [46] proposes a significantly improved auditing scheme for DP-SGD under white-box access model where (i) the auditor knows that the underlying mechanism is DP-SGD with a spherical Gaussian noise with unknown variance, and (ti) all intermediate models are revealed. Since each coordinate of the model update provides an independent sample from the same Gaussian distribution, sample complexity is dramatically improved. [41] proposes CANIFE, a novel canary design method that finds a strong data poisoning canary adaptively under the federated learning scenario.
Prior work in this space shows that privacy auditing can be performed via privacy attacks, such as membership inference or reconstruction, and strong canary design results in better empirical privacy bounds. We emphasize that our aim is not to innovate on optimizing canary design for performing
16

---

privacy auditing. Instead, our framework can seamlessly adopt recently designed canaries and inherit their strengths as demonstrated in 85 and $6.
A.2
Improving Statistical Trade-offs in Auditing
Eq. (2) points to two orthogonal directions that can potentially improve the sample dependence: designing stronger canaries and improving the sample dependence of the confidence intervals. The former was addressed in the previous section. There is relatively less work in improving the statistical dependence, which our framework focuses on.
Given a pair of neighboring datasets, (Do, D1). and for query with discrete output in a finite space, the statistical trade-off of estimating privacy parameters was studied in [25] where plug-in estimator is shown to achieve error of ( /n), where d is the size of the discrete output space. [38] proposes sub-linear sample complexity algorithm that achieves an error scaling as / /de=/ / log n, based on polynomial approximation of carefully chosen degree to optimally trade-off bias and variance motivated by [27, 64]. Similarly, [37] provides lower bound for auditing Rényi differential privacy. [9] trains classifier for the binary hypothesis test and uses the classifier to design rejection sets. [3] proposes local search to find the rejection set efficiently. More recently, [69] proposes numerical integration over larger space of false positive rate and true positive rate to achieve better sample complexity of the confidence region in the roo-dimensionll space. Our framework can be potentially applied to this confidence region scenario, which is an important future research direction.
A.3
Connections to Other Notions of Differential Privacy
Similar to Lifted DP, a line of prior works [36, 55, 61, 66) generalizes DP to include a distributional assumption over the dataset. However, unlike Lifted DP, they are motivated by the observation that DP is not sufficient for preserving privacy when the samples are highly correlated. For example, upon releasing the number of people infected with highly contagious flu within a tight-knit community, the usual Laplace mechanism (with sensitivity one) is not sufficient to conceal the likelihood of one member getting infected when the private count is significantly high. One could apply group differential privacy to hide the contagion of the entire population, but this will suffer from excessive noise. Ideally, want to add noise proportional to the expected size of the infection. Pufferfish privacy, introduced in [36], achieves this with a generalization of DP that takes into account prior knowledge of class of potential distributions over the dataset. A special case of c-Pufferfish with a specific choice of parameters recovers special case of our Lifted DP in Eq. (3) with 5 = 0 [36, Section 3.2], where a special case of Theorem has been proven for pure DP [36, Theorem 1. However, we want to emphasize that our Lifted DP is motivated by completely different problem of auditing differential privacy and is critical breaking the barriers in the sample complexity.
B Properties of Lifted DP and Further Details
B.1 Equivalence Between DP and LiDP
In contrast the usual (c, 5DDP in Eq. (1), the probability in LiDP over both the internal randomness of the algorithm A and the distribution P over the triplet (Do, D2. R). Since we require that the definition holds only for lifted distributions P that are independent of the algorithm A. is easy to show its equivalence to the usual notion of (s, D)-DP.
Theorem 3. randomized algorithm
(e iff A is (E.8)-DP.
Proof. Suppose A is (c, 5)-LiDP. Fix a pair of neighboring datasets Do, Dj and an outcome R C R. n as the point mass on (Do, D1, R), i.e., Define D,,
d' dPD D', R') 1 1D', Do. D' D1, R' R).
so that PP P.PPPo Do Dr R (A(Da) E R) = (P(((Do) E R)) and similarly for D₁. Then, applying the definition of (s, 8) w.r.t. the distribution PD..D..R gives
(A((())) R) S e of (A(A(D)) E R) 6
Since this holds for any neighboring datasets Do, D2 and outcome set R. we get that is (s, dDDP.
17

---

Conversely, suppose that A is (E, 6)-DP. For any distribution P over pairs of neighboring datasets Do: D and outcome set R, we have by integrating the DP definition
/ (((A(D)) R)d,
/ |P(A(D)) e R)dP(Do, + (11)
Next, we use the law of iterated expectation to get
PAP (A(Do) E R))= - EAP [T(ADD)) E R)]
= RI [B^ (I(A(Do) E R) Do. RJ]
= EA [T(A(Do) E R) Do = Do, R = R] dP D1, R)
EA [I(A(Do) R)) dP D1,
PA(A(DO) E R) dP(Do. LI, R),
where (x) followed from the independence of A and P. Plugging this and the analogous expression for (((( E R) into (11) gives that A is (e, 8)-LiDP.
B.2 Auditing LiDP with Different Notions of Neighborhood
We describe how to modify the recipe of 33 for other notions of neighborhoods of datasets. The notion of the neighborhood in Definition is also known as the "add-or-remove" neighborhood.
Replace-one Neighborhood. Two datasets D, D' Z" are considered neighboring if |D] |D' and DD \ D'I = D' DJ 1. Roughly speaking, this leads to privacy guarantees that are roughly twice as strong as the add-or-remove notion of the neighborhood in Definition 1, as the worst-case sensitivity of the operation is doubled. We refer to [48, 63] for more details. Just like Definition 1, Definition 2 can also adapted to this notion of neighborhood.
Auditing LiDP with Replace-one Neighborhood. The recipe of 53.2 can be slightly modified for this notion of neighborhood. The main difference that the null hypothesis must now K canaries as well, with one fresh canary.
The alternative hypothesis is the same same-wa we train model on randomized training dataset D1 DU (cI...., Cк } augmented with K random canaries drawn i.i.d from P Peanary. Under the j"h null hypoth- esis for each [K]. construct coupled dataset Do., D (Ci...... C.-1,.. cj. Cj+1,-... Cx }. where d' is fresh canary drawn i.i.d. from Peanury- This coupling ensures that (Do.j. D2) are neighboring with probability one. We restrict the rejection region R, to now depend only on Gj and not in the index j. e.g., we test for the present of c..²
Note the symmetry of the setup. Testing for the presence of cj in Do.5 is exactly identical to testing for the presence of c/j in D1- Thus, we can again rewrite the LiDP condition as
1 K Σ P(A(D))) RA) < K
P(A(D,) E R2) +
(12)
M
Note the subtle difference between (4) and (12): both sides depend only on A(D,) and we have completely eliminated the need to train models on K canaries.
From here on, the rest of the recipe is identical to $3 and Algorithm 1; we construct XBern confidence intervals for both sides of (12) and get a lower bound
C Confidence Intervals for Exchangeable Bernoulli Means
We give rigorous definition of the multivariate Exchangeable Bernoulli (XBern) distributions and derive their confidence intervals. We also give proof of the correctness of the confidence intervals.
Note that the test could have depended cs well, but we do not need here.
18

---

Definition 5 (XBem Distributions). A random vector (a1..... σk) E {0,1}* is said to be dis- tributed X (HI....,KK if:
El....y øK is exchangeable, i.e., the vector (01, σx) is identical in distribution to (x1)) -.... (K)) for any permutation [K] + [K], and,
for each L = 1,.... K, we have E[me]] = pe, where
my (5) <iC-<<EE((K]
Σ
Th By
(13)
We note that the XBern distribution is fully determined by its K moments M1..., Mk. For K = 1, XBemn (M1) Bermoulli(/41 just the Bernoulli distribution.
The moments my satisfy a computationally efficient recurrence. Proposition 6. Let x XBemn
We have the following for all 1 5 < Km,;
Kmmj
[Km1-9
my
and
m6+1
mi
(K--))
(14)
Computing the first l moments thus be done in O(K + E) time rather than O(K*) by naively computing the sum in (13).
Proof of Proposition 6. We show that this holds for any fixed vector (21...., xx) {0, 1] K and their corresponding moments my,.... mn as defined in (13). Define the sums 81 = Σ 2==1 = K Km, and
K
Σ JIcunee
11. Ize
(15)
We can compute sg by a counting argument: each term the sum is non-zero only all of T. Tie are non-zero. The number of non-zero terms is equal to number of ways of selecting { items from a total of Σ By 81 items, i.e.,
K Σソ=
Kmg
(16)
Combining Equations (15) and (16) completes the proof.
Notation. this section, we are interested in giving confidence intervals on the mean bi X (NI,...,,KR) random variable from i.i.d. observations:
(n) XBemn (pe
We will define the confidence intervals using the empirical mean
K
i
m (5)
where m
(1)
1
Σ
(3)
K
j=1
as well as the higher-order moments for E [K].
where m (8)
Σ
(1) 1
........
f
(K)
C.1 Non-Asymptotic Confidence Intervals
We start by giving non-asymptotic confidence intervals for the XBern distributions based on the Bemnstein bound, recalled below [c.g. 20, Thm. 1.3.2].
19

---

Algorithm 2 First-Order Bernstein Intervals
Input:
Random vectors x11), ..... x()) XBernk ( .k) with unknown parameters, failure probability 3 E (0, 1).
Output: Confidence intervals 1 11) such that P(u1 < ) S and P( > p1) S B.
1: Set 1 as the unique solution of x E [0, [61] such that
V
((2
P1 - r 1----Ve
x(1 2)
log
3n
if it exists, else set 2 O.
2: Set 11 the unique solution of j 1] such that
((2 log
x fa
x(1 - x) = 3n
log
3
if it exists, else 1 1.
3: return i
Lemma' (Bernstein incquality). Let $1...., Tn be independent random variables with E[æ, Var(æ;; S o². and [ S. b almost surely. Let μr (1/n) Ei=1 T₁. For any t 0, have
nt22
PP > 1) S exp
20 + 2bt/3
Equivalently, we have with probability at least B that
20
b
20
1
p1 S
log
log"
+
log
<
log
+
log
9n
B
3n
B
3
3n
3
The last simplification is obtained by using Va + S Vā + vb for scalars a, b 0.
C.1.1 First-Order Bernstein Intervals
The first-order Bernstein interval only depends the empirical mean μa and is given in Algorithm 2.
Proposition Consider Algorithm 2 with inputs ii.dd samples a1 ..... x!n) itd
XBerng (HI,... PK) for some K 2 1. Then, its outputs 14 satisfy P(11 S m 2 and P(1 TT 2 3.
Proof: Applying Bernstein's inequality to m (1/K) Σx= F. we have with probability 1 -B that
2arr(m1)
1
2 3n
2u1 (1 - p1) log
1
2
11 141 S
log
log
log
n
3n
where we used that Var(m.) < (1 - m1) since E [0. 1] a.s. We see from Figure 2 that l that largest value of jn that satisfies the above inequality, showing that is an upper confidence bound. Similarly, get that μt is valid lower confidence bound.
20

---

Algorithm 3 Second-Order Bernstein Intervals
Input:
Random vectors x
(()) XBernk ( with unknown parameters, failure
probability 3 E (0, 1). Output: Confidence intervals [ (4 such that P(u1 < 1 S and P(11 > 11) S 5.
1: For each E [n]. set m (1/K)
ش zj and m2 mi (8)
Kmm -1
K-1
2: Set P (1/n) m
(6) for 2, 3: Set Bt the unique solution of [ 1 such that
2
2 3
2
i42
V
log
s01
- x)
log
n
3n
if it exists, else set 142 =1 1.
4: Set μ, as the unique solution of æ E
[0, jدd] such that
P1 -
2
log 5
2
(
x
x2
K
P2
2
log
2
K
K
3n
3
if it exists, else set 14, 0.
5: Set 1 the unique solution of Jū,, 1] such that
2 x
K
2
2
x
A -
log
x2
+
log
3
K
K
3n
3
if it exists, else 1 = 1.
6: return 14 P.
C.1.2 Second-Order Bernstein Intervals
The second-order Bernstein interval only depends the first two empirical moments μ4i and μ42 is given in Algorithm 3. The algorithm is based on the calculation
Var(m:)
E mm
1
Σ
K2
K
In
(17)
$1 i<<kE](K
K
12
K
where we used x² = æy since an indicator.
Proposition Consider Algorithm 3 with inputs i.d.d
samples (1))
(n) itd
XBerng (HI,.... ........ .K.) for some K 2 2. Then, its outputs Hy 14 satisfy PP[m 2 14 2 1
and (pm E T1) 2 1 - 3 and Pig S in S pT) <
38
2
Proof. Algorithm 3 computes the correct 2nd moment m due to Proposition 6. Applying Bern-
stein's 's inequality m2, get P(u2 & (2)) 2 1 B/2 (see also the proof of Proposition 8). Next, from Bernstein's 's inequality applied to mi, we leverage (17) to say that with probability at least 1 8/2, have
2 log
P1 K
K-1
#1
11 S
log
12
3n
7
K
Together with the result on P2g we have with probability at least
3 that
2
2
2
2
K
p1 <
log
+
log
1¹ +
112
3n
B
3
K
K
21

---

Algorithm 4 Sourth-Orden Bernstein Intervals
Input:
Random vectors x11),
(()) XBernk ( with unknown parameters, failure
probability 3 E (0, 1).
Output: Confidence intervals [ 14) such that P(u1 < / S and P(11 > (11) S 5.
1: For each i [r], set set m (4) (1/K)
وز zj (4) (6) for 1,2,3,4.
and for 8 = 1, 2, 3: m = (1) Km, -
R K-t
2: Set P (1/n) Ei= my
3: For & 3, 4, set fgg as the unique solution of x E [ 1] such that
((2
101 log 4 x(1 - x)
2 3n
I x- i -
log
3
if it exists, else set 14g =1 1. 4: Set Pt as the unique solution, if it exists, of æ E ligg 1] such that
V(2
12200 log 4
2
4
of (I, (3.
log
3n
where (.) is as defined in (18). Else set Tī2 = 1. 5: Set M, as the unique solution of x E [0, ji)] such that
v (( log
4 3
K
A1 - x -
x
12
log
k
K
3n
3
if it exists, else set 2 = 0.
6: Set n, the unique solution of [ 1] such that
fr v
(" log 3 k
4 x - x²
K-1
x
+
P2
log
K
3n
3
if it exists, else 1 = 1. 7: return P..
We can verify that the output }i, the largest value of 141 S that satisfies the above inequality. Similarly, 14, is obtained as lower Bernstein bound m, with probability at least 1 B. By the union bound, Ht S #1 S ii holds with probability least 1-3//2, since we have three invocations of Bernstein's 's inequality, each with failure probability 3/2.
C.1.3 Fourth-Order Bernstein Intervals
The fourth-orde Bernstein interval depends on the first four empirical moments μ1: ......, /44 It is given Algorithm 4. The derivation of the interval based on the calculation
Var(ma) = E/ma) 12
2/12
4(K - 2)
(K - (K-2)(K- -3)
K(K 1)
112
2
K(K 1) 113 +
K(K - 114
(18)
2 (1 - (12)
4(K 2)
(K - -2)(K 3)
+
K(K - 1) (13 -22) +
K(K-1 (Mu 12)
K(K -1)
=: =:0. M3,, M3, M4))
Proposition 10. Consider Algorithm 4 with inputs n i.i.d.
samples (1 "1),,..,!!") (nn) itd
XBerng (.i,..., PK) for some K 2 4. Then, its outputs H, Pi satisfy PP(m 2 n,) 2 3
and PP[1 I 11) 2 1 3 and P(u, < #1 I 41) p1) 51 53
22

---

4 Algorithm 5 First-Order Wilson Intervals
Input:
Random vectors x(1), ................................ (()) XBernk (. pk) with unknown parameters, failure
probability 3 E (0, 1).
Output: Asymptotic confidence intervals [, 1i) such that 1im P(4
1 S B and
-im P(11 > [1)= I B.
1: Set 14 p1 the roots of the quadratic in
(n Zz) x² (2mja + =z3) x mnp = 0.
2: return P.1
Algorithm 6 Second-Orrde Wilson Intervals
Input:
Random vectors x;1),
(x))) ,...,,"", XBern "Vi,....,Kx" with unknown parameters, failure
probability 3 (0, 1).
Output: Asymptotic confidence intervals 1,,, Fil such that lim P(11
I 3 and
lim. P( > 1T) B.
1: For each E [n]]. set m = (1/K) (1/K) zj and m2 (t) = mi
(mm()))
K-1
(6) 2: Set ji (1/n) E1/n) m for 1,
3: Let P2 be the larger root of the quadratic in .::
(n + 2//2) x²²
(2m + 12/22) + npp = 0.
4: Set ,, < 11 the roots of the quadratic in
2
K 1 K
(n - 2 x²
22 +
+ mpt
22/2212 =0.
K
5: return , F1.
Proof. Algorithm 4 computes the correct moments m, for < 4 due Proposition 6. Applying Bernstein's 's inequality to my and m4, we get Pi S F 2 1 - 3/4 /4 for l = 3, 4 (see also the proof of Proposition 8).
(5)
Next, from Bernstein's 's inequality applied to m2, we have with probability at least - 3/4 that
2
4
20 (12, 13, (4a) log
4
P2 j
log
3n
n
Combining this with the results on Pg. B4 with the union bound, we get with probability at least 1 -/// that
4
20
(12 P3. IAA) log 3
#12
i12
log
n
Finally, plugging this into Bernstein bound on my using the variance calculation from (17) (also see the proof of Proposition 9) completes the proof.
C.2 Asymptotic Confidence Intervals
We derive asymptotic versions of the Algorithms 2 to using the Wilson confidence interval.
The Wilson confidence interval is a tightening of the constants for the Bernstein confidence interval
2 1og(1/8)
2
1
Zz V
ia -
Var(m,) + log
to
P1
Var(m1),
3n
B
where ZB is the (1 - (1-33)-qaae)) qu-nntee of the standard Gaussian. Essentially, this completely eliminates the 1/n term, while the coefficient of the 1/vn term improves from /2log(1/B) to Z, Figure 2.
23

---

Algorithm/ 7 -oddr Wilson Intervals
Input:
Random vectors x(1), ,...,,"" (()) XBern s with unknown parameters, failure
probability 3 E (0, 1).
Output: Asymptotic confidence intervals [ 11) such that 1im P(11
S
f
and
lim,-+20 F(11 F1) S B.
For each i [n]] set m (4) i (L/K) j=1
(1/K) 2j and for l 1, m m
(3)
(2)
Km, -1
K-t
2: Set cr (1/n) Ei=1 m
(i) for l 2,
3: For l = 3, let pa be the larger root the quadratic in x::
(n + 23/4) x²
(2mjae + 22ya)) x + njt = 0.
4: Let Ba be the larger root of the quadratic in a::
27 2/K -3) 3)
22//4
n K(K -
x.a 2mf +
x. x mip x
c./3/4 0,
K(K -1)
(K - ())-))(K 3)
4(K 2) K(K 1) RBg
where c=
[Tas [ogz) +
K(K 1)
5: Set 1 < pi as the roots of the quadratic in æ:
22/1 (2nur
-
-K-1
(n 22/10)2² x²
23// Fh2 -0
K
6: return 1 1
The Wilson approximation holds under the assumption that (M) p/)/ / Var (m1)/ & 1), and using Gaussian confidence interval. This can be formalized by the central limit theorem.
Lemma 11 (Lindeberg- -évv Central Limit Theorem). Consider sequence of independent random variables (2),, (2) .... with finite moments (0y < and B(y u)² o² < for each i. Then, the empirical mean p = =(1/n) Ei=1 (() based on n samples satisfies
( (n)
lim IP 70-000
o/vn >1) PENA((O,1) (E>1) x)
for all t E IR. Consequently, we have,
lim P (1- p1 (m) n-
(n) .ZZz///n 21-B and lim P (A - oZ3/Vn) 21-B. n-030
(19)
The finite moment requirement above is satisfied in our case because all our random variables are bounded between () and 1. The asymptotic confidence interval implied by (19) is known as the Wilson confidence interval. states that
oZz/2 /n
(1) 1
w.p. - 3 as 72 + co.
We give the Wilson-variante of Algorithms to 4 respectively in Algorithms 5 to 7. Apart from the fact that the Wilson intervals are tighter, we can also solve the equations associated with the Wilson intervals in closed form as they are simply quadratic equations (i.e., without the need for numerical root-finding. The following proposition shows their correctness.
Proposition 12. Consider n i...d. samples (1) ,..., (n))
(t),...,a((n) itd. XBern (Mzy..., pK) as inputs
to Algorithmss 5 to 7. Then, their outputs μt Th satisfy lima-ree P( I p.) 2 1 - 3 and
lim P(u 2 p1) 2 1- B and limm-zoo P( f1 ( < CB if

---

(a) K 2 1 and C = for Algorithm 5,
(b) K 2 2 and C = for Algorithm 6, and
(c) 2 4 and = 5/4 for Algorithm 7.
We omit the proof as it is identical to those of Propositions 8 to 10 except that it uses the Wilson interval from Lemma rather than the Bernstein interval.
C.3 Scaling of Higher-Order Bernstein Bounds (Proposition 4)
We now re-state and prove Proposition 4.
Proposition 4. For any positive integer that is a power of two and K (n(t-1)/E suppose we have samples from K K-dimensional XBem distribution with parameters (H1,.... MK). If all 4tth -oddrr correlations scale as 1/K, i.e., |P28 - p& = (,, all S l and E is power of two, then the tth -onder Bernstein bound is Inn fai = 0(1 O(1/ (221222))
Proof. We are given samples from XBem distribution (pI....;KK) PK),, where μe == E[m,] with
{0, 1] with parameters
E
my = K(K 1) (K-L+)
Eje
By exchangeability, it also holds that μ B|x wz]. Assuming confidence level - 3 < 1 and
K (6-1// the 1st-order Bernstein bound gives
I م1l
o
o
of
(20)
n
where of = Var(ma). Expanding of. it is easy to show that it is dominated by the 2éth-order correlation 1122 ug1:
of = o = 1 -2
o
A2 -
+
Note that our Bernstein confidence interval does not use the fact that the higher-order correlations small. We only use that assumption to bound the resulting size of the confidence interval in the analysis. Applying the assumption that all the higher order correlations are bounded by 1/K, i.c.,
122 1 = ( K), we get that já2e p O(1/K K + o Applying this recursively into (20), we get that
|e - Ail = o (VV
1/8 (2(2 1)/(2E)
nK
for any that is power of two. For ghdordee Bernstein bound, we only moment estimates up to l and bound of 1. The choice of K (f-1)// gives the desired bound: |u1 أ
D Canary Design for Lifted DP: Details
The canary design employed in the auditing of the usual (c, 6)-DP can be easily extended to create distributions over canaries audit LiDP. We give some examples for common classes of canaries.
Setup. We assume a supervised learning setting with training dataset D {(x,, y:)) and held-out dataset Dval = {(x,, v:) ) N41 minimize the average loss
N of pairs of input x; E X' and output E y. We then aim
N
F(0) = N
Σ L))
(21)
25

---

where L(z, 8) is the loss incurred by model f on input- pair 2 = (a, y).
In the presence of canaries -1,-.-- Cks We instead aim minimize the objective
Cks
N
b
Feanary (0; C1 ck) = N
Σ
L((
+
Σ
Leanary (cg. 0)
(22)
where Leanary (c, 0) is the loss function for canary this may may not coincide with the usual loss L.
Goals of Auditing DP. The usual practice is to set Do = Dimin and Di Do U {c} and R = Re for a canary c. Recall from the definition of (e, 6)-DP in (I), we have
P(A(Di) Ro) ) P(A(Do) E Re)
ž sup log cEC
for some class C of canaries. The goal then is to find canaries e that approximate the sup over C. Since this goal is hard, usually resorts to finding canaries whose effect can be "easy to detect" in some sense.
Goals of Auditing LiDP. Let P canaary denote probability distribution over set C of allowed canaries.
We sample K canaries C1. ....... CK Peanary and set
Do Duman {c1,... CK-1). D1 Durain cck, R Rex
From the definition of (s, d)-LiDP in (3), we have
(P(A(DI) R) R)- P(A(Do) R)
2 sup log Paaaary
for some class of canaries. The goal then approximate the distribution Peumary for each choice of the canary set C. Since this is hard, we will attempt to define distribution over canaries that are easy to detect (similar to the case of auditing DP). Following the discussion in $3.3, auditing LiDP benefits the most when the canaries are uncorrelated. To this end, we will also impose the restriction that a canary e ~ Paamary, if included the training of a model 0, unlikely to change the membership of 0 E Re for an i.i.d. canary c' ~ Peaanry that is independent of c.
We consider two choices of the canary set C (as well as the outcome set Rg and the loss Leanury): data poisoning, and random gradients.
D.1 Data Poisoning
We describe the data poisoning approach known as ClipBKD [32] that is based using the tail singular vectors of the input data matrix and its extension to auditing LiDP.
Let X (IT; ; E Nxd denote the matrix with the datapoints E Idd rows. Let X = [. " be the singular value decomposition of X with σ1 S 02 S ... be the singular values arranged in ascending order. Let Y denote the set of allowed labels.
For this section, take the set of allowed canaries of the right singular vector of X scaled by a given factor a >> 0 together with any possible target from V. We take Leanary (c, () L(c, 0) be the usual loss function, and the output set R. be the loss-thresholded set
{arr1 0T22 ..., OrUming (N,) } y as the set
Re ( 1c
(23)
for some threshold т.
Auditing DP. The ClipBKD approach [32] uses canary with input a11, the singular vector corre- sponding to the smallest singular value, scaled by parameter O. The label is taken as y (av1). where
y (x) = arg max L((x, v), 05)
yEy
the target that has the highest loss on input x under the empirical risk minimizer Oj
arg milleeR F(0). Since unique 0 is not guaranteed for deep nets nor find it exactly.
26

---

Lower Confidence Interval
Upper Confidence Interval
Width Confidence Interval
Width Confidence Interval
10
10-3
Clorper-Pearson Jeffreys
10-3
10-1
Wilson
10
10a
10"
10
10P
10r
10
100
Sample size n
Sample size m
Figure Comparing the Binomial proportion confidence intervals, sample m ~ Binomial(n.. p) for p= = 0.1 and n varying and find the 95% confidence interval -P..P.... We plot the widths P. and P..
versus We find that all confidence intervals are nearly equivalent once n is larger than z 1/ min 1 p)
we train 100 models with different random seeds and pick the class y that yields the highest average loss over these runs.
Auditing LiDP. We extend ClipBKD define a probability distribution given number p of canaries. We take
Peanary Uniform ((cfoormmmee.......... (p)) with Cj = (are, v² (awv))
(24)
i... Peanary is the uniform distribution over the p singular vectors corresponding to the smallest singular values.
D.2 Random Gradients
The update poisoning approach of [2] relies of supplying gradients Uniform( (0, that uniform on the Euclidean ball of a given radius r. This is achieved by setting the loss of the canary as
Leanary (c, 0) = (c. 0), so that Ve (c, 0) = C,
the desired vector c.
The set Re is a threshold the dot product
R 10 R ST}
(25)
for given threshold This set is analogous to the loss-based thresholding of (23) in that both can be written as Leanary (c, 0) S T.
Auditing DP and LiDP. The random gradient approach of [2] relies on defining distribution P Peumary Uniform By (0, r)) over canaries. It can be used directly audit LiDP.
E Simulations with the Gaussian Mechanism: Details and More Results
Here, we give the full details and additional results of auditing the Gaussian mechanism with synthetic data in $4.
E.1 Experiment Setup
Fix dimension d and failure probability / E (0, 1). Suppose we have a randomized algorithm A that returns a noisy sum its inputs with the goal of simulating the Gaussian mechanism. Concretely, the input space Z = {z E IRd || < is the unit ball in Rd Given a finite set D Z", we sample a vector & NO Ia of given variance o² and return
A(D) + Σ z
27

---

z-m Lit Kmymh 00
X K506 d- 10
A 252, d-
Li, & UQL de 10
Emerrca lowe soued
Emerre lour tourd
Erorra Sour tourd
Narber miken vii
macc & Gl d= 10
Nambe macn
Numter
R 351, de 10
50 N 1001 de
Empe al lover bourdd
Empee el love hourd
Empee of love Iosand
Naribar of tida
Karber of b
Namber uidan R 353, d= to
Nanzer inda <- 40, 100
10
Enorecl lover pound
Ero eecl lover sourd
Enorccal lower sound
Eroreaal
Naribar of tridl
Narberr of i
Namber tndan
Numizrr tnila
Empancal over stand
over sound
Narber of bids
Namber of bials
Numberr bial
Namber tiil
Wiloon
LOP
In-Drerr Wienn
UOP à Ord- Wilson
-
LGe Ath-Order Welse
Figure 8: Effect of the number n of trials on the empirical lower bound from auditing the Gaussian mechanism for DP and LiDP. The shaded are denotes the standard error over 25 random seeds.
To isolate the effect of the canaries, set original dataset D {Oz} as singleton with the vector of zeros in IRd, Since we are in the blackbox setting, we do not assume that this is known to the auditor.
DP Upper Bound. The non-private version of our function computes the sum D + ExeD where
each & E is a canary. Hence, the lg sensitivity of the operation is Ag = maX ||0||2 = 1, as
stated in 84.
Since we add & NoO,, Ta),, follows that the operation A(-) (a, -RDP for every 1. Thus, A(-) is 8)-DP where
a 20
1 ad
[1_
$ inf a>l
+
log
+ log
based on [4, Thm. 21J. This can be shown to be bounded above by 1 2 log 1/ + By Theorem 3, follows that the operation A(-) is also (Es, 8)-LiDP
I 20 [44, Prop. 3].
Auditing LiDP. We follow the recipe of Algorithm 1. We set the rejection region R = Rr (CK) as function of the canary eR that differs between Do and D1, where
R+(c,) = {u E Rdd
(u, cj) 2 2
(26)
and IR is tuned threshold.
28

---

UOL de 10
L.,, 4006,
LG, 1854, of
60391 de
Emoree beer bexed
Emerrca bove Soued
Leaed
Narber
Narber zanate C6 1054
ini, d- 10
1096
<w30 6300 de
Erpe al beee bound
Enppe af loundd
Errpe of lowe
Namba canria K
Namber of area &
Narba sauria 1054, if
Narber careeta & 65500 de
1004, 10
Ere real love sound
Erornea scundd
Namber canaiia K
Number of caraa
Narbar zanrka
Namber of caranes &
Erancall over stand
parie ane Pagein
100
Namber conile K
Nambee of
Marber canales
Barrber canaee K
CP Wille
LEP To Drder Willoe
LEP 2ed Oade: Willes
+
LBP 41 Orcar Mi
Figure 9: Effect of the number & canaries on the empirical lower bound & from auditing the Gaussian mechanism for DP and LiDP. The shaded are denotes the standard error over 25 random seeds.
We evaluate empirical privacy auditing methods by how large the lower bound É is - the higher the lower bound, the better the confidence interval.
Methods Compared. An empirical privacy auditing method is defined by the type of privacy auditing (DP LiDP) and the type of confidence intervals. We compare the following auditing methods:
DP + Wilson: audit the usual (e, 8)-DP with = 1 canary. This corresponds exactly to auditing LiDP with K = 1. We use the st--Odeer Wilson confidence intervals for fair comparison with the other LiDP auditing methods. This performs quite similarly to the other intervals used in the literature, cf. Figure 7.
LiDP + Ist-Order Wilson: We audit LiDP with K canaries with the 1st-Order Wilson confidence interval. This method cannot leverage the shrinking of the confidence intervals from higher-order estimates.
LiDP + 2nd/4th-Order Wilson: We audit LiDP with K > canaries using the higher-order Wilson confidence intervals. Unless stated otherwise, we use K test canaries.
Parameters of the Experiment. We vary the following parameters in the experiment:
Number of trials n E {2,,210 ......... 1
Number of canaries k E 21,2, ,..., 200
......2 Dimension d { .... "0...,00....,
29

---

10. 1014 R
c- 10.
1681.
10, x- (013
Ereeeal lowe board
Ersawaa Souved
Dimaatoon
Denerese 966 K-y
Derestoon 1884.
23L Kmy
Km
22, 10530 R
Erpar ca beee boadd
Empie lowe bourdd
Orpiro ca toee board
Erpit toon
Dincwin d
Disrrced d
Dincminn
Drnasise d 02536
06c K-
1085. K-
Dipiccal bowedd
Emppect loune bound
Empicell Loand
Erpanalloos
Dimemion d
Dineract d
Divomion
Dimeuss d
K
K-
62536
scund
Erge oa
Dinension d
Diner slax
Divessoon
Dieeniies
Wilmon
LOP
DnoDrter Wilon
UOP à Ord- Wiloor
-
LCe Sth-Order Welsen
Figure 10: Effect of the data dimension d on the empirical lower bound from auditing the Gaussian mechanism for DP and LiDP. The shaded area denotes the standard error over 25 random seeds.
DP upper bound 418.,4,8).
We fix the DP parameter 8 10-5 and the failure probability 3 0.05.
Tuning the threshold т. For each confidence interval scheme, we repeat the estimation of the lower bound é(T) for a grid of thresholds 7 E on holdout set of trials. We fix the best threshold T" = arg max,er é(T) that gives the largest lower bound é(T) from the grid P. We then fix the threshold -* and report numbers over fresh set of trials.
Randomness and Repetitions. We repeat each experiment 25 times (after fixing the threshold) with different random seeds and report the mean and standard error.
E.2
Additional Experimental Results
Effect of the Number m Test Canaries. In Figure 13, we vary the number m test canaries while keeping the number K of training canaries fixed. We that the 2nd and 4th-order Wilson estimators lead to monotonically improving lower bound é as m increases. However, these improvements soon flatten out between m 8 and value of m K is nearly or equal to the best value of m for K 2 16.
32 depending on other parameters. In particular, the default
We give additional experimental results, expanding the plots shown in Figures 3 and 4:
Figure 8 shows the effect of varying the number of trials n, similar to Figure 3 (left).
30

---

LG UCL 2-
16 36s, 2-
16 1826.
6653) de
Comiitionn Mecuse
Corrlido Meoore
Coneloon Morure
Narbber cronee
crooee
1835,
(753) de
Conseette Meaus
Con-daooe Mozure
Cor-daite Mosure
Hamber of cararix X cw
Narber canerics
Narba canrica 1635,
Narba of caneria R 02535, di 10
af 113
Commation Monee
Conviction Mozure
Comaation Monare
Namber of canaris X
Namber canarics
Namber canaria
Narber of cararic R
Coveaton Manure
Cereaton Menurr
Cern at
Mamber eT craares
Navber Grrales
Namber coarles
Namber careree R.
Figure 11: Effect of the number canaries on the moment estimates employed by the higher-order Wilson intervals in auditing LiDP.
Figure 9 shows the effect of varying the number of canaries k similar to Figure (middle).
Figure 10 shows the effect of varying the data dimension d, similar to Figure 3 (right).
Figure 11 shows the effect of varying the number of canaries on the moment estimates, similar to Figure 4 (right).
Figure 12 shows the effect varying the data dimension d on the moment estimates, similar to Figure 4 (right).
We observe that the insights discussed in $4 hold across wide range of the parameter values. In addition, we make the following observations.
The benefit of higher-order confidence estimators. We see from Figures to 10 that the higher- order Wilson estimators lead to larger relative improvements at smaller s. On the other hand, they perform similarly at large (e.g.. 8) the lower-order estimators.
4th-Order Wilson vs. 2nd-Order Wilson. note that 4th-order Wilson interval outperforms the 2nd-order Wilson interval at 1, while the opposite is true at large 8. At intermediate values E, both behave very similarly. We suggest the 2nd-order Wilson interval default because it is nearly as good or better than the 4th-order variant across the board, but is casier implement.
31

---

F- 1.0, n. 1011 K
<- 10, 1955 Re
F- 10. 1638, Kin
2- 10. 5006 X K-ye
Moreee suastto
Mereet mutitto
Moneet 5.
Divestion
Dirastio 1886.
Dinastoon
2024
Km
0900
Noment moseee
Nomernt meste
Norenn seatte
Discmind
Dircnion
Dironten
Dincmion d
1995,
1688) Ki v/o
Merent nas aba
Moment vas sboa
Dinetiion
Diressoon
Direnion
Dimamion d
4095,
1688, K-
Moree sererr
Morren nererca
Morem caete
Dine
Diresion
Diresdon
Dinenionn d
1/
W
Figure 12: Effect of the data dimension on the moment estimates employed by the higher-order Wilson intervals in auditing LiDP.
4656,
Erperca lowe
cararic
Figure 13: Effect of varying the number of test canaries with the number K of canaries inserted in the training being fixed.
Experiments: Details and More Results
We describe the detailed experimental setup here.
E.1
Training Details: Datasets, Models
We consider two datasets, FMNIST and Purchase-100 Both are multiclass classification datasets trained with the cross-entropy loss using stochastic gradient descent (without momentum) for fixed epoch budget.
32

---

FMNIST: FMNIST or FashionMNIST [65] is a classification of 28 x 28 grayscale images of various articles of clothing into 10 classes. It contains 60K train images and 10K test images. The dataset is available under the MIT license. We experiment with two models: a linear model and a multi-layer perceptron (MIP) with 2 hidden layers of dimension 256 each. We train each model for 30 epochs with a batch size of 100 and fixed learning rate of 0.02 for the linear model and 0.01 for the MLP.
Purchase-100 The Purchase dataset based on Kaggle's 's "acquire valued shoppers" chal- lenge [19] that records the shopping history of 200K customers. The dataset is available publicly on Kaggle but the owners have not created license far as we could tell. We use the preprocessed version of [53]* where the input is 600-dimensional binary vector encoding the shopping history. The classes are obtained by grouping the records into 100 clusters using k-menn. We use fixed subsample of 20K training points and 5K test points. The model is a MLP with hidden layers of 256 units each. It is trained for 100 epochs with a batch size of 100 and a fixed learning rate of 0.05.
F.2 DP and Auditing Setup
We train each dataset-model pair with DP-SGD [1]. The noise level is calibrated so that the entire training algorithm satisfies (s, (e,5)-dit -)-differenttal privacy with varying and 5 = 10-5 fixed across all experiments. We tune the per-exereeeee per-example gradient clip norm for each dataset, model, and DP parameter e so as to maximize the validation accuracy.
Auditing Setup. We follow the LiDP auditing setup described in Appendix B.2. Recall that auditing LiDP with K = 1 canaries and corresponds exactly with auditing DP. We train n E (125, 250, 500, 1000) trials, where each trial corresponds run. We try two methods for canary design (as well as their corresponding rejection regions), as discussed in Appendix D: data poisoning and random gradients.
model trained with K canaries in each
With data poisoning for FMNIST, we define the canary distribution Peantry as the uniform distribution over the last p = 284 principal components (i.e., principal components 500 to 784). For Purchase- 100, we use the uniform distribution over the last p = 300 principal components (i.e., principal components 300 to 600).
For both settings, we audit only the final model, assuming that we do not have access to the interme- diate models. This corresponds to the blackbox auditing setting for data poisoning and a graybox setting for random gradient canaries.
F.3 Miscellaneous Details
Hardware. We run each job on an internal compute cluster using only CPUs (i.e., no hardware accelerators such as GPUs were used). Each job was run with CPU cores and 16G memory.
E4
Additional Experimental Results
F.4.1
Comparison to Bayesian Auditing of DP
We compare the proposed LiDP auditing approach with the Bayesian approach of Begella- et al. [69]. This approach constructs posterior distribution over the true and false positive rates by updating the non-informative Jeffreys priors using empirical observations. They use Bayesian credible intervals (as opposed confidence intervals in our case) computed using numerical quadrature.
We compare the proposed LiDP auditing with = m > 1 with the Bayesian approach [69] with K = = 1 in Figure 14 using the code open-sourced by the authors.* 4 Owing to the increased runtime in the numerical estimation of the E of the Bayesian approach, we tune its threshold r to separate the null and alternate hypotheses (cf. line 5 of Algorithm 1) for the Clopper-Pearson interval.
We observe that the LiDP auditing approach generally provides improved estimates when compared to this baseline. Note that the reason behind the improvement for the Bayesian approach of [69] is by capture the joint distribution of the true and false positive rates, while the improvement behind LiDP
http:://ggggabbbcooeerrtrtstttts "nttps://githur
httpph/wwwe//ccccooo/////e/ssaaa toll--toolooxxppe privacy
33

---

ForiwedeNIsT I laver Pan Poloning
ExekosoNNSTT line Rosson Grodleet
FsdvorkraST-MIF Dan Polwwigg
Fosh coMMISTT MIP Raadon foadent
Erontal
Eroneal
DP las Order Wieer +
De Bayeaan Credile Inaval
LDP IndlOrder Wison
-
LDP
4th-Order
Witso
Figure 14; Comparing the proposed LiDP auditing approach to the Bayesian credible interval approach of Zanella-Béguelin et al. [69].
FNNIST-Lieer c-m Data Canary
FMMST-MLP Date Gasay
Pardhoo 100 MLP 2 Date Gasay
Parchae 100 M03.MPPPPPP.. / - 36 Gral. Caney
017
Enrer FEEE Froee
0.50
Number
Number Canales
Namber
DP When
DF
Bansión
UDP Ond Whon
-
LDP OxlOOde Banolón
Figure 15: Comparison of higher-order Bersstein and Wilson confidence intervals for LiDP auditing.
auditing by a clever use randomized tests. Both sources of improvements are orthogonal each other. This suggests an interesting future research direction: adapt Bayesian credible intervals for LiDP auditing to get the best of both worlds.
E.4.2 Comparison of Asymptotic vs. Non-asymptotic Confidence Intervals
We compare the asymptotic Wilson intervals (used primarily in the experiments) to the non-asymptotic Bernstein intervals (used primarily for the theory) in Figure 15. The results show that the Wilson intervals give larger empirical lower bounds in general with all other parameters remaining the same. This is as expected because the Wilson intervals are an asymptotic tightening of the Bernstein intervals shown in Figure 2.
F.4.3 Experiments Across Different Parameter Settings
We give the following plots to augment Table and Figure 6:
Figure 16: plot of the test accuracy upon adding K canaries to the training process.
Figure 17: experimental results for FMNIST linear model.
Figure 18: experimental results for FMNIST MLP model.
Figure 19: experimental results for Purchase MLP model.
34

---

FMNIST-Linear Data Poisoning
FMNIST-MLP Data Poisoning
Purchase-100-ML Data Polsoning
0.59
0.50
0.65
0.40
Test Test
0.25
Text
0.000
0.20
20
Number er of canaries K
Number of canaries K
Number of canaries
FMNIST-Linear Random Gradlent
FMNIST-MLP Random Gradlent
Turchase-100-MLI Random Gradient
03858
c,00
Test Accuracy
0.844
2.45
0.45
0.40
0.35
Test
2ass-
0.30
0.62
1.20
0.25
Number canaries
Number canaries
Number of canaries
c= 1,0
2.0
==0 4,0
8.0
16.0
Figure 16: Test accuracy the number of canaries K. We plot the 1000 training runs (the standard in under 10-5), Adding multiple canaries audit LiDP does have any impact the final accuracy the model trained with DP.
35

---

Linse Model FMNIST
DP
Empeiiaal cowe lovard
Easeicall louadd
Narbar unde DP am
Nambo of trab DP 16.0
harber oliaao DP
Emgrva Souen Soand
Empree
Nanborr trida
Namber of trab
humber of braan
Liner Model FMNIST with Random Gradient Canary
Dxpplcad lover bound
D 1xl
BP 160
DP 200
Emprrc leee Lvwnd
Number of trab
Namber trabk
Namber of crab
Linea Model on FMNIST with Data Poisoning Canary
DF
Emrpeca Sooer hoxwed
Orgabul loree loued
Eripicl
Number
Number
Narber
Emaiics Stand
beee sound
Linear on FMNIST with Random Grodient Canary
DPimm
DP DP
Drppicl Iove
Emrprtan prrpeiaa Roowr Answetl F
lover Squeel
Namber curaro
Number uneia X
Nandor of Launio
Eneeica owe stadd
Empaicoa col lover
BP Wilies
UOP 1e-Order Wilce
LDP 2nd Order Villos
- LOP + 4th Order Wiloo
Figure 17: Experimental results for FMNIST linear model (top two: varying n, bottom two: varying K).
36

---

MLP Model FMNNST with Data Canary
DP
Empiical lowe louad/
Eryekical
Narbor tidd DP am
Nambe of trab DP 16.
harber of Inaao DP
Emerra lower boand
Emgriea
Nanbor trads
Namber of trab
humber of braa
MIP Model on FMNNST with Random Gradient Cansry
0.75
Emyiicall louue loundd
Empoica loue boaed
BP
y- 16.0
Do a 3211
Emsrra bvend
Emsira beer Loune
harbe of biasn
Number of trab
Narbor trida
MLP Model on FMNIST with Data Paisoning Canary
DP
Erppicllonn
Eriphal
Number Canaris
Number
Exsirc teer Hrad
Emaince ca bave stand
Number
MLP Model on FMNIST with Random Grodient Canary
DP 2
Erppeeal lover bouen
Nanber of dlurei
Number unaia A
Nandor of Launio
Number
11:0 Km v/n
BP Wilies
LOP Oiderder Wilce
LDP 2nd Order Willos
-
LOP 4th Order Wilson
Figure 18: Experimental results for FMNIST MLP model (top two: varying bottom two: varying K),
37

---

MLP Madel Purchee-110 Canaty
DP 20
Emopical opeer boundd
Narba unde DP am
Nambe of trab DP am 16.0
harber of Inaaon DP
cas mon
Emerra lower boand
Emerica bover
Nanborr trida
Namber of trab
humber of braan
MIP Model on Purchase-100 with Random Gradient Canary
Emgircal lowe lound
trad 3P RC
Namber BP y- 16.0
traam DP P 201
Emsira bound
Emorce boend
Nambar mide
Number of trab
humber of bras
MLP Model on Purchase 100 with Data Paisoning Canary
DF
DP
Errpeccl Fooer houadd
1
Eipitaal lopen Souedd
Dripkal
Number
Number Canals
Narber
Ensira love Stand
Number
MLP on Purchase-100 with Random Gradient Canary
DP =
DP D
Enrpiica Rowwr i
Lower
Namber Ba dlune
Number Lnnaaa K
Navdo of Laento
Enpiica owe seard
Erea coe lover
DP Wilies
UOP OrdOrder Wilce
- LBP
2nd Order Willos
- LOP + 4th- Order Wilson
Figure 19; Experimental results for Purchase- 100 MLP model (top two: varying n, bottom two: varying K),
38


Reviews:
[{"review_id": "LmGMZBme2f", "reviewer": "Reviewer_1JBM", "summary": "This paper presents a methodology for calculating lower bounds for the parameter $\\\\varepsilon$ of an $(\\\\varepsilon,\\\\delta)$-differentially private (DP) mechanism. When applied to machine learning algorithms, the methodology can be used to audit the privacy guarantees of popular training algorithms such as DP-SGD.\n\nThe paper builds on existing methods that audit DP guarantees by testing the presence of a canary in the input of the mechanism. Given an $(\\\\varepsilon,\\\\delta)$-DP mechanism $\\\\mathcal{A}$, two neighboring datasets $D_0$ and $D_1 = D_0 \\\\cup \\\\{c\\\\}$ and a measurable set $R$, a lower bound for $\\\\varepsilon$ is given by\n\n$$\n   \\\\varepsilon \\\\geq\n   \\\\log (\\\\mathbb{P}(\\\\mathcal{A}(D_1) \\\\in R) - \\\\delta) -\n   \\\\log \\\\mathbb{P}(\\\\mathcal{A}(D_0) \\\\in R) .\n$$\n\nA lower bound for $\\\\varepsilon$ can be derived from a lower bound $\\\\underline{\\\\boldsymbol{p}}_1 \\\\leq \\\\mathbb{P}(\\\\mathcal{A}(D_1) \\\\in R)$ and an upper bound $\\\\overline{\\\\boldsymbol{p}}_0 \\\\geq \\\\mathbb{P}(\\\\mathcal{A}(D_0) \\\\in R)$ estimated from samples. This lower bound can be made tighter by choosing a canary $c$ whose presence in the training dataset can be easily tested with a rejection set $R$. However, using Bernoulli confidence intervals computed from $n$ samples, the bounds $\\\\underline{\\\\boldsymbol{p}}_1, \\\\overline{\\\\boldsymbol{p}}_0$ are loose by a factor of $1/\\\\sqrt{n}$. Since each sample requires evaluating $\\\\mathcal{A}$ on a different dataset $D_0$, decreasing this factor is expensive.\n\nThe key idea of the paper is to instead audit a probabilistic lifting of DP (LiDP) using counterexamples sampled from a joint distribution $( \\\\boldsymbol{D_0},  \\\\boldsymbol{D_1}, \\\\boldsymbol{R})$. While entirely equivalent to DP, thanks to the exchangeability of random i.i.d canaries  LiDP allows reusing samples $\\\\mathcal{A}(D \\\\cup \\\\{c_1,\\\\ldots,c_K\\\\})$ and $\\\\mathcal{A}(D \\\\cup \\\\{c_1,\\\\ldots,c_{K-1}\\\\})$ to gather multiple correlated test statistics $\\\\boldsymbol{x}_k$, one for each canary $c_k$. A lower bound for $\\\\varepsilon$ can be then calculated similarly as for DP from bounds of the mean of these statistics. The paper analyzes the correlation between the statistics to derive higher-order exact (Bernstein) and asymptotic (Wilson) confidence intervals. Importantly, the authors prove that $\\\\ell$-th order bounds are loose by a factor of $n^{(1-2\\\\ell)/(2\\\\ell)}$ when choosing $K = \\\\lceil n^{(\\\\ell-1)/\\\\ell} \\\\rceil$ and so e.g. second-order bounds reduce the number of samples required to attain a given confidence because their looseness decreases as $1/n^{3/2}$ rather than $1/n^{1/2}$ for first-order bounds (and previous methods auditing DP).\n\nThe authors evaluate the methodology on a Gaussian mechanism showing a 4x gain in sample efficiency when using second-order confidence intervals with $n=1000$ compared to a baseline using Bernoulli confidence intervals. They also evaluate the method on linear and 2-layer MLP classifiers trained with DP-SGD on FMNIST and Purchase-100 using either random or clipping-aware poisoned canaries [31]. This evaluation shows an average improvement in sample efficiency of up to 3x also with $n=1000$.\n\nThe supplemental material includes proofs of the results in the paper, algorithmic descriptions of the methodology, a derivation of asymptotic Wilson intervals, and comprehensive ablation studies varying the privacy budget $\\\\varepsilon$, the number of canaries $K$, samples $n$, and dimension (for the Gaussian mechanism).\n", "questions": "1. Using the form of Bernstein's bound I am familiar with (Dudley, Richard M. Uniform central limit theorems. Vol. 142. CUP, 2014) would give a slightly tighter bound than in Equation (6). The bound in the paper seems to use $\\\\sqrt{a+b} \\\\leq \\\\sqrt{a} + \\\\sqrt{b}$ to simplify it, making it looser. Can you clarify whether you use this simplification, or else provide a detailed derivation?\n\n2. In your evaluation, do you set $m = K$ in Algorithm 1?\n\n3. There seems to be a qualitative difference between $\\\\underline{\\\\boldsymbol{p}}_1$ and $\\\\overline{\\\\boldsymbol{p}}_0$ in Algorithm 1 that is not discussed in the paper. The former is calculated from statistics $\\\\boldsymbol{x}^{(i)}$ using canaries $c_1,\\\\ldots,c_K$ inserted into the training set while the latter is calculated from statistics $\\\\boldsymbol{y}^{(i)}$ depending on canaries $c'_1,\\\\ldots,c'_m$ not in the training set that are independent of the output of the mechanism (the statistics themselves are correlated because they all use the same model). The bias-variance tradeoffs that you discuss in §4 seem to apply only to $c_k$. Are there tradeoffs that make increasing the number of out-canaries $m$ not always beneficial?\n\n### Details\n\n- The paper presents exact Bernstein confidence intervals but then uses asymptotic Wilson intervals exclusively in the evaluation. The two are only compared in Figure 2. I would have liked to see an additional comparison in at least some selected empirical results for bounds on $\\varepsilon$.\n\n- In Eq.1 $D,D'$ should be $D_0,D_1$. This has been fixed in the PDF in the supplemental material.\n\n- l.119: \"the canary has the freedom\" => \"the **adversary** has the freedom\"?\n\n- l.197: \"applying probabilistic method\" => \"applying **a heuristic** method\"?\n\n- Figure 1 is not referenced. I think it is supposed to support the analysis in the paragraph starting at line 271.\n\n- In Figure 3 caption: \"require number\" => \"required number\"\n\n- l.243: \"find §4 that\" => \"find **in** §4 that\"\n\n- l.346: \"it worth\" => \"it **is** worth\"\n\n- l.710: $k$ => $K$\n\n- In Algorithm 3 in steps 4 and 5, and in Algorithm 4 in steps 5 and 6, I believe that there is a missing $\\frac{K-1}{K}$ multiplying $\\overline{\\boldsymbol{\\mu}}_2$ as in Equation (17).", "limitations": "The authors discuss some limitations of the auditing methodology throughout the paper and discuss the need to balance the tightness/computation trade-off in practice.\n\nIt could be a good idea to complement this with a discussion of how the lower bounds for $\\\\varepsilon$ depend on the canary design and detection strategy, how to interpret the gap between lower bounds and the theoretical guarantee of a mechanism, and the impact of deciding whether a mechanism provides enough privacy based on a lower bound alone.\n\nI also believe that given the size and variety of the ML models used in the evaluation, the paper should discuss how the results may extrapolate to other architectures and larger number of parameters. Figure 4 (right) shows the method may benefit as the dimension increases; it would be great if this effect could be backed with experimental results on ML models.", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. A novel method for auditing differential privacy that can be combined with existing canary design strategies and improve sample efficiency.\n\n2. First formal analysis of previously used heuristics reusing trained models to obtain multiple samples.\n\n3. Technically solid theoretical foundations. Detailed proofs. Derivation of exact and asymptotic confidence intervals.\n\n4. Great high-level intuition for why the method improves sample efficiency and the reasons for the bias/variance trade-off in selecting the number of canaries to use.\n\n5. Extensive algorithmic descriptions of the method in the supplemental material that make the paper fairly self-contained and enable reproducibility. Authors promise to open-source their code to replicate results.", "weaknesses": "1. The evaluation on ML scenarios uses very simple models: a linear model and MLPs with 2 hidden layers with 256 units (269k and 245k parameters for FMNIST and Purchase-100, respectively).\n\n2. Evaluation baselines are limited to approaches using Bernoulli confidence intervals and not to more recent approaches using credible regions [66] which also claim improved sample efficiency.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for a thorough review and thought-provoking questions!\n\n\n> **Weakness 1: ... very simple models and small datasets ...**\n\nThese are standard benchmarks in privacy auditing literature, due to computational limitations. We refer to our response at the end of this rebuttal for a discussion. We note that the purpose of auditing is to check for the sanity of the training algorithm, which (in principle) is independent of the model size and the dataset size. In practice, one could use a smaller model and a smaller dataset to audit an algorithm, and, if it passes, deploy a larger model on a larger dataset. We agree that this is not ideal, but perhaps is a practical compromise to speed up the adoption of these tools. \n\n> **Weakness 2: Evaluation with Bayesian credible intervals as baselines**\n\nFollowing the reviewer’s suggestion, we obtained the lower Bayesian credible interval from the approach of [Zanella-Béguelin et al.](https://arxiv.org/pdf/2206.05199.pdf) Our approach generally provides _improved estimates_ when compared to this baseline. Please see **Figure 1 of the rebuttal PDF** for detailed results. \n\nThis suggests an interesting future research direction: adapt Bayesian credible intervals for LiDP auditing to get the best of both worlds.\n\n> **Question 1: Bernstein Inequality**\n\nWe use the analytically simpler bound since our purpose of deriving the Bernstein bound is to understand the tradeoff and their asymptotic dependence. The standard form of Bernstein’s inequality states that the empirical mean $\\hat\\mu_n$ from $n$ samples of i.i.d. $b$-bounded random variables with mean $\\mu$, variance $\\sigma^2$ is bounded with probability at least $1-\\beta$ as \n$$\n\\mu - \\hat \\mu_n \\le \\sqrt{\\frac{2\\sigma^2}{n} \\log\\frac{1}{\\beta} + \\frac{b^2}{9n^2} \\log^2 \\frac{1}{\\beta}} + \\frac{b}{3n} \\log\\frac{1}{\\beta} \n        \\le \n        \\sqrt{\\frac{2\\sigma^2}{n} \\log\\frac{1}{\\beta}} + \\frac{2b}{3n} \\log\\frac{1}{\\beta}\n\t\t$$\n\t\twhere the last inequality used $\\sqrt{a+b} \\le \\sqrt{a} + \\sqrt{b}$ as the reviewer rightly guessed (and similarly for the other tail).\n\n> **Question 2: Do you set $m=K$?**\n\nYes, all the simulations and experiments in the paper use $m=K$ throughout.\n\n> **Question 3: Are there tradeoffs that make increasing the number of out-canaries $m$ not always beneficial?**\n\nThank you for pointing out this subtlety – you are right! There is no bias-variance tradeoff associated with the number $m$ of canaries used for the null hypothesis (which we refer to as “test canaries” below) and larger $m$ never hurts. \n\nWe show the plots for the synthetic Gaussian setting in **Figure 2 of the rebuttal PDF**. We find a near-monotonic improvement in the lower bound as $m$ grows larger but the improvement quickly saturates at or before $m = 2K$. The bias-variance trade-off w.r.t. $K$ still holds though, irrespective of the value of $m$.\n\n> **Details: Numerical comparison of Bernstein and Wilson intervals in the evaluation**\n\nWe refer to **Figure 3 of the rebuttal PDF**. While the Bernstein intervals have slightly worse performance than Wilson intervals as expected, LiDP auditing with Bernstein intervals still leads to improvements over DP auditing with Bernstein intervals.\n\n> **Typos, particularly the missing factor of $\\frac{K-1}{K}$**\n\nGreat catch, we fixed this and other typos. Thanks!\n\n> **Limitations and suggestions on topics to discuss**\n\nThese are great topics worthy of a detailed discussion. We add a brief note here and a more detailed discussion in the paper.\n\n> **Discussion of how the lower bounds depend on the canary design and detection strategy**  \n\nWe provide a detailed discussion on lower bounds in Appendix A. The lower bound for auditing depends on making the right side of Eq. (1) small. This can be done by canary and rejection set design so that the canary is easy to detect. In other words, $\\mathbb{P}(\\mathcal{A}(D_1) \\in R)$ is large and  $\\mathbb{P}(\\mathcal{A}(D_0) \\in R)$ is small. Much previous work has focused on this (particularly on designing the canary); we review this literature in Appendix A.1. On the other hand, our work focuses on improving the statistical dependence on the number of trials (as reviewed in Appendix A.2).\n\n> **Size and variety of models**  \n\nOur analysis in Figures 3 & 4 (and Figures 9 & 11 in the appendix) indicates that random gradient canaries in particular would scale well to larger models. The current bottleneck to larger-scale adoption of rigorous privacy auditing is the prohibitive cost of training multiple models (see also the size of datasets/models in the previous literature [[1](https://arxiv.org/pdf/2006.07709.pdf), [2](https://arxiv.org/pdf/2202.12219.pdf), [3](https://www.computer.org/csdl/proceedings-article/sp/2021/893400b183/1t0x9402gY8), [4](https://openreview.net/pdf?id=AKM3C3tsSx3)]). Our work alleviates this cost to some extent but making privacy auditing feasible at larger scales still requires further research. \n\n"}, {"review_id": "G7omF0M9Xs", "reviewer": "Reviewer_jDkd", "summary": "This work studies the sample complexity (in terms of sampled models) of auditing differential privacy. It proposes a new approach to usage of canaries in auditing via hypothesis test, breaking an existing sample complexity barrier by making use of multiple, randomized canaries. These randomized canaries are used to audit a new, but equivalent formulation of approximate differential privacy called lifted DP, which states a privacy condition for neighboring datasets and rejection sets sampled from a distribution. Sampled models are reused to compute test statistics for each of the multiple canaries included in the dataset, and confidence intervals for the average test statistic are computed using techniques introduced in the paper, tailored to the distribution of test statistics produced by the new auditing method. Empirical evaluation of the proposed method is also given.", "questions": "See comments in weaknesses.", "limitations": "Yes, the authors adequately addressed potential societal impact.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper makes progress in improving the sample complexity of DP auditing by introducing new techniques that should be compatible with future progress in strengthening canaries. The usage of multiple, randomized canaries is innovative and novel tools were used to adapt their usage to existing hypothesis testing frameworks for auditing. The empirical results in Section 4 and 6 were quite helpful in interpreting the expected sample complexity improvements from various choices of K and order of confidence interval.", "weaknesses": "The sample complexity improvements seem notable, but I'm curious about how large of a bottleneck sample complexity is to practical auditing efforts. I'd expect it to be a significant obstacle, but additional discussion of the extent to which sample complexity impedes privacy auditing could help further motivate this work.\n \nNotes:\npg 5 - \"in practice, it depends on how correlated the K test are\"\nIn the caption of figure 3 - \"provides significant gain in the require number of trials to achieve a desired level of lower bound\"\npg 9 - \"For deployment in production, it worth further studying approaches with minimal computational overhead\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": " We thank the reviewer for a constructive review.\n\n**Additional discussion on the bottleneck of sample complexity for privacy auditing:** \n\nAuditing DP is fundamentally constrained by the sample size $n$, where each sample corresponds to one trained model. Rigorous lower bounds on privacy require $1/\\sqrt{n}$ confidence intervals. To get convincing results, [Tramer et al.](https://arxiv.org/pdf/2202.12219.pdf) train $n=10^5$ models, but auditing generally requires $n=O(10^3)$ [[Jagielski et al.](https://proceedings.neurips.cc/paper_files/paper/2020/file/fc4ddc15f9f4b4b06ef7844d6bb53abf-Paper.pdf)]. This makes it unusable for all but the smallest models and datasets. Past approaches use heuristics without rigorous justification to avoid this large computational cost, e.g. [[Zanella-Béguelin et al.](https://arxiv.org/pdf/2206.05199)]. We will add this quantitative discussion in the motivation section.\n\nWe introduce LiDP, which is equivalent to regular DP, but lets us use randomized canaries. We present a novel recipe based on a randomized leave-one-out hypothesis test to audit LiDP. We propose adaptive confidence intervals to leverage multiple correlated observations from each experiment. Altogether, we obtain the same rigorous lower bounds as the baselines with up to 16x smaller sample size for synthetic simulations and up to 5x for real data experiments. \n\nThis directly translates into a 5x gain in the run-time of auditing, enabling the use of rigorous privacy auditing with a reduced computational cost. This, we believe, will speed up and broaden the adoption of these important tools for auditing private mechanisms. Further, the novel technical tools we develop in this paper — LiDP and adaptive XBern confidence intervals — might be of general interest beyond auditing.\n"}, {"review_id": "ZjghWe0Zrk", "reviewer": "Reviewer_2DXh", "summary": "The authors propose a principled improvement over existing privacy auditing techniques. Privacy auditing through the binary hypothesis testing formulation implies gathering samples on the success of the adversary when trying to correctly guess the membership game against a mechanism $M$. All auditing techniques involve switching to a high-probability argument via confidence intervals to be able to provide lower bounds. These CIs converge with a rate of $O(\\frac{1}{\\sqrt{N}})$, where N is the number of auditing samples. The goal of this paper is to improve this convergence rate by testing multiple (possibly correlated) samples at a time, providing an improvement for the convergence of up to $O(\\frac{1}{\\sqrt{NK}})$, where K is the number of inserted canaries. Their proposed technique is as follows: 1. Run the mechanism $M$ on $D \\cup ( c_1, .., c_K ) $ and $D \\cup (c_1, .., c_{K-1}) $, where the canaries are iid samples drawn from a fixed canary distribution. Through a clever randomisation argument, using the property that the canaries are iid from the same distribution, the authors propose testing multiple iid canaries by testing other iid canaries by exchanging the missing $c_K$ with other iid canaries. By doing this, the authors can test $K$ test statistics for the alternative hypothesis and $M$ test statistics for the null hypothesis. Now, the goal is to integrate this new information into the confidence interval. The authors do not make an independence assumption as in previous work and derive a tailored confidence interval that accounts for the possible correlation between the K tests. Their analysis shows how their confidence interval converges with a rate of $O(\\frac{1}{\\sqrt{N\n}})$ when the statistics are correlated to a rate of $O(\\frac{1}{\\sqrt{NK}})$ when the statistics are independent.", "questions": "* The proposed auditing technique is not tailored for the Gaussian mechanism but for any mechanism $M$. For example, one could audit a Laplace Mechanism or a Subsampled Gaussian Mechanism with it. I think the authors could stress this out for the reader, as improving auditing sample complexity in the general case is a truly desirable property, and this work does that. Would the authors want to add some details or employ their technique to audit more diverse mechanisms?\n* The bias/variance argument in section 4 holds against a mechanism that averages over a list of gradients, as it is easy to observe how inserting noisy samples will yield privacy amplification in that scenario. Yet, when we audit a machine learning model with input poisoning (so, actual samples need to be inserted, not the gradients), the relationship is not so clear anymore. How many sample canaries could we use for auditing purposes against a machine-learning model? Is there any scenario in which we can hope to audit correctly by training only two models, for example? (n=1, k=?) What is the performance in that scenario?\n", "limitations": "-", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "* The paper has a nice structure, it solves a clearly stated problem known in the privacy auditing community, for which they introduce all the needed formalism and they make the necessary experiments to back up their results.\n* The authors propose an algorithm that could be used as a drop-in replacement for other auditing techniques.\n* Formally accounting for the correlation between hypotheses fills an existing gap in auditing literature when multiple samples are used for auditing purposes. All the literature I am aware of makes an independence assumption, which might be strong in some cases. This work recovers that case but accounts for others as well, framing and formalising in a principled way the multisample testing problem.\n", "weaknesses": "* in the experimental section, the authors show a bias/variance tradeoff when auditing a mechanism M that computes a noisy sum/mean. The same argument does not hold against differentially private machine learning models, and it would be interesting to show if the proposed technique can achieve tightness when auditing a (possibly simple) machine learning pipeline.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for a detailed review and thought-provoking questions.\n\n> **Bias-variance for ML pipelines + auditing with input poisoning**\n\nWe agree with the reviewer that for the Gaussian mechanism, we have all the information to (numerically) compute the bias and variance exactly for our estimator of the TPR and FPR (and consequently $\\varepsilon$). This clearly shows the bias-variance tradeoff that we discuss in the paper.  For an ML pipeline, things are more complicated for obvious reasons as the reviewer insightfully pointed out, but we still believe that a similar bias-variance trade-off holds.\n\n**Bias increases (i.e., lower bound on $\\varepsilon$ decreases) with larger $K$**: This is challenging to show formally, but intuitively we believe this is true for the following reason. Let us consider the actual theoretical $\\varepsilon$ of the mechanism with $K$ random canaries. The privacy (treating the canary $c_K$ are the one that is absent/present in neighboring datasets) is governed by the pair of distribution $P_{A,c_1^K}(\\theta|c_K)$ and $P_{A,c_1^{K-1}}(\\theta)$, where $A$ accounts for the randomness internal to the training mechanism and $c_1^K$ accounts for the randomness in the canaries 1 to $K$. \n\nWe argue that the bias appears because the theoretical $\\varepsilon$ for $K>1$ should be smaller than that of $K=1$. This is suggested by the fact that the pair $P_{A,c_1^K}(\\theta|c_K)$ and $P_{A,c_1^{K-1}}(\\theta)$ when $K>1$ has more *randomness* coming from the other canaries $c_1^{K-1}$ that act as if they are part of the privacy mechanism, and hence gives a higher variance output (which is more private, and hence smaller $\\varepsilon$). We agree that this is hand-wavy and non-rigorous, and probably can only be confirmed empirically. \n\n**Variance decreases with larger $K$**: This refers to the variance of our estimators on TPR and FPR here, and the dominant term in the derivation (for example for the Bernstein bound) decreases with larger $K$. This is regardless of the mechanism that is being considered and should hold for general ML pipelines. However, again the lower order terms can increase marginally with $K$, so for this to be absolutely true, we need large enough $n$ and small enough correlation between the canaries. \n\nWe will add more details about this to the paper.\n\n> **Would the authors want to add some details or employ their technique to audit more diverse mechanisms (Laplace, etc.)?**\n\nWe thank the reviewer for the fantastic suggestion. Indeed, our recipe can be used to audit any mechanism including a general class of mechanisms built from a composition of additive noise mechanisms and subsampling. Note that the DP-SGD we audit in Section 6 includes sub-sampling and amplification by sampling in the mechanism and privacy accountant (for the theoretical upper bound).\n\nIn the original submission, we only tried DP-SGD due to its overwhelming popularity in practice. Here, as a proof of concept, we additionally audit a Laplace mechanism using canaries uniformly from the $L_1$ sphere. The results are qualitatively similar to those of the Gaussian case with a near 8x gain in the sample complexity. We refer to **Figure 4 of the rebuttal PDF** for detailed results.\n\n> **How many sample canaries could we use for auditing purposes against a machine-learning model?**\n\nIn our experiments with real data training, we observed that our lower bound improves with $K$ up to $K=64$ for Purchase data and $K=256$ for FashionMNIST. Afterward, we believe the lower bounds should start to get worse (get smaller) as $K$ increases. Choosing the right $K$ in practice is a difficult task, although using $K=\\sqrt{N}$ seems to give reasonable results. \n\n> **Is there any scenario in which we can hope to audit correctly by training only two models, for example? (n=1, k=?) What is the performance in that scenario?** \n\nGreat question! Our method currently requires $n \\ge K^{\\ell / (\\ell - l)}$ for an $\\ell$th order confidence estimator (Proposition 4). No lower bounds are known here and whether this can be reduced to $n=1$ is an open question.\n\nThe independent and concurrent work of [Steinke et al.](https://arxiv.org/abs/2305.08846) proposes privacy auditing with $n=1$ (this paper appeared on arXiv only 2 days before the NeurIPS deadline). It is not yet clear how their method compares to ours as the experimental settings are not comparable. There is a potential to harness the benefits of both approaches, which we leave as a future research direction.\n\n"}, {"review_id": "tTFam4Gnix", "reviewer": "Reviewer_W8eW", "summary": "The use of canaries is a very intuitive strategy to evaluate the DP mechanism (which can subsequently attract a broader non-DP specialist audience to this area). The paper is structured well, has comprehensive details on both the method and the corresponding experimental results and shows clear motivation and conclusions. This work presents methodology for auditing of DP trained models through the introduction of Lifted DP and canary-based auditing techniques. ", "questions": "What is the dependency with epsilon level? There does not seem to be a clear trend of how well the method performs with more noise being added. I would like the authors to discuss this further and hypothesise what the trend is and why.\n\nCould the authors elaborate on what they mean by ‘poisoning’ canaries? What is the methodology like on non-image modalities?", "limitations": "I described most of the limitations in the weaknesses section, but to summarise: A) it is not clear how the method performs in non-trivial settings (e.g. ImageNet), B) the improvements compared to the work I linked above are not clear. \nOverall, this work shows promise, but I would like the authors to clarify the points I raised above before I can recommend acceptance. ", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The use of canaries is a very intuitive strategy to evaluate the DP mechanism (which can subsequently attract a broader non-DP specialist audience to this area). The paper is structured well, has comprehensive details on both the method and the corresponding experimental results and shows clear motivation and conclusions. ", "weaknesses": "While the method show promise, the evaluation results are not very representative: FMNIST is a rather small dataset and so is Purchase-100. Given that the models associated with these are also rather small too, I do not see how well can this method scale to larger architectures and more complex datasets (especially as the canary-generation process can heavily depend on it).\n\nIt is not very clear to me what the advantage is over the work of https://arxiv.org/abs/2305.08846. Here model auditing can be performed in a single training run, rendering other methods of auditing significantly less efficient. I would like the authors to comment on why their work is a substantial contribution given the existence of this method. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": " We thank the reviewer for the questions.\n\n> **I would like the authors to comment on why their work is a substantial contribution given the existence of the method [of Steinke et al.]**\n\nWe make **4 key contributions**: (1) the framework of lifted DP, (2) a novel randomized leave-one-out hypothesis test for auditing lifted DP, (3) adaptive confidence intervals, (4) detailed numerical results of the frameworks, including the bias-variance trade-offs it involves.\n\nThe independent and concurrent work of Steinke et al. also considers auditing with randomized canaries that are Poisson-sampled, i.e., each canary is included or excluded independently with equal probability. **Their recipe is different from ours**: it involves computing an empirical lower bound by comparing the accuracy (rather than the full confusion matrix as in our case) from the possibly dependent guesses with the worst-case randomized response mechanism. This allows them to use multiple dependent observations from a single trial. Our **confidence intervals** are adaptive to the level of correlation between the canaries, while theirs are non-adaptive and worst-case.\n\nOur work gives a **deeper analysis of the bias-variance tradeoff** from utilizing randomized canaries. Further, we develop two **novel technical tools**, LiDP and adaptive XBern confidence intervals, which could be of general interest to the community.\n\nWe are excited about the possibilities of combining our adaptive confidence intervals (the key to our improvements) with the framework of Steinke et al. (the key to their improvements) to get the best of both worlds. We leave this for future work.\n\nFinally, we note that the work of Steinke et al. was submitted to arXiv on 15 May 2023, i.e. **2 days before the NeurIPS deadline** on 17 May 2023). Per the **[NeurIPS policy](https://nips.cc/Conferences/2023/CallForPapers)**, \"[a] submission will not be rejected on the basis of the comparison to contemporaneous work\". We request the reviewer assess the merits of our substantial theoretical and methodological contributions independently.\n\n\n> **The evaluation results are not very representative… larger architectures and more complex datasets ... non-trivial settings (e.g. ImageNet)**\n\nWe opted for small datasets and models so we could test our theoretical predictions *comprehensively* and compare them with *previous* baselines in the literature. We run **150K experiments for each dataset-model pair** (6 epsilons * 6 values of K * 2 types of canaries * 2000 seeds per setting), which would be infeasible at larger scales. Small datasets and models have also been the norm for the privacy auditing literature, see e.g. [Jagielski et al. NeurIPS 2020](https://arxiv.org/abs/2006.07709), [Nasr et al. IEEE S&P 2021](https://arxiv.org/abs/2101.04535), [Lu et al. NeurIPS 2022](https://arxiv.org/abs/2210.08643).\n\nWe note that the purpose of auditing is to check for the sanity of the training algorithm, which (in principle) is independent of the model size and the dataset size. One could in practice use a smaller model and a smaller dataset to audit an algorithm, and, if it passes, deploy a larger model on a larger dataset. We agree that this is not ideal, but perhaps is a practical compromise to speed up the adoption of these tools.\n\nFurther, demonstrating rigorous privacy auditing at ImageNet scale for the *first time* would in itself be a *significant milestone* in the field. This is outside the scope of our paper, whose key contributions are methodological, foundational, and theoretical.\n\n> **Question: What is the dependency with epsilon level?**\n\nAuditing DP grows exponentially harder with increasing epsilon. Consider for instance, distinguishing between randomized response $\\text{RR}(\\infty)$ vs. $\\text{RR}(\\varepsilon)$, which is equivalent to distinguishing between $\\text{Bern}(1)$ vs. $\\text{Bern}(\\sigma(\\varepsilon))$ where $\\sigma(\\cdot)$ is the sigmoid function. By known lower bounds in hypothesis testing, this requires at least $n \\ge O(1/(1 - \\sigma(\\varepsilon))^2) \\approx e^{2\\varepsilon}$ samples, which is exponential in $\\varepsilon$. Thus, we can only effectively audit smaller $\\varepsilon$.\n\nEmpirically, we see from **Figure 5 of the rebuttal PDF** that LiDP auditing greatly outperforms the baseline at small $\\varepsilon$ (by a multiplicative factor of 2x to 4x). At large $\\varepsilon$, both methods are constrained by the fundamental difficulty described above and perform similarly. \n\n\n> **Why do we refer to ‘poisoning’ canaries?**  \n\nThe phrase “poisoning” comes from the literature on adversarial machine learning where an adversary can “poison” the model training by adding specific (outlier) data points. Much of the prior work on designing canaries for auditing is inspired by this literature. See e.g. [Jagielski et al. (NeurIPS 2020)](https://arxiv.org/abs/2006.07709) for more historical context behind this nomenclature.\n\n> **What is the methodology (to design data poisoning canaries) on non-image modalities? + Canary designs for complex datasets**\n\nWe run our experiments on image and tabular data. Prior work has considered designing canaries for text/speech in the context of memorization analysis (rather than DP auditing). For the text domain, prevailing approaches insert random sequences possibly based on templates as canaries [e.g. [Carlini et al.](https://arxiv.org/abs/1802.08232), [Mireshghallah et al.](https://arxiv.org/abs/2103.07567)]. For the speech modality, prior work uses a text-to-speech engine to convert such text canaries to the speech modality [[Jagielski et al.](https://arxiv.org/abs/2207.00099) p.16]. \n\nOur framework of LiDP auditing is flexible enough to incorporate recent advances in designing canaries for more complex datasets by lifting as illustrated in Section 5 and Appendix D. The aforementioned strategies can be lifted to audit LiDP as they are random by construction. This would be an interesting exploration for future work.\n\n\n"}]

Author rebuttal:
We thank the reviewers for their detailed and thoughtful comments. We are delighted that the reviewer appreciated the novelty, principled formal analyses, and potential impact of our work.

We are excited that the reviewers recognize that our work "solves a clearly stated problem known in the privacy auditing community" with "innovative and novel tools" that are "compatible with future progress in strengthening canaries." We are pleased that the reviewers appreciate the "first formal analysis of previously used heuristics" and "technically solid theoretical foundations" that are supported by "the necessary experiments."

Below, we respond to each reviewer individually. All additional numerical comparisons requested by the reviewers can be found in the attached PDF. We would be happy to answer any further questions or comments!

Meta-review: This paper proposes a new privacy auditing approach that allows the use of multiple canary samples when auditing a model, thereby improving the efficiency of existing privacy auditing. The approach carefully adapts the hypothesis testing machinery to account for the correlations introduced by the use of multiple canaries. Interestingly, it is agnostic to the way the canaries are generated and can thus be combined with past and future canary generation approaches.

The author response helped to clarify some of the concerns raised by one reviewer, who ended up raising his/her score. In the end, there was a consensus for accepting this paper. Therefore, I recommend acceptance.
Decision: Accept (poster)