A Randomized Approach to Tight Privacy Accounting
Authors: Jiachen T. Wang
Saeed Mahloujifar
Tong Wu
Ruoxi Jia
Prateek Mittal
Venue: NeurIPS 2023 poster (2023)
Keywords: Differential Privacy; Privacy Accounting
TL;DR: We developed a new differential privacy paradigm which enables the safe use of privacy parameter estimate.

Abstract: Bounding privacy leakage over compositions, i.e., privacy accounting, is a key challenge in differential privacy (DP). However, the privacy parameter ($\varepsilon$ or $\delta$) is often easy to estimate but hard to bound. In this paper, we propose a new differential privacy paradigm called estimate-verify-release (EVR), which tackles the challenges of providing a strict upper bound for the privacy parameter in DP compositions by converting an *estimate* of privacy parameter into a formal guarantee. The EVR paradigm first verifies whether the mechanism meets the *estimated* privacy guarantee, and then releases the query output based on the verification result. The core component of the EVR is privacy verification. We develop a randomized privacy verifier using Monte Carlo (MC) technique. Furthermore, we propose an MC-based DP accountant that outperforms existing DP accounting techniques in terms of accuracy and efficiency. MC-based DP verifier and accountant is applicable to an important and commonly used class of DP algorithms, including the famous DP-SGD. An empirical evaluation shows the proposed EVR paradigm improves the utility-privacy tradeoff for privacy-preserving machine learning.

