Numerical Composition of Differential Privacy
Authors: Sivakanth Gopi
Yin Tat Lee
Lukas Wutschitz
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: Differential Privacy
Composition

Abstract: We give a fast algorithm to compose privacy guarantees of differentially private (DP) algorithms to arbitrary accuracy. Our method is based on the notion of privacy loss random variables to quantify the privacy loss of DP algorithms. The running time and memory needed for our algorithm to approximate the privacy curve of a DP algorithm composed with itself $k$ times is $\tilde{O}(\sqrt{k})$. This improves over the best prior method by Koskela et al. (2020) which requires $\tilde{\Omega}(k^{1.5})$ running time. We demonstrate the utility of our algorithm by accurately computing the privacy loss of DP-SGD algorithm of Abadi et al. (2016) and showing that our algorithm speeds up the privacy computations by a few orders of magnitude compared to prior work, while maintaining similar accuracy.


Numerical Composition of Differential Privacy*
Sivakanth Gopi Microsoft Research s sigopi@ms crosoft.
Yin Tat Lee
Lukas Wutschitz Microsoft
University of Washington
sintat@uw.en
lukas. www.chttttttiicoooott..omo
Abstract
We give fast algorithm optimally compose privacy guarantees of differentially private (DP) algorithms to arbitrary accuracy. Our method is based on the notion of privacy loss random variables to quantify the privacy loss of DP algorithms. The running time and memory needed for our algorithm to approximate the privacy curve of DP algorithm composed with itself l: times is O(Vk). This improves over the best prior method by [H22] which requires f2(k:1.5) running time. We demonstrate the utility of our algorithm by accurately computing the privacy loss of DP-SGD algorithm of Abadi et al. (ACG 16 and showing that our algorithm speeds up the privacy computations by a few orders of magnitude compared to prior work, while maintaining similar accuracy.
Introduction
Differential privacy (DP) introduced by (DMNS06] provides provable and quantifiable guarantee of privacy when the results of an algorithm run on private data are made public. Formally, we can define an (e, -eff)edrrrret private algorithm follows.
Definition 1.1 ((s,))-DD 5)-DP (DMNS06) 06)) An algorithm M is (e, 8DP if for any two neighboring databases D, D' differing in exactly one user and any subset S of outputs, we have Pr(M(D) E S] < e PriM((D) E S) 8
Intuitively, says that looking at the outcome of M, we cannot tell whether was run on or D'. Hence adversary cannot infer the existence of any particular in the input database, and therefore cannot learn any personal data of any particular user.
DP algorithms have an important property called composition. Suppose Mi and M2 are DP algorithms and say (D) (M, (D), M2(D)) i.e., M runs both the algorithms on D and outputs their results. Then M is also DP algorithm.
Proposition 1.2 (Simple composition 0K DL09
Mf (51, and Ma is (22,
DP. then M(D) = (2), is (51 F2, 61 + 82)-DP.
This also holds under adaptive composition (denoted by M = M2 M1), where M2 can look at both the database and the output of M, (here MD) = (M), (D))), It turns out that both compositions enjoy much better DP guarantees than this simple composition rule. Let M be an (e, 6D-DP algorithm and let M denote the (adaptive) composition of M with itself times. The naive composition rule shows that M is (kE, DDP This was significantly improved in (DRVIO)
Proposition 1.3 (Advanced composition [DVI DR 14). I is (e, 8)-DP, then M is (s', k8 -DP where
1 8
2k log
+ ke 1).
"Author ordering is alphabetical. accountant
Code is available
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Note that if O and å = o then M satisfies (1), Using simple composi-
vR
tion (Proposition 1.2). we can only claim that M is (O(VR), (D)) Thus advanced composition often results in v factor savings in privacy which is significant in practice. The optimal DP guar- antees for k-fold composition of an (e, 6)-D) algorithm were finally obtained by [OVI5]]. For composing different algorithms, the situation is more complicated. If M1, M2,.... MR are DP algorithms such that M, is (ei, 6:D- then it is shown by [MV16] that computing the exact DP guarantees for M M1 M2 o Mr is #P-complete. They also give an algorithm to approximate the DP guarantees of M to desired accuracy vj which runs in
h A- + ò
17
time where E = (E Ea)/k If each E, ~ 1 (so that M will satisfy reasonable privacy guarantees by advanced composition), then the running time is 0(12-55 /n).
vk
In most situations, DP algorithms come with collection of (e,6)-DP guarantees, i.e., for each value of e, there exists 8 such that the algorithm is (e, DD...
Definition 1.4 (Privacy curve). A DP algorithm M said to have privacy curve ò R + [0, 1], if for every E R. M is (()
For example the privacy curve of a Gaussian mechanism (with sensitivity and noise scale σ) is given by ((e) = ① (-ea + 1/2r) - Φ (-ea- - 1/2rr where ((-) is the Gaussian CDF [BW18]. Suppose we want to compose several Gaussian mechanisms, which (s, 6)-DP guarantee should we choose for each mechanism? Any choice will lead suboptimal DP guarantees for the final composition. Instead, we need a way to compose the privacy curves directly. This was suggested through the use of privacy region in [KOV15] and explicitly studied in the f-DP framework of DRSI9. f-DP is dual way (and equivalent) to look at the privacy curve 8(E).
Independently, an algorithm called Privacy Buckets for approximately composing privacy curves using the notion was initiated in [M118] This algorithm depends on the notion of Privacy Loss Random Variable (PRV) [ whose distribution is called Privacy Loss Distribution (PLD). For any DP-algorithm, one can associate PRV and the privacy curve of that algorithm can be easily obtained from the PRV. The really useful property of PRVs is that under adaptive composition, they just add up: the PRV Yf the composition M M1 o M2 o...... o Mg is given by Y = ー Y; one find the distribution of Y by the convolution of
where Y; is the PRV of - the distributions of Y1, Y2,.... YE. In an important paper, [KJH+20] proposed that one can speed up the convolutions using Fast Fourier Transform (FFT). Explicit error bounds were obtained for the approximation obtained by their algorithm in KJH+200 KJPH2] KH21]. The running time of this algorithm was analyzed in [KH21) where it was shown that the privacy curve (M( of M- = M1 M2 o ...... o M2 can be computed up to an additive error of Serror in time
he E
Jervor
if each algorithm M, is satisfies (E,, O)-DP and E - E.. Assuming that each E; R
VE
1
we
get Ö(k2.5 1 /8mmror) running time. Note that this is slightly worse than ( where the denominator is the multiplicative error in 8Mr When composing the same algorithm with itself for k times, the running time can be improved to Ô
R2c which is Ô
K when 7
Curror
Carror
Moments Accountant and Renyi DP In an influential paper where they introduce Differentially
Private Deep Learning, [ACG* 16) proposed a method called the Moments Accountant (MA) for giving an upper bound the privacy curve of a composition of DP algorithms. They applied their method to bound the privacy loss of differentially private Stochastic Gradient Descent (DP-SGI) algorithm which they introduced. Analyzing the privacy loss of DP-SGD involves composing the
ee has an additive error of r and 8 has a multiplicative error 1). *JJH+ 20) only state this for non- adaptive composition. In this paper we show how to extend this to adaptive composition well.
2

---

privacy curve of each iteration of training with itself & times, where k is the total of number of training iterations. Typical values of k range from 1000 300000 (such as when training large models like GPT3). The Moments Accountant was subsumed into the framework of Renyi Differential Privacy (RDP) introduced by [Mir17]. The running time of these accountants are independent of k, but they only give an upper bound and cannot approximate the privacy curve to arbitrary accuracy.
DP-SGD one of the most important DP algorithms in practice, because one can use it to train neural networks to achieve good privacy-vs-utilyy tradeoff's Therefore obtaining accurate and light privacy guarantees for DP-SGD is important. For example reducing ε from 1, can mean that one can train the network for 4 times more epochs while staying within the same privacy budget. Therefore DP-SGD is one of the main motivations for this work.
There are also situations when the PRVs do not have bounded moments and so Moments Accountant Renyi DP cannot be applied for analyzing privacy. An example of such algorithm is the DP-SGD-JL algorithm of [BGK-2) which uses numerical composition of PRVs to analyze privacy.
GDP Accountant [DSS99 BDLSI9] introduced the notion of Gaussian Differential Privacy (GDP) and used to develop an accountant for DP-SGD. The accountant is based on central limit theorem and only gives approximation to the true privacy curve, where the approximation gets better with k. But as we show in Figure 1
GDP accountant can significantly underreport the true epsilon value.
Several different notions of privacy were introduced for obtaining good upper bounds on the privacy curve of composition of DP algorithms such as Concentrated DP (CDP) [DR 16, [BS66), Truncated CDP [BRRSI8] etc. None of these methods can approximate the privacy curve of compositions to arbitrary accuracy. The notion f-DP introduced by [DRS19), allows for a lossless composition theorem, but computing the privacy curve of composition seems computationally hard and they do not give any algorithms for doing it.
1.1 Our Contributions
The main contribution of this work is a new algorithm with an improved analysis for computing the privacy curve of the composition of a large number DP algorithms.
Theorem 1.5 (Informal version of Theorem ).5)). Suppose M1, M2,.... Mj. are DP algorithms. Then
the privacy curve 8a of adaptive composition M M1 o M2 .... Mg can be approximated in time
Eupper 1 log kyy log Jerror
Eervor
where Eerror is the additive error in E, Servor is the additive error in 5 and Eupper is upper bound on max (ōeroor), max; EM, (Bonoo)
If each M; satisfies (v o(1) -DP, then by advanced composition (Proposition
1.3
set
k 1og I
Eupper O(1). Therefore the running time of our algorithm in this case is Ô
We
Servor
can save a factor of k, when we compose the same algorithm with itself is times.
Theorem 1.6. Suppose M a DP algorithm. Then the privacy curve 8 8zr (E) of M (adaptively) composed with itself k times can be approximated in time
Eupper 2 log k log
desvor
(4)
Eervoz
where Serror is the additive error in E, Servor is the additive error in d and Supper is upper bound on max {E (ferror) SM (eereo
Thus we improve the state-of-the-art by at least a factor of running time. We also note that algorithm improves the memory required by factor of k. See Figure ① for comparison of
"ear (6) is the inverse of (e).
3

---

our algorithm with that of [KPP22]] Also note that RDP Accountant (equivalent to the Moments Accountant) significantly overestimates the true E, while the GDP Accountant significantly underesti- mates the true e. In contrast, the upper and lower bounds provided by our algorithm lie very close to each other.
0.65
Our
0.6
2.5
0.55
0.5
0.45
0.4
1.5
Ours Upper GDP RDP
0.3
0.25
0.2
0.5
DPSCD steps
1500
(a) Our algorithm gives much closer upper and lower bounds on the true privacy curve compared to []РПЕT] under the same mesh size of 4 x 10 Our upper and lower bounds are nearly coinciding.
DPSGD
(b) Our algorithm can improve significantly over the RDP Accountant, We also see that GDP Ac- countant significantly underreport the true We have set Eerror = 0.1, Serror = 6/ 6/1000 here.
Figure 1: Case study on DP-SGD. Sampling probability p 10-3, noise scale 0.8, 10-1
Our Techniques Our algorithm (also the prior work of 20)+ proceeds by approximating the privacy loss random variables (PRVs) by truncating and discretizing them. We then use Fast Fourier Transform (FFT) to convolve the distributions efficiently. The main difference is in the approximation procedure and the error analysis. In the approximation procedure, we correct the approximation so that the expected value of the discretization matches with the expected value of the PRV.
To analyze the approximation error, we introduce the concept of coupling approximation (Defini- tion 5.1 which is variant of Wasserstein (optimal transport) distance specifically tailored this application. We first show that the approximation output by our algorithm to each privacy random variable is good coupling approximation. We then show that when independent coupling approx- imations are added, cancellation happens between the errors due to Hoeffding bound, producing much better coupling approximation than one naively expects from the triangle inequality. This allows us to choose the mesh size in our discretization to be RJ I whereas [KH21] choose a mesh Vk²
size of R. The other improvement is the truncation procedure. We give a tight tail bound of the PRVs (Lemma 5.4b. This allows to choose the domain size for in truncation to be R Ö(1), whereas [KH21] choose Ö(VR). Both ideas together saves factor of k in the time and memory.
For the analysis, the previous paper analyzes the discretization error by studying the stability of convolution. This leads to complicated calculations with the runtime linear in 1/serror (see (2). Since Oervor & 5 < I/N is required to give meaningful privacy guarantee (N is the number of users), this term 1/8errar is huge. this paper, we show various facts about how coupling approximation accumulates and use them to give a runtime depending only on //Tog(1/8
DP Preliminaries
Given a DP algorithm M, for each value of 5 2 O, there exists some 5 E [0, 1] such that M is (P, We can represent all these privacy guarantees by a function dm(()) 20 + [0, 1] and say that (.)(-) is the privacy curve of M. This inspires the following definition of a privacy curve between two random variables.
Definition 2.1 (Privacy curve). Given two random variables X, Y supported some set Q define 8(x Y)
R + [0, 1] as:
(() = sup Pr(Y E - e Pr(X E S).
SCR

---

Therefore an algorithm M is (E, DD iff 8 IM())) S 8 for all neighboring databases D'
Remark 2.2. Note that not all finctions å: IR - [0, 1] are privacy curves. A characterization of privacy curves can be obtained using the f-DP framework of [DRS19]. The notion of privacy curve 6(X()) and tradeoff' function r(X([Y) are dual to each other via convex duality (DRS79J. This implies characterization of privacy curves as shown in (ZDW2]).
Definition 2.3 (Composition of privacy curves [DRSI9I). Let 81 = ( [Y) and d2 = ((X2l) be any two privacy curves. The composition of the privacy curves, denoted by 51 @ 62, defined as
ô1 @ 82 = 8
X2)
where X1, X2 are independently sampled and Y1, Y2 are independently sampled.
Note that there can many pairs of random variables which have the same privacy curve, but above operation is well-defined. If shown by DRST9] that
= 5(11l))) and 8 ((X2)(Y2 ((x))) then it was
8 ((X1, X2) X2)) ((X,, XX)I Y)))
DRS19 also show that & a commutative and associative operation.
Given two DP algorithms Mi and M2, the adaptive composition (M2 (D) is an algorithm which outputs (D), (D, Mi (D)), i.e., .22 can look at the database D and also the output of the previous algorithm M1 (D). Adaptive composition of more than two algorithms is similarly defined. Suppose M1 has privacy curve 81 and My has privacy curve 82 (i.e.. M2(-, y) is a DP algorithm with privacy curve 82 for any fixed y.). The following composition theorem shows how to get the privacy curve M2 o M1.
Theorem 2.4 (Composition theorem DRS19). Let M1, M2...., M, be DP algorithms with privacy curves given by 81, .2,....,, 0g respectively. The privacy curve of the adaptive composition Mj ōg.
M .... o Mi is given by 51 & 62 @ .....
3 Privacy loss random variables
The notion of privacy loss random variables (PRVs) a unique way assign a pair (X, Y) for any privacy curve 8 such that 5 = 6(X Y)). PRVs allow us to compute composition of two algorithms via summing random variables (Theorem 3.5 (equivalently, convolving their distributions). Thus PRVs can be thought of as a reparametrization of privacy curves where composition becomes convolution. In this paper, we differ from the usual definition PRVs given in (DR16] *JH+20) which are tied to specific algorithm. Instead we think of them as a reparametrization of privacy curves and study them directly. This allows us succinetly prove many useful properties of PRVs.
Let R- RR (-00 )o} be the extended real line where we define + for x E IR. Definition 3.1 (Privacy loss random variables (PRVs)), Given privacy curve 8 RR + [0, 1]. we say that (X, Y) are privacy loss random variables for 8, if they satisfy the following conditions:
and -00 + 000
X, Y are supported on TR
((X[)Y) = 6,
(t) = et (t) for every E R and
Y--o) = 0 and X(oo)=0
where X(1), (t) are probability density functions of X, Y respectively.
Mathematically, the correct way to write the condition ((t) = e¹ ( is to say that [o()) = Ex(o(X)e*] for all test functions ø - + [o, 1] with ((xx) = x(-x))
to all situations where X, Y are continuous discrete both. For ) = 0. This will generalize of exposition, we ignore this complication and assume that X(t,, (t) represent the PDFs if X, Y are continuous at t, or the probability masses if they have point masses
The following theorem shows that the PRVs for a privacy curve = 8(PIQ) are given by the log- likeliie random variables of P, Q.
5

---

Theorem 3.2. Let 6 R + [0, 1] be privacy curve given by 8 = ((P where P. Q are two
random variables supported on Q. The PRVs (X,Y) ) for the privacy curve å are given by
(ww)
X log
where w P.
P(w)
Q(w)
Y = log
where ~ Q.
P(w)
The following theorem provides a formula for computing the privacy curve á terms of the PRVs
and conversely a formula for PRVs in terms of the privacy curve. A similar statement appears
in [SMMI9 "JH"20 20).
Theorem 3.3. The privacy curve 0 can be expressed in terms of PRVs (x, Y)
((e) Pr[Y s) - e Pr[x > 5) = By -
([111ee-))) e )+] )+)
Pr(Y 2 + 7].
(5)
where an exponential random variable Conversely, given a privacy curve 8 + [0, 11. we can compute the PDFs of its PRVs (X, Y") as:
(1) - (t) 8' (t) and X(1) ())))=((0((()63)))
Remark 3.4. Theorem 3.3 shows that the PRVs X,Y do not depend on the particular P, Q used represent the privacy curve 8 in Theorem 3.2 So should think of the PDF of of the PRV Y (or X) as an equivalent reparametrization of the privacy curve 8 - [0, 1), just as the notion of f-DP DRST9 is reparametrization of the privacy curve ö.
PRVs are useful in computing privacy curves because the composition of two privacy curves can be computed by adding the corresponding pairs of PRVs. A similar statement appears in [DR16].
Theorem 3.5. Let 81, 82 be two privacy curves with PRVs (X1, Y1) and (X2, Y2) respectively. Then the PRVs for 81 82 8(X1, X2 YY, Y2) are given by (X1 + X2, Yi + Y2). In particular.
51 < 82 = 8(X, X2 Y1 + Y2).
Proof. Let (X,Y) be the privacy random variables for 5(X1, X2 X2, Y2). 12). By Theorem 3.2
(Y1, (2)11.2))
X = log
where (21, ~ Xx)
(11,))
(2((1)V2(12) where fj ~ X1,t2 ~ X₂ (x((t))X2(te) (By independence of X1, X2 and indpendence of Vi, Y2)
log
= log (e" ett)) where 1 ~ X1,42 ~ X₂
t + to where t ~ X1,t2 ~ X2
X1 +X2
Similarly,
(2),,) where (41,82) ~ (Y,,
Y = log
(X1, (2)
f1 + tt where to Y1, t/ ~ Y2
+2.
In the supplementary material, provide proof of Theorems 3.2 and 3.3 compute the PRVs for a subsampled mechanism given the PRVs for the original mechanism and give examples of PRVs for few standard mechanisms. These are used our experiments calculate the PRVs for DP-SGD.
We also discuss how to
'Here (w) and (ww) the probability density functions of Q, P respeetivvly.. Note that the mathematically precise way is replace the ratio Q(w) by the Radon-Nikodyn derivative 4Q di (w).
P(w)
For E R, x+ max/2200 0).

---

Numerical composition of privacy curves
In this section, we present an efficient and numerically accurate method, ComposePRV (Algo- rithm D. for composing privacy guarantees by utilizing the notion of PRVs.
Algorithm 1: ComposePRV: Composing privacy curves using PRVs
Input: CDFs of PRVs Y1, Y....., YR, mesh size h, Truncation parameter hW>0
Output: PDF of approximation Y for Y >i= i=l Y, Y will be supported on
+++ (hZ [-L, LJ) for some μ [0, $
for l = 1 to do
Y; DiscretizePRV(Y; L,)):
end
Compute PDF OF = Yi +2 Y2 0L ... Br Ys by convolving PDFs of Yi, E2,... .... ... Ys using FFT;
Compute 60(5)= = Ep (1-c--) for all e [];
Return V, (-)
In the algorithm ComposePRV, we compute the circular convolution @2 using Fast Fourier Trans- form (FFT). Fix some L > For x R, we define (mod 2L) such that æ - 2n E (- L, L]. Given I, y. we define the circular addition r + x a++ (mod 2L). When we use FFT compute the convolution of two discrete distributions Y1, Y2 supported on 1Z [-,,-, f.j, we are implicitly calculating the the distribution of Y1 Q9, Y2. We will later show that Yi @r. Y2 ... Cr. Ya is good approximation of Y1 +2+ Yk-
2Ln where n E Z is chosen
The subroutine DiscretizePRV (Algorithm 2 is used to truncate and discretize PRVs. In this subroutine, we shift the discretized random variables such that it has the same mean the original variables. This is one main differences between our algorithm and the algorithm in [JPH21] KH21). We show that this significantly decreases the discretization error and allow to use much coarser mesh h = 1/v/ instead of h = 1/k.
Algorithm 2: DiscretizePRV: Discretize and truncate a PRV
Input: CDFy of a PRV Y, mesh size h, Truncation parameter L E h + h2
Output: PDF of an approximation Y supported on μ + [ LJ) for some μ E [0, 4..
L- +
n
h n to n do for < CDFy (ih + h/2) CDF h22)))
end
q + q/ (En-n 4:): L + Y| YI (i.c.. Y conditioned on Y < L):
// Normal ize to make it a probability distribution
+ E| - Em ih qi:
V ih + w.p. y for - n iniisn;
Return y:
For simplicity, throughout this paper, we will assume that the PRVs Y1, Y2...., any mass at do. This is with out loss of generality. Suppose Pr[Y; oo] 6, for each i. Let Y! = Yily Then
......,, Ys do not have
Yi + 8
Y
w.p. (1 (1-88) 52) ... -1 5x)
+
w.p. -- 02) ... (1 6z).
Therefore we can use Algorithm| to approximate the distribution V + Yg + .... + Y% and use to approximate the distribution of Yi Y2 +
Yı.

---

Error analysis
To analyze the discretization error, we introduce the notion of coupling approximation, variant of Wasserstein distance. Intuitively, good coupling approximation is coupling where the two random variables are close to each other with high probability.
Definition 5.1 (coupling approximation). Given two random variables Y1, Yz, we write [Y1 - Y2 Sn h if there exists coupling between Y1, Y2 such that Pr[[Y] Y21 > h] S n.
The following lemma shows that we have a good coupling approximation Ý to a PRV Y, then the privacy curves (E) and (E) should be close.
Lemma 5.2. Y and Y are two random variables such that IY Y Sn h, then for every E R.
55(e + h) 7 S (c) S 6g h) n-
Proof. By Theorem 3.2
8y = Pr(Y 2 E 2] and hence
(6) = Pr[Y - 2 5 2]
< Pr(yY - hJ + Pr(y 2 h+
S n + 67(: h).
Similarly, we have (c(e) n + 8y - h) for all s E
Therefore the goal of our analysis is to show that the ComposePRV algorithm finds good coupling approximation Y Y Σx= Y. We first show that the DiscretizePRV algorithm computes a good coupling approximation to the PRVs and crucially. it preserves the expected value after truncation. Lemma D.5 shows that L y So h where Y is the approximation of a PRV Y output by Algorithm and Y is the truncation of Y [-L, L].
We then use the following key lemma which shows that when we add independent coupling approxi- mations (where expected values match), get much better coupling approximation than what the triangle inequality predicts.
Lemma 5.3. Suppose Y1, Y2,..., YE and Yı, Y..... Ye are two collections of independent random variables such that |Y: Y/ So h and [|Y; E[V.] for all i, then
2 n
Y,
Y
Sn hy 2k log
i=1
Proof. Let X; = Y 8, where (Yi, Yi) are coupled such that Y Vil < h w.p. 1. Then X; E [-h, M] w.p. 1. Note that X1, X2...., ... Xx independent of each other. By Hoeffding's inequality,
(-
2t²
Pr
X 2
< 2exp
12(2)22
r
if we set 12/2k "
This lemma shows that the error of times composition is around Vie and hence setting ~ 1/v gives small enough error. Next, bound the domain size L. Naively, the domain size L should be of the order of Vi because Y is the of k independent random variables with each bounded by constant. In the supplementary material, we prove tighter tail bound of Y.
Lemma 5.4. Let (X,Y) Y) he the privacy random variables for a (e, 8)DD algorithm, then any t 0, we have
5 (1 + 6
Pr[[Y| 2 +
1 -
8

---

This shows that P 2 E + 2] I 16 and hence truncating the domain with L = 2 + only introduces an additive 8 eπror the privacy curve. Therefore, if the composition satisfies a good privacy guarantee (namely & = ( Together with the fact that mesh size is 1/vk, this gives (P(k)--time algorithm for computing the privacy curve when we compose the same mechanism with itself times. The following theorem gives a formal statement of the error bounds of our algorithm, it is proved in the supplementary material.
(1) for small enough 8), we can truncate the domain at 7. = (
Theorem 5.5. Let Eerrory Servor
be some fixed error terms. Let M2,M2 M2... My. be DP
algorithms with privacy curves (e). Let Y, be the PRV corresponding to M; such that d (e) 5y, (5) for = 2 0. Let M be the (adaptive) composition of M2,.......... and let ( be its privacy curve. Set L 2 2
Eerror sufficiently large such that
Serror
Serror
Σ 8m (L 2) and d' Eerror)
4
Let Y be the approximation of Y Ei=1 Ye produced by ComposePRV algorithmm with mesh size
Eerror
log 12
Borror
Then
( + Serror) Serror S (x) = SM(()) S dy - Servor) + Serror-
(8)
Furthermore, our algorithm takes (b log (4)) time where is the number of distinct algorithms among M1,M2, Mr.
Remark 5.6. A simple way to set L such that the condition
holds is by choosing an L such that:
L max {
&eerrur 4
(berror (8kk
Eeerror + tEM
max EM.
(9)
where s0()) is the inverse of (E)). To set the value of L, do not need the exact value of a (or E.J) We only need an upper bound on EM. which can often by obtained by using the RDP Accountant any other method to derive upper bounds on privacy.
6 Experiments
We demonstrate the utility of our composition method by computing the privacy curves for the DP-SGD algorithm, which is of the most important algorithms differential privacy.
5
4.5
4
The DP-SGD algorithm (ACG* 16) is a variant of stochastic gradient descent with & steps. In each step, the algorithm selects p fraction of training examples uniformly at random. The algorithm adds a Gaussian vector with variance xx o² to the clipped gradient of the selected batch. Then it performs a gradient step (or any other iterative methods) using the noisy gradi- computed. The privacy loss of DP-SGD involves composing the privacy curve of each iteration with itself times. The PRVs for each iteration have a closed form and depend only p, (see supplementary material). Our algo- rithms use this closed form PRVs.
3
2.5
2
Eeaacl
1.5
Expo Faiit D.1
0.1
1
Sug Faail 0.5
Sjuw Eaiit
0.5
Exp Gain 1.0
1.0
0
10
10
10
10
10
10
10
10
Figure 2: Setting p and comparing to the analytical solution (10)
See Figure [b) for the comparison between our algorithm and the GDP and RDP Accountant.
Our method provides a lower and upper bound
of the privacy curve according to (8) In Figure
I a), we compare algorithm with [KJPH2]

---

(implemented in [KP21]) Under the same mesh size, our algorithm computes a much closer upper and lower bound.
We validate our program for the case 1. When p = 1, we have an exact formula for
E 1
8(e) +
e
(10)
where μ vx, In Figure 2 show that the true privacy curve is indeed sandwiched between the bounds we compute and that the vertical distance between our bounds is indeed 2Eerror with neglible derror of 10 10-10
Floating point errors Note that our error analysis in Section 5 ignores floating point errors. This is because they are negligible compared to the discretization and truncation errors analyzed in Section for the range of 6 we are interested in. See supplementary material for more details.
6.1
Comparison with KJPH21]
12
100
10-3
KJPH21
10
Speed
80
10-4
70
10-5
Runtime [5]
60
* Speed up
10
50
10-7
30
10-9
20
10
16
10-10
Faw
10a
10
10
10a
100
1000
Discretisation points
DPSGD steps
Figure 3: (a) Comparison of error bounds of with varying number of discretisation points for 0.8, 1.5, k 1000. (b) Comparing runtimes for our algorithm with that of [J]P22] when aligned accuracy for = 0.8, 4 x 10-3, We can see significant reduction runtime in particular for large number of DPSGD steps. We were not able run the algorithm of [KJPH2]] beyond 2,000 steps, since it becomes unstable beyond that point We also plot the speed up directly on the secondary y-axis.
p 10
In this section, provide runtimes of our algorithm with [JРH21] which is the state-of-the-arr, for typical values of privacy parameters (a 0.8, p 4 10 e 1.5). See Figure 3 (a) for the effect of the number of discretisation points n on the accuracy of ó. Our algorithm requires about a few orders of magnitude smaller number of discretization points to converge compared to the algorithm of [JPH21]
results demonstrating the practical of our algorithm. We compare
In order to compare runtimes, we align the accuracy of both FFT algorithms. We set numerical parameters (number of discretization bins and domain length) such that both algorithms give similarly accurate bounds and verify it visually. Figure 3 (b) shows a significant speedup (100x) using our algorithms. We note that runtimes directly proportional to the memory required by the algorithms and so separate memory analysis is not required; the runtime and memory are dominated by the number of points in the discretization of PRV. All experiments performed Intel Xeon W-2155 CPU with 3.30GHz with 128GB of memory.
Acknowledgments and Disclosure of Funding
We would like to thank Janardhan Kulkarni and Sergey Yekhanin for several useful discussions and encouraging us to work on this problem. L.W. would like to thank Daniel Jones and Victor Rühle for fruitful discussions and helpful guidance.
We are using the implementation of [ from KP21
10

---

References
[ACG+16] Martin Abadi, Andy Chu, lan Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang, Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pages 308-318, 2016.
[BDLS19] Zhiqi Bu, Jinshuo Dong, Qi Long, and Weijie J. Su. Deep learning with gaussian differential privacy, 2019.
[BDRS18] Mark Bun, Cynthia Dwork, Guy N Rothblum, and Thomas Steinke. Composable and versatile privacy via truncated cdp. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 74-86, 2018.
[BGK 21G Zhiqi Bu, Sivakanth Gopi, Janardhan Kulkarni, Yin Tat Lee, Judy Hanwen Shen, and Uthaipon Tantipongpipat. Fast and memory efficient differentially private-sgd via jl projections. arXiv preprint arXiv:2102.03013, 2021.
[BS16] Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Theory of Cryptography Conference, pages 358- Springer, 2016.
[BW18] Borja Balle and Yu-Xiang Wang. Improving the gaussian mechanism for differential privacy: Analytical calibration and optimal denoising. In International Conference on Machine Learning, pages 403-412, 2018.
[DKM+06] Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 486- 503. Springer, 2006.
[DL09] Cynthia Dwork and Jing Lei. Differential privacy and robust statisties. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 371-380 2009.
[DMNS06] 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.
[DR+ 14] Cynthia Dwork, Aaron Roth, al. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 9(3-4):211-400 2014.
[DR16] Cynthia Dwork and Guy N Rothblum. Concentrated differential privacy. arXiv preprint crXiv:1603.01887 2016.
[DRS19] Jinshuo Dong, Aaron Roth, and Weijie J. Su. Gaussian differential privacy, 2019.
[DRV10] Cynthia Dwork, Guy N Rothblum, and Salil Vadhan. Boosting and differential privacy. In 2010 IEEE st Annual Symposium Foundations of Computer Science, pages 51-60. IEEE, 2010.
[KH21] Antti Koskela and Antti Honkela. Computing differential privacy guarantees for hetero- geneous compositions using fft. arXiv preprint arXiv:2102. 12412, 2021.
[KJH+20] Antti Koskela, Joonas Jälkö, Antti Honkela, al. Computing tight differential privacy guarantees using fft. In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics. AISTATS. 2020.
[KJPH21] Antti Koskela, Joonas Jälkö, Lukas Prediger, and Antti Honkela. Tight differential privacy for vacceee-vallud mechanisms and for the subsampled gaussian mechanism using fft. In Arindam Banerjee and Kenji Fukumizu, editors, Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pages 3356-336.. PMLR, 13-15 Apr 2021.
11

---

[KOV15] Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The composition theorem for differential privacy. In International conference on machine learning, pages 1376-1385. PMLR, 2015.
[KP21] Antti Koskela and Lukas Prediger. Github repository for fourier accountant. https: //github. www.cco//cce/e Bwtp///Dyyy//LLDACCOOOOe Acco-n-ccctttaaa 2021.
[Mir17] llya Mironov. Rényi differential privacy. In 2017 IEEE 30th Computer Security Foundations Symposium (CSF), pages 263-275. IEEE, 2017.
[MM18] Sebastian Meiser and Esfandiar Mohammadi. Tight on budget? tight bounds for r-fold approximate differential privacy. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, pages 247-264, 2018.
[MV16] 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.
[SMM19] David M Sommer, Sebastian Meiser, and Esfandiar Mohammadi. Privacy loss classes: The central limit theorem in differential privacy. Proceedings privacy enhancing technologies, 2019(2)2455-69,) 2019.
[ZDW21] Yuqing Zhu, Jinshuo Dong, and Yu-Xiang Wang. Optimal accounting of differential privacy via characteristic function. arXiv preprint arXiv:2106.0856,, 2021.
12


Reviews:
[{"review_id": "y_OmwIdLMCi", "reviewer": "Reviewer_Jo5A", "summary": "The paper studies an interesting problem --- obtaining arbitrary tight privacy guarantees of composed mechanisms efficiently. On the one hand, the known efficient RDP-based moments accountant (O(1) computational time) cannot achieve an arbitrary accuracy. On the other hand, the Fast Fourier Transform (FFT) based approach provides explicit error bounds, but the computational complexity is O( k^1.5), where k is the number of compositions. \nThe paper provides an improved analysis for computing the privacy curve of the composition and saves a factor of k in the run time and memory. \n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Weak points. \n\nThe main results are quite limited delta with respect to previous work. Given that the paper's major contribution is to *speed up the privacy computation* for PLD-based accountants, I think this paper is marginally above the acceptance threshold despite its interesting viewpoint in the error analysis. \n\nStrong points.\n\n1. Compared to the prior work [KJPH21], the proposed algorithm shifts the discretized random variables and improves the approximation procedue using the coupling approximation.\n\n2. They provide a tighter tail bound of the privacy loss random variables, which improves the truncation procedure and enables a wide choice on the mesh size ($1/\\sqrt(k)$) compared to ($1/k$) in [KJPH21]. \n \n\nQuestion:\n\nDoes the paper support heterogeneous composition as that in [KH21]?\n\nMinor comments:\nThe authors can improve the clarity by removing words like *in an influential paper* and *in an important paper*. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The potential negative societal impact is not applicable here.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5 hours"}, "extra_text": {}}, {"review_id": "wR6LtSf3ghJ", "reviewer": "Reviewer_MB3M", "summary": "The paper studies numerical composition of DP from a computation complexity perspective. Previous FFT based algorithm is optimized in its selection of discretization grid and truncation threshold. The runtime is significantly improved from $k^{1.5}$ to $k^{0.5}$. It also show that the CLT approach can underreport $\\varepsilon$ for very small $\\delta$.", "questions": "", "limitations": "", "rating": 9, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Although the algorithm is basically the same as the previous work, the improvement brought by the correct selection of discretization grid and truncation threshold is very remarkable. This shows the exciting potential of the FFT type accountant.\n\nThe concept of coupling approximation used in the analysis also seems interesting.\n\nI'd like to point out something that complements the knowledge. In this paper, Definition 3.1 and the claim below gives a clear picture about what (pair of) densities can be PRVs, but since the so-called privacy curve is a more fundamental object (indeed, the whole paper is about computing an operation of this object), it would be great if there is a clear picture about the privacy curve. This appears in the following paper\n\n> Zhu, Yuqing, Jinshuo Dong, and Yu-Xiang Wang. \"Optimal Accounting of Differential Privacy via Characteristic Function.\"\n\nIn the same spirit, from the claim below Definition 3.1, it seems one of the two densities determines the other. This seems worth a serious statement, and I wonder if we can pick a simpler object to work on. It's also not clear to me what privacy curve guarantees density and what privacy curve guarantees discrete probability masses. Is there no privacy curve that we ever imagine to design that has non-discrete PRVs but also no density?\n\nRegarding the writing, for the ease of the most general audience, I think including the runtime plot would be very helpful. Due to the page limit, Section 5 may have to be reduced. I understand how exciting it is to see theoretical ideas lead to practical improvements and the authors would like to tell us why, but I guess by human nature, a plot is more informative.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1.5"}, "extra_text": {}}, {"review_id": "_BPyv31wUC3", "reviewer": "Reviewer_Vztb", "summary": "The paper considers an important problem of computing the total privacy loss under composition. Since computing the exact (and optimal) privacy loss is computationally infeasible under complexity-theoretic assumptions, the paper computes an approximation. ", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Except for spotting some typos (like trucation instead of truncation on page 19), I do not have any complaints about the paper. I only have positive feedback about the paper and I will note it down for the latter stages:\n1. The paper studies a very important problem of computing an approximation to privacy loss under composition. \n2. The paper is very well written, the proof is elegant and easy to follow. \n3. The algorithm is very efficient (not just theoretically, but even practically). \n4. The current submission can be easily plugged in any large-scale deployment. I stressed tested the algorithm and it performed really well. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "4Eu9x1AAk2V", "reviewer": "Reviewer_9iuY", "summary": "The proposes a refined numerical method for (eps,delta)-differential privacy accounting. The method is based on that of [KJPH21]: the discrete privacy random variable (PRV) is formed by using the CDF of the true PRV and then normalised. By then using concentration inequalities, the error analysis is simplified (compared to [KJPH21]) which also leads to tighter bounds that enable choosing smaller parameter values for the algorithm. This improved error analysis also leads to improvement of the theoretical complexity bound (this is also considerably lower than the one given by Murtagh and Vadhan (2016)).", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "All in all I think this is a very nice addition to this line of research, and I am leaning towards accepting the paper. I do have some comments and criticism, in more detail below. I am ready to reconsider my score based on authors' response.\n\nPros:\n\n- The paper completes the previously proposed numerical method: The idea of normalising the truncated distributions and resorting to tail bounds in the error analysis (the way it is done) feels like the right way to do the error analysis. It is difficult to imagine major improvements to the discretisation procedure and to the overall complexity bounds. The complexity bound is considerably  better than the result given by Murtagh and Vadhan (2016).\n\n- The paper seems well written and the presentation of the error analysis elegant.\n\nCons:\n\n- The nature of the contribution is slightly incremental when considering the existing numerical method by [KJPH21]: the novelties lie mainly in the discretisation of the privacy loss random variable and in the error analysis of the resulting approximation. \n\n- The experiments: The 'competing method' is obviously that of [KJPH21]. However, the chosen experimental comparisons (e.g. Figure 1a, Figure 3) seem to be chosen such that the method of [KJPH21] is not yet converging properly, and therefore do not seem to tell the whole truth. The method of [KJPH21] in a sense already 'does the job' by giving accurate tight bounds in affordable runtimes (compute times orders of seconds). E.g. in Figure 3b, I would expect the method of [KJPH21] to give tighter bounds (quickly) when decreasing the discretisation parameter h from the reported $8 \\cdot 10^{-4}$ to $1 \\cdot 10^{-5}$. \n\n\nQuestions and Remarks:\n\n- Could you explain where does the assumption \"$| Y_i - \\widetilde{Y}_i | \\leq_0 h$\" in Lemma 5.3 come from? I would imagine there is always some gap due to the normalisation carried out for the truncated distribution so that for small enough $h$, $Y_i$ and $\\widetilde{Y}_i$ would actually differ with a positive probability. Unless the discretisation interval contains the whole of $Y$, due to the normalisation $Y_i$ and $\\widetilde{Y}_i$ would always differ.\n\n- To make everything rigorous, should you not consider discretisation at the points $\\{i \\cdot h\\}$, $-n \\leq i < n$ instead of $-n \\leq i \\leq n$, due to the periodisation ?\n\n- How is the PRV evaluated for the subsampled Gaussian mechanism exactly? Looking at the discretisation algorithm, you use the CDF at ih - h/2 and at ih + h/2 to obtain the point mass.  So you numerically integrate the CDFs in high precision using the analytic formula for the PRV? How do you ensure that the integration error stays very small e.g. for the PRV of the subsampled Gaussian mechanism?\n\n- Can you get the FFT evaluations down to order of tens of milliseconds with reasonable accuracy? Unless that is the case, the gains from the computational speed up might be limited in practice.\n\n- Remark about the runtime experiments: using those parameter values ($\\sigma=0.8$, $p=4 \\cdot 10^{-3}$, $\\varepsilon=1.5$), the $\\delta$ goes up to ~ $3 \\cdot 10^{-5}$ for $k=2000$, and up to ~0.02 for $k=10^4$, so I would say that for up to $k=10^4$ it is less typical DP-SGD training (unless very small amount of data, $\\delta$ should be less than $1/N$, $N$ number of samples).\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, relation to the other accounting methods is discussed. This is mostly a theory paper.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers felt that, although the algorithm in this paper is very similar to previous work, the modifications feel like the "right" way to solve the problem, and the improvements are significant for an important problem. The reviewers agreed that this paper should be accepted as a spotlight.
Decision: Accept (Spotlight)