Differentially Private Empirical Risk Minimization under the Fairness Lens
Authors: Cuong Tran
My H Dinh
Ferdinando Fioretto
Venue: NeurIPS 2021 Poster (2021)
Keywords: Differential Privacy
Empirical Risk Minimization
Fairness

Abstract: Differential Privacy (DP) is an important privacy-enhancing technology for private machine learning systems. It allows to measure and bound the risk associated with an individual participation in a computation. However, it was recently observed that DP learning systems may exacerbate bias and unfairness for different groups of individuals. This paper builds on these important observations and sheds light on the causes of the disparate impacts arising in the problem of differentially private empirical risk minimization. It focuses on the accuracy disparity arising among groups of individuals in two well-studied DP learning methods: output perturbation and differentially private stochastic gradient descent. The paper analyzes which data and model properties are responsible for the disproportionate impacts, why these aspects are affecting different groups disproportionately, and proposes guidelines to mitigate these effects. The proposed approach is evaluated on several datasets and settings.

Differentially Private Empirical Risk Minimization under the Fairness Lens
Cuong Tran Syracuse University ctran@syr. edu
My H. Dinh Syracuse University mydinh@syr.co edu
Ferdinando Fioretto Syracuse University ffiorett@syr. edu
Abstract
Differential Privacy (DP) [4] is an important privacy-enhancing technology for private machine learning systems. It allows to measure and bound the risk associ- ated with an individual participation observed that DP learning systems may exacerbate bias and unfairness for different This paper builds on these important observa- tions and sheds light the causes of the disparate impacts arising in the problem differentially private empirical risk minimization. disparity arising among groups of individuals in two well-studied DP learning methods: output perturbation [[]] and differentially private stochastic gradient descent 22. The paper analyzes which data and model properties are responsible for the disproportionate impacts, why these aspects are affecting different groups disproportionnaelly and proposes guidelines to mitigate these effects. The proposed approach is evaluated on several datasets and settings.
computation. However, it was recently
groups of individuals 3 27 23
focuses on the accuracy
Introduction
While learning systems have become instrumental for many decisions and policy operations involving individuals, the use of rich datasets combined with the adoption black-box algorithms has sparked concerns about how these systems operate. Two key concerns regard how these systems handle discrimination and how much information they leak about the individuals whose data is used as input.
Differential Privacy (DP) 114 has become the paradigm of choice for protecting data privacy and its deployments are growing at fast rate. DP is appealing as bounds the risks of disclosing sensitive information of individuals participating in computation. However, it recently observed that DP systems may induce biased and unfair outcomes for different groups of individuals B 23 27]. The resulting outcomes have significant societal and economic impacts the involved individuals: classification errors may penalize some groups over others in important determinations including criminal assessment, landing, and hiring [3]
result in disparities regarding the allocation of critical funds, benefits, and therapeutics 23 While these surprising observations have become apparent in several contexts, their causes largely understudied and fully understood.
This paper makes step toward addressing this important knowledge gap. It builds on these key observations and sheds light the causes of the disparate impacts arising in the problem of dif- ferentially private empirical risk minimization (ERM). focuses on the accuracy disparity arising among groups of individuals in two well-studied DP learning methods: output perturbation [I]] and differentially private stochastic gradient descent (DP-SGD) (2]. The paper analyzes which properties of the model and the data are responsible for the disproportionate impacts, why these aspects affecting different groups disproportionately, and proposes guidelines to mitigate these effects.
In summary, the paper makes the following contributions:
1. It develops a notion of fairness under private training that relies on the concept of excessive risk.
35th Conference on Neural Information Processing Systems (NcurIPS 2021)

---

2. It analyzes this faimess notion in two DP learning methods: output perturbation and DP-SGD.
3. It isolates the relevant components related with noise addition and gradient clipping responsible for the disparate impacts.
4. It studies the behaviors and the causes for these components to affect different groups of individuals disproportionately during private training.
Based on these observations, it proposes mitigation solution and evaluates its effectiveness on several standard datasets.
To the best of the authors knowledge, this work represents a first step toward deeper understanding of the causes of the unfairness impacts in differentially private learning.
2 Related work
The research at the interface between differential privacy and fairness is receiving increasing attention and can be broadly categorized into three main lines of work. The first shows that DP is in alignment with fairness. Notable contribution in this direction include Dwork et al. [IS] seminal work, which highlights the relation between individual fairness and differential privacy, and Khalili et al. [1)), which shows that the private exponential mechanism can produce fair outcomes in some selection problems. Works in the second category study the setting under which a fair model can leak privacy [22
25 28). These works propose learning frameworks that guarantee DP while also encouraging the satisfaction of different notions of fairness. For example, Xu et al. [27] proposes private and fair variant of DP-SGD that uses separate clipping bounds for each groups of individuals. Such proposal encourages accuracy parity at the expense of an extra privacy cost (required customize the clipping bound for each group). Works in the last category show that
18
9
private mechanisms can have negative impact towards fairness [23 27 3 17 25 For example, Cummings et al. [13] shows that it is impossible achieve exact equalized odds while also satisfying
pure DP. Pujol et al. [23] observe that decisions made using private version of a dataset may disproportionately affect some groups over others. Similar observations were also made the context of model learning. Bagdasaryan et al. 33 empirically observed that the accuracy of DP model trained using DP-SGD drops disproportionately across groups causing larger negative impacts the underrepresented groups. Farrand et al. [17] reaches similar conclusions. The authors empirically show that the disparate impact of differential privacy on model accuracy is not limited to highly imbalanced data and can occur even in situations where the classes are slightly imbalanced.
This paper builds on this body of work and their important empirical observations. It derives the conditions and studies the causes of unfairness in the context of private empirical risk minimization problems well introduces mitigating guidelines.
Preliminaries
Differential privacy (DP) 14 is a strong privacy notion used to quantify and bound the privacy loss of individual participation a computation. Informally, it states that the probability of any output does not change much when record is added or removed from a dataset, limiting the amount of information that the output reveals about any individual. The action of adding or removing a record from a dataset D, resulting in new dataset D', defines the notion of adjacency, denoted D ~ D'.
Definition 1. A mechanism M:D-R with domain D and range R is (e, o)ddiferrnntiall private, if. for any two adjacent inputs D ~ D' ED, and any subset of output responses R S R:
Pr(M(D) E RJ S e Pr[M(D') E R] +
Parameter 0 describes the privacy loss of the algorithm, with values close 0 denoting strong privacy, while parameter d E [0, 1) captures the probability of failure of the algorithm to satisfy c-DP. The global sensitivity A of real-valued function é D - IR is defined the maximum amount by which l changes in two adjacent inputs: A₁ = maxp-nr [I((D) - ((D) In particular, the Gaussian mechanism, defined by M(D) ((D) NOO,, A3 o²), where NO0 A? a²)) is the Gaussian distribution
with mean and standard deviation A; o satisfies (c, 5)-DP for 8> exp(<(orc)) /2) and << [16].

---

4 Problem settings and goals
The paper adopts boldface symbols to describe vectors (lowercase) and matrices (uppercase). Italic symbols are used to denote scalars (lowercase) and data features random variables (uppercase). Notation ||-I| is used to denote the L2 norm. The paper considers datasets D consisting of n individuals' data points (X,, Y),, with EE [n] drawn i..d. from unknown distribution. Therein, X; X is feature vector, A, A is a protected group attribute, and Y; e is a label. For example, consider the case of classifier that needs to predict the risks associated with lending decision. The training example features X; may describe the individual's demographics, education, credit score, and loan amount, the protected attribute A, may describe the individual gender or ethnicity, and Y, represents whether or not the individual will default on the loan. The goal is to learn a classifier fe : X y, where is vector of real-valued parameters, that guarantees the privacy of each individual data (X, A,, Y, in D. The model quality is measured in terms of a nonnegative loss function f: y x R.,, and the problem is that of minimizing the empirical risk (ERM) function:
min L(0: D) - Σ (Vo(())) Yi). 1=1
(L)
For a group a E A. the paper uses D2 to denote the subset of D containing exclusively samples whose group attribute A = a. The paper focuses on learning classifiers that protect the disclosure of the individuals' data using the notion of differential privacy and analyzes the fairnsss impact (as defined next) of privacy on different groups of individuals. Importantly, the paper assumes that the attribute A is not part of the model input during inference.
Fairness The fairness analysis focuses on the notion of excessive risk, a widely adopted metric in private learning 26 29 It defines the difference between the private and non private risk functions:
R(O, D) = Eg [(): m) L(0";
where the expectation is defined over the randomness of the private mechanism and 0 denotes the private model parameters while 0" = argming L(0; D). The paper uses shorthands R(O) and (0) to denote, respectively, the population-level R(O, D) excessive risk and the group level R(O, Da) excessive risk for group a. Fairness is measured with respect to the excessive risk gap:
E.
-
(Pure) fairness is achieved when &. 0 for all groups A and, thus, private and fair classifier aims at minimizing the maximum excessive risk gap among all groups. The paper assumes that the private mechanisms are non-trivial, i.e., they minimize the population-level excessive risk R(O).
All proofs are reported in the Appendix, Section
5 Warm up: output perturbation
The paper starts with analyzing faimess under the DP setting induced by an output perturbation mechanism. In this setting the analysis restricts to twice differentiable and convex loss functions l. Output perturbation is a standard DP paradigm in which noise calibrated to the function sensitivity is added directly to the output of the computation. In the context of the regularized ERM problem, adding noise drawn from a Gaussian distribution (O, A30²2 to the optimal model parameters 0' ensures (e. 5) diffferrentaal privacy (II) Therein, A = 2/na with regularization parameter 2. The following result sheds light on the unfairness induced by this mechanism.
Theorem 1. Let E be twice differentiable and convex loss function and consider the output perturba- tion mechanism described above. Then, the excessive risk gap for group is approximated by:
1 Ea N30 (T(H))
where =V EoxAYeDD (X), Y) is the Hessian mutrix of the loss function, at the optimal parameters vector 0¹, computed using the group data Da, He is the analogous Hessian computed using the population data D, and Tr(.) denotes the trace of matrix.
3

---

The approximation above follows form a second order Taylor expansion of the loss function, linearity of expectation, and the properties of Gaussian distributions. It uses that fact that the excessive risk (2) for group can be approximated as 1/2420² (r(A)TTT(((H)) HT) The proof is reported in Appendix A
Theorem T sheds light the relation between faimess and the difference in the local curvatures of the losses l associated with a group and the population and provides a necessary condition to guarantee pure fairness. It suggests that output perturbation mechanisms may introduce unfairness when the local curvatures associated with the loss function of different groups differ substantially from one another. Additionally, the unfairness level is proportional the amount of noise or or, equivalently, inversely proportional to the privacy parameter e, for fixed 6. Finally, it also suggests that groups with larger Hessian traces Tr Tr(H)) will have larger excessive risk compared to groups with smaller Hessian traces. An additional analysis on the reasons behind why different groups may have large differences in their associated Hessian traces is provided in Section g
The plots show the correlation between the excessive risk [ riskBand and the quantity Tr(H)) for each group z E A, at varying of the privacy loss E 10.005,0.5) 0 = le on two datasets. Each data point represents the average of 100 runs of a DP Logistic Regression (obtained with output perturbation) on each group z E A. Details on dataset and experimental setting are provided in Appendix B and additional experiments in Appendix [ Note the positive correlation between the excessive risk and the
Figure | illustrates Theorem T
Abalone
Churn
0
Tr0*" - 00.9
Trje*) - 10.0
ToooP) -13
Tr/+*)-285 -8.5
Excesdive Risk
0.15
0.10
0.2
0.05
0.00
0.0
10
10
10
10y
E
Correlation between excessive risk and Hessian Traces at varying of the privacy loss e.
Figure 1:
Hessian trace: Groups with larger Iesssinn traces tend to have larger excessive risks. Note also the inverse correlation between and the dependency between the excessive risk and the Hessian trace. This is due to that larger values require smaller or values, and thus, as shown in Equation 3 the dependency between the excessive risk and Hessian trace is attenuated.
The following illustrates that even a class of simple linear models may not to satisfy pure faimess.
Corollary 1. Consider the ERM problem for a linear model fo(X) def 0_x, with La loss function i.e.. p fairness.
((f(X),Y) y)= (oo(X)-))- Then, output perturbation does not guarantee pure
It follows from the observation that the Hessian of the L2 loss for group a E A. i.c., Tr(H)) Ex-D, Tr(XX")=Bx-n, this result highlights the relation between fairness and the average input norms of different group elements. When these norms are substantially different one another they will impact their respective excessive risks differently. An additional analysis on this behavior is also discussed in Section 7
IIXIP, -x,_ix, depends solely on the input norms of the elements in D.F Interestingly,
The following is a positive result.
Corollary 2. for any two groups a, b E A their average group norms Dx,_-,,1lxall = |xxbl have identical values, then output perturbation with La loss function provides pure fairness.
The above is direct consequence of Corollary I
Note also that pure fairness may be achieved, in this setting, by normalizing the input values for each group independently (as shown in Appendix C although this solution requires accessing the sensitive group attributes at inference time.
6 Gradient perturbation: DP-SGD
Having identified the dependency between the Hessian of the model loss and the privacy parameters with the excessive risk gap in output perturbation mechanisms, this section extends the analysis to the context of DP Stochastic Gradient Descent (DP-SGD) (2] In contrast to output perturbation, DP-SGD does not restrict focus on convex loss functions and the privacy analysis does not require optimality of the model parameters 0, rendering it an appealing framework for DP ERM problems.
In all experiment presented, the excessive risk is approximated by sampling over 100 repetitions. Throughout the paper, we abuse notation and treat the dataset Dy associated with group Z as distributions.

---

In a nutshell, DP-SGD computes the gra- dients for each data sample in random mini-batch B, clips their L2-norm, adds noise to ensure privacy, and computes the average. Two key characteristics of DP- SGD are: (1) Clipping the gradients whose La norm exceeds given bound C, and (2) Perturbing the averaged clipped gradients with O-mean Gaussian noise with variance C'C². The procedure is described Algo-
Algorithm 1: DP-SGD
input: Disjoint dataset D Sample prob. q; Iterations T; Noise variance σ²; Clipping bound C; learning rate 1)
6, + 0"
for iteration 1 = 1.2..... T do
< random sub-sample of D with Prq foreach (X, Y) B do
9. (X), Y.)
9D (E)ec(g)) ((O,
r Therein, 9; represents the gradient of data sample (X,, A, V;), In the average clipped noisy gradient of the samples in mini-batch B, and the function xc(x:) min(1, [
0,1 - 0, - ngs
The following theorem is an important result of this section. It connects the expected loss B[ D.)] of a group a A with its excessive risk (0), which is, turn, used in our fairness analysis. decomposes the expected loss during private training into three key components: The first relates with the model parameters update and it is not affected by the private training. The other two relate with gradient clipping and noise addition, and, combined, capture the notion of excessive risk.
Theorem 2. Consider the ERM problem (L) with loss & twice differentiable w.et. the model parame- ters. The expected loss B[ D.)l of group ae A at iteration I+ 1, is approximated as:
B [[[(0,11; D.)l (.); (9.., 9D) + o 2
9h 9
(4)
non-private term
+ 17 (gD., - -(D,, + (B
-
H;
(R
2
private term due to clipping
L
2 Tr
(Racise)
private term due to noise
O(10,,1 0,11²,
where the expectation is taken over the randomness of the private noise and the mini-batch selection, and the terms gz and ğz denote, respectively. the average non-private and private gradients over subset Z of at iteration (the iteration number is dropped for ease of notation).
The result in Theorem 2 follows from a second order Taylor expansion of the non-private and private ERM functions _(O,- 1198; Da) and (', 17(@0 N(0. o D.), respectively, around 0, and by comparing their differences. Once again, proofs are reported in Appendix A
The first term in the expression (Equation 4 denotes the Taylor approximation of the (non (hon-private)
SGD loss. Terms R and ( quantify, together, the excessive risk for group Therein, R quantifies the effect of clipping to the excessive risk, and (Rnoke) quantifies the effect of perturbing the average gradients to the excessive risk. Therefore, Theorem shows that there are two main sources of disparate impact in DP-SGD training:
1. Gradient clipping (RE which, in turn, depends of three factors: (i) The values of the Hessian matrix H of the loss function associated with group a; (ii) The gradients values 9p, associated with the samples of group a: and (iii) The clipping bound C, which appears in gn and gn-
2. Noise addition (Rmoise): which, in turn, depends on two factors: (i) The values of the (trace of the) Hessian matrix H. of the loss function associated with group a; and (ii) The privacy loss parameters (e, 5, Ae) (which, in turn, are characterized by the noise variance C2
schematic representation of these factors is shown Figure Therein, Xp, denotes the features values X X of the subset D, of D. Theorem entails that unfairness occurs whenever different groups have different values for any of the gradient clipping and noise addition excessive risk terms.
The next sections analyze the reasons behind the disparity in excessive risk focusing, independently, on terms Relip (Section 7 and Rhoise (Section 8) Independently studying these terms is motivated by
5

---

Closeness decision boundary
Hessian loss
H
ExwXDo
(x)(
Excessive Risk for group Rs
Inpur values
D.
Gradionts
Input values
X
9v.,
R
Hossian
H
Clipping bound
Clipping bound and noise multiplier
C'
Rnolse
Privacy parameters
(f. 6, A,) ---- (C,o)
Figure 2: Diagram of the factors affecting the excessive risk R for group a of individuals. Components affecting Rg output perturbation involve exclusively green boxes while those affecting R, DP-SGD involve both green and blue boxes. The main direct factors (e.g.. those appearing in Eq. (4) affecting the excessive risk clipping R." and noise Ra components are highlighted within colored boxes. These direct factors are also regulated by latent factors, shown in white boxes, with dotted lines illustrating dependencies.
observation that the clipping value C regulates the dominance of a factor over the other. Indeed, for sufficiently large (small) C values Rpoise will dominate (be dominated by) Relip) 3
7 Why gradient clipping causes unfairness?
As highlighted above, there are three factors influencing the clipping effect to the excessive risk R: the Hessian loss, the gradient values, and the clipping bound. This section illustrates their dependencies with the excessive risk, provides conditions to compare the disparate impacts between different groups, and shows the presence of an extra (latent) factor: the norm of the input values Xp. which plays role to this disparate impacts by indirectly controlling the norms of gradient gD, (see the diagram illustrated in Figure 2
The next results assume that the empirical loss function L(0; Da), associated with each group a E A, is convex and Bm-smooth. The analysis also consider learning rates S 1/max,8, and gradients gBB and g(B) with small variances. Note that this is not restrictive the variance decreases as function of the batch size B. Finally, for notational convenience, and w.l.o.g., the result focus on the case in which [A] 2. As shown in the empirical assessment (see Appendix C). however, the conclusions carry on even in cases when the above assumptions may not hold.
Group
Group b
Theorem 3. Let Pt = IP///i be the fraction of training samples in group E A. For groups b A. Relip Relip whenever:
C-0.001
Grad Norm
1.00
C-0.1-4
0.75
P2 |9
c+ 11t1o.1ll 2 ==2
+
P 2
(5)
C-0.001
0=0.1
0.00
Theorem 3 provides sufficient condition for which group may have larger excessive risk than another solely based on the clipping term analysis. It relates unfairness with the average (non-private) gradient norms of the groups go, and gn, and the clipping value C. As shown in the diagram of Figure 2 this result relates two main factors to the excessive risk due to clipping " (1) the clipping bound C, and (2) the (norm of the) gradients llgp,ll- While the relative dataset size Pa = DD.//xx of each group also appears in Equation (5). our extensive experiments showed that this factor may not play prime role in controlling the disparate impacts (see Appendix[]] C
Excessive Risk
C-0.001
1.0-
C-0.001
C-0.1
0.5
C-5
0.0
G-5
150
Iterations
Figure 3: Impact of gradient clipping gradient norms for different clipping bounds. Bank dataset.
The relation with these two factors illustrated in Figure 3 which shows the impact of gradient
clipping (for different C values) the gradient norms (top) and to the excessive risk R, (bottom).
'This observation relates with the bias- variance trade-off typically observed in SGD 25

---

shows that the gradient norms reduce as C. increases and that the group with larger gradient norms have also larger excessive risk.
Finally, the diagram in Figure 2 also shows the presence of an additional factor affecting the gradient norms: the imput norms, whose average is denoted Xp, = Ex-xx, [|X]], in the figure. While this aspect is not directly evident in Theorem 3 the following examples highlight the positive correlation between input and gradients norms when considering a linear classifier and a feedforward neural network.
Example 1. Consider the ERM problem LL) for a linear classifier fo(X) def softmax(O" (f X) and cross-entropy loss (X) - Σ Y, log f (X) where K is the number of classes. The gradient of the loss function at a given data point (X. Y) is: 9x VOE(fo(X), Y) (Y f) @ X. The result is by 7 and it suggests that the gradient norms are proportional the input norms: llgxll o [IX]].
Example 2. Next, consider a neural network with single hidden loyer, fo(X) def softmax (f) o0 x)). where of)) is a proper activation function and 0,, O2 are the model parameters. can be seen that l|gxll oc IIV (X),(X), 1I ([Ve,(fo(X), Y)I. where Vo,((a(()) Y)ll æ ||X||_ The full derivations are
reported in Appendix D
Bank
0.6
Both examples illustrate correlation between the gradients norms llgx|l and input norms ||X]] for a given data sample X. 0.4
Correlation
This behavior is also illustrated in Figure which highlights a positive correlation between the individual inputs and the gradients norms obtained while privately training simple neural network (with one hidden layer) using DP-SGD on the Bank dataset. The experiment use C 0.1 and = 1. The correlation decreases during training since the gradients norms reduce as training advances.
0.0
30
Iterations
Figure 4: Correlation between inputs and gradients norms.
These observations imply that group data with large input norms- norms-typicnn -tynicalyyyylyy defining the tail of data Distribution-resti in large gradient norms and, thus, as shown Theorem 3 may have larger disproportionate impucts than groups with smaller inpul norms, under DP-SGD. This analysis is in alignment with the empirical observation raised in [3] showing that samples at the tail of a distribution may experience larger accuracy losses, in private training, with respect to other samples.
While the above shows dependency between gradients and clipping bound, illustrated in the ( equation, the group excessive risk also affected by the Hessian values. However, as shown in Appendix C the Hessian factor is almost always dominated by the other factors examined in this section. This is due to the presence of the multiplier r//2 which attenuate the impact of the Hcssian value to the excessive risk due to clipping in conjunction with the smoothness assumptions, which prevents the Hessian values to grow too large.
In summary, the main factors affecting Re for group a E A are the norm of the group gradients gD. in turn controlled by the norm of the inputs XD,, and the clipping bound C.
8 Why noise addition causes unfairness?
Next, the paper analyzes the factors influencing the noise effect to the excessive risk Ruoise, which, as highlighted in Theorem [ for DP-SGD and Theorem for output perturbation,
the Hessian loss, and the privacy loss parameters (E, ô, A²) (see also Figure Noting that the privacy parameters have multiplicative effect on the Hessian loss (see Equations (R and (3), the following analysis, treats them as constants, and restricts focus on the effects of the Hessian trace to the disparate impacts.
The following result provide condition to compare the disparate impacts between different groups,
Theorem 4. For groups a, b E A, Ruoise > Rnoise whenever
TY(H;) Tr(H))
Note the connection of the result above with Theorem I Additionally, as illustrated in the diagram of Figure Hessian trace for a group is controlled by two (latent) factors: (1) The average distance of the group data to the decision boundary, and (2) The values of the group input norms. While
7

---

Bank
Abalone
Stroke
0.4
Correlatoon
0.3
0.2
0.1
0
0
0
Figure 6: Correlation between input norms and excessive risk; DP-SGD with C 0.1 and o 1.0.
these aspects are not directly evident in Theorem 4 the following highlights the positive correlation between these two factors and the Hessian Traces.
Example 3. Consider the same setting of Example 7 The Hessian of the cross entropy loss of a sample X ~ D is given by H! [[dia(()) f @ XX" where @ is the Kronecker product f7y. This result suggests that the trace of the Hessian for sample is proportional to its input norm: Tr(H,) ||II Additionally it also shows that: Tr(H)) (1 Σ (X)), where K is the number of classes, whose term is connected to the distance the decision boundary, as shown next.
The following result highlights the connection between the term (1 (1-E (X) and the distance of sample X to the decision boundary.
(X))
Theorem 5. Consider a K-class classifier fox (k E [K]). For a given sample D, the term (1 Σ (x)) is maximized when fax(X)= = 1/K and minimized when 3k & [K] s.t. fax(X) = and fex = 0 VK E [K],k k. k.
That is, the term EI (X) is maximized (minimized) when the sample X is close (far) the decision boundary. Since, shown in Example this term be proportional to the Hessian trace, then the aforementioned relation also indicates a connection between the Hessian trace value for sample and its distance the decision boundary: The closest (farther) is sam- ple X to the decision boundary the larger (smaller) is the associated Hessian trace value Tr(H,)) This is intuitive as the model decision are less robust the presence of noise in the model (e.g., as that introduced by DP mechanism) for the samples which are close the decision boundary w.r.t. those which are far from it.
0.75
0.50
Correlation
0.25
An analogous behavior is also observed in Neural Networks and described Oopendix[Djdue to space constraints. Figure iillusttsss this behavior using the same setting adopted in Figure 4 It highlights the positive correlation between the input norm, the trace of Hessian, and the closeness the decision boundary for a given sample X.
-0.25
Tr( boundary
TriH() vs. [X]
00.50
Iterations
Figure 5: Correlation between trace of Hessian with closeness boundary (dark color) and input norm (light color).
While the above discusses the relation between input norms and Hessian losses, Figure 6 illustrates this dependencies with the excessive risk, which is one of the main objective of the analysis, three datasets. Once again this observation recognizes the difference in input norms as a crucial proxy to unfairness: Groups with larger input norms will tend have larger disproportionate impacts under private training than groups with smaller imput norms.
In summary, the main factor affecting Ruuise for group A is the Hessian loss H. which, in turn, controlled by the group's ss distance to the decision boundary and by their inputs norm.
Mitigation solution
The previous sections showed that, in DP-SGD, the excessive risk R, for group a E could be decomposed into two factors Relipp due to clipping, and Roolse due to noise addition. In turn, identified the gradients values gn, associated with the samples of group and the clipping bound C

---

- 02
1,
Y1 0.
1. =1
Excersive Risk
0.4
0.3
0.2
0.1
0.00
0.25
0.50
0.75
0.00
0.25
0,50
0.75
0.00
0.25
0.50
0.75
0.00
0.25
0.50
0.75
E
Figure 7: Mitigating solution: Excessive risk gap varying of the privacy loss on the Bank dataset for different values of y1 and y2. Majority (minority) group shown in dark (light) colors.
as the main sources of disparate impact in component Re and the (trace of the) Hessian H. of the group loss function as the main source of disparate impact in component Ramie
solution mitigate the effects of these components to the excessive risk gap is equalize the factors responsible for Relip and Rnoise among all group e A during private training. The resulting empirical risk loss becomes:
min L(O; D) 0
E(n Kgn, 9b.9n go)l + + (T(TT((HH)) -TT(HH)))H())))))))))))))))) GEA
Tr(H))).
(6)
where the component multiplied by y1 comes for simplifying the expression (gD,, ) (gD, gD) (go. gn) (go. ýD) associated the empirical risk gap & of the main factor affecting Rehp and component multiplied by y2 by the analogous expression for the main factor affecting Ruoise, Note that this last component involves computing the Hessian matrices of the loss functions during each training step, which is computationally expensive process. The previous section, however, showed strong dependency between the trace of the Hessian losses and the distance the decision boundary the proposed mitigating solution solves:
(Theorem 5). Thus, in place of Equation (6)
Σ Er Crrks Kgb. 9D. go go)l Bx-D, 11- 6EA7
(x) Bx- 11- Σ C
min L(0; D)
Figure fillustrates this approach work, for various multipliers Y1 and y2 the Bank dataset with two protected group (blue = majority; orange = minority). Similar trends are shown for other datasets well in Appendix C The implementation uses neural network with single hidden layer and Suppose uses DP-SGD with C = 0.1, o = 5.0. A clear trend arises: For appropriately selected values yi and y2 the excessive risk gap between the majority and minority groups not only tends to be equalized, but it also decreases significantly for both groups. These results imply that the proposed mitigating strategy may not only improve fairess but also the loss in utility of the private models.
10 Limitations and conclusions
This work was motivated by the recent observations regarding the disparate impacts induced by DP in learning systems. The paper introduced notion of fairness that relies the concept of excessive risk, analyzed this fairness notion in output perturbation and DP-SGD for ERM problems, it isolated the relevant components related with noise addition and gradient clipping responsible for the disparate impacts, studied the main factors affecting these components, and introduced a mitigation solution.
This study recognizes the following limitations: Firstly, the analyses in Section 7 requires the ERM losses to be smooth and convex. While these are common assumptions adopted in the analysis of private ERM [29 [10,, the generalization to the non-convex case is interesting open question. The second limitation regards the selection of the multipliers yı and y2 in Equation 6 While the paper does not investigate how to optimally selecting these values, the adoption of Lagrangian Dual framework, as in (25). could useful tool to the automatic selection of such parameters, for an extra privacy cost. Finally, the proposed mitigation solution negatively affects the training runtime and the design of more efficient solutions and implementations is an interesting challenge.
Despite these limitations, given the increasingly key role of differential privacy in machine learning, we believe that this work may represent an important and broadly useful step toward understanding the roots of the disparate impacts observed in differentially private learning systems.

---

Acknowledgments and Disclosure of Funding
This research is partially supported by NSF grant 2133169, Its views and conclusions are those of the authors only.
References
[1] Healthcare dataset stroke data.
URL http://www..aglke...co//eeessss
[2] M. Abadi, A. Chu, I. Goodfellow, McMahan, Mironov, K. Talwar, and L. Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pages 308-318, 2016.
[3] E. Bagdasaryan, O. Poursaeed, and Shmatikov. Differential privacy has disparate impact on model accuracy. In Advances in Neural Information Processing Systems, pages 15479-15488, 2019.
[4] B. Balle and Y.-X. Wang. Improving the gaussian mechanism for differential privacy: Analytical calibration and optimal denoising. In International Conference on Machine Learning, pages 394-403. PMLR, 2018.
[5] C. Bishop. Exact calculation of the hessian matrix for the multilayer perceptron, 1992.
[6] C. Blake and C. Merz. Uci repository of machine learning databases, 1988. URL https 1/archive.ics ics. uci /uci.edu/ll/dataaetsss php)
[7] D. Böhning. Multinomial logistic regression algorithm. Annals of the institute of Statistical Mathematics, 44(1 11197)))))0)) 1992.
[8] F. Carcillo, Y.-A. Le Borgne, O. Caelen, Y. Kessaci. F. Oblé, and G. Bontempi. Combining unsupervised and supervised learning in credit card fraud detection, 05 2019.
[9] H. Chang and R. Shokri. On the privacy risks of algorithmic fairness. arXiv preprint arXiv:2011.03731 2020.
[10] K. Chaudhuri, C. Monteleoni, and A. D. Sarwate. Differentially private empirical risk mini- mization. Journal of Machine Learning Research, 2011.
[11] K. Chaudhuri, Monteleoni, and A. D. Sarwate. Differentially private empirical risk mini- mization. Journal of Machine Learning Research, 12(3), 2011.
[12] I. A. Communities.
Telco customer churn dataset, 2015.
URL
http:/ //www ibm. www.commuciiiccocommmmmmcmmmmice sewiictieeiinsighhte. theeess-----teeeeel---oooooo customer--eooo churn data- dwt.aaaannnntaeeeeaaaaaaaaaaaaee
communi ties/ /ls////allyalliissstttttoooooo- aat.ttssonnaaallliiclllllooooooo
[13] R. Cummings, V. Gupta, D. Kimpara, and J. Morgenstern. On the compatibility of privacy and fairness. In Adjunct Publication of the 27th Conference on User Modeling, Adaptation and Personalization, pages 309-315, 2019.
[14] C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pages 265-284, Springer, 2006.
[15] C. Dwork, M. Hardt, T. Pitassi, O. Reingold, and R. Zemel. Faimess through awareness. In Proceedings of the 3rd innovations in theoretical computer science conference, pages 214-226, 2012.
[16] C. Dwork, A. Roth, al. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 1:::44:-1144411 2014.
[17] T. Farrand, F. Mireshghallah, S. Singh, and A. Trask. Neither private nor fair: Impact of data imbalance on utility and faimess in differential privacy. In Proceedings of the 2020 Workshop on Privacy-Prrservvng Machine Learning in Practice, pages 15-19, 2020.
[18] M. Jagielski, Kearns, Mao, A. Oprea, Roth, S. Shariff-Malvajerdi, and J. Ullman. Differentially private fair learning. In International Conference Machine Learning, pages 3000-3008, PMLR, 2019.
[19] M. M. Khalili, X. Zhang, M. Abroshan, and Sojoudi. Improving fairness and privacy in selection problems. In Thirty-Fifth AAAI Conference on Artificial Intelligence, 2021.
10

