Individual Privacy Accounting with Gaussian Differential Privacy
Authors: Antti Koskela
Marlon Tobaben
Antti Honkela
Venue: ICLR 2023 poster (2023)
Keywords: differential privacy
gaussian differential privacy
fully adaptive compositions
privacy accounting
individual privacy loss

Abstract: Individual privacy accounting enables bounding differential privacy (DP) loss individually for each participant involved in the analysis. This can be informative as often the individual privacy losses are considerably smaller than those indicated by the DP bounds that are based on considering worst-case bounds at each data access. In order to account for the individual losses in a principled manner, we need a privacy accountant for adaptive compositions of mechanisms, where the loss incurred at a given data access is allowed to be smaller than the worst-case loss. This kind of analysis has been carried out for the Rényi differential privacy by Feldman and Zrnic (2021), however not yet for the so-called optimal privacy accountants. We make first steps in this direction by providing a careful analysis using the Gaussian differential privacy which gives optimal bounds for the Gaussian mechanism, one of the most versatile DP mechanisms. This approach is based on determining a certain supermartingale for the hockey-stick divergence and on extending the Rényi divergence-based fully adaptive composition results by Feldman and Zrnic (2021). We also consider measuring the individual  $(\varepsilon,\delta)$-privacy losses using the so-called privacy loss distributions. Using the Blackwell theorem, we can then use the results of Feldman and Zrnic (2021) to construct an approximative individual $(\varepsilon,\delta)$-accountant. We also show how to speed up the FFT-based individual DP accounting using the Plancherel theorem.

