Individual Privacy Accounting for Differentially Private Stochastic Gradient Descent
Authors: Da Yu
Gautam Kamath
Janardhan Kulkarni
Tie-Yan Liu
Jian Yin
Huishuai Zhang
Venue: Submitted to ICLR 2023 (2023)
Keywords: individual privacy for DP-SGD
fairness in privacy

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 an efficient algorithm to compute privacy guarantees for individual examples when releasing models trained by DP-SGD. We use our algorithm to investigate individual privacy parameters 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 are simultaneously underserved in terms of privacy guarantee. For example, on CIFAR-10, the average $\varepsilon$ of the class with the lowest test accuracy is 43.6% higher than that of the class with the highest accuracy. We also run membership inference attacks to show this reflects disparate empirical privacy risks.


Under review as a conference paper at ICLR 2023
INDIVIDUAL PRIVACY ACCOUNTING FOR DIFFEREN- TIALLY PRIVATE STOCHASTIC GRADIENT DESCENT
Anonymous authors Paper under double-blind review
ABSTRACT
Differentially private stochastic gradient descent (DP-SGD) is the workhorse al- gorithm for recent advances private deep learning. It provides a single privacy guarantee to all datapoints in the dataset. We propose efficient algorithm compute privacy guarantees for individual examples when releasing models trained by DP-SGD. We use algorithm investigate individual privacy parameters 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 terms of model utility are simultaneously underserved in terms of privacy guarantee. For example, on CIFAR-10, 10, the average of the class with the lowest test accuracy is 43.6% higher than that of the class with the highest accuracy.
INTRODUCTION
Differential privacy is strong notion of data privacy, enabling rich forms of privacy-preserving data analysis (Dwork & Roth 2014). Informally speaking, it quantitatively bounds the maximum influence of any datapoint using a privacy parameter E, where small value of corresponds to stronger privacy guarantees. Training deep models with differential privacy is an active research area (Papernot al. 2017 Bu al. 2020 Yu et al. 2022 Anil al.. 2021| Li al. 2022 Golatkar et al.) Mehta et al. 2022 De et al. 2022 Bu et al. 2022). Models trained with differential privacy
not only provide theoretical privacy guarantee their data but also are more robust against empirical
attacks (Bernau et al. 2019 Carlini et al. 2019 Jagielski et al. 2020
Nasr et al. 2021).
Differentially private stochastic gradient descent (DP-SGD) is the de-facto choice for differentially private deep learning (Song et al. [2013] [Bassily et al. 2014 Abadi et al. 20166). DP-SGD first clips individual gradients and then adds Gaussian noise the average of clipped gradients. Standard privacy accounting takes worst-case approach, and provides all examples with the same privacy parameter E. However, from the perspective of machine learning, different examples can have very different impacts on learning algorithm (Koh & Liang 2017: Feldman & Zhang 2020). For example, consider support vector machines: removing non-support vector has no effect on the resulting model, and hence that example would have perfect privacy.
In this paper, we give an efficient algorithm to accurately estimate individual privacy parameters of models trained by DP-SGD. Our privacy guarantee adapts to the training trajectory of one execution of DP-SGD to provide precise characterization of privacy cost (see Section 2. for more details). Inspecting individual privacy parameters allows us to better understand example-wise impacts. It turns out that, for common benchmarks, many examples experience much stronger privacy guarantee than the worst-case bound. To illustrate this, plot the individual privacy parameters of MNIST (LeCun et al. 1998), CIFAR-10 (Krizhevsky) 22009). and UTKFace (Zhang et al. (017) in Figure I Experimental details, as well more results, can be found in Section 4 and 5 The disparity in
individual privacy guarantees naturally arises when running DG-SGD. To the best of our knowledge, investigation is the first explicitly reveal such disparity.
We propose two techniques to make individual privacy accounting viable for DP-SGD. First, we maintain estimates of the gradient norms for all examples the individual privacy costs can be computed accurately at every update. Second, we round the gradient norms with a small precision r control the number of different privacy costs, which need be computed numerically. We explain

---

Under review as a conference paper at ICLR 2023
CPARI-1,, test scc -74.2 mas 6-7.8, mineel
VANST seat scc 2,21, max 12244.mm ee0.3
22028
1200
20011
18010
18913
4010
3240
6012
2933
UUTeFaco Gander ac..0c6--2...... min 6w07
UTKFfaco Age. aoc -00.4 6-07
4028
4360
1235
1200
2403
322
3240
431
400
65
00
25
25
21
25
25
33
35
45
45
45
05
09
15
23
25
29
33
33
Figure I: Individual privacy parameters of models trained by DP-SGD. The value is x 10 The dashed lines indicate 10,, 30%, and 50% of datapoints. The black solid line shows the privacy parameter of the original analysis.
why these two techniques are necessary in Section 2 More details of the proposed algorithm, as well as methods to release individual privacy parameters, are in Section
We further demonstrate strong correlation between the privacy parameter of an example and its final training loss. We find that examples with higher training loss also have higher privacy parameters in general. This suggests that the same examples suffer simultancous unfairness in terms of worse privacy and worse utility. 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 Bagdasaryan et al. (2019); Suriyakumar al.) (20TT); [Haneen et al. (2022); Noe et al. 2022), we are the first to show that the privacy guarantee and utility are negatively impacted concurrently. This comparison to prior work in the differentially private setting which took worst-case perspective for privacy accounting, resulting in uniform privacy guarantee for all training examples. For instance, when running gender classification on UTKFace, the average s of the race with the lowest test accuracy is 25% higher than that of the race with the highest accuracy. We also study the disparity in privacy when models are trained without differential privacy, which may be of independent interest the community. We use the success rates of membership inference attacks to measure privacy in this case and show groups with worse accuracy suffer from higher privacy risks.
1.1 RELATED WORK
Several works have explored example-wise privacy guarantees in differentially private learning. Jorgensen et al. (2015) propose personalized differential privacy that provides pre-specified individual privacy parameters which are independent of the learning algorithm, e.g., users can choose different levels of privacy guarantees based on their sensitivities privacy leakage (Mühl & Boenisch] 2022). A recent line of works also uses the variation in example-wise sensitivities that naturally arise in learning to study example-wise privacy. Per-instance differential privacy captures the privacy parameter of a target example with respect to fixed training set (Wang) 2019 Redberg & Wang 202T Golatkar al., 2022). Feldman Zrnic (202T) design an individual Rényí differential privacy filter. The filter stops when the accumulated cost reaches target budget that is defined before training. It allows examples with smaller per-step privacy costs to run for more steps. The final privacy guarantee offered by the filter is still the worst-case over all possible outputs the predefined budget has to be independent of the algorithm outcomes. In this work, we propose output-specific differential privacy and give efficient algorithm to compute individual guarantees of DP-SGD, We further discover that the disparity in individual privacy parameters correlates well with the disparity in utility.
2

---

