Individual Privacy Accounting for Differentially Private Stochastic Gradient Descent
Authors: Da Yu
Gautam Kamath
Janardhan Kulkarni
Tie-Yan Liu
Jian Yin
Huishuai Zhang
Venue: Accepted by TMLR ()

Abstract: Differentially private stochastic gradient descent (DP-SGD) is the workhorse algorithm for recent advances in private deep learning. It provides a single privacy guarantee to all datapoints in the dataset. We propose \emph{output-specific} $(\varepsilon,\delta)$-DP to characterize privacy guarantees for individual examples when releasing models trained by DP-SGD. We also design an efficient algorithm to investigate individual privacy  across a number of datasets. We find that most examples enjoy stronger privacy guarantees than the worst-case bound. We further discover that the training loss and the privacy parameter of an example are well-correlated. This implies groups that are underserved in terms of model utility simultaneously experience weaker privacy guarantees. For example, on CIFAR-10, the average $\varepsilon$ of the class with the lowest test accuracy is 44.2\% higher than that of the class with the highest accuracy.

Published in Transactions on Machine Learning Research (09/2023)
Individual Privacy Accounting for
Differentially Private Stochastic Gradient Descent
Da Yu
yudc2@maill.syuu.ce
Sun Yal-sen University
Gautam 3
g G.caai mast edu
Cheriton School of Computer Science University of Waterloo
Janardhan Kulkarni Microsoft Research
jakul@mierosofl.com
Tie- Yan Liu Microsoft Research
tyliau@microsoft.coom
Jian Yin San Yat-sen University
isshyintmmai.ssys...le
Huishuai Zhang
huchang@mmicrroofft.com
Microsoft Research
Reviewed on OpenReview: https: // openreview. net/ forum? id= 14Jcms0fpC
Abstract
Differentially private stochastic gradient descent (DP-SGD) is the workhorse algorithm for recent advances in private deep learning. It provides single privacy guarantee to all datapoints in the dataset. We propose output-specific (e, D) to characterize privacy guarantees for individual examples when releasing models trained by DP-SGD, We also design an efficient algorithm to investigate individual privacy across a number of datasets. We find that most examples enjoy stronger privacy guarantees than the worst-case bound. We further discover that the training loss and the privacy parameter of an example are well-correlated. This implies groups that are underserved in terms of model utility simultaneously experience weaker privacy guarantees. For example, on CIFAR-10, the average of the class with the lowest test accuracy is 44.2% higher than that of the class with the highest accuracy. Our code is available at pettps://githen
Introduction
Differential privacy strong notion of data privacy, enabling rich forms of privacy-preservingg data analysis (Dwork et al. 2006 Dwork Roth 2014). Informally speaking, it quantitatively bounds the maximum influence of any datapoint using a privacy parameter E, where smaller values of correspond to stronger privacy guarantees. Training deep models with differential privacy is active research area PPaernot et al.
2017 Zhu et al.
2020 Anil et al. 2021 Yu et al.
2022 Li et al.) 2022: Golatkar et al. 2022 Mehta et al., Bu et al. 2022 Mehta et al. 2022a Models trained with differential privacy not only
b022b
De et al.
2022
provide theoretical
privacy guaranlees lo their data owners
but also are more robust against empirical aacks
Rahman et al.
2018
Bernau et al. 2019 Carlini et al. 2019a Jagielski et al. 2020 Nasr et al. 2021a).
Differentially private stochastic gradient descent (DP-SG)) is the most popular algorithm for differentially private deep learning (Song et. al. 2013 Bassily el. al. 2014 Abadi et al. 2016). At. each step, DP-SGD takes
tupportted by an NSERC Discovery Grant, an unrestricted gift from Google, and University of Waterloo startup grant. Authors are listed in alphabetical order.

---

Published in Transactions on Machine Learning Research (09/2023)
CIFAR-10, test acc. 27222m2... max G
MNITT test acc -97.1 max <-2-4
5000
UTTFFace Gander, test acc.-88.2 max 6-4.5
L [TKFace:Age test scc. max cm42
9083
4200
4597
16000
7363
3500
7503-
Coun
14200
Count
22009
2300
2502
20000
2000
8000
1500
1502
4000
2363
1600
1005
2000
98
32
40
60
0.3
06
09
18
21
24
0.
15
20
25
30
35
6.
0. 05
10
20
25 30 15 40 45
Figure Individual privacy parameters of models trained by DP-SGD. The value of á is 1 x 10-5. The dashed lines indicate 30,, 50,, and 70% of datapoints. The black solid line shows the worst-casc privacy parameter.
the model from the previous step and the dataset as inputs. adds isotropic Gaussian noise to the average gradient of the current step. Models trained with DP-SGD satisfy (s, diifffeerlt privacy. The canonical notion of differential privacy, including (e, (),D, considers the worst-case privacy over all possible inputs. In the case of DP-SGD, this results in the privacy cost of all examples being computed with the largest possible magnitude of individual gradients, i.c., the gradient clipping threshold.
In practice, we may care more about the privacy guarantees of the models that will be deployed, which depend on the observed training trajectories. Broadly speaking, different examples may have very different. impacts on a trained model (Feldman & Zhang, 2020 Jiang et al., 2021j. Some examples may be easier learn and hence the magnitudes of their individual gradients along the observed training trajectory could be much smaller than the clipping threshold. Such fine-grained privacy guarantee can not be inferred by the canonical (c, 5) because it requires the privacy guarantee to hold for all possible datasets and training trajectories. In this paper, we define outyut-specific (s, 6)-DP, which adapts to the training trajectory of the model to analyze the individual privacy of DP-SGD. Our definition captures the impact of various factors, such as the training set and algorithmic randomness, on individual privacy. We also develop algorithms efficiently and accurately estimate individual privacy.
It turns out that, unsurprisingly, for common benchmarks, many examples experience much stronger privacy guarantees than implied by the worst-case DP analysis. To illustrate this, we plot the individual privacy parameters of four benchmark datasets in Figure [ Experimental details, as well as more results, are Sections f and To the best of our knowledge, this paper is the first to reveal the disparity in individual privacy when rumning DP-SGD.
Further, we demonstrate strong correlation between the privacy parameter of an example and its final training loss. That is, the examples with higher training loss also have higher privacy parameters general. This suggests that the examples that suffer unfairness in terms of worse privacy are also the ones that have worse utility. See Figure 2 for illustration. While prior works have shown that underrepresented groups experience worse utility (Buolamwini & Gebru 2018). and that these disparities are amplified when models are trained privately (Bagiasaryan et al. 2019 Hansen et al. 2022 Noe et al.] 2022 Lowy et al. 2022 we are the first to show that the privacy guarantee and utility are negatively impacted concurrently. In contrast, prior work that takes a worst-case perspective for privacy accounting, results in a uniform privacy guarantee for all training examples. For instance, when running gender classification on UTKFace, the average z of the race with the lowest test accuracy is 35.1% higher than that of the race with the highest accuracy.
1.1 Related Work
Several works have explored individual privacy analysis in difforentially private learning. Jorgensen ot al. 2015 Mühl & Boenisch 2022)). and the work subsequent to ours of Boenisch et al. (002)) design learning algorithms that satisfy prespecified individual privacy parameters. Those prespecified parameters are independent of the learning algorithm, e.g., in some applications different users may have different expectations of privacy, WWang (2019) defines Per-instance differential privacy to analyze individual privacy when the target example is put in
fixed dataset. Redberg & Wang 2021 investigate per-instance DP of the objective perturbation algorithm
2

---

Published in Transactions on Machine Learning Research (09/2023)
Test CIFAR-10
UTKface-Gender
Test Acc.
7.5
90
7.3
97.5
26
Accuracy (in %)
Accuracy (in %
80-
0.5
92.5
AveraoE
2.0
70
-5.5
67.5
85.0
62.5
Privacy Parameter
4.5
Privacy Parameter
14
ship Auto. Bruck Frog Harse Air. Dog Dear Bird Cat Subgroup Name
Indian
Black
White Subgroup Name
Adian
Figure 2: Accuracy and average of different groups on CIFAR-10 and UTK-Face. Groups with worse accuracy also have worse privacy general.
2022 explore per-instance DP of differentially private batch gradient descent. Redberg & Wang (2021]: Golatkar et al. (2022) focus on (strongly) convex objective functions because otherwise fixing the dataset not sufficient to determine the individual privacy parameters. In this work, we define oulput-specific (e, 6)-D that allows us to study the individual privacy of non-convex models
Kifer et al. 2012). Golatkar et al.
trained by DP-SGD, We also conduct experiments several datasets and demonstrate strong correlation between privacy and utility.
Feldman & Zrnic 2021): Koskela et al. (022 design individual privacy fillers to make use the variation in individual sensitivity. The filters allow examples with smaller per-step privacy costs to run for more steps until the accumulated cost reaches a target budget. By design, the target budget has to be constant that is independent of the learning algorithm. Consequently, the formal privacy guarantee offered by the filters is still uniform for all examples.
Our oupput-specific (e, 8)-DP and the notion of ex-post DP by Ligett et al. (2017) both tailor the privacy guarantee to algorithm outcomes. Ex-post DP bounds the ratio between two probability /density functions at a single outcome. It can be generalized to pure differential privacy ((e, O)-DP. In contrast, DP-SGD uses Gaussian mechanisms and provides approximate differential privacy ((s, D)-D). There is no clean conversion between (e, 8)-DP and ex-post DP (Meiser 2018). Therefore, our notion necessary for analyzing individual privacy within the (s, 6D framework.
2 Preliminaries
We first give some background DP-SGD and explain why the canonical (s, 6) is not suitable for measuring individual privacy. Then define output-specific (e, (P..) Finally, give empirical evidence showing that providing the same privacy to all examples is not idcal.
2.1 Background on Differentially Private SGD
The privacy guarantee of DP-SGD is measured by (e, diiffferrnt privacy.
Definition 1. [(s, ()DP An algorithm A: D + O satisfies (e, -)dffferrenti privacy if for any pair of neighboring dalasets DD, ID' E D and any subset of oulputs $ C C it holds that
Pr(A(D) E < e Pr(A(D') E S
Two datascts D. DD are neighboring datascts if they only differ in one datapoint. DP-SGD uses Rényi differential privacy (RDP) (Mronnov] 2017 in privacy accounting to get a tighter composition bound (Abadi et al.] 2016). After training, the accumulated RDP converted (e,8)-DP. RDP measures the Rényi divergence at different orders. The Rényi divergence between two probability distributions μ and v order is
1 dp y
Da(ulv)) = a- log
3

---

Published in Transactions on Machine Learning Research (09/2023)
Let D (xll)) (x(ll)a) be the maximum divergence of two directions. The definition of RDP is as follows.
Definition 2. [Rényi differential privacy (Mironoy, 2017)/ A randomized algorithm A: D - O satisfies
() if for any neighboring datasets D, DD' E D it holds that
(Z(A()IA)) S.
When A is deep learning algorithm, it is infeasible to directly measure the output distributions because of the non-convex nature of neural networks. To address this, DP-SGD makes each gradient update differentially private and uses the composition property of different ial privacy to reason about the overall privacy cost.
Definition 3. /Composition of RDP (Mironov, 2017 1 Let A D + O, be (a, (1), RDP and A O XD + O2 be (a, (2))22)DDP then the mechanism defined as (X,Y), where X ~ AI and Y A2), satisfies (o + P2)-RDP.
The output of the composed algorithm is tuple containing the outputs from all steps. Consequently, the output of DP-SGD at stop is a sequence of models (01, (y)
The privacy cost of a target example depends on its gradients along the training trajectory. We formalize the output distributions of DP-SGD at cach step to illustrate this. DP-SGD uses Poisson sampling, i.c., each example is sampled independently with probability p. Let v = Eiem 9: be the sum of the minibatch gradients of D. where M. the set. of sampled indices. Consider also a neighboring dataset IT> that has one datapoint (with gradient g) added. Because of Poisson sampling, the output is exactly with probability 1-p (g is not sampled) and is v' + g with probability p (g is sampled). After adding isotropic Gaussian noise, the putput distributions of two neighboring datasets are
A(D) ((v,021)
(1)
A(D') ~ oN with prob. 1 -
A(D') ~N(',, with prob. p.
(2)
The RDP of d at the current step is the Rényi divergences between Equation 1 and P For given o and p, the divergences are determined by the L2 norm of g v' v. Therefore, a larger gradient would result in larger privacy cost. If consider all possible i O.-1 required by Definition [ we would have to compute the divergences with the largest possible magnitude of Abadi et al. (2016) use the gradient clipping threshold to compute the privacy cost, which results in worst-casc privacy analysis for every example.
2.2 Output-specific (e, (DiferrDillllttiaal Privacy
We define output-specific individual (e, diifferrent privacy to provide a fine-grained analysis of individual privacy. It makes the privacy parameter & a function of the outputs and the target datapoint.
Definition 4. (Output-specific individual (s, d)DDP Fix a datapoint d and set of outcomes & C O. Let IB be an arbitrory dataset and D' = DD u [d), an algorithm A:D D + satisfies output-specife individual (e(A, d)) for d h. if for any SCA
Pr(A(D) E 8] S (((A,)) Pr(A(D') E S] +
Pr(A(D') E < dlA,d) Pr(A(D) E S] +
Definition 4 is a strict generalization of (s, DP as one can recover (s, 6)-DP by maximizing E(A, d) over A and d. With & being a function of some outcomes, we can analyze the individual privacy of models trained by DP-SGD by fixing the first T' models (O,,.... 0r- which fully specify the gradients along the training. Such fine-grained analysis is meaningful because the privacy risk of deploying specific model that is always bound to observed training trajectory.
4

---

Published in Transactions on Machine Learning Research (09/2023)
DP-SGD with Emax 7.5
Airplane
Automabile
Cat
Median Gradient Norm
10
2
50
100
200
Epoch
Figure 3: Median of gradient norms of different classes when training a ResNet-20 model on CIFAR-10.
2.3 Gradients of Different Examples Vary Significantly
At each step of DP-SGD, the privacy cost of an example depends on its gradient at the current step (see Section 2.1 for details). In this section, we empirically show gradients different examples vary significantly to demonstrate that different examples experience very different privacy costs. We train a ResNet-20 model with DP-SGD on CIFAR-10. The maximum clipping threshold is the median of gradient norms initialization. More implementation details are in Section 4 We plot the median of gradient norms of three different. classes in Figure 3 The gradient norms of different classes show significant stratification. Such stratification naturally leads to different privacy costs. This suggests that it is meaningful to further quantify individual privacy parameters.
3 Individual Privacy of DP-SGD
Algorithm 1 shows the implementation of DP-SGD Abadi al., 2016). Thcorem 3.1 gives the individual privacy analysis of DP-SGD. Algorithum 2 gives the pseudocode for computing individual privacy parameters. At each step, Algorithm 2 uses the (estimated) individual gradient norms to compute per-step Rényi differential privacy (RDP) for every example. It also updates the individual gradient norms and the accumulated RDP. We introduce two arguments in Algorithm to reduce the computational cost of individual privacy accounting. The first one is the frequency K of computing batch gradient norms and the second one is whether to round individual gradient norms with a small constant r. More discussion on these two arguments could be found in Soction 3. and 3.2
Theorem 3.1. Let (0.....00-1)) be the observed models step Suppose we run Algorithon with K log(1/8) and without rounding, then Algorithmm 1 salisfies (ou + a-I" -oooopeuu- individual DP for the in exomple al A (01...., 0,,1, where (t) is the accumulated RDP al order and O is the range of Ac-
Proof Skelch. At step 1, given the observed models (01,...,0,.)) 0--1), the composited training algorithm
A (2), (B) A.(O,.... 0,,,,,
We first use the composition theorem show the accumulated RDP the RDP of A Then we prove the RDP bound on (1) gives output-specific-(e.bb 8DP bound Algorithm We relegate the proof to Appendix
'Our implementation of DP-SGD follows the privacy analysis in Abdi et al. 2016) which uses Poisson sampling. We note
that many existing implementations of DP-SGD use shuffle data instead of Poisson sampling enforce stochasticity. Shuffle data is easier to implement but using it would create mild discrepancy with the analysis in Abadi al. (2016). Formal privacy
analysis of shuffle data requires privacy amplification by shuffling (Koskela al.
2023
Wang 2023
Feldman et al. 2023
5

---

Published in Transactions on Machine Learning Research (09/2023)
Algorithm Differentially Private SGD
Input: Clipping threshold C, noise variance o², sampling probability p, number of steps T.
Let {Z() = C) be the estimates of individual gradient norms, initialized as C.
Let (o(0) - be the accumulated individual RDP.
for t= 0 to T
do
//Indiviual privacy accounting.
Run Algorithm
2 with {2()) J==1 and fo
J==1.
Update (2 N=1 and {o M==1 with the results of Algorithm 2
//Run DP-SGD usual. Sample a minibatch of gradients (g {g with probability p, where the sampled indices.
Clip gradients g(::) clip(g()), C).
Update model 0r = 0 (Eg(5) + +)), where 2 ~ N2),
end for
Algorithm Individual Privacy Accounting for DP-SGD
Individual gradient norms (Z (n accumulated individual RDP {o())= Ji=1 frequency K of updating
Input:
rounding precision r, current iteration t.
if mod K = 0 then
// Updae individual sensitivity:
Compute batch gradient norms (I]g 11 Update 7 min(]]g() C).
if use rounding then //Reduce the number of different norms.
Update (7 = arg min,ec(le. - //))>>>>>> where C (r, 2r, C. contains all possible norms. end end
// Compute the current step RDP. Compute the Rényi divergences between Equation and numerically with Zi, p. and 0² and store the result in p
//Update the accumulated RDP.
( of0) + +(%
return {2"0] [o J
Remark 1. Algorithm 2 does not change the worst-case privacy guarantee (Definition of DP-SGD because it does not modify the update rule.
In Theorem we run Algorithm 2 with K = 1 and without rounding individual gradient norms. This configuration computationally expensive for two reasons. Firstly, setting K requires computing batch gradient norms at each SGD update. Secondly, the number of unique gradient norms large without rounding. Each unique gradient norm corresponds to different single-step RDP that needs to be computed numerically. In Section 3.1 we give more details the computational challenges. In Section 3.2 use larger K and round individual gradient norms to provide cstimations of individual privacy. This greatly improves the we show the estimates of individual privacy parameters are accurale.
efficiency of Algorithm 2 In Section 3.3
3.1 Computational Challenges of Individual Privacy
The first challenge is that computing exact privacy costs at each step requires batch gradient norms, which is impractical when running SGD. At each update, we need the gradient of every example compute the corresponding RDP between Equation D and 2 The worst-case privacy analysis of DP-SGD does not have this problem because it simply assumes all examples have the maximum possible gradient, i.c., the clipping threshold.

---

Published in Transactions on Machine Learning Research (09/2023)
CIFAR-10: y= 0.5
MNIST: y= 0.5
UTKFace-Gender; 0=5
UTKface-Age: y=
Estimated
Estimated E
2
Estimated
Estimated
3-
y
x
2-
y
y= 7.8
/= 2.4
y 4.5
y = 4.2
Praraana 0.903
Naamarrr 3.00
1--1-000
Maw cl.00.44 54
0.355
Mov
0.20
3
4
Actual
Actual
Actual
Actual
CIFAR-10: y=1
MNIST: y= 1
UTKFace- acee-enderr y= 1
UTKFace-Age: y
Estimatedd 3
Estimated
2-
Estiaated
Estimatedd
3-
y
y=x
y-x X
2-
y -
y= 7.8
2.4
y= 4.5
y 4.2
Peamsnte 3 3.350 Aug 11-4
Phaneon >- 0.903
Seartanter: ei 1.000
1-
Peamonn c 1.200 Aug [F- (F-
Arg [--1- 0.04
Apg 1--0 Max 0.334
0.255
-0.77
i
3
4
Actual
Actual e
Actual e
Actual
CIFAR-10: y= 3
MNIST: y=
UTKFace- ace-Gender; y= 3
UTKFace-Age: y=3
3-
Estimated
Estimated
Est/mated e
Estimated
2
3
3-
y X
y=x x
y-x X
2-
y -
y=
2.3
y= 4.5
y =
Pearaana 0.503
Nearazr's r- 1.000
Tearson 1.200 Arg. 18 1 Moue 0.30.7
Arg. if- -1.000
Arg. (F-v1- 0.01
Ang: 1 Max 0.36
Ii- (4--)-000 32
Havl (2 -.0.07
0
0
0
Actual
Actual e
Actual g
Actual
Figure 4: Privacy parameters based on estimations of individual gradient norms (c) versus those based on exact ones (f). The value of y denotes the number of updates of full gradient norms per epoch. The horizontal line shows the worst-case privacy guarantec.
The second challenge is that the RDP of every example at each step needs to be computed numerically. It has been shown that numerical computations are necessary to get tight bounds the Rényi divergences between Equation and 2 Abadi et al. 2016 Wang et al.) 2019 Mironov et al. 2019 Gopi et al. 2021). h. In Abadi et al. 2016) only one numerical computation is required because all examples are assumed to have the worst-case privacy cost. However, when computing individual privacy parameters, the number of numerical computations the same as the number of different gradients that could be as large as n x T, where n is the datasct size and T is the number of itcrations.
3.2 Improving the Efficiency of Individual Privacy Accounting
We only compute the batch gradient norms every K iteration to reduce the computational overhead. The norms are then used to estimate the privacy costs for the subsequent iterations. We note that providing estimates of privacy costs inevitable when the computational budget is limited. This is because, by the nature of SGD, one does not have the exact individual gradient norms at every iteration. In Appendix [..2] we explore another design choice which is to clip (()) with Z in Algorithm [ Although this slightly changes the implementation of DP-SGD, Algorithmm 2 would relurn the exact privacy costs. We run experiments with this design choice and report the results in Appendix B.2 Our observations in the main text still hold in Appendix B.2
To reduce the number of numerical computations, we round individual gradient norms with a small constant r. Because the maximum clipping threshold C constant, then, by the pigeonhole principle, there are at most [C/r] different values of gradient norms, and hence there are most [C/r] different values of RDP between Equation [ and (2). Note that should be small enough to avoid underestimation of RDP. We set 0.010 throughout this paper.
7

---

Published in Transactions on Machine Learning Research (09/2023)
Table 1: Computational costs of computing individual privacy paramcters for CIFAR-10.
w/ rounding
w/o rounding
# of computations
1 x 10
1 x 10
Time (in seconds)
3
2.6 x 10*
We compare the computational costs with/wiin with/without rounding in Table 1 We run the numerical method in Mironov et al. (2019) once for every different value RDP (with the default setup in the Opacus library Yousefpour et al. 2021a)). We run DP-SGD on CIFAR-10 for 200 epochs. The full gradient norms are updated once per epoch. All results in Table use multiprocessing with cores of an AMD EPYC" 7V13 CPU. With rounding, the overhead of computing individual privacy parameters is negligible. The computational cost without rounding is more than 7 hours.
3.3 Estimates of Individual Privacy Are Accurate
We run Algorithm 2 with the setup in Section 3.2 and compare the results with ground-truth values. To compute the ground-truth individual privacy, randomly sample 1000 examples before training. During training, compute the exact privacy costs for the same 1000 examples at every iteration.
We compute the Pearson correlation coefficient between the estimations and the ground-truth values. We also compute the average and the worst absolute errors. We report results on MNIST, CIFAR-10, and UTKFaae. Details about the experiments are in Section 4 We plot the results in Figure 4 The estimations of close to those ground-truth values (Pearson's
0.99) even when only update the gradient norms every two epochs (7 = 0.5). Updating batch gradient norms more frequently further improves the estimation, though doing so would increase the compulational overhead.
It is worth noting that the maximum clipping threshold C affects the computed privacy parameters. Large C increases the varialion of gradient norms (and hence the variation of privacy parameters) but leads to large noise variance while small C suppresses the variation and leads to large gradient bias. Large noise variance and gradient bias are both harmful to learning (Chen et al. 2020 Song et al., 2021). In Appendix C we show the influence of using different C' on both accuracy and privacy.
3.4 What Can We Do with Individual Privacy Parameters?
Individual privacy parameters depend on the private data and are thus sensitive. They can not be released publicly without care. We describe some approaches to safely make use of individual privacy parameters.
The first approach is to release e to the owner of d, This approach does not incur additional privacy cost for two reasons. First, it is safe for d; because only the rightful owner sees E,. Second, releasing E; does not increase the privacy cost of any other example d; # d,. This is because computing can be seen as a post-processing of (01....,0,. 0z-1), which is reported in a srivacy-preservine manner. We prove the claim in Theorem 2.
Theorem 3.2. Let A: D - O be algorithm that is (Ej, -ppppt---peeiif individual DP for d, at A C O. Let (c,d,) :0) 0 R O be post-processing function that returns the privacy parameter of d, (# d and the training trajectory. We have (. dz) is (ej, (0o,,))-ulppl---pp -pipps----eii DP for d, al R x O where F = (f (a, de) E A} all possible post prost-rocessing results.
Proof. First note that the construction of f (:; di) does not increase the privacy cost of d, because it is independent of dy. Without loss of generality, let D, D' E D be the neighboring datasets where D' = D U (d,}. Let be an arbitrary event and T {a E A (a, d') E S). Because ʃ is a bijective function, we have
Pr[ (A(D), Pr (A(D) E T
S E Pr(A(D') E T 6
(4)
e Prif (A(D'), d:) +5,
(5)
8

---

The experimental sctup is as Published in Transactions on Machine Learning Research (09/2023)
Table Statistics of individual privacy paramcters can be accurately relcased with minor privacy costs. The average estimation error rale is 1.13% for MNIST and 0.91% for CIFAR-10. The value of 8 is 10-5.
MNIST
Average
0.1 0.1-quantile
0.3-quantile
Median
0.7-quantile
0.9-quantile
Non-private
0.686
0.236
0.318
0.431
0.697
1.682
8 = 0.1
0.681
0.238
0.317
0.436
0.708
1.647
CIFAR-10
Average
o.l-quantile
0.3-quantile
Median
0.7-quantile
0.9-quantile
Non-private
5.942
2.713
4.892
6.730
7.692
7.815
E = 0.1
5.939
2.801
4.876
6.744
7.672
7.923
which completes the proof. Using a bijective post-processing function is necessary for Theorem 3.2 to hold. Otherwise, there may be some & A and a E A that have the same processed output, which invalids the derivation from Equation to Equation 5
The second approach to privately release aggregate statistics of the population, e.g., the average or quantiles of the e values. Recent works have demonstrated such statistics can be published accurately with a minor privacy cost Andrew ct al. (021). Specifically, we privately release the average and quantiles of the values. We report the results on CIFAR-10 and MNIST. For releasing the average value of é, we use the Gaussian Mechanism. For releasing the quantiles, we use 20 steps of batch gradient descent to solve the objective function in Andrew et al. (2021) h with the default sctup. The results are in Table The released statistics are close to the actual values under 101110-
Finally, individual privacy parameters can also serve as a powerful tool for a trusted data curator to improve the model quality. By analyzing the individual privacy parameters of a dataset, a trusted curator can focus on collecting more data representative of the groups that have higher privacy risks to mitigate the disparity in privacy.
4 Individual Privacy Parameters on Different Datasets
In Section 4.1 we first show the distribution of individual privacy parameters on four tasks. Then we study how individual privacy parameters correlate with training loss in Section 4.2 follows.
Datasets. We use two benchmark datasets MNIST (n 60000) and CIFAR-10 (n 50000) LeCun et al., 1998; Krizhevsky| 2009) as well as the UTKFace dataset (n 15000) (Zang et al. 2017) that contains the face images of four different races (White, > 7000; Black, ~ 3500; Asian, ~ 2000; Indian, ~ 2800). We construct two classification tasks on UTKFace: predicting gender, and predicting whether the age is under 30 We slightly modify the dataset between these two tasks by randomly removing a few examples to ensure each race has balanced positive and negalive labels.
Models and hyperparameters. For CIFAR-10, we use the WRN16-4 model in De al. (2022), which achieves advanced performance in private setting. We follow the implementation details in De et al. (2022) expect their data augmentation method to reduce computational cost. For MNIST and UTTKFace we use ResNet20 models with batch normalization layers replaced by group normalization layers. For UTKFace, we initialize the model with weights pre-trained on ImageNet.
We set C= on CIFAR-10, following De et al. 2. For MNIST and UTKFace, we set C as the median of gradient norms at initialization, following the suggestion in Abadi et al. (2016). The privacy cost of using the median not taken care of. However, the median of gradient norms could be released accurately with a small privacy cost The batchsize is 4096 for CIFAR-10 and 1024 for MNIST and UTKFace. The training epoch is 300 for CIFAR-10 and 100 for MNIST and UTKFace. For target maximum E, use the package
2We acknowledge that predicting gender and from images may be problematic. Nonetheless, as facial images have previously been highlighted as setting where machine learning has disparate accuracy on different groups, revisit this domain through related lens. The labels are provided by the dataset curators.
For instance, if we use the algorithm in Andrew et al. (2021) to privatize the median gradient norm of the UTKFace-Gender datasct with (a 0.1,6 1 10 9). The non- oon-private median 15.73 and the privatized median is 15.82.

---

Published in Transactions on Machine Learning Research (09/2023)
CIFAR 10 (Pearsan's 0.91)
MNIST [Pearson's 0.92)
UTKFace Gender (Pearsan's 0.93)
UTKFace Age [Pearson's 0.93)
2.0
2
1
== 0.30kggM 7.67
7.8
0.5
y 0.22llog40++13
y.2
y 0.200ogte: +4.10
4.7
== 0.330gglkl
4.3
10
Figure 5: Privacy parameters and final training losses. Each point shows the final training loss and privacy parameter of one example. Pearson's r is computed between privacy parameters and log loss values.
in the Opacus library to find the corresponding noise variance Yousefpour et al. (2021b). We update the batch gradient norms three times per epoch for all experiments in this section (the case of 3 in Figure 4 All experiments are run on single Tesla V100 GPUs with 32G memory. Our source code will be publicly available.
4.1 Individual Privacy Parameters Vary Significantly
Figure [ shows the individual privacy parameters on all datascts. The privacy parameters vary across large range on all four tasks. On the CIFAR-10 dataset, the maximum & is 7.8 while the minimum e; 1.0. When running gender classification on the UTKFace dataset, the maximum & is 4.5 while the minimum E is only 0.1.
We also observe that, for easier tasks, more examples enjoy stronger privacy guarantees. For example, ~55% of examples reach the worst-case & on CIFAR-10 while only ~3% do so on MNIST. This may be because the loss decreases quickly when the task is easy, resulting in gradient norms also decreasing and thus stronger privacy guarantees.
4.2 Privacy Parameters and Loss Are Positively Correlated
We study how individual privacy parameters correlate with final training loss values. The privacy parameter of one example depends on its gradient norms along the training. In strongly convex optimization, the loss value of an example is reflected the norm gradient. However, for non-convex deep models, there is no clear relation between the final training loss of one example and its gradient norms. Therefore, we run experiments to reveal the empirical correlation between privacy and utility.
The individual privacy parameters increase with loss until they reach the maximum e. To quantify the order of correlation, further fit the points with one-dimensional logarithmic functions and compute the Pearson correlation coefficients between the privacy parameters and log loss values. The Pcarson correlation cocfficients are larger than 0.9 all datasets, showing logarithmit correlation between the privacy parameter of datapoini and its final training loss. In Appendix D we experiment with C = 5 and C = 10 on CIFAR-10 10 to study the correlation between training loss and privacy under various clipping thresholds. The Pearson correlation coefficients are 0.89 and 0.9 for C' 5 and = 10, respectively, suggesting that there is still a positive logarithmic correlation.
We visualize individual privacy parameters and the final training loss values Figure 5
5 Groups Are Simultaneously Underserved in Both Accuracy and Privacy
It is well-documented that the accuracy of machine learning models may be unfair for differont subpopulations
Buolamwini & Gebru 2018 Bagdasaryan et al. 2019 Suriyakumar et al. 2021 Our finding demonstrates
that this disparity may be simultancous terms of both accuracy and privacy. We empirically verify this by plotting the average and test accuracy of different groups. The experiment setup is the same Section 4 For CIFAR-10 and MNIST, the groups the data from different classes, while for UTKFace, the groups are the data from different races.
10

---

Published in Transactions on Machine Learning Research (09/2023)
MNIST
UTKFace-Age
100
Test
Test Acc.
3.2
3.00
Accuracy (in %)
98.
Accuracy tin %6
97-
0.8
2.50
Averag
80
96-
-0.6
2.25
95-
0.4
70-
1.75
93
Privacy Parameter
Privacy Parameter
1.50
Adan
White
Indian Subgroup Name
Black
Subgroup Name
Figure 6: Accuracy and average s of different groups on MNIST and Uge- Groups with worse accuracy also have worse privacy in general.
We plot the results in Figure 2 and 6 The groups are sorted based on the average E. The test accuracy of different groups correlates well with the average & values. Groups with worse accuracy do have worse privacy guarantees general. On CIFAR-10, the average ε of the 'Cat' class (which has the worst test accuracy) is 44.2% higher than the average of the 'Automobile' class (which has the highest test accuracy). On UTKFace-Gendee Gender, the average of the group with the lowest test accuracy ('Asian') is 35.1% higher than the average of the group with the highest accuracy ('Indian'). Similar observation also holds on other tasks. To the best of our knowledge, our work is the first to reveal this simultaneous disparity. In Appendix D we run membership inference attacks to show the disparity in privacy parameters reflects the disparity in empirical privacy risks.
6 Conclusion
We define output-specific individual (s, diifffernntt privacy to characterize the individual privacy guarantees of models trained by DP-SGD. We also design an efficient algorithm to accurately estimate the individual privacy parameters. We use this new algorithm to examine individual privacy guarantees several datasets. Significantly, we find that groups with worse utility also suffer from worse privacy. This new finding reveals the complex while interesting relation among utility, privacy, and fairness. It suggests that mitigating the utility fairness under differential privacy more tricky than doing so the non-private case. This is because classic methods such as upweighting underserved examples would exacerbate the disparity privacy. We hope that our work sheds new light on this timely topic.
Broader Impact
One way utilize individual privacy parameters is to release them corresponding users (see Section 3.4 for details). This provides more accurate, and hence more responsible, privacy report. However, releasing individual privacy parameters may pose new challenges when machine learning system enables data deletion, also known as machine unlearning (Ginart et al. 2019: Bourtoule et al. 2019). ) Data deletions may worsen the privacy guarantees of the remaining examples [Carlini et al. 2022). Moreover, groups with larger may send deletion requests more frequently than others, which could further deteriorate their privacy guarantees (Hashimoto et al. 2018). It's important to keep these considerations in mind when implementing both data deletion and individual privacy accounting in real-world settings.
Acknowledgments
The authors express their gratitude Yu-Xiang Wang and Saced Mahloujifar for their valuable comments an earlier version of this paper, and to the anonymous reviewers for their insightful feedback.
11

---

Published in Transactions on Machine Learning Research (09/2023)
References
Martin Abadi, Andy Chu, lan Goodfellow, H Brendan McMahan, llya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of ACM Conference on Compuler and Communica- tions Security, 2016.
Galen Andrew, Om Thakkar, Brendan McMahan, and Swaroop Ramaswamy, Differentially private learning with adaptive clipping. In Advances in Neural Information Processing Systems, 2021.
Rohan Anil, Badih Ghazi, Vineet Gupta, Ravi Kumar, and Pasin Manurangsi. Large-scale differentially private BERT. arXiv preprint arXio:2108. 01624, 2021.
Eugene Bagdasaryan, Omid Poursaced, and Vitaly Shmatikov. Differential privacy has disparate impact on model accuracy. In Advances Neural Information Processing Systems, 2019.
Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In Proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science, 2014.
Daniel Bernau, Philip-Williien Grassal, Jonas Robl, and Florian Kerschbaum. Assessing differentially privale deep learning with membership inference. arXiv preprint arXiv: 11328, 2019.
Franziska Boenisch, Christopher Mühl, Adam Dziedzic, Roy Rinberg, and Nicolas Papernot. Have your way: Individualized privacy assignment for dp-sgd. arXiv preprint arXiv:2303. 17046, 2023.
Lucas Bourtoule, Varun Chandrasekaran, Christopher Choquette-Choo, Hengrui Jia, Adelin Travers, Baiwu Zhang, David Lie, and Nicolas Papernot. Machine unlearning. arXiv preprint arXiv:1912.088 2019.
Zhiqi Bu, Jialin Mao, and Shiyun Xu. Scalable and efficient training of large convolutional neural networks with differential privacy. arXiv preprint xrXiu:2205.10683, 2022.
Joy Buolamwini and Timnit Gebru, Gender shades: Intersectional accuracy disparities in commercial gender classification. In Conference on Fairness, Accountability, and Transparency, 2018.
Nicholas Carlini, Chang Liu, Úlfar Erlingsson, Jernej Kos, and Dawn Song. The secret sharer: Evaluating and testing unintended memorization in neural networks. In 28th USENIX Security Symposium, 2019a.
Nicholas Carlini, Chang Liu, Úlfar Erlingsson, Jernej Kos, and Dawn Song. The secret sharer: Evaluating and testing unintended memorization in neural networks. In USENIX Security Symposium, 2019b.
Nicholas Carlini, Matthew Jagielski, Chiyuan Zhang, Nicolas Papernot, Andreas Terzis, and Florian Tramer. The privacy onion effect: Memorization is relative. Advances in Neural Information Processing Systems, 01113233-337777 2022.
Xiangyi Chen, Steven Z Wu, and Mingyi Hong. Understanding gradient clipping in private sgd: geometric perspective. Advances in Neural Information Processing Systems, 2020.
Soham Dc, Loonard Berrada, Jamic Hayes, Samuel Smith, and Borja Balle. Unlocking high-accuracy differentially private image classification through scale. arXiv preprini arXiv:2204.1365 2022.
Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and Trends2 in Theoretical Computer Science, 2014.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Proceedings of the 3rd Conference on Theory of Cryptography, TCC '06, pp. 265 284, Berlin, Heidelberg, 2006. Springer.
Vitaly Feldman and Chiyuan Zhang. What neural networks memorize and why: Discovering the long tail via influence estimation. In Advances in Neural Information Processing Systems 33, 2020.
12

---

Published in Transactions on Machine Learning Research (09/2023)
Vitaly Feldman and Tijana Zrnic. Individual privacy accounting via a Renyi filter. In Advances in Neural Information Processing Systems, 2021.
Vitaly Feldman, Audra McMillan, and Kunal Talwar. Stronger privacy amplification by shuffling for rényi and approximate differential privacy. In Annual ACM-SIAM Symposium Discrete Algorithms,, 2023.
Antonio Ginart, Melody Guan, Gregory Valiant, and James Zon. Making ai forget you: Data deletion in machine learning. In Advances in Neural Information Processing Systems, 2019.
Aditya Golatkar, Alessandro Achille, Yu-Xiang Wang, Aaron Roth, Michael Kearns, and Stefano Soatto. Mixed differential privacy in computer vision. In Proceedings of IEEE Computer Society Conference on Computer Vision and Poltern Recognition, 2022.
Sivakanth Gopi, Yin Tat Lee, and Lukas Wutschitz. Numerical composition of differential privacy. In Advances in Neural Information Processing Systems, 2021.
Victor Petrén Bach Hansen, Atula Tejaswi Neerkaje, Ramit Sawhney, Lucie Flek, and Anders Søgaard. The impact of differential privacy on group disparity mitigation. arXie preprint arXiv:2203.08 02745, 2022.
Tatsunori Hashimoto, Megha Srivastava, Hongseok Namkoong, and Percy Liang, Fairness without demo- graphics in repeated loss minimization. In International Conference on Machine Learning, pp. 1929-1938. PMLR, 2018.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of IEEE Computer Society Conference Computer Vision and Pattern Recognition, 2016.
Matthew Jagielski, Jonathan Ullman, and Alina Oprea. Auditing differentially private machine learning: How private is private sgd? In Advances in Neurol Information Processing Systems, 2020.
Ziheng Jiang, Chiyuan Zhang, Kunal Talwar, and Michael C Mozer. Characterizing structural regularities of labeled data in overparameterized models. In International Conference on Machine Learning, pp. 5034-5044. PMLR, 2021.
Zach Jorgensen, Ting Yu, and Graham Cormode. Conservative or liberal? personalized differential privacy. In International Conference on Data Engineering (ICDE), 2015.
Daniel Kifer, Adam Smith, and Abhradeep Thakurta. Private convex empirical risk minimization and high-dimensional regression. In Proceedings of the 25th Annual Conference on Learning Theory, COLT '12 pp. 25.1-25.40, 2012.
Antti Koskela, Marlon Tobaben, and Antti Honkela. Individual privacy accounting with gaussian differential privacy. XrXiv preprinl arXio:2209. 15596, 2022.
Antti Koskela, Mikko A Heikkilä, and Antti Honkela. Numerical accounting in the shuflle model of differential privacy. Tronsactions Machine Learning Research, 2023.
Alex Krizhevsky. Learning multiple layers features from tiny images, 2009.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient- based learning applied to document recognition. Proceedings of the IEEE, 1998.
Mathias Lécuyer. Practical privacy filters and odometers with rényi differential privacy and applications to differentially private deep learning. arXiv preprint arXiv:2103.0133 2021.
Xuechen Li, Florian Tramèr, Percy Liang, and Tatsunori Hashimoto. Large language models can be strong differentially private learners. In Proceedings of the 10th International Conference on Learning Representations, 2022.
Katrina Ligett, Seth Neel, Aaron Roth, Bo Waggoner, and Steven Z Wu. Accuracy first: privacy level for accuracy constrained erm. Advances in Neural Information Processing Systems, 2017.
Selecting differential
13

---

Published in Transactions on Machine Learning Research (09/2023)
Andrew Lowy, Devansh Gupta, and Meisam Razaviyayn. Stochastic differentially private and fair learning. arXiv preprint arXiv:2210. 08781,, 2022.
Harsh Mehta, Walid Krichene, Abhradeep Thakurta, Alexey Kurakin, and Ashok Cutkosky. Differentially private image classification from features. arXiv preprint 2r 2022a.
Harsh Mehta, Abhradeep Thakurta, Alexey Kurakin, and Ashok Cutkosky. Large scale transfer learning for differentially private image classification. arXiv preprint arXiv:, 2022b.
Sebastian Meiser. Approximate and probabilistic differential privacy definitions. Cryptology ePrint Archive, 2018.
Ilya Mironov. Rényi differential privacy, In Proceedings of the 30th IEEE Computer Security Foundations Symposimm, 2017.
Nla Mironov, Kunal Talwar, and Li Zhang. Rényi differential privacy of the sampled gaussian mechanism. arXiv preprint 19c8:190000000 2019.
Christopher Mühl and Franziska Bocnisch. Personalized PATE:
Differential privacy for machine learning with individual privacy guarantees. arXic preprint 2XXi:2202.10511 2022.
Milad Nasr, Shuang Song, Abhradeep Thakurta, Nicolas Papernot, and Nicholas Carlini. Adversary in- stantiation: Lower bounds for differentially private machine learning. arXiv preprint arXiv:2101.04558, 2021a.
Milad Nasr, Shuang Songi, Abhradeep Thakurta, Nicolas Papemoti, and Nicholas Carlin. Adversary instantiation: Lower bounds for differentially private machine learning. In 2021 IEEE Symposium on Security and Privacy (SP), 2021b.
Frederik Noe, Rasmus Herskind, and Anders Søgaard. Exploring the unfairness of dp-sgd across settings. arXiv preprint arXiv:2202. 12058, 2022.
Nicolas Papernot, Martin Abadi, Ulfar Erlingsson, lan Goodfellow, and Kunal Talwar, Semi-supervised knowledge transfer for deep learning from private training data. In Proceedings of the 5th International Conference on Learning Representations, 2017.
Nicolas Papernot, Abhradeep Thakurta, Shuang Song, Steve Chien, and Ulfar Erlingsson. Tempered sigmoid activations for deep learning with differential privacy. arXiv preprint arXiw:2007.14100 2020.
Md Atiqur Rahman, Tanzila Rahman, Robert Laganiere, Noman Mohammed, and Yang Wang. Membership inference attack against differentially private deep learning model. Transactions on Data Privacy, 2018.
Rachel Redberg and Yu-Xiang Wang. Privately publishable per-instance privacy. In Advances in Neural Information Processing Systems, 2021.
Alexandre Sablayrolles, Matthijs Douze, Yann Ollivier, Cordelia Schmid, and Hervé Jégou. White-box vs black-box: Bayes optimal strategies for membership inference. International Conference on Machine Leurning, 2019.
Shuang Song, Kamalika Chaudhuri, and Anand D Sarwate. Stochastic gradient descent with differentially private updates. In Proceedings of IEEE Global Conference on Signal and Information Processing, 2013.
Shuang Song, Thomas Steinke, Om Thakkar, and Abhradeep Thakurta. Evading the curse of dimensionality in unconstrained private glms. In International Conference on Artificial Intelligence and Statistics, 2021.
Vinith M Suriyakumar, Nicolas Papernot, Anna Goldenberg, and Marzych Ghassemi. Chasing your long tails: Differentially privale prediction in health care settings. In Proceedings of ACM Conference on Fairness, Accountability, and Transparency, 2021.
Shaowei Wang. Privacy amplification via shuffling: Unified, simplified, and tightened. ar preprint arXiv:2304.05001, 2023.
14

---

Published in Transactions on Machine Learning Research (09/2023)
Yu-Xiang Wang. Per-instance differential privacy. The Journal of Privacy and Confidentialityy 2019.
Yu-Xiang Wang, Borja Balle, and Shiva Prasad Kasiviswanathan. Subsampled rényi differential privacy and analytical moments accountant. In Proceedings of the 22nd International Conference Artificial Intelligence and Statistics, 2019.
Justin Whitehouse; Aaditya Ramdas, Ryan Rogers, and Zhiwei Steven Wu. Fully adaptive composition differential privacy. arXiv preprint arXiv:2203.055 05488, 2022.
Ashkan Yousefpour, Igor Shilov, Alexandre Sablayrolles, Davide Testuggine, Karthik Prasad, Mani Malek, John Nguyen, Sayan Ghosh, Akash Bharadwaj, Jessica Zhao, Graham Cormode, and Tlya Mironov. Opacus: User-friendly differential privacy library PyTorch. arXiv prepriul arXiv:2109. 12298, 2021a.
Ashkan Youselpour, Igor Shilov, Alexandre Sablayrolles, Davide Testuggine, Karthik Prasad, Mani Malek, John Nguyen, Sayan Gosh, Akash Bharadwaj, Jessica Zhao, Graham Cormode, and Ilya Mironov. Opacus: User-friendly differential privacy library in PyTorch. arXiv preprint arXiv:2109.1120 12298, 2021b.
Da Yu, Huishuai Zhang, Wei Chen, Jian Yin, and Tie- Yan Liu. Large scale private learning via low-rank reparametrization. In International Conference Machine Learning, 2021.
Da Yu, Saurabh Naik, Arturs Backurs, Sivakanth Gopi, Huseyin Inan, Gautam Kamath, Janardhan Kulkarni, Yin Tat Lee, Andre Manoel, Lukas Wutschitz, Sergey Yekhanin, and Huishuai Zhang, Differentially private fine-tuning of language models. In Proceedings of the 10th International Conference on Learning Representations, 2022.
Zhifei Zhang, Yang Song, and Hairong Qi. Age progressionfregresson by conditional adversarial autoencoder. In Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2017.
Yuqing Zhu, Xiang Yu, Manmohan Chandraker, and Yu-Xiang Wang. Private-knn: Practical differential privacy for computer vision. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 11854 1044-11862 11862, 2020.
15

---

Published in Transactions on Machine Learning Research (09/2023)
A Proof of Theorem 3.1
Theorem 3.1. Let (01.....00-1 be the observed models step Suppose we run Algorithm with K and without rounding, then Algorithm satisfies (oa + log[1/8] coutput-specpppp individual DP for the ish ezample at A (f1.....,e B 1. where 0a is the accumulated RDP at order and O2 is the range of A
a-l
Here we give the proof of Theorem 3.1 Let (A......AAAAA))) be a sequence of randomized algorithms and (01....,01-) be some fixed outcomes, we define
A 0c.,,,
Noting that the individual RDP parameters of each individual mechanism in (0 02-1, DD) are constants. Further let
( - (A()) A.A .D)
be the adaptive composition. In Lemma A.1 we show RDP bound on A gives an output-specifie DP bound (t)), We comment that the individual RDP parameters of each individual mechanism in A are random variables. The composition of random privacy parameters requires additional care because the standard composition theorem requires the privacy parameters to be constants (Feldman & Zrnic 2021 Whitehouse et al. 2022
Lécuyer 2021
Lemma A.1. Let A (01,... .......,0-1111 O0 is the domain of (D) and (D). If ()) satisfies Oa RDP at order a, then (D) satisfies 00-oooppl--spene differential privacy
0--1, O.) O!!) where 01,...,0,-
01-1 some arbilvary fixed oulcomes and
(o, + log(1/8) a-1
Proof. For given outcome 010) =001, 02.00,..,00011.1 A, we have IP (D) O(0]]
Ar- P ( (D) = (((-11) P (A), D) 0. (t-1) (ID = gl(-11].
(6)
=P ( = 0
= 0,),
(7)
by the product rule of conditional probability. Apply the product rule recurrently on P ((((-))(D)) = g(t-1)),
we have P (A(0(D) p(t)]
P ( (D) g(c-2)] P. [P[A-- 1 (0....... .0....,,.,............. D) -) 0,.,, 0.]
(8)
(D) PP (A2
(0,, ID) = 02)...P :...0........................... [AA,(()....,,0.111
= -O],
(9)
= P A (01, 0 0--1, = 8(0]
(10)
In words, (t) and A are identical in A. Therefore, A satisfics (E, 8) at any S c A if A4()) satisfies (e, ().P) Converting the RDP bound on (TD) into a (s, O)D bound with Lemma A.2 then completes the proof.
Lemma A.2 (Conversion from RDP to (e, 6)DD Mironov (017)) ). If A satisfies (DDP) then A satisfies (p log(1/8) a 8)-DP for all 0 < 8 < 1.
16

---

Published in Transactions on Machine Learning Research (09/2023)
Algorithm 3 Differentially Private SGD with Individual Clipping
Input: Clipping threshold C, noise variance o², sampling probability p, number of steps T.
for f t= T - do
Call Algorithm 2 for individual privacy accounting and get estimates of individual gradient norms 1 1=1'
Sample minibatch of gradients {g with probability p where I is the sampled indices.
Clip gradients g g(,,) = clipíg())) 2(6)).
Updale model 0. = 0t-1 - ((gg) +2), where 2 ~ ~N(,0
end for
B Individual Privacy Accounting with Individual Clipping
We set K > 1 in Algorithm 2 to reduce the computational cost of individual privacy accounting (see Section for details). In this case, the computed privacy costs are estimates of the exact ones. In Section 3.3 we demonstrate the estimates are accurate. In this section, we give another design choice that slightly modifies the original DP-SGD to give exact privacy accounting. More specifically, we clip the individual gradients with the estimates of gradient norms } from Algorithm 2
3
We refer this design choice as individual clipping. We give the implementation in Algorithm g and highlight the changes in bold font. We run experiments with
individual clipping and report the results in Appendix that in Section
B.1 and
B.2
The experimental setup is the same
4
B.1 Individual Clipping Does Not Affect Accuracy
Algorithm uses individual clipping thresholds to ensure the computed privacy parameters are strict privacy guarantocs. If the clipping thresholds are close the actual gradient norms, then the clipped results are close to those of using a single maximum clipping threshold. However, the estimations of gradient norms are not accurate, individual thresholds would clip more signal than using single maximum threshold.
Table 3: Comparison between the test accuracy of using individual clipping thresholds and that of using a single maximun clipping threshold. The maximum e is 7.8 for CIFAR- 10 and 2.4 for MNIST.
CIFAR-10
MNIST
Individual
74.0 (#0011)
97.17 (=0.12)
Maximum
74.1 (+0.24)
97.26 (=0.11
We compare the accuracy of two different clipping methods in Table g The individual clipping thresholds are updated once per epoch. We repeal the experiment four times with different random seeds. The results suggest that using individual clipping thresholds in Algorithm has negligible effect on accuracy.
B.2 Individual Clipping Does Not Change The Observations
Here we show running DP-SGD with individual clipping does not change our observations in Section and
Privacy parameters have strong correlation with individual training loss. In Figure 7 we show privacy parameters computed with individual clipping are still positively correlated with training losses. The Pearson correlation coefficient between privacy parameters and log losses is larger than 0.9 for all datasets.
Groups are simultancously underserved in both accuracy and privacy We show our observation in Section i.e., low-accuracy groups have worse privacy parameters, still holds in Figure g We also make direct comparison with privacy parameters computed without individual clipping, We find that privacy parameters computed with individual clipping are close to those computed without individual clipping. We also find that the order of groups, sorted by the average e, is exactly the same for both cases.
17

---

Published in Transactions on Machine Learning Research (022)
CIFAR-10 (Pearson's
MNIST (Pearson's 0.92)
UTKFace Gender (Pearson's 0.93)
UTKFace (Pearson's 0.94)
4,5
3.5
1.5
1.0
255
2.0
3-
15
2-
sslayle)
7
y 2.3
1.0
y
y-
0.5
18"1
Figure 7: Privacy parameters and final training losses. The experiments are run with individual clipping
(Algorithm 3)
The Pearson correlation coefficient is computed between privacy parameters and log losses.
180
(W U.s.t...C..
7.5
100
99-
90-
AocuraI (n 5g
Aocuracy ftr 5g
110
5.0
94
-0.4
98
Privacy Parsmeter (Wiir LC)
455
Privacy Parsmeter (Wit (C)
Auto Truck frep Hone Ar: Deer Dog Bird De:
Subgroup Name
Subgroup Name
UTK seendee-
UTK JTK/ace-Age
103.0
Whoutl.CC.
07.5
90
accurccy fio
87.5
85.0
2.00
82.5
Perameter (WimmatiC)
70
Perameter (Wimaut
Parameter (With
Porameter (With
Indian
Blace
White
Asian
Asian
White
Indias
Black
Subgroup
Subgroup Name
Figure 8: Test accuracy and privacy parameters computed with/withon individual clipping (I.C.). Groups with worse test accuracy also have worse privacy in general.
18

---

Published in Transactions on Machine Learning Research (09/2023)
CMM.1M, test #0.7 4=7.5, min 6=1.6
C=0.3M, test acc. max 4=7.5, 5, min 4=1.0
40000
15000
36000
28000
24500
24000
20000
17500
16000
14000
8000
7000
4000
3520
0.0
0.8
16
2.4
3.2
4.0
4.8
5.6
6.4
7.2
8.0
0.0
0.8
1.6
2.4
3.2
4.0
4.8
5.6
6.4
7.2
8.0
C=0.5M. test acc.
c.7.5. min 6=0.9
C=1 test mcc.m63.. max e min c=0.5
30000
10000
27000
9000
21000
7000
18000
6000
Coom
15000
5000
12000
4000
2000
3000
1000
0.0
0.8
16
2.4
3.2
4.0
4.8
5.6
6.4
7.2
8.0
0.0
0.8
1.6
2.4
32
4.0
4.8
5.6
6.4
7.2
8.0
Figure 9: Distributions of individual privacy parameters on CIFAR-10 with different maximum clipping thresholds. The dashed line indicates the average of privacy parameters.
Clip-8.1
Clip- Modian
Training Acc. (Mac Min. 79)
Training Aor. (Max -in
(Hler Min
(Mox
7.
Accurais 01:9
10
7.0
7.0
Auarage
665
6.0
12
60
40
Privecy Parameter (Max-Rin Minu--in-1.330
40
Privacy Parameter z (Mar-Vin-3
Adto Truce Ar. Harse Bidd Deer Cat
Ship Auto. Truck Air.
Cat
Subgruu hä me
Subgroup Name
Clip=0.5 0.5 Median
1.ip11.5 Median
Training
546)
Training
Min =36
75
Acc. (Max, Min -3.
525
80
5.00
accurscy fi
70
425
50-
55
Privacy Parameter (Max Min-).i-...
Wino
Stip Auto, Truck Frog Horse Ar. Dog Bird Dear Cat
Ship Aulo. Truck Ar. trog Dog Horse Ca: Ooor Bird Sibgtoup
Subgruu
Figure 10: Accuracy and average of different groups CIFAR-10 with different maximum clipping thresholds.
19

---

Published in Transactions on Machine Learning Research (09/2023)
C
The Influence of Different Maximum Clipping Thresholds
The value of the maximum clipping threshold C' would affect individual privacy parameters. large value of C' would increase the stratification in gradient norms but also increase the noise variance for a fixed privacy budget. A small value of C' would suppress the stratification but also increase the gradient bias. Here we run experiments with different values of C' on CIFAR-10. We use small ResNet20 model in He et al.] (2016), which only has ~0.2M parameters, to reduce the computation cost. All batch normalization layers are replaced with group normalization layers. Let M be the median of gradient norms at initialization, we choose C' from the list [0.1M, 0.3.M, 0.5M, 1.5M).
The histograms of individual privacy parameters are in Figure 9 In terms of accuracy, using clipping thresholds near the median gives better test accuracy. In terms of privacy, using smaller clipping thresholds increases privacy parameters in general. The number of datapoints that reaches the worst privacy decreases with the value of C. When C = 0.1M, nearly 70% datapoints reach the worst privacy parameter while only ~2% datapoints reach the worst parameter when = 1.5M.
The correlation between accuracy and privacy is in Figure 10
The disparity in average is clear for all choices of C. Another important observation is that when decreasing C, the privacy parameters of underserved groups increase quicker than other groups. When changing C' = 1.5. to 0.5.M, the average e of 'Cat' increases from 4.8 to 7.4, almost reaching the worst-case bound. In comparison, the increment in & of the 'Ship' class is only 1.3 (from 4.2 to 5.5).
D Privacy Parameters Reflect Empirical Privacy Risks in Non-Private Learning
We run membership inference (MI) attacks to verify whether examples with larger privacy parameters have higher privacy risks in practice. We use simple loss-threshold attack that predicts an example is member if its loss value is smaller than a prespecified threshold (Sablayrolles et al. 2019). Previous works show that even large privacy paramcters are sufficient to defend against such attacks (Carlini et al. 2019b Yu et al., 2021). In order to better observe the difference in privacy risks, we also include models trained without differential privacy as target models. For each data subgroup, we use its whole test set and a random subset of the training set so the numbers of training and test loss values are balanced. We further split the data into two subsets evenly to find the optimal threshold on one and report. the success rate on another.
CIFAR-10
UTKFace-Gende Gender
3,00
70,0
Average Epsilon
Average Epsilon
Success Rate (without DP)
90
Success Rate (without DP)
67.5
Success Rate (with DF)
Success Rate (with DP)
2.50
65.0
29.7.
80
All Success hate
2.25
62.5
Average
Average
21.3 20.9
2.00
60.0
57.8
$7.8
ss.
1.75
57.1
-77.5
665
61.4
6
1.50-
55.0
52.0.52.4 $1. 514.5177.55
52.1 52.1,522,,2222 52.8
55
50.7
51.8
50.4
$1.2
52.5
ship Auto. Truck Frog Horze Air. Dég Dear Bird Subgroup Name
Cat
1.00
Indian
Black
White
Asian
50.0
Subgroup Name
Figure 11: Average e and membership inference success rates on different subgroups.
The results on CIFAR-10 and UTKFaco-Gondor are in Figure 11 The subgroups are sorted based on their average e. When the models are trained with DP, all attack success rates are close to random guessing (50%). Although the attack we use can not show the disparity in this case, we note that there are more powerful attacks whose success rates are closer to the lower bound that DP offers (Nasr et al. 2021b). On the other hand, the difference in privacy risks is clear when models are trained without DP. On CIFAR-10, the MI success rate is 79.7% on the Cat class (which has the worst average when trained with DP) while is
20

---

Published in Transactions on Machine Learning Research (09/2023)
only 61.4% on the Ship class (which has the best average c). These results suggest that the values reffect empirical privacy risks which could vary significantly in different subgroups.
E
The Correlation Between Privacy Parameters and Loss Holds under Different Clipping Thresholds
Section 1.2 we show that there a positive logarithmic correlation between privacy parameters and training loss. In this section, we run experiments on CIFAR-10 with C and C = 10 to show the correlation still holds under different clipping thresholds. The experiment setup, except the value of C, is the same Section 4.2 The results are in Figure 12 Although changing the clipping threshold changes the slope and intercept, the logarithmic correlation is still strong. The Pearson correlation coelficients are 0.89 and 0.9 for
C = and C = 10, respectively.
CIFAR-10, C= (Pearson's 0.89)
CIFAR-10, C 10 (Pearson's 0.90)
8
8
7-
7
6
5
4
3-
2-
y= 0.52log(x) 7.18
y= 0.85log(x) 6.45
1
7.9
y 8.0
10 10 5 10-4
10
10
10
10a
0
10-6
10-5
10
10 10
10
10c
Loss
Loss
Figure 12: Privacy parameters and final training losses. Each point shows the final training loss and privacy parameter one example. Pcarson's r is computed between privacy parameters and log loss values.
F Individual Privacy Accounting in More Settings
In this section, we study individual privacy accounting in more experimental settings. The dataset in this section CIFAR-10. We first study the influence of loss function. We replace the cross-entropy loss with the multi-class hinge loss. Other settings are the same those in Section | The results are in Figure [3 We also study the influence of model architectures. We replace WRN16-4 with the two-layer convolutional neural networks in Papernot et al. (2020) and still use the cross-entropy loss. The learning rate is set as 1.0 and
other settings are the same as those in Section 4 The results are in Figure 14
Our main observations in the main text still hold the new seltings. The Pearson's correlation coelficients between the estimated and actual privacy parameters are larger than 0.99 in both cases. Examples that are underserved by the model also suffer from higher privacy costs. Although the main observations do not change, observe some differences in the privacy parameters. When using the two-layer neural network instead of WRN16-4, the privacy parameters become larger. For instance, the average e of Cat increases from 7.3 to 7.7.
21

---

Published in Transactions on Machine Learning Research (022)
CIFAR-10: y 1
Test CIFAR-10
Estimated e
80
6.0
Average
Accuracy
4
X
5.5
70-
y 7.9
2
5.0
Pearson's - 0.999
Avg. j - 0.06 0.06
60-
Max c) 0.37
0
2
6
Privacy Parameter
Actual
Ship Auto. Thack frog Home Air. Dewr Bind
Dog.
Subgroup Name
(a) Estimated & versus exact 8.
(b) Accuracy and group e.
Figure 13: The results using multi-class hinge loss instead cross-entropy loss.
10::R-10: y 1
CIFAR-10
8.0
8
Estimated E
80-
Average
4-
= X
Accuracy
20
5,5
y 7.9
2
Pearson's == 0.999
6.0
Avg. 1 a 0.05 0.05
Max i c 0.28
50-
0
2
4
6
8
Privacy Parameter
Actual
Auto. Ship
Tack Horse Air. Dog Deer Bid Cal
Subgroup Name
(a) Estimated & versus exact
(b) Accuracy and group-wise E.
Figure 14: The results of using the small convolutional ncural network in Papernot et al.
2020
22


Reviews:
[{"review_id": "4GUbL89hNa", "reviewer": "Reviewer_9Tbq", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "*Strengths*\n\nPrivately learning deep learning models is an active field of research and DP-SGD is widely used. This paper aims at advancing the understanding of privacy guarantees and its implications for specific users, in terms of exposure risk and accuracy which I think is of interest to the community. \n\n*Weaknesses* \n\n- The paper makes several mistakes on privacy accounting that can lead to private information being leaked (see requested changes). \n- The suggested “individual” privacy definition is misleading since individual budgets depend on all other data points on the dataset. Specifically, the budget of sample $x$ on the dataset $[y_1, …, y_n, x]$ can be drastically different from its budget if the model is learned from the dataset $[z_1, …, z_n, x]$. \n- I think there is an inconsistency between algorithm 1 and the implementation used by the authors regarding computation of per-example gradients norms. Algorithm 1 computes the gradients for the clipping step so it is unclear to me the section spent on avoiding computation of gradients norms for privacy accounting in section 3.1. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies DP-SGD and introduces a “per-example privacy guarantee”, a definition achieved by specific runs of the algorithm on each sample for a specific datasets. The paper first claims that a large proportion of examples benefit from a stronger privacy guarantee. Second, that per-class accuracy is correlated with the level of privacy, i.e., small privacy budget $\\epsilon$ on a given class correlates with higher test accuracy for that class. ", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Most DP-SGD implementations use shuffle data, not poisson sampling. However, I understand that most of the literature uses this simplification because privacy accounting is simpler under this assumption. I would encourage the authors to include a note on this for transparency. \n\n\n2. The privacy definition of being “individual” is misleading since it depends on the dataset. Assume the algorithm is learning a binary classification model on a dataset $D_1=[(x_1, y_1), …, (x_n, y_n)]$ where  $ x_1\\approx x_2\\approx...\\approx x_n $ , and $y_i=0$. After a few training rounds it is likely that the gradient at $x_1$ will be small since it already “learned” the information from $x_1$ through other samples, and will have a small budget. \nHowever, if we had a dataset $D_2=[(x_1, y_1), (w_2,z_2), …, (w_n, z_n)]$,  where $w_i = -x_i$, and $z_2=...=z_n=1$, in this case the gradient at $(x_1,y_1)$ might be large since it is learning new information from what it learns from other data points, and consequently its budget might be much larger. \n\n\n3. Theorem 3.2 is incorrect when assuming $f$ is only post-processing since $Z_i$ depends on the non-private norm at iteration $t$ and this norm itself depends on the whole dataset. \n\n4. Revealing privacy budgets reveals information to user $i$ about other users. This step has to be clarified.\n\n5. DP-SGD computes per-example gradient norms for clipping at each iteration (line \"`clip gradient norms g^(I_i)...`\"  in algorithm 1). Efficiency of this step is a large area of research and recently `ghost` clipping techniques try to devise efficient ways of computing these norms. Why would norms have to be recomputed in algorithm 2? Maybe something needs clarification or sections 3.1. and 3.2. are redundant since norms can be reused from this step. \n\n6. Wouldn’t clipping to Z(i), as suggested in section 3.2 mean no clipping at all?\n\n7. In the experiments the authors define “C as the median of gradient norms at initialization,”. This step does not respect privacy unless the median is privatized. \n\n8. “Intuitively, an example would have a high loss after training if its gradient norms across training are large” I don’t see how this is intuitive. Large steps could result precisely in an optimal point with minimum loss.  Additionally, the relation of the loss value with the clipping parameter is not discussed. Large privacy budgets being correlated with high loss values could be due to over-clipping. ", "broader_impact_concerns": "The paper makes claims on the privacy risk of users. I don’t think there are ethical concerns, but rather incorrect claims and/or misleading interpretations of results that could lead to leaking private information. \n", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "wfMSpggA0z", "reviewer": "Reviewer_8AUH", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The new individual DP notion is interesting in the sense that it can characterize the privacy guarantee of different training samples in DPSGD\n2. The observation that underserved training samples also have high privacy cost is interesting.\n\nWeaknesses:\n1. Calculating individual privacy introduces quite significant computation cost in the context of DPSGD.\n2. The theoretical contribution is limited since the privacy accounting is straightforwardly using existing techniques.\n3. The individual privacy variation could vary depends on datasets, training loss, model architecture, and so on. But the key observation is drawn only from using two datasets. This leaves a question whether the same phenomenon holds if other factors are changed.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a new DP notion for each individual examples in the dataset. The notion can be used to characterize privacy guarantee for each training sample in DPSGD. For the new notion of DP (which is a generalization of traditional (epsilon, delta)-DP), the authors provided ways to efficiently estimated the privacy cost. One interesting and intuitive observation is that the samples that served poorly by the model also suffer from higher privacy cost. ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Have the authors explored how other factors affect the variance of individual privacy cost (e.g., model architecture and loss function as mentioned earlier)? It might be good to try verify the observations in more settings. E.g., how much does model architecture matters?", "broader_impact_concerns": "No concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "LmeDQXPZoe", "reviewer": "Reviewer_EYWv", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nTheorem 3.2 is a very important property for working with these quantities, and I'm glad the authors have addressed this.\n\nThe paper offers an analysis of disparate impact in DP that considers both utility and privacy.\n\nThe two speedups are nice. It's surprising to me that the privacy accounting step is so slow, but rounding is a nice way to get around that.\n\nWeaknesses:\nThe direction of privacy filters is quite related to the accounting technique described here, although differences are discussed appropriately in the paper.\n\nNot much fine-grained can be done with these individual epsilons. Even reporting them to the user can result in something nonprivate, if this enables the user to take action in response to learning this. For example, if this prompts a user to issue an unlearning request, this user's deletion can change other users' risks, leaking that the other user had a high epsilon [R1]. Based on the results, user demographics can be correlated with high epsilons, which may lead to disproportionate deletion requests, which can amplify the bias [R2].\n\nRounding can lead to an underestimation of RDP, if the rounded clipping norm is too small, especially if r is relatively large relative to the true gradient norm.\n\n[R1] - https://arxiv.org/abs/2206.10469\n[R2] - https://arxiv.org/abs/1806.08010\n\n\nReview questions:\nAre the claims made in the submission supported by accurate, convincing and clear evidence? I'd say so. All the trends mentioned seem to be quite robust, and the theorems appear correct.\n\nWould at least some individuals in TMLR's audience be interested in knowing the findings of this paper? I think this is of interest to some private ML folks.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper measures the \"individual privacy parameter\" obtained for each example from DP-SGD. Intuitively, an example whose gradient norm is not at the clipping threshold will have an individual epsilon value which is smaller than the worst-case epsilon that assumes every example contributes a full-norm gradient. For this setting, the paper proposes an algorithm for computing these individual epsilons, builds a more efficient approximate algorithm, and offers some takeaways on the usefulness of these individual epsilons.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I would like to see a discussion of the dangers of releasing epsilon to users in the context of a broader system, perhaps where data deletions are an available recourse. (strengthen)\n\nIt might be interesting to understand the relationship with individual privacy loss as computed by privacy attacks and this measurement approach to understand how correlated they are. The approach here should be a valid upper bound. (strengthen)", "broader_impact_concerns": "none", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes an example specific notion of epsilon, delta DP, where the epsilon is defined for a an example, outcome pair. The paper claims that a large proportion of examples in a training during DP-SGD benefits from this more nuanced notion. The reviewers found this notion interesting and useful. There were some clarifications/corrections requested by the reviewers which were answered by the authors. Reviewers had the general concern that the individual privacy guarantees usefulness is limited due to the risk of exposure however they unanimously leaned towards acceptance.
Decision: Accept (poster)