A Randomized Approach to Tight Privacy Accounting
Jiachen T. Wang Princeton University ti sianhaovagg@princttoor edu
Saeed Mahloujifar Princeton University sf sfar@princeton. edu
Tong Wu
Princeton University
tongsu@princeton.edd
Ruoxi Jia Virginia Tech ruoxijia@vt. edu
Prateek Mittal
Princeton University pmittall@pinneton.cc
Abstract
Bounding privacy leakage over compositions, i.e., privacy accounting, is key chal- lenge in differential privacy (DP). However, the privaey parameter or d) is often easy to estimate but hard to bound. In this paper, we propose new differential pri- vacy paradigm called estimate-verify-ee of providing a strict upper bound for the privacy parameter in DP compositions by converting an estimate of privacy parameter into formal guarantee. The EVR paradigm first verifies whether the mechanism meets the estimated privacy guaran- tee, and then releases the query output based on the verification result. The core component of the EVR is privacy verification. We develop randomized privacy verifier using Monte Carlo (MC) technique. Furthermore, we propose an MC-based DP accountant that outperforms existing DP accounting techniques in terms of accuracy and efficiency. MC-based DP verifier and accountant is applicable important and commonly used class of DP algorithms, including the famous DP-SGD. An empirical evaluation shows the proposed EVR paradigm improves the dullity-prvage tradeoff for
(EVR), which tackles the challenges
machine learning.
Introduction
The concern of privacy is a major obstacle to deploying machine learning (ML) applications. In response, ML algorithms with differential privacy (DP) guarantees have been proposed and developed. For privacy-preserving ML algorithms, DP mechanisms are often repeatedly applied to private training data. For instance, when training deep learning models using DP-SGD [1]. it is often necessary to execute sub-sampled Gaussian mechanisms on the private training data thousands of times.
A major challenge in machine learning with differential privacy is privacy accounting, i.e., mea- suring the privacy loss of the composition of DP mechanisms. privacy accountant takes a list of mechanisms, and returns the privacy parameter (e and ō) for the composition of those mechanisms. Specifically, privacy accountant is given a target and finds the smallest achievable such that the composed mechanism M is (e, DD (we can also fix 8 and find :). We use (M)(E) to denote the smallest achievable å given E, which is often referred to as optimal privacy curve the literature.
Training deep learning models with DP-SGD is essentially the adaptive composition for thousands of sub-sampled Gaussian Mechanisms. Moment Accountant (MA) a pioneer solution for privacy loss calculation in differentially private deep learning
[[]. However, MA does not provide the optimal 6 (E) in general 44. This motivates the development of more advanced privacy accounting techniques that outperforms MA. Two major lines of such works are based on Fast Fourier Transform Both techniques can provide an estimate
(FFT) (e.g., [99 and Central Limit Theorem (CLT)
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Estimate- Seiiiatte-Veiiff--eeeesss (EVR) Paradigm
Pass
Execute M
Privacy Accountant How private M?
(c, estimate
Privacy Verifier Is.M (c. D)-DP?
PFT-hased CLT Methods
MC baseba Verifler (ours)
Terminate
MC Accountant (ours)
Reject
program
Figure 2: An overview of our EVR paradigm. EVR converts estimated (s, 6) provided by privacy accountant into a formal guarantee. Compared with the original mechanism, the EVR has an extra failure mode that does not output anything when the estimated (2, is rejected. We show that the MC-based verifier we proposed can achieve negligible failure probability (O())) in Section 4.4
as well as an upper bound for (s) though bounding the worst-case estimation error. In practice, only the upper bounds for (s) can be used, as differential privacy is strict guarantee.
estimates can be more accurate than upper bounds. The motivation for this paper stems from the limi- tations of current privacy accounting techniques in providing tight upper bounds for (c) Despite outperforming MA, both
Motivation:
Desct
CDP- edgewortbesst
FFFupp
FFfest
CD--Edpworth-up
100
FFT- and CLT-bbsed methods can provide ineffective bounds in certain regimes [19 41). We demonstrate such limitations in Figure [ using the composition of Gaussian mechanisms. For FFT-based technique [19) we can see that although it out- performs MA for most of the regimes, the upper bounds (blue dashed curve) are worse than that of MA when 5 < 10-10 due to computational limitations (as discussed in [19 's Appendix A; also see Remark 6 for a discussion of why the regime of 6 < 10 10 is important). The CLT-based techniques (c.g.. (II also produce sub-optimal upper bounds (red dashed curve) for the entire range of 8. This is primarily due to the small number of mechanisms used (k = 1200), which does not meet the re- quirements for CLT bounds to converge (similar phenomenon observed 41)). On the other hand, we can see that the es- limates of (2) from both FFT and CLT-based techniques, which estimate the parameters rather than providing an upper bound, are in fact very close to the ground truth (the three curves overlapped in Figure []. However, as we mentioned carlier, these accurate estimations cannot be used in practice, as we cannot prove that they do not underestimate (E). The dilemma raises important question: parameter estimates instead of strict upper bounds in privacy accounting
10-2
10-1
10-6
10-8
10-10
10-12
2.0
2.5
3.0
3.5
Figure 1: Results of estimat- ing/bounding dM(() for the com- position of 1200 Gaussian mecha- nisms with = 70. '-upp' means upper bound and '-est' means es- timate. Curves of 'Exact', 'FFT- est', and 'CLT-est" are overlapped. The groundtruth curve ('Exact') ) for pure Gaussian mechanism can be computed analytically 19]
develop new techniques that allow us use privacy
This paper gives a positive answer to it. Our contributions are summarized as follows:
Estimate- Estimate--Verify-ee Verify- (EVR): DP paradigm that converts privacy parameter estimate into formal guarantee. We develop a new DP paradigm called Estimate- Verify-Release which augments a mechanism with a formal privacy guarantee based on its privacy parameter estimates. The basic idea of EVR is to first verify whether the mechanism satisfies the estimated DP guarantee, and release the mechanism's output if the verification is passed. The core component of the EVR paradigm is privacy verification. A DP verifier can be randomized and imperfect, suffering from both false positives (accept an underestimation) and false negatives (reject an overestimation). We show that EVR's privacy guarantee can be achieved when privacy verification has a low false negative rate.
A Monte Carlo-based DP Verifier. For an important and widely used class of DP algorithms including Subsampled Gaussian mechanism (the building block for DP-SGD), we develop Monte
We note that this not only brings benefits for the regime where d < 10 10 but also for the more common regime where 8 x 10-3, See Figure 3 for an example.

---

Carlo (MC) based DP verifier for the EVR paradigm. We present various techniques that ensure the DP verifier has both low false positive rate (for privacy guarantee) and a low false negative rate (for utility guarantee, i.e., making the EVR and the original mechanism as similar as possible).
A Monte Carlo-based DP Accountant. We further propose new MC-based approach for DP accounting, which we call the MC accountant. It utilizes similar MC techniques as in privacy verification. We show that the MC accountant achieves several advantages over existing privacy accounting methods. In particular, we demonstrate that MC accountant is efficient for online privacy accounting, a realistic scenario for privacy practitioners where one wants to update the estimate on privacy guarantee whenever executing a new mechanism.
Figure gives an overview of the proposed EVR paradigm well as this paper's 's contributions.
2 Privacy Accounting: a Mean Estimation/Bounding Problem
In this section, we review relevant concepts and introduce privacy accounting as a mean estima- tion/bounding problem.
Symbols and notations. We use D, D' E N to denote two datasets with an unspecified size over space X. We call two datasets D and D' adjacent (denoted D D') if we can construct one by adding/removing one data point from the other. We use P. Q to denote random variables. We also overload the notation and denote P(.), Q() the density function of P, Q.
Differential privacy and its equivalent characterizations. Having established the notations, we can now proceed to formally define differential privacy.
Definition 1 (Differential Privacy 13).. For e, 2 0, a randomized algorithm M :N* + y is (e, diifffferett private if for every pair of adjacent datasets D D' and for every subset of possible outputs E C Y, we have PrM(M(D) E E] S e² PIM[M(D') E E +
One can alternatively define differential privacy in terms of the maximum possible divergence between the output distribution of any pair of M(D) and M(D').
Lemma 2 (5.). A mechanism M is (ePD) iff supp-D Ear (M(()))((()))) S 6, where P(o)
(PIl)) = E 7)+ & (a)+ max(a,
E, is usually referred as Hockey- Stick (HS) Divergence in the literature. For every mechanism M and every 2 0, there exists a smallest ō such that M is ().P) Following the literature [44 2 we formalize such as function of e.
Definition (Optimal Privacy Curve). The optimal privacy curve of a mechanism M is the function 5M : R + [0. 1] s.t. 5M(()= == supp~ E (M(D)))M(('))
Dominating Distribution Pair and Privacy Loss Random Variable (PRV). It computationally infeasible to find (s) by computing Egr (M D) (I('))) for all pairs of adjacent dataset 7) and D'. mainstream strategy in the literature is to find a pair of distributions (P, Q) that dominates all (M(D), M(D')) in terms of the Hockey-Stick Stick divergence. This results in the introduction of dominating distribution pair and privacy loss random variable (PRV).
Definition 4 (144). A pair of distributions (P, Q) is a pair of dominating distributions for M under adjacent relation ~ for all y 2 0, sup pi. ((M(D)))M((D') < (P(l)) If equality achieved for all 7 Z 0, then we say (P, Q) is a pair of tightly dominating distributions for
M. Furthermore, call Y : log Q(a) 0 P the privacy loss random variable (PRV) of M associated with dominating distribution pair (P,Q).
[(oo
Zhu et al. [44] shows that all mechanisms have pair of tightly dominating distributions. Hence, we can alternatively characterize the optimal privacy curve ( Ee- (PIIQ) for the tightly dominating pair (P, Q), and we have (M(E) I Ear (Pl[Q) if (P, Q) is dominating pair that is not necessarily tight. The importance of the concept of PRV comes from the fact that we write Eer (PI()) as an expectation over it: (PIIQ) Ey [1 [1-
Thus, one can bound (s) by first identifying M's dominating pair distributions as well as the associated PRV Y, and then computing this expectation. Such formulation allows us to bound 6,((=) without enumerating over
3

---

all adjacent D and D'. For notation convenience, we denote 6y := By (1-e* -x Clearly, 5M S dy. If (P,Q) is a tightly dominating pair for M, then 8M = dy.
)+]
Privacy Accounting as Mean Estimation/Bounding Problem. Privacy accounting aims to estimate and bound the optimal privacy curve (E) for adaptively composed mechanism M Mi ..... MM,(D). The adaptive composition of two mechanisms M₁ and M2 is defined as Mi M2(D) == (M, M,(D, MM (D))), in which M2 can access both the dataset and the output of M₁. Most of the practical privacy accounting techniques are based on the concept of PRV, centered on the following result.
Lemma 5 (144). Let (P).Qz) be pair of tightly dominating distributions for mechanism Mj for (1....,, k). Then (Pi x ... x Px: Q1 x... x Qk) is pair of dominating distributions for M = oM........ o........ Ma. where x denotes the product distribution. Furthermore, the associated privacy
loss random variable is Y Di=1 Y; where Y; is the PRV associated with (t):
Lemma 5 suggests that privacy accounting for DP composition can be cast into mean estima- tion/bounding problem where one aims to approximate or bound the expectation in 2 when
Y == = Yú. Note that while Lemma 5 does not guarantee a pair of tightly dominating dis- tributions for the adaptive composition, it cannot improved in general, as noted in [TO]. Hence, all the current privacy accounting techniques work on ōy instead of dM, as Lemma 5 is tight even for non-adaptive composition. Following the prior works, in this paper, we only consider the practical scenarios where Lemma 5 is tight for the simplicity of presentation. That is, we assume dy = 6M unless otherwise specified.
Most of the existing privacy accounting techniques can be described as different techniques for such a mean estimation problem. Example-1: FFT-hased methods. This line of works (e.g.. (19) discretizes the domain of each Y; and use Fast Fourier Transform (FFT) to speed up the approximation of (s).. The upper bound is derived through the worst-case error bound for the approximation. Example-2: CLT-based methods. 7 41 use CLT to approximate the distribution of Y = = Y;
as Gaussian distribution. They then use CLT's sniple approximation guarantee to derive the upper bound for 5y (s).
Remark 6 (The Importance of Privacy Accounting in Regime d < 10-11), The regime where 8 < 10 10 is of significant importance for two reasons. (I) serves
upper bound the chance of severe privacy breaches, such as complete dataset exposure, necessitating a "'ryptographicall small" value, namely, 5 < n. -w(1) (14 40). (2) Even with the oft-used yet questionable guideline of = n or n -11, datasets of modern scale, such as JFT-3B (43] or LAION-5B (37y, already comprise billions of records, thus rendering small 8 values crucial. While we acknowledge that it requires a lot of effort to achieve a good privacy-utility tradeoff even for the current choice of d Rs it is important keep such a goal in mind.
3 Estimate- Sirinatte-erifyRReeeass
As mentioned earlier, upper bounds for (E) are the only valid options for privacy accounting techniques. However, we have demonstrated in Figure both FFT- and CLT-based methods can provide overly conservative upper bounds in certain regimes. On the other hand, their estimates for (E) can be very close the ground truth even though there is no provable guarantee. Therefore, is highly desirable to develop new techniques that enable the use of privacy parameter estimates instead of overly conservative upper bounds in privacy accounting.
We tackle the problem by introducing a new paradigm for constructing DP mechanisms, which we call Estimate-Verine -elle--Reeeaeeee (EVR). The key component of the EVR is object called DP verifier (Section 3.T). The full EVR paradigm is then presented Section 3.2 where the DP verifier is utilized as a building block to guarantee privacy.
3.1 Differential Privacy Verifier
We first formalize the concept of differential privucy verifier, the central element of the EVR paradigm. In informal terms, a DP verifier an algorithm that attempts to verify whether mechanism satisfies specific level of differential privacy.

---

Definition 7 (Differential Privacy Verifier), We say differentially private verifier DPV(-) is an algorithm that takes the description of mechanism M and proposed privacy parameter (E, 8 as imput, and returns True <- DPV(M, e, ( if the algorithm believes M is (e.8st))-D) (i.e., gest 8y (6) where Y is the PRV of M), and returns False otherwise.
A differential privacy verifier can be imperfect, suffering from both false positives (FP) and false negatives (FN). Typically, FP rate is the likelihood for DPV to accept (s, 8 when gest < ōy (E). However, 8est is still good estimate for (x) by being small (c.g.. <10%) underestimate. To account for this, we introduce smoothing factor, 7 E (0, 1], such that øest is deemed "should be rejected" only when 8 < Tōy (E). A similar argument can be put forth for FN cases where also introduce a smoothing factor E (0, 1]. This leads to relaxed notions for FP/EN rate:
Definition 8. We say a DPV's T-relaxed false positive rate at (E, 80s) is
FParr(e, :T)
sup M. (r)
Pr DDV(D,,,, True]
We say a DPV's p-relaxed false negative rate at (e, 80st) FNarls, dmm Mrceal ppyy (e)
sup
Pr [DP( 8 False]
Privacy Verification with DP Accountant. For composed mechanism M MM....oMMM MM a DP verifier can be easily implemented using any existing privacy accounting techniques. That is, one can execute DP accountant to obtain an estimate or upper bound (s, 8) of the actual privacy parameter. gest < 8, then the proposed privacy level is rejected as it is more private than what the DP accountant tells; otherwise, the test is passed. The input description of mechanism M,, in this case, can differ depending on the DP accounting method. For Moment Accountant []] the input description the upper bound of the noment--gneratinnn individual mechanism. For FFT and CLT-based methods, the input description is the cumulative distribution functions (CDF) of the dominating distribution pair of each individual M,.
function (MGF) of the privacy loss random variable for each
3.2 EVR: Ensuring Estimated Privacy with DP Verifier
We now present the full paradigm of
Algorithm 1 Estimate- Esttiate--Verify-ee Release (EVR) Framework
EVR. As suggested by the name, it contains three steps: (1) Estimate: A
Input: M: mechanism. D: dataset. (e, (E.8:t)): an esti- mated privacy parameter for M. if DPV(M, 80st) outputs True then Execute M(D).
privacy parameter (e, 8est) for M is estimated, e.g., based on a privacy au-
diting or accounting technique. (2) Verify: A DP verifier DPV is used for
3: else Print L.
validating whether mechanism M sat- isfies (c, J-st guarantee. (3) Release: If DP verification test is passed, we can execute M as usual; otherwise, the program terminated immediately. For practical utility, this rejection proba- bility needs to be small when (c, jost) is an accurate estimation. The procedure is summarized in Algorithm
Given estimated privacy parameter (s, J,st,, we have the privacy guarantee for the EVR paradigm:
Theorem 9. Algorithm is (e, 5ust /T) for any > 0 if FP per(e, 8est; < gest /T.
We defer the proof to Appendix B
The implication of this result is that, for any estimate of the privacy parameter, one can safely use it as DPV with a bounded false positive rate would enforce differential privacy. However, this is not enough: an overly conservative DPV that satisfies 0 FP rate but rejects everything would not be useful. When gest is accurate, we hope the DPV can also achieve small false negative discuss the instantiation of DPV in Section
that the output distributions of EVR and M indistinguishable. We
4 Monte Carlo Verifier of Differential Privacy
As we can see from Section 3.2 a DP verifier (DPV) that achieves small rate is the central element for the EVR framework. In the meanwhile, it is also important that DPV has low FN rate in
5

---

order to maintain the good utility of the EVR when the privacy parameter estimate is accurate. In this section, we introduce an instantiation of DPV based on the Monte Carlo technique that achieves both a low FP and FN rate, assuming the PRV is known for each individual mechanism.
Remark 10 (Mechanisms where PRV can be derived). PRV can be derived for many commonly used DP mechanisms such as the Laplace, Gaussian, and Subsampled Gaussian Mechanism [24 [9]. In particular, our DP verifter applies for DP-SGD, one of the most important application scenarios of privacy accounting. Moreover, the availability of PRV is also the assumption for most of the recently developed privacy accounting techniques (including FFT- and CLT-based methods). The extension beyond these commonly used mechanisms is an important future work in the field.
Remark 11 (Previous studies on the hardness of privacy verification). Several studies [6 g)
have shown that DP verification is an NP-hard problem. However. these works consider the setting where the input description of the DP mechanism is its corresponding randomized Boolean circuits. Some other works [18] show that DP verification impossible, but this assertion is proved for the black-box setting where the verifier can only query the mechanism. Our work gets around this barrier by providing the description of the PRV of the mechanism as inpua to the verifier.
4.1 DPV through an MC Estimator for (c)
Recall that most of the recently proposed DP accountants are essentially different techniques for estimating the expectation
8y EY=Et (,) (6)= = Ey (1((11
where each Y; is the privacy loss random variable Y; = log pair of dominating distribution for individual mechanism M, In the following text, we denote the product distribution P = P1 x... x Pa and Q == Q1 x x Qt- Recall from Lemma 5 that (P.Q) a pair of dominating distributions for the composed mechanism M. For notation simplicity, we denote a vector t == (t()).....t! (())).
P.0 Q.( for t ~ P., and (P,, Qi) is
Monte Carlo (MC) technique is arguably one of the most natural and widely used techniques for approximating expectations. Since 5y (s) is an expectation in terms of the PRV Y, one can apply MC-based technique to estimate it. Given an MC estimator for dy (s), we construct a DPV s, ) as shown in Algorithm 2 (in- stantiated by the Simple MC estimator intro- duced in Section (.2)). Specifically, we first obtain estimate 8 from MC estimator for dy (z). The estimate gest passes the test if
Algorithm 2 DPV(M, e, dest) with Simple MC Estimator and Offset Parameter A.
1: Obtain i.i.d. samples (t, i=1 from P.
2: Compute 8
===1 (1 - e5-))) with
m
PRV samples yi log Qit.)
Pit.)
1...m
3: if 8 < gost A then return True.
4: else return False.
8 < gest A, and fails otherwise. The parameter A 2 0 here is an offset that allows us to conveniently controls the r-relaxed false positive rate. We will discuss how to set A in Section 4.4
In the following contents, we first present two constructions of MC estimators for 8y-(E) in Section
4.2 We then discuss the condition for which our MC-based DPV achieves a certain target FP rate in Finally, we discuss the utility guarantee for the MC-based DPV in Section 4.4
Section 4.3
4.2
Constructing MC Estimator for (E)
In this section, we first present a simple MC estimator that applies any mechanisms where we can derive and sample from the dominating distribution pairs. Given the importance of Poisson Subsampled Gaussian mechanism for drivacy-rreseviigg machine learning, we further design more advanced and specialized MC estimator for it based on the importance sampling technique.
Simple Monte Carlo Estimator. One can easily sample from Y by sampling t ~ P and output P()) Hence, straightforward algorithm for estimating 2 is the Simple Monte Carlo (SMC) log Q(t) algorithm, which directly samples from the privacy random variable Y. We formally define here.

---

Definition 12 (Simple Monte Carlo (SMC) Estimator). We denote ((o(E) as the random variable of SMC estimator for öy (c) with m samples, i.e., (x)(E) sampled Y.
m Di=l (1 e for yis...g yru i.d.d.
Importance Sampling Estimator for Poisson Subsampled Gaussian (Overview). As 8y(e) is usually a tiny value (10-s or even cryptographically small), it is likely that by naive sampling from Y. almost all of the samples in {[1 Bf + j== are just Os! That is, the i.i.d. samples {vi ) from Y can rarely exceed e. To further improve the sample efficiency, one can potentially use more advanced MC techniques such as Importance Sampling or MCMC. However, these advanced tools usually require additional distributional information about Y and thus need to be developed case-by case-by-case, by-case.
Poisson Subsampled Gaussian mechanism is the main workhorse behind the DP-SGD algorithm M. Given its important role in on the Importance Sampling technique. Importance Sampling (IS) is a classic method for rare event simulation (3)] It samples from an alternative distribution instead of the distribution of the quantity of interest, and weighting factor is then used for correcting the difference between the two distributions. The specific design of alternative distribution is complicated and notation-heavy. and we defer the technical details Appendix C At a high level, we construct the alternative sampling distribution based on the exponential tilting technique and derive the optimal tilting parameter such that the corresponding IS estimator approximately achieves the smallest variance. Similar Definition [2] we use 8 to denote the random variable of importance sampling estimator with m samples.
MI., we derive an advanced MC estimator for based
4.3 Bounding FP Rate
We now discuss the FP guarantee for the DPV instantiated by 8gg and 8 we developed in the last section. Since both estimators are unbiased, by Law of Large Number, both 8ig and 8 converge to (E) almost surely as m + 2o, which leads a DPV with perfect accuracy. Of course, m cannot go to oo in practice. In the following, we derive the required amount of samples m for ensuring that r-relaxed false positive rate is smaller than 8est/ /T for Eye and 8 We use Swc (or ōis) as an abbreviation for &gc (or ggg), the random variable for single draw of sampling. We state the theorem for ogg, and the same result for 8m can be obtained by simply replacing 8yc with Sis. We use FP to denote the FP rate for DPV implemented by SMC estimator.
Theorem 13. Suppose E. (8xc)
I v. DPV instantiated by diz has bounded r-relaxed false
positive rate Fxxc(e, gost; 7) S gest /T with
2u A3 log(T/80st)
The proof is based on Bennett's 's inequality and is deferred to Appendix D This result suggests that, to improve the computational efficiency of MC- DPV (i.e., tighten the number of required samples), is important tightly bound [[((nc) )3] (or [[ e I)), the second moment of 8 (or ōis).
Bounding the Second-Moment of MC Estimators (Overview). For clarity, we defer the notation- heavy results and derivation of the upper bounds for [ {mc)) and [[(0rs)? }1 to Appendix Our high-level idea for bounding (rxc) ?| is through the RDP guarantee for the composed mechanism M. This a natural idea since converting RDP to upper bounds for (e) - the first moment of 8Nc Bounding [[(()s))* is highly technically involved.
is a well-studied problem 30
3
4.4 Guaranteeing Utility
Overall picture so far. Given the proposed privacy parameter (E, (E,8 a tolerable degree of underestimation т, and an offset parameter A, one can now compute the number of samples m required for the MC-based DPV such that r-relxeed FP rate to be < 8est /T based on the results from Section 4.3 and Appendix E We have not yet discussed the selection of the hyperparameter A. An appropriate A is important for the utility of MC-based DPV. That is, when gest is not too smaller than (E), the probability of being rejected by DPV should stay negligible. If we set A - co, the DPV simply rejects everything, which achieves O FP rate (and with m 0) but is not useful all!
Formally, the utility of a DPV is quantified by the p-relaxed false negative (FN) rate (Definition While one may be able to bound the FN rate through concentration inequalities, more convenient
7

---

way is to pick an appropriate A such that FNoey is approximately smaller than FP After all, FP already has to be small value I 8es /T for privacy guarantee. The result is stated informally in the following (holds for both 8xc and 11)) and the involved derivation is deferred to Appendix
Theorem 14 (Informal). When A = 0.4 (1/T 1/p) 8 then FNxc(E, 8est p) ~ FPxc(e, 800;;
Therefore, by setting A 0.4 1/p) gest, one can ensure that FNic(e, 80st; p) also (approxi- mately) upper bounded by ((80st/7) Moreover, in Appendix, we empirically show that the FP rate actually a very conservative bound for the FN rate. Both and are selected based on the tradeoff between privacy, utility, and efficiency.
The pseudocode of privacy verification for DP-SGD is summarized in Appendix G
5 Monte Carlo Accountant of Differential Privacy
The Monte Carlo estimators ôyc and ô1s described in Section 4.2 are used for implementing DP verifiers. One may already realize that the same estimators can also be utilized to directly implement DP accountant which estimates dv(e), It is important note that with the EVR paradigm, DP accountants are no longer required to derive a strict upper bound for (e). We refer to the technique of estimating 6y(e) using the MC estimators Monte Carlo accountant.
Finding E for a given 6. is straightforward to im- plement MC accountant when we fix and compute for dy (s). In practice, privacy practitioners often want do the inverse: finding for given 8, which we denote as (6). Similar to the existing privacy accounting methods, we use binary search to find ey (5) (see Algorithm 3). Specifically, after generat-
Algorithm 3 MC Accountant for Ey (d).
Obtain PRV samples { with either
Simple MC or Importance Sampling.
Binary
such that 1 - (1- (1-
search
Return c.
ing PRV samples (3/)
1=1+ we simply need to find the
such that > 1-ee --f=
ö. We do not
need to generate new PRV samples for different & we evaluate during the binary search; hence the additional binary search is computationally efficient.
Number of Samples for MC Accountant. Compared with the number of samples required for achieving the FP guarantee in Section 4.3 one may be able to use much fewer samples to obtain decent estimate for (e), as the sample complexity bound derived based on concentration inequality may be conservative. Many heuristics for guiding the number of samples in MC simulation have been developed (c.g., Wald confidence interval) and can be applied to the setting of MC accountants.
Compared with FFT-based and CLT-based methods, MC accountant exhibits the following strength:
(1) Accurate 8y (E) estimation in all regimes. As we mentioned earlier, the state-of of-te--f--hharr FFT- based method [19 fails to provide meaningful bounds due to computational limitations when the true value of 8y (E) is small. In contrast, the simplicity of the MC accountant allows us accurately estimate 5 (E) in all regimes.
(2) Short clock runtime & Easy GPU acceleration. MC-based techniques are well-suited for parallel computing and GPU acceleration due to their nature repeated sampling. One can easily utilize PyTorch's is CUDA functionality (e.g.. torch, randn (size= (k, (k,m)) ) cuda (immimma+mu) to significantly boost the computational efficiency for sampling from common distributions such as Gaussian. In Appendix H. we show that when using one NVIDIA A100 GPU, the runtime time of sampling Gaussian mixture (1 q) (0, o²) + (N can be improved by 10 times compared with CPU-only scenario.
(3) Efficient online privacy accounting. When training ML models with SGD or its variants, a privacy practitioner usually wants to compute a running privacy leakage for every training iteration, and pick the checkpoint with the best utility-privant Sellvty-privay tradeoff. This involves estimating (
for every i = 1,...,k, k. where y = Σ Yj. We refer to such a scenario as online privacy accounting MC accountant is especially efficient for online privacy accounting. When estimating
NNote that this is different from the scenario of privacy odometer 336, as here the privacy parameter of the next individual mechanism is not adaptively chosen.

---

8yco (E), one can re-use the samples previously drawn from Yi..... Yi-1 that were used for estimating privacy loss earlier iterations.
These advantages are justified empirically in Section 6 and Appendix
6 Numerical Experiments
In this section, we conduct numerical experiments to illustrate (1) EVR paradigm with MC verifiers enables tighter privacy analysis, and (2) MC accountant achieves oate-of-theeart performance in privacy parameter estimation.
6.1 EVR vs Upper Bound
To illustrate the advantage of the EVR paradigm compared with directly using strict upper bound for privacy parameters, we take the current state-of-the-art DP accountant, the FFT-based method from 19 as the example.
EVR provides a tighter privacy guarantee. Recall that in Figure [ FFT-based method pro- vides vacuous bound when the ground-trutt truth
10
102
10"
FFE (V (1999))
(e) 10-10 Under the same hyperpa- rameter setting, Figure (a) shows the privacy bound of the EVR paradigm where the jest are FFT's estimates, We use the Importance Sam-
Runtine
10-12
PIT-INE 240)
109
pling estimator 81s for DP verification. We ex- periment with different values of higher value of leads to tighter privacy guarantee but longer runtime. For fair comparison, the EVR's 's output distribution needs to be almost indistin- guishable from the original mechanism. We set p (1/+ and set A according the heuris- tic from Theorem 14 This guarantees that, as long as the estimate of gest from FFT is not big underestimation (i.e., as long as gost 2 p5y-(E)), the failure probability of the EVR paradigm is negligible (O(5y (+))). The "FFT-EVR' curve in Figure (a) is essentially the 'FFT-est' curve in see, EVR provides significantly better privacy analysis in the
10-45
PIT-DVR IT 0:30
2.8
3.0
32
344
3.6
2.8
3.0
3.2
3.4
Figure 3: Privacy analysis and runtime of the EVR paradigm. The settings are the same Figure For (a), when т >> 0.9, the curves are indistin- guishable from 'Exact'. For fair comparison, we set (1 (1+77 r)/2 and set A according to Theorem [4] which ensures EVR's failure probability of the order of 6. For (b). the runtime is estimated on an NVIDIA A100-SXM4-80CK GPU.
Figure Scaled up by 1/T. As regime where the 'FFT-upp" is unmeaningful (8 10-11).
EVR incurs little extra runtime. In Figure 3 (b), we plot the runtime of the Importance Sampling
verifier in Figure (b) for different т
0.9. Note that for t > 0.9, the privacy curves are
indistinguishable from 'Exact' in Figure (a). The runtime of EVR is determined by the number of
samples required to achieve the target relelxe FP rate from Theorem [3] Smaller 7 leads to faster see, when r 0.99. the runtime of DP verification in the EVR is < 2 minutes. This is attributable to the sample-efficient IS estimator and GPU acceleration.
DP verification. As
EVR provides better privacy-utility tradeoff for consumption. To further underscore the superiority of the EVR paradigm in practical applications, we illustrate the privacy-utilice tradcoff curve when finetuning shown Figure 4 the EVR paradigm provides a lower test error across all privacy budget compared with the traditional upper bound method. For instance, it achieves around 7% (relative) error reduction when æ = 0.6. The runtime time required for privacy verification is less than < 10-10 seconds for all which is negligible compared to the training time. We provide additional experimental results in Appendix H
MIL with minimal time
CIFAR 100 dataset with DP-SGD. As
6.2 MC Accountant
We evaluate the MC Accountant proposed in Section 5 We focus on privacy accounting for the composition of Poisson Subsampled Gaussian mechanisms, the algorithm behind the famous DP-SGD The mechanism specified by the noise magnitude and subsampling rate q.
algorithm [

---

Settings. We consider two practical scenarios of privacy account- ing: (1) Offline accounting which aims at estimating 6y (s), and (2) Online accounting which aims at estimating 6 (e) for all i == -....., k. For space constraint, we only show the results of online accounting here, and defer the results for offline accounting to Appendix H Metrie: Relative Error. To easily and fairly evaluate the performance of privacy parameter estimation, we compute the almost exact (yet computationally expensive) privacy parameters the ground-truth value. The ground-trun truth value allows us to compute the relative error of an estimate of privacy leakage. That is, if the corresponding ground-truth of an estimate 8 is 6, then the relative error Terr 5 - 8/66. /6. Implementation. For MC accountant, we use the IS estimator described in Section 4.2 For baselines, in addition to the FFT-based and CLT-based method we mentioned earlier, we also examine AFA 44 and GDP accountant 77]. For a fair compar- ison, we adjust the number of samples for MC accountant so that the runtime of MC accountant and FFT is comparable. Note that we compared with the privacy parameter estimates instead of upper bounds from the baselines. Detailed settings for both MC accountant and the baselines are provided
Test Drvor (%)
13
12
11
RFT-p00
FFT-EVR 0.95)
0.4
0.6
0.8
1.0
12
Figure 4: tradeoff curve for fine-tuning ImaaeeNet-pretrainee BEiT on CIFAR 100 when = 10 We follow the training proce- dure from 34
Urility-privacy
in Appendix H
Results for Online Accounting: MC accountant is both more accurate and efficient. Figure 5 (a) shows the on- line accounting results for (a, d.9) q) (1.0, 10- 10-3). As accountant outperforms all of the base- lines in estimating Ey (6). The sharp decrease in FFT at approximately 250 steps is due the transition of FFT's estimates from underestimating before this point overestimating after. Fig- ure (bb shows that MC accountant is around times faster than FFT, the base- line with the best performance in (a), This showcases the MC accountant's ef- ficiency and accuracy in online setting.
FFT
GDP
GDP-Edgeworth
MC (IS)
Relative Error in Estimating
Cumulative Runtime
10
see, MC
Relative Eiror
10-2
10a
10
100
10-4
10-3
10-2
10-1
250
500
750
1.000
250 500
750 1000
(4) Number of Compositions
(b) Number of Compositions
Figure 5: Experiment for Composing Subsampled Gaus- sian Mechanisms in the Online Setting. (a) Compares the relative error in approximating k + EY E The error bar for MC accountant is the variance taken over independent runs. Note that the y-axis is in the log scale. (b) Compares the cumulative runtime for online privacy accounting. We did not show AFA as it does not terminate in 24 hours.
7 Conclusion & Limitations
This paper tackles the challenge of deriving provable privacy leakage upper bounds in privacy accounting. We present the estimate-verrfy--reeee (EVR) paradigm which enables the safe use of privacy parameter estimate. Limitations. Currently, our MC-based DP verifier and accountant require known and efficiently samplable dominating pairs and PRV for the individual mechanism. Fortunately, this applics to commonly used mechanisms such as Gaussian mechanism and DP-SGD. Generalizing MC-based DP verifier and accountant to other mechanisms is an interesting future work.
10

---

Acknowledgments
This work was supported in part by the National Science Foundation under grants CNS-2131938. CNS-1553437, CNS-1704100 the ARL's Army Artificial Intelligence Innovation Institute (A (A212), the Office of Naval Research Young Investigator Award, the Army Research Office Young Investigator Prize, Schmidt DataX award, and Princeton E-ffiliates Award, Amazon- Amazon-Virginia Tech Initiative in Efficient and Robust Machine Learning, and Princeton's 's Gordon Y. S. Wu Fellowship. We are grateful to anonymous reviewers at NeurlPS for their valuable feedback.
References
[1] Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pages 408-318, 2016.
[2] Wael Alghamdi, Juan Felipe Gomez, Shahab Asoodeh, Flavio Calmon, Oliver Kosut, and Lalitha Sankar. The saddle-point method in differential privacy. In Proceedings of the 40th International Conference Machine Learning, pages 508-528, 2023.
[3] Shahab Asoodeh, Jiachun Liao, Flavio P Calmon, Oliver Kosut, and Lalitha Sankar. Three variants of differential privacy: Lossless conversion and applications. IEEE Journal on Selected Areas in Information Theory, 2(1):208 222, 2021.
[4] Hangbo Bao, Li Dong, Songhao Piao, and Furu Wei. Beit: Bert pre-training of image trans- formers. arXiv preprint arXiv:2106.08254 2021.
[5] Gilles Barthe and Federico Olmedo. Beyond differential privacy: Composition theorems and relational logic for f-divergences between probabilistic programs. International Colloquium on Automata, Languages, and Programming, pages 49-60. Springer, 2013.
[6] Benjamin Bichsel, Samuel Steffen, Ilija Bogunovic, and Martin Vechev. Dp-sniper: Black-box discovery of differential privacy violations using classifiers. In 2021 IEEE Symposium on Security and Privacy (SP), pages 391-409. IEFF, 2021.
[7] Zhiqi Bu, Jinshuo Dong, Qi Long, and Weijie J Su. Deep learning with gaussian differential privacy. Harvard data science review, 2020(23), 2020.
[8] Mark Bun, Marco Gaboardi, and Ludmila Glinskih. The complexity of verifying boolean pro- grams differentially private. In 2022 IEEE 35th Computer Security Foundations Symposium (CSF), pages 396-411. IEEE, 2022.
[9] Clément L Canonne, Gautam Kamath, and Thomas Steinke. The discrete gaussian for differen- tial privacy. Advances in Neural Information Processing Systems, 33:15676-15688, 2020.
[10] Jinshuo Dong, Aaron Roth, and Weijie Su. Gaussian differential privacy. Journal of the Royal Statistical Society Series B: Statistical Methodology, 84(1):3-37, 2019.
[1I] Vadym Doroshenko, Badih Ghazi, Pritish Kamath, Ravi Kumar, and Pasin Manurangsi. Connect the dots: Tighter discrete approximations of privacy loss distributions. Proceedings on Privacy Enhancing Technologies, 4:552-570, 2022.
[12] Cynthia Dwork and Jing Lei. Differential privacy and robust statistics. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 371-380, 2009.
[13] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pages 265-284. Springer, 2006.
[14] Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Founda- tions and Trends@ in Theoretical Computer Science, 112211-400 407, 2014.
[15] Cynthia Dwork, Guy N Rothblum, and Salil Vadhan. Boosting and differential privacy. In 2010 IEEE 51st Annual Symposium Foundations of Computer Science, pages 51-60. IEEE, 2010.

---

[16] Marco Gaboardi, Kobbi Nissim, and David Purser. The complexity of verifying loop-free programs as differentially private. In 47th International Colloquium on Automata. Languages, and Programming (ICALP 2020). Schloss Dagstuhl- Pagstuhl-Leebbniz--Zeetruu für Informatik, 2020.
[17] Badih Ghazi, Pritish Kamath, Ravi Kumar, and Pasin Manurangsi. Faster privacy accounting via evolving discretization. In International Conference on Machine Learning, pages 7470-7483. PMLR, 2022.
[18] Anna C Gilbert and Audra McMillan. Property testing for differential privacy. In 2018 56th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 249-258. IEEE, 2018.
[19] Sivakanth Gopi, Yin Tat Lee, and Lukas Wutschitz. Numerical composition of differential privacy. Advances in Neural Information Processing Systems, 14:11631-1164) 2021.
[20] Daniele Gorla, Louis Jalouzot, Federica Granese, Catuscia Palamidessi, and Pablo Piantanida. On the (im) possibility of estimating various notions of differential privacy. arXiv preprint arXiv:2208. 14414, 2022.
[21] Matthew Jagielski, Jonathan Ullman, and Alina Oprea, Auditing differentially private machine learning: How private is private sgd? Advances in Neural Information Processing Systems, 33:22205-2222 22216,2222222 2020.
[22] Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The composition theorem for differential privacy. In International conference on machine learning, pages 1376-1385, PMLR, 2015.
[23] Antti Koskela and Antti Honkela. Computing differential privacy guarantees for heterogeneous compositions using fft. CoRR, 1ttp2100212112.. 2021.
[24] Antti Koskela, Joonas Jälkö, and Antti Honkela. Computing tight differential privacy guarantees using fft. In International Conference on Artificial Intelligence and Statistics, pages 2560-2569. PMLR, 2020.
[25] Antti Koskela, Joonas Jälkö, Lukas Prediger, and Antti Honkela. Tight differential privacy for discrete-valued mechanisms and for the subsampled gaussian mechanism using fft. In International Conference on Artificial Intelligence and Statistics, pages 2021.
PMLR,
[26] Xiyang Liu and Sewoong Oh. Minimax optimal estimation of approximate differential privacy on neighboring databases. Advances in neural information processing systems, 32, 2019.
[27] Fred Lu, Joseph Munoz, Maya Fuchs, Tyler LeBlond, Elliott V Raff, Francis Ferraro, and Brian Testa. A general framework for auditing differentially private machine learning. In Advances in Neural Information Processing Systems, 2022.
Edward
[28] Yun Lu, Yu Wei, Malik Magdon-Ismail, and Vassilis Zikas. Eureka: A general framework for black-box differential privacy estimators. Cryptology ePrint Archive, 2022.
[29] Saeed Mahloujifar, Alexandre Sablayrolles, Graham Cormode, and Somesh Jha. Optimal membership inference bounds for adaptive composition of sampled gaussian mechanisms. arXiv preprint 1rXiv:2204006100 2022.
[30] Ilya Mironov. Rényi differential privacy. In 2017 IEEE 30th Computer Security Foundations Symposium (CSF), pages 263-275. IRHE, 2017
[31] Jack Murtagh and Salil Vadhan. The complexity of computing the optimal composition of differential privacy. In Theory of Cryptography Conference, pages 157-175. Springer, 2016.
[32] Milad Nasr, Jamie Hayes, Thomas Steinke, Borja Balle, Florian Tramèr, Matthew Jagielski, Nicholas Carlini, and Andreas Terzis. Tight auditing of differentially private machine learning. arXiv preprint 2rXiv:2302.07956 2023.
[33] Milad Nasr, Shuang Songi, Abhradeep Thakurta, Nicolas Papernot, and Nicholas Carlin. Ad- versary instantiation: Lower bounds for differentially private machine learning. In 202/ IEEE Symposium security and privacy (SP), pages 866-882. IEEE, 2021.
12

---

[34] Ashwinee Panda, Xinyu Tang, Vikash Sehwag, Saeed Mahloujifar, and Prateek Mittal. Dp-raft: differentially private recipe for accelerated fine-tuning. arXiv preprint arX14:2212.04486. 2022.
[35] Rachel Redberg, Yuqing Zhu, and Yu-Xiang Wang. Generalized pir: User-friendly recipes for data-adaptive algorithms with differential privacy. In International Conference on Artificial Intelligence and Statistics, pages 3977-4005, PMLR, 2023.
[36] Ryan M Rogers, Aaron Roth, Jonathan Ullman, and Salil Vadhan. Privacy odometers and filters: Pay-as-you-go composition. Advances in Neural Information Processing Systems, 29, 2016.
[37] Christoph Schuhmann, Romain Beaumont, Richard Vencu, Cade Gordon, Ross Wightman, Mehdi Cherti, Theo Coombes, Aarush Katta, Clayton Mullis, Mitchell Wortsman, et al. Laion- 5b: An open large-scale dataset for training next generation image-text models. Advances in Neural Information Processing Systems, 35:25278 25294,, 2022.
[38] Thomas Steinke, Milad Nasr, and Matthew Jagielski, Privacy auditing with one (1) training run. arXiv preprint arXiv:2305. 30.30086666.,... 2023.
[39] Surya T Tokdar and Robert E Kass. Importance sampling: review. Wiley Interdisciplinary Reviews: Computational Statistics, 2(1):54-60, 2010.
[40] Salil Vadhan. The complexity of differential privacy. Tutorials on the Foundations of Cryptog- raphy: Dedicated to Oded Goldreich, pages 347-450, 2017.
[41] Hua Wang, Sheng Gao, Huanyu Zhang, Milan Shen, and Weijie Su. Analytical composition of differential privacy via the edgeworth accountant. arXiv preprint arXiv:2206.0422: 2022.
[42] Jiachen T Wang, Saeed Mahloujifar, Shouda Wang, Ruoxi Jia, and Prateek Mittal. Renyi differential privacy of propsse-testreeeass and applications to private and robust machine learning, Advances in Neural Information Processing Systems, 35:38719-38732 2022.
[43] Xiaohua Zhai, Alexander Kolesnikov, Neil Houlsby, and Lucas Beyer. Scaling vision transform- ers. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages
2022.
[44] Yuqing Zhu, Jínshuo Dong, and Yu-Xiang Wang. Optimal accounting of differential privacy via characteristic function. In International Conference on Artificial Intelligence and Statistics, pages 4782-4817. PMLR, 2022.
13

---

A Extended Related Work
In this section, we review the related works in privacy accounting, privacy verification, privacy auditing, and we also discuss the connection between our EVR paradigm and the famous Propose- Test-Release (PTR) paradigm.
Privacy Accounting, Early privacy accounting techniques such as Advanced Composition The-
orem
[T]] only make use of the privacy parameters of the individual mechanisms, which bounds in terms of the privacy parameter (c,, 6;) for each MM, i = .,...,h k. The optimal bound for (c) under this condition has been derived [2 31. However, the computation of the optimal bound is #P-hard in general. Bounding (E) only in terms of (c;, 6,) is often sub-optimal for many [31] This disadvantage has spurred many recent advances in privacy ac- counting by making use of more statistical information from the specific mechanisms to be composed
(
commonly used mechanisms
41 2 All of these works can be described as approximating the discretize the domain of each Y; and use Fast Fourier Transform (FFT) in order to speed up the approximation of (e). [44] tracks the characteristic function of the privacy loss random variables for the com- posed mechanism and still requires discretization when the mechanisms do not have closed-form characteristic functions. The line of 77 41
1130 7 23 25 19
expectation in 2 when Y = Σ i=1 Y, For instance, the line of 24 23 25
uses Central Limit Theorem (CLT) to approximate the distribution of Y Zi=1. Yú Gaussian distribution and uses the finite-sample bound to derive the strict upper bound for (E). We also note that [29] also uses Monte Carlo approaches to calculate optimal membership inference bounds. They use similar Simple MC estimator as the one in Section 4.2 Although their Monte Carlo approach is similar, their error analysis only works for large values
k
of 8 (6 z 0.5) they use sub-optima concentration bounds.
Privacy Verification. As we mentioned in Remark some previous works have also studied the problem of privacy verification. Most of the works consider either "white-box setting" where the input description of the DP mechanism its corresponding randomized Boolean circuits [16] 8). Some other works consider even more stringent "black-box setting" where the verifier can only query the mechanism [18 [6 6, 20 28). In contrast, our MC verifier is designed specifically for those mechanisms where the PRV can be derived, which includes many commonly used mechanisms such as the Subsampled Gaussian mechanism.
Privacy verification via auditing. Several heuristics have tried to perform DP verification, forming a line of work called auditing differential privacy (3 27 32, 38). Specifically, these techniques can verify a claimed privacy parameter by computing lower bound for the actual privacy parameter, and comparing that with the claimed privacy parameter. The input description of mechanism M for DPV, in this case, is black-box oracle MM-). where the DPV makes multiple queries to MM() and estimates the actual privacy leakage. Privacy auditing techniques can achieve 100% accuracy when gest > (x) (or 0 p-FN rate for any p & 1), as the computed lower bound is guaranteed be smaller than gest, However, when gest lies between šy (E) and the computed lower bound, the DP verification will be wrong. Moreover, such techniques do not have guarantee for the lower bound's tightness.
Remark 15 (Connection between our EVR paradigm and the Propose- [12). PTR is a classic differential privacy paradigm introduced over a decade ago by [12], and is being generalized in (35 42y. At high level, PTR checks if releasing the query answer is safe with certain amount of randomness (in private way). If the test is passed, the query answer is released: otherwise, the program is terminated. PTR shares a similar underlying philosophy with our EVR paradigm. However, they are fundameentally different in terms of implementation. The verification step in EVR is completely independent of the dataset. In contrast, the test step in PTR measures the privacy risks for the mechanism M on specific dataset D, which means that the test itself may cause additional privacy leakage. One way to think about the difference is that EVR asks "whether M is private", while PTR asks "whether MDD is private".
(PTR) paradigm
14

---

B Proofs for Privacy
Theorem 9, Algorithm 7 is (e, 8 /T) for any FP oFr(E, 8 ; S g0st /T.
Proof.
For any mechanism M, we denote A as the event that gest 2 (E), and indicator variable B DDV(M, 8 = True]. Note that event implies M (fest /T)-DP.
Thus, we know that
Pr[B = 1|A] S PPDPv(E, 8
(I)
For notation simplicity, we also denote := Pr[B = 1|A1, and PTP = Pr[B 1|A].
For any possible event S.
Pr Mang [M S] E|B 1| (/M
-PT(M(D) E SBB 1, A| - + L, [AV]A
+ Pr(B = 0]
( PH(M(DD E =
Jost
Pr[B= [|A[A
+PIM)(D E 1, = [[A][[ M
+ ILLES Pr[B =0
eF RELM(DD) E = + Jost
pTp + pFp/[A] + + e Pr|B = -]
S (PFLM(D') E SBB = A|pTe/ + PH(M(D') E S = 1, Alpp [A] 1[ e S) Pr[B = 01)
gost
[TP][A]] PFP
gest PTP
Se [Mang (D)) S) + max
PFP
Maux
where in the first inequality, we the definition of differential privacy. Therefore, Masg is (e, max "re .PF)) -DP. By assumption of pFp FPopr(e, 8e)t;) S 8est//r /T, we reach the conclusion.
15

---

C Importance Sampling via Exponential Tilting
Notation Review. Recall that most of the recently proposed DP accountants are essentially different techniques for estimating the expectation
8y E (z(e) = IFy (1--)-))_]
where each Y; is the privacy loss random variable Y, = log
P. Q.01
for t P., and (Ps, Qi) a pair
of dominating distribution for individual mechanism MM, In the following text, we denote the product distribution P = P1 ... x Ps and Q = Q1 x .... x Qx- Recall from Lemma 5 that (P, Q) is pair of dominating distributions for the composed mechanism M. For notation simplicity, we denote
a vector t = (((,),..., (())), We slightly abuse the notation and write y(4: P) = log 2(1
P(C)
Note that y(t: P.Q) Ei= v(t(1; P., Q.). When the context clear, we omit the dominating pairs and simply write y(t).
Dominating Distribution Pairs for Poisson Subsampled Gaussian Mechanisms. The dominating distribution pair for Poisson Subsampled Gaussian Mechanisms a well-known result.
Lemma 16. For Poisson Subsampled Gaussian mechanism with sensitivity C, noise variance C² and subsampling rate 4, one dominating pair (P, Q) is Q = NNO00 o²) and P = (1 - (0, o²)
qN(1,
Proof. See Appendix B of [1
That is, Q is just a 1-dimensional standard Gaussian distribution, and a convex combination between standard Gaussian and Gaussian centered at 1.
Remark 17 (Dominating pair supported on higher dimensional space). The cost of our approach would not increase (in terms of the number samples) even if the dominating pair is supported in high dimensional space. For Monte Carlo estimate, we can see from Hoeffding's 's inequality that the expected error rate of estimation is independent of the dimension of the support of dominating distribution pairs. This means the number of samples we need to ensure a certain confidence interval independent of the dimension. However, we should also note that although the number of samples does not change, the sampling process itself might be more costly for higher dimensional spaces.
C.1 Importance Sampling for the Composition of Poisson Subsampled Gaussian Mechanisms
Importance Sampling (IS) is classic method for rare event simulation. It samples from an alternative distribution instead of the distribution of the quantity of interest, and a weighting factor then used for correcting the difference between the two distributions. Specifically, we can re-write the expression for 5y (e) as follows:
dy(s)= = Ey [(1 - c
(1- )
EtnP
= Etap' (1-
P(t) P'(t))
where p' the alternative distribution up to the user's choice. From Equation one can construct an unbiased importance sampling estimator for (=) by sampling from P In this section, we develop P' for estimating dy when composing identically distributed Poisson subsampled Gaussian mechanisms, which is arguably the most important DP mechanism nowadays due to its application in differentially private stochastic gradient descent.
Exponential rilting a common way to construct alternative sampling distribution for IS. The exponential tilting of a distribution P is defined as
St
Pa(t)
Mp P(t)
16

---

where Mp( := E is the moment generating function for P. Such a transformation especially convenient for distributions from the exponential family. For example, for normal distribution N (u,, )²), the tilted distribution is NN + 0r r²),, which is easy to sample from.
consider Poisson Subsampled Gaussian mechanism with sensitivity 1, noise variance o², and subsampling rate Recall from Lemma 16 that the dominating pair in this case is Q := -0 o²) and P : (1-9)A((,, o²) + qV(L, o²). For notation simplicity, we denote Po == (",, and thus P p (1- gfo. Since each individual mechanism is the same, P ... and Q = =x XQ. The exponential tilting of P with parameter
Without the loss of generality,
is Pg == (1 (Bo? o²)
+ qV + 10"1 00², We propose the following importance sampling
estimator for dy (E) based on exponential tilting.
Definition 18 (Importance Sampling Estimator for Subsampled Gaussian Composition). Let the alternative distribution
;= Po PP,... Po P). i i~ Unif((k])
ith dim
with 0 1/2 + 0² log
(xp(6))(1-11) ). Given random draw Po. unbiased sample for 9
5y (E) is (1-ce-a(t.P.)))
We denote 8t (E) as the random variable of the 18,8 corresponding importance sampling estimator with m samples.
(+E
Po(t.)
P(t.)
We defer the formal justification of the choice of e to Appendix C.2 We first give the intuition for why we choose such an alternative distribution Po.
Intuition for the alternative distribution Po. It well-known that the variance of the importance sampling estimator is minimized when the alternative distribution
P'(t) x (1- (1-6-v(()) P(t)
The distribution of each privacy loss random variable y(t; P. Q), P light-tailed, which means that for the rare event where yt) Σ y(((0) > e, is most likely that there is only one outlier t" among all {t()) y such that y(t*) is large (which means that y(t) is also large), and all the rest of y((())s ys are small. Hence, a reasonable alternative distribution can just tilt the distribution of a randomly picked t(0), and leave the rest
distributions to stay the same. Moreover, is selected to approximately minimize the variance of δ.s.e (detailed in Appendix C.2 An intuitive way see is that y() E, which significantly improves the probability where y(t) 2 E while also accounting for the fact that P(t) decays exponentially fast as t increases.
We also empirically verify the advantage of the IS estimator over the SMC estimator. The orange curve in Figure (a) shows the empirical estimate of E (((88s,))) which quantifies the variance of Ō15.0. Note that 0 = 0 corresponds to the case of 8 As we can see, (E((81s.))² drops quickly as increases, and eventually converges. We can also see that the 0 selected by our heuristic Definition
18 (marked as red '**) approximately corresponds to the lowest point of TE (E(0r,,)) This validates theoretical justification for the selection of 0.
17

---

1.0
Analytical Bound
10
Empirical Est.
Rejection Probability
0.8
10-
Elö a]
0.6
(8
15- Bo-BBonddd Optimel (0 + 7.5)
0.4
Houristte 9.54)
10-8
0.2
(a)
0.0
2.5
5.0
7.5
10.0
(b)
10a
10a
107
0
# Samples (m)
Figure 6: We examine the properties of MC-based DP verifiers for Poisson Subampled mechanism.
We q 10-3,- a 0.6, 1.5, k 100. 6y 7.7 x 10-6 in this case. (a) Plot for
the upper bound and empirical estimate of E Kicl and B(6ig,o)- The upper bounds are computed E fs. Note that f
by Corollary 22 (for E B( and Theorem 23 (for E
corresponds δyc-
The red star indicates the second moment for the value of 0 selected by our heuristic in Definition 18 The blue star indicates the 0 that minimizes the analytical bound. (b) Empirical estimate of
the rejection probability Pr(om,, IS.0 8est /T A] scaled with the number of samples m. We set
gest 0.85y (e), 10-5/800 and we A following the heuristic proposed in Section 4.4 4.4
C.2 Justification of the Heuristic of Choosing Exponential Tilting Parameter 0
The variance of the IS estimator proposed in Definition 18 given by
(1 (1-0-
(P((t)
P(t) 27
EePPh
1 c v(EP.
P(tt)
Po(t)) ]
EEp
Po(ts)
- (1-
P(t:)
= <oMp( (1-0-(()).)))
(
1
Σ
clti
Let S(0) = kMP(0)E<~P (1----((PP.)) S(0).
We aim to find 0 that minimizes
5h
Note that
Mp(0) = (1 - (1-))et220
+ ge $090
(3)
To simplify the notation, let b(t) = (1- - 2 I Po()))
-1
S(0) [1- 2000 (020) + ge"+2
(1 (1 [2000]]
f...JMt b(L) Σ
dt
(4)
- [[1 (1--)eto00) + ge g /b(e) b(t) Σx cliie dt EEhn ElPi
(5)
By setting a S(0) 0 and simplify the expression, we have
18

---

S S
E eltic Ex
dl
q (0=0) qe 1 q + qe"
(Ei-) e.li)
(6)
[... (E/=) clles
dt
As mentioned earlier, b(t) 0 only when y(t) Σ y(t and for such event it is most likely that there is only outlier t' among all { of ((())) O. Therefore, simple but surprisingly effective approximation for the RHS of 6 is
Ji=1 such that y(t*) = and all the rest
E ct dt (Ei-1 cot)) )
b(t)
b(t)e -66
S J... ((t) (Ein ( )
b(t)e- 98
dt
for s.t. y(t) = E. This leads to an approximate solution
0" 20 log ((exp()) 9))///)
(8)
19

---

D Sample Complexity for Achieving Target False Positive Rate
To derive the sample complexity for achieving DP verifier with target false positive rate, use Bennett's s inequality.
Lemma 19 (Bennett's inequality). Let X1, XI,..., Xa be independent real-valued random variables with finite variance such that X; I for some b O almost surely for all 1 i Let 2 [[ For any & > O, we have
Pr Σ
X. - [[X 21
< exp
V B
h
bt
(9)
1=1
where h(z) (1 Z)) log(1 + x) for > 0.
Theorem 13. Suppose E (6xc)
DPV instantiated by 6% has bounded T-relaxed false
positive rate FPxcle, gest; 8est /r with 2v
log(t//est)) A
Proof. For any M s.t. gost < <ōy (E); we have
Pr
8 (e; Y) 80st /T A
S Pr
NC
(s; Y) < (c - ]
Pr
1
m
6 (e)) A
HO
m
Pr
(ōr
A
(10)
Since ôwc [-1, the condition in Bennett's inequality is satisfied with 0+. Hence, be upper bounded by
10
my
10
lim
exp
5-00+
b
v
mA2
exp
2v
By setting exp
(-
md²) 1-2""
< 80st /T, we have
2y
m 2
log(T/6
A
20

---

E Proofs for Moment Bound
E.1 Overview
(8xc) )²1 (or E (61s) 2)
As suggested by Theorem 13 a good upper bound for E
is important for
the computational efficiency of MC-based DPV.
We upper bound the higher moment of Eyc through the RDP guarantee for the composed mechanism M. This is a natural idea since converting RDP to upper bounds for (E) - the first moment of ENc a well-studied problem (30, 9 3. Recall that the RDP guarantee for M equivalent to bound for My (A) == E BEEAY] for M's privacy loss random variable Y for any À 2 0.
Lemma 20 (RDP-MGF bound conversion
30
If mechanism M is (a,ER(a))-RDP, then
(A) I exp(AER + 1)).
We convert an upper bound for M- into the following guarantee for the higher moment of 8nc= e
Theorem 21. For any u 2 we have
[[((xc)"] (11-6-))4
S min (A)e =x x" (u + A)a43
X20
The proof is deferred to Appendix E.2 The basic idea is to find the smallest constant e such that
[[((Hc) "I - eMy (A). By setting 1. our result recovers the RDP-DP conversion from [9] By setting 2, we obtain the desired bound for [E((xx))*
Corollary 22. E[ (8x))² & minA20 My (A)e -c (A+2)=-7
Corollary 22 applies to any mechanisms where the RDP guarantee available, which covers wide range of commonly used mechanisms such as (Subsampled) Gaussian or Laplace mechanism. We also note that one may be able to further tighten the above bound similar to the optimal RDP-DP conversion in 3]. We leave this an interesting future work.
Next, we derive the upper bound for (E((d1,,)) for Poisson Subsampled Gaussian mechanism. Theorem 23. For any positive integer X, and for any a.b 2 s.t. 1/a + 1/b 1, we have 1/a (b0e->e [(((), e --b0l blrdx)
1/b where r(2, x)) is upper
B[(ōrs.0) 11 $ kM) [[
bound for Pra- mmax 4 S x. v() 2 e| detailed in Appendix E.3
The proof is based on applying Hölder's inequality to the expression of (((615,)) {), and then bound I
{ Pa(ts) P(a)
-17
the part where is involved: Ee-P
We can bound I8 (0 through Theorem
21
Figure (a) shows the analytical bound from Corollary 22 and Theorem 23 compared with empirically estimated [[x()))) and (((8Ts,))²) As we can see, the analytical bound for ([(0r,,))² for relatively large is much smaller than the bound for (((()c))) (i.e., 0 O in the plot). Moreover, the 0 which minimizes the analytical bound (the blue ***) is close to the 0 selected by our heuristic (the red ***). For computational efficiency, one may prefer use that minimizes the analytical bound. However, the heuristically selected is still useful when one simply wants to estimate &y (s) and does not require the formal, analytical guarantee for the false positive rate. We such scenario when we introduce the MC accountant in Section 5 We also note that such a discrepancy (and the gap between the analytical bound and empirical estimate) is due to the use of Hölder's inequality in bounding E (8 ))). Further tightening the bound for E ( ) )
find that
is important for future work.
E.2
Moment Bound for Simple Monte Carlo Estimator
Theorem 21. For any u 2 1, we have
(((c))) "1 B [11 (1--c
- < min (Y)e
AA (u Aju+3
X20
21

---

Proof.
/ (1-6 P(x)dx
[ - + )
(1 -Mx(1) / 2 Au P(a)ete Elerr dr
My (M)EEww -0-
M ((1 - e - e(e
where (x)))= P(xee
E is the exponential tilting of P. Define (at A) (1 e -- =2
When
x I 50, A) = 0. When x > O, the derivative of f with respect to x
0f(r,A) -1 3)- (u+ X) A]
It is casy to see that the maximum of f(z, A) is achieved at x log (x+2) ) and we have
u max f(x, =
u + x u 2 (u + Ajutx
u+1 A
Overall, have
B[(1 - e ) S My(e -2 An
Ajuta
E.3
Moment Bound for Importance Sampling Estimator
In this section, we first prove two possible upper bounds for Bi(ōis,)) in Theorem 24 and Theorem We then combine these two bounds in Theorem 23 via Holder's inequality.
26
Theorem 24. For any 0 2 1/0², we have
E +k) e ]
E((6,100) < My
q
Proof.
(1-6-0((P(0))
P(() 27
BenP,
Po(t)
((())
Etap
1 - (1-6-0(6PP.0)
Pb(())
1 (1-E-
Po(ta) P(())
=Eap
K
(1-0-01eP.0))
k
-Mr(O)Ee>>
(II)
i= co
Note that
(1-C--(RPO))
k
EmP
Σ eBl
(1-E-)()P(0)))
2
=Eup
Ily(t; P,Q) 2
Σ t Clts
22

---

Lemma 25. When y(t; (.Q: = = log (1 -1-10 9 gel qe(22;-11/(20")
2 E and 0o² 2 we have
k ( +k+ cl/1203) or2
th k
Proof.
Since log(1 + x) S x,, we have
1 - + qe - 1)/(203))
log
(1:-11/1200) -1)
==
Hence,
/
///0²
- +k) 2/(20²)
e
2
9
1=1
Hence,
k
O02
(1 Oo2
Σ
(2t1/²))
=
1=1
i=1
Oa²
(et//o2)
k
G
el/1202)
2 k
+
000
k
+ ht
012
k
where the first inequality is due to Jensen's 's inequality.
By Lemma
25
we have
1
(1-6- 21
S (0)
Eap
(1-
187
+ k)
6012
q
-0o²
1
Mr(O)
+
2
To
which concludes the proof.
Theorem 26. For any positive integer X, we have
E[(ōrs,0)) ) s (0)00 [ e "dx
(12)
where r(), x) an upper bound for mixture Plea-
for the MGF of privacy loss random variable of truncated Gaussian
Proof. Similar to Theorem 24 the goal is to bound
(1- (1-0-0((R22)))
kM kMp
23

---

Note that
(1 (1-
1
Ex-P
E chrs
+
(1 (1-6-1()P)))
=Eap
Tlu(t: P.Q) 20]
Eup
Tyy(t: P.Q)
* ii= cll
E
Ily(t; P, Q) 2
(13)
Mmax
where tmax max; tz-
Further note that
13
Et-P Mmmxx [by(t) {]]
EeoP 00max (u(t) 2 &
Pr (u(t) 2 E]
t~p
(J --ord Pr Imax sa] Pr Pplu(()) 2
tmp
(1
Pr Umax sxlu(()) 2 s)de Ur UP
Pr Pplu(t) 2 ee
(14)
up
Ibmax S x. vtt(()) 2 8) ordr tvp
Pr
(15)
where (14) is obtained through integration by parts.
Now, as we can see from 15). the question reduces to bound Preu Umaax S x. x1,((1) 2 8) for any E R. It might be easier to write
Pr top
Itmax S x2,(() =|
Pr (u(t) 2 Eltmax I x] Pr t-P
[tmax x]
toP
and we know that
Pr [t S a1) * knP
Pr twp
Immax
S x]
(16)
= ((1 q) 0, 020) + (0(x;
(17)
as all 4, are i.i.d. random samples from P, where 1 (:) is the CDF of Gaussian distribution with mean and variance o².
It remains to bound the conditional probability Pre- (u(t) 2 Eltmax S 20. it may be easier to see it in this way:
(u(() 2 E mmxx S 2² t~p
Pr
Pr (y(() 2 Elt1 S tt...,t I x]
top
Pr Σ u(ts) 2 Ely(ti) s
..... ((z))...,((tt)) v(x)
... EnP J v(t)) ((el((t)) so(o)...,v(tall S v(x)
where the last step due Chernoff bound which holds for any > Now we only need to
21-1
bound the moment generating function for y(t) log(1 q ge no ) Pl where Pl Plcu is
24

---

the truncated distribution of P. We note that this is equivalent to bounding the Rényi divergence for truncated Gaussian mixture distribution.
Recall that (1 q)W(0, o2) For any that is positive integer, we have
Ex-P
AD( llt x]]
(1 g) 1
(1 q + ge 200
f2 + l (1- qe 200
V
2 ge 20
q' (1 g)e
l--1 20
erf
x x (A 1A-11 1)
+1 + qe
(1-4411-1 2x
erf
x2 1--AA-+t1) 11
+1)
20
/20
(18)
where q := (1-9) (2x2) Note that the above expression can be efficiently computed. Denote
9
the above results as r(), x) = 18).
Hence
e Aoll S s]]
r(>, x)
ExP
(19)
Prew (1 S
Now we have
Evop ler Ei Eimn u(t)) 2 et x
Pr t-p
[t(()= 2 e//max S $x]5
ede
[r(,,z)] ed (Preoplt S x))*
Plugging this bound into 15 we have
13
Pr Immxx S <x,3(t) 2 E] 0r dx twp
S Oe de / [1((,)))* e e dx
which leads to the final conclusion.
Remark 27. In practice, we can can further improve the bound by moving the minimum operation inside the integral:
E((6..0)71 S kMp())
[[ [mmin((AA=)) e -0z dx
(20)
Of course, this bound will be less efficient to compute.
Theorem 23 (Generalizing Theorem 24 and Theorem 26 via Holder's inequality). For any positive
and
integer X, and for any a, b 2 1 s.I. 1/a + 1/b 1, we have E((6is0)7 S kM)(0) (I85%) 1/a
(b8c de ( Ir(A,)))* e b0x dx
1/b
where r r(A, x) is an upper bound for the MGF of privacy loss
random variable of truncated Gaussian mixture Pl <x defined in (18.
Proof. Note that Theorem 24 and Theorem 26 can both be viewed two special cases of Hölder's
inequality: for any a, b 2 s.t. + b 1. we have
Enp (1 (1-0--(..00)
2
1
+
A i= ebr,
(I-E-V(tRO))
1
=EmP
[y[t; P,Q) 26
E/e ell,
+
1/8
(1- (1-E--
20 1/a
1
< Enp
Erp
llu(t:P.Q)
2 E]
5 E cat,
+
25

---

Theorem 24 corresponds to the case where a = 1. and Theorem 26 corresponds to the case where b 1. We can actually tune the parameters and if we can obtain any better bounds, have
ENP (1
2a
EE [6
(21)
and
( ck clt,
Etpp p
1
(.()) $]
s b0e
/ (r(), e e-bor dx
(22)
Simply combining the above inequalities leads to the final conclusion.
26

---

F
Proofs for Utility
E.
Overview
While one may be able to bound the false negative rate through similar techniques that we bound the false positive rate, i.c., applying the concentration inequalities, the guarantee may be loose. As formal, strict guarantee for FNDPy is not required, we provide a convenient heuristic of picking an appropriate A such that FNDPY approximately smaller than FP DPV.
For any mechanism M such that gest > poy we have
Pr DPV
DPV(M,E, 808)) False]
8m > 80st /T A
= Pr
= Pr fy
5y > gest/ /T - 8Y(c)= - A]
< Pr
8m
or (e) > ((1/T - 1/p) 8rst - -1)]
and in the meantime, if gost
< Tōy (E), we have
Pr 0%
80st / a
<
Pr
Ogc (x(E) -
Our main idea is to find A such that
M 8y (c) > 11/) gost ]
Pr
(5) < [
Pr OhC
In this way, we know that FNxc (s, gest; p) is upper bounded by O(8rst /r) for the same amount of samples we discussed in Section
Observe that ônc (or 81s with not too large 0) is typically a highly asymmetric distribution with a significant probability of being zero, and the probability density decreases monotonically for higher values. Under such conditions, we prove the following results:
Theorem 28 (Informal). When m 2
2y log(t/8 (8 we have A
3 _A1 6x(E)= - A Pr(on 8r(5)> Pr MC
The proof is deferred to Appendix F.2
Therefore, by setting A = 0.4 -1 (1/ gest, one can ensure that F p) is also (approximately) upper bounded by 6 /T). We empirically verify the effectiveness of such a heuristic by estimating the actual false negative rate. As we can see from Figure (b), the dashed curve is much higher than the two solid curves, which means that the false negative rate is a very conservative bound.
Remark 29 (For the halting case). In this section, we develop techniques for ensuring the false negative rate (i.e., the rejection probability) is around O()) when the proposed privacy parameter gest is close to the true 8. In the experiment, we use the state-of-the-ari FFT accountant to produce gest, which is very accurate we can see from Figure 1. Hence, the rejection probability in the experiment is around O(8), which means the probability of rejection is close to the probability of catastrophic failure for privacy.
If one is still concerned that the rejection probability is too large, we can further reduce the probability as follows: we two instances of EVR paradigm simultaneously; if both of the instances are passed, we randomly pick one and release the output. If either one of them is passed, we release the passed instance. It only fails when both of the instances fail. By running two instances of the EVR paradigm in parallel, the false positive rate (i.e., the final 8) will be only doubled, but the probability of rejection will be squared.
We can also introduce a variant of our EVR paradigm that better deals with the failure case: whenever different mechanism M' that is guaranteed to be (s, ( DDP
we face the "rejection",
27

---

(e.g., by adjusting the subsampling rate and/or noise multiplier in DP-SGD). Moreover, we use FFT accountant to obtain a strict privacy guarantee upper bound (E, 8 for the original mechanism M, where jest < Supp. We use PEN and pFp to denote the false negative and false positive rate of the privacy verifier used EVR paradigm. If the original mechanism M indeed (e, 8 )DD,, then for any subset S, for this augmented EVR paradigm M we have
Pr(M)(((D) E S] PEN Pr(M(D) E 5] + (1 PFN) ET
S PFN(C Pr(M(D') S] +0 + (1 - PEN)(E EI 5 +
E Pr[M (D') E S] &
If the original mechanism M is not (e, 8 DDD, then we have
Pr[Ma (D) E S] = PFP Pr(M(D) E S] + (1 PFP) Pr(M E S]
S pFp(e Pr(M(D') E S) + PuPP) + (1 - [pFp) Pr(M((D') E e + dea)) Se Pr(M (D') E S) + 8ust + PFP
Hence, this augmented EVR algorithm will be (E, 8 + PFP (8 - 8rat)), and if pFP is around gest, then this extra factor pFp (8upp -ess) will be very small. We can also udjust the privacy guarantee for M' such that the privacy guarantees for the two cases are the same, which can further optimize the final privacy cost.
28

---

F.2 Technical Details
In this section, we provide theoretical justification for the heuristic of setting A 0.4 (1/T - 1/p) gest
For notation convenience, throughout this section, we talk about Snc, but the same argument also applies to 818,0 with not too large 8, unless otherwise specified. We use (xc(x) to denote the density of 8bc at æ. Note that eNc (0) = oc.
We make the following assumption about the distribution of ŌNC- Assumption 30. Pr[oxc 0] 1/2.
While intuitive, this assumption is hard to analyze for the case of Subsampled Gaussian mecha- nism. Therefore, we instead provide a condition for which the assumption holds for Pure Gaussian mechanism.
Lemma 31. Fix a. When k/(2 < E, Assumption 30 holds.
Proof.
The PRV for the composition of k Gaussian mechanism is / 20 )
Pr[(1 e ) = 0] Pr S c)
which is clearly 2 1/2 when k/(2x²) S 8.
We also empirically verify this assumption for Subsampled Gaussian mechanism as in Figure 7 As we can see, the selected by our heuristic (the red star) has Pr Pr(ois, = 0) 1/2 which matches principle of selecting 0. The minimizes the analytical bound (which we going to in
practice) achieves Pr Pr(ois.e
0] 0.88 >> 0.5.
1.0
0.8
Pr[ōis. =
0.6
0.4
0.0
2.5
5.0
7.5
10.0
Figure We empirically estimate Pr Pr( 0) for the case of Poisson Subampled Gaussian mechanism. We q 10-3 star indicates the second moment for the value of selected by our heuristic in Definition 18 The blue star indicates the 0 that minimizes the analytical bound.
3, a 0.6, 1.5, k 100. (e) 7.7 10-6 6 in this case. The red
Our goal is to show that Pr (x) < - Pr(o (y > A+] for large m. For notation simplicity, denote = B|8mc] (y in the remaining of the section. We also denote
Po = Pr Pr(2pc= = -]
P(o,1) Pr(0 < 6xc
P(1.2) = Pr(8 < 5 S 28]
P(2.c0) = Pr( 28
Note that Po + P(o. + P(1.)) + P(2,0)) We also write Snck(a,)) and 8xc (a.0) indicate the truncated distribution of 8 on (a, b) and [a, b). respectively.
29

---

We first construct an alternative random variable dyc with the following distribution:
x. for x. ~ 62c|226
w.p. P(2,00)
a for (0c((0.6)
w.p. P(0.1)
6NC 28 x for (0.6)
(23)
w.p. P(0,1)
x for x oxc 2226 6
w.P. P(2,0))
w.p. 2(p(0.1) P(2,00)
This is valid probability due to Assumption 30 P(o,1) + P(2,00) 1 1o 1/22. The distribution of Eec is illustrated in Figure 8 Note that ône is a symmetric distribution with E[ōxc] =
28 1
28
Figure 8: Illustration for the density function of dwc (black curve indicates the density curve for ôNc. and red curve indicates the density curve for 81s,0).
Similar to the notation of 8ye, we write 8m
1 Σ
m
We show an asymmetry result for 5
i== KC
in terms of
30

---

Lemma 32. For any A E R, we have
Pr(ox-- - - Pr(ose Tm
8> A
(24)
Proof. Note that the ahove argument holds trivially when 0. For 2 use the induction argument. Suppose we have
Pr(o - < -
Pr 1r(omm-1 8 A'
(25)
for any A IR. That is,
Pr
(m - 1)8 < <m 1)
2 Pr
(+) NC
(m 1)5 > (m 1)4'
(26)
NC
1=1
for any A I..
Pr(o% - Pr
5() NC
md < -ma"
m
HC (m 1)5 + 3((m) 8 -m
Pr
1
Pr
(0) NC
(m - 1)6 < -m x
Pr Pr(Okmn) = x dz
2
Pr
ONC
(m
1)8 m * + Pr(oke 5 = æ/d2
Pr
7()) HC
(m
1)8 (5/1))
8) > md'
/ Pr
(5(m))
5) > m Pr
m-1
(m
1)
dx
xC
/ Pr
(m)) NNC
m
8 =m + Pr
Ovc
(m
1)d
dx
m
Pr
(m) NC
8 mn -1
Pr
50 MC
(m
1)6 = x
dx
(
md > mA
NC
8
where the two inequalities are due the induction assumption.
Now come back and analyze 8m by using Lemma
32
31

---

Pr
6 MC
8 Σ -
Pr
MC
yyc
NC
8 < -A'
Pr
S
Pr
NG
HH
8 -
|6Nc
8 S c
Pr
Pr
2 Pr
8yc S
Pr
N
Similarly,
Pr
cm HC
8
2
A
+c
Pr
NC
HC
O%c
8
+
Pr
HG
Pr
8
8
8
8
-
Pr
HC
Pr
8
+
2c
Overall, have
Pr
8yc
8 ---
2
mm
OHC
S
Pr
8
2
2c
(27)
for any A
R. Note that the above argument does not require 8m and h be correlated. To
maximize Pr
8m
8m
S c
sample dgp for given 8%z follows: for each ((1)
(0) 1. If
0, then let K
K
2. If 200) MC 0, then with probability P(2. po. output 26 - for x ~ 8wc (2.c0) with probability
P(o.1) Po output 25 x for x d (o. with probability (P(o.1) P(2. )/po output
Denote the random variable dain 8Bc 8pc It is not hard that E din
E E + 8 z
[kc By Bennett's inequality, with m 2 22 log(t/66 (T/ttt/ we have
Pr
NC
Jest
exp
A
1
Jest
we set c = O(A). Let = A then by setting
and A 22c (1/T 1/p) gost -.
we have A 0.4 (1/7 1/p) gest.
To summarize, when we set A with the heuristic, we have
7/8 gest
Pr
8 >
A
+2
2 (1
Jest
T T/8 gest
32

---

G Pseudocode for Privacy Accounting for DP-SGD with EVR Paradigm
In this section, we outline the steps of privacy accounting for DP-SGD with our EVR paradigm. Recall from Lemma T6 that for subsampled Gaussian mechanism with sensitivity C, noise variance Caa² and subsampling rate q. one dominating pair (P Q := (0, o²) and = g),V o²) qN(1, o²). Hence, for DP-SGD with & iterations, the dominating pair is the product distribution P = Pi x Ps and Q = Q ... x Qs where each P. and Q; follow the same distribution P and Q
Algorithm 4 Privacy Accounting for SGD with EVR Paradigm
I: Privacy Parameters for DP-SGD: number of mechanisms to be composed, noise multiplier, q subsampling rate, clipping ratio.
2:
3: // Step 1:
Estimate Privacy Parameter.
4: Obtain a privacy parameter estimate (e8) from DP accountant (e.g., FFT/GDP/MC accoun- tant). Set the smoothing factor т = 0.99 (one can also adjust the value of t according to the privacy guarantee and runtime requirements).
5:
6: // Step 2: Verify Privacy Parameter.
7:
8: // Step 2.1: Derive the required amount of samples for privacy verifi-
cation.
9: Compute the number of required samples m according Theorem 13 where the second moment upper bound y computed according to Corollary [22 for Simple MC estimator, or Theorem 23 for Importance Sampling estimator. Set (1 7)/2 and set A according to Theorem 14 utility guarantee.
11: // Step 2.2: Estimate privacy parameter with MC estimator.
If Simple MC estimator: Obtain i.i.d. samples (4,)m² 1m from P. Compute simple MC
estimate 8 = m Σ - (--),, with PRV samples yi log P(t.)
Qit.) 1...m..
13: If use Importance Sampling estimator: compute MC estimate according to Definition [8
15: // Step 3: Release according to verification result.
16: if < g A then release the result of DP-SGD.
17: else terminate program.
II can also be extended to the heterogeneous easily.
33

---

H Experiment Settings & Additional Results
H.1 GPU Acceleration for MC Sampling
MC-based techniques are well-suited for parallel computing and GPU accelcration due to their nature of repeated sampling. One can easily utilize PyTorch's ' CUDA functionalityy, e.g..
torch. randn (size- (k,m) ) cuda () ssigma+mu
to significantly boost the computational efficiency. Figure 9 (a) shows that when using NVIDIA A100-SXM4-80GB GPU, the execution time of sampling Gaussian mixture ((1 q W (0, o²)
(1(1, o²)) can be improved by 10 times compared with CPU-only scenario. Figure (b) shows the predicted runtime for different target false positive rates for 1000. We vary and set the 10-r that is greater than 6y) where E {1,5) and
target false positive rate as the smallest r is positive integer. We set jest 0.86y and T, P, A are set as the heuristics introduced in the previous sections. The runtime is predicted by the number of required samples for the given false positive rate. As we can see, even when we target at 10 10 false positive rate (which means that ~ 10 10), the clock time is still acceptable (around hours).
10c
GPU
109
CPU
104
Clock Time (s)
Clock Time (s)
107
10a
109
10
10
10
107
10
1013
10-10
10-7
10-1
(a)
Gaussian Mixture Sample
(b)
Figure 9: The execution time of sampling Gaussian mixture ((1 - g), (0) + (2((1, when
only using CPU and when using NVIDIA -100-SXM4-80GB GPU.
34

---

H.2
Experiment for Evaluating EVR Paradigm
H.2.1
Settings
For Figure & Figure
the FFT-based method has hyperparameter being set Eerror 10-10 For the GDP-Edgeworth accountant, we use the second-order expansion
10-3, Serror
and uniform bound, following 41
For Figure 4 (as well as Figure the BEiT is first self-supervised pretrained on ImageNet- -k and then trained finetuned ImageNet-21k, following the state-of-the-art approach in [34]. For DP-GD training, we set as 28.914, clipping norm as I, learning rate as 2, and we train for at most 60 iterations, and only finetune the last layer CIFAR-100.
H.2.2 Additional Results
- E (6) curve. We show additional results for a more common setting in privacy-preserving machine learning where one set target ô and try to find ( for different the number of individual mechanisms in the composition. We use y(k) to stress that the PRV Y is for the composition of k mechanisms. Such a scenario can happen when one wants to find the optimal stopping iteration for training a differentially private neural network.
Figure shows such result for Poisson Subsampled Gaussian where we set subsampling rate 0.01, 2. and 5 10-5, We set Eerror 10 Serror 10 10 for the FFT method. The estimate in this case is obtained by fixing gest = 7ō and find the corresponding estimate for e through FFT-hased method [99. As
see, the EVR paradigm achieves much tighter privacy analysis compared with the upper bound derived by FFT-based method. The runtime privacy verification in this case 15 minutes for all ks.
0.7
0.6
0.5
0.4
0.3
0.2
FFT-upp
0.1
FFT- EVR (T=
250
500
750
1000
Figure 10: k + (v) (0) curve for Poisson Subsampled Gaussian mechanism for subsampling rate 0.01, = 2, and 10-5 When running on an NVIDIA A A100-SX44-80BB GPU, the runtime of privacy verification is < 15 minutes.
Privacy-Uttilit Tradeoff. We show additional results for the privacy-utilit tradeoff' curve when finetuning seageeect-rettrinee BEiT on CIFAR100 dataset with DP stochastic gradient descent (DP- SGD). For DP-SGD training, set 5.971, clipping norm 1, learning rate as 0.2, momentum as 0.9, batch size 4096, and we train for at most 360 iterations (30 epochs). We only finetune the last layer on CIFAR-100.
tradeoff compare with the traditional upper bound method. In Figure TI (b), we show the runtime of DP verification when (1 + r)/2 2/2 and we set A according to Theorem 14 (which ensures EVR's 's failure probability is negligible). The runtime is estimated
As shown in Figure II (a), the EVR paradigm provides a better
NVIDIA ATW0SXM4-800BB GPU. As we can see, it only takes few minutes for privacy verification, which is short compared with hours of model training.
35

---

35
FFEupp FET-EVR 0.95)
FFT-EVR (T= 0.95)
Test Error (%%
Runlime (min)
12
25
10
20
8
10
(8)
0.3
0.5
0.6
0.7
0.8
(b)
0.2
0.4
0.8
1.0
Figure 11: (a) Utility-privacy tradeoff curve for fine-tuning ImageNet-pretraiine BEiT on CI- FARI00 when 5 10-12 with DP-SGD. We follow the training hyperparameters from 64 (b)
Runtime of privacy verification in the EVR paradigm. For fair comparison, we set p = (1 7)/2 and set A according to Theorem 14. which ensures EVR's failure probability is around 066). For (b), the runtime is estimated on an NVIDIA A A100-SXM4-80GB GPU.
H.3
Experiment for Evaluating MC Accountant
H.3.1
Settings
Evaluation Protocol. We use ( to stress that the PRV Y is for the composition of k Poisson Subsampled Gaussian mechanisms. For the offline setting, we make the following two kinds of plots: (1) the relative error in approximating + (s) (for fixed k). and (2) the relative error in + ay (8) (for fixed 8), where ( (6) is the inverse of ay (e) from 2 For the online setting, we make the following two kinds of plots: (1) the relative error in approximating k + ( (for fixed 8), and (2) + cumulative time for privacy accounting until kth iteration.
MC Accountant. We use the importance sampling technique with the tilting parameter being set according to the heuristic described in Definition [8]
Baselines. We compare MC accountant against the following state-of-the-art DP accountants with the following settings:
The state-of-the-art FFT-based approach 19 The setting of Curror and Serror specified in the next section.
CLT-based GDP accountant
GDP-Edgeworth accountant with second-order expansion and uniform bound.
The Analytical Fourier Accountant based on characteristic function [4], with double quadrature approximation this is the practical method recommended in the original paper.
H.3.2
Additional Results for Online Accounting
Figure and show the online accounting results for 6.) (0.5, 10 10-3) 3) and (a, 9) = (0.5. 10
10 10 respectively. For the setting of (o, d. (0.5, 10 1,000100033 10-3). can that
the MC accountant achieves a comparable performance with a shorter runtime. For the setting of (a, d) (0.5, 10 13 10-3) 10-3),
see that the MC accountant achieves significantly better performance compared to the state-of-the-ar FFT accountant (and again, with a shorter runtime). This showcases the MC accountant's 's efficiency and accuracy in online setting.
36

---

FFT
GDP
GDP-Edgeworth
MC (IS)
Relative Error in Estimating E
Cumulative Runtime
10"
10a
Relative Error
10
Time (s)
10
109
10-1
10-
10-2
(a)
250
500
750
1000
(b)
250
500
750
1000
Number of Compositions k
Number of Compositions k
Figure 12: Experiment for Composing Subsampled Gaussian Mechanisms in the Online Setting with hyperparameter (o, 6, q) = (0.5, 10-3; 10100-), ). (a) Compares the relative error in approximating A sy (d). The error bar for MC accountant is the variance taken over 5 independent runs. Note that the y-axis is in the log scale. (b) Compares the cumulative runtime for online privacy accounting. We did not show AFA
44 as it does not terminate in 24 hours.
FFT
GDP
GDR-Edgeworth
MC
Relative Error in Estimating
Cumulative Runtime
10a
10a
10a
Relative Error
10-2
102
Time (s)
10
101
10-1
109
10-5
10-1
10
10-2
250
500
750
1000
250
500
750
1000
Number of Compositions k
Number of Compositions
Figure 13: Experiment for Composing Subsampled Gaussian Mechanisms in the Online Setting with hyperparameter (a, q) (0.5, 10- 10 10-3). (a) Compares the relative error in approximating k + (0). The error bar for MC accountant is the variance taken over 5 independent runs. Note that the y-axis is in the log scale. (b) Compares the cumulative runtime for online privacy accounting. We did not show AFA as it does not terminate in 24 hours.
37

---

H.3.3 Additional Results for Offline Accounting
In this experiment, we set the number of samples for MC accountant as 10", and the parameter for FFT-based method as Serror 10-3 -0-3,,0 Serror 10-10. The parameters are controlled so that the MC accountant is faster than FFT-based method, as shown in Table 1 Figure 14 (a) shows the offline accounting results for + ay when we set (a, q. k) = (0.5, 10 1000). As we can see, the performance of MC accountant is comparable with the state-of-the-an art FFT method. In Figure [5] (a), we decreases q to 10-5, Compared against baselines, MC approximations are significantly more accurate for larger compared with the FFT accountant, Figure (b) shows the offline accounting results for + g (6) when we set (a, q, 6) = (0.5, 10 10 5). Similarly, MC accountant performs comparably as FFT accountant. However, when we decrease q to 10 and å to 10 14 (Figure 15 (b)), MC accountant significantly outperforms FFT accountant. This illustrates that MC accountant performs well in all regimes, and is especially more favorable when the true value of 6y (e) is tiny.
APA
FFT
CDP
GDP-Edgeworth
MC (IS)
Relative Error in Estimating 5
Relative Brror in Estima ting
10?
10
Relative Error
100
Relative Error
10-2
10-2
10-
10-4
10
5.0
7.5
10.0
600 800
1000
(a)
(b) Number of Compositions k
Figure 14: Experiment for Composing Subsampled Gaussian Mechanisms: (a) Compares the relative
eтror in approximating Σ + (y()) where we set 0.5. A: 1000, q 10 (b) Compares the relative error in k + Ey (6) where we set σ = 0.5, 8 = 10 10 The eгror bar for MC accountant is the variance taken over independent runs. Note that the y-axis is in the log scale.
Table 1: Runtime for k: 1000.
AFA
GDP
GDP-E
FFT MC-IS
10
APA
PFT
GDP
GDP-Edgeworth
MC (IS)
Relative Error Eslimaling
Relalive Error Estinating
102
10a
10
101
Relative Error
10a
Relative Errrr
10a
10-1
10-1
10-2
10-1
10
10-4
10-4
(a)
(b)
800 1000
Number of Compositions k
Figure 15: Experiment for Composing Subsampled Gaussian Mechanisms: (a) Compares the relative
error in approximating - 8yms (E) where relative error in & + (ō) where we set = 0.5, = 10
0.5. k: 100, q 10-5, (b) Compares the 14 14
10-5 The error bar for MC
accountant is the variance taken over independent runs. Note that the y-axis is in the log scale. The curves for AFA, GDP and GDP-Edgeworth are overlapped with each other.
38


Reviews:
[{"review_id": "ypyIDPVLWU", "reviewer": "Reviewer_D6i7", "summary": "The authors propose EVR framework for privacy accounting. The core idea is to estimate the privacy budget, verify whether the budget is approximately met, and then decide whether to release the result or halt. The workhorse is a Monte-Carlo verifier (also used as an accountant through binary search). The empirical evaluation shows significant improvement over existing techniques, especially in the large epsilon/small delta regime.", "questions": "Any idea on how to deal with halting in practical usage?", "limitations": "Yes", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. The authors propose a novel framework for privacy accounting: EVR. By trading off a small probability that the program halts with privacy budget, the authors manage to get a tighter privacy profile curve at larger epsilon/smaller delta regime.\n2. The authors verify the proposed framework empirically and showcase the advantage of EVR.", "weaknesses": "1. One downside of the proposed approach is that there is a probability that the mechanism halts with a privacy budget cost. To get a tighter epsilon, you need to take the risk that you get nothing. Although this seems to be reasonable trade-off, it can be a problem in practical use case. More discussion should be put on this.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the very positive feedback!\n\n**Q [How to deal with halting in practical usage?]**\n\n**A:** In Section 4.4, we developed techniques for ensuring the false negative rate (i.e., the rejection probability) is around O(delta) when the proposed privacy parameter delta^est is close to the true delta. In Section 6.1’s experiment, we use the state-of-the-art FFT accountant to produce delta^est, which is very accurate as we can see from Figure 1. Hence, the rejection probability in the experiment is around O(delta), which means the probability of rejection is close to the probability of catastrophic failure for privacy.\n\nIn addition, if one is still concerned that the rejection probability is too large, we can further reduce the probability as follows: we run two instances of EVR paradigm simultaneously; if both of the instances are passed, we randomly pick one and release the output. If either one of them is passed, we release the passed instance. It only fails when both of the instances fail. By running two instances of the EVR paradigm in parallel, the false positive rate (i.e., the final $\\delta$) will be only doubled, but the probability of rejection will be squared. \n\nWe can also introduce a variant of our EVR paradigm that better deals with the failure case: whenever we face the \"rejection\", we run a different mechanism $M’$ that is guaranteed to be $(\\epsilon, \\delta^{(est)})$-DP (e.g., by adjusting the subsampling rate and/or noise multiplier in DPSGD). Moreover, we use FFT accountant to obtain a strict privacy guarantee upper bound $(\\epsilon, \\delta^*)$ for the original mechanism $M$, where $\\delta^{(est)} < \\delta^*$. We use $p_{fp}$ and $p_{fn}$ to denote the false positive and false negative rate of the underlying DP verifier. \n- If the original mechanism $M$ is indeed $(\\epsilon, \\delta^{(est)})$-DP, then for any subset $S$ we have \n\n$\\Pr[EVR(D) \\in S] = p_{fn} * \\Pr[M(D) \\in S] + (1-p_{fn}) * \\Pr[M’(D) \\in S] $\n\n$\\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\     \\le p_{fn} * (e^\\epsilon \\Pr[M(D’) \\in S] + \\delta^{(est)} ) + (1-p_{fn}) * (e^\\epsilon \\Pr[M’(D’) \\in S] + \\delta^{(est)}) $\n\n$\\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\  \\le e^\\epsilon \\Pr[EVR(D) \\in S] + \\delta^{(est)}$\n\n- If the original mechanism $M$ is not $(\\epsilon, \\delta^{(est)})$-DP, then we have \n\n$\\Pr[EVR(D) \\in S] = p_{fp} * \\Pr[M(D) \\in S] + (1-p_{fp}) * \\Pr[M’(D) \\in S]$\n\n$\\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\  \\le p_{fp} (e^\\epsilon \\Pr[M(D’) \\in S] + \\delta^*) + (1-p_{fp}) * (e^\\epsilon \\Pr[M’(D’) \\in S] + \\delta^{(est)})$\n\n$\\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\  \\le e^\\epsilon \\Pr[EVR(D) \\in S] + \\delta^{(est)} + p_{fp} * (\\delta^* - \\delta^{(est)})$\n\nHence, this augmented EVR algorithm will be $(\\epsilon, \\delta^{(est)} + p_{fp} * (\\delta^*-\\delta^{(est)}))$-DP, and if $p_{fp}$ is around $\\delta^{(est)}$, then this extra factor $p_{fp} * (\\delta^*-\\delta^{(est)})$ will be very small. We can also adjust the privacy guarantee for $M’$ such that the privacy guarantees for the two cases are the same, which can further optimize the final privacy cost. \n\nWe have added the above discussion to the paper. \n"}, {"review_id": "qAMxnsYB9g", "reviewer": "Reviewer_UAod", "summary": "The paper proposes a privacy accounting method called estimate-verify-release (EVR), whose basic principle is to convert an estimate of a privacy parameter into a formal privacy guarantee. The mechanism works by verifying whether the estimated privacy guarantee holds, and then releasing the query output depending on the verification result. The paper develops a Monte-Carlo-based verifier for this paradigm. The overall accountant is broadly applicable and is shown to give a tighter privacy-utility tradeoff than existing baselines.", "questions": "Nothing at the moment.", "limitations": "NA", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The mechanism is applicable broadly, in particular to important DP algorithms such as DP-SGD (that is, the subsampled Gaussian mechanism). It exploits the fact that existing work provides good privacy loss estimates and converts these estimates into a formal paradigm for ensuring differential privacy. The method is shown to beat a strong baseline, namely the FFT-based accountant from [19].", "weaknesses": "The paper places a lot of emphasis on the fact that we can't naively use an estimated privacy parameter as the truth, because DP is a strict guarantee, and this makes perfect sense. But then in the analysis and implementation of the accountant there are some steps of the new accountant that are not made completely rigorous, such as the number of Monte Carlo samples. Or, in Theorem 13 there is a nu parameter that is not known. So my suggestion is to write a fully formal version of the accountant for DP-SGD in the main body to show that the paradigm can indeed be applied fully rigorously.\n\nIn addition, it would be good to see at least one more experiment showing the same comparison as Figure 5. In Figure 5 the gains of MC over FFT are not clear for a small number of compositions. So it would be good to see if the comparison of Figure 5 is robust and generalizes to different problem settings.\n\nA few minor comments:\n- In the Conclusion, you say \"allowing safe privacy parameter estimates *without* provable assurance\"?\n- The Figures don't seem to be in vector format and are blurry if zoomed in.\n- Typo in Line 132, \"privacy loss random variable *is* ...\" (right now there's no verb in the main clause)\n- In Line 180, say where rho takes values.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the very positive feedback!\n\n**Q1 [Fully formal version of DP-SGD with EVR paradigm]** *“The paper places a lot of emphasis on the fact that we can't naively use an estimated privacy parameter as the truth, because DP is a strict guarantee, and this makes perfect sense. But then in the analysis and implementation of the accountant there are some steps of the new accountant that are not made completely rigorous, such as the number of Monte Carlo samples. Or, in Theorem 13 there is a nu parameter that is not known. So my suggestion is to write a fully formal version of the accountant for DP-SGD in the main body to show that the paradigm can indeed be applied fully rigorously.”*\n\n**A:** We thank the reviewer for the very concrete and useful suggestion. In the updated paper, we have included a pseudo-code outlining the full steps of DP-SGD with the EVR paradigm, as well as a theorem stating that the algorithm satisfies DP guarantee (**see Q1 in global response and Algorithm 4 in the rebuttal’s PDF**). \n\nFor ***“in Theorem 13 there is a nu parameter that is not known”:*** $\\nu$ is the upper bound for the second moment of the MC estimator, which we discuss how to bound it (which can be explicitly computed) for $\\delta_{SMC}$ and $\\delta_{IS}$ in the last paragraph of Section 4.3 and Appendix E. \n\n**Q2 [More experiment showing the same comparison as Figure 5]** *“In addition, it would be good to see at least one more experiment showing the same comparison as Figure 5. In Figure 5 the gains of MC over FFT are not clear for a small number of compositions. So it would be good to see if the comparison of Figure 5 is robust and generalizes to different problem settings.”*\n\n**A:** Thanks for the suggestion! We have conducted additional experiment in Appendix G.3.2, and the results are shown in **Figure 12 and 13 in the rebuttal’s PDF (see Q2 in Global response)**. The experiment settings follow exactly the same as Figure 5. Figure 12 and 13 show the online accounting results for $(\\sigma, \\delta, q) = (0.5, 10^{-5}, 10^{-3})$ and $(\\sigma, \\delta, q) = (0.5, 10^{-13}, 10^{-3})$, respectively. For the setting of $(\\sigma, \\delta, q) = (0.5, 10^{-5}, 10^{-3})$, we can see that the MC accountant achieves a comparable performance with a shorter runtime. For the setting of $(\\sigma, \\delta, q) = (0.5, 10^{-13}, 10^{-3})$, we can see that the MC accountant achieves significantly better performance compared to the state-of-the-art FFT accountant (and again, with a shorter runtime). This further showcases the MC accountant's efficiency and accuracy in online setting.\n\n**Q3 [Typos & Grammar & Blurred Images]** \n\n**A:** Thanks a lot for the catch! We have fixed the typos and grammars in the paper. For the comment about blurred image, we checked all of the images and they all look clear even after zoomed in on our side. Could you kindly point out the specific figure you are talking about? We are more than happy to change it!"}, {"review_id": "fPHftGbJgy", "reviewer": "Reviewer_hkgF", "summary": "Authors introduce a new privacy accounting method to characterize the privacy loss random variable. The work reduce the classical privacy accounting problem into mean estimation problem following the previous work and give a Monte Carlo solution.  The work provides detailed analysis of the proposed method and its utility and also give some common distribution to show the effectiveness and performance theoretically. The numerical studies also show the correctness and practicability of the method in the real privacy accounting tasks.", "questions": "/", "limitations": "Yes", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": " Pros: \n1. The analysis for the proposed method is detailed and the writing is friendly to follow with a detailed preliminary.\n2. The proposed tool works better than the compared existing accounting tools like CLT and FFT-based methods.\n3. The fast speed and the online implementation show some potential for the method used in privacy accounting applications.\n\n", "weaknesses": "Actually, I have reviewed the paper in ICML. I think the paper has fixed almost the problem in the former cycle. The only problem I still keep is about whether the method will suffer from the dimension curse when deriving the prv samples for a general distribution. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer (again) for the very positive feedback!\n\n**Q** *“The only problem I still keep is about whether the method will suffer from the dimension curse when deriving the prv samples for a general distribution.”*\n\n**A:** This is a great comment that actually points to one of the important benefits of our approach. The cost of our approach would not increase (in terms of number of samples) even if the dominating pair is supported in a high dimensional space. For Monte Carlo estimate $\\delta = 1/m \\sum_{i=1}^m (1-e^{\\varepsilon - y_i})_+$, $y_i$ is the sampled log density ratio, and hence it is a scalar value. We can now see from Hoeffding’s inequality that the expected error rate of estimation is $O(1/\\sqrt{m})$ which is independent of the dimension of the support set of dominating distribution pairs. This means that the number of samples we need to ensure a certain confidence interval is independent of the dimension. However, we should also note that although the number of samples does not change, the sampling process itself might be more costly for higher dimensional spaces. But one would expect that to grow at most polynomially. We will clarify this in the paper."}, {"review_id": "YMGLJc6wxE", "reviewer": "Reviewer_eMPH", "summary": "The authors consider the problem of bounding the privacy loss for a composition of DP mechanisms. This problem is well-studied in the literature and the particular setting here is when the mechanisms are Gaussian or have Gaussian sub-routines but the privacy loss is measured through the original (approximate) DP definition. This is particularly difficult for Gaussians because of the sub-exponential tail and other work has created new definitions better suited to the Gaussian mechanism. While the privacy loss random variable may be challenging to work with under the original DP definition, it can still be efficiently sampled from, so an estimate of the expected privacy loss can be computed efficiently. The authors show that these estimates are quite accurate with high probability and leverage this guarantee to turn the estimate into a formal privacy bound (or failure to run with tiny probability). As a result, for certain settings the authors give improved privacy composition bounds over the previous work.", "questions": "$\\textit{All questions were answered by the authors}$\n\nWhat's the runtime for the 'Exact' method compared to FFT or EVR? It was a bit confusing why that couldn't be used given that it's the ideal privacy parameter to output.\n\nFrom the experimental result with DP-SGD, it looks like MC beats FFT even with more standard delta settings. Does this hold more generally? Why was this not the result emphasized in the intro instead of the gaussian mechanism composition? Are the curves in figure 4 identical but shifted? So basically using MC accounting you compute a better epsilon at each epoch?", "limitations": "The limitations were appropriately discussed", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "1. Clever new technique to use composition privacy loss estimates instead by rejecting the estimate with low probability.\n\n2. Significant technical work that combines a variety of techniques.\n\n3. Their work extends nicely to the subsampled Gaussian mechanism for DP-SGD.\n\n4. Empirical testing run in a variety of settings for both Gaussian mechanism and DP-SGD.\n\n5. Improves upon previous work for DP composition in a reasonably important setting.", "weaknesses": "Remark 6 feels exaggerated. For the settings considered in this paper, the delta parameter is just a result of concentration bounds and sub-exponential tails of Gaussians, not the probability of a catastrophic data breach. Unless the authors know of examples with delta <= 10^{-10}, I've only seen practical applications with delta at minimum 10^{-7} and 10^{-6} is most common. Of course there are privacy advocates that will always push for more privacy, but they are also likely to further push for \"pure\" differential privacy in which composition is easy and Laplace mechanism must be used instead.\n\n$\\textit{The authors pointed to the discussion here I missed, so strike this comment}$\nThere are privacy definitions better suited to Gaussians that have become very common both in practice and in the literature that allow for easier analysis and make this more difficult accounting less necessary (though still interesting).\n\n$\\textit{The authors adequately addressed this in the rebuttal}$\nThe improvement in epsilon for composition of the Gaussian mechanism over the previous work is quite small (<1%) for their empirical study (figure 5).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive comments!\n\n**Q1 [The Importance of Privacy Accounting in Regime of small $\\delta$]** \n\n**A:** **Regarding the common rule of setting $\\delta = 1/n$:** Setting $\\delta$ around $1/n$ implies a maximum $1/n$ likelihood of a privacy guarantee failing for an individual. With a basic union bound, this offers no assurance that the privacy won't fail for everyone in the dataset. Mainstream DP textbooks advocate for a \"cryptographically small\" $\\delta$, specifically, $\\delta < n^{-\\omega(1)}$ [[1]'s page 25, [2]'s page 9]. The current literature tends to choose a higher value of $\\delta$ for a decent utility. Our Remark 6 is intended to remind the community about the importance of using a smaller $\\delta$. While it still requires a lot of effort for achieving a good privacy-utility tradeoff even for the current choice of $\\delta$, it is important to keep such a goal in mind. \n\nAdditionally, recent literature [3] in DP foundation models uses a $\\delta$ around $2*10^{-9}$. We anticipate $\\delta<10^{-10}$ will become necessary given the trend of using large-scale datasets.\n\n**Our EVR algorithm has improvement when $delta=10^{-5}$ too**. While the improvement for bounding $\\delta$ is barely visible when $\\delta$ is around $10^{-5}$, the corresponding improvement for $\\varepsilon$ can in fact be significant if we align $\\delta$ to be the same for the EVR and the original FFT accountant. For example, in Figure 4 we obtain around 0.1 improvements in $\\varepsilon$, which lead to around 0.8% accuracy improvement in the privacy-utility tradeoff. Figure 10 in Appendix shows $\\varepsilon$-$k$ curves when fixing $\\delta = 10^{-5}$. We can see that there’s a non-trivial improvement in $\\varepsilon$. \n\n[1] Dwork and Roth. \"The algorithmic foundations of differential privacy.\"\n\n[2] Vadhan, Salil. \"The complexity of differential privacy.\"\n\n[3] Yu et al. “ViP: A Differentially Private Foundation Model for Computer Vision”\n\n\n\n**Q2.** *“There are privacy definitions better suited to Gaussians ...”*\n\n**A:** May we ask the specific privacy definition that *“suited to Gaussians”* the reviewer is referring to? If the reviewer is referring to GDP or RDP (zCDP), we have already shown the disadvantage of the privacy accounting techniques based on these two alternative privacy notions in Figure 1:\n\n**GDP-based accountant:** We can see that GDP accountant completely fails due to the relatively small number of composed mechanism (1200). The original paper [1]’s Figure 3 also shows that GDP's bound is very loose when $m$ is relatively small.\n\n**RDP-based accountant (Moment accountant):** We can see that the Moment Accountant (MA) in Figure 1 is sub-optimal for the entire regime of $\\delta$. Moment Accountant is sub-optimal even for the Gaussian mechanism due to the lossy RDP-DP conversion [2]. \n\n[1] Analytical composition of differential privacy via the edgeworth accountant. arXiv 2022.\n\n[2] Optimal accounting of differential privacy via characteristic function. AISTATS 2022.\n\n\n**Q3** “The improvement in epsilon for composition of the Gaussian mechanism over the previous work is quite small (<1%) for their empirical study (figure 5).”\n\n**A:** While we agree the absolute improvement is small, we would like to stress that **(1)** Even a slightly more accurate estimation of $\\varepsilon$ could result in hundreds of additional training iterations in DP-SGD, which can lead to higher utility; **(2)** Figure 5 aims to illustrate that MC accountant is **both** more accurate and efficient. In other words, MC accountant can achieve a better performance while being around 5 times faster than FFT. \n\nFor completeness, we also tune the hyperparameter ($\\varepsilon_{error}$) of the FFT accountant to adjust the runtime between FFT and MC accountant to be closer (by setting $\\varepsilon_{error}=0.4$ while keeping all other hyperparameters the same). The result is shown in **Q3 in global response & Figure 14 in rebuttal’s PDF**. As we can see, the error of FFT is larger in this case. \n\n**Q4 [How does the `exact’ curve being computed in Figure 1 and 3(a)?]**\n\n**A:** In Figure 1 and 3(a), the “exact” curve can be analytically derived since it’s the composition of pure Gaussian mechanisms (e.g., see [1]’s Equation (10)). This means that the exact $(\\varepsilon, \\delta)$ curve can be analytically computed, and the composition of pure Gaussian mechanisms mainly served as a toy example for easier performance comparison between different DP accountants. This is a common experiment strategy in the prior literature (e.g., [1]’s Figure 2, [2]’s Figure 2). \n\n[1] Numerical composition of differential privacy. NeurIPS 2021\n\n[2] Connect the Dots: Tighter Discrete Approximations of Privacy Loss Distributions. PETS 2022.\n\n**Q5 [EVR also has improvement on standard $\\delta$ setting?]** *“From the experimental ... at each epoch?”*\n\n**A:** In Figure 4, we are comparing between FFT accountant and the FFT accountant augmented with EVR paradigm. That is, we are essentially comparing between FFT accountant’s \"upper bound\" and \"estimate\" for epsilon by aligning $\\delta$ to be the same, which makes the curves look identical but shifted. In Figure 1, while the improvement for bounding $\\delta$ can be barely visible when delta is around $10^{-5}$, the corresponding improvement for $\\varepsilon$ can in fact be significant if we align $\\delta$ to be the same for the EVR and the original FFT accountant. Hence, in Figure 4 we obtain around 0.1 improvements in $\\varepsilon$, which lead to around $0.8\\%$ accuracy improvement in the privacy-utility tradeoff curve. Additionally, Figure 10 in Appendix shows $\\varepsilon$-$k$ curves when fixing $\\delta = 10^{-5}$. We can see that there’s a non-trivial improvement in $\\varepsilon$. \n\nWe thought Figure 1 is better for illustrating the failure case of “strict upper bound”; for revision, we have further emphasized the improvement of EVR at the regime of $\\delta=10^{-5}$ in the Introduction."}]

Author rebuttal:
We thank all of the reviewers for their detailed and valuable comments. We are pleased that all the reviewers expressed a positive view of our work! We considered the reviews carefully and modified our paper accordingly. We have answered other questions in the individual responses. Here’s a summary of the contents in the submitted PDF:

**Q1 (for Reviewer UAod) [Fully formal version of DP-SGD with EVR paradigm]**

**A:** We thank Reviewer UAod for the very concrete and useful suggestion. Here, we additionally outline the full steps of privacy accounting for DP-SGD with our EVR paradigm through pseudo-code in **Algorithm 4 in Rebuttal’s pdf**. Recall from Lemma 16 that for subsampled Gaussian mechanism with sensitivity $C$, noise variance $C^2 \sigma^2$, and subsampling rate $q$, one dominating pair $(P, Q)$ is $Q := N(0, \sigma^2)$ and $P := (1-q) N(0, \sigma^2) + q N(1, \sigma^2)$. Hence, for DP-SGD with $k$ iterations, the dominating pair is the product distribution **P** $ := P_1 \times \ldots \times P_k$ and **Q** $:= Q_1 \times \ldots \times Q_k$ where each $P_i$ and $Q_i$ follow the same distribution as $P$ and $Q$ (It can also be extended to the heterogeneous case easily). 

We have also included the following corollary in the paper so that the paradigm can indeed be applied fully rigorously.

**Corollary:** The Step 2-3 in Algorithm 4 is $(\varepsilon, \delta^{est}/\tau)$-DP. 

The corollary directly follows from Theorem 9 in the paper. 

**Q2 (for Reviewer UAod) [More experiments for evaluating MC accountant in online setting]**

**A:** Thanks for the suggestion! We have conducted additional experiment in Appendix G.3.2, and the results are shown in **Figure 12 and 13 in the rebuttal’s PDF**. The experiment settings follow exactly the same as Figure 5. Figure 12 and 13 show the online accounting results for $(\sigma, \delta, q) = (0.5, 10^{-5}, 10^{-3})$ and $(\sigma, \delta, q) = (0.5, 10^{-13}, 10^{-3})$, respectively. For the setting of $(\sigma, \delta, q) = (0.5, 10^{-5}, 10^{-3})$, we can see that the MC accountant achieves a comparable performance with a shorter runtime. For the setting of $(\sigma, \delta, q) = (0.5, 10^{-13}, 10^{-3})$, we can see that the MC accountant achieves significantly better performance compared to the state-of-the-art FFT accountant (and again, with a shorter runtime). This further showcases the MC accountant's efficiency and accuracy in online setting.

**Q3 (for Reviewer eMPH) [Additional experiments which increase the runtime for FFT accountant]**

**A:** Figure 5 aims to illustrate that MC accountant is **both** more accurate and efficient. In other words, MC accountant can achieve a better performance while being around 5 times more efficient than FFT. To better illustrate the advantages of MC accounting over the FFT accountant, we tune the hyperparameter ($\varepsilon_{error}$) of the FFT accountant so that the runtime of FFT and MC accountant are closer to each other. Specifically, we set $\varepsilon_{error}=0.4$ while keeping all other hyperparameters to be the same. The result is shown in **Figure 14 in the rebuttal’s PDF**. As we can see, the improvement of the MC accountant over the FFT accountant is larger in this case. 

Meta-review: There was a consensus among reviewers to accept this paper. The proposed approach is a nice, principled and useful addition to the privacy accounting literature, which gives tighter bounds than existing methods while being reasonably efficient. Therefore, I recommend acceptance.
Decision: Accept (poster)