---

[20] M. Little, P. Mcsharry. S. Roberts, D. Costello, and I. Moroz. Exploiting nonlinear recurrence and fractal scaling properties for voice disorder detection. Biomedical engineering online, 6:23, 02 2007. doi: 10.1 186/1 07775-9922---23
[21] S. Moro, P. Cortez, and P. Rita. A data-driven approach to predict the success of bank telemar- keting. Decis. Support Syst. 62:22-31, 2014.
[22] H. Mozannar, M. I. Ohannessian, and N. Srebro. Fair learning with private demographic data.
In Proceedings of the 37th International Conference on Machine Learning, 2020.
[23] D. Pujol, R. McKenna, Kuppam, M. Hay, A. Machanavajihala, and Miklau. Fair decision making using privacy-protected data. In Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency, pages 189-199, 2020.
[24] Sadowski. Lecture Notes: Notes Backpropagation, 2021. https:t http::///www..t wwtp://.ww...c..cc
eduu/ppjsadows/notes pdf) Last visited on 2021/05/01.
[25] C. Tran, Fioretto, and P. Hentenryck. Differentially private and fair deep learning: A lagrangian dual approach. In Thirty-Fifth AAAI Conference Artificial Intelligence, 2021.
[26] D. Wang, M. Ye, and J. Xu. Differentially private empirical risk minimization revisited: Faster and more general. In Advances Neural Information Processing Systems, 2017.
[27] D. Xu, W. Du, and X. Wu. Removing disparate impact of differentially private stochastic gradient descent on model accuracy, 2020.
[28] R. Xu, N. Baracaldo, Y. Zhou, A. Anwar, and H. Ludwig. Hybridalpha. Proceedings of the 12th ACM Workshop Artificial Intelligence and Security AlSec' 19, 2019. doi: 10.1145/3338501 3357371. URL. http://dds
wwt/orgg///0 10. 1145/3338501. 3357371
[29] Zhang, K. Zheng, W. Mou, and L.. Wang. Efficient private erm for smooth objectives. In Proceedings of the Twenty-Sixth International Joint Conference Artificial Intelligence, IJCAI-17, pages 3922-3928, 2017. doi: 10.24963/iccai.221//54. URL httph::////oo org//
10. 220224963/111 wtt.ca.......1100 2017/548


