Disparate Impact in Differential Privacy from Gradient Misalignment
Authors: Maria S. Esipova
Atiyeh Ashari Ghomi
Yaqiao Luo
Jesse C Cresswell
Venue: ICLR 2023 notable top 25% (2023)
Keywords: Differential privacy
fairness
privacy

Abstract: As machine learning becomes more widespread throughout society, aspects including data privacy and fairness must be carefully considered, and are crucial for deployment in highly regulated industries. Unfortunately, the application of privacy enhancing technologies can worsen unfair tendencies in models. In particular, one of the most widely used techniques for private model training, differentially private stochastic gradient descent (DPSGD), frequently intensifies disparate impact on groups within data. In this work we study the fine-grained causes of unfairness in DPSGD and identify gradient misalignment due to inequitable gradient clipping as the most significant source. This observation leads us to a new method for reducing unfairness by preventing gradient misalignment in DPSGD.

Published as a conference paper at ICLR 2023
DISPARATE IMPACT IN DIFFERENTIAL PRIVACY FROM GRADIENT MISALIGNMENT
Maria S. Esipova, Atiych Ashari Ghomi, Yaqiao Luo & Jesse C. Cresswell Layer Al {maria, atiyeh, emily, jesse)elayer6.ai
ABSTRACT
As machine learning becomes more widespread throughout society, aspects in- cluding data privacy and fairness must be carefully considered, and are crucial for deployment in highly regulated industries. Unfortunately, the application of pri- vacy enhancing technologies can worsen unfair tendencies in models. particu- lar, one of the most widely used techniques for private model training, differen- tially private stochastic gradient descent (DPSGD), frequently intensifies disparate impact on groups within data. In this work we study the fineggriined causes of un- fairness in DPSGD and identify gradient misalignment due to inequitable gradient clipping as the most significant source. This observation leads to new method for reducing unfairness by preventing gradient misalignment in DPSGD,
INTRODUCTION
The increasingly widespread use of machine learning throughout society has brought into focus social, ethical, and legal considerations surrounding its use. In highly regulated industries, such as healthcare and banking, regional laws and regulations require data collection and analysis to respect the privacy of individuals Other regulations focus on the fairness of how models are developed and used [ As machine learning is progressively adopted in highly regulated industries, the privacy and fairness aspects of models must be considered at all stages of the modelling lifecycle.
There are many privacy enhancing technologies including differential privacy (Dwork et al. 2006). federated learning (McMahan et al.) (0177), secure multiparty computation (Yao) 1986). and ho- momorphic encryption (Gentry) 2009) that are used separately or jointly to protect the privacy of individuals whose data is used for machine learning (Choquette- Chho et al., 2020 Adnan et al. 2022 Kalra et al. 2021). The latter three technologies find usage in sharing schemes and can allow data to be analysed while preventing its exposure to the wrong parties. However, the procedures usually return trained model which itself can leak private information (Carlini al. 2019). On the other hand, differential privacy (DP) focuses on quantifying the privacy cost of disclosing aggre- gated information about dataset, and can guarantee that nothing is learned about individuals that could not be inferred from population-level correlations (Jagielski et al. 2019). Hence, DP is often used when the results of data analysis will be made publicly available, for instance when exposing the outputs of a model, or the results of the most recent US census (Abowd) 2018).
Not only must privacy be protected for applications in regulated industries, models must be fair. While there is no single definition that captures what it means to be fair, with regards to model- based decision making fairness may preclude disparate treatment or disparate impact (Mehrabi et al.) 2021]. Disparate treatment is usually concerned with how models are applied across populations, whereas disparate impact can arise from biases in datasets that are amplified by the greedy nature of loss minimization algorithms (Buolamwini & Gebru 2018). Differences in model performance across protected groups can result in a significant negative monetary, health, or societal impact for individuals who are discriminated against (Chouldechova & Roth 2020).
"Examples of laws governing data privacy include the General Data Protection Regulation in Europe, Health Insurance Portability and Accountability Act in the USA, and Personal Information Protection and Electronic Documents Act Canada.
In the USA, fair lending laws including the Fair Housing Act, and Equal Credit Opportunity Act prohibit discrimination based on protected characteristies such as race, age, and sex.

---

Published as a conference paper at ICLR 2023
Unfortunately, it has been observed that disparate impact can be exacerbated by applying DP in machine learning (Bagdasaryan et al. 2019). Applications of DP always come with a privacy-utility tradeoff, where stronger guarantees of privacy negatively impact the usefulness of results model performance in this context (Dwork & Roth 2014). Underrepresented groups within the population can experience disparity in the cost of adding privacy, hence, fairness concerns a major obstacle to deploying models trained with DP.
The causes of unfairness in DP depend on the techniques used, but are not fully understood. For the most widely used technique, differentially private stochastic gradient descent (DPSGD), two sources of error are introduced that impact model utility. Per-sample gradients are clipped to a fixed upper bound on their norm, then noise is added to the averaged gradient. Disparate impact from DPSGD was initially hypothesized to be rooted in unbalanced datasets (Ragdasaryan et al. 2019), though counterexamples were found by Xu et al. (2021). Recent research claims disparate impact to be caused by incommensurate clipping errors across groups, in turn effected by a large difference in average group gradient norms (Xu et al. 202 Tran al. 2021a).
In this work we highlight the disparate impact of gradient misalignment. In particular, we claim that the most significant cause of disparate impact is the difference in the direction of the unclipped and clipped gradients, which in turn can be caused by aggressive clipping and imbalances of gradient norms between groups. Our analysis of direction errors leads to variant of DPSGD with properly aligned gradients. We explore this alternate method in relation to disparate impact and show that it not only significantly reduces the cost of privacy across all protected groups, it also reduces the difference in cost of privacy for all groups. Hence, it removes disparate impact and is more effective than previous proposals in doing so. On top of this, the only approach which does not require access to protected group labels, and thereby avoids disparate treatment of groups. In summary we:
Conduct a more fine-graing ane-grained analysis of disparate impact in DPSGD, and demonstrate gradient misalignment to be the most significant cause;
Identify existing algorithm, previously undiscussed in the faimess context, which prop- erly aligns gradients, and show it reduces disparate impact and disparate treatment;
Improve the utility of said algorithm via two alterations;
Experimentally verify that aligning gradients is more successful at mitigating disparate impact than previous approaches.
2 RELATED WORK
While privacy and fairness have been extensively studied separately, re- cently their interactions have come into focus. [Estrrad et al. (2018) considered the intersection of privacy and fairness for several definitions of privacy. This research gained new urgency when Bagdasaryan et al. 2019) observed that DPSGD exacerbated existing disparity in model accuracy on underrepresented groups Disparate impact due to DP was further observed in [Pujol et al. (2020) and Farrand et al.] (2020) for varying levels of group imbalance. Using an adversarial definition of privacy, Jaiswal & Mower Provost (2020) found that overrepresented groups can incur higher pri- vacy costs. Similar examples were shown in Xu et al. (2021) for DPSGD, and disparate impact was linked groups having larger gradient norms.
Privacy and Fairness:
Other fairness-aware learning research has evaluated the fairness of private model's outcomes on protected groups. In this context fairness might refer to a statistical condition of non-discrimination with respect to groups (Mozannar et al. 2020 Tran et al. 2021b), for example, equalized odds (Jagielski et al. ).19). equality of opportunity (Cummings et al. 2019), or demographic parity (Xu) et al. [019 Farrand et al., 2020). Chang & Shokri (2021) empirically found that imposing fairness constraints on private models could lead to higher privacy loss for certain groups. We consider cross- model fairness where the cost of adding privacy to a non-private model must be fairly distributed between groups.
Adaptive Clipping: Many variations on the clipping procedure in DPSGD have been proposed to improve properties other than fairness. Adaptive clipping comes in many forms, but usually tunes the clipping threshold during training to provide better privacy-utility tradeoffs and convergence (Andrew et al. [202]] Pichapati et al. (019). The convergence of DPSGD connects to the symmetry properties of the distribution of gradients (Chen et al. 2020) which are affected by clipping.
2

---

Published as a conference paper at ICLR 2023
3 BACKGROUND
3.1 SETTING AND DEFINITIONS
We begin by laying out the problem setting and review the relevant definitions for discussing fairness in privacy. For concreteness we consider a binary classification problem on a dataset D) which consists of points of the form (Ii, Og 0g, Vs)., where 2; E F. is feature vector, yi E {0, 13 is binary label, and ag E [K] refers to a protected group attribute which partitions the data. The group label a, can optionally be an attribute in zi, the label value yr. or some distinct auxiliary value.
The goal is to train model fe Rd + [0, 1] with parameter vector O that is simultaneously useful and private, and in which the application of privacy is fair. Utility in the empirical risk minimization (ERM) problem is governed by the per-sample loss e [0, 1] x {0, 1} - IR with the optimal model minimizing the objective [(: D) 1 Eien ((f( ys). which happens for optimal parameters 0" arg ming [(0; D). The requirement of privacy is applied to the model through its parameters; private parameters 0 must be obtained while exposing minimal amount of private information in D. For this we apply the framework of differential privacy, recounted in the next section.
n
Fairness of the privacy methodology can be measured terms of the disparate impact that applying privacy has the protected groups. As in Bagdasaryan al. (2019), we use version of accuracy parity, the difference
classification accuracy across protected groups after adding privacy, We denote a subset of the data containing all points belonging to group l as D3 { at 9a) D DIa, a, = k}. A private model has accuracy parity for subset D2 if it minimizes the privacy cost
(0, D&)) acc(O"; D&) - E,g (acc((;; D&)],
where the expectation is over the randomness involved in acquiring private model parameters. Of course, metrics other than classification accuracy could be used as required by the problem setting. Alternatively, fairness for privacy can be measured the level of the loss function in Tran et al. (2021a), which is more amenable to analyzing the causes of unfairness. The excessive risk over the course of training experienced by a group is
R(0, D2) EgIc(o; D&)] - L(0"; DR).
(2)
When the model is clear from context we denote R(0; Dx) as RE, and similarly for privacy cost Th- For both accuracy and loss we consider the gap between disparate impact values across groups. The privacy cost gap is aa, = ATa Tol for groups a, b E [K], and the excessive risk gap refers to Ru.b Rr RRl. The goal of a fair private classifier to minimize the privacy cost and/or excessive risk for all values of the protected group attribute, while maintaining small fairness gaps.
3.2 DIFFERENTIAL PRIVACY
Algorithm DPSGD
Diffcrential privacy (DP) DDoork et al. 2006 is a widely used framework for quantifying the privacy consumed by a data analysis procedure. Formally, let D represent set of data points, and M proba- bilistic function, or mechanism, acting on datasets. We say that the mechanism is (e, dddifferrrel private if for all subsets of possible outputs S C Range(M (M), and for all pairs of databases D and D' that differ by the addition or removal of one element,
Require:
Iterations T, Dataset D, sampling rate g, clipping bound Co, noise multiplier a, learning rates 1/t Initialize O, randomly do B +- Poisson sample of D with rate q for (I;, ys) in B do
for in O.................... .,.
9i - Vol(fo, (x.(). (x:),01 Ut)
(D) E S] S PF)M E S]+ 8. (3)
9 9: min
1, To
Co
JB + 1 {Σ SBB 9. NN
For the ERM problem, there are several ways to train a differentially private model (Chaudhuri et al. 2011). In this work we consider models that can be trained with stochastic gradient descent (SGD), such as neural networks, and focus on the most suc- cessful approach, DPSGD (Abadi et al.) 2016). in which the Gaussian mechanism (Dwork & Roth 2014) is applied to gradient updates as in Alg. I Since per-sample gradients 9i generally do not have finite sensitivity, defined A max Dr [lh(D) h(D')l for a function h, they are first clipped to have norm upper bounded by a fixed hyperparameter Cp- Clipped gradients ğ. in a batch B C 1 are aggregated into ÿa and noise is added produce ÿn used in the parameter update.
0.+1 + 0, n(9B
3

---

Published as a conference paper at ICLR 2023
3.3 FAIRNESS CONCERNS FROM CLIPPING AND NOISE IN DPSGD
The two most significant steps in DPSGD, clipping and adding noise, can impact the learning process disproportionately across groups, but the exact conditions where disparate impact will occur have been debated (Bagdasaryan et al. 2019; Farrand et al. 2020 Xu et al. [22T]] (Taan et al. (021a). The most concrete connection so far appears in (Tran et al. 2021a), where the expected loss L(o: Da) is decomposed into terms contributing to the excessive risk at a single iteration for group Ra:
(Tran et al. (021a)). Consider the ERM problem with twice-diffrrentiable loss with respect to the model parameters. The expected loss [[[(0++1; Da)l of group a E [K] at iteration t approximated up to second order in |1c++1 0ell as:
Proposition 1
[[[(0(+1: Da)l xe L(0;; Da) - -11 1o'9D.,.00 ID) + I Higg
(non-private term)
2
+ m.lD. 9D DD) +
ØD)
Ti
2 -Blg
(Reli
(Ranise)
The expectation is laken over the randomness of the DP mechanisms, and batches of data.
Terms in the first line appear for ordinary SGD, and do not contribute the excessive risk Eq. The terms in the second line, Relip are caused by clipping since they cancel when GB = 9B for every batch. They involve gradients 9D, and Hessians Hÿ- averaged over datapoints belonging to group a. The final term, R depends on the scale of noise added in Alg. I as well as the trace of the Hessian, also called the Laplacian, averaged over Da- Based on Prop. [ Tran et al. (2021a) argue that clipping causes excessive risk to groups with large gradient norms, which can result from large input norms ||=;|]- Whether or not group is underrepresented has less influence. In the next section we provide a new perspective on Relli and the underlying causes of unfairness in DPSGD.
DISPARATE IMPACT IS CAUSED BY GRADIENT MISALIGNMENT
Clipping in DPSGD introduces two types of er- to the clipped batch gradient Íg- It will generally have different norm than [| and be misaligned compared to the SGD batch gra- dient, РB- At high level, gradient misalign- ment poses more serious problem the con- vergence of DPSGD than magnitude error, as illustrated in Fig. Changing only the norm means gradient descent will still step towards the (local) minimum of the loss function, and any norm error could be completely compen- sated for by adapting the learning rate 7/I- In contrast, a misaligned gradient could result in step towards significantly worse regions of the loss landscape causing catastrophic failures con- vergence. Misaligned gradients add bias which compounds over training, as underrepresented or complex groups are systematically clipped. For comparison, adding noise to the aggregated gradi- ent does not add bias, so noise errors tend cancel out over training. We aim to quantify the relative impact of these effects and how they contribute to the excessive risk.
02.
g8
gB
|dall Tasl
g
0,
Figure I: Direction errors from clipping are more severe than magnitude errors over the course of training and can lead to suboptimal convergence.
We can distinguish the effects of clipping by rewriting the clipped batch gradient as gn) for orthogonal matrix MB such that ÿn and Magn are colinear. As proof of concept that gradient misalignment is the more severe error we compared models trained by taking steps
@n=Ma
|
Tos
|لها|| [| 9B vs. MøgB with no noise added. These represent magnitude errors and direction errors from clipping, respectively. The models were trained on MNIST with class 8 un- dersampled, and the results compare the typical class 2 to the underrepreseented class 8; full details provided in App. B As seen in Table [ direction error is more detrimental to performance than magnitude error. In particular, it disproportionately increases loss and decreases accuracy on the underrepresented class 8.
4

---

Published as a conference paper at ICLR 2023
Table I: Effect of direction vs. magnitude error on MNIST with class undersampled. The results compare accuracy and loss on the typical class 2 to the underrepresented class 8.
TYPE OF ERROR
Acc 2
Acc 8
Loss
Loss 8
MAGNITUDE
99.0
93.5
0.002
0.005
DIRECTION 96.8
84.1
0.076
0,518
Our first theoretical result quantifies the excessive risk from the two types of errors, and follows from Taylor expansion of the expected loss using 9s in the gradient descent update compared to РB. The excessive risk from magnitude error comes from comparing 9B gradient misalignment is isolated by comparing AB=MB
| ||ae|| 9B. while that of
| 9B)
to ||
9B (see Fig.
Consider the ERM problem with tvice-differentiable loss with respect to the model parameters. The excessive risk due clipping experienced by group E [K] at iteration is approximated up to second order in
Proposition 2.
||0
02l as
Relip = (9D., E (1
[gal]]
+ oZ TE [(
92l1 92ll
- 9 H
(Raaee
19281
9B
+ The (D E
|لall Igaal (gB - (9n-MB9R))
Lin [igs
((Mngn)* Hy H2 (M
(R
where gD., ID. denote the average non-clipped and clipped gradients over group a at iteration t, Hi refers the Hessian over group a, and MB is an orthogonal matrix such that ğø and M MBgB are colinear. The expectations are taken over batches of data.
Note that when the magnitude error is zero for all batches, 0 as expected. As well, when there is no gradient misalignment then MB is the identity matrix for every batch, and so Rdi = O.
We provide derivation in App. |
|, we have that Ra nhe
To determine the characteristics of groups that will have unfair outcomes from clipping in DPSGD we can distill a simpler condition for when INdr > Righ: Tran et al. (2021a) already provide such a condition for clipping overall, however it does not effectively account for the danger of gradient misalignment. Their condition sufficient, but not necessary. and some of its looseness stems from the inequality x= y 2 -I| -|lll|ll/| used to convert all terms in Relip into expressions involving group gradient norms. This approach loses information about gradient direction. We instead propose cos O, where 0 = L(x,y)-
tighter analysis of Ielir Ie using x² ||=||| ||
Proposition 3. Assume the loss is twice continuously differentiable and convex with respect to the model parameters. As well, assume that T) S (maxкe(k) Ax) 1 where N is the maximum eigenvalue of the Hessian H. For groups a, b E [K]. Rdir Rd if
E [[@BBl(cos 87 cos (oo)%))]
llop llab.ll
E [IāBl] 0% cos 0h:)]
B|llan| llp..
(4)
where 0 =/ (B) and 0%:3 = (gD, ÿB) for group t: [K). Furthermore, the bound is tight.
contains our proof. Prop- 3 shows that if the clipping operation disproportionately and sufficiently increases the direction error for group a relative to group b. then group incurs larger excessive risk due to gradient misalignment.
App.
The lower bound for Rar - Regir inferred from Eq, is tight, and in our experiments we empirically show that it is close to saturation in a typical case. Hence, when the direction errors for groups and b are small (i.e. we expect that 0; x 8i for i a, b), we have that Rdir Ryji ~ O regardless of the size of llgp. relative to [lg,, ll. It follows that clipping does not negatively impact excessive risk if gradients remain aligned. On the other hand if direction error is not close to zero, large group gradient norms do exacerbate the error in direction, as the dominant term of Relir scales with || ||-
The excessive risk in Eq. 2 is evaluated at the end of training, whereas Props. 1 anddd estimate it per-iteration. Fig. demonsttattes that the full impact of clipping errors may not felt per-iteration, but only at convergence. Indeed what matters to the end user is how fair the final model is, not how fair any intermediate training step is. However, it is not possible to attribute overall excessive risk to the per-iteration terms Rdir R. and Rroise since the optimal 8 used in the expansions of Props. Tand [2] differ at each iteration, and do not equal the overall optimal 6*. Still, Table demonstrates that gradient misalignment is the main cause of disparate impact, seek method prevent it.
5

---

Published as a conference paper at ICLR 2023
Rverage
Clp
Clp and Scale
Average and Add Noise
OE
20
Clp
(b) In DPSGDD-Gloal-AGE Adapt scaling alone docs not guarantec finite sensitivity, so gradients with norm above Z are clipped to Co (DPSGD-Globs clips large gradients to rather than Co).
(a) Left: Per-sample gradients colored based group membership. Top: Local clipping in DPSGD Bottom: Global scaling in DPSGD-Global.
Figure 2: Illustration of privatization steps in DPSGD, DPSGa-Global, and DPSGD
5 PREVENTING GRADIENT MISALIGNMENT IN DPSGD
Our results so far show that gradient misalignment due to clipping is the most significant cause of un- fairness in DPSGD. Logically, Rdir would be min- imized if privatization left the direction of 9B un- changed. A promising avenue is to scale down all per-sample gradients in batch by the same amount. This is the approach taken by DPSGD-Globil (Bu et al. 2021), which was recently proposed to im- prove the convergence of DPSGD, and has not been discussed in the context of fairnsss before. Our theo- retical results suggest that global scaling will reduce disparate impact.
Algorithm 2 DPSGD-Gllbal( (ooobal((Adap))
Require: Iterations T. Dataset D, sam- pling rate q. clipping bound Co. strict clipping bound Z 2 Co- noise multipliers Ø1, (02), learn- ing rates ne. (clipping learning rate nz. threshold 2 0)
Initialize Og randomly for in O..... . do
B t Poisson sample of D with rate q for (m4, v/) in B do
9: < Vol(fo, (xx).
DPSGD-Global (Alg. ( aims to preserve privacy by scaling gradients as Øi 79: 0 <<>= course, scaling alone is insufficient to ensure per- sample gradients have bounded sensitivity. How- ever, supposing that there were strict upper bound Z 2 |lgi|iii E D, then scaling all gradients by == Co/Z would guarantee bounded sensitivity of Co for each 9i (Fig. 22a. Given sufficient smooth- ness of the loss function, for any sample of data there will be such an upper bound max D [ but deter- mining it exactly cannot be done in a differentially private manner. DPSGD-Global sets Z as hyper- parameter without looking the data, in the same way Co is chosen in DPSGD. If Z fails to be a strict upper bound, any gradients with [1 > Z are discarded to guarantee a bound on sensitiv- ity. When Z is chosen sufficiently large, no gradients are discarded and gradient misalignment is avoided. The drawback of large Z is that the scaled gradients G. will become small and conver- gence of gradient descent may be hindered.
Co
|9 < Z
7 < 1. Of
Z
%
| Z
91 + 79h
(ErEB 9: + +N of
GB +- 1BT
0.+1 <- 0₁ n18B
(Adaptively set Z):
b, +- {i |196|1 T Z}|
b
B (be NO oî))
Z - exp(- + by)
In addition to identifying that DPSGD- pose two modifications to improve its utility. First, we note that discarding gradients with l| Z can exacerbate disparate impact as it is often underrepresented groups that have large gradient norms (Xu al. (02T). Instead, we clip large gradients to have norm Co. which preserves more informa- tion while maintaining finite sensitivity (Fig. 2b).. Second, rather than choosing Z as hyperpa- rameter, we adaptively update Z to upper-bound max llg.]l. When Z is larger than all gradients it should be reduced to scale down gradients less, but if gradients are being clipped, Z should be increased. can be updated each iteration by privately estimating b,, the number of gradients in B that are larger than Z times a tolerance threshold 2 0. Since b, is a unit sensitivity quantity estimate it privately as b. 1
has the potential to reduce disparate impact, we pro-
(he + NV( oB)). Then, we use the geometric update rule
7 <- Z exp( -1z b.) with a learning rate 7/ (ef. (Addre al. 2021)). When all samples

---

Published as a conference paper at ICLR 2023
have gradient norm less than equal to T Z, then in expectation b, = 0 and Z is decreased by factor of exp( (17))) Alternatively, Z is increased when b, 12. which occurs with probability 0.977 when hy
[A] 72 + 20g As result, with high probability the algorithm will not have more than B nz + 20² gradients with norm exceeding T ZZ
We call the method with our two alterations DPSGD-Global-Adune shown in Alg. 2 in red paren- theses. We empirically find in Sec. 6 that both global approaches improve fairness compared to prior methods, and that DPSGD-Global-Aaap has improved utility over DPSGD-Global. While the alterations are minor, our main contributions are elucidating that gradient misalignment is the main cause of disparate impact, and identifying that global scaling can prevent this problem.
Both global methods apply the sampled Gaussian mechanism Mironov et al. 2019) to gradient norms with a sensitivity of Co. and hence are amenable to the same DP analysis DPSGD itself. In DPSGD-Global-Adie
the additional step of privately estimating the number of gradients with norm larger than t Z must be accounted for in the overall DP guarantee via a composition of sampled Gaussian mechanisms. From the analysis in (Mironov et al., 2019), DPSGD-Global-Adaap (c, 6)-DP for any 01 02 > 0, where e can be determined numerically given 8. However, our adaptive method is empirically not sensitive to the exact count bg, so a relatively large amount of noise can be used, see (Andrew et al.) 202T) for comparison. In practice we used 02 = 100, which produced a negligible additional cost in the overall privacy budget.
Finally, we note that other approaches for mitigating unfairness, specifically DPSGD-F (Xu et al, 2021) and that of Tran et al. (2021a), require protected group labels for the training set. Collecting such labels may expose individuals to additional privacy risks in the case of security breaches, or may be prohibited in practice. Both global methods have the advantage of not requiring protected group labels for training data, and treat all training examples on an equal footing, thereby avoiding disparate treatment, while disparate impact is mitigated by reducing gradient misalignment.
EXPERIMENTS
In experiments provide evidence that gradient misalignment is the most significant cause of unfairness, and demonstrate that global scaling can effectively reduce unfairness by aligning gradients. Our code for reproducing the experiments is provided as supplementary material.
6.1 EXPERIMENT SETTINGS
For all experiments, full details are provided in App. B We use an artificially unbalanced MNIST training dataset where class 8 only constitutes about 1% of the dataset on average, and protected groups are the classes. We also use two census datasets popular in the ML fairness literature, Adult and Dutch (van der Laan 2000), preprocessed as in Le Quy et al. (2022). For both datasets, "sex" is the protected group attribute which is balanced between males and females. Finally, use the CelebA dataset (Liu et al. 2015) for binary classification on the gender label. The protected group attribute is whether the image contains eyeglasses. Images with eyeglasses comprise 12% of male images but only 2% of female images, and are more difficult to classify accurately.
We compare both global scaling techniques (Alg. 2 against two methods designed reduce unfair- ness, DPSGD-F (Xu et al. (021)) (Alg. 3) and the Fairness-Lens method (Tran et al. 202 (Alg. A.. both of which are reviewed in App. B.5 Each method's effectiveness in removing disparate
impact is measured using privacy cost Ta (Eq. D. and excessive risk R₂ (Eq, 2 per group, as well as the privacy cost gap Ta and excessive risk gap Ra, between groups. For MNIST, the underrep-
resented group 8 is compared to group 2 (Xu et al., (02T). All experiments were run for 5 random seeds, and results are given as means + standard errors.
For MNIST and CelebA, all methods train convolutional neural network with two layers of 32 and 16 channels, 3x3 kernels, and tanh activations. Adult uses an MLP model with two hidden layers of 256 units, while Dutch uses logistic regression model. For all private methods, we use an RDP accountant (Mironov 2017) with = 10 6 As a baseline, for DPSGD we set o = 1, C. = 0.5 for Adult, σ 1, Co 0.1 for Dutch, and 0.8, Co 1 for image datasets. With this, training 20 epochs for tabular datasets, 60 epochs for MNIST and 30 epochs for CelebA gives e = 3.41 for Adult, 6 2.27 for Dutch, e 5.90 for MNIST, and e 2.49 for CelebA. DPSGD-F has negligibly
7

---

Published as a conference paper at ICLR 2023
higher e, while our method achieves the same guarantees to three significant digits. Complete hyperparameters are given in App. B.2
6.2 RESULTS
Table 2: Performance and Faimess metrics for MNIST
METHOD
Acc 2
Acc
X2
X2.8
Loss
Loss 8
Ra
Rs
Ras
NON PRIVATE
98.020.1
84.3=1.1
0.06:20.00
0.32=0.01
DPSGD
89.010.11
26.320.4
8.9.0.1
57.911.3
48.9-13
2.56:10.04 0.6710.01
0.61:0.01
2.24
1.6310.03
DPSGD-F
89.510.1
3..4
8.510.1
21.9113
164=13
0.65.10.11
1.47:0.04
0.59
1.1610.03
0.56.10.04
DPSGD-G.
90.6+0.2
02.0#26
7.440.1 22.2+2.6
14.8=2.7 0.34
1.31=0.04
0.28=0.01
0.99
0.71+0.04
DPSGD-G.-A.
92.0+0.2
65.5+122 6.0 18.8+0.9
12.8=0.8 0.35+t0.11
1.20==0.04 0.29=0001
0.89+0.03
0.60++o.03
Table 3: Performance and Fairness metrics for CelebA
METHOD
ACC W/O
Acc W
www.
Loss W/O
Loss W
Rwzo
Rw
Roon.
NON PRIVATE
95.8+0.1
89.7#0.4
0.11=0.00
0.24+0.01
DPSGD
86.5+0.2
74.0=0.6
9.3=0.3
15.7#0.6
6.4+0.7
0.60=0.01
1.34+0.05
0.49+0.01
1.10#0.05
0.61=0.05
DPSGD-F
91.8+0.2
79.7
4.0=0.2
10.0#0.6
6.0#0.6
0.32=0.01
0.97
0.21+0.01
0.73+t0.0
0.52=0.04
DPSGD-G.
93.1+0.3
82.5+0.5
2.7=0.3
7.240.6
4.5+0.5
0.21=0.01
0.57+0.05
0.10#a.01
0.33+0.05 0.24-0.04
DPSGD-G.-A
94.2+0.1
84.5+0.2 1.6=0.2
5.240.5
3.640.4
0.17=0.00
0.45+0.01
0.06+0.00
0.21 0.15=0.01
Tables 2 and 3 display the accuracy and loss, along with privacy cost and excessive risk metrics re-
spectively for MNIST on classes 2 and 8 and CelebA on group W with eyeglasses, and group W/O without Recall that higher is better for accuracy, but for all other metries lower is better. Accord- ing to the one-sided Wilcoxon signed rank test, both global methods have statistically significant (p 0.05) improvement over DPSGD on accuracy, loss, privacy cost gap, and excessive risk gap. Similarly, DPSGDDGiobbl-Adaag has statistically significant improvement over DPSGD-Global and DPSGD-F on accuracy and loss. The same conclusions hold for the Adult dataset, and also for Dutch with the exception of DPSGD-Global being comparable to DPSGD in loss, see Tables 4 and S in
App. B.7 We infer that the global scaling technique mitigates unfaimesss, while our modifications further improve utility.
Not only are final model metrics improved. we see that DPSGD- DPSGD-Global-A to non-private SGD in Fig. 3 for Dutch (ef. Figs. 8 g
Ellobal-Adap trains more similarly and T0 in App. B.7 for Adult, MNIST, and CelebA). This shows the average train loss per iteration, and average norm of the batched gradient. The difference in loss for groups in DPSGD-Global-Adap resembles that of the non-private method more closely than other methods. Consider Fig. 3 (bottom), where the group M average norm does not converge to 0 in DPSGD, a problem which is somewhat improved in DPSGD-F, while for FairLens the group F norms become much larger. In DPSGD-GII BDSGD-Global-aoe Global-Adap the norms for both groups remain small, but importantly the gap between groups is reduced.
'hhe FairLens method (Tran al. 2021a) is not compared for MNIST and CelebA because the author- provided code only handles binary classification problems, and does not scale to image datasets.
Spedoo
Epodes
Sparta
Speda
COOCTT
Figure 3: Dutch dataset. Top: Train loss per epoch. Bottom: [|ga|] averaged over batches per epoch.
8

---

Published as a conference paper at ICLR 2023
DPSGD
FaiLLens
DPSG0-
DPSGD-Gleb
2.000
21000
5.000
30000
0.000
1000
1000
1.00
3.000
50005
50055
1000
00000
4100
Mog/Rbe 0w000ve
0:0
0.000
1100
0000
080
6.00
6000
5000
6000
Danatorn
Tamilooa
Serstorra
Figure 4: Adult dataset. Top Rdir, excessive risk due gradient misalignment per group. Bottom R excessive risk due to magnitude error per group. See Prop. 2 for definitions.
Fig. shows the excessive risk terms due to gradient misalignment Ielr, and magnitude error It, for Adult at each iteration (see Figs. II 12 and in App. B.7 for Dutch, MNIST, and CelebA).
We see that global clipping almost completely removes direction errors as intended, but as a tradeoff increases magnitude error. However, we have argued that direction error is the more severe cause of disparate impact over the course of training, which is borne out by the results in Tables [ and 3 as well as 4 and 5 in App. B.7 Direction errors introduce bias which accumulates, whereas magnitude errors do not alter the convergence path, and noise errors add zero bias and tend to cancel out.
6.3 TIGHTNESS OF LOWER BOUNDS
Gippinng Dippseat Imspect vo Lower Bearal
Disadiio Dispansis Impoaci vs Lower Bound
In Fig. we compare the usefulness of the lower bound of Re Relii given in the proof of Theorem 3 in Tran et al. 222 aa)
6010
lowe bound
0000
6000
-0.00
to the lower bound we give in Prop 3 for
0.10
Rdir - periences disparate impact due to clipping, the lower bound from Tran et al. (2021a) is negative for each iteration, failing to cap- ture that Reliig > Re On the other hand, the true values of R Ryfi are closely lower-bounded in our version, such that disparate impact due to direction error is accurately predicted. The assumptions of Prop. 3 are discussed in App. B.6
Rdir. We see that while group 0 ex-
-0.30
Roie. Edio.
200
900
760
1000
850 020
760
Patrtton
Figure 5: Comparison of excessive risk gaps R to lower bounds on Adult. Left: Rg. due to clipping er- ror, and bound from Tran al. (2021a). Right: Ro, due to direction error, and bound from our Prop.
7 DISCUSSION
In this paper we identified a core cause of disparate impact in DPSGD, gradient misalignment, and proposed a mitigating solution, global scaling. We empirically verified that global scaling is successful in improving fairness in terms of accuracy and loss over DPSGD and other fair baselines on several datasets. Our method has additional advantages over other fair baselines in that it does not require the collection of protected group data for training, does not involve disparate treatment, and it removes disparate impact for all groups simultaneously.
It is important to note that while global scaling is effective at reducing disparate impact by aligning gradients, it does not resolve the privacy-utility trade-off, which exists in any private mechanism fundamentally. Nor does it ensure that the model is non-discriminatory towards subgroups, only that adding privacy does not exacerbate unfairness. For example, biases in data collection or dis- criminatory modelling assumptions can cause disparate impact within the non-private model. which overlaying global scaling will not cure. Any models trained with global scaling should still be vali- dated for fairness independently; failure to do could unknowingly cause additional unfairness.
9

---

Published as a conference paper at ICLR 2023
REFERENCES
Martin Abadi, Andy Chu, lan Goodfellow, Brendan McMahan, llya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pp. 308-318, 2016.
John M. Abowd. The U.S. Census Bureau Adopts Differential Privacy. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 2867, 2018. ISBN 9781450 1500555555...
Mohammed Adnan, Shivam Kalra, Jesse C. Cresswell, Graham W. Taylor, and Hamid R. Tizhoosh. Federated learning and differential privacy for medical image analysis. Scientific reports, 12(1): 1-10, 2022.
Galen Andrew, Om Thakkar, Brendan McMahan, and Swaroop Ramaswamy, Differentially Pri- vate Learning with Adaptive Clipping. In Advances in Neural Information Processing Systems, volume 34, pp. 17455-17466, 2021.
Eugene Bagdasaryan, Omid Poursaeed, and Vitaly Shmatikov. Differential privacy has disparate impact on model accuracy. In Advances in Neural Information Processing Systems, volume 32, pp. 15479-15488, 2019.
Zhiqi Bu, Hua Wang, Qi Long, and Weijie Su. On the Convergence of Deep Learning with Differential Privacy. arXiv preprint arXiv:2106.07880. 2021.
Joy Buolamwini and Timnit Gebru, Gender Shades: Intersectional Accuracy Disparities in Com- mercial Gender Classification. In Proceedings of the 1st Conference on Fairness, Accountability and Transparency, volume 81, pp. 77-91, 2018.
Nicholas Carlini, Chang Liu, Úlfar Erlingsson, Jemej Kos, and Dawn Song. The Secret Sharer: Evaluating and Testing Unintended Memorization in Neural Networks. In 28th USENIX Security Symposium, pp. 267-284, 2019.
Hongyan Chang and Reza Shokri. On the privacy risks of algorithmic faireess. In 2021 IEEE European Symposium on Security and Privacy, pp. 292-303, 2021.
Kamalika Chaudhuri, Claire Monteleoni, and Anand D. Sarwate. Differentially Private Empirical Risk Minimization. Journal of Machine Learning Research, 12229)1069--1099 2011.
Xiangyi Chen, Steven Z. Wu, and Mingyi Hong. Understanding Gradient Clipping in Private SGD: A Geometric Perspective. In Advances in Neural Information Processing Systems, volume 33, pp. 13773-13782, 2020.
Christopher A Choquette-Chie -Cho, Natalie Dullerud, Adam Dziedzic, Yunxiang Zhang, Somesh Jha, Nicolas Papernot, and Xiao Wang. CaPC Learning: Confidential and Private Collaborative Learn- ing. In International Conference on Learning Representationss 2020.
Alexandra Chouldechova and Aaron Roth. A Snapshot of the Frontiers of Fairness in Machine Learning. Commun. ACM, 63(5):82-89, 2020. ISSN 0001-0782.
Rachel Cummings, Varun Gupta, Dhamma Kimpara, and Jamie Morgenstern. On the Compatibil- ity of Privacy and Fairness. In Adjunct Publication of the 27th Conference on User Modeling, Adaptation and Personalization, pp. 309-315, 2019, ISBN 9781450367110.
Cynthia Dwork and Aaron Roth. The Algorithmic Foundations of Differential Privacy. Found. Trends Theor. Comput. Sci., 9(3-4):211-407, August 2014. ISSN 1551-305X. doi: 10.1561/ 0400000042.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating Noise Sensitivity in Private Data Analysis. In Theory of Cryptography, pp. 265-284. Springer Berlin Heidelherg, 2006. ISBN 978-3-540-32732-55
Michael D. Ekstrand, Rezvan Joshaghani, and Hoda Mehrpouyan. Privacy for All: Ensuring Fair and Equitable Privacy Protections. In Proceedings of the 1st Conference on Faimess,, Accountability and Transparency, volume 81, pp. 35-47, 2018
10

---

Published as a conference paper at ICLR 2023
Tom Farrand, Fatemehsadat Mireshghallah, Sahib Singh, and Andrew Trask. Neither Private Nor Fair: Impact of Data Imbalance on Utility and Faimnsss in Differential Privacy. In Proceedings of the 2020 Workshop on Privary-Preservingg Machine Learning in Practice, pp. 15-19, 2020.
Craig Gentry. Fully Homomorphic Encryption Using Ideal Lattices. In Proceedings of the Forty- First Annual ACM Symposium on Theory of Computing, pp. 169-178, 2009.
M.F. Hutchinson. A stochastic estimator of the trace of the influence matrix for Laplacian smoothing splines. Communicationn in Statistics Simulation and Computation, 19(2):433 450, 1990. doi: 1001080003610001908888888888
Matthew Jagielski, Michael Kearns, Jieming Mao, Alina Oprea, Aaron Roth, Saeed Sharifi Mal- vajerdi, and Jonathan Ullman. Differentially Private Fair Learning. In Proceedings of the 36th International Conference Machine Learning, volume 97, pp. 3000-3008, 2019.
Matthew Jagielski, Jonathan Ullman, and Alina Oprea. Auditing differentially private machine learning: How private is private SGD? Advances in Neural Information Processing Systems, 33: 22205-22216, 2020.
Mimansa Jaiswal and Emily Mower Provost. Privacy Enhanced Multimodal Neural Representations for Emotion Recognition. Proceedings of the AAAI Conference Artificial Intelligence, 34(05): 7985-7993, 2020. doi: 20.1160/aaii.v34ii0 v34105.63077
Shivam Kalra, Junfeng Wen, Jesse C. Cresswell, Maksims Volkovs, and Hamid R. Tizhoosh. ProxyFL: Decentralized Federated Learning through Proxy Model Sharing. arXiv preprint arXiv:2111.11343, 2021.
Tai Le Quy, Arjun Roy, Vasileios Iosifidis, Wenbin Zhang, and Eirini Ntoutsi. A survey on datasets for fairness-aware machine learning. WIREs Data Mining and Knowledge Discovery, pp. e1452, 2022.
Ziwei Liu, Ping Luo. Xiaogang Wang. and Xiaoou Tang. Deep learning face attributes in the wild. In Proceedings of International Conference on Computer Vision, December 2015.
H. Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Coamunication-EEfficie Learning of Deep Networks from Decentralized Data. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, 2017.
Ninareh Mehrabi, Fred Morstatter, Nripsuta Saxena, Kristina Lerman, and Aram Galstyan. A Survey on Bias and Fairness in Machine Learning. ACM Comput. Surv., 54(6), 2021.
Ilya Mironov. Rényi differential privacy. 2017 IEEE 30th Computer Security Foundations Sympo- sium (CSF), Aug 2017. doi: 10. 1091ccsf......111...
Ilya Mironov, Kunal Talwar, and Li Zhang. Rényi Differential Privacy of the Sampled Gaussian Mechanism, arXiv preprint arXiv: 1908. 10530, 2019.
Hussein Mozannar, Mesrob Ohannessian, and Nathan Srebro. Fair learning with private demo- graphic data. In International Conference on Machine Learning, pp. 7066-7075. PMLR, 2020.
Milad Nasr, Shuang Songi, Abhradeep Thakurta, Nicolas Papemoti, and Nicholas Carlin. Adversary instantiation: Lower bounds for differentially private machine learning. In 202/ IEEE Symposium on Security and Privacy, pp. 866-882. IEEÉ, 2021.
Venkatadheeraj Pichapati, Ananda Theertha Suresh, Felix X. Yu, Sashank Reddi, and Sanjiv Ku- mar. AdaCliP: Adaptive Clipping for Private SGD. arXiv preprint arXiv:1908.07643, 2019.
David Pujol, Ryan McKenna, Satya Kuppam, Michael Hay, Ashwin Machanavajjhala, and Gerome Miklau. Fair decision making using privacy-protected data. In Proceedings of the 2020 Confer- ence on Fairness, Accountability, and Transparency, pp. 189- 2020.
Cuong Tran, My Dinh, and Ferdinando Fioretto. Differentially Private Empirical Risk Minimization under the Fairness Lens. In Advances in Neural Information Processing Systems, volume 34, pp. 27555-27563 2021a.
11

---

Published as a conference paper at ICLR 2023
Cuong Tran, Ferdinando Fioretto, and Pascal Van Hentenryck. Differentially Private and Fair Deep Learning: A Lagrangian Dual Approach. Proceedings of the AAAI Conference on Artificial Intel- ligence, 35(11))9932-99) 9939, May 2021b.
Paul van der Laan. The 2001 Census in the Netherlands Integration of Registers and Surveys. In Seminar Censuses after 2001, 2000.
Depeng Xu, Shuhan Yuan, and Xintao Wu. Achieving differential privacy and fairness in logistic regression. In Companion Proceedings of The 2019 World Wide Web Conference, pp. 594-599, 2019. doi: 10. 011114533355003331755555
Depeng Xu, Wei Du, and Xintao Wu. Removing Disparate Impact Model Accuracy in Differen- tially Private Stochastic Gradient Descent. In Proceedings of the 27th ACM SIGKDD Conference Knowledge Discovery & Data Mining, pp. 1924-1932, 2021.
Andrew Chi-Chil Yao. How to generate and exchange secrets. In 27th Annual Symposium on Foundations of Computer Science, pp. 162-167, 1986.
A THEORETICAL RESULTS
A.1 PROOFS MAIN RESULTS
In this section we provide complete proofs for our theoretical contributions.
Proposition 2. Consider the ERM problem with twice-differentiable loss É with respect to the model parameters. The excessive risk due clipping experienced by group [K] at iteration is approximated up to second order in |10.-1
0.1l
Relip ni (9D.. E [11
[0 1an
9B
[(
|8 2
H 9B
(Ra
mag
E mi (gD.: 192
(gB
MBBB)
Gel 98
((Mgge)* H (Mag8)- 9 Hi (
(R
where 9D., 9D. denote the average non-clipped and clipped gradients over group iteration Hi refers to the Hessian over group a, and MB is an orthogonal matrix such that ğB and MBgB are colinear. The expectations are taken over batches of data.
We remark that assuming twice-differentiable loss is mild requirement in machine learning where most loss functions and models are designed to be smooth enough for backpropagation.
Proof.
The proof is based Taylor expansion of the excessive risk, as in Tran et al. (2021a).
Let MB be an orthogonal matrix such that ÎB = MB and JB and [[ 9B are colinear, and the former characterizes direction error, and the latter error magnitude. The excessive risk due to error in magnitude for group a at iteration then given by
[[g [|gs|| ge). In this way, |l
|
||
| 1/ |9
E
C
0c
9B; Da
- L (0: 17:8;; Da)
the cost in loss using the update vector tion is over randomness of batch sampling.
|g [ On rather than 9n. where the expecta- We perform second-order Taylor expansion of
C 0. n
g8: Da)] and take the expectation to get that
|gall
| |
v E
| |g
2 9
L 0r 7/t
yn; Da.
(O,;; Da) mh gn. E
gn
H
gg
12

---

Published as a conference paper at ICLR 2023
Hence,
ni
Rel 1 9D 9D) +
(Big
Elg HP gsl)
2
=n0 9D)
EE
[E
Hg
Elght H H)lll)
9 12
1t
JD.1
1
9B
1gn
Hi 9B
99
l
+ 7)
9D
19B
9B
2
119
12
9
H 9B
Th
9D 9D
E
9
9
+
ME
2
E
1g
9B
H 9B
E
T Hi 9B]
1
Vi
| 11
9Da. E +
|1988l
9D
+
2
E
[9
-E
|198
1|
9
T
H
9B
+ nE
Th
9D. 9D
E
19
9B
2
IE
|19
g 111
(Ru
1
"i
|ل
+ 1/1
g
|9
9B
gD
+
2
E
[[gh
E
|9
gb
Hign)
(Re
We can also further simplify Rlir by using that ğD Elgal. ūB linear transformation
MB
[āel [1aa]
9B
and that My is
Rdir
1/
JD.
E
CB
BB
MB
|
JB
199
|g
nk
1g
gB
+
2
1
(MBgg)"
H2 (MB98)
||g
1
In
H 9B
(5)
|ooll
(gB MB98) 1)
|
2
1h
9D., E
2
E
||gn|
((MBgB)" (M - u 9B)
Proposition 3. Assume the loss is twice continuously differentiable and convex with respect to the model parameters. As well, assume that tt S [maxKE]]] Ax)-1 where d the maximum eigenvalue of the Hessian H For groups a, b E [K], Rdir Rd if
1gD.
Bll@el [3]
E [[]ll(cos cos [000%)] >
[1@8 (cos 0g - cos Ø3)] +
(6)
[gp_
[gp__
where 8 = L(DD. (B) and - -(gD, 9B) for group l k [K]) Furthermore, the bound is tight.
Again, requiring a twice continuously differentiable loss is mild requirement. However, when neural networks are used most loss functions are non-convex. Empirically we see in Fig. 5 that the lower bound can still apply in practice. The requirement on the learning rate is under the control of the practitioner, and we have verified that practice can be satisfied.
Proof.
13

---

Published as a conference paper at ICLR 2023
This proof follows some steps presented in Lemma 2 of Tran et al. (021a). condition for when the following is positive,
We seek simplified
Re Rg
11t
2D
(9B
MB9E))
T/t (D.,
98
(9B
MB9E)
9
|
7i
19 ((MRg)) H& (MBgn) -3 Hz
19911
n
1|?
((Mag8)" (MBgE) H3
2
||9
Looking one of the inner product terms, we use that (x, y) ||>|||yy|| cos(a,,) y) and linearity of expectation to obtain
1g |
(gn Magaa)
|laal
(gD.,, gn) - (gD., Mnge))
(D.:
=
|9g
|g |gs||
= -1g0, ||E
(Ilgsl) cos cos(gD..
| cos Magn))
= -1 [I [I@gll(cos cos cos0
where 8% = L(gn,, 9n) and 8% = <(p.. Mggn) = L The last equality follows from definition of M such that ýn and Mggn are aligned and || || = ||Mggell
We can also get bound on the difference in conjugates of the Hessian, ((Magn)² (MMnggn)))))) 9f |
Note that since we assume the loss is convex, the Hessian Hद is positive semi cemi-definite such that x HH that [xx"" Hg 2 0 and so using linearity of expectation,
x 2 0 for all vectors It follows
|gel |
[g |1g8
E
(f
<
E
(Mags) Hj (M
(9)
Since is twice continuously differentiable we have that H3 is symmetric and hence x H² < |||l=r||2 where >a is the maximum eigenvalue of Hy. We then again use that || = |l and linearity of expectation to obtain
Lg |
E
((Mag)) Hy - - H8
< Ax
[|@B 12]
(10)
Similar analysis gives that E
1ea 19
(M (
> - Bllga
Combining the above, it follows that
Rdir Redir nt (Il9D. [ [llā (Cosl 03 cos 0z)] - 11,,, |E [llãa (cos 0 cos 04:1)
vi
(11)
(Aa Ao E
2
and since we assume 7)t S maxxe Au
Relir Rdir 2 t/. (1lgp. E [lle (cos 0 cos 0%)
(12)
ll,,,
E [1|ōn (cos 8 cos o |Blla=
It follows that Adlir Regir when the following is satisfied:
||gn,
E B [2]
E [ (cos cos 03)]
E [llø (cos 0zz cos 03)] +
(13)
g9..
14

---

Published as a conference paper at ICLR 2023
Finally, to that the bound is tight simply note that the inequalities that were introduced can all be saturated simultaneously. In Eq. 9 we require that H gB = O, and in Eq. 10 we require (Mggg)* Hy (MBgB) = >a M I for each batch. These independent conditions can plausibly be met for some Hj 9B. and Mp. The only other inequality introduced is the assumption for the sake of achieving saturation.
M) S ma] Ac
which we can strengthen to 7): max Av
A.2 ALTERNATE DECOMPOSITIONS OF THE CLIPPING ERROR
In Sec. A.2 wc proposed decomposition of the clipped batch gradient into parts representing
magnitude and direction eπrоr, ОB=MB to demonstrate that direction error causes the most severe problems for the final performance of
19n 9B) We presented simple experiment in Table
models, and analysed the contributions of the two effects to the excessive risk in Prop. 2
However, the decomposition we used is not unique, and furthermore it is not possible to completely iso- late the two effects in the excessive risk analysis. For example, if we think of magnitude error the dif-
a
B
ference in loss between using update vector 9B and
M B
g
9B (? in Fig. 6). then it follows that the remain- ing error is due gradient misalignment, in other words, the difference in loss between using update del vector [92l 9B and ūB (A in Fig. 6). In this exam- ple, the error due to gradient misaligmment includes both error in direction and error in magnitude, while magnitude error is "pure".
lāell lasll
|! ||@all
g B
gB
Figure 6: Decomposition of steps between 9n and ğB-
R E[ 1h Isn
JB: Da) [(O. 7:9B: Da)], Relr = E|C(0, - Th9B; Da) - C(0: - Tk [gall [aal||
|
(14)
98: D.)]-
(15)
A different way of decomposing the clipping error is considering the direction error as the difference in loss between using update vector dg and Mag8 (a in Fig. (6) In this case, direction error is pure, Le. does not include difference in magnitudes. It follows that the remaining error is magnitude error, is the difference in loss between using update vector M agn and ÿn (3 in Fig. (6) Thus, the magnitude error in this case quantifies the difference in loss of scaling the already misaligned ğn,
Rair" = EE[((, M Da) - [(O, - T998 Da)l, R2mag * [E[ TkūB; D.) L(0, M: D.)].
(16)
(17)
In our analysis used the first decomposition where magnitude error be completely corrected by an adjustment of the learning rate, and direction error, what we hypothesized to be the largest cause of disparate impact, the remaining part of the clipping error. For completeness, by using the second decomposition we can derive alternative versions of Props. aaddd
Proposition 2a. Consider the ERM problem with twiie-ddfferentiable loss with respect to the model parameters. The excessive risk due to clipping experienced by group [K] iteration t is approximated up to second order in [|0.-1 0.1 as
Relip 17. (9D., E
[[
[10
[198|]
9B
+ " [(1
Iis 12
19s
12 9b
H
(R (Rmag*)
Im (9D. 9D MBgBl> + 2 E [(MB9B)' (M H.
(R
where 9D., ID. denote the average non-clipped and clipped gradients over group at iteration t, Hς refers the Hessian over group o, and MB an orthogonal matrix such that gB and M BgB are colinear. The expectations are taken over batches of data.
Proposition 3., Assume the loss is twice continuously differentiable and convex with respect to the model parameters. As well, assume that ft. & (maxкe(k) xx)- where 2E. is the maximum
15

---

Published as a conference paper at ICLR 2023
eigenvalue of the Hessian H For groups a, b E [K], Rdl R if
E g
E [ll98|] II (cos 0 cos (oss
E
[llg (cos 0 cos (bss
(18)
|gg.11
gg..
where 0h L(DD, 9n) and 0% L for a group k E [K].
We omit the proofs since they are directly analogous to those in App. A.1
B EXPERIMENTAL DETAILS
B.I DATASET PREPROCESSING
MNIST We use the artificially unbalanced MNIST training dataset where class is sampled with probability 9% such that class 8 only constitutes about 1% of the dataset average. This gives about 6000 data samples for each class, other than class 8 with about 500. The protected group values are the class labels. As in Xu et al. (2021), we compare models on how they treat the under-represented class 8 versus the well-represented class 2. The test set remains balanced, with approximately 1000 samples for each class. Data is scaled to be in the domain [0.1].
Adult The original Adult dataser" consists of 48,842 samples, reduced to 45,222 by removing all samples with missing values. The "final weight" feature is removed and the "race" attribute is discretized by (white, non- w. giving 5 numerical, 3 binary and 6 categorical features. The numerical features are normalized and the categorical features are one-hot encoded. As is typical in the faimess literature, choices for the protected attribute are "sex", "race" (binary) and possibly the discretized "age". We use "sex" by default. The classification label "income" (whether or not income exceeds $50,000). Prior to sampling, the Adult dataset is unbalanced with respect to sex with 30,527 males and 14,695 females. We sample balanced dataset as in Xu et al. (2021) ) with 14,000 females and 14,000 males on average.
Dutch The Dutch dataset van der Laan 2000 is preprocessed by dropping underage samples (14 and under) and removing the "weight" feature. As well, all "unemployed" samples are removed, as well as those with missing middle-level "occupation" for total of 60,420 samples. Specifically, "occupation" values 3,6,7,8 88 are considered middle-level. "Occupation" is then made binary by con- sidering values 4,5,9 low-level professions (0) and 1,2 high-level professions (1). The binary classification task is to predict "occupation", given the rest of the features. We consider "sex" as the protected group attribute. The processed dataset is balanced with respect to "sex" with 30,147 male and 30,273 female samples.
We 80/20 train/test split for both tabular datasets.
CelebA The CelebA dataset (Liu et al. 2015 consists of 64x64 pixel RGB images of celebrity faces, along with binary attributes describing each image. Many of these attributes are subjective, but we chose to use the most objective ones for training and group labels. We used the binary attribute "Male" for the classification target, which is roughly balanced at 84,434 males in 202,599 total images. The attribute "Fyeglasses" was our protected group label; although wearing eyeglasses in public typically does not construe sensitive information, we used this attribute because was objectively defined, and formed minority group which was empirically more difficult for models to classify accurately. Of the male images, 10,478 have eyeglasses, while only 2,715 female images have them. The rrainingvalidatioon/es split is provided with the dataset and is roughly in 80/10/10 ratio.
*The Adult datasct is available at atarchive..cc. httpi/iww.i......cd/m//iiiieeeee mwi..cd//mm//dattssts//tt
'The Dutch dataset also available through the work Le Quy et al. (2022) at
raw. www.githuhusercomeet.comm http://ntttttcoooaa///////aaaaae /ttp//aelquu//amessss dataset//mann/Duchh census/dutch census 2001. arff
Wee accessed this dataset wag.eaaalalaoooottttttteeseeeeee
16

---

Published as a conference paper at ICLR 2023
B.2 EXPERIMENT SETTINGS
We set a = 1, Cp = 0.5 for Adult, 0 = 1, Co 0.1 for Dutch, while for MNIST and CelebA, we set a = 0.8 and Co = 1. For DPSGD-F, the gradient noise is unchanged 02 = 0, and 01 = 100g- For Fairl.ens, we use regularization weights as in Tran et al. (2021a), \ = X2 1. For non-global methods, the learning rate is T/: = 0.01 for all iterations t and all datasets except Dutch which has
T = 0.8. For DPSGD-Global we have 7p = 1, Z 50 for Adult, 7t = 2, Z 1 for Dutch, T = 0.2, Z = 100 for MNIST, and 7/ = 0.1, Z = 100 for CelebA. For DPSGD-Global-Adaptt we have d2 10, Z 50, 72 0.1 for all datasets (the only exception is for CelebA Z 100), ")- 0.2, 7 = for Adult, = 1,T = 1 for Dutch, and 1) 0.1, = 0.7 for MNIST and CelebA.
All methods for all datasets use training and test batches of size 256.
Experiments were conducted on single TITAN V GPU machines. Approximately four GPU-days were used train all methods over five seeds for the four datasets.
B.3 IMPLEMENTATION DETAILS
The excessive risk terms for different groups (FE and Rooise in Prop. and R and Rddir in Prop- 2 all involve the Hessian of the loss function with respect to the model parameters. Calculating the Hessian as a matrix is computationally expensive, but more crucially requires memory that scales quadratically in the number of parameters. In the previous work studying Ra and Re Tran et al. (202Ta) use the PyHessian library to compute the Hessian as a matrix, and then used it to compute the products and traces needed for Ralip and Ra Because this approach incurs a high memory burden, the models trained were limited to small MLPs with a single hidden layer of 20 hidden units 7
In implementation, provided supplemental material, we avoid computing the Hessian matrix altogether which allows us to scale our experiments to common image datasets. For the four datasets, our models have parameter counts of N 91650 for Adult, N 120 for Dutch, N = 80522 for MNIST, and N = 120722 for CelebA, which would produce Hessian matrices with up to 14.5 billion entries. Instead, we compute the terms involving Hessians like gB through Hessian-vector products (HVPs) using the f quires memory comparable to that used when computing gradients for SGD.
with PyTorch 1.11. Using HVPs re-
For the trace of the Hessian matrix, also called the Laplacian, one possible approach that does not require realizing the entire matrix in memory is to compute HVPs with unit vectors to isolate each diagonal element: Tr(Hz)) = Ei=, If Hi 7, where T, is the ith column of the identity matrix. While exact, this approach requires N HVPs for each group a E K, of which there are at least two. Since this method is much too expensive for even the simple MLPs and CNNs we used, we instead employed Hutchinson's 's trace estimator (Hutchinson, 1990) to estimate Tr(Hş) = Eg[=" T Hy z]. This estimator is unbiased when is drawn from Rademacher distribution which we used, and only requires n HVPs per group, where n can be chosen as large as required for convergence of the estimate. In practice we used
100.
Additionally, whereas Tran et al. (2021a) replace dataset gradients gD and gD. with batch gradients when computing Ralii and [2nosse in Prop. we use the exact gn and gn. This eliminates easily preventable source of noise in our results.
To further reduce computation time, we only evaluate excessive risk terms (Hessians) every 50, 100, 200, or 200 iterations for the Adult, Dutch, MNIST, and CelebA datasets respectively.
B.4 DIRECTION ERROR IS MORE SEVERE THAN MAGNITUDE ERROR
As noted earlier, Prop. 2 only evaluates excessive risk for single iteration, not necessarily capturing how each of Ixlir and Tuing contribute to convergence and disparate impact over the course of train- ing. In order to evaluate the full impact of magnitude error and error due to gradient misalignment, we consider the difference in final loss and accuracy between models which have zero magnitude
"See implementation available at "ee documentation |pyonch.ory//mnntorc//ssaabb
17

---

Published as a conference paper at ICLR 2023
error and zero direction error in Table I In these experiments, consider zero magnitude error to be when |g = ||ga|| for all batches, and zero direction error to be when 9B and 0ø are aligned for all batches. Note that these definitions correspond to comparing update vectors JB and ||
[| 9B
for the zero magnitude error experiment, and comparing update vectors gn and ||ăا||| 11 ge for the zero
direction error experiment. These do not correspond to the definitions of Rdji and Ra in Prop. 2 but capture the intuitive definitions of direction and magnitude error. As described in App. A.2
while Relip = Rame + pdlir direction error and magnitude error cannot be purely separated with any definition of Rua Rdir.
B.5 BASELINE METHOOSS
We compared our approach DPSGD-Global-Adapp with its predecessor DPSGD-Global, which was designed to improve convergence, not fairness, as well as two approaches specifically designed to improve fairness.
DPSGD-Global (Bu et al. 2021) is presented in Alg. 2 and involves scaling almost all per-sample gradients by global factor rather than only scaling large gradients with ||gi|| > Co by norm- dependent factor. We say "almost all"", because scaling alone does not provide strict upper bound on the sensitivity, as required for an application of the Gaussian mechanism, see Fig. 2b The method additionally clips gradients to zero if their norm is above strict upper bound Z, which we found to be unnecessarily aggressive. Otherwise, the global scaling factor is Co/2 ZZ, which ensures that the sensitivity, namely Co, is finite. The advantage of DPSGD-Global is that it can better preserve the direction of In. especially when no gradients are clipped to zero. Hence, Bu et al. (202I) advocate for setting Z larger than || for any sample in the batch. The drawback of large Z is that all gradients are scaled down by a larger factor, so the convergence will be slowed unless the learning rate is increased compensate. Setting& Z is itself a challenge because we cannot inspect the batch to determine max, [|gi|| without accounting for that expense in our privacy budget. In Sec. 5 we described how BUSGD-Global-Adae
resolves these concern,, first by clipping less aggressively, to Co instead of O, while maintaining the same sensitivity, and second by adaptively setting Z each round according to a private estimate of how many gradients in a batch exceeded Z (using the tolerance threshold r).
Xu et al. (02T)) designed DPSGD-F as method for removing disparate impact caused by DPSGD by adaptively setting the clipping threshold for different protected groups. The method was based on the observation that negatively impacted groups tended to have large gradient norms which were affected more by clipping. Hence, the clipping threshold is raised for groups with larger gradient norms, based on a private estimate of how many gradients per-group have l| > Co. Given large enough batch sizes, the private estimate can be done with much more noise compared to the gradient update, so it does not meaningfully increase the privacy budget.
One drawback of this approach is that it requires group label information for every datapoint in the training set. In practice, especially in highly regulated industries, such information may not be permissible use or even collect. Collecting additional private information from data subjects on protected attributes can itself be a negative process and creates unnecessary privacy risks, One major advantage of DPSGD DPSGD-Global- Global-Aday is that it reduces unfairness without ever using group label information.
While each group is clipped using its own threshold, noise is added the batched gradient based on the sensitivity, determined by the largest group threshold. While all groups receive the same theo- retical privacy guarantee in terms of (c, 5), groups that are clipped to smaller thresholds may enjoy stronger empirical privacy guarantees, as determined for example by adversarial attacks (Jagielski jtt al. 2020 Nasr et al. 2021). Hence, it appears likely that DPSGD-F can produce unfairness the amount of privacy afforded to different groups.
DPSGD-F is shown Alg. Note that we present the algorithm as implemented in the author's codebase, not as written in their paper. In our experiments we use the version shown in Alg.
Our final baseline, referred to as "FairLens" was developed in (Tran et al. 222 la to reduce excessive risk from clipping, Adlip, and adding noise, Ra Regularization terms are added to the loss function in DPSGD that specifically target these sources of excessive risk. The source of Rooise was identified
18

---

Published as a conference paper at ICLR 2023
Algorithm 3 DPSGD-F
Require: Iterations T, Dataset D, sampling rate clipping bound Co, noise multipliers d1, d2,
learning rates 7
Initialize 0n randomly
for in 0, i do
B Poisson sample of D with rate q
for (z,,as, 3/4 in do
9i Val(Jo, (2:). 1/)
Compute per-sample gradients Count samples per-group above/below clipping bound
for inn [K] do
m <
{ | > CoHl
of p {i: |1g Σ Co
(m, 6t)
kE[K] f (m* KEIK]
+ +0(00,ff1)
Privatize unit sensitivity count vectors
{m² 0t
kE[K]] f- Imax(1n* 1.0,, max((==).0)) kE(K]
Postprocessing
mn = -Ene k] m
for i in [K] do
8t m + 0t
C Cp
1 + 7/|
th* 18*
for (si, 0s. yt) in B do
9: min (1.
C2 Tal1l
where k == a₁
>> Clip according to per-group clipping bounds
jB (EieB Fr + (1 (3
0.+1 f- 719B
to involve the per-group Laplacian of the loss with respect to model parameters a second order derivative whose computation scales poorly with model size. To avoid this difficulty, the authors used a stand-in for the Laplacian based on the distance of a point to the decision boundary.
Our implementation is directly based off of code made available by the authors on OpenReview at openreview. oppeneeview.ne/foruum net/forum Pid=7EFdodS Wee4, The version implemented in their code is shown Alg. and assumes there only two mutually exclusive protected groups, denoted and b. Hence, it is not applicable to the MNIST dataset. We also attempted to use this code for our CelebA experiments but found that the implementation did not scale to the simple CNNs used. Therefore, we omitted FairLens from the CelebA experiments.
B.6 VERIFYING ASSUMPTIONS ON LOWER BOUND
Nax Ligeveetue over Group leesiaass per lameiion
In Sec. 6.3 and Fig. 5 we compared the
fulness of our lower bound on Rei Indir from Prop. 3 to previous lower bound in the lit- erature. For our lower bound to be valid, the assumptions Prop. 3 should be satisfied. The first assumption, that the loss is twice contin- uously differentiable with respect to the model parameters, holds since the model architecture an MLP with tanh activations. However, the loss is not in general convex. The third assump- tion, that the inverse the learning rate upper bounds the largest eigenvalue of any group's Hessian, is checked empirically for each iter-
00
Nax Elgenati
-.. trvesse LR
10
15
20
70
30
Benston
ation in Fig. 7
Figure/ 7: The maximum eigenvalue of any -1
group's Hessian remains below n)
19

---

Published as a conference paper at ICLR 2023
Algorithm 4 FairLens
Require: Iterations T, Dataset D, sampling rate clipping bound Co, noise multiplier o, learning rates 7/+ regularization weights Y/, 722
Initialize 0n randomly do B Poisson sample of D with rate q
for 0, o
for (z,, as, 1/4 in do
9i Vol(So, (So, (2:), 1/5
Compute per-sample gradients of original loss
Di min
1,
Co
Talll
9B Σ iEB 9i GB & [8] EiEB 9i
for k in {a, b) do
yR, f B LisB,a 9i
SE f- [Bx LieB, J0, (zi))
R1 \g8,, 9B. 9B 9B}
R2 {(fa (1 fa) (a)+ + fo (1-
C ( (2; W1) RR R2
Define regularized loss
for (I,, Mi) in B do
g' VeL(fo. (z.). 91)
Compute per-sample gradients of regularized loss
9. g': min
1, 19
Co
Clip to ensure finile sensifivity
9BB B
(Eie Te + (O, o2
04+1 + 02 - 71
B.7 ADDITIONAL RESULTS
In this section we complete the set of experimental results shown in Sec. over all datasets and methods. All results are averaged over five random seeds with one standard error shown.
Table 4: Performance and Fairness metrics for Adult dataset
METHOD
Acc M
Acc F
Loss M
Loss F
RM
Rp
RMLF
NON PRIVATE
80.510.4
92.210.1
0.40.1..0 00 0.1910.00
DPSGD
69.910.4
88.510.1
10.610.3
3.6.0.11
6.0
0.7810.01
0.4010.01 0.39
0.2110.01
0.1710.01
FAIRLENS
68.820.4
88.520.1
11.740.2
3.720.1
7.9-0.2
0.57
0.4240.00
0.18=0.00
0.23:0000
0.05=2.00 80
DPSGD-F
78.010.6
89.410.1
25103
2.7.0.1
0.2=0.3
0.49:0.00
00
0.3110001
0.0010.00
0.12:0.00
0,0210.0
DPSGD-G.
78.510.5
89.910.1
2.010.2
2.210.1
0.2.0.2
0.43.0.00
0,25110.00
0.0110.00
0.05110.0
0,0210.00
DPSGD-G.-A.
80.710.4
92.3+0.1
-0.140.1
-0.1 0.0=0.1 0.39 0.18:00000 0.00=0.00 0.00:10.00
0.00
Table 5: Performance and Fairness metrics for Dutch dataset
METHOD
Acc
ACC
JM
Loss
Loss F
RM
RM.
NON PRIVATE
79.910.2
86.910.0
0.49910.000
0.447.1.000
DPSGD
76.0
86.4#41 3.840.3
0.440.0
3.440.4 0.520++..00
0.450=4.000
0.02140.001
0.003:t0.001
0.018-+0.002
FAIRLENS
78.6+0.3
86.940.1
1.340.2
+0.1
1.4+0.2
0.552+0.001
0.526=20.000
0.033+0.001
0.07944.000
0.026++0.001
DPSGD-F
78.910.2
86.610.1
0.910.1
0.310.0
0.740.1 0.50310.001
0.41710.001
0.00510.001
0.00010.000
0. 0.005:10.001
DPSGD-G.
79.0+a.2
86.5ed.1
0.8+0.1
0.4
0.4#0.2 0.510#a.000
0.460=2..002
0.012+0.002
0.013:tu.00
0.002+40.00
DPSGD-G.-A.
79.4+0.1
86.740.1 0.4+0.2
0.240.0 0.2+0.2 0.504+0.001 0.452+0.001 0.006+0.003
0.005+40.001 0.00140.001
First we look at the final performance and fairness metrics on the test set for Adult in Table and Dutch in Table 5) (cf. MNIST in Table and CelebA in Table 3). We that FairLens inconsistent in reducing the privacy cost gap and excessive risk gap compared to DPSGD. DPSGD- F improves both fairness metrics while achieving better performance. DPSGD-Glos or is comparable to DPSGD-F in all metrics, and does so without requiring access to protected group membership information. Our method DPSGD-Global-Adan further improves both performance and fairness by clipping less aggressively and adaptively setting the upper clipping threshold Z.
improves over
20

---

Published as a conference paper at ICLR 2023
Non-Private
DPPS3D
FaiLLnns
DPSGDD
DPSGD-Gletel
12
1.0
10
1.
130
100
Epocha
Epocha
Epochs
Eppoha
Epocts
Epochts
Figure 8: Adult dataset. Top: Train loss per epoch. Bottom: |g averaged over batches per epoch.
Non Privale
DPSGD
DPSGD-F
DPSGD-Global
DPSGD DPSGD-Globall Alopal-AAapp
dlss
dlasa
1ran 103
Nom ofove 020 gradenn
dass
Epacits
Epoche
Epoctts
Epoche
Epoctrs
Figure 9: MNIST dataset. Top: Train loss per epoch. Bottom: |gg averaged over batches per epoch.
Non-Private
30
2.
30
2.0
30
WD
Autrage 1855
70
1.5
05
05
23
0.5
Nom of average giadent
WO
30
20
Epochs
Figure 10: CelebA dataset. Top: Train loss per epoch. Bottom: || averaged over batches per epoch.
To go along with the training curves shown for Dutch in Fig. we present the same for Adult in Fig. 8 MNIST in Fig. | and CelebA in Fig. 10 The trends consistent across datasets whereas DPSGD produces large values and a large gap for the gradient norms and losses between protected groups, our method DPSGD-Global-Adap reduces the values and gap at all stages of training.
21

---

Published as a conference paper at ICLR 2023
DPSGD-F
DPSGD-Gkbbl
JPSGD-Globel-Adepp
000090
(106-2)
003160
030190
000110
Direction D40200ive FOR
000025
003125
000025
0160.6
000030
000000
033000
000130
006000
000675
000075
033013
0000'5
000075
000030
000050
02300
000050
000050
000035
02000
000035
040025
000030
020000
0.0000
0/0000
0054
2.84
0.04
0.044
2.014
Magiluuee eccessive 1l3k
2.912
00/2
0102
0.912
00.0
1..0
0.000
0.000
1.100
0.00
2.00
0.000
0.00
1.00
0.00
2.00
0.00
0.00
2.00
0004
2.00
0.04
0.04
2.34
0132
2.2
0102
0182
200
0030
2.00
0.00
Berstions
Bersiios
Itersions
Ferations
Figure 11: Dutch dataset. Top: Excessive risk due to gradient misalignment per group. Bottom: Excessive risk due to magnitude error per group.
DPSGD
DPSGD-F
DPSGD-Global
DPSGD- -loaal--apaa
Disecton micoooo0i 1984
cless 2
2.155
0.013
0015
0015
2.10
0300
0010
0013
-2.00
0.00
-0.65
-0.00
Maggitudo eioessive rick
choos 2
20
43
20 Barationa
Banations
Figure 12: MNIST dataset. Top: Excessive risk due to gradient misaligmment per group. Bottom: Excessive risk due magnitude error per group.
DPSGD
DPSGD-F
DPSGD-Gleba
DFSGD--GoobalAddap
Meg Meggitudee excesstee risk Dieccton excessne mok
WNO
W
2:44
014
0.4
000
3:2
2.00
0.00
-00
-20
-50
-50
-120
-13
-150
WHO
-200
-159
-000
herations
Iteration
Derations
Figure 13: CelebA dataset. Top:
Excessive risk due gradient misalignment per group. Bottom: Excessive risk due to magnitude error per group.
for MNIST in Fig. 12 and CelebA in Fig. 13 as was done for Adult in Fig, 4 Both Global methods dramat- the final training results where global methods also show the best performance, this provides further evidence for our hypothesis that gradient misalignment is the most significant cause of disparate impact in DPSGD.
We also present the values of terms Rdlr and Ram over training for Dutch in Fig. II
ically reduce Fdlr compared to DPSGD at the cost of larger R. mag Comparing
22

---

Published as a conference paper at ICLR 2023
DPSGD
FailLens
DPSGD-F
DPSGD-Global
DPSGD-Giibel-Aeig
047
M
0.0
N10
0.0
10
15
13
borations
Figure 14: Excessive risk due to noise error per group for the Adult dataset
DPSGD
FairLens
DPSGD-F
DPSGD-Gkbbl
DPSCD-Gkial-Addot
0.02
Nel0o Nekin 0r0000000 100
0.000
Berations
Earation
Bor allinn
Itrralons
Itorations
Figure 15: Excessive risk due to noise error per group for the Dutch dataset
DPSGD
DPSGD-F
DPSGD-Global
17.5
clss
Borations
lorations
Parations
Horations
Figure 16: Excessive risk due to noise error per group for the MNIST dataset
DPSGD
DPSGD-F
DPSGD-Glotal
DPSGD-Glebal-An
Nobis prwaasaeeeeet dak
Figure 17: Excessive risk due to noise error per group for the CelebA dataset
We note that by tuning the learning rate DPSGID-Global and DPSGI-Gilobal-Adapt there is trade-off between magnitude error and noise error. Referring Prop. Rusise n THHr))C33 we see that the excessive risk due to noise is affected by the learning rate T) the noise multiplier a,, clipping bound Co and the trace of the Hessian for group a. choosing larger learning rate for the global methods to offset the magnitude error, we increase the noise error quadratically. Refer to the values of Regoise over training for Adult in Fig. 14 Dutch in Fig. 15 MNIST in Fig. 16 and CelebA in Fig. 17 While the excessive risk due to noise is significantly larger for the global methods, these methods outperform all other private methods at the end of training, see Tables 2
4 Gaussian noise adds zero bias and the errors it introduces tend to cancel out over the course of training. These observations further validate that direction error is the core cause disparate impact, and minimizing gradient misalignment should be prioritized over other sources of unfairness.
23


Reviews:
[{"review_id": "qpMs2l7m4u", "reviewer": "Reviewer_ktiq", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper identifies the gradient misalignment as the main reason why applying privacy-enhancing methods may lead to more unfairness. The authors use an existing method, DPSGD-Global, and a variant of it, DPSGD-Global-Adapt, to prevent misalignment and reduce this unfairness.", "summary_of_the_review": "This paper shows detailed experimental results to support their statement that the unfairness is mainly caused by gradient misalignment. The interpretation of the results may have some problems which weaken the validity of the analysis.", "strength_and_weaknesses": "Major strengths:\n1. Proposition 3 is closely related to the focus of this paper on the disparate impact caused by gradient misalignment.\n2. The authors have very detailed experiment results which supports their statements.\n\nMinor strengths:\n1. This paper is easy to follow and the algorithms are intuitive and can be implemented easily.\n\nMajor weaknesses:\n1. The experiment results seem to be confusing. In Figure 3, the DPSGD is not working in terms of the train loss while the DPSGD-Global is even as good as the non-private result. Such results are not shown in Bu et al, 2021. In Figure 4, the DPSGD-Global and Adapt solves the direction excess risk, but the magnitude of this direction excess risk seems to be much smaller than the excess risk from the magnitude error. Additionaly, the excess risk from the noise error is analyzed in the supplementary material where I think the magnitude of them is much larger than the excess risk from the gradient misalignment and the magnitude error. \nFor example, for the Dutch dataset, I do not understand how the excess risk is break down into the three parts in the way that the authors claim the direction one contributes the most while has the smallest magnitude.\n2. Proposition 3 does not show why $|R_a^{dir} - R_b^{dir}|$ is larger than $|R_a^{mag} - R_b^{mag}|$. It uses the inverse of the largest eigenvalue of the Hessian among different groups as an upper bound for the learning rate. It seems to be hard to satisfy such constraint. In Figure 5, this lower bound (I guess it is derived from the proof of Prop 3) is shown to be very good. Therefore, there is a lack of an explanation about the learning rate being used and the upper bound from the assumption of Prop 3.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "max__0t-prt", "reviewer": "Reviewer_Sern", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the fine-grained causes of unfairness in DPSGD and identifies gradient misalignment due to inequitable gradient clipping as the most significant source. They show that excess risk, the notion of fairness, can be decomposed into both non-private terms, clipping bias, noising bias according to previous work. Based on that work, they further analyze the gradient misalignment as a cause for unfairness. They show a lower bound for excessive risk gaps which is tight.", "summary_of_the_review": "The paper provides an interesting view, gradient misalignment, for analyzing the unfairness of DP-SGD. The technique is not new and can not resolve the privacy-fairness tradeoff but empirically DP-SGD-Global-Adapt can work. The fairness problem in DP can be important and related to societal impact since many trustworthy aspects are connected and some applications might require both.", "strength_and_weaknesses": "Pro: The paper provides a new angle in understanding the disparate impact of DP-SGD - gradient misalignment. The mitigation solution, gradient scaling, is different from previous works like global clipping and [1]. The lower bound is much tighter in fig.5 than [1] - the two curves almost overlap, which is intriguing.\n\nCons: Despite the differences with previous work [1], the decomposition of excess risk into clipping bias and noising bias is not new. And that DP-SGD hurts fairness was already understood as the combination of per-example gradient clipping and gradient noise injection. \n\n[1] Differentially Private Empirical Risk Minimization under the Fairness Lens", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "jwEyGU6SB4", "reviewer": "Reviewer_pvjf", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper examines the cause of disparate impact on unbalanced datasets (tabular and MNIST) and finds gradient misalignment to be the cause. Furthermore, they introduce techniques to mitigate these disparities. ", "summary_of_the_review": "There are several areas on which this paper can elaborate on. But overall, it is a useful contribution.", "strength_and_weaknesses": "Strengths: \n1. Nice, clean decomposition of magnitude vs direction error. It would be great to see this for other datasets as well. \n2. Thorough comparison to previous techniques. \n\nWeaknesses: \n1. Authors compare only 1 epsilon per dataset.  It is unclear whether results also hold in other epsilon regimes. \n2. Would like to see more discussion on why DPSGD and DPSGD-F diverge so much in Figure 3. Has proper hyperparameter tuning been done? It looks like DPSGD would further improve with more epochs?\n3. It is unclear whether this analysis extends to more complex image datasets like CIFAR10 and CIFAR 100. It would be nice to see a discussion on why or why not. \n4. How does noise compound issues of gradient misalignment? In Table 1, the authors compare the effects without noise. It is not immediately clear to me that similar results could hold for a fixed amount of noise. \n5. The authors mention that DPSGD-Global has the potential to exacerbate disparate impact by discarding gradients, but I don't see this happening empirically in Figure 3 or Table 2. Please explain further. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "TYJw-r5s9a", "reviewer": "Reviewer_tDQn", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper conducts a fine-grained analysis of DP-SGD to show that gradient misalignment is  a principal cause of the disparate impact that occurs when DP-SGD is applied to a dataset. This analysis compares two key components of the DP-SGD: clipping and noise addition. Ultimately, this paper shows that clipping further impacts and exacerbates gradient misalignment, which greatly increases the disparate impact of DP-SGD. This insight is nicely illustrated in a simple experiment that keeps the noise level in DP-SGD fixed, but changes the level of gradient alignment to show that when the gradient is more misaligned, it leads to more disparate results. The fix proposed by this paper is to  scale down all per-sample gradients in a batch by the same amount. The improved results are demonstrated experimentally on the MNIST and adult datasets.", "summary_of_the_review": "This paper provides new insights on an important problem. The paper also demonstrates empirically improvements based on a modified DP-SGD algorithm that reduces disparate impact.", "strength_and_weaknesses": "### Strengths\n\n- This paper refines the cause of disparate impact in SGD, which is an important problem. \n\n- The experiment and analysis presented in Section 4 clearly show the main take home of this paper.\n\n- The proposed modification to DP-SGD is quite simple and straightforward. The proposed optimizer can be easily plugged-in to other settings.\n\n### Weaknesses\n- One of the benefits of the proposed DP-SGD-Adapt global is that it does not need group identifiers. However, it is unclear whether the methods that use group identifiers lead to models with better utility. While the comparison is not 1:1 here, it would still be good to know how these results compare to when one actually takes into account group identifiers.\n\n- The datasets considered the paper are small and somewhat toyish even though these are the datasets that were used in previous papers. It is unclear how this proposal scales to larger models and bigger setups. However, I think future work can likely address these issues.\n\n- The theorems and analysis presented applies or explicitly assume convexity or in some cases that the loss is twice differentiable. It is nice that the analysis generalizes to model classes that do not satisfy these assumptions but this issue could be better highlighted.\n\n- This work highlights gradient misalignment as a key cause of disparate impact, but it is hard to judge how much that is more important than say group difficulty as measured by the trace of the hessian of the loss per group. It could be that more difficult to learn groups have hessian-trace values that are substantially different than other groups. \n\n-  (Minor) The term 'excessive risk' is used quite a bit in a number of places in the paper. I believe it should be 'excess risk'. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-25%