Published as a conference paper at ICLR 2023
INDIVIDUAL PRIVACY ACCOUNTING WITH GAUSSIAN DIFFERENTIAL PRIVACY
Antti Koskela
Marlon Tobaben University of Helsinki ma marlon cooaaen@@elssnnde fi
Nokia Bell Labs
University of Helsinki
www.kkkkkkllakkiiaakaaaaaa htt.--beellllbaceoom com
Antti Honkela
University of Helsinki
ABSTRACT
Individual privacy accounting enables bounding differential privacy (DP) loss in- dividually for each participant involved in the analysis. This can be informative as often the individual privacy losses are considerably smaller than those indicated by the DP bounds that are based on considering worst-case bounds at each data ac- cess. In order to account for the individual privacy losses in a principled manner, we need a privacy accountant for adaptive compositions of randomised mecha- nisms, where the loss incurred at given data access is allowed to be smaller than the worst-case loss. This kind of analysis has been carried out for the Rényi differ- ential privacy by Feldman and Zrnic (12), however not yet for the called optimal privacy accountants. We make first steps in this direction by providing careful analysis using the Gaussian differential privacy which gives optimal bounds for the Gaussian mechanism, proach is based on determining a certain supermartingale for the hockey-stice divergence and extending the Rényi divergence based fully adaptive composi- tion results by Feldman and Zrnic (12). We also consider measuring the individual (c, --privacy losses using the called privacy loss distributions. With the help of the Blackwell theorem, we can then make use of the results of Feldman and Zrnic (12) construct an approximative individual (s, -accouuntt....
of the most versatile DP mechanisms. This ap-
INTRODUCTION
Differential privacy (DP) 8 provides means to accurately bound the compound privacy loss of multiple accesses to database. Common differential privacy composition accounting techniques such as Rényi differential privacy (RDP) based techniques (23
33
38 24) so called optimal
accounting techniques (19; 15 37) require that the privacy parameters of all algorithms are fixed beforehand. Rogers et al. (88) were the first analyse fully adaptive compositions, wherein the mechanisms are allowed to be selected adaptively. Rogers et al. (28) introduced two objects for measuring privacy in fully adaptive compositions: privacy filters, which halt the algorithms when given budget is exceeded, and privacy odometers, which output bounds on the privacy loss incurred so far. Whitehouse tightness of the so called advanced composition theorem (9). Feldman and Zmnc (12) obtain similar (s, assymmttssss via RDP analysis.
al. (44) have tightened these composition bounds using filters to match the
In their analysis using RDP, Feldman and Zrnic (12) consider individual filters, where the algorithm stops releasing information about the data elements that have exceeded pre-defined RDP budget. This kind of individual analysis has not yet been considered for the optimal privacy accountants. We make first steps in this direction by providing a fully adaptive individual DP analysis using the Gaussian differential privacy (7). Our analysis leads tight bounds for the Gaussian mechanism and it is based on determining a certain supermartingale for the hockey-stick divergence and on using similar proof techniques in the RDP-baaed fully adaptive composition results of Feldman

---

Published as a conference paper at ICLR 2023
and Zmic (12). We note that the idea of individual accounting of privacy losses has been previously considered various forms by. e.g., Ghosh and Roth (13); Ebadi et al. (10); Wang (2); Cummings and Durfee (6); Ligett et al. (22); Redberg and Wang (2
We also consider measuring the individual (s, -p-ivvac losses using the so called privacy loss distributions (PLDs). Using the Blackwell theorem, can in this case rely the results of (12) to construct an approximative (e, 6) acccuunttt that often leads to smaller individual e-values than commonly used RDP accountants. For this accountant, evaluating the individual DP-parameters using the existing methods requires computing FFT at each step of the adaptive analysis. We speed up this computation by placing the individual DP hyperparameters into well-chosen buckets, and by using pre- crepcompeeed Fourier transforms, Moreover, by using the Plancherel theorem, we obtain further speed-up.
1.1 OUR CONTRIBUTIONS
Our main contributions are the following:
We show how to analyse fully adaptive compositions of DP mechanisms using the Gaus- sian differential privacy. Our results give tight (s, (e,5)-boul)) 8--bounds for compositions of Gaussian mechanisms and are the first results with tight bounds for fully adaptive compositions.
Using the concept of dominating pairs of distributions and by utilising the Blackwell the- orem, we propose an approximative individual (e, 6)-accountant that in several cases leads smaller individual e-bounds than the individual RDP analysis.
We propose efficient numerical techniques to compute individual privacy parameters using privacy loss distributions (PLDs) and the FFT algorithm. We show that individual e-values can be accurately approximated in (nn)-time, where is the number of discretisation points for the PL.Ds. Due the lack of space this described in Appendix [
We give experimental results that illustrate the benefits of replacing the RDP analysis with GDP accounting or with FFT based numerical accounting techniques. As an observation of indepedent interest, notice that individual filtering leads disparate loss of accuracies among subgroups when training a neural network using DP gradient descent.
BACKGROUND
2.1 DIFFERENTIAL PRIVACY
We first shortly review the required definitions and results for our analysis. For more detailed dis- cussion, see c.g. (7 and (37).
An input dataset containing N data points is denoted as X = (z).... NN) E N where x; X, I s 1 < N. We say X and X' are neighbours we get one by adding or removing one element in the other (denoted X ~ X'). To this end, similarly to Feldman and Zrnic (12), we also denote X the dataset obtained by removing element x; from X, i.e.
X (a1,..., ".s...,,T:-1.. Z441 NN).
A mechanism M is (e, 8)-DP if its outputs are (s, 8) j--ddddstinggishabbll for neighbouring datasets.
Definition 1. Let and jo, 1). Mechanism M X
(e, D) if for every pair of
neighbouring datasets X, X', every measurable set E C
O,
P(M(X) E F) S (TP(M(X') E EE
call M tightly (e, DD-,, if there does not exist 8' < such that M (c, 8D)
The (s, dD bounds can also be characterised using the Hockey-stice stick divergence. For a >> 0 the hockey-stick divergence He from distribution P to a distribution Q defined as
H. (P(1Q) /
[P(L) Q(14 dt,
where for x E R, [x]+ max(0, x). Tight (e, 5)-values for given mechanism can be obtained using the hockey-stiek-diivrrenee.
2

---

Published as a conference paper at ICLR 2023
Lemma 2 (Zhu al. 37). For given 2 0. right ō(E) is given by the expression
8(e) = max Hos (M(((()))M(())) X-x
Thus, if we can bound the divergence Hes (M(()))M(X)) accurately, we also obtain accurate 6(E)-bounds. To this end we consider so called dominating pairs of distributions:
Definition 3 (Zhu al. (37.. A pair of distributions (P, Q) is dominating pair of distributions for mechanism M(X) for all neighbouring datasets X and X' and for all a > 0,
Ha(M(x))IM(X')) & (PlQQ....
the equality holds for all for some X, X', then (P, Q) is tightly dominating.
Dominating pairs of distributions also give upper bounds for adaptive compositions:
Theorem (Zhu et al. 37). (f, Q) dominates M and (P", ,Q') dominates M', then PP Q') dominates the adaptive composition M M'.
To convert the hockey-stick divergence from x P" to Q x Q' into an efficiently computable form, consider so called privacy loss random variables.
Definition 5. Let P and Q be probability density functions. We define the privacy loss function P as
(t)) = log P(I) Q(t)
define the privacy loss random variable (PRV) wP/Q as
hP/q (p) 1. ~~ P(I).
With slight abuse of notation, denote the probability density function of the random variable wp/Q by (t). and call it the privacy loss distribution (PLD).
Theorem (Gopi et al. 15). The 5(e)-bounde can be represented using the following representation that involves the PRV:
He-(P11Q) = E top
1----
E saa
[1-1
11-
(2.1)
Moreover, if Wr/q is the PRV for the pair of distributions (P, Q) and wp jQ' the PRV for the pair of distributions (P', ('), then the PRV for the pair of distributions (P x P', PP,Q x Q') is given by wP/Q wp''Q--
When we set a = e., the following characterisation follows directly from Theorem
Corollary 7. If the pair of distributions (P, Q) is a dominating pair of distributions for mechanism M, then for all neighbouring datasets X and X' and for all R.
e e ( < E top
1 -
e (p)((t)
E
Mx)(
We will in particular consider the Gaussian mechanism and its subsampled variant.
Example: hockey-stick divergence between two Gaussians. Let Fo, Ti E IR, a 2 0, and let be the density function of N M( o²) and Q the density function of (x11, a Then, the PRV wp/Q is
distributed as (Lemma 11 by 30
WP1Q N (Jo =x1)² (3o x1 )2
(2.2)
20²
Thus, in particular: (Pll)) Ha (Q) for all > O. Plugging in PLD wp/Q to the ex-
pression 2.1.. we find that for all 2 0. the hockey-stick H.- is given by the expression
EG A
E0
A
5(0)
e
(2.3)
20
A
2
3

---

Published as a conference paper at ICLR 2023
where & denotes the CDF of the standard univariate Gaussian distribution and A [To z1|- This
formula was originally given by Balle and Wang (3)
If .M is of the form M(X) f(x) + Z, where f X R and Z _N(0, La and A = maxx=xxx (Xx f(x))l2. then for zo = 0, x1 = A, (P.Q) of the above form gives a
tightly dominating pair of distributions for M (37). Subsequently, by Theorem 6 M is (e, 8)- for (()) given by 2.3
Lemma 8 allows tight analysis of the subsampled Gaussian mechanism using the hockey-stick di- vergence. We state the result for the case of Poisson subsampling with sampling rate 7.
Lemma (Zhu et al. 37). If (P.Q) dominates a mechanism M for add neighbors then (P, (1 - - P T Q) dominates the mechanism M Spoisson for add neighbors and [(1 7) Q 7 P7, P) dominates M o Spoisson for removal neighbors.
We will also use the Rényi differential privacy (RDP) (33 which is defined as follows. Rényi divergence of order 00) between two distributions P and Q is defined
a - -- log / (20)
(PII)) =
Q(t) dt.
By continuity, we have that lim (PIl)) equals the KL divergence KL(PIIQ).
Definition 9. We say that a mechanism M is (a, p)- if for all neighbouring datasets X,X', the output distributions M(X) and M(X') have Rényi divergence of order a less than p. i.e.
max X-x
S.
2.2 INFORMAL DESCRIPTION: FILTRATIONS, SUPERMARTINGALES, STOPPING TIMES
Similarly to (34) and (2),, we use the notions of filtrations and supermartingales for analysing fully adaptive compositions, where the individual worst-cast pairs of distributions not fixed but can be chosen adaptively based on the outcomes of the previous mechanisms. Given a probability space (2, IP), filtration (F,, NEN of F is sequence of a-algebras satisfying: (i) Fr C Fn+1 for all E N. and (ii) Fr C F for all n E N. In the context of the so called natural filtration generated by stochastic process Xz, E N. the o-algebra of the filtration Fn represents all the information contained in the outcomes of the first n random variables (X1... states that if random variable X is Fx)),.). Thus, if we have natural filtrations Fo...., Fn for stochastic process Xo... X,, then
X,). The law of total expectation F, measurable and F, C Fut1, then [(ta) =
[(X, .o) ([(((X Fa (Fo).
(2.4)
The supermartingale property means that for all n,
[[(X,|F=-1) S Xn-1.
(2.5)
From the law of total expectation it then follows that for all N, N( S Xo.
We follow the analysis of Feldman and Zrnic 12) and first set a maximum number of steps (denote by k) for the compositions. We do not release more information if a pre-defined privacy budget is exceeded. Informally speaking, the stochastic process X,, that we analyse represents the sum of the realised privacy loss up step n and the budget remaining at that point. The privacy budget has to be constructed such that the amount of the budget left at step n is included in the filtration Fn-1- This allows us to reduce the privacy loss of the adaptively chosen nihh mechanism from the remaining budget. Mathematically, this means that the integration [F_x) will be only w.r.t. the outputs of the nith mechanism. Consider e.g. the differentially private version of the gradient descend (GD) method, where the amount of increase in the privacy budget depends on the gradient norms which depend on the parameter values at step n - 1, i.c., they are included in Fn Then, E(X; (Fo) corresponds to the total privacy loss. If we can show that (2.5) holds for X,, then by the law of total expectation the total privacy loss less than Xg. the pre-defined budget. In our case the total budget Xo will equal the (s. -e-erve for j--aaussian DP mechanism, where μ determines the total privacy budget, and E[Xr], the expectation of the consumed privacy loss at step T, will equal the (e, -uuuue for the fully adaptive composition to be analysed.
4

---

Published as a conference paper at ICLR 2023
A discrete-valued stopping time 7 is random variable in the probability space (Q, (FF),, with values in IN which gives a decision when to stop. It must be based only on the information present at time t, i.e., it has to hold (r = t} E Fz. The optimal stopping theorem states that if the stochastic process X, is a supermartingale and if T is a stopping time, then E[Xr] S [[ - In the analysis of fully adaptive compositions, the stopping time T will equal the step where the privacy budget is about to exceed the limit B. Then, only the outputs of the (adaptively selected) mechanisms up to step I" released, and from the optimal stopping theorem follows that B[XT] S Xo.
3 FULLY ADAPTIVE COMPOSITIONS
In order to compute tight 5(g)-bounds for fully adaptive compositions, we determine a suitable supermartingale that gives the analogues of the RDP results of (12).
3.1 NOTATION AND THE EXISTING ANALYSIS
Similarly to Feldman and Zmnc 12. we denote the mechanism corresponding to the fully adaptive
composition of first mechanisms
M = (M)(
X) M,( M X))
and the outcomes of ( as (n) = (aI,..., "ai.....a,)) an), For datasets X and X', define c(a) x/Xx as P(M (X) a(m))
_x/x log (P((()()) (X') = a!ni)
and, given (m-11), we define / x as the privacy loss of the mechanism Mn.
_ log F(Mn(al" (n-1) (X )== an)
([(Mn(atn-iv x))) = On))
Using the Bayes rule it follows that /
c(n-l) X/X' + -x/// Σ 12
(c, 5)-rrivacy bounds for fully adaptive compositions via a certain privacy loss martingale. However, our approach is motivated by the analysis of Feldman and Zrnic (12). We review the main points of the analysis in Appendix A The approach of Feldman and Zmncc (1) does not work directly in our case since the hockey-stick divergence does not factorise as the Rényi divergence does. However, we can determine a certain random variable via the hockey-stick divergence and show that it has the desired properties in case the individual mechanisms M, have dominating pairs of distributions that are Gaussians. As we show, this requirement is equivalent to them being Gaussian differentially private.
Whitehouse et al. (34) obtain the delivancee-commositiionn
3.2 GAUSSIAN DIFFERENTIAL PRIVACY
Informally speaking, randomised mechanism A is μ-GDP, μ 2 O. if all neighbouring datasets the outcomes of M are not more distinguishable than two unit-variance Gaussians apart from each other 7). Commonly the Gaussian differential privacy (GDP) is defined using so called trade- off functions 7 For the purpose of this work, equivalently formalise GDP using pairs of dominating distributions:
Lemma 10. A mechanism M is μ-GDP, if and only for all neighbouring datasets X, X' and for all 0:
H. (M(()))IM(X))) - (N 1)I 1)).
(3.1)
Proof. By Corollary 2.13 of 77. a mechanism is GDG if and only it is ()P5) for all é 2 0. Φ (- -/ From we see that this is equivalent to the fact that for all neighbouring datasets X,X X' and for all 2 He (M(()))M(X)) < (N (H, 1)). By Lemma 31 of (37), Ho (M(X)))
where 5(E) + (-E +
< Ho (P, (P)Q) for all > 1if and only if H, (M(X)]IM((X') < H. (Q. for all 0 < a S 1. As P and Q are Gaussians, we see from the form of the privacy loss distribution 2.2 that H, HQ, holds for all >> 0.
(Q, P) = -H, (P. Q) and that (..I
5

---

x/ denotes the privacy loss be- Published as a conference paper at ICLR 2023
3.3 GDP ANALYSIS OF FULLY ADAPTIVE COMPOSITIONS
Analogously to individual RDP parameters
A. D. we define the conditional GDP parameters as Pm = inf [u 2 0 MM (1, a () J-GDP)
(3.2)
By Lemma 10 above, in particular, this means that for all neighbouring datasets X, X' and for all 0:
Ha(M ( am
S Ho
(0)
Notice that for all m, the GDP parameter fr depends the history a amm-1) and is therefore random variable, similarly to the conditional RDP values Pm defined in (A.I.
Example: Private GD. Suppose each mechanism Mi, E [Rt] is of the form M,(X,a)
Exex f(r,a) a) + /N(,, Since the hockey-stick divergence is scaling invariant, and since the sensitivity of the deterministic part of M,(X,a) a) is max f ( a(m- we have that Mm maxxex [lf am ((m-
We now give the main theorem, which is GDP equivalent of (Thm. 3.1, 12 Theorem 11. Let k denote the maximum number of compositions. Suppose that, almost surely,
Σn m 1 - B².
Then, (xx(X) is B-GDP.
Proof. We here describe the main points, proof with more details is given in Appendix B We mark that an alternative proof of this result given an independent and concurrent work by Smith and Thakurta (29). First, recall the notation from Section 3.1
(k)
tween ( and (X') with outputs (kk) Let E R. Our proof is based on showing the supermartingale property for the random variable Mn, (s), n E [k]. defined as
(k) 1 - X/XX
Mx(E)
(3.3)
c(m) X/X (t)
Ma(e) EE b-ll
1
L<nsk-l
where (1) = logg Rr (t))Q(() and RS, is the density function of NW B - Em= M 1) and Q is the density function of (0, 1). This implies that My(E) Ex-Ro 11-e--co(1)
-
where (I) = log( (R((()/((()) and Ro is the density function of (BB11) 1) and Q is the density function of (O, 1). In particular, this means that Mo(e) gives Ó(E) for a B-GDP mechanism.
Let Fn denote the natural filtration (a(n)). First, we need to show that E [M) S ME). Since the pair of distributions (N (0, 1)) dominates the mechanism Mg, we have by the Bayes rule and Corollary 7
- 3 -xx) - -xixx
E
Ma(e) Fe-1
E a
FR-1
(3.4)
<
E tr
1-es-
13 -u(tt) x/Xx
< (R-1(E),
where (t) = log log(P(())/(()), Pe is the density function of NN 1) and Q is the density function of N/ 1). Above we have also used the fact that c x E Fx-1- The last inequality
follows from the fact that Σm 2 S B a.s. i.e. 14 W (B² kK1 (2)) a.s., and from the data- processon inequality. Moreover,
that (B² Em=1 22) FR-2. Thus we can repeat (3.4) and use the fact that a composition of fi-GDD and w2-GDD mechanisms (m12 + T
) 2-2-DDD GDP (Cor. 3.3, 77, and by induction see that M., (E) is supermartingale. By the law of total expectation (2.4p. E[Mx(e)) < Mo(e). By Theorem E (+) = Har (X))M)))()))
and Mo(s) = H. (NBB, ()) 1)). As E was taken to be an arbitrary real number, we see that the inequality [e)] & Mo(e) holds for all E R and by Lemma 10 (x))(X) is B-GDP. n

---

Published as a conference paper at ICLR 2023
4 INDIVIDUAL GDP FILTER
Similarly to (12), we can determine an individual GDP privacy filter that keeps track of individual privacy losses and adaptively drops the data elements for which the cumulative privacy loss is about to cross the pre-determined budget (Alg. D. First, we need to define GDP filter:
[HALT, if E u B²
FB(PI...... ..AP..... ..)
(4.1)
CONT,
else.
Also, similarly to (12,, define S(x;, n)) the set of dataset pairs (S,S"), where |S] = and S is obtained from S by deleting the data element T; from S.
Algorithm 1 Individual GDP Filter Algorithm
Input: Budget B, maximum number of compositions k. initial value ag.
for j = I....,k do For each i E [N], find 11j 2 0 such that for all >> 0 and for all (8, E S(ri,)):
Ha (5 (1 d)-1))) S Ha 1))1(())))
(4.2)
Define the active set Sy: S = {a
FB FB((1) (0),) CONT}. CONT)
For all x4: set 2 ;1 ( 1|2 E Sz}.
Compute aj My My(ali-1) S,).
end for return (())
Using Theorem 11 and the supermartingale property of personalised version of M, (E) (Eq. 3.3 we can show that the output of Alg. iis B-GDP.
Theorem 12. Denote by M the output of Algorithm 7 relation, meaning that for all datasets E XN, for all i E [N] fnr all a > O:
.M B-GDP under remove neighbourhood
max(H.(MMX)))IM))) H. (M((X
Proof. The proof goes the same way as the proof for (Thm. 4.3 12) which holds for the RDP filter.
Let Fe denote the natural filter (a and let the privacy filter FB be defined as in (4.1) We see
HALT), A} is a stopping time since [T' = E Let Mn (s) be the random variable of Eq. 3.3 defined for the pair of datasets
that the random variable T' min min FB(u1
(8)
(4)
(X.X 3) or (X-"XX) X). From the optimal stopping theorem (26) and the supermartingale property
of (=) it follows that [E)] < Mo(E) for all E E IR. By the reasoning of the proof of Thm
we have that Alg. [ is B-GDP.
4.1 BENEFITS OF GDP vs. RDP: MORE ITERATIONS FOR THE SAME PRIVACY
When we replace the RDP filter with GDP filter for the private GD, we get considerably smaller e- valuues. As an example, consider the private GD experiment by Feldman and Zrnic (12 and set 100 and the number of compositions k 420 (this corresponds to worst-case analysis = 0.8 for 5 = 10 55. When using GDP instead of RDP, we can run 495 iterations for an equal value of e. Figure (Section C.4 depicts the differences in (c, vvvlluss computed via RDP and GDP.
APPROXIMATIVE (s, 8)-FILTER VIA BLACKWELL'S THEOREM
We next consider filter that can use any individual dominating pairs of distributions, not just Gaussians. To this end, we need to determine pairs of dominating distributions each iteration.
Assumption. Given neighbouring datasets X,X' X', we assume that for all i, i E [n], we can determine a dominating pair distributions (P., Q.) such that for all a > 0,
H. (M
(a))))(((()))) x')) < H. (P:l(:))
7

---

Published as a conference paper at ICLR 2023
A tightly dominating pair of distributions (P, Qi) always exists (Proposition 8,37), and on the other hand, uniquely determining such a pair is straightforward for the subsampled Gaussian mechanism, for example (see Lemma (). For the so called shufflers, such worst case pairs be obtained by post-processing (II). As we show in Appendix [C.6) the orderings determined by the trade-off equivalent. Therefore, from the Blackwell theorem 7 Thm. 2.10) it follows that there exists a stochastic transformation (Markov kernel) '' such that TP: (,(a(111), X) and TQ; M,
functions and the hockey-stick divergence
First, we replace the GDP filter condition Σn² S B by the condition (μ > 0)
E
[ ef 2mm (m(tm))
- He (N(H, ()1l)(
(5.1)
11 I.NPP...teoPPP
for all e E R. By the Blackwell theorem there exists stochastic transformation that maps Mu, 1) and (M,, to the product distributions (Pi,..., Pn) and (Qi,...,QU,, respectively. From the data-proce drocessig inequality for Rényi divergence then have
(P X x... x Qr x... x Qn) S Da (NI,, 1)),
(5.2)
for all a: 2 1, where Da denotes the Rényi divergence of order Since the pairs (P;, (:), < n, are the worst-case pairs also for RDP (as described above, due to the data-pron processo inequality), by 5.2) and the RDP filter results of Feldman and Zrnic (12). we have that for all a 2 1,
Do Da((M(X)) < Da (N (O,
(5.3)
By converting the RDPs of Gaussians in 5.3 to (E, 6)-buunds, this procedure provides (s, 8 bounds and can be straightforwardly modified into an individual PLD filter as in case of GDP. One difficulty, however, is how to compute the parameter μ in (5.1), given the individual pairs (P,, Qi),
S S n. When the number of iterations large, by the central limit theorem the PLD of composition starts to resemble that of a Gaussian mechanism (30), and it is then easy to numerically approximate j (see Fig. [ for an example). It is well known that the (e, -)bbunds obtained via RDPs are always non-tight, since the conversion of RDP to (E, is lossy (37). Moreover, often the computation of the RDP values themselves is lossy. In the procedure described here, the only loss comes from converting (5.3) (c, -buudds. In Appendix D we show how numerically
efficiently compute the individual PLDs using FFT.
To illustrate the differences between the individual e-values obtained with RDP accountant and with our approximative PLD-based accountant, we consider DP-SGD training of a small feedfor- ward network for MNIST classification. We choose randomly subset of 1000 data elements and compute their individual e-values (see Fig. [. To compute the g-values, we compare RDP account-
ing and our approach based on PLDs. We train for 50 epochs with batch size 300, noise parameter 2.0 and clipping constant C' = 5.0.
10
160
Individual e-values (via PLDs) Individual s-values (via RDPs)
140
10
120
100
10
40
10-7
Tight DP-SGD (s, 8)-P
Approximative y-GDP Upper Bound
20
0.0
0.2
0.4
0.6
0.8
0.2
0.4
0.6 c
0.8
1.0
Figure 1: MNIST experiment. Left: Randomly chose data element and its accurate (e, 8) -curve after 50 epochs the G-GDP upper bound approximation. Right: Comparison of individual e-values obtained via RDPs and PLDs: histograms for randomly selected 1000 samples after 50 epochs (8 10-00. 9). Computation using PLDS is better able to capture small individual e-values.
8

---

Published as a conference paper at ICLR 2023
EXPERIMENTS WITH MIMIC-III: CROUP-WWISH E-ISE&EVAAN E- E-VALUES
For further illustration, consider the phenotype classification task from MIMIC-III benchmark library (16) on the clinical database MIMIC-III (I7), freely-available from PhysioNet (14). The task multi-label classification and aims to predict which of 25 acute conditions present in a patient's MIMIC-III record. We have trained a multi-layer perceptron to maximise the macro- averaged AUC-ROC, the task's primary metric. We train the model using DP-GD combined with the Adam optimizer, and use the individual GDP filtering algorithm ! details.
See Appendix E for further
To study the model behaviour between subgroups, we observe five non-overlapping groups of size 1000 from the train and of size 400 from the set by the present acute care condition: subgroup O: no condition all, subgroups and 2: diagnosed with/not with Pneumonia, subgroups 3 and 4: diagnosed with/not with acute myocardial infarction (heart attack). Similarly as Yu al. (36), we see correlation between individual e-values and model accuracies across the subgroups: the groups with the best privacy protection (smallest average e-values) have also the smallest average training and test losses. Fig. shows that after running the filtered DP-GD beyond the worst-case threshold for a number of iterations, both the training and test loss get smaller for the best performing group and larger for other groups. Similarly DP-SGD has disparate impact model accuracies across subgroups (2), we find that while the individual filtering leads to more equal group-wise e- values, it leads even larger differences in model accuracies. Here, one could alternatively consider other than algorithmic solutions for balancing the privacy protection among subgroups, by. e.g.. collecting more data from the groups with the weakest privacy protection according to the individual e-values (36). Finally, we observe negligible improvements of the macro-averaged AUC-ROC in the optimal hyperparameter regime using filtered DP-GD, but similarly to (12) improvements can be seen when choosing sub-optimal hyperparameters (see Appendix E.T
average at epoch
3.75
1.25
50
3.00
1.00
2.25
0.75
Loss
Avg.
loss epoch
train (50)
test (50)
train (100)
0.75
0.25
test (100)
0.00
0.00
group
group
group subgroups
group
group
Figure 2: MIMIC III experiment and individual filtering for private GD. Comparing the test losses, training losses and average privacy losses before and after filtering has started 50 epochs). The filtering has further disparate impact on model accuracies across subgroups.
7 CONCLUSIONS
To conclude, we have shown how to rigorously carry out fully adaptive analysis and individual DP accounting using the Gaussian DP. We have also proposed an approximative (e, -accuunttt that can utilise any dominating pairs of distributions and shown how to implement it efficiently. As an application we have studied the connection between group-wise individual privacy parameters and model accuracies when using DP-GD, and found that the filtering further amplifies the model accuracy imbalance between groups. An open question remains how to carry out tight fully adaptive analysis using arbitrary dominating pairs of distributions.

---

Published as a conference paper at ICLR 2023
8 ETHICS STATEMENT
Our work is on improving differential privacy techniques, which contributes to the strong theoretical foundation privacy-preserving machine learning, an essential component of trustworthy machine learning. Our method provides accurate estimates of individual privacy loss, therefore helping to evaluate the impact of indicate that the filtered DP gradient descent has disparate impact subgroups of data, and should therefore be used with caution.
machine learning to individual privacy. Our experiments
Our experiments use the MIMIC-III data set of pseudonymised health data by permission of the data providers. The data was processed according to usage rules defined by the data providers, and all reported results are anonymised. All the code related MIMIC-III data is publicly avail- able
gdp), as requested by Physionet http:///ssa.aa..ooooocc/oooooo/t
REPRODUCIBILITY STATEMENT
All the missing details from proofs and missing proof' in the main text are given in the Ap- pendix, as well as more detailed descriptions the experiments. Pythons codes needed for the experiments and plots is made publicly available
com/DPBayes/ Individual-accoom inncuunting-oo gdd)). To compute (e, d)-bounds via RDP, we have used the con- version formula of Canonne et al. 44. GDP bounds are easily converted to (s, 6--buunds using the formula
10 ACKNOWLEDGMENTS
The authors acknowledge CSC IT Center for Science, Finland, and the Finnish Computing Com- petence Infrastructure (FCCI) for computational and data storage resources.
This work was supported by the Academy of Finland (Flagship programme: Finnish Center for Ar- tificial Intelligence, FCAI; and grant 325573), the Strategic Research Council at the Academy of Finland (Grant 336032) well as the Furopean Union (Project 101070617). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the Euro- pean Union or the European Commission. Neither the European Union nor the granting authority can be held responsible for them.
REFERENCES
[1] Akiba, T., Sano, S., Yanase, T., Ohta, T., and Koyama, M. (2019). Optuna: A next-generation hyperparameter optimization framework. In Proceedings of the 25rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.
[2] Bagdasaryan. E., Poursaced, O., and Shmatikov, (2019). Differential privacy has disparate impact on model accuracy. Advances in Neural Information Processing Systems. 32.
[3] Balle, B. and Wang, Y.-. (2018). Improving the Gaussian mechanism for differential privacy: Analytical calibration and optimal denoising. In International Conference Machine Learning, pages
PMLR.
[4] Canonne, C. L., Kamath, G., and Steinke, T. (2020). The discrete gaussian for differential privacy. Advances in Neural Information Processing Systems, 33:15676-15688.
[5] Cooley, J. W. and Tukey, J. W. (1965). An algorithm for the machine calculation of complex Fourier series. Mathematics of computation, 297001
[6] Cummings, R. and Durfee, D. (2020). Individual sensitivity preprocessing for data privacy. Proceedings of the Fourteenth Annual ACM- Symposium on Discrete Algorithms, pages 528-547. SIAM.
10

---

Published as a conference paper at ICLR 2023
[7] Dong, J., Roth, A., and Su, W. J. (2022). Gaussian differential privacy. Journal of the Royal Statistical Society Series B, 84(1):3-37.
[8] Dwork, C., McSherry, F., Nissim, K., and Smith, A. (2006). Calibrating noise to sensitivity in private data analysis. In Theory of Cryptogruphy; Third Theory of Cryptogruphy Conference, TCC, Proceedings 3, pages 265-284. Springer.
[9] Dwork, C. and Roth, A. (2014). The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., 9(3 44:2114440
[10] Ebadi, H., Sands, D., and Schneider, G. (2015). Differential privacy: Now it's getting personal. ACM SIGPLAN Notices, 50(1):69-81
[11] Feldman, V., McMillan, A., and Talwar, K. (2023). Stronger privacy amplification by shuffling for rényi and approximate differential privacy. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 4966-4981. SIAM.
[12] Feldman, V. and Zrnic, T. (2021). Individual privacy accounting via Rényi filter. Advances in Neural Information Processing Systems, 34.
[13] Ghosh, A. and Roth, A. (2011). Selling privacy at auction. In Proceedings of the 12th ACM conference on Electronic commerce, pages 199-208.
[14) Goldberger, A. I., Amaral, L. A. N., Glass, L., Hausdorff, J. M., Ivanov, P. C., Mark, R. G., Mietus, E., Moody, G. B., Peng. C.-K., and Stanley, H. E. 2000). PhysioBank, PhysioToolkin and PhysioNet: Components of new search resource for complex physiologic signals. Circulation, 101(23):e11--2220 Circula- wttp:iicchaaaouuuualsooo/otteeee
tion Electronic Pages: 10.1161/01.CIR.1 101. 10..232.2..
PMID:1085218: doi:
[15] Gopi, S., Lee, T., and Wutschitz, L. (2021). Numerical composition of differential privacy. Advances in Neural Information Processing Systems, 34: 1631-11662.
[16] Harutyunyan, H., Khachatrian, H., Kale, D. C., Ver Steeg, G., and Galstyan, A. (2019). Multi- task learning and benchmarking with clinical time series data. Scientific data, 6(1):1-18.
[17] Johnson, A. E.,, Pollard, T. J., Shen, L., Li-Wei, H. L.,, Feng, M., Ghassemi, M., Moody, B., Szolovits, P., Celi, L. A., and Mark, R. G. (2016). MIMIC-III, freely accessible critical care database. Scientific data, 3(1):1-9.
[18] Koskela, A. and Honkela, A. (2021). Computing differential privacy guarantees for heteroge- neous compositions using FFT. arXiv preprint 1XX.::2102.12412.
[19] Koskela, A.. Jälkö, J., and Honkela, A. (2020). Computing tight differential privacy guarantees using FFT. In International Conference on Artificial Intelligence and Statistics, pages 2560- 2569. PMLR.
[20] Koskela, A., Jälkö, J., Prediger, I.., and Honkela, A. (2021). Tight differential privacy for discrete-valued mechanisms and for the subsampled Gaussian mechanism using FFT. In Inter- national Conference on Artificial Intelligence and Statistics, pages 3358-3366. PMLR.
[21] Lécuyer, M. (2021). Practical privacy filters and odometers with Rényi differential privacy and applications to differentially private deep learning. arXiv preprint arXiv:2/03.01.39.
[22] Ligett, K., Peale, C., and Reingold, (2020). Bounded-leakage differential privacy. In Ist Symposium on Foundations of Responsible Computing (FORC 2020). Schloss Dagstuhl-Leebnizz Zentrum für Informatik.
[23] Mironov, I. (2017). Rényi differential privacy. In 2017 IEEE 30th Computer Security Founda- tions Symposium (CSF), pages 263-275.
[24] Mironov, L. Talwar, K., and Zhang, L. (2019). Rényi differential privacy of the sampled Gaussian mechanism. arXiv preprint arXiv: 1908. 10530.

---

Published as a conference paper at ICLR 2023
[25] Press, W. H., Teukolsky, S. A., Vetterling, W. T., and Flannery, B. P. (2007). Numerical recipes 3rd edition: The art of scientific computing. Cambridge university press.
[26] Protter, P. (2004). Stochastic integration and stochastic differential equations. Berlin: Springer- Verlag.
[27] Redberg, R. and Wang, Y.-.. (2021). Privately publishable per-instance privacy. Advances in Neural Information Processing Systems, 34:17335- 17346.
[28] Rogers, R., Roth, A., Ullman, J., and Vadhan, S. (2016). Privacy odometers and filters: pay- as-you-go composition. Advances in Neural Information Processing Systems, 10:1929-1937,
[29] Smith, A. and Thakurta, A. (2022). Fully adaptive composition for gaussian differential pri- vacy. arXiv preprint arXiv:2210.1755
[30] Sommer, D. M., Meiser, S., and Mohammadi, E. (2019). Privacy loss classes: The central limit theorem in differential privacy. Proceedings on Privacy Enhancing Technologies, 2019(2):245- 269.
[31] Stoer, J. and Bulirsch, R. (2013). Introduction to numerical analysis, volume 12. Springer Science & Business Media.
[32] Wang, Y.-X. (2019). Per-instance differential privacy. Journal of Privacy and Confidentialityy 9(1).
[33] Wang, Y.-X., Balle, B., and Kasiviswanathan, S. (2019). Subsampled Rényi differential privacy and analytical moments accountant. In The 22nd International Conference Artificial Intelligence and Statistics, pages 1226-1235.
[34] Whitehouse, J., Ramdas, A., Rogers, R., and Wu, Z. S. (2022). Fully adaptive composition in differential privacy. arXiv preprint 2rXiv:2203.0548).
YYousefpour et al.] Yousefpour, A., Shilov, I., Sablayrolles, A., Testuggine, D., Prasad, K., Malek, M., Nguyen, J., Ghosh, S., Bharadwaj. A., Zhao, J., et al. Opacus: User-friendly differential privacy library in pytorch. In NeurlPS 2021 Workshop Privacy in Machine Learning.
[36] Yu, D., Kamath, G., Kulkarni, J., Yin, J., Liu, T.-Y., and Zhang, H. (2022). Per- instance privacy accounting for differentially private stochastic gradient descent. arXiv preprint arXiv:2206.02617.
[37] Zhu, Y., Dong. J., and Wang, Y.-X. (2022). Optimal accounting of differential privacy via char- acteristic function. In Proceedings of The 25th International Conference on Artificial Intelligence and Statistics.
[38] Zhu, Y. and Wang, Y.-X. (2019). Poisson subsampled Rényi differential privacy. Interna- tional Conference on Machine Learning, pages 7634-7642.
A EXISTING ANALYSIS USING RDP BY FELDMAN AND ZRNIC 12
We next illustrate how the stochastic process Xn, that is used to analyse fully adaptive compositions determined in case of RDP analysis (1).. Central in the analysis is showing the supermartingale property (2.5 of X,,.
The fully adaptive RDP analysis by Feldman and Zmic 12 is based on studying the properties of the supermartingale M,, which they define
Ma X') = Loss(a (m) X,
" X a) (a- (a- 1>>
where a 2 1,
Loss(a (,,,,'')aa)) (((M))(() = a(m))
((M(() a!m))
12

---

Published as a conference paper at ICLR 2023
and Pm gives the RDP of order given M1:m- 1 i..
((M(()(X)) (PLM)(())
((((()))) (X) - a (m))
Pm a
log
sup (XS Mim)
R
= a(m)
a
(m-1)
(A.1)
where S is pre-determined set of neighbouring datasets In particular, the RDP bounds for the fully adaptive compositions are obtained by showing that M, (X, X') has the supermartingale property, meaning that
E.M,, X - MX,
(A.2)
Feldman and Zrnic 12 show that from this property, and from the law of total expectation 2.4
follows that Σ P: S B almost surely, where is the maximum number of compositions, then the fully adaptive composition is (a, B)-RDP (Thm. 3.1, 12)..
Due to the factorisability of the Rényi divergence, the property A..2) is straightforward to show for the random variable M, (X,, X') using the Bayes theorem:
E(,,(X, x')
= =E(Loss(a x,X', -e- -a-aa-) Fa-
(A.3)
=E (P(M,(X)) un (a(n-1))
((MM(XX) = an 11(--1)) -Toss(a ,,,,,,, .x,' e
since pi....:PP Pn Fn-1 and Loss(a (m X, X', a)) Fn-1. Moreover, as Mn pr RDP.
Loss(a!n-1) X,XXX,o
X", a) S cla-1)pn,
and the supermartingale property follows from A.3) i.e., that
(X, S M (X,
As the hockey-stick divergence does not factorise in this way, we need to take another approach to get the required supermartingale.
B
MAIN THEOREM
Theorem B.1. Let ls denote the maximun number of compositions. Suppose that, almost surely.
2 S B².
(B.1)
m=1
Then, (X) is B-GDE
Proof. First, recall the notation from Section 3.1 L x/xx denotes the privacy loss between (1) (X) and (x') with outputs (k), Let R. Our proof is based showing the supermartingale property for the random variable (c) n E [A). defined as
(kk)
Ma(e)
x/Xx
(B.2)
x/xx - (t)
Mx(s) = E bwR
1
--
0 OSnsk-1,
where (t) = log (t)Q((t)) and R2 the density function of NV Em M2 1) and Q the density function of (00 1). Moreover,
Mo(e) = E t~R
Lo(())
where Lo(1) log (t)) and Ro is the density function of N (B,1)) and Q is the density function (0, 1). Notice that in particular this means that Mo(E) gives 6(E) for a B-GDP mech- anism.
13

---

Published as a conference paper at ICLR 2023
We next show that E Ms(s) FR-1 S (e) for all The supermartingale property follows then by induction.
Since the pair distributions (N(uss (),4,,) 1)) dominates the mechanism Ma. we have by the Bayes rule and Corollary 7 that
E Ma(e) Fa-i)
E M(k)
(k)
X/X1
Fk-1
clk x/X
c
E (s)
Fk-1
clle 13 XIX
(t(
tr
where (t) log (t) and Ps is the density function of N 1) and Q is the density function of (0(00, 1). Above we have also used the fact that XX/X E Fx
Since Em Pi < B almost surely, i.e., Me V B2 E p almost surely, by the data- processing inequality for a-divergence we have that, almost surely,
E Pn
1 1
- - Zx(0) -2(()
I
1-e -- -xx" - -c-1111-111)) = -M)-1(E)
Ru
where Ck-1 log Ra (1) and Ra-1 is the density function of NN B2 >mm 12 1)
and Q is the density function of (0, 1). Therefore, Mr(E) Fk-1 Ma-1(E).
Since (41,
we have that, almost surely, E FF -.k.....--
1 5- (t-1) - C4 ((t)
M (e) Fk-2
Fx-2
alt D2M 1) LW
h- cl--2) ck-1 - -c-
E.
-
x/xx
F Fk
ak ak-
twBB
E
- e
-- -
ch-1
X/Xx
-c-1(()
F
(B.3)
(~ Ru-1
ot M-MM-1
<
E
1
1
e-
S4 2)
x/x
Ex (1 -
(~
ck X/X
Ca 2(r)
2~
-M-22
where (t) log Pe-1(t)/Q(C and Pa-1 is the density function of N (uu=1,1) 1) and Q is the density function of (V, 1). In the inequality step we use Corollary 7 and the fact that the pair of distributions 1). 1)) dominates the mechanism M ( In the second last step we have also use the fact that if P Ni 1), P N 1) and Q N(0,, 1), and
(t) = log (t() and (x) log (att)/((t), then
1 1 c 2200)2200)))
1- S-a(t) Ea(t)
E
G~ fN
where P3 A + T2 1) and (t) (t))((tt). This follows directly from the fact that the PLDs determined by the pairs of distributions (P,, Q) and (P2, Q) are Gaussians (see Eq. (2.2 the convolution of two Gaussians is Gaussian.
14

---

Published as a conference paper at ICLR 2023
By induction, from (B.3) that the the supermartingale property holds for the random variable (x).). By the law of total expectation (2.4). E[Ma(E)) I Mo(e). By Theorem
[[MM[(s]] Ho. (X)IM))M
and
Mo(e) Ho. (N( 1) 1)).
As was taken to be an arbitrary real number, the inequality B. & Mo(e) holds for all E R and by Lemma 10 we see that M (X) is B-GDP.
C FILTERS AND ODOMETERS
We here give additional details on the GDP filters and shortly discuss implementation of GDP pri- vacy odometers as well.
C.I GDP PRIVACY FILTER
For simplicity, we here consider a GDP filter that chooses the privacy parameters adaptively, but not individually (like the filter in the main text). Le., the amount that the privacy budget is spent each step has to provide a guarantee over the whole dataset.
To this end formally define GDP filter
(ALLT, if D B², CONT,
FB(
m4)
else.
Using the filter FB, GDP filter is given as Alg.
Algorithm 2 GDP Filter Algorithm
Input: Budget B, maximum number of compositions k. initial value ag. for j = .k. do
Find parameter Hj 2 0 such that Ms(:a0011) is py GDP.
if D 1 B2; then BREAK
else
end if end for return a(i-1)
In principle, the supermartingale property of the random variable (s), as defined 3..3 sufficient to show that the algorithm below is B-GDP. The only difference is that the algorithm can stop at random time. To include that feature in the analysis, we need to use the optimal stopping time theorem.
Theorem C.1. Denote by M the output of Algorithm 2 relation, meaning that for all datasets X N for all i E [N] and for all 0:
M is B-GDP under remove neighbourhood
max{Ha (M(())(( (M(
& H. (
(C.1)
Proof. The proof goes exactly the same the proof for (Thm. 4.3 12) which holds for the RDP filter. By using the fact that for all 2 0: #441 Fe, where F, is the natural filter (a)!)), that the random variable
T T min FB(HI.... (441) = HHLLT A k
is stopping time since {T' 1) E F, since p4+1 E F,. Let (s) be the random variable of From the optimal stopping theorem
Eq. (3.) defined for the pair of datasets (X,X-)) or (X-+, and the supermartingale property it then follows that for all E RR (E)] < Mole), which by the reasoning of the proof of Thm IT shows that (C.I) holds, ie.. output of Alg. 2 is B-GDP w.r.. to the removal neighbourhood relation of datasets.
15

---

Published as a conference paper at ICLR 2023
A benefit of GDP filter when compared to RDP filter is that obtain tight (e, (()))-bounds for adaptive compositions of Gaussian mechanisms. Moreover, from Thm. 10 it follows that these tight (c, (E, bounds can be obtained by an analytic formula:
Corollary C.2. For GDP-budget B > O, the oulputs of Algorithms and are (e,8(E))-DP for all & 2 0 and
B
E
B
ö(e) = +b B
e
+
(C.2)
2
B
2
C.2 GDP PARAMETERS FOR THE INDIVIDUAL FILTERING OF PRIVATE GD
Notice that we have the following for the individual GDP filtering. Suppose each mechanism Mi. i [k)] in the sequence is of the form
M, = Σ [(,,a)
TEX
Since the hockey-stick divergence is scaling invariant and since the sensitivity of of ExEx f(z ali-1)) w.r.t. to removal of z; is (I;; a(i-1))ll, we have that
= 1lf(z, al 12//o.
C.3 TIGHT BOUNDS FOR THE GAUSSIAN MECHANISM
When running e.g. the DP-GD algorithm and using either the filtering of Alg. 2 or the individual filtering of Alg. D by appropriate scaling of the gradients each individual data element can be made to fully consume its privacy budget. This scaling for individual filtering is given in (Algorithm
12).
Remark C.3. Suppose use the Gaussian mechunism and scale the noise for each data element E [N] at the last step such that the GDP budget is fully consumed, i.e., we have that E, 12
())
then the resulting algorithm is lightly (e, () for ō(e) given by the expression that for all i E [N},
sense
max(He He (M (X)II (X-)), (XXM) 5(E).
C.4 BENEFITS OF GDP VS. RDP FILTERING
To experimentally illustrate the benefits of GDP accounting, consider of the private GD exper- iments of (12), where o = 100, and number of compositions corresponding to worst-case analysis is 420. The RDP value of order a corresponding to this iteration is then a/(2 σ²), where a oo/Vk Figure 3 shows the (e, 8) -values, computed via RDP and GDP. To get the (e, 8)-valu from the RDP-values, we use the conversion formula of Lemma C.4 below. When using GDP in- stead of RDP, we can run & 495 iterations instead of the k 420 iterations, for an equal privacy budget of E = 0.8, when = 10-5
Rényi DP parameters are converted to (e, 6)PD) by minimizing w.r.t. À over the values given by
Lemma C.4 (Canonne et al. Suppose the mechanism M is (A,E')-RDP Then M is also (c, D(P)))DP for arbitrary 2 with
8(E) exp ((A - 1)(E' =)) (1 1 (1-1) X-1
(C.3)
16

---

Published as a conference paper at ICLR 2023
10-1
10
10-3
10
10
(E, 6)-DP via RDP Filtering
10-6
(E, 6)- via GDP Filtering
0.2
0.4
0.6
0.8
Figure 3: Comparison of RDP and GDP for private GD with o = 100 and number of iterations k 420 (experiment conisdered by Feldman and Zrnic (12). This means that when replace the RDP filter with GDP filter for the private GD, we can get roughly 10 percent smaller e-values.
C.4.1
FURTHER COMPARISONS OF RDP AND GDP
Figures and 5
further illustrate the differences between RDP and GDP accounting for filtering.
Figure shows the effect of number of compositions k, when 100 and Figure 5 illustrates the maximum number of compositions for given privacy budget e, when 100 and = 10-5.
10-2
10 -4
10
(c, 6)DD via RDP
Filtering (k= 300)
10-8
5)-DP via GDP
Filtering (k 300)
(s. 6)-DP via RDP Filtering (k 500)
(c. 6)-DP via GDP
Filtering (k 500)
10-10
6P via RDP Filtering 900)
(E. 5)-DP via GDP Filtering (k 900)
0.2
0.4
0.6
0.8
1.0
Figure 4: Comparison of RDP and GDP for private GD with compositions k.
100 and different number of
17

---

Published as a conference paper at ICLR 2023
600
(E, 6)-DP via PLD Filtering
max number of compositions k
(E, 6)-DP via RDP Filtering
500
400
300
200
100
0.0
0.2
0.4
0.6
0.8
1.0
Figure 5: Comparison of RDP and GDP for private GD with a = 100: maximum number of allowed
steps for private GD (number of compositions k) for different values of e, when 10-5
C.5 GDP PRIVACY ODOMETERS
We here also shortly comment on privacy odometers, considered e.g. by (88 12 21
In practice, one might want to track the privacy loss incurred so far. Rogers al. (28) were the first ones to formalise this in terms of privacy odometer. Feldman and Zmnc (12) utilise sequence of valid Rényi privacy filters such that a fixed sequence of privacy losses B1. B2... determine random stopping times Tú, T2, ... such that the privacy spent up to time T; is most B, By assuming, for example, that for all i, B B; = for a fixed discretisation parameter A > O, we may employ the RDP filter such that whenever the privacy budget counter crosses A (suppose for the mtth time) release the sequence (Tm)) and initialize the privacy loss counter to zero. The fact that a (Tm) is mA-RDP follows directly from the RDP results that hold for the filters.
With the GDP, every predetermined amount GDP budget A is spent. If at round we spend 4--GDP budget, by the results for GDP filters we know that B B + A,, and that the output a (2m) is B,, -DDP
construct in the exactly same way algorithm that outputs states always after
where B + A
C.6 BLACKWELL'S THEOREM VIA DOMINATING PAIRS DISTRIBUTIONS
There is one-to-one relationship between the orderings determined by trade-off functions and the hockey-stick divergence and this follows from the results by Zhu et al. (37) as follows. Let P and
Q be probability distributions and denote by T(P, Q) the trade-off function determined by P and Q and let Ho (PIIQ) denote the hockey-stick divergence or order a > O. The Lemma of (37) is restatement of (Proposition 2.12, (7) and it states that for any R.
H (PIIQ)
T(P. (-ce),
(C.4)
where, for trade-off function l denotes the function
f (v) sup yr fzx zER
From the equivalence follows directly, i.e., (P, Q) is another pair of probability distributions, then
He (P < H (PI[Q)
for all IR if and only if
T(P. 인 2 T(P. Q]
18

---

Published as a conference paper at ICLR 2023
This also means that, if
(Pll)) & (PllQ)
all a O, then by the Blackwell theorem (see e.g. Thm. 2.10, 7). there exists a stochastic transformation (Markov kernel) 7 such that TP P and TQ = Q.
D EFFICIENT INDIVIDUAL NUMERICAL ACCOUNTING FOR DP-SGD
We next show how to compute the individual PLDs for DP-SGD. These are needed when imple- menting the approximative individual (e, 8) -accountant described in Section 5 The errors arising from the approximations are generally negligible and a rigorous error analysis could be carried out using the techniques presented in (20) and (15).
The numerical approximation based on
1. numerical o-grid which allows evaluating upper bounds for d's efficiently; we precom- pute FFTs for different o-values and no additional FFT computations are then needed dur- ing the evaluation of the individual g-values. By the data-processing inequality this grid approximation also leads to upper (e, 6))bounds.
2. the Plancherel Theorem, which removes the need to compute inverse FFT's when evaluating individual PLDs.
First, we recall some basics about numerical accounting using FFT (see also 19 15)
D.1 NUMERICAL EVALUATION OF DP PARAMETERS USING FFT
We use Fast Fourier Transform (FFT)-basee method by Koskela et al. (19 20) called the Fourier Accountant (FA). The same approximation could be done when using the PRV accountant by Gopi et al. (15). Using FFT requires that we truncate and place the PL. w on an equidistant numerical grid over interval [- L, L), L 0. Convolutions evaluated using the FFT algorithm, and using the existing error analysis (see e.g.. 20). the error incurred by the numerical FFT approximation can be bounded.
The Fast Fourier Transform (FFT) is described as follows (5). Let x = [.o..... Fn w [Wp,.... Wn-1 R.. The discrete Fourier transform F and its inverse F-1 are defined as (31
(Fz) = Σ z,e -12xk//n
(F-
wye 12nks/n
where = I-I. Using FFT the running time of evaluating Fx and F-' w reduces to ( log n)). Also, FFT enables evaluating discrete convolutions efficiently using the so called convolution theo- rem
For obtaining computational speed-ups, we the Plancherel Theorem (Chpt. 12, 25 which states that the DFT preserves inner products: for x, R
(x, v) 1 (((x)
When using to approximate 8(e), we need evaluate an expression of the form
b" - DF oh o ... okmm))) D =
0
ln/2
E R"
In/2
where corresponds to numerical PLD for a combination of DP hyperparameters i, and k; the number of times the composition contains mechanism with this PLD.
Approximation for 5(E) is then obtained from the discrete sum that approximates the hockey-stick integral:
)(E)= = Σ -LLAASSS (1- 8
The Plancherel Theorem gives the following:
19

---

Published as a conference paper at ICLR 2023
Lemma D.I. Let Ö(E) and bt be defined above.
Denote w, R such that
(we)e = 0, e--
(D.1)
Then, have that
Ō(E) 1 (F(D::), ... ((Da)
n
Proof. See 18)
We instantly see that if both F(Dwz) and F(Da'). S i S m, are precomputed, K(e) can be computed in (n) time (where is the number of discretisation points for the PLD).
We can utilise this by placing the individual DP hyperparameters into well-chosen buckets, and by pre-computing FFTs corresponding the hyperparameter values of each bucket. Then, the approximative numerical PLD for each sequence of DP hyperparameters (e.g. sequence of noise ratios) can be written in form
F(Da σ @ J(Da"")okn
where k 's correspond to number of elements in each bucket. If we also have F(Dw:) precomputed for different values of we can easily construct numerical accountant that outputs an approxima- tion of as a function of d.
D.2 NOISE VARIANCE GRID FOR FAST INDIVIDUAL. ACCOUNTING
We next show how construct the DP hyperparameter grid for DP-SGD: numerical o-grid. We remark that Yu et al. (36) carry out similar approximations for speeding up their approximative individual RDP accountants.
Suppose we have models do...., or as an output of DP-SGD iteration that we run with subsampling ratio g, clipping constant C and noise parameter a. Also, suppose, that for given data element x, along the iteration the gradients have norms
Cz. = (af(a,,)))
0 0SiST-L.
We get the individual Eg value (or individual numerical PLD, more generally) then for the entry by considering heterogeneous compositions of DP-SGD mechanisms with parameter values
C
and Zz,
0SiST-1.
Cz,i
naive approach would require up to T FFT evaluations which quickly becomes computationally heavy. For the approximation, we determine a a-grid
= {oo..... ............0 on }
where no Z is number of intervals in the grid and
ai = min + i. mmax Miin
then encode the sequence noise ratios
Σ =
into tuple of integers
k == (ko, "hobkk,..,....... kn.)
where
# o, 0. <5
i< no:
h; i.e. ky is number of scaled noise parameters 5 hitting the bin number in the grid Σ. By the construction of the approximation, we have the following:
(D.2)
# on, SG).
i= nr.
20

---

Published as a conference paper at ICLR 2023
Theorem D.2. Consider the approximation described above. Denote the FFT transformation the approximative numerical PLD obtained with the E-grid as
0g F(Dā Ski .... F(Da" Jokn
and the corresponding ó (as function E), as given by Lemma D.1 as
0(e) (F(Dwe)) āz);
where w is the weight vector (D.I Then, have that for each 2 0: 8(c) S 8(e) + crr.
where ō(E) is the tight value of å corresponding the actual sequence of noise ratios (on.0..... Jz.n-1 and err denotes the (controllable) numerical errors arising from the discreti- sations of PLDs.
Proof. The results follows from the data- proceproesssing inequality since each Vz,i-value is placed to bucket corresponding a smaller noise ratio.
The numerical error term err can also be bounded using the techniques and results of 15 The importang thing here is that if the FFTs F(Dā") 0 < S no precomputed as well F(Dws), then evaluating 8(=) is an (n) operation.
To implement the approximative accountant described in Section 5 we numerically approximate individual upper bound μ-GDP values using the bisection method.
D.3 POISSON SURSAMPLING OF THE GAUSSIAN MECHANISM
For completeness we show how to determine the PLDs for the Poisson subsampled Gaussian mech- anism, required for the individual accounting of DP-SGD, Consider the Gaussian mechanism
M(X) E f(x) + +N
where is function f X Rd. Then, if the dataset X' and X are neighbours such that X = X'U('') for some entry x', then from the translation invariance of the hockey-stick divergence and from the unitary invariance of the Gaussian noise, it follows that, for all 2 0,
HA
H., (N (IIIII(()))))) o (0,
Furthermore, from the scaling invariance of the hockey-stick divergence, have that for all 2 0,
(X = Ha =H,(N(.,33)IW(000)
H. (
where C [1ff(x')] 2. Using the subsampling amplification results of Zhu al. (37) get unique worst-case pair (P.Q), where
P (e9,N(1,77)) (1 (1-1)) -V
where 5 = o/C. The PL.D wpyQ is then determined by P and Q as defined in Def.
E EXPERIMENTS WITH MIMIC-III
We use the preprocessing provided by 166 to obtain the train and test data for the phenotyping task. We refer to (16) for details on the preprocessing pipeline and the details on the phenotyping task. We tune the hyperparameters using Bayesian optimization using the hyperparameter tuning library Optuna (I) to maximise the macro-averaged AUC-ROC, the task's primary metric. We train using DP-GD and opacus (Yousefpour et al.) with noise parameter a ss 10.61 and determine the optimal C 0.79 in our training runs. We compute the budget B that filtering starts after 50 epochs and set the maximum number of epochs to 100. With these parameter values = 2.75, when ê = 10-3
clipping constant
21

---

Published as a conference paper at ICLR 2023
E. EFFECT OF SUBOPTIMAL HYPERPARAMETER VALUES ON FILTERED DP-GD
We study here the effect of choosing sub-optimal clipping constants by evaluating the effects of filtering using clipping constants reaching from half the optimum to five times the optimum (Fig- 6 We observe that filtering only improves the utility when choosing clipping constants that are sub-optimal (e.g., 5x the optimum). Our observations complement the observations made by (12, who also observe the largest improvements by filtering in sub-optimal hyperparameter regimes.
0.74
dipping
30000
0.5x sptmum
1.0x optmuu
1.5x optimum
3.0x optimumm
5.0x
25000
0.73
20000
untty mracco-maingedklle AUG.RO)
0.72
elements
10000
0.70
5000
clipping
0.5x opamum
1.0x optmum
1.5x
3.0x opımum
opfmuu
0.89
opoch
Figure 6: Filtered DP-GD with maximum privacy loss of (e, 8) (2.75, 10-5) using different clipping constants. Rest of the hyperparameters are tuned. Left:: The test AUC-ROČ as function of epochs. The red vertical line denotes the starting point of the filtering. Right: The number of active elements.
E.2 HISTOGRAMS OF INDIVIDUAL E- VALUES FOR THE MIMIC-III EXPERIMENT
As described in the main text, to observe the differences across subgroups, we choose five non- overlapping groups of size 1000 based on the following criteria: subgroup 0: No diagnosis at all, subgroups and 2: Pneumonia/no Pneumonia, subgroups 3 and 4: Heart attack/no heart attack. In the training data, there are total 2072 cases without a diagnosis, 4105 Pneumonia cases and total 9413 heart attack cases. We remark that it is not uncommon for patient to have multiple conditions.
During the training, we track the gradient norms Cz,; ; for all elements of the training dataset, and thus compute the individual e-values after given number of iterations for given value of 8 (8 is set to 10 -5). In Figures] and we display histograms of the individual E values after 50 epochs. With the optimal clipping constant majority of the datapoints have an individual 2.75, which is near the budget. For a clipping constant that is 5x the optimum most points are significantly smaller than 2.75.
22

---

Published as a conference paper at ICLR 2023
subgroup
subgroup
800
number of datapoints
0
2
1
3
600
400
200
0
2 individual E
3
0
2 individual E
3
Figure 7: Histogram individual e after 50 epochs without filtering when using the optimal clipping constant. A majority of the individual are near 2.75, which means that they will be deactivated in epoch 51, which uses filtering.
subgroup
subgroup
0
number datapoints
200
150
100
50
0.0
0.5
1.0
1.5
2.0
2.5
3.0
0.5
1.0
1.5
2.0
2.5
3.0
individual E
individual
Figure 8: Histogram of individual after 50 epochs without filtering when using clipping constant that is 5x the optimum. A majority of the individual e are far away from 2.75, which means that they will not be instantly deactivated in epoch 51, which filtering.
E.3 FURTHER EXPERIMENTAL RESULTS
We run the same experiment as above but now, instead of maximum privacy loss of (e = 2.75, & 10-9), using maximum privacy loss of 0.5 and 10.0. Figures 9 and 10 depict the perfor- mance in these cases (test AUC-ROC curves). We see, similarly to the experiments of (12), that the overall performance slightly increases when using the individual filtering.
23

---

Published as a conference paper at ICLR 2023
Filtered DP-GD with (E 0.5, 1e-5)
30000
27500
0.89
25000
utity (wwcro--ewnee))) cerro--eenggeoooee AUC-RDC)
22500
elementss
0.88
20000
17500
0.67
15000
0.68
12500
10000
0.85
60
29
epoch
Figure 9: Filtered DP-GD with a maximum privacy loss of (c, = (0.5, 10 10-5) using tuned hyper- parameters. Left: the test AUC-ROC function of epochs. Right: The number of active elements.
24

---

Published as a conference paper at ICLR 2023
Fillered
1e-5)
0.75
30000
25000
utilly (nacco-eeeengeeee AUC-ROC)
of aclve eloments
22800
20000
0.72
0.71
15000
12500
0.70
epoch
5poth
Figure 10: Filtered DP-GD with a maximum privacy loss of (5, (10.0, 10-5) using tuned hyperparameters. Left: the test AUC-ROC as a function of epochs. Right: The number active elements.
25


Reviews:
[{"review_id": "u2oNiij4v6", "reviewer": "Reviewer_ERD6", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "", "summary_of_the_paper": "This work derives privacy accounting for Gaussian-DP under fully adaptive composition, which gives tighter privacy bounds than RDP analysis. Efficient numerical techniques are proposed to compute the privacy parameters in practice. The theoretical findings are verified by experiments.", "summary_of_the_review": "This work derives tighter privacy accounting for Gaussian mechanisms with Gaussian-DP than RDP accounting. However the presentation needs improvement, and technical contributions is somewhat limited. ", "strength_and_weaknesses": "Strengths\n- The proposed accountant method achieves tighter bounds for the Gaussian mechanism than the commonly used RDP accounting. \n- Efficient numerical calculation method is proposed.\n\nWeakness\n- The writing can be improved. Overall the paper looks very technical. The main results and their implications do not stand out well. \n- Technically this work mainly uses existing techniques from previous works. \n- More experiments can help to sufficiently demonstrate the effectiveness of the proposed PLD method \n- The disparate loss among subgroups for DP is observed in previous works and this part is somewhat orthogonal to the main contribution of this work.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "VIvwMT-a3E", "reviewer": "Reviewer_MJHk", "summary": "", "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": "", "summary_of_the_paper": "This paper generalizes the Renyi Filter techniques and individual privacy accounting results by Feldman and Zrnic (2021) from Renyi DP to Gaussian DP. At the end of this paper, the authors use experiments with MIMIC-III to obtain a similar result to Yu et al. (2022) which shows a correlation between the average of individual privacy guarantees and the accuracies among different groups. ", "summary_of_the_review": "This paper is easy to read and follow. The authors connect the existing work together (Gaussian DP, dominating pairs, and Renyi Filter), so their results are natural and correct. It is like an exact follow-up to the work done by Feldman and Zrnic (2021). There are minor issues in this paper but I believe all are fixable. ", "strength_and_weaknesses": "Major strengths: \n1. The Gaussian DP is a special case of f-DP which is one of the optimal DP definitions for tight privacy analysis, and the Renyi filter is also one of the most important breakthroughs for fine-grained DP analysis. It is great to see this work connect these two ideas.\n\nMinor strengths: \n1. The paper is well-written and easy to read. \n\nMajor weaknesses: \n1. The results in this paper are not as comprehensive and novel as I expected. It is natural to use the idea of dominating pair of distributions which is equivalent to f-DP. Since Gaussian DP is mostly useful in asymptotic composition results, and the tight privacy analysis often requires f-DP, I would like to know why the proof of Theorem 11 cannot be generalized to f-DP. \n2. The Blackwell theorem used in Section 5 is not very appropriate since it is based on the relationship between two tradeoff functions (as shown in the Gaussian DP paper). There is no such result in the dominating pair paper (Zhu et al. 2022). I mean, the authors should provide or cite such a result that if $(P,Q)$ is a dominating pair, then the tradeoff function $T_{P,Q}$ is a lower bound for the tradeoff functions of neighboring datasets. By the way, I guess the stochastic transformation $T$ is a Markov kernel instead of a Markov process, therefore there is a typo on Page 8.\n3. The experimental results are not very related to the main topic of this paper.\n\nMinor weaknesses:\n1. The composition result of Gaussian DP is not stated in the main text (the proof description of Theorem 11) but it must be used somewhere (I know it is shown at the end of Appendix Section B, but I cannot find it in the main text.). This confuses me since in the proof of Theorem 12, the authors used $\\sum_{i=1}^t \\mu_i \\geq B$ instead of $\\sum_{i=1}^t \\mu_i^2 \\geq B^2$ (which I think is a typo and appears again in the line above Equation (5.1).)\n2. Algorithm 1 may need to be revised. I suggest the authors check 'Algorithm 2 by Feldman and Zrnic (2021)' again since we need $(X, X^{-i})$ to be any $(S_1,S_2) \\in \\mathcal{S}(X_i,n)$. By the way, I think $\\mu_{j+1}^{(i)}$ should be $\\mu_{j}^{(i)}$\n3. Theorem 12 should be put before Algorithm 1 since the two conditions, HALT and CONT, need to be defined.\n4. In Section 4.1, the worse-case analysis is said to be $(\\varepsilon=1.0, \\delta=10^{-5})$, but this is not shown in Figure 3. Is Figure 3 an average result of individual privacy accounting?\n5. In Section 6, the authors claim that 'we find that while the individual filtering leads to more equal group-wise $\\varepsilon$ values, ...' I cannot find any result that shows the 'more' equal values. There seems to be no such comparison in Figure 2.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "SQExV0gEmKA", "reviewer": "Reviewer_6fJh", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "", "summary_of_the_paper": "This paper gives new methods for privacy loss accounting in differentially private (DP) algorithms, and illustrates the improvements of its methods over prior work through experimental results. The experiments are mainly performed via the case of running private gradient descent (DP-GD) in various learning tasks. As the paper lists in Section 1.1, it contains four main contributions.\n1. Analysis of fully adaptive compositions of DP mechanisms using Gaussian differential privacy (GDP), which in turn gives tight $(\\varepsilon, \\delta)$ bounds for compositions of Gaussian mechanisms.\n2. Using the idea of dominating pairs of distributions and the Blackwell Theorem, they provide an approximative $(\\varepsilon, \\delta)$ accountant, which frequently leads to better $\\varepsilon$ bounds than the traditional Renyi differential privacy (RDP) accountants.\n3. It provides efficient numerical techniques to account for individual privacy parameters using privacy loss distributions (PLD's) and and FFT, which improves on the running time of existing accountants.\n4. It gives experimental results to show the improvements in privacy accounting over RDP for both the aforementioned methods. It also observes that a result of individual filtering is that it leads to disparate loss in accuracies among subgroups while training using a neural network via DP-GD.", "summary_of_the_review": "I do vote for acceptance of this paper based on what I wrote earlier -- the positives seem to outweigh the negatives, in my opinion. That said, my review might change depending on the authors response.", "strength_and_weaknesses": "Strengths:\n1. The paper is well-written, with the flow and the preliminary ideas being easy to follow. The definitions and the ideas are explained quite nicely, along with supporting examples at different places. I also like the idea of keeping the appendix within the same document because for me, personally, it makes it easier to read.\n2. The ideas are backed by rigorous proofs, which seem believable to me. So, the paper appears strong enough to me mathematically.\n3. The experiments support the claims, too, as the improvements over the usual RDP accountants are clearly visible.\n4. On a high level, I think this does seem to be an important problem to work on because of the existing gap between deployable DP systems and the theoretical foundations. Of course, more progress has been made, especially in the last few years to invent more practical algorithms for various applications, but tighter accounting is a great step here. It feels like a significant problem to study to learn about the limits of the existing DP tools or even for what we could possibly hope to achieve privately. Essentially, all I'm saying is that I like the paper also because of the problem they're trying to solve.\n\nWeaknesses:\n1. I did see comparisons with prior work, but only through experiments. I'm not *super* familiar with this particular aspect of DP literature, so I'm wondering if it were possible at all to have more in-depth theoretical comparisons, as well?\n2. The experiments were somewhat convincing, but not fully, if I'm honest. For example, in Figure 1, the plot of $\\delta$-vs-$\\varepsilon$ doesn't give me that much details as to how it compares with the RDP accountant. Also, I'm not sure how much we gain by improving $\\delta$ because any non-trivial DP algorithm usually has polylogarithmic dependence on $\\delta$ in its accuracy guarantees. Isn't $\\varepsilon$ the quantity we should be focussing on more? More clarity on these details would be nice, unless I'm missing something obvious.\n3. I wish I could see more applications of their work besides DP-GD. That would have given me a better idea of how useful this is for other techniques that don't involve the Gaussian mechanism, for example, those that use stability-based techniques. What do I expect the results to look like in those cases, and why?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "60GpCQXa2CK", "reviewer": "Reviewer_wyyZ", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "", "summary_of_the_paper": "The paper extends previous results on individual privacy accounting from Rényi DP to Gaussian DP. It also considers methods to maintain approximate privacy filters.", "summary_of_the_review": "A nice extension of previous individual accounting results, from the Rényi DP to the Gaussian DP case.", "strength_and_weaknesses": "## Strengths\n- The paper has adequate review of the relevant literature, is mostly self-contained, and clearly states the prior results it builds upon.\n- It provides a proof for a natural (and perhaps not surprising) extension of the prior individual privacy accounting in the RDP case.\n\n## Weaknesses\n- The technical contribution seems incremental (proof of Theorem 11), but I will leave the assessment of the paper's novelty to the experts in this particular topic.\n- Experiments should better highlight the practical use of individual GDP accounting compared to RDP. Figure C.3 shows one example for private GD, with a fixed number of steps. Perhaps showing similar plots under different settings (e.g. different number of steps) can help.\n- Experiments in Section 6 merit further discussion. Besides the disparate impact problem, the experiments suggest that even in terms of overall AUC (Figure 4), very soon after filtering starts, the overall AUC begins to drop, which suggest a limited benefit from individual accounting. Did the authors compare to not using individual accounting?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster