Numerical Composition of Differential Privacy∗
Year: 2022

Abstract:
We give a fast algorithm to 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 a DP algorithm composed with itself k times is Õ( √ k). This improves over the best prior method by [KH21] which requires Ω̃(k) running time. We demonstrate the utility of our algorithm by accurately computing the privacy loss of DP-SGD algorithm of Abadi et al. [ACG16] and showing that our algorithm speeds up the privacy computations by a few orders of magnitude compared to prior work, while maintaining similar accuracy.

text: √ k). This improves
over the best prior method by [KH21] which requires Ω̃(k1.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.

heading: 1 Introduction
text: Differential privacy (DP) introduced by [DMNS06] provides a provable and quantifiable guarantee of privacy when the results of an algorithm run on private data are made public. Formally, we can define an (ε, δ)-differentially private algorithm as follows. Definition 1.1 ((ε, δ)-DP [DMNS06, DKM+06]). An algorithm M is (ε, δ)-DP if for any two neighboring databases D,D′ differing in exactly one user and any subset S of outputs, we have Pr[M(D) ∈ S] ≤ eε Pr[M(D′) ∈ S] + δ.
Intuitively, it says that looking at the outcome ofM, we cannot tell whether it was run on D or D′. Hence an adversary cannot infer the existence of any particular user in the input database, and therefore cannot learn any personal data of any particular user.
DP algorithms have an important property called composition. SupposeM1 andM2 are DP algorithms and say M(D) = (M1(D),M2(D)), i.e., M runs both the algorithms on D and outputs their results. Then M is also a DP algorithm. Proposition 1.2 (Simple composition [DKM+06, DL09]). If M1 is (ε1, δ1)-DP and M2 is (ε2, δ2)DP, then M(D) = (M1(D),M2(D)) is (ε1 + ε2, δ1 + δ2)-DP.
This also holds under adaptive composition (denoted by M = M2 ◦M1), where M2 can look at both the database and the output of M1 (here M(D) = (M1(D),M2(D,M1(D)))). It turns out that both compositions enjoy much better DP guarantees than this simple composition rule. Let M be an (ε, δ)-DP algorithm and let M◦k denote the (adaptive) composition of M with itself k times. The naive composition rule shows that M◦k is (kε, kδ)-DP. This was significantly improved in [DRV10]. Proposition 1.3 (Advanced composition [DRV10, DR+14]). IfM is (ε, δ)-DP, thenM◦k is (ε′, kδ+ δ′)-DP where
ε′ = ε √ 2k log ( 1
δ′
) + kε(eε − 1).
∗Author ordering is alphabetical. Code is available at https://github.com/microsoft/prv_ accountant.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
Note that if ε = O (
1√ k
) and δ = o ( 1 k ) , then M◦k satisfies (Oδ′(1), δ′)-DP. Using simple composi-
tion (Proposition 1.2), we can only claim that M◦k is (O( √ k), o(1))-DP. Thus advanced composition often results in √ k-factor savings in privacy which is significant in practice. The optimal DP guarantees for k-fold composition of an (ε, δ)-DP algorithm were finally obtained by [KOV15]. For composing different algorithms, the situation is more complicated. If M1,M2, . . . ,Mk are DP algorithms such that Mi is (εi, δi)-DP, then it is shown by [MV16] that computing the exact DP guarantees for M = M1 ◦M2 ◦ · · · ◦Mk is #P-complete. They also give an algorithm to approximate the DP guarantees of M to desired accuracy η which runs in
Õ
( k3ε̄(1 + ε̄)
η
) (1)
time where ε̄ = ( ∑k i=1 εi)/k.
2 If each εi ≈ 1√k (so that M will satisfy reasonable privacy guarantees by advanced composition), then the running time is Õ(k2.5/η).
In most situations, DP algorithms come with a collection of (ε, δ)-DP guarantees, i.e., for each value of ε, there exists δ such that the algorithm is (ε, δ)-DP.
Definition 1.4 (Privacy curve). A DP algorithm M is said to have privacy curve δ : R→ [0, 1], if for every ε ∈ R, M is (ε, δ(ε))-DP.
For example the privacy curve of a Gaussian mechanism (with sensitivity 1 and noise scale σ) is given by δ(ε) = Φ (−εσ + 1/2σ)−eεΦ (−εσ − 1/2σ) where Φ(·) is the Gaussian CDF [BW18]. Suppose we want to compose several Gaussian mechanisms, which (ε, δ)-DP guarantee should we choose for each mechanism? Any choice will lead to 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 [DRS19]. f -DP is a dual way (and equivalent) to look at the privacy curve δ(ε).
Independently, an algorithm called Privacy Buckets for approximately composing privacy curves using the notion of was initiated in [MM18]. This algorithm depends on the notion of Privacy Loss Random Variable (PRV) [DR16], whose distribution is called Privacy Loss Distribution (PLD). For any DP-algorithm, one can associate a 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 Y of the composition M = M1 ◦M2 ◦ · · · ◦Mk is given by Y = ∑k i=1 Yi where Yi is the PRV of Mi.3 Therefore, one can find the distribution of Y by the convolution of the distributions of Y1, Y2, . . . , Yk. 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+20, KJPH21, KH21]. The running time of this algorithm was analyzed in [KH21] where it was shown that the privacy curve δM (ε) of M = M1 ◦M2 ◦ · · · ◦Mk can be computed up to an additive error of δerror in time
Õ
( k3ε̄
δerror
) , (2)
if each algorithm Mi is satisfies (εi, 0)-DP and ε̄ = 1k ∑k i=1 εi. Assuming that each εi ≈ 1√ k , we get Õ(k2.5/δerror) running time. Note that this is slightly worse than (1), where the denominator η is the multiplicative error in δM . When composing the same algorithm with itself for k times, the running time can be improved to Õ ( k2ε̄ δerror ) , which is Õ ( k1.5 δerror ) when ε̄ = 1√ k .
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-SGD) algorithm which they introduced. Analyzing the privacy loss of DP-SGD involves composing the
2ε has an additive error of η and δ has a multiplicative error of η. 3[KJH+20] only state this for non-adaptive composition. In this paper we show how to extend this to adaptive
composition as well.
privacy curve of each iteration of training with itself k times, where k is the total of number of training iterations. Typical values of k range from 1000 to 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 is one of the most important DP algorithms in practice, because one can use it to train neural networks to achieve good privacy-vs-utility tradeoffs. Therefore obtaining accurate and tight privacy guarantees for DP-SGD is important. For example reducing ε from 2 to 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 or Renyi DP cannot be applied for analyzing privacy. An example of such an algorithm is the DP-SGD-JL algorithm of [BGK+21] which uses numerical composition of PRVs to analyze privacy.
GDP Accountant [DRS19, BDLS19] introduced the notion of Gaussian Differential Privacy (GDP) and used it to develop an accountant for DP-SGD. The accountant is based on central limit theorem and only gives an 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) [DR16, BS16], Truncated CDP [BDRS18] etc. None of these methods can approximate the privacy curve of compositions to arbitrary accuracy. The notion of 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.

heading: 1.1 Our Contributions
text: 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 of DP algorithms. Theorem 1.5 (Informal version of Theorem 5.5). SupposeM1,M2, . . . ,Mk are DP algorithms. Then the privacy curve δM (ε) of adaptive composition M = M1 ◦M2 ◦ · · · ◦Mk can be approximated in time
O
εupper k1.5 log k √ log 1δerror
εerror  , (3) where εerror is the additive error in ε, δerror is the additive error in δ and εupper is an upper bound on max { εM (δerror),maxi εMi ( δerror k )} .4
If each Mi satisfies (
1√ k , o(1)k
) -DP, then by advanced composition (Proposition 1.3), we can set
εupper = O(1). Therefore the running time of our algorithm in this case is Õ
( k1.5
√ log 1δerror εerror ) . We
can save a factor of k, when we compose the same algorithm with itself k times. Theorem 1.6. Suppose M is a DP algorithm. Then the privacy curve δM◦k(ε) of M (adaptively) composed with itself k times can be approximated in time
O
εupper k 12 log k √ log 1δerror
εerror  , (4) where εerror is the additive error in ε, δerror is the additive error in δ and εupper is an upper bound on max { εM◦k(δerror), εM ( δerror k )} .
Thus we improve the state-of-the-art by at least a factor of k in running time. We also note that our algorithm improves the memory required by a factor of k. See Figure 1 for a comparison of
4εM (δ) is the inverse of δM (ε).
our algorithm with that of [KJPH21]. Also note that RDP Accountant (equivalent to the Moments Accountant) significantly overestimates the true ε, while the GDP Accountant significantly underestimates the true ε. In contrast, the upper and lower bounds provided by our algorithm lie very close to each other.
0.15
0.2
0.25
0.3
0.35
0.4
0.45
0.5
0.55
0.6
0.65
10 15 20 25 30 35 40 45 50
ε
DPSGD steps
εup Ours εlow Ours εup [KJPH21] εlow [KJPH21]
(a) Our algorithm gives much closer upper and lower bounds on the true privacy curve compared to [KJPH21], under the same mesh size of 4 × 10−5. Our upper and lower bounds are nearly coinciding.
0
0.5
1
1.5
2
2.5
0 500 1000 1500 2000
ε
DPSGD steps
Ours Upper Ours Lower
GDP RDP
(b) Our algorithm can improve significantly over the RDP Accountant. We also see that GDP Accountant can significantly underreport the true ε. We have set εerror = 0.1, δerror = δ/1000 here.
Figure 1: Case study on DP-SGD. Sampling probability p = 10−3, noise scale σ = 0.8, δ = 10−7.
Our Techniques Our algorithm (also the prior work of [KJH+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 (Definition 5.1), which is a variant of Wasserstein (optimal transport) distance specifically tailored to this application. We first show that the approximation output by our algorithm to each privacy random variable is a good coupling approximation. We then show that when independent coupling approximations are added, cancellation happens between the errors due to Hoeffding bound, producing a 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 ≈ 1√
k , whereas [KH21] choose a mesh
size of ≈ 1k . The other improvement is the truncation procedure. We give a tight tail bound of the PRVs (Lemma 5.4). This allows us to choose the domain size for in truncation to be ≈ Õ(1), whereas [KH21] choose ≈ Õ( √ k). Both ideas together saves a factor of k in the run 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/δerror (see (2)). Since δerror δ 1/N is required to give meaningful privacy guarantee (N is the number of users), this term 1/δerror is huge. In this paper, we show various facts about how coupling approximation accumulates and use them to give a runtime depending only on √ log(1/δerror).

heading: 2 DP Preliminaries
text: Given a DP algorithm M, for each value of ε ≥ 0, there exists some δ ∈ [0, 1] such that M is (ε, δ)-DP. We can represent all these privacy guarantees by a function δM(ε) : R≥0 → [0, 1] and say that δM(·) is the privacy curve ofM. 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 on some set Ω, define δ(X||Y ) : R→ [0, 1] as:
δ(X||Y )(ε) = sup S⊂Ω Pr[Y ∈ S]− eε Pr[X ∈ S].
Therefore an algorithmM is (ε, δ)-DP iff δ (M(D)||M(D′)) (ε) ≤ δ for all neighboring databases D,D′.
Remark 2.2. Note that not all functions δ : R → [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 δ(X||Y ) and tradeoff function T (X||Y ) are dual to each other via convex duality [DRS19]. This implies a characterization of privacy curves as shown in [ZDW21]. Definition 2.3 (Composition of privacy curves [DRS19]). Let δ1 ≡ δ(X1||Y1) and δ2 ≡ δ(X2||Y2) be any two privacy curves. The composition of the privacy curves, denoted by δ1 ⊗ δ2, is defined as
δ1 ⊗ δ2 ≡ δ ((X1, X2)||(Y1, Y2)) where X1, X2 are independently sampled and Y1, Y2 are independently sampled.
Note that there can be many pairs of random variables which have the same privacy curve, but the above operation is well-defined. If δ(X1||Y1) ≡ δ(X ′1||Y ′1) and δ(X2||Y2) ≡ δ(X ′2||Y ′2), then it was shown by [DRS19] that δ ((X1, X2)||(Y1, Y2)) = δ ((X ′1, X ′2)||(Y ′1 , Y ′2)) . [DRS19] also show that ⊗ is a commutative and associative operation. Given two DP algorithms M1 and M2, the adaptive composition (M2 ◦M1)(D) is an algorithm which outputs (M1(D),M2(D,M1(D)), i.e., M2 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 δ1 and M2 has privacy curve δ2 (i.e., M2(·, y) is a DP algorithm with privacy curve δ2 for any fixed y.). The following composition theorem shows how to get the privacy curve of M2 ◦M1. Theorem 2.4 (Composition theorem [DRS19]). LetM1,M2, . . . ,Mk be DP algorithms with privacy curves given by δ1, δ2, . . . , δk respectively. The privacy curve of the adaptive composition Mk ◦ Mk−1 ◦ · · · ◦M1 is given by δ1 ⊗ δ2 ⊗ · · · ⊗ δk.

heading: 3 Privacy loss random variables
text: The notion of privacy loss random variables (PRVs) is a unique way to assign a pair (X,Y ) for any privacy curve δ such that δ ≡ δ(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 of PRVs given in [DR16, KJH+20], which are tied to a specific algorithm. Instead we think of them as a reparametrization of privacy curves and study them directly. This allows us to succinctly prove many useful properties of PRVs.
Let R = R∪ {−∞,∞} be the extended real line where we define∞+ x =∞ and −∞+ x = −∞ for x ∈ R. Definition 3.1 (Privacy loss random variables (PRVs)). Given a privacy curve δ : R→ [0, 1], we say that (X,Y ) are privacy loss random variables for δ, if they satisfy the following conditions:
• X,Y are supported on R,
• δ(X||Y ) ≡ δ,
• Y (t) = etX(t) for every t ∈ R and
• Y (−∞) = 0 and X(∞) = 0
where X(t), Y (t) are probability density functions of X,Y respectively.
Mathematically, the correct way to write the condition Y (t) = etX(t) is to say that EY [φ(Y )] = EX [φ(X)eX ] for all test functions φ : R→ [0, 1] with φ(∞) = φ(−∞) = 0. This will generalize to all situations where X,Y are continuous or discrete or both. For ease of exposition, we ignore this complication and assume that X(t), Y (t) represent the PDFs if X,Y are continuous at t, or the probability masses if they have point masses at t.
The following theorem shows that the PRVs for a privacy curve δ = δ(P ||Q) are given by the log-likelihood random variables of P,Q.
Theorem 3.2. Let δ : R → [0, 1] be a privacy curve given by δ ≡ δ(P ||Q) where P,Q are two random variables supported on Ω. The PRVs (X,Y ) for the privacy curve δ are given by5:
X = log
( Q(ω)
P (ω)
) where ω ∼ P,
Y = log
( Q(ω)
P (ω)
) where ω ∼ Q.
The following theorem provides a formula for computing the privacy curve δ in terms of the PRVs and conversely a formula for PRVs in terms of the privacy curve. A similar statement appears in [SMM19, KJH+20]. Theorem 3.3. The privacy curve δ can be expressed in terms of PRVs (X,Y ) as:
δ(ε) = Pr[Y > ε]− eε Pr[X > ε] = EY [(1− eε−Y )+] = Pr[Y ≥ ε+ Z]. (5) where Z is an exponential random variable.6 Conversely, given a privacy curve δ : R→ [0, 1], we can compute the PDFs of its PRVs (X,Y ) as:
Y (t) = δ′′(t)− δ′(t) and X(t) = et(δ′′(t)− δ′(t)). (6) Remark 3.4. Theorem 3.3 shows that the PRVs X,Y do not depend on the particular P,Q used to represent the privacy curve δ in Theorem 3.2. So we should think of the PDF of of the PRV Y (or X) as an equivalent reparametrization of the privacy curve δ : R→ [0, 1], just as the notion of f -DP [DRS19] is a 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 δ1, δ2 be two privacy curves with PRVs (X1, Y1) and (X2, Y2) respectively. Then the PRVs for δ1 ⊗ δ2 = δ(X1, X2||Y1, Y2) are given by (X1 +X2, Y1 + Y2). In particular,
δ1 ⊗ δ2 = δ(X1 +X2||Y1 + Y2).
Proof. Let (X,Y ) be the privacy random variables for δ(X1, X2||Y1, Y2). By Theorem 3.2,
X = log
( (Y1, Y2)(t1, t2)
(X1, X2)(t1, t2)
) where (t1, t2) ∼ (X1, X2)
= log
( Y1(t1)Y2(t2)
X1(t1)X2(t2)
) where t1 ∼ X1, t2 ∼ X2
(By independence of X1, X2 and indpendence of Y1, Y2) = log ( et1 · et2 ) where t1 ∼ X1, t2 ∼ X2
= t1 + t2 where t1 ∼ X1, t2 ∼ X2 = X1 +X2.
Similarly,
Y = log
( (Y1, Y2)(t1, t2)
(X1, X2)(t1, t2)
) where (t1, t2) ∼ (Y1, Y2)
= t1 + t2 where t1 ∼ Y1, t2 ∼ Y2 = Y1 + Y2.
In the supplementary material, we provide a proof of Theorems 3.2 and 3.3. We also discuss how to 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 in our experiments to calculate the PRVs for DP-SGD.
5HereQ(ω) andP (ω) are the probability density functions ofQ,P respectively. Note that the mathematically precise way is to replace the ratio Q(ω)
P (ω) by the Radon-Nikodym derivative dQ dP (ω).
6For x ∈ R, x+ = max{x, 0}.

heading: 4 Numerical composition of privacy curves
text: In this section, we present an efficient and numerically accurate method, ComposePRV (Algorithm 1), for composing privacy guarantees by utilizing the notion of PRVs.
Algorithm 1: ComposePRV: Composing privacy curves using PRVs Input: CDFs of PRVs Y1, Y2, . . . , Yk, mesh size h, Truncation parameter L ∈ h2 + hZ >0
Output: PDF of an approximation Ỹ for Y = ∑k i=1 Yi. Ỹ will be supported on µ+ (hZ ∩ [−L,L]) for some µ ∈ [0, h2 ]. for ` = 1 to k do
Ỹi ← DiscretizePRV(Yi, L, h); end Compute PDF Of Ỹ = Ỹ1 ⊕L Ỹ2 ⊕L · · · ⊕L Ỹk by convolving PDFs of Ỹ1, Ỹ2, . . . , Ỹk using FFT;
Compute δỸ (ε) = EỸ
[( 1− eε−Ỹ ) + ] for all ε ∈ [0, L];
Return Ỹ , δỸ (·)
In the algorithm ComposePRV, we compute the circular convolution ⊕L using Fast Fourier Transform (FFT). Fix some L > 0. For x ∈ R, we define x (mod 2L) = x− 2Ln where n ∈ Z is chosen such that x−2Ln ∈ (−L,L]. Given x, y, we define the circular addition x⊕L y = x+y (mod 2L). When we use FFT to compute the convolution of two discrete distributions Y1, Y2 supported on hZ ∩ [−L,L], we are implicitly calculating the the distribution of Y1 ⊕L Y2. We will later show that Ỹ1 ⊕L Ỹ2 ⊕L · · · ⊕L Ỹk is a good approximation of Y1 + Y2 + · · ·+ Yk. 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 as the original variables. This is one of main differences between our algorithm and the algorithm in [KJPH21, KH21]. We show that this significantly decreases the discretization error and allow us to use much coarser mesh h ≈ 1/ √ k 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 ∈ h2 + hZ >0 Output: PDF of an approximation Ỹ supported on µ+ (hZ ∩ [−L,L]) for some µ ∈ [0, h2 ]. n← L− h 2
h ; for i = −n to n do
qi ← CDFY (ih+ h/2)− CDFY (ih− h/2); end q ← q/ (∑n i=−n qi ) ; // Normalize q to make it a probability distribution
Y L ← Y ∣∣ |Y |≤L (i.e., Y conditioned on |Y | ≤ L);
µ← E[Y L]− ∑n i=−n ih · qi;
Ỹ ← { ih+ µ w.p. qi for − n ≤ i ≤ n ;
Return Ỹ ;
For simplicity, throughout this paper, we will assume that the PRVs Y1, Y2, . . . , Yk do not have any mass at ∞. This is with out loss of generality. Suppose Pr[Yi = ∞] = δi for each i. Let Y ′i = Yi|Yi 6=∞. Then
Y1 + Y2 + · · ·+ Yk = { Y ′1 + Y ′ 2 + · · ·+ Y ′k w.p. (1− δ1)(1− δ2) · · · (1− δk)
∞ w.p. 1− (1− δ1)(1− δ2) · · · (1− δk).
Therefore we can use Algorithm 1 to approximate the distribution of Y ′1 + Y ′ 2 + · · ·+ Y ′k , and use it to approximate the distribution of Y1 + Y2 + · · ·+ Yk.

heading: 5 Error analysis
text: To analyze the discretization error, we introduce the notion of coupling approximation, a variant of Wasserstein distance. Intuitively, a good coupling approximation is a coupling where the two random variables are close to each other with high probability.
Definition 5.1 (coupling approximation). Given two random variables Y1, Y2, we write |Y1−Y2| ≤η h if there exists a coupling between Y1, Y2 such that Pr[|Y1 − Y2| > h] ≤ η.
The following lemma shows that if we have a good coupling approximation Ỹ to a PRV Y , then the privacy curves δY (ε) and δỸ (ε) should be close.
Lemma 5.2. If Y and Ỹ are two random variables such that |Y − Ỹ | ≤η h, then for every ε ∈ R,
δỸ (ε+ h)− η ≤ δY (ε) ≤ δỸ (ε− h) + η.
Proof. By Theorem 3.2, δY (ε) = Pr[Y ≥ ε+ Z] and hence
δY (ε) = Pr[Y − Ỹ + Ỹ ≥ ε+ Z] ≤ Pr[Y − Ỹ ≥ h] + Pr[Ỹ ≥ ε− h+ Z] ≤ η + δỸ (ε− h).
Similarly, we have δỸ (ε) ≤ η + δY (ε− h) for all ε ∈ R.
Therefore the goal of our analysis is to show that the ComposePRV algorithm finds a good coupling approximation Ỹ to Y = ∑k i=1 Yi. 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 |Ỹ − Y L| ≤0 h where Ỹ is the approximation of a PRV Y output by Algorithm 2 and Y L is the truncation of Y to [−L,L]. We then use the following key lemma which shows that when we add independent coupling approximations (where expected values match), we get a much better coupling approximation than what the triangle inequality predicts.
Lemma 5.3. Suppose Y1, Y2, . . . , Yk and Ỹ1, Ỹ2, . . . , Ỹk are two collections of independent random variables such that |Yi − Ỹi| ≤0 h and E[Yi] = E[Ỹi] for all i, then∣∣∣∣∣ k∑ i=1 Yi − k∑ i=1 Ỹi ∣∣∣∣∣ ≤η h √ 2k log 2 η .
Proof. LetXi = Yi−Ỹi where (Yi, Ỹi) are coupled such that |Yi−Ỹi| ≤ hw.p. 1. ThenXi ∈ [−h, h] w.p. 1. Note that X1, X2, . . . , Xk are independent of each other. By Hoeffding’s inequality,
Pr [∣∣∣∣∣∑ i Xi ∣∣∣∣∣ ≥ t ] ≤ 2 exp ( − 2t 2 k(2h)2 ) = η
if we set t = h √
2k log 2η .
This lemma shows that the error of k times composition is around √ k ·h and hence setting h ≈ 1/ √ k gives small enough error. Next, we bound the domain size L. Naively, the domain size L should be of the order of √ k because Y is the sum of k independent random variables with each bounded by a constant. In the supplementary material, we prove a tighter tail bound of Y .
Lemma 5.4. Let (X,Y ) be the privacy random variables for a (ε, δ)-DP algorithm, then for any t ≥ 0, we have
Pr[|Y | ≥ ε+ t] ≤ δ (1 + e −ε−t)
1− e−t .
This shows that Pr[|Y | ≥ ε + 2] ≤ 43δ and hence truncating the domain with L = 2 + ε only introduces an additive δ error in the privacy curve. Therefore, if the composition satisfies a good privacy guarantee (namely ε = O(1) for small enough δ), we can truncate the domain at L = Θ(1). Together with the fact that mesh size is 1/ √ k, this gives a O( √ k)-time algorithm for computing the privacy curve when we compose the same mechanism with itself k times. The following theorem gives a formal statement of the error bounds of our algorithm, it is proved in the supplementary material.
Theorem 5.5. Let εerror, δerror > 0 be some fixed error terms. Let M1,M2, . . . ,Mk be DP algorithms with privacy curves δMi(ε). Let Yi be the PRV corresponding toMi such that δMi(ε) = δYi(ε) for ε ≥ 0. LetM be the (adaptive) composition ofM1,M2, . . . ,Mk and let δM(ε) be its privacy curve. Set L ≥ 2 + εerror sufficiently large such that
k∑ i=1 δMi(L− 2) ≤ δerror 8 and δM(L− 2− εerror) ≤ δerror 4 . (7)
Let Ỹ be the approximation of Y = ∑k i=1 Yi produced by ComposePRV algorithm with mesh size
h = εerror√ k 2 log 12 δerror .
Then δỸ (ε+ εerror)− δerror ≤ δY (ε) = δM(ε) ≤ δỸ (ε− εerror) + δerror. (8)
Furthermore, our algorithm takes O ( bLh log ( L h )) time where b is the number of distinct algorithms amongM1,M2, . . . ,Mk. Remark 5.6. A simple way to set L such that the condition (7) holds is by choosing an L such that:
L ≥ 2 + max { εerror + εM ( δerror
4 ) ,max i∈[k] εMi ( δerror 8k )} (9)
where εA(δ) is the inverse of δA(ε). To set the value of L, we do not need the exact value of εM (or εMi). We only need an upper bound on εM, which can often by obtained by using the RDP Accountant or 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 one of the most important algorithms in differential privacy.
The DP-SGD algorithm [ACG+16] is a variant of stochastic gradient descent with k steps. In each step, the algorithm selects a p fraction of training examples uniformly at random. The algorithm adds a Gaussian vector with variance ∝ σ2 to the clipped gradient of the selected batch. Then it performs a gradient step (or any other iterative methods) using the noisy gradient computed. The privacy loss of DP-SGD involves composing the privacy curve of each iteration with itself k times. The PRVs for each iteration have a closed form and depend only p, σ (see supplementary material). Our algorithms use this closed form of PRVs.
See Figure 1(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 1(a), we compare our algorithm with [KJPH21]
(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 p = 1. When p = 1, we have an exact formula for
δ(ε) = Φ ( − ε µ + µ 2 ) − eεΦ ( − ε µ − µ 2 ) (10)
where µ = √ k σ . In Figure 2, we show that the true privacy curve is indeed sandwiched between the bounds we compute and that the vertical distance between our bounds is indeed 2εerror with a neglible δerror of 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 we analyzed in Section 5 for the range of δ we are interested in. See supplementary material for more details.
6.1 Comparison with [KJPH21]
In this section, we provide more results demonstrating the practical use of our algorithm. We compare runtimes of our algorithm with [KJPH21], which is the state-of-the-art, for typical values of privacy parameters (σ = 0.8, p = 4 × 10−3, ε = 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 [KJPH21].
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 are directly proportional to the memory required by the algorithms and so a separate memory analysis is not required; the runtime and memory are dominated by the number of points in the discretization of PRV. All experiments are performed on a 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.
7We are using the implementation of [KJPH21] from [KP21].

Review summaries:
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)).

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.  The 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.  

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$.