Reviews:
[{"review_id": "aBrzW-pT9Nc", "reviewer": "Reviewer_SVBW", "summary": "The goal of the paper is to study the disparate impact that differential privacy can have across different groups. The authors do so within an ERM framework, and aim to equalize (or minimize the difference in) the excessive risk across groups.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths: \n- the excessive risk gap is a natural fairness metric here: it measures how far each group is from its optimal outcome, and compares this excess error/risk across groups. Low excessive risk gap means that all groups are *additively* as close to the best model as each other.\n- It is nice that the results of the paper go beyond the classical understanding that different group sizes lead to different amount of noise added to the data, hence leading to disparate impact. \n- Some of the insights in the paper are interesting: for example, the authors were able to “show” that the unfairness level is proportional to the amount of noise added for privacy\n- The decomposition of Theorem 2 is really nice. It explicitly points out which part of the loss comes from the non-private loss, from clipping the gradients, and from the noise added for privacy.\n- The experiments of Figure 3 shed some interesting insights as to how the choice of gradient clipping affects fairness/excessive risk. \n\nWeaknesses:\ni) The major weakness of the paper is that the math is hand-wavy and not rigorous. The results of the authors are approximations, and are not complemented with confidence intervals or some understanding of the order of magnitude of the higher order terms that are being ignored. In turn, this weakens the theoretical insights of the paper.\nii) More minor, but some of the insights of the paper are a bit hard to understand: \n- Page 4 mentions the effect of the magnitude of Hessian traces on the excessive risk, but what does having a large Hessian trace means with respect to the data and the loss function? There are a few examples in the paper, but I am still having a hard time parsing what this means.\n- Theorem 3 gives a sufficient condition on the magnitude of the average non-private gradient norm of the groups and the clipping value to cause unfairness, but the average gradients is something that is hard to understand theoretically, making this condition hard to use.  \n\nQuestion:\nWhat happens when using different clipping values for different groups? Is it possible to intervene there to guarantee better fairness at the cost of possibly lower clipping values in some groups. This would also lead to lower sensitivity hence amount of noise to add to the gradients?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors acknowledge the limitations of their paper. In terms of societal impact, this paper is directly relevant as it aims to understand the social and disparate impact of differential privacy across groups.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3-4"}, "extra_text": {}}, {"review_id": "T6RlwiiXwuk", "reviewer": "Reviewer_K3eh", "summary": "The paper tries to solve the problem that ML models with DP tend to excerbate bias and unfairness. Particularly, it focuses on two well-studied DP algorithms: output perturbation and DP-SGD. The paper shows that the unfairness is caused by gradient clipping and noise addition. Based on the observations,  it further proposes a solution and its effectiveness has been tested experimentally. ", "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": "Originality:  The observations that both gradient clipping and noise addition cause unfairness, and the proposed mitigation solution are new and the related works are adequately cited. \n\nQuality:  Claims are well supported by theoretical analysis and the the analyses are used appropriate. The current work includes two well-known DP algorithms and their theoretical results, demonstrations are included; Hence it is complete. \n\nClarity: The submission is clearly written and well organized.\n\nSignificance: The developed notion of fairness is important and interesting and other researches are likely to use the concept to build the fairness of their methods in the future.  The work narrows the gap between the unfairness of ML models and differential privacy. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "1 Why does Theorem 2 only show a second-order Taylor expansion of the excessive risk for group a, rather than similar result showing in Theorem 1? Since the unfairness defined in line 107 is based on excessive risk gap $\\xi_a$, it is more meaningful and consistant to see the theoretical results with respect to $\\xi_a$ for DP-SGD in section 6.\n\n2  In Section 9, the paper proposes a mitigation solution with extra terms. So how to determin appropriate values for $\\gamma_1$ and $\\gamma_2$? How do different values of $\\gamma_1$ and $\\gamma_2$ affect the performance of original tasks, such as the MSE or prediction accuracy? \n\n3 Can authors explain more about the definition of  excessive risk in line 103 and how to calculate in practice, in terms of expectation?  Since the optimal solution $\\theta^*$ is not the optimal solution for the loss function w.r.t. data of group a. It can be negative values, right? But I see all excessive risk values in Figure 3 and Figure 7 are positive.  What's more, are values of excessive risk comparable among different groups? If not,  can authors explain why excessive risk is a good representation for fairness? ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "N/A"}, "extra_text": {}}, {"review_id": "P8NLpaiJP3N", "reviewer": "Reviewer_yKaM", "summary": "This paper investigates the underlying causes of the disparate impact produced by differentially private machine learning methods. To that end, the paper considers the notion of excessive risk gap, which measures the difference between the population-level and subgroup risks. The paper explores how two different differential privacy mechanisms (output perturbation and DP-SGD) affect the excessive risk gap. For output perturbation, the paper relates the excessive risk gap to the absolute difference between the population-level and subgroup trace of the hessian. For DP-SGD, the paper decomposes the expected loss into a non-private term, a private term due to clipping, and a private term due to noise. Finally, the paper leverages these insights to propose a novel formulation of DP-SGD that empirically decreases the excessive risk gap on real-world datasets.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Originality:** This paper sheds light on the causes of the disparate impact produced by differentially private machine learning methods. This disparate impact was recently discovered by prior work and has not yet been fully understood. The paper presents novel insights via careful theoretical analysis of the effects of differential privacy methods on excessive risk. \n\n**Quality:** The submission is technically sound, and the proofs are generally correct. However, there are some (mostly minor) mistakes:\n- The term $\\nabla_{\\theta^*} \\mathcal{L}(\\theta^*, D_a)$ is missing in the expectation of L506.\n- Equations 15b, 15c, 15d, and 16 all mistakenly use $\\bar{g}_B$ instead of $\\bar{g}_D$.\n- You probably also need to assume that $\\eta \\leq 1$ since $\\eta$ is squared in Equation 25d.\n- Equation 28c is strictly greater than the right-hand side of Equation 29a.\n\n**Clarity:** The paper is clearly written and well organized. However, certain presentational aspects could be improved (also see questions below). The most critical ambiguity is the paper’s claim on L134 that `groups with larger Hessian traces will have larger excessive risk than groups with smaller Hessian traces`. It is unclear why this statement would make sense since the excessive risk is approximated by the absolute difference of the population-level and subgroup hessian traces. Thus the magnitude of the subgroup Hessian trace is entirely irrelevant if it is close to the population-level Hessian trace. Furthermore, the adjacency relation and range should be defined for the Gaussian mechanism on L083. Finally, there are a couple of errors:\n- DP-SGD is frequently misspelled as DP-SDG\n- L025 lending instead of landing\n- L125 from instead of from\n- L140 varying *levels* of\n- L322 these instead of this\n- L604 it instead of if\n\n**Significance:** The submission advances the understanding of the interplay between differential privacy and fairness in machine learning. The results could be useful to researchers from both fields when designing novel fairness of privacy approaches.\n\n**Questions**\n\n- Section 10 mentions that the proposed mitigation solution negatively affects the training runtime but does not provide any concrete numbers. How much slower is the proposed solution?\n- How can the excessive risk gap values in Figure 8 be negative if the excessive risk gap is the absolute difference between two risk functions?\n- What happened to the term $- p_a p_b g_{D_a} g_{D_b}$ when going from Equation 27b to Equation 28a?\n- Is the global sensitivity in L081 and L118 the same?\n- Why is the convexity assumption necessary in Theorem 1? Is this only required for output perturbation?\n- Why does the privacy analysis of output perturbation require optimality of the model parameters? Could one not apply output perturbation to non-optimal parameters?\n\nI am happy to increase my score if the authors can resolve my concerns.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper fails to discuss potential negative societal impacts within the page limit (as required by the [NeurIPS blog](https://neuripsconf.medium.com/introducing-the-neurips-2021-paper-checklist-3220d6df500b)).", "review_text": "", "extra_scores": {"ethical_concerns": "There are no ethical issues with this paper.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8.5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies impact of various DP algorithms on fairness. The paper is well written and easy to follow.  I encourage authors to incorporate reviewer suggestions and make the analysis more rigorous in the final version of the paper e.g., change Theorem 1 to include higher order error terms via O() notation. 
Decision: Accept (Poster)