One-shot Empirical Privacy Estimation for Federated Learning
Authors: Galen Andrew
Peter Kairouz
Sewoong Oh
Alina Oprea
Hugh Brendan McMahan
Vinith Menon Suriyakumar
Venue: ICLR 2024 oral (2024)
Keywords: differential privacy
federated learning
empirical privacy
Primary area: societal considerations including fairness, safety, privacy
TL;DR: Empirical estimation of privacy during training with minimal overhead, useful when tight analytical bounds are not known, e.g. when the adversary observes only the final model.

Abstract: Privacy estimation techniques for differentially private (DP) algorithms are useful for comparing against analytical bounds, or to empirically measure privacy loss in settings where known analytical bounds are not tight. However, existing privacy auditing techniques usually make strong assumptions on the adversary (e.g., knowledge of intermediate model iterates or the training data distribution), are tailored to specific tasks, model architectures, or DP algorithm, and/or require retraining the model many times (typically on the order of thousands). These shortcomings make deploying such techniques at scale difficult in practice, especially in federated settings where model training can take days or weeks. In this work, we present a novel “one-shot” approach that can systematically address these challenges, allowing efficient auditing or estimation of the privacy loss of a model during the same, single training run used to fit model parameters, and without requiring any a priori knowledge about the model architecture, task, or DP algorithm. We show that our method provides provably correct estimates for the privacy loss under the Gaussian mechanism, and we demonstrate its performance on a well-established FL benchmark dataset under several adversarial threat models.

Published as a conference paper at ICLR 2024
ONE-SHOT EMPIRICAL PRIVACY ESTIMATION FOR FEDERATED LEARNING
Galen Andrew
Peter Kairouz"
Sewoong Oh'
Alina Oprea"
H. Brendan McMahan"
Vinith M. Suriyakumar
ABSTRACT
Privacy estimation techniques for differentially private (DP) algorithms are useful for comparing against analytical bounds, empirically measure privacy loss in settings where known analytical bounds are not tight. However, existing privacy auditing techniques usually make strong assumptions on the adversary (e.g.. knowl- edge of intermediate model iterates or the training data distribution), are tailored to specific tasks, model architectures, or DP algorithm, and/or require retraining the model many times (typically on the order of thousands). These shortcomings make deploying such techniques scale difficult in practice, especially in federated settings where model training can take days or weeks. In this work, we present a novel "one-shot" approach that can systematically address these challenges, allow- ing efficient auditing or estimation of the privacy loss of model during the same, single training run used to fit model parameters, and without requiring any a priori knowledge about the model architecture, task, DP training algorithm. We show that our method provides provably correct estimates for the privacy loss under the Gaussian mechanism, and we demonstrate its performance on well-established FL benchmark datasets under several adversarial threat models.
INTRODUCTION
Federated learning (FL. (McMahan et al. 2017 Kairouz et al. 2021b) is paradigm for training machine learning models on decentralized data. At each round, selected clients contribute model updates to be aggregated by server, without ever communicating their raw data. FL incorporates data minimization principles to reduce the risk of compromising anyone's 's data: each user's data never leaves their device, the update that is transmitted contains only information necessary to update the model, the update is encrypted in transit, and the update exists only ephemerally before being combined with other clients' updates and then incorporated into the model (Bonawitz et al. 2022). Technologies such as secure aggregation (Bonawitz et al.) 2017 Bell et al., 2020) can be applied to ensure that even the central server cannot inspect individual updates, but only their aggregate.
However, these data minimization approaches cannot rule out the possibility that an attacker might learn some private information from the training data by directly interrogating the final model (Carlini et al. 2021 Balle et al. 2022 Haim et al., 2022). To protect against this, data anonymization for the model required. FL can augmented to satisfy user-level differential privacy (Dwork and Roth 2014; Abadi et al.] 2016 McMahan et al. (018)), the gold-standard for data anonymization. DP can guarantee each user that a powerful attacker one who knows all other users' data, all details about the algorithm (other than the values of the noise added for DP), and every intermediate model update still cannot confidently infer the presence of that user the population, or anything about their data. This guarantee is typically quantified by the parameters and 6, with lower values corresponding to higher privacy (less confidence for the attacker).
DP is often complemented by empirical privacy estimation techniques, such membership inference attacks (Shokri et al.) 2017 Yeom et al. 2018 Carlini et al.) 2022), which measure the success of an
Google
1 Northeastern University
1 MII
8 "oorespnnniigg author; ga lenandrew@goog1 com

---

Published as a conference paper at ICLR 2024
adversary at distinguishing whether particular record was part of training not Such methods have been used to audit the implementations of DP mechanisms or claims about models trained
with DP (Jagielski et al.) 2020 Nasr et al., 202T: Ganella-Béguelin et al. 2023 Lu et al., 2022). They are also useful for estimating the privacy loss in cases where a tight analytical upper bound on is unknown, for example when clients are constrained to participate in most some number of rounds, or when the adversary does not see the full trace of model iterates. However, existing privacy auditing techniques suffer from several major shortcomings. First, they require retraining the model many times (at least thousands) to provide reliable estimates of DP's e (Jagielski et al. 2020; Nasr et al.] 202T). Second, they often rely on knowledge of the model architecture and/or the underlying dataset (or at least similar, proxy dataset) for mounting the attack. For example, common approach is to craft a "canary" training example on which the membership is being tested, which typically requires an adversary to have access to the underlying dataset and knowledge of the domain and model architecture. Finally, such techniques usually grant the adversary unrealistic power, for example (and in particular) the ability to inspect all model iterates during training (Maddock et al. 2022). something which may or may not be reasonable depending on the system release model.
Such assumptions are particularly difficult to satisfy in FL due to the following considerations:
Minimal access to the dataset, or even to proxy data. A primary motivating feature of FL is is that it can make use of on-device data without (any) centralized data collection. In many tasks, on-device data is more representative of real-world user behavior than any available proxy data.
Infeasibility of training many times, or even more than one time. FL training can take days or weeks, and expends resources on client devices. To minimize auditing time and client resource usage, an ideal auditing technique should produce estimate of privacy during the same, single training run used to optimize model parameters, and without significant overhead from crafting examples or computing additional "fake" training rounds.
Lack of task, domain, and model architecture knowledge. A scalable production FL platform is expected to cater to the needs of many diverse ML applications, from speech to image to language modeling tasks. Therefore, using techniques that require specific knowledge of the task and/or model architecture makes it hard to deploy those techniques at scale in production settings.
In this paper, we design an auditing technique tailored for FL usage with those considerations in mind. We empirically estimate E efficiently under user-level DP federated learning by measuring the training algorithm's 's tendency to memorize arbitrary clients' updates. We insert multiple canary clients in the federated learning protocol with independent random model updates, and design test statistic based on the cosine angle of each canary update with the final model to test participation of that canary client in the protocol. The intuition behind the approach comes from the elementary result that in high-dimensional space, isotropically sampled vectors are nearly orthogonal with high probability. So we can think of each canary as estimating the algorithm's 's tendency to memorize along dimension of variance that is independent of the other canaries, and of the true model updates.
Our method has several favorable propertics. It can be applied during the same, single training run which is used to train the federated model parameters, and therefore does not incur additional performance overhead. Although it does inject some extra noise into the training process, the effeet on model quality is negligible, provided model dimensionality and number of clients are reasonably sized. We show that in the tractable case of a single application of the Gaussian mechanism, our method provably recovers the true, analytical in the limit of high dimensionality. We evaluate privacy loss for several adversarial models of interest, for which existing analytical bounds are not tight. In the case when all intermediate updates are observed and the noise is low, our method produces high values of e. indicating that an attacker could successfully mount a membership inference attack. However, in the common and important case that only the final trained model is released, our e estimate is far lower, suggesting that adding a modest amount of noise is sufficient to prevent leakage, as has been observed by practitioners. Our method can also be used to explore how leakage changes as aspects of the training protocol change, for which no tight theoretical analysis is known, for example if we limit client participation. The method we propose is model and dataset agnostic, so it can be easily applied without change to any federated learning task.
'Some prior work only applies to example-level DP, in which records correspond to examples, as opposed to user-level, in which records are users. We will descrihe our approach in terms of user-level DP, but it can be modified provide example-level DP by using DP-SGD in place of DD-FedAvg.
2

---

Published as a conference paper at ICLR 2024
2 BACKGROUND AND RELATED WORK
2006; Dwork and Roth 2014) is rigorous notion of privacy that algorithm can satisfy. DP algorithms for training ML models include DP-SGD (Abadi et al. (2016), DP-FTRL (Kairouz et al.
Differential privacy. Differential privacy (DP) (Dwork et al.
2021a), and DP matrix factoriza- tion (Denissov et 2022 Choquette- Choo et al. 2023). Informally, DP guarantees that powerful attacker observing the output of the algorithm A trained on one of two adjacent datasets (differing by addition or removal of one record), D D', cannot confidently distinguish the two cases, which is quantified by the privacy parameters e and 8.
Definition 2.1. User-level differential privacy. The training algorithm A D + R is user-level (e, 6) differentially private if for all pairs of datasets D and D' from D that differ only by addition or removal of the data of one user and all output regions C R:
Pr(A(D) E RJ S e Pr[A(D') E R| +
DP can be interpreted as hypothesis test with the null hypothesis that A was trained on D and the alternative hypothesis that was trained on D'. False positives (type-I errors) occur when the null hypothesis is true, but is rejected, while false negatives (type-ll errors) occur when the alternative hypothesis is true, but is rejected. Kairouz et al. (2015) characterized (c. 8)-DP in terms of the false positive rate (FPR) and false negative rate (FNR) achievable by an acceptance region. This characterization enables estimating the privacy parameter as:
1 5 FPR
1 1 Ó - FNR
é = max
log
log
(1)
FNR
FPR
Private federated fearning. DP Federated Averaging (DP-FedAvg) (McMahan et al., 2018) is a user-level DP version of the well-known Federated Averaging (FedAvg) algorithm (McMahan et al. 2017) for training ML models in a distributed fashion. In FedAvg, a central server interacts with set of clients to train global model iteratively over multiple rounds. In each round, the server sends the current global model to a subset of clients, who train local models using their training data, and send the model updates back to the server. The server aggregates the model updates via the Gaussian mechanism, in which each update is clipped to bound its f2 norm before averaging and adding Gaussian noise proportional to the clipping norm sufficient to mask the influence of individual users, and incorporates the aggregate update into the global model. DP- DP-FedAvg can rely on privacy amplification from the sampling of clients at each round, but more sophisticated methods can handle arbitrary participation patterns (Kairouz et al. 2021a Choquette-Chov et al. 2023).
Privacy auditing. 2018, Jagielski et al. 2020) is a set of techniques for empirically auditing the privacy leakage of an algorithm. The main technique used for privacy auditing is mounting membership inference
Privacy auditing (Ding et al., 2018 Liu and Oh| 2019 Gilbert and McMillan
attack (Shokri et al. 2017 Yeom et al., 2018: Carlini et al. 2022) and translating the success of the adversary into an E estimate using Equation (1) directly.
Most privacy auditing techniques (Jagielski et al., 2020 Nasr et al. 202 Lu et al. 2022 Zanella-
Béguelin et al. 2023) have been designed for centralized settings, with the exception of CAN- IFE (Maddock et al. 2022), suitable for privacy auditing of federated learning deployments. CANIFE operates under strong adversarial model, assuming knowledge of all intermediary model updates, as well as local model updates sent by a subset of clients in each round of training. CANIFE crafts data poisoning canaries adaptively, with the goal of generating model updates orthogonal to updates sent by other clients in each round. We argue that when the model dimensionality is sufficiently high, such crafting is unnecessary, since randomly chosen canary update with already be essentially orthogonal to the true updates with high probability. CANIFE also computes a per-round privacy measure, which it extrapolates into a measure for the entire training run by estimating an equivalent por-round noise o, and then composing the RDP of the repeated Poisson subsampled Gaussian mechanism. However, in practice FL systems do not use Poisson subsampling due to the infeasibility of sampling clients i.i.d. at each round. Our method flexibly estimates the privacy loss in the context of arbitrary wow.ultt-to-caaateeiiiie
participation patterns, for example passing over the data in epochs, the de facto pattern of participation in a deployed system, which may include techniques intended to amplify privacy such limits client participation within temporal periods such one day.
3

---

Published as a conference paper at ICLR 2024
We empirically compare approach with CANIFE in Appendix Gadd discuss the assumptions the auditor's 's knowledge and capabilities for all recent approaches (including ours) in Appendix H
3 ONE-SHOT PRIVACY ESTIMATION FOR THE GAUSSIAN MECHANISM
As a warm-up, we start by considering the problem of estimating the privacy of the Gaussian mechanism, the fundamental building block of DP-SGD and DP-FedAvg. To be precise, given D = (11:" , , with | S 1 for all E [m], the output of the Gaussian vector sum query is A(D) = E + oZ, where I = =, 2J and Z ~ (0, Without loss of generality, we can consider neighboring dataset D' with and A(D") ~ (1 + zo, I)
additional vector zo with || < 1. Thus, A(D) (Nr o2) P. For the purpose of computing the DP guarantees, this mechanism is equivalent to analyzing A(D) (00 o²) and A(D") ~ N11, due to spherical symmetry.
The naive approach for estimating the e of an implementation of the Gaussian mechanism would run it many times (say 1000 times), with half of the rums on D and the other half on D'. Then the outputs of these runs are shuffled and given to an "attacker" who attempts to determine for each output whether it computed from D or D'. Finally, the performance of the attacker is quantified in terms of FPR/ENR, and Eq. (T is used to obtain an estimate of the mechanism's 's e at a target ó.
We now present provably correct approach for estimating by running the mechanism only once. The key idea is to augment the original dataset with & canary vectors c; for i E [k]]. sampled i..dd uniformly at random from the unit sphere gd-1 { E Rd: ||=||| 1}. obtaining D Ck). We consider l neighboring datasets, each excluding one of the canaries,
(11, ... Em C1, i... Dj D }er} for [k). We run the Gaussian mechanism once on D and use its output to compute k test statistics {gi (e))). the cosine of the angles between the output and each one of the canary vectors. We use these cosines to estimate the distribution of test statistic on D by
computing the sample mean j = 1 E/= 9i and sample variance 8² E (g. ()) and fitting Gaussian ((a, d²). To estimate the distribution of the test statistic on D', it would seem we need to run the mechanism on each D/ and compute the cosine of the angle between the output vector and c,. This is where our choice of (i) independent isotropically distributed canaries and (it) cosine angles as our test statistic are particularly useful. The distribution of the cosine of the angle between an isotropically distributed unobserved canary and the mechanism output (or any independent vector) can be described in a closed form; there is no need to approximate this distribution with samples. We will show in Propositions 3.1 and 3.2 that this distribution can be well approximated by N( 1/d). Now that we have models of the distribution of the test statistic on D and D', we estimate the of the mechanism using the method given in Appendix A which allows us compute the exact & when the null and alternate hypotheses are arbitrary Gaussians. Our approach is summarized in Algorithm
Algorithm One-shot privacy estimation for Gaussian mechanism.
1: Input: Vectors ",,"." , Fim with ||r $ 1,
DP noise variance o², and target
6: Release p f p N
2: p p+ Eye(m) Øy
7: for i E [K] do
8: + (c,, pllppll
3: for i E [k] do
4: Draw e i.i.d. from 1d-1
9: á t- mean std
5: + +
10: + e(N(O, (R, 0²);
Proposition 3.1. For d E N, 2 2, let c be sampled uniformly from S and let Tu = (c, e)/llu/) e [-1,1] 1] be the cosine similarity between e and some arbitrary independent nonzero vector v. Then, the probability density function of Ta is
T($) fa(t) = T( (1 22)
(All proofs are in Appendix B The indefinite integral of ff can be expressed via the hypergeometric function, or approximated numerically, but we use the fact that the distribution is asymptotically Gaussian with mean zero and variance 1 //d as shown in the following proposition.
4

---

Published as a conference paper at ICLR 2024
Proposition 3.2. Let Ta be the random variable of Proposition 3.1 in R.. Then Tav converges in distribution (0, 1) as d oo, i.e., AA E R. limg-roo P( S 2/ Vd = P2.N( S X).
For d 2 1000 or so the discrepancy is already extremely small: we simulated IM samples from the correct cosine distribution with d 1000, and the strong Snderson-Darling test failed to reject the null hypothesis of Gaussianity at even the low significance level of 0. 1 Therefore, we propose to use (0, l/d) as the null hypothesis distribution when dimensionality is high enough.
Finally, one might ask: what justifies fitting Gaussian M(i, 6²) to the samples for the alternate distribution? While appears empirically that the distribution of the cosine angles under the alternate distribution is asymptotically Gaussian, there are some subtleties in proving this, we discuss in Appendix C But the important thing is that under this choice, as becomes large, Algorithm ] outputs an estimate& é that is asymptotically equal to the correct e of the mechanism we are auditing.
Theorem 3.3. For d E N. For some m. (which may grow with d), let Tal Fddn such that
||aall = =oVa) where Xa = ===1 Tdj- Let = o(d), but = =w(1,, and for E [b]] let cai be sampled i.i.d. uniformly from Sd-1, Let Za ~ N() For a E Rt,, define the mechanism result Pa Xa + Σ Cds oZa. and the cosine values 9 Tlaal
icar-pa). Write the empirical
mean of the cosines Pia = 1/2 E Idi, and the empirical variance 02 = E -pa)² Let Ed = c( 1/d) II (NPa,, 0)) Then éd converges in probability to the constans o2)(0,)2
Running the algorithm with moderate values of d and k already yields a close approximation. We simulated the algorithm for d ranging from 10 to 10?, always setting k- = vd. The results are shown in Table | The mean estimate is always very close to the true value of E. There is more noise when is small, but method is primarily designed for "normal" scale contemporary deep-learning models which easily surpass IM parameters, and at these sizes the method is very accurate.
analytical d= 10a
d= 10
d d= 106
d 107
0.541
10.0
9.89 = 0.71
10.1 00.100.0 0.41
10.0 0.23
10.0 + 0.10
1.54
3.0
3.00 + 0.46
3.00 + 0.31
2.96 + 0.15
3.00 + 0.08
4.22
1.0
0.98 + 0.41
1.05 + 0.23
0.99 + 0.14
1.00 + 0.07
Table 1: One-shot auditing of the Gaussian mechanism for a range of values of d, setting k
and 8 = 10-6 For each value of e, we set a using the optimal calibration of Balle and Wang 201 8). Shown is the mean and std Eest over 50 simulations.
ONE-SHOT PRIVACY ESTIMATION FOR FL WITH RANDOM CANARIES
We now extend this idea to DP Federated Averaging to estimate the privacy of releasing the final model parameters in one shot, during model training. We propose adding & canary clients to the training population who participate exactly as real clients do. Each canary client generates a random model update sampled from the unit sphere, which it returns every round in which it participates, scaled to have norm equal to the clipping norm for the round. After training, we collect the set of canary/final-model cosines, fit them Gaussian, and compare them to the null hypothesis distribution (0, 1 1/d) just as we did for the basic Gaussian mechanism. The procedure is described in Algorithm 2
The rationale behind this attack is as follows. FL is an optimization procedure in which each client contributes an update each round in which it participates, and each model iterate is a linear combination of all updates received thus far, plus Gaussian noise. Our threat model allows the
"To our knowledge, there is way of confidently inferring that set of samples comes from given distribution, or even that they come from distribution that close the given distribution some metrie. However it gives us some confidence to see that strong goodness-of of fit test cannot rule out the given distribution even with very high number of samples. The low significance level means the test is so sensitive it would he expected to reject even set of truly Gaussian-distributes set of samples 15% of the time. This is more quantitative claim than visually comparing histogram or empirical CDF, is commonly done.
5

---

Published as a conference paper at ICLR 2024
Algorithm 2 Privacy estimation via random canaries
1: Input: Client selection function clients,
n clients (t) + canaries(t)
client training functions Ty, canary selection function canaries. set of canary updates C₁ number of rounds T. initial parameters lo. noise generator Z, l2 clip norm function S. privacy parameter d, server learning rate
9: 0. f 81-1 + 7p + Z(t))/n
10: for all canaries do
11:
+ (c, 0r) 0r)//
12: μ. me
13: E + (NV(0, N (1, );;
2: for I....,T ....,,Too Tooo do
3: P p=
14: function CLiP(a;; k)
4:
for E clients(() do
15: return I min(1, K/ />||==]]
5:
- p+ CL::(T)(()11:: for: i E canaries( do
16: function PROI(E; k)
6:
17: return x ///l//
7:
- p+ ((t)((;;;
attacker to control the updates of a client when it participates, and the ability to inspect the final model. We would argue that a powerful (perhaps optimal, under some assumptions) strategy is to return very large update that is essentially orthogonal to all other updates, and then measure the dot product (or cosine) to the final model. Fortunately, the attacker does not even need any information about the other clients' updates in order to find such orthogonal update: if the dimensionality of the model is high relative to the number of clients, randomly sampled canary updates are nearly orthogonal all the true client updates and also each other.
Unlike many works that only produce correct estimates when clients are sampled uniformly and independently each round, our method makes assumptions on the pattern of client participation. The argument of the preceding paragraph holds whether clients are sampled uniformly at each round, shuffled and processed in batches, or even if they are sampled according to the difficull-to-charattriize de facto pattern of participation of real users in a production system. Our only assumption is that canaries can be inserted according to the same distribution that real clients are. In production settings, a simple and effective strategy would be to designate small fraction of real clients to have their model updates replaced with the canary update whenever they participate. If the participation pattern is such that memorization is easier, for whatever reason, the distribution of canary/final-modee cosines will have a higher mean, leading to higher e estimates.
The task of the adversary is to distinguish between canaries that were inserted during training vs. canaries that were not observed during training, based on observation of the cosine of the angle between the canary and the final model. If the canary was not inserted during training, we know by the argument in the preceding section that the distribution of the cosine will follow (O, 1/d). To model the distribution of observed canary cosines, we approximate the distribution with a Gaussian with the same empirical mean ja and variance 82, Then we report the & computed by comparing two Gaussian distributions as described in Appendix
We stress that our empirical e estimate should not be construed as a formal bound on the worst-case privacy leakage. Rather, low value of can be taken as evidence that an adversary implementing this particular, powerful attack will have a hard time inferring the presence of any given user upon observing the final model. If we suppose that the attack is strong, or even optimal, then we can infer that any attacker will not be able to perform MI successfully, and therefore our is justifiable metric of the true privacy when the final model released. Investigating conditions under which this could be proven would be valuable direction for future work.
Existing analytical bounds on & for DP-SGD assume that all intermediate model updates can be observed by the adversary (Abadi et al. (016)). In cross-device FL., an attacker who controls multiple participating devices could in principle obtain some or all model checkpoints. But we argue there are at least two important cases where the "final-modeloonl"" threat model is realistic. First, one can run DP- FedAvg on centrally collected data in the datacenter to provide a user-level DP guarantee. In this scenario. clients still entrust the server with their data, but intermediate states are ephemeral and only the final privatized model (whether via release of model parameters or black-box access) is made public. Second, there is much recent interest in using Trusted Execution Environments (TEFs)

---

Published as a conference paper at ICLR 2024
Algorithm 3 Privacy estimation via random canaries using all iterates
1: Input: As in Algorithm 2 but with unob-
10:
for all canaries do
served canary updates of and observed ca- nary updates c..
11:
L.. = (c. Pt |||
12:
gi, f)..p)/lpp)
2: for part= 1=
l......,,T do
13: Og t 0 + Tp
3:
p=
4:
for j E clients(t) do
14: for all canaries do
5:
P <ー p (0::( for i canarics(t) do
15: 9. + max, L.,
16:
+ max, gh.
6:
7:
p PROS())))
17: μo, O0 f mean {g 1 (19
8:
n = cliinnsstt] |canaries(t)
18: μl, 01 t mean (g. 1), std((g)
19: E t (W(p,, o (p1,
9:
p - (o Z(t)//n
for further data minimization. For example, using TEEs on server and client, client could prove to the server that they are performing local training as intended without being able to access the model parameters (Mo et al.) 202T). Therefore we believe the final-model-only threat model is realistic and important, and will be of increasing interest in coming years as TEEs become more widely used.
Aside from quantifying the privacy of releasing only the final model, our method allows us to explore how privacy properties are affected by varying aspects of training for which we have no tight formal analysis. As an important example (which we explore in experiments) we consider how the estimate changes if clients constrained to participate fixed number of times.
We also propose a simple extension to our method that allows us to estimate & under the threat model where all model updates are observed. We use as the test statistic the maximum over roundy of the angle between the canary and the model delta at that round. A sudden increase of the angle cosine particular round is good evidence that the canary was present in that round. Unfortunately in this case we can no longer express in closed form the distribution of max-over-rounds cosine of an canary that did not participate in training, because it depends on the trajectory of partially trained models, which is task and model specific. Our solution is to sample a set of unobserved canaries that are never included in model updates, but we still keep track of their cosines with each model delta and finally take the max. We approximate both the distributions of observed and unobserved maximum canary/model-dell cosines using Gaussian distributions and compute the optimal e. The pseudocode for this modified procedure is provided in Algorithm 3 We will see that this method provides estimates of æ close to the analytical bounds under moderate amounts of noise, providing evidence that attack is strong.
EXPERIMENTS
In this section we present the results of experiments estimating the privacy leakage while training a model on parge-scale public federated learning dataset: the stackoverflow word prediction data/model word-based L.TM with 4.1M parameters. We train the model for 2048 rounds with 167 clients per round, where each of the m=341k clients participates in exactly one round, amounting to a single epoch over the data. We use the adaptive clipping method Andrew al. (021). With preliminary manual tuning, server learning rate of 0.56, and momentum of 0.9 on the server for all experiments because this choice gives good performance over a range of levels of DP noise. We use 1k canaries for each set of cosines; experiments with intermediate iterates use 1k observed and 1k unobserved canaries. We fix 8 m I.1, We consider noise multipliers in the range 0.0496 to 0.2317, corresponding to analytical
of Reddi et al. (020 3 The model
selected client learning rate of 1.0,
We present experimental results the image dataset EMNIST in Appendix Code reproduce ex- periments is available at ht/httss://gttata htwptg/t.tbb...//./// com/
www.b...ooggooooleeo googl wtt.eeaerrreeeeeaeeeeeeeeee
one_ one_shot sit__htt__e___ _epe
"The noise multiplier is the ratio of the noise the clip norm. When adaptive clipping is used, the clip norm varies across rounds, and the noise scales proportionally.
7

---

Published as a conference paper at ICLR 2024
Noise
analytical e
-l-lall
-eu-all
Elu
Eeu-final
0
00
6.240
45800
2.88
4.60
0.0496
300
6.238
382
1.11
1.97
0.0986
100
5.05
89.4
0.688
1.18
0.2317
30
0.407
2.693
0.311
0.569
Table 2: Comparing e estimates using all model deltas vs. using the final model only. E is the empirical 95% lower bound from our modified[agieela et al.] (2020) method. For moderate noise, Eest-all is in the ballpark of the analytical providing evidence that the attack is strong and therefore the & estimates are reliable. On the other hand, - is far lower, indicating that when the final model is observed, privacy is better.
E estimates from 300 down to 30 5 We also include experiments with clipping only (noise multiplier 0). Table in Appendix D shows that across the range of noise multipliers, the participation of Ik canaries had no significant impact on model accuracy at most causing a 0. 0.1% absolute decrease.
We also report the method of Jagielski et al. (2020) to the set of cosines. That work uses Clopper-Peareee Pearson upper bounds on the achievable FPR and FNR thresholding classifier to derive a bound on E. We make two changes: following Zanella-Béguelin et al. (002)), we use the tighter and more centered Jeffreys confidence interval for the upper bound on FNR at some threshold a, and we use the exact CDF of the null distribution for the FPR as described in Section 4 We refer to this lower bound Elo. We set a = 0.05 to get a 95%-ccnffiencc bound. This estimate has a maximum posisble value of 6.24 with perfect separation. We include it illustrate that our method does not suffer from this limitation, and to show that our estimate not falsified by the lower bound.
lower bound on that comes from applying a modified version of
We first consider the case where the intermediate updates released described in Algorithm 3 The middle columns of Table the results of these experiments over a range of noise multipliers. For the lower noise multipliers, our method easily separates the cosines of observed vs. unobserved canaries, producing very high estimates all, which are much higher than lower bounds -jol estimated by previous work. This confirms our intuition that intermediate model updates give the adversary significant power to detect the presence of individuals in the data. It also provides evidence that the canary cosine attack is strong, increasing our confidence that the & estimates assuming a weakened adversary that observes only the final model is not a severe underestimate.
The rightmost columns of Table Ssoow the results of restricting the adversary observe only the Now Eest is significantly smaller than when the adversary has access to all intermediary updates. With clipping only, our estimate is 4.60, which is still quite weak from rigorous privacy perspective But with even small amount of noise, approach the high-privacy regime is sufficient prevent most memorization.
final model, as described in Algorithm? 2
1, confirming observations of practitioners that a small amount noise
5.1 EXPERIMENTS WITH MULTIPLE CANARY PRESENTATIONS
Here we highlight the ability of our method to estimate privacy when we vary not only the threat model. but also aspects of the training algorithm that may reasonably be expected to change privacy properties, but for which no tight analysis has been obtained. We consider presenting each canary fixed multiple number of times, modeling the scenario which clients are only allowed check in for training every so often. In practice, client need not participate in every period, but to obtain worst-case estimates, we present the canary in every period.
In Figure I we show kernel density estimation plots of the canary cosine sets. As the number of presentations increases each plot, the distributions become more and more clearly separated.
'This bound comes from assuming the adversary knows on which round a target user participated. It is equal to the privacy loss of the unamplified Gaussian mechanism applied once with no composition. Stronger guarantees might come from assuming shuffling of the clients (Feldman al. 2023 2022. but tight bounds for that case are not known.
AA of 5 means that attacker go from small suspicion that user participated (say, 10%) a very high degree of certainty (94%) (Desfontaines 2018).
8

---

Published as a conference paper at ICLR 2024
1000
Figure I: Density plots of cosine values with four values of noise corresponding to analytical epsilons (oo, 300, 100. 30) and four values of canary repetitions 21, 4, 8). The black curve each plot is the pdf of the null distribution (0, 1/d). With no noise (s 0o), the distributions are easily separable, with increasing separation for more canary repetitions. At higher levels of noise, distributions are less separable, even with several repetitions.
Figure 2: Blue bars are our Eest and red ticks are the E -5nf-coneee lower bound for four values of noise corresponding to analytical epsilons (oo, 300, 100, 30) and four values of canary repetitions (1, 2, 4, 8). Note the difference y-axis scales in each plot. Our estimate of epsilon increases sharply with the number of canary repetitions, confirming that limiting client participation improves privacy.
the other hand as the amount noise increases across the three plots, they converge to null distribution. Also visible on this figure is that the distributions roughly Gaussian-shaped, justifying the Gaussian approximation that is used our estimation method. In Appendix [E we give quantitative evidence for this observation. Finally canary presentations Figure 2 For each noise level, Eest increases dramatically with increasing presentations, confirming our intuition that seeing examples multiple times dramatically reduces privacy. In Appendix we provide analogous experiments on the federated EMNIST dataset, with similar results.
compare Et
Ses with multiple
CONCLUSION
In this work we have introduced a novel method for empirically estimating the privacy loss during training of model with DP-FedAvg. For natural production-sized problems (millions of parameters, hundreds of thousands of clients), produces reasonable privacy estimates during the same single training run used estimate model parameters, without significantly degrading the utility of the model, and does not require any prior knowledge of the task, data or model. The resulting Sest can be interpreted as bounding the degree of confidence that particular strong adversary could have in performing membership inference. It gives reasonable metric for comparing how privacy loss changes between arbitrary variants of client- patenn-artiiiiationn, or other variations of DP-FedAvg for which no method for producing a tight analytical estimate of is known.
In future work we would like to explore how our metric is related to formal bounds on the privacy loss. We would also like to open the door to empirical refutation of our epsilon metric that is, for researchers to attempt to design successful attack on a training mechanism for which our metric nevertheless estimates low value of epsilon. To the extent that are confident such attack exists, we can be assured that our estimate is faithful. We note that this is the case with techniques like the cryptographic hash function SHA-3: although proof exists that inverting SHA-3 is computationally difficult, it is used in high-securing applications because highly motivated security experts have not been able to mount successful inversion attack in the many years of its existence.

---

Published as a conference paper at ICLR 2024
7 ACKNOWLEDGEMENTS
We are extremely grateful to Krishna Pillutla for his detailed review of an early draft of the paper. We also thank the anonymous ICLR reviewers who helped to make proofs more rigorous.
REFERENCES
M. Abadi, A. Chu, I. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and L. Zhang. Deep learning with differential privacy. Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pages 308 018-318, 2016.
T. W. Anderson and D. A. Darling. Asymptotic theory of certain "goodness of fit" criteria based on stochastic processes. The Annals of Mathematical Statistics, 23(2):193 212, 1952. doi: 24.214/aoms/111772292.
URL|tttps: pttteps:/doo0 /tw.////ii/////////////////oo/ org/10. 1214 aoms /
G. Andrew, O. Thakkar, B. McMahan, and S. Ramaswamy. Differentially private learning with adaptive clipping. Advances in Newral Information Processing Systems, 34:17555-1746, 2021.
B. Balle and Y.-. Wang. Improving the gaussian mechanism for differential privacy: Analytical calibration and optimal denoising. In International Conference Machine Learning, pages 394-403. PMLR, 2018.
B. Balle, G. Cherubin, and J. Hayes. Reconstructing training data with informed adversaries. In 2022 IEEE Symposium on Security and Privacy (SP), pages 1138-1156. IEEE, 2022.
J. H. Bell, K. A. Bonawitz, A. Gascón, T. Lepoint, and M. Raykova. Secure single-server aggregation with (poly) logarithmic overhead. In Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, pages 1253-1269, 2020.
K. Bonawitz, Ivanov, B. Kreuter, A. Marcedone, H. B. McMahan, S. Patel, D. Ramage, A. Segal, and K. Seth. Practical secure aggregation for privacy-preservie machine learning. In proceedinggs of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pages 1175- 1191, 2017.
K. Bonawitz, P. Kairouz, B. Mcmahan, and D. Ramage. Federated learning and privacy. Commun. ACM, 65(4):90 97, mar 2022. ISSN 0001-0782, doi: 10.1145/3500240. URL https::////// org/ 20g/10.10 11211115335 10.4111555520000
N. Carlini, F. Tramer, E. Wallace, M. Jagielski, A. Herbert- Voss, K. Lee, A. Roberts, T. Brown, D. Song, U. Erlingsson, Oprea, and C. Raffel. Extracting training data from large language models. In 30th USENIX Security Symposium (USENIX Security 2021), 2021.
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. IEEE Computer Society, doi: 10. 2991099944422422222.2. 00090. URL 00090
https:://oi.. Ttttss///bl..eeeccoottttttet http://p....ecooottteerrreeeeeoe 1ttp:///....1111944411111
C. Choquette Choo, H. MeMahan, K. Rush, and Thakurta. Multi-epoch matrix factorization mechanisms for private machine learning. In International Conference Machine Learning, volume 202, pages 5924-5963, 2023.
S. Denissov, McMahan,
Rush, A. Smith, and A. G. Thakurta. Improved differential privacy for SGD via optimal private linear operators adaptive streams. In A. H. Oh, A. Agarwal, D. Belgrave, and K. Cho, editors, Advances in Neural Information Processing Systems, 2022. URL https://cpenreviier net Fwrrroiiiee 1X
D. Desfontaines. Differential privacy in (a bit) more detail. https://desfontain.. Drivact//dlEeerentiil----ii 09-28.
more dew.aillaee.......eeeeeee..deeee html 2018. Accessed 2023-
Z. Ding. Y. Wang, G. 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.
10

---

Published as a conference paper at ICLR 2024
C. Dwork and A. Roth. The algorithmic foundations of differential privacy. Foundations and Trends(R) in Theoretical Computer Science, 9(3 (f3-4):21-440, 2014. ISSN 1551-305X. doi: 10.1561/0400000042. URL htlphtt://dx www.:/oo...gg....o.. /tt.:////11111110000000000000000
C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. In Conference on Theory of Cryptography, TCC '06, pages 265-2844 New York, NY, USA, 2006.
V. Feldman, A. McMillan, and K. Talwar. Hiding among the clones: A simple and nearly opti- mal analysis of privacy amplification by shuffling. In 2021 IEEE 62nd Annual Symposium Foundations of Computer Science (FOCS), pages 954-964, IEEE, 2022.
V. Feldman, A. McMillan, and K. Talwar. Stronger privacy amplification by shuffling for Rényi and approximate differential privacy. Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 4966-4981. SIAM, 2023.
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.
N. Haim, G. Vardi, Yehudai, michal Irani, and O. Shamir. Reconstructing training data from trained neural networks. In A. H. Oh, A. Agarwal, D. Belgrave, and K. Cho, editors, Advances in Neural Information Processing Systems, 2022. URL httttt::p//ppnttee
net/ forum?
1id=Sxk8Ba SBsekkKK
M. Jagielski, J. Ullman, and Oprea. Auditing differentially private machine learning: How private is private sgd? In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS'20, 20, Red Hook, NY, USA, 2020. Curran Associates Inc. ISBN 9781713829544
M. Jagielski, S. Wu, A. Oprea, Ullman, and R. Geambasu. How to combine membership- inference attacks on multiple updated machine learning models. Proceedings on Privacy Enhancing Technologies, 3:211-232, 2023.
P. Kairouz, S. Oh, and P. Viswanath. The composition theorem for differential privacy. In F. Bach and D. Blei, editors, Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pages 1376-1388 Lille, France, 07-09 Jul 2015. PMLR. URL
m press
Kairouz, B. McMahan, S. Song, O. Thakkar, A. Thakurta, and Z. Xu. Practical and private (deep) learning without sampling shuffling. In International Conference Machine Learning, pages PMLR, 2021a.
P. Kairouz, H. B. McMahan, B. Avent, A. Bellet, M. Bennis, A. N. Bhagoji, K. Bonawitz, Z. Charles, G. Cormode, R. Cummings, et Advances and open problems in federated learning. Foundations and Trends in Machine Learning,
2021b.
S. Li. Concise formulas for the area and volume of hyperspherical cap. Asian Journal of Mathematics & Statistics, 4, 01 2011, doi: 10.3923/ajms.201 1.66.70.
X. Liu and S. Oh. Minimax Optimal Estimation of Approximate Differential Privacy on Neighboring Databases. In Advances Neural Information Processing Systems, volume 32, 2019.
Lu, J. Munoz, M. Fuchs, Т. LeBlond, E. V. Zaresky-Williams, E. Raff, F. Ferraro, and B. Testa. A general framework for auditing differentially private machine learning. In A. H. Oh, A. Agarwal, D. Belgrave, and K. Cho, editors, Advances in Neural Information Processing Systems, 2022. URL h
net Tentt/oorunn Forum? (trumm2.ddAAMM33t.S55.
S. Maddock, A. Sablayrolles. and Stock. Canife: Crafting canaries for empirical privacy measure- ment in federated learning. arXiv preprint ar arXiv:22/0.029//. 2022.
H. B. Mann and A. Wald. On stochastie limit and order relationships. The Annals of Mathematical Staristics, 14(3):217-266, 1943. ISSN 00034851. htth: :/wp:////www../ jstor. wwt.:oogalll..ooo..o stable/ 2235800
11

---

Published as a conference paper at ICLR 2024
B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y. Arcas. Communicationn Effiicien Learning of Deep Networks from Decentralized Data. In A. Singh and Zhu, editors, Proceed- ings of the 20th International Conference Artificial Intelligence and Statistics, volume 54 of Proceedings of Machine Learning Research, pages 1273-1282. PMLR, 20-22 Apr 2017. URL https:://rooee
ngs ml m...ppree press / v54 wwmammmmaaaammmm 7a 1at.mmma.lllllm...m.mmmmmmmmm
H. B. McMahan, D. Ramage, K. Talwar, and Zhang. Learning differentially private recurrent language models. In International Conference on Learning Representations, 2018.
F. Mo, H. Haddadi, K. Katevas, E. Marin, D. Perino, and N. Kourtellis. PPFL: privacy- preseeviig federated learning with trusted execution environments. In Proceedings of the 19th annual international conference on mobile systems, applications, and services, pages 94-108, 2021.
M. Nasr, Songi, A. Thakurta, N. Papemoti, and N. Carlin. Adversary instantiation: Lower bounds for differentially private machine learning. In 2021 IEEE Symposium on Security and Privacy (SP), pages 866-882. IEEE, 2021.
M. Nasr, J. Hayes, T. Steinke, B. Balle, F. Tramèr, M. Jagielski, N. Carlini, and A. Terzis. Tight auditing of differentially private machine learning. In 32nd USENIX Security Symposhum (USENIX Security 23), pages 1631-1648 2023.
K. Pillutla, G. Andrew, P. Kairouz, H. B. McMahan, A. Oprea, and S. Oh. Unleashing the power of randomization in auditing differentially private ML. Advances in Neural Information Processing Systems, 36, 2024.
S. Reddi, Z. Charles, M. Zaheer, Z. Garrett, K. Rush, J. Konečnj, S. Kumar, and H. B. McMahan. Adaptive federated optimization. arXiv preprint arXiv:2003.00299, 2020.
H. Scheffé. A useful convergence theorem for probability distributions. The Annals of Mathematical Statistics, 18(3):434 438, 1947. ISSN 00034851. URL 2235739
URt.tttp://// http:hhtt:////tt jstorr http::/wwww.ooooo.ostttaaaaalaaa
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. IEFE, 2017.
T. Steinke. Composition of differential privacy & privacy amplification by subsampling. arXiv preprint arXiv:2210.00597, 2022.
T. Steinke, M. NasI, and M. Jagielski. Privacy auditing with one (1) training run. Advances in Neural Information Processing Systems, 36, 2024.
Z. Xu, Y. Zhang, G. Andrew, C. A. Choquette-Choo, P. Kairouz, H. B. McMahan, J. Rosenstock, and Y. Zhang. Federated learning of gboard language models with differential privacy. arXiv preprint arXiv:2305.18465. 2023.
Yeom, I. Giacomelli, M. Fredrikson, and S. Jha. Privacy risk in machine learning: Analyzing the connection to overfitting. In 2018 IEEE 31st Computer Security Foundations Symposium (CSF), pages 282. IEEE, 2018
S. B L. Wutschitz, S. Tople, A. Salem, V. Rühle, A. Paverd, M. Naseri, B. Köpf, and D. Jones. Bayesian estimation of differential privacy. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 40624 40636. PMLR, 23-29 Jul 2023.
A ALGORITHM FOR EXACT COMPUTATION OF COMPARING TWO GAUSSIAN DISTRIBUTIONS
In this section we give the details of the computation for estimating E when A(D) and A(D') are both Gaussian-distributedd with different variances. An implementation of this computation is available at
one http://.ww...aaapaaaaaa.aaaaaaaa 1 1b.py
12

---

Published as a conference paper at ICLR 2024
Let the distribution under A(D) be P1 of) and the distribution under A(D)) be
P2 N(u, oB) with densities Pi and Pa respectively. Define (P) log (a
(a) Now
Z1 = fRaII (X1) with X1 ~ P1 is the privacy loss random variable. Symmetrically define
Z2 = PPAIIP, (x2) with X2 ~ P2.
From Steinke 2022 Prop. we have that (e, 6)-DP implies
Pr 71
e² Pr 72 S d and Pr (22 > e) - Pr >- 5
Now we can compute
Pi (xx
(P) log
p2(x)
02 exp
1
(x k2)
(x - 112)
log
2
of
02
(x - 122 )
(x - 111 )
= llog 02 - log 01
20
20
ax²
+ bit +
where
a
2
0
2
11
112
of
o2
2
2
U12
111
and c=
+ log 02 - log 01
To compute Pr [Z1 > c). we need Pr [aX? + bX, + (c a) > with X1 ~ P1. To do so, divide the range of X, into intervals according to the zeros of R(x)) = ox= + be + (c 8). For example, if R has roots r1 < r2 and a is positive, we compute Pr [71 > e] Pr < ri + Pr [X1 > r2). using the CDF of the Normal distribution. This requires considering few cases, depending on the sign of a and the sign of the determinant 6² 4a(c - e). Now note that fralr; -ffr so
Pr[- -2 > E| = Pr Pr [-frg] (X2) > E| = Pr(aX3 + bX2 + (c =c 0).
So the two events we are interested in (Z1 > and -22 > 8) are the same, only when we compute their probabilities according to Pi vs. P2 we use different values for μ and o.
For numerical stability, the probabilities should be computed in the log domain. So we get
log 8 2 log (Pr 7 > E] e Pr[ Zz > e))
= log Z > e| + log (1 exp(e + log Pr( Zz > s] - log Pr(Zi > s)))
Note it can happen that Prizi > e| < Pr > 5| in which case the corresponding bound is invalid. A final trick we suggest for numerical stability is i ~ ~N(,,a") to use Pr(X < pit,o²) in place of Pr(X > t; o²).
Now to determine & at a given target one can perform a line search over a to find the value that matches.
B PROOFS OF RESULTS FROM THE MAIN TEXT
Preliminaries. First we must introduce an elementary result about the measure of a hyperspherical cap. In Rd, the area ((d- me of the hypersphere of radius is (Li 2011
2/2
Ad(r) = r(d/2)
13

---

Published as a conference paper at ICLR 2024
Define the unit hyperspherical cap of maximal angle 0 [0. w] to be the set far : |||||| and 21 2 cos f), and let Ma( denote its area. From (Li 2011) we have
/. 1 () dø,
Ma(0)
from which it follows from the fundamental theorem of calculus that
2T 7
Ma(0) = - = - r( sin d- 0. d0
(2)
Proposition 3.1. For d E N, d 2 2, let c be sampled uniformly from S and let TO = (c, / E
[-1, be the cosine similarity between and some arbitrary independent nonzero vector v. Then, the probability function of Ta is
( fa(t) r I( (1 11-
Proof. Due to spherical symmetry, without loss of generality, we can take v to be constant and equal the first standard basis vector e1. First we describe the distribution of the angle [0, т| between e and eg. then change variables to get the distribution of its cosine Td. Using (2) and normalizing by the total area of the sphere (1), the density of the angle is
ea = (Aa(1)) d
Ma(0) de
2T #
2T 7
sin d-2 dind-2
I( 2
r(a)
sin d- 8.
Now change variables to find the density of the angle cosine Ta = cos(0) E [-1, 1]: daa (arcccsss
d
fa(t)
arccos(f)
di
r(
sin (arccos t) d-2
d- r(
v1 12
2
I(
(vI 82) d-2
1 V
V1 - 12
((4)
-
T(
Proposition 3.2. Let Ta be the random variable of Proposition 3.1 in Rdd Then TaV converges in
distribution to (0, 1) as d + co, ie.. VA E R, lim P(ra S a/Va) = -P) & A).
Proof. The probability density function of T.V is r(
MRd (1 /2)
for |t| S Vd:
fa(t)
for |t| > Vd.
For any I, for large enough d, 1 5 Vil so
r($)
lim fa(t)
lim d=
lim (1 (1- (1- d=000
lim (1 e/d) -3 d=000
d=000
I'( d=1 V
1
1//2 1,
V2T
14

---

Published as a conference paper at ICLR 2024
where we have used the fact that states that pointwise convergence of the density function implies convergence in distribution (Scheffé 1947).
T( - ~ vd/2. The result follows by Scheffe's theorem, which
r(#)
Lemma B.1. Ta is distributed according to the cosine angle distribution described in Proposi- tion 3.1 then Var[ra] 1/d.
Proof. Let c = (ci..... ca) be uniform on gd-1 Then = (c, E1} has the required distribution.
Ejc,] is zero, so we are interested in Var[cı] = E [cf]- Since Σ. c = 1, we have that [
Ece] = 1. But all of the e₂ have the same distribution, so E' [c]]] 1/d.
Lemma B.2. If is sampled uniformly from S6-1, then for any y. E Rd, we have that Elic, (c, = (ar, s)/d.
Proof. Lete= (cI,..., ..)). From the proof of Lemma B.1 we have that for all i, E E[e]] = 1/d. is also easy to see that for all # j. [[[,,y]] = O, since by symmetry E|c,c,] = B[(-c;)c = -[ccc]] Therefore.
Σ 2 Blae,] = Σ Izlhi 1
(x.y) v)
Blic (c,
d
d
Theorem 3.3. For d N. For some m (which may grow with d). let ad ... Zdm. such that ||aall = =oVa) where Xa = ==== Waj Let k = o(d), but k = w(1), and for i E [b], let cai be sampled i.i.d. uniformly from S4-1, Let 7 N(O; For E R+, define the mechanism Write the empirical
result pa = Xa + Σi=1 Cds + oZa and the cosine values gai = sedssee)
Teall
mean of the cosines jaa- E Et Idi and the empirical variance 03 # Et=( jua Let Ea c(N(0,1//) || 0)) Then Es converges in probability to the constant (")(0,)))I(((10)))
Proof. We will show that as d - co, we have that vdpa 24 1/0 and dō3 _", 1. Note that E (ON 1)IIA((Vppa dōž); 8), since this is just a rescaling of both distributions by a factor of 1/vd, which does not change E. Therefore by the Mann-Wai theorem (Mann and Wald 1943). the estimate é. converges in probability to e (O 1) ([1/a, d). Now these two distributions are just a scaling of A(D) ~ A'(0, o²) and A(D') ~ ~N(1 by a factor of 1/a. This proves our claim.
For the remainder of the proof, we will omit the subscript d on Xd, Cdis Zds and pa. All summations, such E, Ct. should be understood going from to k.
Rewrite
Vdjaa= - Vi
Σ
(c. lelll
[Pll] Vd
1
1
Ke
We will show that "ell P 0², while & E((rs))
24 1.
We will need to consider the following dot products: (X,
(X.c) ca) (for all 1), (X, (ci, Z) (for all i),
(cs, (z) (for all < f), and (Z, = - All but Z are zero-mean, and they are pairwise uncorrelated 7 It follows that (c:, p) and (cj, p) are uncorrelated for all + j. Note that (c,, Z) ~ A/ 1), and [ct, is distributed like Ta (and (x)c)) is distributed like [x](Ta). Finally, note that (c,, 2)a is Chi-squared distributed with single degree of freedom while (Z, Z) ||2||2 is Chi-squared distributed with d degrees of freedom.
TTo see that (X, Z) and || 2 are uncorrelated, write [[ []]]]
[e || E((X, 2}}, since the Z: are independent draws from // 1).
|X|
||] [B[ D R. 71 z
15

---

Published as a conference paper at ICLR 2024
Now can proceed,
|pl d
1
X + Σ a a oZ, X Ea+0z)
1
(1x1+ + o²
d
ool-
The variance decomposes:
|||l3
1
( x Σ La+ozi X _ a 5a+t22
Var
Var
d²
1
Σ, Var 12xx, [1) + Var oZ)] + Eiss Var (ar(2(c),)))
d²
E. Var 2 o [i] + Var Var Z, oZ)
1
| + 4- X|| + 2k(k - 1)
d + 4ko² 20'd
de
o(1.
Taken together, these imply that Ielll
va Now reusing many of the same calculations,
E
p)
Σ
(c,, X Σ oj + oZ)
k
k
Bl(cg, X) + Σ Bl(a, + Σ Blles zY1
T
(0+ k +)=
and
Var
Σ (c)
Var Var[(c;, + Σ
Var Var + Varl((c 2)]
k
222
1
|||
b: -
o²
k
o(1),
which together imply that Ex(rs p) 2 1.
Now consider
( 9i )²)
do3 d
1
Σ
96
b
d
Σ
(c (1
((eeev))) (c)
||a|
k
16

---

Published as a conference paper at ICLR 2024
We already have that be sufficient to show 1
d P,
and Ex(c, p) _ so demonstrate that d _2, 1. it will
|
2
k
Σ,
p)
Ps 1+0² 0². To that end:
8:
X) + Elench + (()00))))) 21
E
Σ
p)?
Σ
E
k
Σ
+ EB((ch eg) + +B([s,
||x
+ (1+
k -
h Σ
d + to²
d
= =1 + o(1).
Finally, to show that Var
(ct, - =o(1), we will show that
E
(
1
Σ
(ct, ())
E
1
E (cr (c
+1(1)
k
k
Rewrite
E
Σ
(cis 013)
=
E ()
i
3 if
BlGg, A)Cc, Bycc, CY(,, A,B.C.D
22
where A, B,B,C,D range independently over the terms of pt {X, (I,,,, Ck2 o Z}. Now if (c, ej
{A, B, D) = 0. then defining V-i = fci..... Ck2 Z} fca, oj and using Lemma B.2 E[(c, (y, B) (e, D)] [[[[(cs, A) (e Cy Dy
[E[E((C, (e. B)[V-i)) B)]B Cye, -y
LE[(A, BY (C, DMD /d2
IE[(A, ByJ EKC, Ddf
= TE[(c,, A) (cs. B)) BlG,, Cyy, D))
If we allow [f,, , n (A, > 0, there is only one case where the decomposition does not hold: if the fourth central moment of the standard Gaussian that vdlci, e5) converges to by Proposition 3.2 whereas E [cc, ,,, 1/d². Now we can conclude:
Cj and C D c, (and + j) we have (() 3/d (considering
(G. p)
1
Σ
Σ
Kl,, A) B) D),, k d
A,B.C,D
Blies AYG,, AXG,, + o(1)
A.B
2
E
Σ
(cn (cr,p) p)?
Note on the rate growth of X₂ in Theorem 3.3 Theorem 3.3 requires that ||xal| o(vd).
This follows from any of several natural sufficient conditions:
the data Æaj are bounded and m = o(v)).
the data zşj are i.i.d. from some isotropic distribution with finite variance and m o(d),
there exists some constant C' E R with ||a I C.
This last condition is reasonable if the my are updates during some well-behaved learning process.
17

---

Published as a conference paper at ICLR 2024
accuracy Ik canaries
noise multiplier
baseline accuracy
analytical
added
25.3%
25.3%
0.064
194
24.0%
23.9%
0.102
93.8
23.1%
23.1%
0.184
40.2
21.5%
21.5%
0.234
28.9
20.6%
20.5%
Table Comparison of accuracy of word prediction models trained with and without the presence of 1000 random canary clients. Inserting 1000 random clients among the 341k real clients in the Stackoverflow word prediction task has almost negligible effect on model performance.
C ASYMPTOTIC GAUSSIANITY OF COSINE STATISTICS IN ALGORITHM
Algorithm specifies that we should fit the cosine statisties &i Gaussian distribution according to their empirical mean and variance. Empirical results, including visual comparison of the histogram Gaussian distribution function, and Maderson-Darlingg tests as we ran Appendix for the statistics of Algorithm 2 indicate that the empirical distribution of the cosine statistics in Algorithm | are approximately Gaussian in high dimensions. However is not immediately clear how to prove this. Note that it would not be sufficient to show that each cosine sample y: is marginally Gaussian, which would relatively easy. we proved only that much, it could for example be the case that all of the samples 9i always identical to each other each run (but Gaussian distributed across runs) so that the empirical variance on any run is zero. Then our method would be broken. We would need stronger statement about their joint distribution, such that the joint distribution converges to an isotropic Gaussian. While we believe this to the case, we emphasize that is not essential that the cosine statistics yj actually be independently Gaussian distributed in order for Algorithm| to be correct. Theorem 3.3 proves that we asymptotically recover the correct & by fitting them to Gaussian, regardless of their true distribution.
D IMPACT OF CANARIES ON ACCURACY
One might worry that the adding random canary clients could impact model utility. In experiments on Stackoverflow, with 341k real clients, the addition of 1000 canary clients had negligible impact on model accuracy. The change in performance is shown in Table We note that many practical FL problems have even more clients than this: see for example Xu et al. (2023) which trains language models using DP-FL variety of languages, almost of all of which have more than 3M clients each ten times more than in our experiments.
E GAUSSIANITY OF COSINE STATISTICS FROM EXPERIMENTS
The density plots of the cosine statistics from the experiments in section 5.1 shown in Figure appear Gaussian-shaped To our knowledge, there no way of confidently inferring that set of samples comes from given distribution, even that they come from a distribution that is close the given distribution in some metric. To quantify the error of our approximation of the cosine statistics with Gaussian distribution, Table (nderson and Darling 1952). It gives us some confidence to see that a strong goodness-of test cannot rule out that the distributions are Gaussian. This is more quantitative claim than visually comparing the density.
apply the Anderson Anderson-Darling test to each set of cosines in
F SUPPLEMENTARY EXPERIMENTAL RESULTS ON EMNIST DATASET
In the main paper we presented results on the Stackoverflow federated word prediction task. Here present similar results the EMNIST character recognition dataset. It contains 814k characters written by 3383 users. The model a CNN with 1.2M parameters. The users are shuffled and we train for five epochs with 34 clients per round. The optimizers client and server are both SGD,
18

---

Published as a conference paper at ICLR 2024
Noise
1 rep
2 reps
reps
reps
10 reps
0
0.464
0.590
0.396
0.407
0.196
1010
0.976
0.422
0.340
0.432
0.116
0.2344
0.326
0.157
0.347
0.951
0.401
Table 4: Maderson-Darlingg test statistics for each set of canary-cosine samples from the experiments in section 5.1 The test rejects at a 1% significance level if the statistic is greater than 1.088, and rejects at 15% significance if the statistic is greater than 0.574. If all 15 (independent) distributions were Gaussian, the probability of observing three or more values with test statistic greater than 0.574 would be 68%, so we cannot reject the null hypothesis that they are, indeed, Gaussian.
Noise
analytical E
Elo-all
Eest-all
Ejo Jo-final
Eest see-final
0.0
30
6.25
48300
3.86
5.72
0.16
33.8
2.87
17.9
1.01
1.20
0.18
28.1
2.32
12.0
0.788
1.15
0.195
24.8
2.02
8.88
0.723
1.08
0.25
16.9
0.896
3.86
0.550
0.818
0.315
12.0
0.315
1.50
0.216
0.737
Table 5: Comparing estimates using all model deltas using the final model only, Ej is the empirical 95% lower bound from our modified Jagielski et al. [2020] method. The high values of Eest-all indicate that membership inference easy when the attacker has access to all iterates. On the other hand, when only the final model is observed, fea-final is far lower.
with learning rates 0.031 and 1.0 respectively, and momentum 0.9 on the server. The client batch size is 16.
Table SJshows the empirical epsilon estimates using either model iterates or only the final model. As with Stackoverflow next word prediction, using all iterates and low amount of noise gives us estimates close to the analytical upper bound, while using only the final model gives a much smaller estimate.
Figure 3 demonstrates effect of increasing the number canary repetitions for EMNIST. The results are qualitatively similar to the case of Stackoverflow.
G EMPIRICAL COMPARISON WITH CANIFE
As discussed in the main text, our method is significantly more general than the CANIFE method of Maddock al. 2002). CANIFE periodically audits individual rounds get per-round é, estimates the noise for the round o, by inverting the computation of e for the Gaussian mechanism, and uses
25
m94
Figure 3: Blue bars are our and red ticks are the E 95%-confidence lower bound for three noise multipliers (0.16, 0.18. 0.15) and four numbers of canary repetitions. Our estimate of epsilon increases sharply with the number of canary repetitions, confirming that limiting client participation improves privacy.
19

---

Published as a conference paper at ICLR 2024
CANIFE 0.88 + 0.12
Eb 1.82 = 0.46
ours
analytical E
6.8 + 1.1
34.5
Table 6: Mean and standard deviation over 50 runs of three estimates, and analytical bound.
standard composition theorems to determine final cumulative epsilon. Therefore the estimate will be inaccurate if the assumptions of those composition theorems do not strictly hold, for example, clients are not sampled uniformly and independently at each round, or the noise is not in fact isotropic Gaussian and independent across rounds. In contrast, our method will detect if any unanticipated aspect of training causes some canaries to have more influence on the final model in terms of higher canary/model dot product, leading in turn to higher & estimates, Also CANIFE'S s method of crafting canaries is model/dataset specific, and computationally expensive.
is still interesting to see how the methods compare the limited setting where CANIFE's assump- tions do hold. Unfortunately comparison of two "estimates" is not straightforward when there is no solid ground truth. In this case, we do not have any way to determine the "true" E, even inefficiently, because doing so would require designing a provably optimal attack. However, we can use strong attack to determine a lower bound on & directly from Eq. (T. If the lower bound exceeds CANIFE'S e, then we know it is an underestimate.
We trained a two-layer feedforward network on the fashion MNIST dataset. Following experiments in Maddock et al. (2022), we used a canary design pool size of 512, took 2500 canary optimization steps to find a canary example optimizing pixels and soft label, ran auditing every 100 rounds with 100 attack scores on each auditing round. We trained with a clip norm of 1.0 and noise multiplier of 0.2 for one epoch with a batch size of 128, which corresponds to an analytical E of 34.5.
To compute lower bound, we trained with 1000 inserted gradient canaries sampled from the unit sphere. We computed attack statistics by taking the maximum over steps of the cosine of the canary to the model delta for the step. just as in Algorithm Only instead of fitting them to a Gaussian to produce an estimate, we compute a lower bound on by bounding the FPR and FNR of the attack as in Jagielski et al. Following Jeffreys confidence interval.
et al. (2023) we use the tighter and more centered
The results are shown in Table D CANIFE'S e of 0.88 is somewhat lower than the lower bound of 1.82, while ours is significantly higher, at 6.8. We still cannot rule out that our method is not overestimating e, but at least we can say that it is in the plausible (but wide) range [1.82, 34.5] while CANIFE's is not.
There are several reasons why CANIFE might be underestimating E. Although the authors bill the method "measurement" of e, not lower bound, nevertheless, it uses lower bound the per-round & to estimate the per-round ar- Thus, it has a built-in bias toward lower e, and there is a maximum it cannot exceed simply due the finite sample size. CANIFE also searches for canary example whose gradient is nearly orthogonal to a held-out set of data (not necessarily to the actual batch being audited). Our method uses random gradient which is provably nearly orthogonal the other gradients in the batch with high probability, leading to stronger attack.
H COMPARISON OF ASSUMPTIONS AND REQUIREMENTS OF EMPIRICAL PRIVACY ESTIMATION METHODS
As discussed in Section 2 related work in privacy auditinglestimation relies on various assumptions on the auditor's knowledge and capability. Here we summarize the major differences.
The standard assumption in auditing centralized private training algorithm is a black-box setting where the auditor only gets to control the training data and observes the final model output. In practice, many private training algorithms guarantee privacy under releasing all the intermediate model checkpoints. One can hope to improve the estimate of privacy by using those checkpoints as in (Jagielski et al. 2023). If the auditor can use information about how the minibatch sequence is drawn and the distribution of the privacy noise, which is equivalent to assuming that the auditor controls the privacy noise and the minibatch, one can further improve the estimates.
20

---

Published as a conference paper at ICLR 2024
auditor controls
auditor receives
Jagielski al.
(020)
train data
final model
Zancila Begueli
2023
train data
final model
Central
Pillutla ct al.
2024)
train data
final model
Steinke al
2024)
train data
final model
Jagielski 2023
train data
intermediate models
Nast et al. (2023)
train data, privacy noise, minibatch
intermediate models
Algorithm
client model update
final model intermediate models intermediate models
Algorithm
client model update
CANIFE Maddock
2022
client sample, privacy noise, minibatch
Table 7: Assumptions of different auditing approaches from the literature. For each paper, state the most relaxed condition the technique can be applied to, since they can generalized in straightforward manner to scenarios with more strict assumptions the auditor's control and observation. Within each category of (central training, federated learning]. the lists are ordered from least most strict assumptions.
Empirical at quantile, 0.049
Empirical quantile, 0=0.988
2.6
1/1000
10/100
1/1000
10/100
1.8
2.4
1.6
empirical
empiric
2.0
1.2
1.8
1.0
1.6
1.4
0.8
0.1
Figure 4: Quantiles of é over fifty experiments using either with 1000 canaries ten with 100 canaries each. For both noise multipliers, the distributions are very close.
In the federated learning scenario, assume canary client can return any model update. Note that while CANIFE only controls the sample the canary client and not the model update directly, CANIFE utilises the Renyi-DP accountant with Poisson subsampling implemented via the Opacus library, which is equivalent to the auditor fully controlling the sequence of minibatches (cohorts in FL terminology). Further, the privacy noise is assumed to be independent spherical Gaussian, which is equivalent to the auditor fully controlling the noise.
Table 7 compares the assumptions of different auditing approaches from the literature.
EXPERIMENTS COMPARING WHEN MULTIPLE RUNS ARE USED
In the limit of high model dimensionality, canaries are essentially mutually orthogonal, and therefore they will interfere minimally with each other's cosines to the model. In this section we give evidence that even in the range of model dimensionalities explored in our experiments, including many canaries in one run does not significantly perturb the estimated epsilon values. Ideally we would train 1000 models each with one canary to collect a set of truly independent statistics. However this is infeasible. particularly if we want to perform the entire process multiple times to obtain confidence intervals. Instead, we reduce the number of canaries per run by factor of ten and train ten independent models to collect total of 1000 canary cosine statistics from which to estimate We repeated the experiment 50 times for two different noise multipliers, which still amounts to training a total of 1000 models. (Ten runs, two settings, fifty repetitions.)
The results on the stackoverflow dataset with the same setup as in Section 5 are shown in Figure 4 We report the 0.1, 0.3, 0.5, 0.7 and 0.9 quantile of the distribution of over 50 experiments. For both noise multipliers, the distributions are quite close. Our epsilon estimates do not seem to vary significantly even the number of canaries per is changed by order of magnitude.
21


Reviews:
[{"review_id": "iacTaqQ7Ug", "reviewer": "Reviewer_LDHu", "summary": "This paper proposes an approach for auditing the privacy of differentially-private learning algorithm in the context of federated learning such as DP-FedAvg. One of the benefits of the approach is that it is « one-shot » in the sense that it can be used at the same time as the model is learnt, without needing any retraining. It has also the advantage of being model agnostic.", "questions": "It would be great if the authors could conduct additional experiments with a lower number of canaries as well as lower values of epsilon to be able to characterize how well the proposed method would fare in these situations.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The introduction clearly introduces the context of federated learning and motivates the need to develop empirical estimation methods to be able to audit the privacy provided by a differentially-private learning algorithm. The main challenges that need to be address to realize this are also clearly discussed. Overall, the paper is well-written and easy to follow. \n\nThe proposed approach has clear benefits over previous approaches, in the sense that it does not require retraining of the system or the use of well-crafted canaries. A comparison is also performed with CANIFE, which is one of the state-of-the-art method for privacy auditing. Overall, the obtained results demonstrate that the proposed method is promising in providing more tight privacy estimates.", "weaknesses": "The example analyzed in Table 1 assumes a high dimension as well as a large number of canaries, which is not particularly realistic. The authors should provide similar analysis for lower values of d and k. Similarly, in the experiments conducted the number of canaries used is quite large, which is likely to have an impact on the model utility. Thus, the authors should also reports the accuracy obtained for the model. In contrast, the values of epsilon used are very high and additional experiments should be performed with values of epsilon such as 0.1, 1, 5 and 10. Finally, experiments with a varying number of clients should also be conducted.\n\nThe difference between user-level and example-level differential privacy should be discussed and defined more clearly within the context of federated learning. For instance, how would the attack framework be impact by the change of definition, in particular with respect to the guarantees measured.\n\nA small typo :\n-« the choice gives » -> « this choice gives »", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QTJmiDd5dp", "reviewer": "Reviewer_zCeQ", "summary": "This work proposes a one-shot empirical privacy estimation method for DP-FedAvg. Instead of choosing canary examples, the authors choose canary clients that releases randomly generated updates to the system. The idea is then to measure the cosine similarity between the overall updates and random updates to determine the effect of canary clients in the overall system. Then using the similarity they determine the empirical privacy using the final model.", "questions": "- I could not see any dependence on canary clients- true clients ratio in your results. Why is there not a dependence on $k/m$ in Theorem 1-3? What are the effects of this ratio empirically and theoretically?\n- In Table 2 what is the goal of comparing to $\\epsilon_{lo}$, and what is the conclusion?\n- I think for a setting in experiments you should also vary the dimensionality of the model and obtain a empirical privacy-dimensionality relationship (by keeping analytical one constant). \n- What is the conclusion of Appendix F? Even if your method is close to the analytical method, do you think that is enough evidence to say that it is a better method? I'm curious if there are any other ways to make a comparison between two methods (such as using Canife in the warm-up experiment). \n- How could one extend this method to other privacy mechanisms other than Gaussian?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper is well-written and easy to follow. Introduction and motivation of the method is clearly communicated. \n- Consideration of estimation of $\\epsilon$ for Gaussian mechanism is spot on, since in that case authors are able to prove that the estimation becomes correct asymptotically (in d).\n- Experiments with multiple datasets and architectures are presented.", "weaknesses": "- Using canary clients seems more inefficient compared to using canary examples. More resource allocation might be needed. \n- In the paper it is suggested that \n\"In production settings, a simple and effective strategy would be to designate a small fraction of real clients to have their model updates replaced with the canary update whenever they participate.\"\nbut this would destroy the representation of such clients and problematic, especially, in data heterogenous settings. It would also result in fairness problems. \n- It is hard to interpret the provided empirical comparison with CANIFE. Other than the assumptions for CANIFE, it is not clear to me how this method is better. \n- The authors claim that their method is agnostic to architecture knowledge, but aren't the $c_j$ are of same dimension as the architecture? Hence would not designing such canaries would require architecture knowledge?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "My8ST7abN0", "reviewer": "Reviewer_ZyjW", "summary": "The paper proposes a new method to empirically estimate the privacy loss of an algorithm, targeted at federated learning. The method can estimate the privacy loss from just one run of the algorithm, which makes it easy to apply. This is done by randomly sampling canary vectors, which are presented to the central aggregator as regular updates. The cosine similarity between each of the canaries and the output of the audited algorithm is then used as a test statistic to infer whether the canary was in the training set or not. The test statistic's distribution, both with or without the canaries, can be approximated with simple Gaussians, as the canaries are likely to be orthogonal to each other and the actual update when the space is high-dimensional. The Gaussian approximations are justified with asymptotic theorems, and the whole method is evaluated on several experiments.", "questions": "- Is the distribution of the test statistic in Theorem 3.3 (asymptotically) Gaussian?\n- What are the upper bounds for the $\\epsilon$ confidence intervals in Table 2? It looks like the intervals are huge in the -all columns.\n- Which plots correspond to which canary levels in Figure 1 and which epsilons in Figure 2? Adding the canary levels and epsilons to the plots, for example in subplot titles, would make the figures much easier to read.\n- Is it possible to use your method to audit standard DP-SGD? If so, how does the method compare to other auditing methods? For example, do the other methods require more than one training run?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper is very well-written and easy to understand. The proposed method fairly simple, so it should be easy to implement, and potentially to extend to other settings. The main idea of randomly sampling canaries that are orthogonal with everything else with high probability is novel to my knowledge. Being able to estimate the privacy loss in a single training run, with minimal effect on the target model's accuracy, makes the method fairly practical.", "weaknesses": "The analytical privacy bound doesn't seem like a good \"ground truth\" for the comparison with CANIFE, as the analytical bound is expected to be much larger than necessary. The best $\\epsilon$ to return would be the upper bound that any membership inference attack could achieve, which is of course not known. It is possible that your method is simply overestimating the best $\\epsilon$, and is closer to the analytical because of that, and not because it is better at estimating the best $\\epsilon$ than CANIFE. This does not seem a too remote of a possibility, as if your result was accurate, it would imply that CANIFE grossly underestimated the $\\epsilon$, and simply doesn't work in the setting.\n\nA better \"ground truth\" would be an $\\epsilon$ lower bound obtained from the TPR and FPR of some strong membership inference attack. It might be possible to use your method as this attack by thresholding the cosine test statistics $g_i$, and estimating the TPRs and FPRs that different thresholds give empirically.\n\nThe proofs are missing some details, which makes them harder to understand and check than necessary. In the proof of Theorem 3.1, what is the value of the measure $A_d(\\theta)$, and how is it derived from the $(d-2)$ measure of its boundary? In the proof of Theorem 3.2, $t$ is not defined. You should also name the theorem that allows you to conclude convergence in distribution from pointwise convergence of the density function, and you should explicitly account for the fact that the density of $t$ is 0 outside $[-\\sqrt{d}, \\sqrt{d}]$.\n\nThese two issues are the main reason for my score, and I will increase the score if they are addressed.\n\nRegarding the challenge to come up with an attack that breaks your method, I can come up with two scenarios where this is likely to happen. The first is not using a cryptographically secure random number generator to generate the Gaussian noise, which would allow an attacker to remove the noise if they can break the insecure RNG. The second is an attack based on finite-precision issues with floating point numbers (see Mironov 2012 and Holohan and Braghin 2021), if the noise is not sampled with defenses against these in place. I don't think your method would detect these, as it is only looking at the noise as a real number, and detecting either scenario seems to require looking at the noise as a finite-precision float. Of course, your method is not designed to detect anything like these in the first place, and I don't think any of alternatives are either, so this is not a large limitation, but it should still be mentioned.\n\nReferences:\n- N. Holohan, S. Braghin \"Secure random sampling in differential privacy\" Computer Security – ESORICS 2021\n- I. Mironov \"On significance of the least significant bits for differential privacy\" ACM Conference on Computer and Communications Security 2012\n\nMinor comments:\n- The Anderson-Darling test should be cited.\n- The assumption that $n = o(d)$ should be stated in Theorem 3.3, not just as a footnote.\n- Font size in Figures 1 and 2 are too small.\n- Table 6 would be much easier to read as a plot of the quantiles, which would also allow showing much more than 5 quantiles.\n- Specifying the exact CNN and LSTM architectures in the experiments would be good for reproducibility, as the code is not included in the submission.\n- Using \\left and \\right on the curly braces in Equation (1) would make the equation easier to read.\n\nComments on references:\n- Feldman et al. (2021) URL points to arXiv, not the conference submission\n- Capitalisation in some paper titles, for examples \"rényi\" in Feldman et al. (2023)\n- arXiv papers have inconsistent format, for example compare Maddock et al. (2022) and Pillutla et al. (2023)\n- Steinke (2022) is missing the publication forum\n- Zanella-Beguelin et al. (2022) and (2023) are the same paper", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (oral)