Under review as a conference paper at ICLR 2023
2
PRELIMINARIES
We first give some background on differential privacy. Then we highlight the challenges in computing individual privacy for DP-SGD. Finally, we argue that providing the same privacy bound all examples is not ideal because of the variation in individual gradient norms.
2.1 BACKGROUND ON DIFFERENTIALLY PRIVATE LEARNING
Differential privacy builds on the notion of neighboring datasets. A dataset D = [d.)== is a neighboring dataset of ITy (denoted as D IE) if DV' can be obtained by adding/removing one example from D. The privacy guarantees in this work take the form of (e, -difffrrreett privacy.
Definition 1. [Individual (),6) For datapoint d, let DB be an arbitrary dataset and TV/ = DU DU{d} be its neighboring dataset. An algorithm A satisfies (#(d), 6)-individual DP if for any subset of outputs & C Range (A) it holds that
Pr[A(I)) E E S (=(d) Pr(A(D)) SS] + and Pr[A(TT') e S cc(d) Pr[A(D) E ES)+ +
We further allow the privacy parameter & to be function of a subset of outcomes to provide sharper characterization of privacy. We term this variant as output- suppt--ppecific (s. 6)-DP. It shares similar insights as the ex-post DP in Ligett et al. (2017); Redberg & Wang (2021) both definitions tailor the privacy guarantee to algorithm outcomes. Ex-post DP characterizes privacy after observing a particular outcome. In contrast, the canonical (e, 5-DD is an ex-ante privacy notion. Ex-ante refers to 'before sampling from the distribution'. Ex-ante DP builds on property about the distribution the outcome. When the A in Definition 2 contains more than one outcome, output-specific (s, 0)D remains ex-ante because it measures how the outcome is distributed over A.
Definition 2. [Oulput-specinn individual (e, 8)-DPJ Fix a datapoint d and a of outcomes A. C Range (A), let D be an arbitrary dataset and D' = D U {d]. An algoritim A satisfies (E(A, d), 6)- individual DP for d at à for any S A holds that
Pr[A(D) 8) S c(h.d) Pr[A(DD) ( $] + 8 and Pr[A(ID') e (H(()) E 8
Definition 2 has the same semantics as Definition] | once the algorithm's outcome belongs to A is known. It strict generalization (c, 5D-DP as one can recover (c, 8DP by maximizing e(A, d) over A and d. Making this generalization is crucial for us precisely compute the privacy parameters of models trained with DP-SGD. The output of DP-SGD a sequence of models {0.)ī= where T is number of iterations. The privacy risk at step highly depends on the training trajectory (the first t 1 models). For example, one can adversarially modify the training data and hence change the training trajectory to maximize the privacy risk of target example (Tramer et al., 2022 With Definition 2 we can analyze the privacy guarantee of DP-SGD with regards to a fixed training trajectory, which specifies subset of DP-SGD's outcomes. In comparison, canonical DP analyzes the worst-case privacy over all possible outcomes which could give loose privacy parameters.
common approach for doing deep learning with differential privacy is make each update differentially private instead of protecting the trained model directly. The composition property of differential privacy allows us reason about the overall privacy of running several such steps. We give simple example to illustrate how to privatize each update. Suppose we take the sum of all gradients = > 9i from dataset ID. Without loss of generality, further assume we add an arbitrary example d' to obtain a neighboring dataset DD' The summed gradient becomes v' = + g'. where g' is the gradient of d'. If we add isotropic Gaussian noise with variance o², then the output distributions of two neighboring datasets are
A(D) ~ ~N(, and A(DD) ~ N(w',0"))
We then can bound the divergence between Gaussian distributions prove differential privacy, e.g., through Rényi differential privacy (RDP) (Mironov) (007)). We give the definition of individual RDP in Appendix A The expectations of A(D) and A(DD") differ by g'. larger gradient leads to larger difference and hence a worse privacy parameter.
2.2 CHALLENGES OF COMPUTING INDIVIDUAL PRIVACY PARAMETERS FOR DP-SGD
Privacy accounting in DP-SGD is more complex than the simple example in Section 22. because the analysis involves privacy amplification by subsampling. Roughly speaking, randomly sampling
3

---

Under review as a conference paper at ICLR 2023
minibatch in DP-SGD strengthens the privacy guarantees since most points in the dataset
not involved in a single step. How subsampling complicates the theoretical privacy analysis has
been studied extensively (Abadi et al.] 2016 Balle et al. 2018 Mironov et al. 2019 Zhu & Wang 2019; Wang et al. 2019). In this section, we focus on how subsampling complicate the empirical computation of individual privacy parameters.
Before we expand on these difficulties, we first describe the output distributions of neighboring datasets in DP-SGD (Abadi et al. 20T6). Poisson sampling is assumed, i.., each example is sampled independently with probability p. Let v Σiem 9: be the sum of the minibatch of gradients of D, where M is the set of sampled indices. Consider also neighboring dataset WD that has one datapoint with gradient g' added. Because of Poisson sampling, the output is exactly v with probability 1 p (g' is not sampled) and is v' = g with probability (g' is sampled). Suppose we still add isotropic Gaussian noise, the output distributions of two neighboring datasets are
A(DD) ~ (( A(D') ~
(1)
with prob. 1 1- p. A(D') ~ o2) with prob. p.
(2)
With Equation and (2). we explain the challenges in computing individual privacy parameters.
2.2.1 FULL BATCH GRADIENT NORMS ARE REQUIRED AT EVERY ITERATION
There is some privacy cost for d' even if it is not sampled in the current iteration because the analysis makes use of the subsampling process. For a given sampling probability and noise variance, the amount of privacy cost is determined by |lg') [|. Therefore, we need accurate gradient norms of all examples to compute accurate privacy costs every iteration. However, when running SGD, we only compute minibatch gradients. Previous analysis of DP-SGD evades this problem by simply assuming all examples have the maximum possible norm, i.e., the clipping threshold.
2.2.2 COMPUTATIONAL COST OF INDIVIDUAL PRIVACY PARAMETERS HUGE
The density function of A(D)) is a mixture of two Gaus- sian distributions. Abadi et al. (2166) compute the Rényi divergence between A(D)) and A(DE)) numerically to get tight privacy parameters. Although there are some asymp- totic bounds, those bounds are looser than numerical com- putation, and thus such numerical computations are nec-
DP-SGD CIFAR 10 with 7.5
25
Airplane
Aversge Gradient toom
Automobile
Calt
20-
essary in practice (Abadi et al.] 2016: Wang et al., 2019)
15
Mironov et al.] 20pp et | (021). In the classic analysis, there is only one numerical computation examples have the same privacy cost over all iterations.
all
10.
However, naive computation of individual privacy param- eters would require up to n X T numerical computations, where is the dataset size and T is the number of itera- tions.
6
50
100 Epoch
150
200
Figure 2: Gradient norms CIFAR-10.
2.3 AN OBSERVATION: GRADIENT NORMS DEEP LEARNING VARY SIGNIFICANTLY
As shown in Equation I and 2 the privacy parameter of an example is determined by its gradient norm once the noise variance given. is worth noting that examples with larger gradient norms usually have higher training loss. This implies that the privacy cost of an example correlates with its training loss, which we empirically demonstrate in Section 4 and 5 In this section, we show gradient norms of different examples vary significantly to demonstrate that different examples experience very different privacy costs. We train a ResNet-20 model with DP-SGD. The maximum clipping threshold is the median of gradient norms at initialization. We plot the average norms of three difffernnt classes in Figure 2 The gradient norms of different classes show significant stratification. Such stratification naturally leads to different individual privacy costs. This suggests that quantifying individual privacy parameters may be valuable despite the aforementioned challenges.
3 DEEP LEARNING WITH INDIVIDUAL PRIVACY
We give an efficient algorithm (Algorithm[I T to estimate individual privacy parameters for DP-SGD. The privacy analysis of Algorithm D is in Section 3.J We perform two modifications to make individual privacy accounting feasible with small computational overhead. First, we compute full
4

---

Under review as a conference paper at ICLR 2023
batch gradient norms once in while, e.g., at the beginning of every epoch, and use the results to estimate the gradient norms for subsequent iterations. We show the estimations of gradient norms are accurate in Section 3.2 Additionally, we round the gradient norms to given precision so the number of numerical computations is independent of the dataset size. More details of this modification are in Section 3.3 Finally, we discuss how to make use of the individual privacy parameters in Section (3.4]
In Algorithm 1 we clip individual gradients with estimations of gradient norms (referred to as individual clipping). This is different from the vanilla DP-SGD that uses the maximum threshold to clip all examples (Abadi et al. 2016). Individual clipping gives us exact upper bounds on gradient norms and hence we have exact bounds on privacy costs. Our analysis is also applicable vanilla DP-SGD though the privacy parameters in this case become estimates of exact guarantees, which is inevitable because one can not have exact bounds on gradient norms at every iteration when running vanilla SGD. We report the results for vanilla DP-SGD in Appendix C.2 Our observations include: (I) the estimates of privacy guarantees for vanilla DP-SGD are very close to the exact ones, (2) all our conclusions in the main text still hold when running vanilla DP-SGD, (3) the individual privacy of Algorithm very close to that of vanilla DP-SGD.
Alg Algorithm 1: Deep Learning with Individual Privacy Accounting
Input
:aaxmmmm clipping threshold C, rounding precision r, noise variance a², sampling probability frequency of updating full gradient norms every epoch K, number of epochs E.
Let (C()) Nim be estimated gradient norms of all examples and initialize ( = C.
Let C = fr, 2r, 3r, .r,..., ,..,,C C} be all possible norms under rounding.
for e C de
Compute Rényi divergences different orders between Equation
2 and store the results in Pa-
end
Let
(o(*) = 0);=1 he the accumulated Rényi divergences at different orders.
1
for
= 1 to F. do
for
to [1/p] do
t= +' [1/p] x (e- 1) I/Global step count.
10
l mod [1/pK] = 0 then
Compute full batch gradient norms { Ji=--
Update gradient estimates with rounded norms (C++) arg min ()
13
end
Sample minibatch of gradients (5) Jj=1= where I is the sampled indices.
Clip gradients (z clip(g ((1))).
Update model 0, = 0 "1 g (1y) z), where o0.
for i to do
Set (9) Pe where (((). 00 = (4) + )()) //Update individual privacy costs.
20
end
21
end
22
end
3.1 PRIVACY ANALYSIS OF ALGORITHM
We state the privacy guarantee of Algorithm in Theorem account the privacy costs of a realized run of Algorithm
3.1 We use output-specific DP to precisely
Theorem 3.1. (Output-specifet privacy guarantee] Algorithum at step t satisfies (of.) + log(1/5) 8)-
output-speciffe individual DP for the in example at A accumulated RDP at order a and O is the domain of Or-
(0,.... 0, where da is the
To prove Theorem 3.1 we first define a t-step non-adaptive composition with oI...., - We then show RDP of the non-adaptive composition gives an ouput--ppecifc privacy bound on the adaptive composition in Algorithm I
We relegate the proof to Appendix
3.2 ESTIMATIONS OF GRADIENT NORMS ARE ACCURATE
Although the gradient norms used for privacy accounting are updated only occasionally, we show that the individual privacy parameters based estimations are very close the those based exact
5

---

Under review as a conference paper at ICLR 2023
CIFAR-10: K
MNIST: K 0.5
UTKFace-Gender: K 0.5
UTKFace-Age: K 0.5
(lectmaadd (omm))))
(Busiou papenps)
(pusiou payoinss)
y
2
yex
7.78
2-4
y=
y 4.2
Paanerare 1991
Mox 2- +0.00
F- C22
(lactual norms)
(actual norms]
factual norms)
(actual norma)
CIFAR-10: K
MNIST: K
UTKFace-Gender: K-1
UTKFace-Age: K-1
Elsdimaae nomms)
m
[suaiou (ogpintoo
(Duliiu (ocainnco
y
y 2.4
4-4.5
y 42
930
1337
Mox 023
Warle-d---2
2-1--33
factuall norms)
(actual norms]
fectual norms)
(ectual norms)
CIFAR-10: K
MNIST: K
UTKFace-Gender:
UTKFace-Age: K
(estimated norms))
(tuuzu poopnnss)
y= 7.8
y 2.3
y 4,5
y 42
wwwns/eene CCL
Porsee/a 188
2- -028
Pacli-4-60
Elactual norms)
(ectual norms]
factual norms)
(actual norms)
Figure 3: Privacy parameters based on estimations of gradient norms (e) versus those based on exact
norms (f). The results suggest that the estimations of gradient norms are close to the exact norms.
norms (Figure3) This indicates that the estimations of gradient norms are close to the exact ones. We comment that the privacy parameters computed with exact norms are not equivalent to those of vanilla DP-SGD because individual clipping in Algorithm T slightly modifies the training trajectory. We show individual clipping has small influence the individual privacy of vanilla DP-SGD in Appendix C.2
To compute the exact gradient norms, we randomly sample 1000 examples and compute the exact gradient norms at every iteration. We compute the Pearson correlation coefficient between the privacy parameters computed with estimated norms and those computed with exact norms. 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 B. The e values based on estimations are close to those based on exact norms (Pearson's r > 0.99) even we only update the gradient norms every two epochs (K = 0.5). Updating full batch gradient norms more frequently further improves the estimation, though doing so would increase the computational overhead.
is worth noting that the maximum clipping threshold C' affects the computed privacy parameters. Large C' increases the variation 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 for learning (Chen et al. 2020: Song et al.) 2021). In Appendix D we show the influence of using different C on both accuracy and privacy.
3.3
ROUNDING INDIVIDUAL GRADIENT NORMS
The rounding operation in Algorithm T is essential to make the computation of individual privacy parameters feasible. The privacy cost of one example at each step is the Rényi divergences between Equation (1) and (2). For a fixed sampling probability and noise variance, we use Pe to denote the privacy cost of an example with gradient norm Note that p. is different for every value of Consequently, there are at most n x E different privacy costs because individual gradient norms vary across different examples and epochs (n is the number of datapoints and E is the number of training epochs). In order to make the number of different p. tractable, we round individual gradient norms with prespecified precision (see Line 12 in Algorithm [ Because the maximum clipping

---

Under review as a conference paper at ICLR 2023
threshold C' is usually small constant, then, by the pigeonhole principle, there are at most [C/r] different values of Pe- Throughout this paper we set r = 0.01C that has almost no impact on the precision of privacy accounting.
Table Computational costs of computing individual privacy parameters for CIFAR-10 10 with K
With Rounding
Without Rounding
# of numerical computations
1 10
1 10"
Time (in seconds)
< 3
~ 2.6 x 10
We give concrete comparison on the computational costs in Table |
We run the numerical method in Mironov et al. (2019) once for every different privacy cost (with the default setup in the Opacus library YYousefoour et al. 2021)). We run SPD CIFAR- 10 for 200 epochs with K 1. All results in Table use multiprccessing with 5 cores of an AMD EPYC 7V13 CPU. With rounding. the overhead of computing individual privacy parameters is negligible. In contrast, the computational cost without rounding is more than 7 hours.
3.4
WHAT CAN WE Do WITH INDIVIDUAL PRIVACY PARAMETERS?
Note that individual privacy parameters are dependent on the private data and thus sensitive, and consequently may not be released publicly without care. We describe some approaches to safely make use of individual privacy parameters.
The first approach is to release é; to the owner of the ith example. Although we use gradient norms without adding noise, this approach does not incur additional privacy loss for two reasons. First, it is safe for the ith example because only the rightful owner sees E;. Second, releasing E, does not increase the privacy loss of any other examples. This is because the computation only uses (01..... 06-1). which is reported in privacy-preserving manner. We proof the claim in Appendix
The second approach is to privately release aggregate statistics of the population, e.g., the average or quantiles of the values. Recent works have demonstrated such statistics can be published accurately with minor privacy cost Andrew et al. (202T). We show the statistics can be released accurately with very small privacy parameter (e 0.1) in Appendix F.2
Finally, individual privacy parameters also serve powerful tool for trusted data curator to improve the model quality. By analysing 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
We first show the distribution of individual privacy parameters of running DP-SGD four classifi- cation tasks in Section 4.1
Then we investigate how individual privacy parameters correlate with
training loss in Section 4.2 Experimental setup as follows.
Datasets. We use two benchmark datasets MNIST (n 60000) and CIFAR-10 (n = 50000) LeCunn et al.] 1998 Krizhevsky, 2009) as well as the UTKFace dataset (n ~ 15000) (Zhang et al. 201 7) that contains the face images of four different races (White, 2000; Indian, n ~ 2800). We construct two tasks on UTKFace: predicting gender, and predicting whether the age is under 30 We slightly modify the dataset between these tasks by randomly removing a few examples to ensure each race has balanced positive and negative labels.
7000: Black, ~ 3500; Asian, ~
Models and hyperparameters. For CIFAR-10, we use the WRN16-4 model in De et al. (022)) ). 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
UTKFace, 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 = 1 on CIFAR-10. following De et al. (2022). For MNIST and UTKFace, we set C' as the median of
We acknowledge that predicting gender and age from images may be problematic. Nonetheless, as facial images have previously heen highlighted as setting where machine learning has disparate accuracy different groups, revisit this domain through related lens. The labels are provided by the dataset curators.
7

---

Under review as a conference paper at ICLR 2023
CIAR 5/
MNIST (Pearson's 0.921
UTKeaae Gender (Pearson's 0.93
UTieFsce (Pearson's 0.94)
2.-
15-
50-
100
3.5
2.0
2-222 kgght 1.89
0.20egg/7
y- 0:300000000000000000000000000000
0.
2-3
yw
y242
10
10
10
10
10
10
107
1314
10
10
10
10
10
10
10
10
10
10
10"
10
10
Figure 4: Privacy parameters and final training losses. Each point shows the loss and privacy parameter of one example. Pearson's ' is computed between privacy parameters and log losses.
gradient norms at initialization, following the suggestion in Abadi et al. (201)). We set K =3 3 for all experiments in this section. More details about the hyperparameters in Appendix B
4.1 INDIVIDUAL PRIVACY PARAMETERS VARY SIGNIFICANTLY
Figure I shows the individual privacy parameters on all datasets. The privacy parameters vary across a large range on all tasks. On the CIFAR- 10 dataset, the maximum value is 7.8 while the minimum E value is only 1.1. We also observe that, for easier tasks, more examples enjoy stronger privacy guarantees. For example, ~40% of examples reach the worst-case do so on MNIST. This may because the loss decreases quickly when the task is easy, resulting in gradient norms also decreasing and thus reduced privacy loss.
CIFAR-10 while only ~3%
4.2 PRIVACY PARAMETERS AND LOSS ARE POSITIVELY CORRELATED
We study how individual privacy parameters correlate with individual training loss. The analysis in Section 2 suggests that the privacy parameter of one example depends on its gradient norms across training. Intuitively, an example would have high loss after training if its gradient norms are large. We visualize individual privacy parameters and the final training loss values in Figure 4 The individual privacy parameters on all datasets increase with loss until they reach the maximum s. To quantify the order of correlation, we further fit the points with one- mie-dmmnnioonl logarithmic functions and compute the Pearson correlation coefficients with the privacy parameters predicted by the fitted curves. The Pearson correlation coefficients are larger than 0.9 on all datasets, showing an logarithmic correlation between the privacy parameter of a datapoint and its training loss.
5 GROUPS ARE SIMULTANEOUSLY UNDERSERVED IN BOTH ACCURACY AND PRIVACY
5.1 LOW-ACCURACY GROUPS HAVE WORSE PRIVACY PARAMETERS
It is well-documented that machine learning models may have large differences in accuracy on different groups (Buolamwini & Gebru 2018 Bagdasaryan et al. 2019). Our finding demonstrates that this disparity may be simultaneous in terms of both accuracy and privacy. We empirically verify this by plotting the average and training/test accuracy of different groups The experiment setup the same as Section 4 For CIFAR-10 10 and MNIST, the groups are the data from different classes, while for UTKFace, the groups are the data from different races.
We plot the results in Figure The groups are sorted based on the average e. Both training and test accuracy correlate well with e. Groups with worse accuracy do have worse privacy guarantee in general. On CIFAR-10, the average e of the 'Cat' class (which has the worst test accuracy) is 43.6% higher than the average E of the 'Automobile' class (which has the highest test accuracy). On UTKFaae- Gender, the average E of the group with the lowest test accuracy ( ('Asian') ') is 25.0% higher than the average E 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.
5.2 LOW-ACCURACY GROUPS SUFFER FROM HIGHER EMPIRICAL PRIVACY RISKS
We run membership inference (MI) attacks against models trained without differential privacy to study whether underserved groups are more vulnerable to empirical privacy attacks. Several recent works show that MI attacks have higher success rates on some examples than other examples (Song
8

---

Under review as a conference paper at ICLR 2023
CIFAR-10
VNST
Traving (ttax Hil -60--5..000 ANN)
140
Traeegg har (Max
56
12
123
344
1.
14
33
45
Micet
Acto. Truck Hone Door
Ca:
Sulgruu Name
Subgres hame
Gender
Ago
100
Traere Pax -33 A9)
Test Aiy. plax ad
Tedt Acr (M0x, Min w18.99
57.5
325
-38
275
20.0
22
225
525
Peserncir Mice
Pewo Perembtor MecwE3T:
Adion
While
Nams
Subgrau
Figure 5: Accuracy and average e of different groups. Groups with worse accuracy also have worse privacy in general.
lac: Accursoy 1i Suscems Kisa
Isc: Accussyy 40 Sustons fasa
last Accetiy
55-
201.-
M Succoss Sala
Zie
Socoii Fare
35.2
flle
56.3
16-
ban
Sungress Nome
Sengree Nome
54 Suegrce Nore
Figure 6: MI attack success rates on different groups. Target models are trained without DP
& Mittal 2020
Choquette-Choo al. 2021 Carlini et al. 2021). In this section, directly connect such disparity in privacy risks with the unfairness in utility. We use simple loss-threshold attack that predicts an example is a member its loss value is smaller than a prespecified threshold (Sablayrolles) et al. 2019). For each group, we use its whole test set and random subset of training set so the numbers of training and test losses 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. More implementation details are in Appendix [ The results are in Figure 6 The groups are sorted based on their average The disparity in privacy risks is clear. On UTK F'TK-aceAAee the MI success rate is 70.6% on the 'Black' group while is only 60. 1% on the 'Asian' group. This suggests that empirical privacy risks also correlate well with the disparity in utility.
CONCLUSION
We propose an efficient algorithm to accurately estimate the individual privacy parameters for DP- SGD. We use this new algorithm to examine individual privacy guarantees on 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 has two immediate implications. Firstly, it shows that the learning objective aligns with privacy protection for a given privacy budget, i.e., the better the model learns about an example, the better privacy that example would get. Secondly, it suggests that mitigating the utility faimess under differential privacy is more tricky than doing so in the non non-privee private case. This is because classic methods such as upweighting underserved examples would exacerbate the disparity in privacy.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Martin Abadi, Andy Chu, Ian Goodfellow, Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of ACM Conference Computer and Communications Security, 2016.
Galen Andrew, Om Thakkar, Brendan McMahan, and Swaroop Ramaswamy. Differentially private learning with adaptive clipping. In Advances Neural Information Processing Systems, 2021.
Rohan Anil, Badih Ghazi, Vineet Gupta, Ravi Kumar, and Pasin Manurangsi. Large-scale differen- tially private BERT, arXiv preprint arXiv:2108.000 01624, 2021.
Eugene Bagdasaryan, Omid Poursaeed, and Vitaly Shmatikov. Differential privacy has disparate impact on model accuracy. Advances in Neural Information Processing Systems, 2019.
Borja Balle, Gilles Barthe, and Marco Gaboardi. Privacy amplification by subsampling: Tight analyses via couplings and divergences. In Advances in Neural Information Processing Systems, 2018.
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-William private deep learning with membership inference. arXiv preprint
William Grassal, Jonas Robl, and Florian Kerschbaum. Assessing differentially
2019.
Zhiqi Bu, Jinshuo Dong, Qi Long, and Weijie J. Su. Deep learning with Gaussian differential privacy. Harvard Data Science Review, 2020.
Zhiqi Bu, Jialin Mao, and Shiyun Xu. Scalable and efficient training of large convolutional neural networks with differential privacy. arXiv preprint arXiv: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, Jemej Kos, and Dawn Song. The secret sharer: Evaluating and testing unintended memorization in neural networks. 28th USENIX Security Symposium, 2019.
Nicholas Carlini, Steve Chien, Milad Nasr, Shuang Song, Andreas Terzis, and Florian Tramer. Membership inference attacks from first principles. arXiv preprint arXiv:2112.035700 2021.
Xiangyi Chen, Steven Z Wu, and Mingyi Hong. Understanding gradient clipping in private sgd: A geometric perspective. Advances in Neural Information Processing Systems, 2020.
Christopher Choquette-Choo, Florian Tramer, Nicholas Carlini, and Nicolas Papernot. Label-only membership inference attacks. In Proceedings of the 38th International Conference on Machine Learning, ICML '21, pp. 1964-1974. JMLR, Inc., 2021.
Soham De, Leonard Berrada, Jamie Hayes, Samuel Smith, and Borja Balle. Unlocking high- accuracy differentially private image classification through scale. arXiv preprint arXiv:2204.13660, 2022.
Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and Trends@ in Theoretical Computer Science, 2014.
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.
Vitaly Feldman and Tijana Zrnic Individual privacy accounting via a Renyi filter. In Advances in Neural Information Processing Systems, 2021.
Aditya Golatkar, Alessandro Achille, Yu- Xiang Wang. Aaron Roth, Michael Kearns, and Stefano Soatto. Mixed differential privacy in computer vision. Proceedings of IEEE Computer Society Conference Computer Vision and Pattern Recognition, 2022.
10

---

Under review as a conference paper at ICLR 2023
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. arXiv preprint arXiv:2203.02745, 2022.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of IEEE Computer Society Conference on 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 Neural Information Processing Systems, 2020.
7ach Jorgensen, Ting Yu, and Graham Cormode. Conservative or liberal? personalized differential privacy. In International Conference on Data Engineering (ICDE), 2015.
Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions. In Proceedings of the 34th International Conference on Machine Learning, 2017.
Alex Krizhevsky. Learning multiple layers of 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 applica- tions to differentially private deep learning. arXiv preprint arXiv:2103.01379, 2021.
Xuechen Li, Florian Tramèr, Percy Liang, and Tatsunori Hashimoto. Large language models can be strong differentially private learners. Proceedings of the 10th International Conference on Learning Representations, 2022.
Katrina Ligett, Seth Neel, Aaron Roth, Bo Waggoner, and Steven Z Wu. Accuracy first: Selecting differential privacy level for accuracy constrained erm. Advances in Neural Information Processing Systems, 2017.
Harsh Mehta, Abhradeep Thakurta, Alexey Kurakin, and Ashok Cutkosky. Large scale transfer learning for differentially private image classification. arXiv preprint arXiv: 2022.
Ilya Mironov. Rényi differential privacy. In Proceedings of the 30th IEEE Computer Security Foundations Symposium, 2017.
Ilya Mironov, Kunal Talwar, and Li Zhang. Rényi differential privacy of the sampled gaussian mechanism. arXiv preprint arXiv::900 10530, 2019.
Christopher Mühl and Franziska Boenisch. Personalized PATE: Differential privacy for machine learning with individual privacy guarantees. arXiv preprint 27X1:22202.10517, 2022.
Milad Nasr, Shuang Song, Abhradeep Thakurta, Nicolas Papernot, and Nicholas Carlini. Adver- sary instantiation: Lower bounds for differentially private machine learning. arXiv preprint arXiv:2101.0455: 001.55555. 2021.
Frederik Noe, Rasmus Herskind, and Anders Søgaard. Exploring the unfaimess of dp-sgd across settings. arXiv preprint arXiv:2202.1 12058, 2022.
Nicolas Papernot, Martín Abadi, Ulfar Erlingsson, Ian Goodfellow, and Kunal Talwar. Semi- supervised knowledge transfer for deep learning from private training data. In Proceedings of the 5th International Conference Learning Representations, 2017.
Rachel Redberg and Yu-Xiang Wang. Privately publishable per-instance privacy. In Advances in Neural Information Processing Systems, 2021.

---

Under review as a conference paper at ICLR 2023
Alexandre Sablayrolles, Matthijs Douze, Cordelia Schmid, Yann Ollivier, and Hervé Jégou. White- box vs black-box: Bayes optimal strategies for membership inference. In Proceedings of the 36th International Conference Machine Learning. 2019.
Liwei Song and Prateek Mittal. Systematic evaluation of privacy risks of machine learning models. arXiv preprini arXiv:2003. 10595, 2020.
Shuang Song, Kamalika Chaudhuri, and Anand D Sarwate. Stochastic gradient descent with differ- entially private updates. 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 private prediction in health care settings. In Proceedings of ACM Conference on Fairness, Accountability, and Transparency, 2021.
Florian Tramèr, Reza Shokri, Ayrton San Joaquin, Hoang Le, Matthew Jagielski, Sanghyun Hong, and Nicholas Carlini. Truth serum: Poisoning machine learning models to reveal their secrets. arXiv preprint urXiv:2204.00032, 2022.
Yu-Xiang Wang. Per-instance differential privacy. The Journal of Privacy and Confidentiality, 2019.
Yu-X 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 on Artificial Intelligence and Statistics, 2019.
Justin Whitehouse, Aaditya Ramdas, Ryan Rogers, and Zhiwei Steven Wu. Fully adaptive composi- tion differential privacy. arXiv preprint wxXiv:2233005881 2022.
Ashkan Yousefpour, Igor Shilov, Alexandre Sablayrolles, Davide Testuggine, Karthik Prasad, Mani Malek, John Nguyen, Sayan Ghosh, Akash Bharadwaj, Jessica Zhao, Graham Cormode, and Ilya Mironov, Opacus: User-friendly differential privacy library in PyTorch. arXiv preprint arXiv:2109.1 12298, 2021.
Da Yu, Saurabh Naik, Arturs Backurs, Sivakanth Gopi, Huseyin A 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 Learning Representations, 2022.
Zhifei Zhang, Yang Song, and Hairong Qi. Age progression/regressinn by conditional adversarial autoencoder. In Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2017.
Yuqing Zhu and Yu-Xiang Wang. Poission subsampled Rényi differential privacy. In Proceedings of the 36th International Conference on Machine Learning, 2019.
12

---

Under review as a conference paper at ICLR 2023
A PROOF OF THEOREM 3.1
Theorem 3.1. (Ouiput-specifer privacy guarantee] Algorithm / at step t satisfies (oa + 1og(1/5) 6)- 0,-1, θ²), where (1) is the
ouppu--ppeiiic individual DP for the ith example A accumulated RDP at order a and O2 is the domain of 0c.
We compose the privacy costs different steps through Rényi differential privacy (RDP) (Mironov] 2017). RDP uses the Rényi divergence at different orders to measure privacy. We use Da (2 = o-T log f [' de ) dv to denote the Rényi divergence at order between and and D (u|lv) max (ullv), (,(ull() to denote the maximum divergence of two directions. The definition of individual RDP as follows.
Here give the the proof of Theorem 3.1
de
Definition 3. [Individual RDP Feldman & Zrnic (22Tg) | Fix datapoint d, let D be an arbitrary dataset and ID' 13 U {d). A randomized algorithm A satisfies (a, p(d)) -indvviud RDP for d if holds that D (A(D)))A(I))) S p(d).
Let
be sequence of randomized algorithms and (1....,00-)) be some arbitrary fixed outcomes from the domain, we define
(0 D)
Ac A(,,)....0.,1,
Noting that A is adaptive composition the input of each individual mechanism does depend on the outputs of previous mechanisms. Further let
A (D) (A,
A((Ai
be the adaptive composition. Theorem [A.1] we show a RDP bound on the non-adaptive composition A()) gives an output-specific DP bound on the adaptive composition A(t),
Theorem A.1. Let A = (01...., Range(Ae)) C Range(A(0) O....., O2-1 are some arbitrary fixed outcomes. If (.) satisfies RDP order then A (T))
Range(A(() where
satisfies (o. + a-1 8) -oupput--ppciif differential privacy A.
Proof. For a given outcome g(t) = =011, (81,0,...,00111111 E A, we have (T())(D) = B(0]
P ( p(t-1)) P (A.AA())...AA..11))))
A.- D) (1- (ID = 8((-11], (3)
=P =P[A nt (1 (TD) = 9it o P (OA 0,1,, = 6z],
(4)
by the product rule of conditional probability. (ID)) = ((t-1)]. we have P [A(t) (ID) = 800]
Apply the product rule recurrently on
P (1(-2) = 2)) P (A ......,...... DD) = P ...-,....0..11.))) = 0z), = =P[Ai(D) = 0,) (0, = 02) O2)...P(A.(0. PO.. 0z),
(5)
(6)
= =P[A0 (O....... D) 0(0)
(7)
In words, (A and (tt) are identical in A. Therefore, A satisfies (c. 6)- at any $ C A if A(t)
satisfies (s, dD. Converting the RDP bound on (D) into (c, 8)DP bound with Lemma A.2 then completes the proof.
Lemma A.2 (Conversion from RDP to (e, 8)DP Mironov 2017 A satisfies (a, RDP then A satisfies (p + a-1
log(1/6), D)D for all 0 6 <.
13

---

Under review as a conference paper at ICLR 2023
We comment that the RDP parameters of the adaptive composition of Algorithm 1 are random variables because they depend on the randomness of the intermediate outcomes. This is different from the conventional analysis that chooses constant privacy parameter before training. Composition of random RDP parameters requires additional care because one needs to upper bound the privacy parameter over its randomness (Feldman & Zmic 2021 Lécuyer 2021] Whitehouse et al.) (022)) In this paper, we focus on the realizations of those random RDP parameters and hence provide a precise output-specific privacy bound.
B MORE IMPLEMENTATION DETAILS
The batchsize is 4K, 2K, and 200 for CIFAR-I0, MNIST, and UTKFace, respectively. The training epoch is 300 for CIFAR- 10 and 100 for MNIST and UTKFace. We use the package yousefpour et al. (202T) to compute the noise multiplier. The standard deviation of noise in Algorithm is the noise multiplier times the maximum clipping threshold. The non-private models in Section 5.2 are as follows. For CIFAR-10, 10, we use ResNer20 model in He et al. (20T6) that has ~0.2M parameters, with all batch normalization layers replaced by group normalization layers. For UTKFace, we use the same models in Section We remove both gradient clipping and noise for non non-private training. Other settings are the same as those in Section 4 All experiments are run on a single Tesla V100 GPU with 32G memory. Our source code, including the implementation of our algorithm well as scripts to reproduce the plots, will be released soon.
C
MORE DISCUSSION ON INDIVIDUAL CLIPPING
C.1 INDIVIDUAL CLIPPING DOES NOT AFFECT ACCURACY
Here experiments to check the influence of using individual clipping thresholds on utility. Algorithm uses individual clipping thresholds to ensure the computed privacy parameters are strict privacy guarantees. If the clipping thresholds are close to the actual gradient norms, then the clipped results are close to those of using single maximum clipping threshold. However, if the estimations of gradient norms are not accurate, individual thresholds would clip more signal than using single maximum threshold.
Table 2: Comparison between the accuracy of using individual clipping thresholds and that of using a single maximum clipping threshold. The maximum is 7.8 for CIFAR-10 and 2.4 for MNIST.
CIFAR-10
MNIST
Individual
74.0 19).
97.17 (+0.12)
Maximum
74.1 (+00244)
97.26 (+0.111)
We compare the accuracy of two different clipping methods in Table 2 The individual clipping thresholds are updated once per epoch. We repeat the experiment four times with different random seeds. Other setups the same those in Section 4 The results suggest that using individual clipping thresholds in Algorithm D has negligible effect on accuracy.
C.2 EXPERIMENTS WITHOUT INDIVIDUAL CLIPPING
We run Algorithm [ without individual clipping, i.e., vanilla DP-SGD in Abadi et al. (2016), to see whether our conclusions in the main text still hold. Specifically, we change the Line 15 of Algorithm [ to clip all gradients with the maximum clipping threshold C. Other experimental setup is the same as that Experiment and Appendix
We get accurate estimations of actual guarantees. The privacy parameters are still computed with the estimations of gradient norms and hence are estimations of the actual guarantees. We compare the privacy parameters and actual guarantees Figure 7 To compute the actual guarantees, we randomly sample 1000 examples and compute their exact gradient norms at every iteration. The results suggest that the privacy parameters are accurate estimations (Pearson's 's r > 0.99 and small maximum absolute errors).
Privacy parameters still have strong correlation with training loss. In Figure g show privacy parameters computed without individual clipping are still positively correlated with training losses. The Pearson correlation coefficient between privacy parameters and log losses is larger than
14

---

Under review as a conference paper at ICLR 2023
CIFAR-10: K
MNIST: K 0.5
UTKFace-Gender K 0.5
UTKFace-Age: K 0.5
(eectmaadd nomm))))
(Buuoou pacenps)
2 (ousiou payoinss)
y
y=x
7.8
y 2.4
y 4.5
y 4.2
Faneekya E539
Paanerare 1399
Mox U- -0.4
F- C25
Pacle---12
(aacuall norms)
(actual norms]
factual norms)
(actual norms)
CIFAR-10: K
MNIST: K
UTKFace-Gender:
UTKFace-Age: K-1
[estmmaed nomms)
m
[suaiou (ogpin
(Duliiu (ocoincc
4
y-x
7
2.4
y=4.5 4.5
y 4.2
1999
Mox +0.00
Warle-d-636
Eactuall norms)
(actual norms]
fectual norms)
(ectual norms)
CIFAR-1D: K
MNIST: K
UTKFace-Gender:
UTKFace-Age: K
(esttmated norms))
(Buueu pasennss))
y 7.8
2.3
y 4,5
y 42
Porses/a 188
2- -032
Pacli-q-E66
Elactual norms)
(ectual norms]
factual norms)
factual norms)
Figure 7: Privacy parameters based on estimations of gradient norms (s) versus the actual privacy guarantees (é). We do not use individual clipping in this plot. The privacy parameters are very close to the actual guarantees.
CIFAR-10
NNIST (Pearson's 0.921
UTKFace Gender (Pearson's 0.93!
UTKF (Pearson's 0.93)
45
2.8
20
65
15
yu 540mgoo-7
y= 0.23 1.01
A. 4.3
yo 0::0000000000000
60
2.4
10th 10th
10
10 10
10
197
10t
10-
10
10th
10P
10t4
10
10
10
10
30-d
30
30
Loss
Figure 8: Privacy parameters and final training losses. The experiments are run without individual clipping. The Pearson correlation coefficient is computed between privacy parameters and log losses.
0.9 for all datasets. Moreover, we show our observation in Section S] i.e., low-accuracy groups have worse privacy parameters, still holds in Figure 9
We also make a direct comparison with privacy parameters computed with individual clipping. We find that privacy parameters computed with individual clipping are very 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.
D THE INFLUENCE OF MAXIMUM CLIPPING ON INDIVIDUAL PRIVACY
The value of the maximum clipping threshold C would affect individual privacy parameters. A 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 ResNer20 for CIFAR- 10 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, O.3.M, 0.5.M, 1.5M). Other experimental setup is the same as that in Section
15

---

Under review as a conference paper at ICLR 2023
CIFAR-10
MNIST
Acc. (Without LC.
7.5
100
Test Acc. (Without
90
7.0
1.2
98
Accunsc (in
80
97
6.0
96
5.5
95
0.6
94
0.4
60
Privacy Parameter c (Without IC.))
93
Privacy Farameter (Without I.C.)
Privacy Parameter (With LC!.
4.5
Privacy Parameter (With L.C.)
Ship Auto. Truck Frog Horse Air. Deer Dog Bird Cat Subgroup Name
4
Subgroup Name
UTKFace-Gender
UTKFace-Age
Test Acc. (Without I.C.)
3.2
95
Test Acc. (Without I.C.)
3.50
97.5
3.25
Accurscy (in %
85
2.6
Avamag
90.0
2.4
2.2
75
2.25
85.0
2.0
2.00
82.5
Privacy Parameter (Without IC..)
Privacy Parameter (Without L.C.)
Privacy Parameber (With
Privacy Farameter a (With I.C.)
1.75
Indian
Black
White
Asian
Asian
White Subgroup Name
Indian
Black
Subgroup Name
Figure 9: Test accuracy and privacy parameters computed with/without individual clipping (I.C.). Groups with worse test accuracy also have worse privacy in general.
C=0.1M, testacc.=60., max 4:5.5, min c=1.6
0-0.3M, test acc,=64.3 9,9 max ==7.5 min ==1.0
35000
315.0
32000
28000
20000
17500
16000
14000
12000
10500
4000
3500
3.2
1/6
4.
=65.6, max 6--7.5, B.9
1.5M, test acc. max 6-7.5, C-0.5
33000
10000
21000
7000
10000
6000
9000
3000
6000
2000
0.5
1.5
2.4
5.2
4.0
4.8
5.
0.8
1.5
2.4
3.2
4.0
4.5
5.0
Figure 10: Distributions of individual privacy parameters on CIFAR-10 with different maximum clipping thresholds. The dashed line indicates the average of privacy parameters.
16

---

Under review as a conference paper at ICLR 2023
Clip- Median
Clip-0.3
Trairing Acc. M3x,-MMn,.34.85.
8.0
Training Acc. (Nax.MMir -40. 7%6
7.5
-75
70
100
-7.0
Averagez
70-
Averagez
Accunccy
Accuracy
-0.5
60
6.5
50
Privacy
Privacy (MMs--Min11.78)
40
Ship frog
Ship
Irog TruckHorrse Dog Bird Subgroup Name
Subgroup
Clip= 0.5 Median
Clip=1.5 Median
90
Trairing Acc. (Nax, Min.
Training Acc. (Max. Min, -3..9%)
5.50
Test Acc. Mik..MMn.3365%.
7.5
Test Acc. (Max. Min, -3.66333.69)
80
5.25
5.00
6.5
Aueraged
Accuracy
6.0
30-
50
Privacy Farameter x (Max Min-1.7)
Privacy Parameter IMax 0.5-
Ship Auto, Truck Frog Horse Air. Dog
Bird Deer
Cat
Ship Auto. Trück Air. Frog Dog Horse Cat. Deer
Bird
Subgroup
Subgroup Name
Figure 11: Accuracy and average of different groups on CIFAR-IO with different maximum clipping thresholds.
The histograms of individual privacy parameters are in Figure 10 In terms of accuracy, using clipping thresholds near the median gives better accuracy. 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 When privacy parameter while only ~2% datapoints reach the worst parameter when C = 1.5M.
1,, nearly 70% datapoints reach the worst
The correlation between accuracy and privacy is in Figure 11 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.5M to 0.5M, 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 only 1.3 (from 4.2 to 5.5).
E MAKE USE OF INDIVIDUAL PRIVACY PARAMETERS
E. RELEASING INDIVIDUAL PRIVACY PARAMETERS TO RIGHTFUL OWNERS
Let e; be the privacy parameter of the in user, we can compute e; with the training trajectory and d; itself. Theorem E. shows that releasing E; does not increase the privacy cost any other example d, * d; The proof uses the fact that computing E; can be seen post-processing of (f.....,fk (2-1). which is reported in savacc-preserving manner.
an algorithm that is (c,, opeppt---pecffe DP for d, at A C O. Let (,,d,) O x O be a post-processing function that returns the privacy parameter of d; (+ dz) and the training trajectory. We have f is (Ej, 8) coutput-speet DP for d, at IF C R x O where FF { (a,di) di) A) is all possible post-processing resulis.
Theorem E.1. Let A - O
Proof. We first note that the construction is independent of dj. Without loss generality, let D. DV' D be the neighboring datasets where TV' DU (d,). Let S C F be arbitrary event and
17

---

Under review as a conference paper at ICLR 2023
Table 3: Populational statistics of individual privacy parameters MNIST. The average estimation
eπror rate is 1.19%. The value of á is 1 x 10
MNIST
Average
0.1-quantile 0.3-quantile
Median
0.7-quantile
0.9-quantile
Non-private
0.850
0.362
0.467
0.626
0.931
1.840
E 0.1
0.852
0.361
0.469
0.628
0.935
1.742
Table 4: Populational statistics of individual privacy parameters on CIFAR-10. The average estimation
emoor rate is 1.51%. The value of 5 is 1 x 10
CIFAR-10 10
Average
0.1-quantile 0.3-quantile
Median
0.7-quantile
0.9-quantile
Non-private
5.813
2.870
4.957
6.602
7.290
7.488
8 = 0.1
5.811
2.960
4.975
6.609
7.357
7.828
T = {a E A: (a, d,) EB}. Because f is bijective function, we have
Pr (A()) d:) E E = Pr [A(D) T)
(8)
S E Pr [A('') E T + c. Prif (A(D'), d,) +
(9)
(10)
which completes the proof.
E.2 RELEASE POPULATIONAL. STATISTICS OF PRIVACY PARAMETERS
The individual privacy parameters computed by Algorithm are sensitive and hence can not be directly released the public. Here we show the populational statistics individual parameters can be released with minor privacy cost. Specifically, with differential privacy. For average, we release the noisy aggregation through Gaussian Mechanism. For quantiles, solve the objective function in Andrew et al. (202) with 20 steps of full batch gradient descent. The results on MNIST and CIFAR-10 10 are Table 3 and Table 4 respectively. The released statistics close to the actual values on both datasets with (0.1, 10 10-3)-1110 DDD.
compute the average and quantiles of the values
18


Reviews:
[{"review_id": "whn1uh9hN8g", "reviewer": "Reviewer_9tdY", "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": "\nThe paper studies \"individual differential privacy\", i.e., given a specific example x, to what extent can one determine the membership (in a dataset D) of that example x given the output of a given algorithm?\n\n", "summary_of_the_review": "\nThe paper is interesting and with some more effort can be made sufficiently clear.", "strength_and_weaknesses": "\nThe idea is interesting, it allows to evaluate to what extent an individual suffered privacy loss due to the publication of a learnt model.\n\nThe paper could be made clearer (avoiding ambiguity among others by using symbols in addition to text when confusion is possible) and more self-contained (reviewing briefly already existing concepts).\n\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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "uy-dBoukIQ", "reviewer": "Reviewer_JYd4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper presents an algorithm to accurately account for individual differential privacy guarantees in DPSGD. ", "summary_of_the_review": "This paper provides an algorithm for individual privacy analysis in DPSGD. However, the proposed algorithm does not correctly analyze the individual privacy as defined in their paper. In addition, the techniques proposed are straightforward. Furthermore, no ground truth is given.\n", "strength_and_weaknesses": "Strength: Compared with worst-case DP guarantees, the individual DP guarantee of a sample allows us to better understand the privacy guarantee of a specific data sample, and its impact over model parameters.\n\nWeaknesses: \n\nW1. The proposed algorithm does not correctly estimate individual-level privacy as in Definitions 1 and 2. Hence, the claimed contribution is not justified and the impact of this paper is questionable. \n\n(1) The proposed algorithm modifies the underlying DPSGD algorithm for training. In particular, the algorithm modifies clipping norms for individuals, whereas the original DPSGD clips all gradient samples using the same constant. This change would affect the privacy analysis in DPSGD, and hence, it is unclear whether the algorithm could still correctly estimate the individual privacy guarantee. \n\n(2) The authors claim that their techniques are used for the output-specific individual privacy of DPSGD. Hence, we expect the algorithm to take the output of DPSGD as the input, which is the noisy gradient sum.  However, in the proposed algorithm, only the DP estimates for individual clipping norms (which, again, is not a component of the original DPSGD) are taken into account. It is unclear how the noisy gradient sums in multiple iterations, as the ``trajectory`` of output, impact the output of the algorithm. \n\n(3) No ground truth about individual privacy is provided. Hence, it is confusing how the paper evaluates the accuracy/correctness of the proposed algorithm. \n\nW2. The proposed techniques are straightforward.\n\n(1) The claim that subsampling in DPSGD complicates the privacy analysis is not well justified. The worst-case privacy analysis of DPSGD already incorporates subsampling, as shown in the following papers: \"Rényi Differential Privacy of the Sampled Gaussian Mechanism\" by Zhang et al., and \"Subsampled Rényi Differential Privacy and Analytical Moments Accountant\" by Wang et al. Thus, it is why subsampling brings a challenge in the analysis of individual DP.\n\n(2) Overall, the algorithm simply computes the Rényi divergence based on different clipping norms, which is merely an application of existing analysis.\n\n(3) The computation cost of N (which is the size of the private dataset) does not seem to be a problem for individual privacy accounting by definition, since otherwise you would miss some data samples and the accounting is not individual-level anymore (instead it is group level).\n\n(4) The technique for reducing the computation cost is to simply group data samples by their estimates of clipping norms at each iteration. This technique is straightforward. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "NKd8qRVDru", "reviewer": "Reviewer_rPUG", "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 authors provide an efficient algorithm for individual privacy accounting when using DP-SGD. By checking the individual privacy parameters, the authors find that these parameters are highly correlated to individual training loss. The authors also verify the validity of their individual privacy parameters by the results of membership inference attacks.", "summary_of_the_review": "This paper is novel in terms of finding a correlation between training loss and individual privacy. Although without any theoretical analysis of this phenomenon, this paper provides various experimental results to support their finding. \n\n---\n After discussion with Area Chair and other reviewers \n\n---\nIt would be great if the authors could explain directly how Definition 2 is used in considering the privacy guarantee for a group. Currently, there is a lack of evidence why Definition 2 and Theorem 3.1 is necessary for Section 5, which is the highlight of this paper.\n", "strength_and_weaknesses": "Major strengths:\n1. This is the first result showing the correlation between individual training loss and individual privacy parameters. Although this idea is natural if we consider the influence of the data points in the tail of the data distribution on both loss and privacy guarantee, it is great to see such a detailed experimental analysis.\n\nMinor strengths:\n1. This paper is easy to follow.\n2. The visualization of the experimental results is good.\n\nMajor weaknesses:\n1. I see that the authors are aware of the work by Feldman and Zenic (2021) on the Renyi Filter. It is not explained in this paper why they choose to use the concept by Redberg and Wang (2021) instead. (The authors are not giving enough acknowledgment to Redberg and Wang (2021) in their Definitions 1 and 2.)\n2. There is no theoretical result on the underlying reason behind this correlation between training loss and privacy parameters.\n3. In Section 6, the correlation between the attack success rate and the average $\\varepsilon$ is from the non-private model. This does not support the relationship between the individual privacy parameters and the actual privacy risk. This part of the experiment needs to be removed or replaced.\n\nMinor weaknesses:\n1. In Figure 4, I do not understand why the Pearson correlation coefficient is not calculated with the original points but with the fitted curve.\n2. Algorithm 1 needs to be revised. I think $q$ should be $p$ which is the sampling ratio for each batch. The authors have not defined $I_j$, and I guess $m$ is the batch size.\n3. In Section 3.4, the authors propose to release $\\varepsilon_i$ to the owner of the $i$th example. I think there needs a theoretical proof of why this does not incur additional privacy loss. I think the calculation of $\\varepsilon_i$ depends on the differentially private model which depends on the other examples. Therefore, we should be careful about what has been released and how much of the privacy budget has been used up.\n4. The usage of individual clipping is discussed in Section C but I do not think this is a common practice. If we do not adopt this individual clipping but only global clipping, will the result still show the correlation between loss and privacy as strong as it is now?\n\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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject