Differentially Private Empirical Risk Minimization under the Fairness Lens
Year: 2021

Abstract:
Differential Privacy (DP) [14] 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 [3, 27, 23]. 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 [11] and differentially private stochastic gradient descent [2]. 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.

heading: 1 Introduction
text: While learning systems have become instrumental for many decisions and policy operations involving individuals, the use of rich datasets combined with the adoption of 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) [14] has become the paradigm of choice for protecting data privacy and its deployments are growing at a fast rate. DP is appealing as it bounds the risks of disclosing sensitive information of individuals participating in a computation. However, it was recently observed that DP systems may induce biased and unfair outcomes for different groups of individuals [3, 23, 27]. The resulting outcomes can have significant societal and economic impacts on the involved individuals: classification errors may penalize some groups over others in important determinations including criminal assessment, landing, and hiring [3] or can 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 are largely understudied and not fully understood.
This paper makes a step toward addressing this important knowledge gap. It builds on these key observations and sheds light on the causes of the disparate impacts arising in the problem of differentially private empirical risk minimization (ERM). It focuses on the accuracy disparity arising among groups of individuals in two well-studied DP learning methods: output perturbation [11] 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 are 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 (NeurIPS 2021)
2. It analyzes this fairness 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. 5. Based on these observations, it proposes a mitigation solution and evaluates its effectiveness on
several standard datasets. To the best of the authors knowledge, this work represents a first step toward a deeper understanding of the causes of the unfairness impacts in differentially private learning.

heading: 2 Related work
text: 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. [15] seminal work, which highlights the relation between individual fairness and differential privacy, and Khalili et al. [19], 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, 18, 9, 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 a 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 to customize the clipping bound for each group). Works in the last category show that private mechanisms can have a negative impact towards fairness [23, 27, 3, 17, 25]. For example, Cummings et al. [13] shows that it is impossible to achieve exact equalized odds while also satisfying pure DP. Pujol et al. [23] observe that decisions made using a private version of a dataset may disproportionately affect some groups over others. Similar observations were also made in the context of model learning. Bagdasaryan et al. [3] empirically observed that the accuracy of a DP model trained using DP-SGD drops disproportionately across groups causing larger negative impacts to 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 as well as it introduces mitigating guidelines.

heading: 3 Preliminaries
text: Differential privacy (DP) [14] is a strong privacy notion used to quantify and bound the privacy loss of an individual participation to a computation. Informally, it states that the probability of any output does not change much when a 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 a new dataset D′, defines the notion of adjacency, denoted D ∼ D′. Definition 1. A mechanismM :D→R with domainD and range R is (ϵ, δ)-differentially private, if, for any two adjacent inputs D ∼ D′ ∈D, and any subset of output responses R ⊆ R:
Pr[M(D) ∈ R] ≤ eϵ Pr[M(D′) ∈ R] + δ.
Parameter ϵ > 0 describes the privacy loss of the algorithm, with values close to 0 denoting strong privacy, while parameter δ ∈ [0, 1) captures the probability of failure of the algorithm to satisfy ϵ-DP. The global sensitivity ∆ℓ of a real-valued function ℓ : D → Rk is defined as the maximum amount by which ℓ changes in two adjacent inputs: ∆ℓ = maxD∼D′ ∥ℓ(D) − ℓ(D′)∥. In particular, the Gaussian mechanism, defined byM(D) = ℓ(D) +N(0,∆2ℓ σ2), where N(0,∆2ℓ σ2) is the Gaussian distribution with 0 mean and standard deviation ∆2ℓ σ 2, satisfies (ϵ, δ)-DP for δ> 45 exp(−(σϵ)2/2) and ϵ <1 [16].

heading: 4 Problem settings and goals
text: The paper adopts boldface symbols to describe vectors (lowercase) and matrices (uppercase). Italic symbols are used to denote scalars (lowercase) and data features or random variables (uppercase). Notation ∥·∥ is used to denote the L2 norm. The paper considers datasets D consisting of n individuals’ data points (Xi, Ai,Yi), with i ∈ [n] drawn i.i.d. from an unknown distribution. Therein, Xi ∈X is a feature vector, Ai ∈A is a protected group attribute, and Yi ∈Y is a label. For example, consider the case of a classifier that needs to predict the risks associated with a lending decision. The training example features Xi may describe the individual’s demographics, education, credit score, and loan amount, the protected attribute Ai may describe the individual gender or ethnicity, and Yi represents whether or not the individual will default on the loan. The goal is to learn a classifier fθ : X → Y, where θ is a vector of real-valued parameters, that guarantees the privacy of each individual data (Xi, Ai,Yi) in D. The model quality is measured in terms of a nonnegative loss function ℓ : Y ×Y → R+, and the problem is that of minimizing the empirical risk (ERM) function:
min θ L(θ; D) = 1 n n∑ i=1 ℓ( fθ(Xi),Yi). (L)
For a group a ∈ A, the paper uses Da 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 it analyzes the fairness 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(θ,D) = Eθ̃ [ L(θ̃; D) ] − L(θ∗; D), (1)
where the expectation is defined over the randomness of the private mechanism and θ̃ denotes the private model parameters while θ∗ = argminθ L(θ; D). The paper uses shorthands R(θ) and Ra(θ) to denote, respectively, the population-level R(θ,D) excessive risk and the group level R(θ,Da) excessive risk for group a. Fairness is measured with respect to the excessive risk gap:
ξa = |Ra(θ) − R(θ)|. (2)
(Pure) fairness is achieved when ξa = 0 for all groups a ∈ A and, thus, a 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(θ).
All proofs are reported in the Appendix, Section A.

heading: 5 Warm up: output perturbation
text: The paper starts with analyzing fairness under the DP setting induced by an output perturbation mechanism. In this setting the analysis restricts to twice differentiable and convex loss functions ℓ. 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 N(0,∆2ℓσ2) to the optimal model parameters θ∗ ensures (ϵ, δ)-differential privacy [11]. Therein, ∆ℓ = 2/nλ with regularization parameter λ. The following result sheds light on the unfairness induced by this mechanism.
Theorem 1. Let ℓ be a twice differentiable and convex loss function and consider the output perturbation mechanism described above. Then, the excessive risk gap for group a ∈ A is approximated by:
ξa ≈ 1 2 ∆2ℓσ
2 ∣∣∣Tr(Haℓ ) − Tr(Hℓ)∣∣∣ , (3)
where Haℓ =∇2θ∗ ∑
(X,A,Y)∈Daℓ( fθ∗(X),Y) is the Hessian matrix of the loss function, at the optimal parameters vector θ∗, computed using the group data Da, Hℓ is the analogous Hessian computed using the population data D, and Tr(·) denotes the trace of a matrix.
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 Ra(θ) for a group a can be approximated as 1/2∆2ℓσ 2 Tr(Haℓ ). The proof is reported in Appendix A.
Theorem 1 sheds light on the relation between fairness and the difference in the local curvatures of the losses ℓ 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 to the amount of noise σ or, equivalently, inversely proportional to the privacy parameter ϵ, for a fixed δ. Finally, it also suggests that groups with larger Hessian traces Tr(Hℓa) 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 8.
Figure 1 illustrates Theorem 1. The plots show the correlation between the excessive risk 1 and the quantity Tr(Hℓz ) for each group z ∈ A, at varying of the privacy loss ϵ ∈ [0.005, 0.5], δ = 1e−5 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 ∈ A. Details on dataset and experimental setting are provided in Appendix B and additional experiments in Appendix C. Note the positive correlation between the excessive risk and the
Hessian trace: Groups with larger Hessian 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 σ 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 fairness.
Corollary 1. Consider the ERM problem for a linear model fθ(X) def = θT X, with L2 loss function i.e., ℓ( fθ(X),Y) = ( fθ(X) − Y)2. Then, output perturbation does not guarantee pure fairness.
It follows from the observation that the Hessian of the L2 loss for group a ∈ A, i.e., Tr(Haℓ ) = EX∼Da Tr(XX
T )=EX∼Da∥X∥2, depends solely on the input norms of the elements in Da2. Interestingly, 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.
The following is a positive result.
Corollary 2. If for any two groups a, b ∈ A their average group norms EXa∼Da∥Xa∥ = EX∼Db∥Xb∥ have identical values, then output perturbation with L2 loss function provides pure fairness.
The above is a direct consequence of Corollary 1. 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.

heading: 6 Gradient perturbation: DP-SGD
text: 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 θ, rendering it an appealing framework for DP ERM problems.
1In all experiment presented, the excessive risk is approximated by sampling over 100 repetitions. 2Throughout the paper, we abuse notation and treat the dataset DZ associated with group Z as distributions.
Algorithm 1: DP-SGD input :Disjoint dataset D ; Sample prob. q; Iterations T ; Noise variance σ2; Clipping bound C; learning rate η θ0 ← 0T for iteration t = 1, 2, . . .T do
B← random sub-sample of D with Pr q foreach (Xi, Ai,Yi) ∈ B do gi = ∇ℓ ( fθt (Xi),Yi ) ḡB ← 1|B| (∑ i πC(gi) +N(0, IC2σ2)
) θt+1 ← θt − ηḡB In a nutshell, DP-SGD computes the gradients for each data sample in a random mini-batch B, clips their L2-norm, adds noise to ensure privacy, and computes the average. Two key characteristics of DPSGD are: (1) Clipping the gradients whose L2 norm exceeds a given bound C, and (2) Perturbing the averaged clipped gradients with 0-mean Gaussian noise with variance σ2C2. The procedure is described in Algorithm 1. Therein, gi represents the gradient of a data sample (Xi, Ai,Yi), ḡB the average clipped noisy gradient of the samples in mini-batch B, and the function πC(x) = x ·min(1, C∥x∥ ).
The following theorem is an important result of this section. It connects the expected loss E[L(θ; Da)] of a group a ∈ A with its excessive risk Ra(θ), which is, in turn, used in our fairness analysis. It 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.r.t. the model parameters. The expected loss E[L(θt+1; Da)] of group a∈A at iteration t+1, is approximated as:
E [L(θt+1; Da)] = L(θt; Da) − η 〈 gDa , gD 〉 + η2
2 E
[ gTBH a ℓ gB ] ︸ ︷︷ ︸
non-private term
(4)
+ η (〈 gDa , gD 〉 − 〈gDa , ḡD〉) + η22 (E [ḡTBHaℓ ḡB] − E [gTBHaℓ gB])︸ ︷︷ ︸ private term due to clipping
(Rclipa )
+ η2
2 Tr(Haℓ )C 2σ2︸ ︷︷ ︸ private term due to noise
(Rnoisea )
+ O(∥θt+1 − θt∥3), where the expectation is taken over the randomness of the private noise and the mini-batch selection, and the terms gZ and ḡZ denote, respectively, the average non-private and private gradients over subset Z of D at iteration t (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 L(θt − ηgB; Da) and L(θt − η(ḡB +N(0, IC2σ2); Da), respectively, around θt 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-private) SGD loss. Terms (Rclipa ) and (Rnoisea ) quantify, together, the excessive risk for group a. Therein, (R clip a ) quantifies the effect of clipping to the excessive risk, and (Rnoisea ) quantifies the effect of perturbing the average gradients to the excessive risk. Therefore, Theorem 2 shows that there are two main sources of disparate impact in DP-SGD training: 1. Gradient clipping (Rclipa ): which, in turn, depends of three factors: (i) The values of the Hessian
matrix Haℓ of the loss function associated with group a; (ii) The gradients values gDa associated with the samples of group a; and (iii) The clipping bound C, which appears in ḡB and ḡD. 2. Noise addition (Rnoisea ): which, in turn, depends on two factors: (i) The values of the (trace of the) Hessian matrix Haℓ of the loss function associated with group a; and (ii) The privacy loss parameters (ϵ, δ,∆ℓ) (which, in turn, are characterized by the noise variance C2σ2). A schematic representation of these factors is shown in Figure 2. Therein, XDa denotes the features values X ∈ X of the subset Da of D. Theorem 2 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 Rclipa (Section 7) and Rnoisea (Section 8). Independently studying these terms is motivated by
<latexit sha1_base64="jhyXc5IRIc/xqiktWBUYXb4OYIU=">AAACFHicbVDLSsNAFJ34rPUVHzs3wSK4KokUdFl047KKfUBby2R62w6dTMLMjVhDfsO1W/0Gd+LWvZ/gXzhts7C2By4czrmHmXv8SHCNrvttLS2vrK6t5zbym1vbO7v23n5Nh7FiUGWhCFXDpxoEl1BFjgIakQIa+ALq/vBq7NcfQGkeyjscRdAOaF/yHmcUjdSxD2879D5pITyiFokMuYY07dgFt+hO4MwTLyMFkqHSsX9a3ZDFAUhkgmrd9NwI2wlVyJmANN+KNUSUDWkfmoZKGoBuJ5Pfp86JUbpOL1RmJDoT9W8ioYHWo8A3mwHFgZ7x/GChbCJjcZHXjLF30U64jGIEyabv92LhYOiMG3K6XAFDMTKEMsXNCQ4bUEUZmh7zphvvfxPzpHZW9ErF0k2pUL7MWsqRI3JMTolHzkmZXJMKqRJGnsgLeSVv1rP1bn1Yn9PVJSvLHJAZWF+/RSCfKg==</latexit>
<latexit sha1_base64="JJO3YOHFLk1/Kb38SPyiOfopQ8c=">AAAB/HicbVBNS8NAEN34WetXtEcvi0XwVBIp6LHoxWMV+wFtDJvtpl262YTdiRhC/StePCji1R/izX/jts1BWx8MPN6bYWZekAiuwXG+rZXVtfWNzdJWeXtnd2/fPjhs6zhVlLVoLGLVDYhmgkvWAg6CdRPFSBQI1gnGV1O/88CU5rG8gyxhXkSGkoecEjCSb1dufXKf94E9ghY5FTyZTHy76tScGfAycQtSRQWavv3VH8Q0jZgEKojWPddJwMuJAk4Fm5T7qWYJoWMyZD1DJYmY9vLZ8RN8YpQBDmNlSgKeqb8nchJpnUWB6YwIjPSiNxX/83ophBdezmWSApN0vihMBYYYT5PAA64YBZEZQqji5lZMR0QRCiavsgnBXXx5mbTPam69Vr+pVxuXRRwldISO0Sly0TlqoGvURC1EUYae0St6s56sF+vd+pi3rljFTAX9gfX5A7ZGlXg=</latexit>
<latexit sha1_base64="OuiItAFRRc2V+inzcL6/Rz11sRo=">AAACEXicbVBLTsMwFHTKr5RfCks2FhUSqypBlWBZwabLItGP1ITIcZ3Wqu1EtgOqopyCNVs4AzvElhNwBG6B22ZBaUd60mjmjew3YcKo0o7zbZU2Nre2d8q7lb39g8Mju3rcVXEqMengmMWyHyJFGBWko6lmpJ9IgnjISC+c3M783iORisbiXk8T4nM0EjSiGGkjBXbVC3nWyoPMI4zlDxnKA7vm1J054CpxC1IDBdqB/eMNY5xyIjRmSKmB6yTaz5DUFDOSV7xUkQThCRqRgaECcaL8bP71HJ4bZQijWJoRGs7Vv4kMcaWmPDSbHOmxWvJCvlY2kZm4zhukOrr2MyqSVBOBF+9HKYM6hrN64JBKgjWbGoKwpOYEiMdIIqxNiRXTjfu/iVXSvay7jXrjrlFr3hQtlcEpOAMXwAVXoAlaoA06AIMn8AJewZv1bL1bH9bnYrVkFZkTsATr6xd2lZ2g</latexit>
<latexit sha1_base64="dMkpf5MBLfqVMnjIK3VcvjoEBWc=">AAAB/3icbVC7SgNBFL0bXzG+opY2g0GwCrsS0DKYxjIB84BkCbOTm2TIzO4yMyuEJYW1rX6Dndj6KX6Cf+Ek2cKYHLhwOOceZu4JYsG1cd1vJ7e1vbO7l98vHBweHZ8UT89aOkoUwyaLRKQ6AdUoeIhNw43ATqyQykBgO5jU5n77CZXmUfhopjH6ko5CPuSMGis1av1iyS27C5B14mWkBBnq/eJPbxCxRGJomKBadz03Nn5KleFM4KzQSzTGlE3oCLuWhlSi9tPFR2fkyioDMoyUndCQhfo3kVKp9VQGdlNSM9YrXiA3yjYyFzd53cQM7/yUh3FiMGTL94eJICYi8zLIgCtkRkwtoUxxewJhY6ooM7aygu3G+9/EOmndlL1KudKolKr3WUt5uIBLuAYPbqEKD1CHJjBAeIFXeHOenXfnw/lcruacLHMOK3C+fgGE65YA</latexit>
<latexit sha1_base64="3IqfGseHMSLU+CHL4pFbV/3XTW8=">AAACH3icbVDLSsNAFJ3UV62vqEsXDhahgpRECros6sJlBfuApoTJ9LYdOpmEmYlQSpd+iGu3+g3uxG0/wb9w0mahbQ9c7uGce7ncE8ScKe04Uyu3tr6xuZXfLuzs7u0f2IdHDRUlkkKdRjySrYAo4ExAXTPNoRVLIGHAoRkM71K/+QxSsUg86VEMnZD0BesxSrSRfPu05EGsGI/EJfa6wDUx/T7tvgecX/h20Sk7M+Bl4makiDLUfPvH60Y0CUFoyolSbdeJdWdMpGaUw6TgJQpiQoekD21DBQlBdcazRyb43Chd3IukKaHxTP27MSahUqMwMJMh0QO16KXiSi8IV8ntRPduOmMm4kSDoPP7vYRjHeE0LNxlEqjmI0MIlcy8gOmASEK1ibRgsnEXk1gmjauyWylXHivF6m2WUh6doDNUQi66RlX0gGqojih6QW/oHX1Yr9an9WV9z0dzVrZzjP7Bmv4CEw6h/Q==</latexit>
<latexit sha1_base64="4CFcpjztFLZ0FbzNIqHLESGv5yI=">AAACTXicbVFdSxtBFJ1NrR+pH2l97MtgKCjUsCsBfSmIViiUgkKjC9l1mZ3cTYbM7C4zd4Uw7K/yh/TZV33yB/gmpZOYB60eGDiccw+XeyYtpTDo+zde493C+8Wl5ZXmh9W19Y3Wx0/npqg0hx4vZKHDlBmQIoceCpQQlhqYSiVcpOPjqX9xBdqIIv+NkxJixYa5yARn6KSk9StSDEdpak/qxIaREYqGif2esLqmzchUKrHjb0F9+ZNGEjLs04Du0uxyL7ERjgDZ13G9He7QSIvhCOOk1fY7/gz0NQnmpE3mOE1a99Gg4JWCHLlkxvQDv8TYMo2CS6ibUWWgZHzMhtB3NGcKTGxnZ9f0i1MGNCu0eznSmfo8YZkyZqJSNzk90rzwUvWm7CJT8S2vX2F2EFuRlxVCzp/2Z5WkWNBptXQgNHCUE0cY18KdQPmIacbRfUDTdRP838Rrcr7XCbqd7lm3fXg0b2mZfCZbZJsEZJ8ckh/klPQIJ9fkhtySO++P9+A9en+fRhvePLNJXqCx9A9RgbL/</latexit>
<latexit sha1_base64="rX+9wOLFOlrcsC/DcxQmDFE88k4=">AAACLHicdVDLSgMxFM3UV62vqks3wSK4KCXTt7uiG5dV7AOmw5BJ0zY08yDJCGXoT/ghrt3qN7gRcSv4F2b6AJV6IHA459yb5LghZ1Ih9Gak1tY3NrfS25md3b39g+zhUVsGkSC0RQIeiK6LJeXMpy3FFKfdUFDsuZx23PFV4nfuqZAs8O/UJKS2h4c+GzCClZacbD7uzZZYYujaMSpUS/XqBcqjAkKVeq2UEBNViqXprYOnTja3TMBlAi4T0NRKghxYoOlkv3r9gEQe9RXhWErLRKGyYywUI5xOM71I0hCTMR5SS1Mfe1Ta8exBU3imlT4cBEIfX8GZ+nMixp6UE8/VSQ+rkfzrJeJKz/VWyVakBnU7Zn4YKeqT+f2DiEMVwKQ52GeCEsUnmmAimP4CJCMsMFG634zuZlkA/J+0iwWzXCjflHONy0VLaXACTsE5MEENNMA1aIIWIOABPIFn8GI8Gq/Gu/Exj6aMxcwx+AXj8xt+RKRi</latexit>
<latexit sha1_base64="OuiItAFRRc2V+inzcL6/Rz11sRo=">AAACEXicbVBLTsMwFHTKr5RfCks2FhUSqypBlWBZwabLItGP1ITIcZ3Wqu1EtgOqopyCNVs4AzvElhNwBG6B22ZBaUd60mjmjew3YcKo0o7zbZU2Nre2d8q7lb39g8Mju3rcVXEqMengmMWyHyJFGBWko6lmpJ9IgnjISC+c3M783iORisbiXk8T4nM0EjSiGGkjBXbVC3nWyoPMI4zlDxnKA7vm1J054CpxC1IDBdqB/eMNY5xyIjRmSKmB6yTaz5DUFDOSV7xUkQThCRqRgaECcaL8bP71HJ4bZQijWJoRGs7Vv4kMcaWmPDSbHOmxWvJCvlY2kZm4zhukOrr2MyqSVBOBF+9HKYM6hrN64JBKgjWbGoKwpOYEiMdIIqxNiRXTjfu/iVXSvay7jXrjrlFr3hQtlcEpOAMXwAVXoAlaoA06AIMn8AJewZv1bL1bH9bnYrVkFZkTsATr6xd2lZ2g</latexit>
observation that the clipping value C regulates the dominance of a factor over the other. Indeed, for sufficiently large (small) C values Rnoisea will dominate (be dominated by) R clip a .3

heading: 7 Why gradient clipping causes unfairness?
text: As highlighted above, there are three factors influencing the clipping effect to the excessive risk Rclipa : 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 XDa , which plays a role to this disparate impacts by indirectly controlling the norms of gradient gDa (see the diagram illustrated in Figure 2).
The next results assume that the empirical loss function L(θ; Da), associated with each group a ∈ A, is convex and βa-smooth. The analysis also consider learning rates η ≤ 1/maxa βa and gradients g(B) and ḡ(B) with small variances. Note that this is not restrictive as the variance decreases as a 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.
Theorem 3. Let pz = |Dz |/|D| be the fraction of training samples in group z ∈ A. For groups a, b ∈ A, Rclipa > Rclipb whenever:∥∥∥gDa∥∥∥ p2a2 ≥ 52C + ∥∥∥gDb∥∥∥ 1 + pb + p2b2  . (5)
Theorem 3 provides a sufficient condition for which a 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 gDa and gDb 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 Rclipa : (1) the clipping bound C, and (2) the (norm of the) gradients ∥gDa∥. While the relative dataset size pa = |Da |/|D| of each group also appears in Equation (5), our extensive experiments showed that this factor may not play a prime role in controlling the disparate impacts (see Appendix C).
The relation with these two factors is illustrated in Figure 3, which shows the impact of gradient clipping (for different C values) to the gradient norms (top) and to the excessive risk Ra (bottom). It
3This observation relates with the bias-variance trade-off typically observed in DP-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 input norms, whose average is denoted XDa = EX∼XDa ∥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 (L) for a linear classifier fθ(X) def = softmax(θT X) and cross-entropy loss ℓ( fθ(X),Y) = − ∑K i=1 Yi logf i θ
(X) where K is the number of classes. The gradient of the loss function at a given data point (X,Y) is: gX = ∇θℓ( fθ(X),Y) = (Y − f ) ⊗ X. The result is by [7] and it suggests that the gradient norms are proportional to the input norms: ∥gX∥ ∝ ∥X∥.
Example 2. Next, consider a neural network with single hidden layer, fθ(X) def = softmax ( θT1 o(θ T 2 X) ) , where o(·) is a proper activation function and θ1,θ2 are the model parameters. It can be seen that ∥gX∥ ∝ ∥∇θ1ℓ( fθ(X),Y)∥ + ∥∇θ2ℓ( fθ(X),Y)∥, where ∥∇θ2ℓ( fθ(X),Y)∥ ∝ ∥X∥. The full derivations are reported in Appendix D.
Both examples illustrate a correlation between the gradients norms ∥gX∥ and input norms ∥X∥ for a given data sample X. This behavior is also illustrated in Figure 4, which highlights a positive correlation between the individual inputs and the gradients norms obtained while privately training a 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.
These observations imply that group data with large input norms—typically defining the tail of data distribution—result in large gradient norms and, thus, as shown in Theorem 3, may have larger disproportionate impacts than groups with smaller input 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 a dependency between gradients and clipping bound, as illustrated in the (Rclipa ) equation, the group excessive risk is 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 η2/2 which attenuate the impact of the Hessian 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 Rclipa for a group a ∈ A are the norm of the group gradients gDa , in turn controlled by the norm of the inputs XDa , and the clipping bound C.

heading: 8 Why noise addition causes unfairness?
text: Next, the paper analyzes the factors influencing the noise effect to the excessive risk Rnoisea , which, as highlighted in Theorem 2, for DP-SGD and Theorem 1 for output perturbation, are the Hessian loss, and the privacy loss parameters (ϵ, δ,∆ℓ) (see also Figure 2). Noting that the privacy parameters have a multiplicative effect on the Hessian loss (see Equations (Rnoisea ) 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 a condition to compare the disparate impacts between different groups, Theorem 4. For groups a, b ∈ A, Rnoisea > Rnoiseb whenever
Tr(Haℓ ) > Tr(H b ℓ ).
Note the connection of the result above with Theorem 1. Additionally, as illustrated in the diagram of Figure 2 the 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
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 1. The Hessian of the cross entropy loss of a sample X ∼ D is given by HXℓ = [ ( diag(f ) − ffT ) ⊗ XXT ], where ⊗ is the Kronecker product [7]. This result suggests that the trace of the Hessian for sample X is proportional to its input norm: Tr(HXℓ ) ∝ ∥X∥2. Additionally it also shows that: Tr(HXℓ ) ∝ (1 − ∑K k=1 f 2 θ,k(X)), where K is the number of classes, whose term is connected to the distance to the decision boundary, as shown next.
The following result highlights the connection between the term (1 −∑Kk=1 f 2θ,k(X)) and the distance of sample X to the decision boundary. Theorem 5. Consider a K-class classifier fθ,k (k ∈ [K]). For a given sample X ∼ D, the term( 1 −∑Kk=1 f 2θ,k(X)) is maximized when fθ,k(X) = 1/K and minimized when ∃k ∈ [K] s.t. fθ,k(X) = 1 and fθ,k′ = 0 ∀k′ ∈ [K], k , k.
That is, the term ( 1 −∑Kk=1 f 2θ,k(X)) is maximized (minimized) when the sample X is close (far) to the decision boundary. Since, as shown in Example 3 this term can be proportional to the Hessian trace, then the aforementioned relation also indicates a connection between the Hessian trace value for a sample and its distance to the decision boundary: The closest (farther) is a sample X to the decision boundary the larger (smaller) is the associated Hessian trace value Tr(HXℓ ).
This is intuitive as the model decision are less robust to the presence of noise in the model (e.g., as that introduced by a DP mechanism) for the samples which are close to the decision boundary w.r.t. those which are far from it.
An analogous behavior is also observed in Neural Networks and described in Appendix D due to space constraints. Figure 5 illustrates 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 to the decision boundary for a given sample X.
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, on 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 to have larger disproportionate impacts under private training than groups with smaller input norms.
In summary, the main factor affecting Rnoisea for a group a ∈ A is the Hessian loss Haℓ , which, in turn, is controlled by the group’s distance to the decision boundary and by their inputs norm.

heading: 9 Mitigation solution
text: The previous sections showed that, in DP-SGD, the excessive risk Ra for a group a ∈ A could be decomposed into two factors Rclipa , due to clipping, and Rnoisea , due to noise addition. In turn, it identified the gradients values gDa associated with the samples of group a and the clipping bound C
as the main sources of disparate impact in component Rclipa , and the (trace of the) Hessian Haℓ of the group a loss function as the main source of disparate impact in component Rnoisea .
A solution to mitigate the effects of these components to the excessive risk gap is to equalize the factors responsible for Rclipa and Rnoisea among all group a ∈ A during private training. The resulting empirical risk loss becomes:
min θ L(θ; D) + ∑ a∈A ( γ1 ∣∣∣〈gDa − gD, gD − ḡD〉∣∣∣ + γ2 ∣∣∣Tr(Haℓ ) − Tr(Hℓ)∣∣∣) , (6) where the component multiplied by γ1 comes for simplifying the expression | 〈 gDa , gD
〉 − 〈gDa , ḡD〉− ⟨gD, gD⟩ − ⟨gD, ḡD⟩ | associated to the empirical risk gap ξa of the main factor affecting Rclipa , and component multiplied by γ2 by the analogous expression for the main factor affecting Rnoisea . Note that this last component involves computing the Hessian matrices of the loss functions during each training step, which is a computationally expensive process. The previous section, however, showed a strong dependency between the trace of the Hessian losses and the distance to the decision boundary (Theorem 5). Thus, in place of Equation (6) the proposed mitigating solution solves:
min θ L(θ; D) + ∑ a∈A γ1 ∣∣∣〈gDa − gD, gD − ḡD〉∣∣∣ + γ2 ∣∣∣∣∣∣∣EX∼Da [1− K∑ k=1 f 2θ,k(X)] − EX∼D[1− K∑ k=1 f 2θ,k(X)] ∣∣∣∣∣∣∣  .
Figure 7 illustrates this approach at work, for various multipliers γ1 and γ2 on the Bank dataset with two protected group (blue = majority; orange = minority). Similar trends are shown for other datasets as well in Appendix C. The implementation uses a neural network with a single hidden layer and Suppose uses DP-SGD with C = 0.1, σ = 5.0. A clear trend arises: For appropriately selected values γ1 and γ2 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 fairness but also the loss in utility of the private models.

heading: 10 Limitations and conclusions
text: This work was motivated by the recent observations regarding the disparate impacts induced by DP in learning systems. The paper introduced a notion of fairness that relies on 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 an interesting open question. The second limitation regards the selection of the multipliers γ1 and γ2 in Equation 6. While the paper does not investigate how to optimally selecting these values, the adoption of a Lagrangian Dual framework, as in [25], could a 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.

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

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.