Fair Differential Privacy Can Mitigate the Disparate Impact on Model Accuracy
Authors: Wenyan Liu
Xiangfeng Wang
Xingjian Lu
Junhong Cheng
Bo Jin
Xiaoling Wang
Hongyuan Zha
Venue:  (2021)

Abstract: The techniques based on the theory of differential privacy (DP) has become a standard building block in the machine learning community. DP training mechanisms offer strong guarantees that an adversary cannot determine with high confidence about the training data based on analyzing the released model, let alone any details of the instances. However, DP may disproportionately affect the underrepresented and relatively complicated classes. That is, the reduction in utility is unequal for each class. This paper proposes a fair differential privacy algorithm (FairDP) to mitigate the disparate impact on model accuracy for each class. We cast the learning procedure as a two-stage optimization problem, which integrates differential privacy with fairness. FairDP establishes a self-adaptive DP mechanism and dynamically adjusts instance influence in each class depending on the theoretical bias-variance bound. Our experimental evaluation shows the effectiveness of FairDP in mitigating the disparate impact on model accuracy among the classes on several benchmark datasets and scenarios ranging from text to vision.

Under review as a conference paper at ICLR 2021
FAIR DIFFERENTIAL PRIVACY CAN MITIGATE THE DISPARATE IMPACT ON MODEL ACCURACY
Anonymous authors Paper under double-blind review
ABSTRACT
The techniques based on the theory of differential privacc (DP) has become a stan- dard building block in the machine learning community. DP training mechanisms offer strong guarantees that an adversary cannot determine with high confidence about the training data based on analyzing the released model, let alone any details of the instances. However, DP may disproportionately affect the underrepresented and relatively complicated classes. That is, the reduction in utility is unequal for each class. This paper proposes fair differential privacy algorithm (FairDP) to mitigate the disparate impact each class's ' model accuracy. We cast the learning procedure as a bilevel programming problem, which integrates differential privacy with fairness. FairDP establishes a self-adaptive DP mechanism and dynamically adjusts instance influence in each class depending on the theoretical ttas-variance bound. Our experimental evaluation shows the effectiveness of FairDP mitigat- ing the disparate impact on model accuracy among the classes on several bench- mark datasets and scenarios ranging from text to vision.
INTRODUCTION
Protecting data privacy significant concern in many data-driven decision-makinn applications (Zhu et al. 2017). such as social networking service, recommender system, location-based service. For example, the United States Census Bureau will firstly employ differential privacy to the 2020 census data (Bureau 2020). Differential privacy (DP) guarantees that the released model cannot be exploited by attackers to derive whether one particular instance is present or absent in the training dataset (Dwork al. (0066). However, DP intentionally restricts the instance influence and intro- duces noise into the learning procedure. When we enforce DP to a model, DP may amplify the discriminative effect towards the underreepesentte and relatively complicated classes (Bagdasaryan jet al.] 2019; Du et al.) 2020; Jaiswal & Provost] (020)). That is, reduction in accuracy from non- private learning private learning may be uneven for each class. There several empirical stud- ies on utility reduction: (Bagdasaryan et al.) 2019 Du et al. 2020) show that the model accuracy in private learning tends decrease more on classes that already have lower accuracy non-prie non-private learning. (Jaiswal & Provost 2020) shows different observations that the inequality in accuracy is not consistent for classes across multiple setups and datasets. needs be cautionary that although private learning improves individual participants' security, the model performance should not harm one class more than others.
The machine learning model, specifically in supervised learning tasks, outputs hypothesis [(x; 0) parameterized by 0, which predicts the label y given the unprotected attributes æ. Each instance's label belongs to class k. The model aims to minimize the objective (loss) function L(O; a, y),
i...
0 arg min E [C(0; v)]
Our work builds on recent advance in machine learning models' training that uses the differentially private mechanism, i.c., DPSGD (Abadi et al.) 2016) for releasing model. The key idea can be extended to other DP mechanisms with the specialized noise form (generally Laplacian or Gaussian distribution). The iterative update scheme of DPSGD at the (t + 1)-th iteration is of the form
gmm::)
Ø++1 1=+1=00 g n² n
Σ
+ +51 )
VESt max(1, Lg 12l

---

Under review as a conference paper at ICLR 2021
1.00
Cless (Nt C Noise]
9.59-
(CIp Nonel
[CIp Natuel
Accunccy
Nctuel
0.6
Class
0.09
Noisa)
0.4-
Class
0:75
0.2
025
0.0
05.0 20 3.0 5.
8.0 5.0 10.0
3281.82_90M
4358
2204124, TCC, 8%)
2,001222,001128432222.00 18343.222446
Cliping threshold
(a) Clipping threshold accuracy
(b) r(C, 0; accuracy.
Figure 1: Effect of clipping and noise in differentially private mechanism and T TCC, o; (*) on MNIST dataset
where and n² denote the batch size and step-size (learning rate) respectively; S denotes the randomly chosen instance set; the vector denotes the vector filled with scalar value one; and g' (xx;) denotes the gradient of the loss function in (1) at iteration t. i.c., V (iu; 0 2x)). The two key operations of DPSGD are: clipping each gradient gx,) in f--norm based on the threshold parameter C: ii) adding noise & ddrawn from Gaussian distribution N(, o C²C² with variance of noise scale a and the clipping threshold parameter C. These operations enable training machine learning models with non-convex objectives at manageable privacy cost. Based on the result of traditional SGD, we theoretically analyze the sufficient decrease type scheme of DPSGD, i.e.
(3) where the last term 7 rC,, a; 0²) denotes the gap of loss expectation compared with ideal SGD at this (l 1--th iteration, and related with parameters C, and The term rCC, 03,0), which can be called bias-variance term, can be calculated mathematically as
E [ & f(0') + ( (VV((O', 00+1 0->] +
L 2
IE
110
0-10]] + +T(C,,;00))
2(1 LLL ) (V.[()) 7 n²
1²
Clipping bins
Noise variance
where L denotes the Lipschitz constant of f: |1] denotes the vector dimension; and we have
Σ
(1lg' (ax))l
17
n
where (a;)"(;;))) ->e denotes the cardinality number of satisfying [x,)( C. The detailed proof of (3) and (4) can be found in Appendix A r(C, o)) is consist of clipping bias and noise variance terms, which means the amount that the private gradient differs from the non non-prite private gradient due to the influence truncation and depending the scale of the noise respectively. As result, we call r(C, .) the biri-nariance term.
As underrepresented class instances complicated instances manifest differently from common instances, a uniform threshold parameter C' may incur significant accuracy disparate for different classes. In Figure [(a) employ APSGD(Abadi al., 2016) the unbalanced MNIST dataset (Bagdasaryan et al. 2019) to numerical study the inequality of utility loss (i.e., the prediction ac- curacy gap between private model and non-private model) caused by differential privacy. For the unbalanced MNIST dataset, the underrepresented class (Class 8) has significantly larger utility loss than the other classes (e.g.. Class 2) in the private model. DPSGD results accuracy on the well-represented classes, but accuracy on the underrepresented class drops 74.16%. Training with more epochs does not reduce this gap while exhausting the privacy budget. DPSGD obviously introduces negative discrimination against the underrepresented class (which already has lower accuracy in the non-private SGD model). Further, Figure ((b) shows the classification accu- racy of different sub-classes for 7 rCC, σ; 9) the unbalanced MNIST dataset. Larger hlas-variance term 7 (C, a; f) (determined by C and σ)) results in more serious accuracy bias on different classes,
6.% decrease in
while similar results are also shown in (Bagdasaryan al. 2019 Du et al. 2020) Jaiswal & Provost
2

---

Under review as a conference paper at ICLR 2021
2020). Both theoretical analysis and experimental discussion suggest that minimizing the clipping bias and noise variance simultancously could learn "better" DP parameters, which mitigates the accuracy bias between different classes. This motivates us to pursue fairness with self-adaptive differentially privacy scheme"
This paper proposes fair differential privacy algorithm (FairDP) mitigate the disparate impact problem. FairDP introduces a self-adaptive DP mechanism and automatically adjusts instance influ- ence in each class. The main idea is formulate the problem as bilevel programming by minimizing the bias-variance term as the upper-level objectíve with a lower-level differential privacy machine learning model. The self-adaptive clipping threshold parameters are calculated by balancing the fairness -arrinne and per-class accuracy terms simultancously. Our contributions can be sum- marized as follows:
FairDP uses a self-adaptive clipping threshold to adjust the instance influence in each class, the model accuracy for each class is calibrated based their privacy cost through fair- ness balancing. The class utility reduction is semblable for each class FairDP.
To our knowledge, we are the first to introduce bilevel programming to private learning, aiming to mitigate the disparate impact on model accuracy. We further design an alternating scheme to learn the self-adaapive clipping and private model simultancously.
Our experimental evaluation shows that FairDP strikes balance among privacy, faimess, and accuracy by performing stratified clipping over different subclasses.
The following is the road-map of this paper. Section 2 describes the proposed FairDP algorithm. In Section 3 we provide a brief but complete introduction to related works in privacy-aware learning, fairness-awand learning, and the intersection of differential privacy and fairness. Extensive experi- ments are further presented in Section 4 and we finally conclude this paper and discuss some future work in Section 5
2 FAIRDP: FAIR DIFFERENTIAL PRIVACY
2.1 THE BILEVEL FAIRDP FORMULATION
Our approach's intuition is to fairly balance the level of privacy (based on the clipping threshold) for each class based on their bias-variance terms, which are introduced by associated DP. The bias- variance terms arise from capping instance influences to reduce the sensitivity of machine learning algorithm. In detail, self-adaptive DP mechanism is designed to balance the bias-variance dif- ference among all groups, while the obtained DP mechanism must adapt to the original machine learning problem simultaneously. Recall the definition of the machine learning problem, we assume there are é classes and according to the bias-variance term for class io E [1...., E} can be denoted as
Th (C = 2(1
LLL [VV((0)) Th m 2 + 0² C 3/11,
(5)
where C₁ denotes the clipping parameter for class k; Sk denotes the data sample set for class As motivated by Section [1 aim minimize the associated varianar term to obtain unified clipping parameter for the machine learning problem. However, to mitigate the disparate impact on model accuracy for different classes, we minimize the summation of per-class bias-variance terms. This objective can lead to the self-adaptive clipping threshold among different classes, while the inconsistent DP schemes for different classes should work on the privacy protection on the machine learning model. The self-adaptive clipping threshold parameters should be utilized to learn the orig- inal machine learning privately with the DP mechanism. simple bilevel programming problem"
(Dempe et al. 2019 Liu et al. 2019) is introduced to model these two goals which influence each
Note that we do attempt optimize the bias-variance bound in diffcrentially private way, and most interested in understanding the forees at play.
"The simple bilevel programming is not to say that the bilevel problem is simple, and it denotes a specific bilevel programming problem.
3

---

The FairDP Method Under review as a conference paper at ICLR 2021
Σ 2(1 I
n2 + ||]
1922
n2a
C
Clipping
Noton vartance
C7 [od
(xx) Vy
6
o pd: Σ Ve.
of (m:) min
Step 8:12
Figure 2: Main flowchart of the FairDP Method (Step 4-12 in Algorithm I)
other. The formulation be denoted as follows, i.e.,
min (Ca).
[n((C,,o;
(6a)
k=1
s.t. E arg L(0; (9x
(6b)
where the upper-level problem 66a) aims to fairly adjust the clipping threshold parameters for all classes, which is related the classification model 0; as for the lower-level problem (6b), aim learn the classification model based on the differential privacy schema with the self-adaptive clipping threshold {Cx]. These two objectives are coupled together, although the model of the lower-level problem is determined only by 0. The effect of clipping is reflected through the DP calculation procedure. Guided by the bias-variance term in (6a), the parameters of the DP learning can be finely updated simultaneously with the learning process of the classifiers in (6b).
Algorithm 1:
Input : Instances ((21,y1,.". (IN, (N)) objective function L(B; æ. y). learning rate μ²;
Initialize fu:
for / 4-1 to T do
Randomly sample a batch of instances St with probability N Compute gradient for x; E St do Compute (x;) V D(y;;00 mx);; end
Minimize bias-variance Oft1 +- arg ming, Th (Ck, o; 0*); for x; St and y/ k do Clip gradient
g'(x:) +
(x,)
1, 110000011
max
10
end
Add noise
g' - -x: EI):
11
Noise Gradient Descent
ge+l -
n'
12
13
end
Output: 0r, accumulated privacy cost O),
2.2
THE FAIRDP METHOD
Calculating the optimal 8* and {CT) require two nested loops of optimization, and we adopt an alternating strategy update 0 and {Ck} respectively. The FairDP method is summarized in Al- gorithm [ while Figure [ illustrates its main process (i.e., Steps 4-12 in Algorithm [ For the self-adaptive clipping step (6ab in upper-level, given the current obtained model parameter 0*,
4

---

Under review as a conference paper at ICLR 2021
can calculate optimal {Cx} directly by solving quadratic programming problem. Based on a batch of training samples 8 (Step 3), the overall gradient V f((0") are approximately estimated by V f(*) with the samples in S As for private training step (6b) in lower-level, the updating equation of the classifier parameter can be formulated by moving the current # along the descent direction of the
objective loss in (6b) on a batch training data (Step-46)
g' gx4))) = V L(vs; 0* .;)
After receiving the classifier parameter updating g (x.) from 7 the updated @++ is employed to ameliorate the parameter 0 of the classifier in DP way 2) with the obtained clipping parameters {C&} from Step 7 (Step 8- 12). All the details can be found in Algorithm
RELATED WORK
3.1 PRIVACY-AWARE LEARNING
Existing literature in differentially private machine learning can be divided into three main cate- gories, input perturbation, output perturbation, and inner perturbation. The input perturbation ap- proach adds noise the input data based on the differential privacy model. The output perturbation approach adds noise to the model after the training procedure finishes, i.e., without modifying the training algorithm. The inner perturbation approach modifies the learning algorithm such that the noise is injected during training. (Chaudhuri et al. 2011)) modifies the objective of the training pro- cedure. DPSGD (Abadi et al. 2016) adds noise to the gradient of each step of the training without modifying the objective.
Limiting users to small influences keeps noise level low at the cost of introducing bias. Several works study how to adaptively bound users' influences and clip the model parameters improve learning accuracy and robustness. DPSGD fails to provide a detailed analysis of how to choose the gradient norm's truncation level, instead suggesting using the median of observed gradients. Using the median (or any fixed quantile independent of the privacy parameter e) as a cap can yield suboptimal estimations of a sum (Amin al. 2019). DP-FEDAvG (McMahan al. 2018) proposes per-layer clipping, which chooses to distribute the clipping budget across layers. (van der Veen jet al. 2018) proposes a gradient-aware clipping schedule, which uses a constant factor times the mean private norm of the previous batch as the norm bound for the current batch. (McMahan & Andrew 2018)) does pre-processing step via the scaling operation. DP-GAN (Zhang et al.) (018)) assumes that we have access small amount of public data, which is used to monitor the change of gradient magnitudes and set the clipping parameters based on the average magnitudes. (Amin et al. 2019) characterizes the trade-off between bias and variance, and shows that a proper bound can be found depending on properties of the dataset. It does not matter how large or small the gradients above or below the cutoff, only that fixed number of values sets an adaptive clipping norm based on a differentially private estimate of a targeted quantile of the distribution of unclipped norms. AdaClip (Pichapati et al.) 2019) uses coordinate- wise adaptive clipping of the gradient to achieve the same privacy guarantee with much less added noise.
clipped. (TTaakaar et al. 2019)
Previous work either ignores computing the trade-off completely (DPSGD(Abadi al. 2016) sim- ply uses the empirical median, DP-FedAvg (McMahan et al.) 2018) scatter privacy budget evenly over the layers), or requires strong assumptions on the data (Zhang et al. 2018) assumes the acces- sibility of public data).
3.2 FAIRNESS-AWARE LEARNING
Fairness is broad topic that has received much attention in the machine learning community. How- ever, the goals often differ from those described in this work. Most researches on fairness-aware machine learning study the discriminatory prediction problem: how can we reduce the discrimi- nation against the protected attribute in the predictive decision made by machine learning model (wook et al. 2012 Hardt et al. 2016: Kusner et al.] 2017). Three common approaches are to preprocess the data to remove information about the protected attribute (Zemel al.] 2013), op- timize the objective function under some faimess constraints during training (Zafar et al. (017). or post-process the model by adjusting the prediction threshold after classifiers are trained (Hard
5

---

Under review as a conference paper at ICLR 2021
et al. 2016). The others study the discriminatory impact problem Kusner et al. 2019): how reduce the discrimination arising from the impact of decisions.
In federated learning, AFL (Mohri et al., 2019) has taken step towards addressing accuracy parity by introducing good-intent fairness. The goal is to ensure that the training procedure does not overfit model to any one class another's s expense. However, the proposed objective is rigid because it only maximizes the performance of the worst class and has only been applied at small scales (for handful of devices). q-FFL (Li et al., 2020) reweighs the objective function in FedAvg to assign higher relative weight to classes with higher loss, which reduces the variance of model performance. Although accuracy parity enforces equal error rates among specific classes (Zafar et al. 2017), our goal is not to optimize for identical accuracy across all classes, and we focus on the inequality introduced by differential privacy.
3.3 DIFFERENTIAL PRIVACY AND FAIRNESS
Recent works study the connection between achieving privacy protection and fairesss. (work
al., 2012) proposes notion of fairness that generalization of differential privacy. ADFC
(Ding et al. 2020p, Jp-POSTPROCESSINN//D SETROOSSSSIN//DDORRAAIIAAC
(Jagielski et al. 2019), PFI.R* Xu al. 2019) achieve fairness in addition to enforcing differential privacy in the private model.
Most existing work focuses preventing private information extraction while reaching acceptable fairness performance. Minority work focuses on the accuracy disparity among classes with different protected attributes caused by differential privacy. DPSGF-F (Xu et al. 2020) prevents the disparate impact of the privacy model on model accuracy across different groups by scales the clipping bound with relative ratio. Different from their restriction of the fraction of instances with gradient norms exceeding the clipping threshold, our analyses quantify the bias-variance with sufficient decrease difference between non-private and private learning.
EXPERIMENTS
This section reports evaluation of the fair differential private learning on some benchmark datasets from text to vision. We use PyTorch 1.6.0 to implement all the methods with only one NVIDIA GeForce RTX 2080Ti.
2017). the Dutch (Kamiran & Calders 2011) and the Unbalanced MNIST (LeCun et al. 1998 The details can be found in Appendix
Datasets: three datasets are used, including the Adult (Dua & Graft
Comparison methods: 1) SGD: non-private learning without clipping and noise-addition: 2) DPSGD (Abadi et al. 2016): private learning with flat clipping; 3) DP-FedAvg (McMahan et al.)
2018 t private learning with per-layer clipping; 4) Opt Q: private learning with (1 /2/T a o/e)- quantile clipping, which is adapted from (Amin et al., 2019) and details can be found Appendix C.1 5) DPSGD-F (Xu et al. 2020): private learning with clipping proportional to the relative ratio of gradients exceeding the threshold. More details in Appendix
Settings and hyper-parameters. Without loss of generalization, we assume that the function f is I-Lipschitz. For the Adult and Dutch datasets, we employ a logistic regression machine learning model. Then for logistic regression, the DP- DP-FedAvg will degenerate to classical DPSGD. The noise scale o,, clipping bound and are set to be 1, 0.3 and 10 respectively. For the Unbalanced MNIST dataset, we employ neural network with 2 convolutional layers and 2 fully-connected layers. The noise scale a, clipping bound and are set to be 1, 1 and 10-5 respectively. More Details can be found in Appendix [D.3]
To evaluate the efficiency of the proposed FairDP, we aim to complete the following three tasks, i.e., 1) Faimesss performance: not only the utility loss is small, but also we can obtain more fair utility loss on different classes; 2) Privacy performance: the proposed FairDP method can preserve the privacy of training data; 3) Adaptive performance: the effect of param-parameters on compared private methods.
"The original MNIST dataset is modified by reducing the number of training samples in Class 8 500

---

Under review as a conference paper at ICLR 2021
Table 1: Utility loss for SGD on total population, well-represented group (Class 2 in Unbalanced MNIST and Male in Adult/uuth) and underrepresented group(Class 8 in Unbalanced MNIST and Female in Adult/Dutch..
Dataset
Unbulanced MNIST
Aduli
Dutch
Class
Total
Class 2
Class
Total
Male
Female
Total
Male
Female
Sample
54649
30162
20380
48336
24201 4.0
24135 1m
Test Sample size
10000
1032
974
15080
10147
4913
12084
60722
641 6012
08
99.28
95.96
82.02..08 08
75.45 09
91.222000 06
81.74..43
20, 80
77.17..00
DPSGD
-11.6-11.00
-6.33..99
-75.31
-7.10 06
+..31 4.
-2.54.006
-3.82= 57
-0.75+
28
-6.94=1.02
DP-FedAvg
-10.85
-5.95
-73.87
-7.10
1.
-2.341.00
-3,82
-0.73
-6.94
Opt-Q
2.92+ 16
-3.67
+0.134.30
50
+0.83 10
40.61+.12
-1.28
-0.80 20
+0.47
+ 26
-2.07 44
DPSGD-F
-,38
-4,53
-16.43134
-0.68
40.67
-0.71 1.00
-1.13
+0.67
-2.94
FairDP
4065 1.
-1.20 4m
g0.55 10
+0.03, 08
+0.02
+0.05 1 04
-0.03
15
+0.01
-0.07
Table 2: Model faimess comparison
Dalaset
Metrics
SGD
DPSGD
DP-TedAvg
Upt-Q
DFSGD-F
FairDP
Index
10000010.000
10.56710.185
0.1171
10007710.0002
0.0167
.0.0055
0.0007
Lc. 10.000
Unbalanced MNIST
Gini Index
0:047420.0077
0.8791
0.8574
D.064340.0002
0,2317
0,0581
20,0114
MLD
0.0006.0.000
0.6807+0.100
0.6602-0.128
400007
0.0167-0.000
0.0007
=0, 0000
Theil Index
100006.0.000
0.4267-0.00s
000107
10.0002
0.0159
00.005
0,0107
46 0001
Atkinson Index
0.025 0002
0000
0.009500.001
0,0232
+0000220.0007
0,025550.000
0.0000
0.025
0005
Adult
Gimi Index
MLDD
0.0253-0.0002
0.338920.001
0.009740.0001
0.0697-0.001
0.5678
0.0232+00000
10:000
0.0256-0.003
20.0000 0,3407
0.3394
0.0254
20, 0002
Index
000001
0.0004_0.0001
0.0233440000
0007
0.12600_0.oo
000000
0.0258
26 0005
Atkinson Index
0x0150+2.022
1.0477+0.0000
0.0477
0.0251
0.0251+0.020
+0.0027
0,01404
0.000
0.0152
0022
Dutch
MLD
000150
0.2726.0.025 0274
0.0076+000000
04086
0.0478=00000
0.4855_0.0456
0,0251
0.35556g0.019
0188
0,0304
0.0026
0.2750
0,0152
20.00022
0105
Theil Index
0.01 20150 00g9
0.0477 7:00000000 0006
0,0477 000277-0.000
0.0251
4000007
0,0300 0036
0.0152 0003
0.60
952
3.50-
S6B
0.500
SGD
D75CD
DF500
Pusb
Adveninge
0.10
Advanage
onc-
0.00
0.1
0.02
klew
Attack Type
Aback Type
Atbick Type
(a) Unbalanced MNIST
(b) Adult
(c) Dutch
Figure 3: Privacy vulnerability comparison
4.1 FAIRNESS PERFORMANCE
Table [ and Table 2 provides the comparison results on model accuracy and fairness after imple- menting different DP methods. presenss the utility loss of different private learning methods w.r.t. classical SGD. cluding Atkinson Index, Gini Index. MLD and Theil Index (Appendix [D4]. In most cases, FairDP has the least accuracy loss from SGD than other methods and offers equal fair statistics as SGD (a lower value is better). Although Opt-Q has little improvement in fairness on the Adult dataset, reduces both per-class and overall accuracies. Overall, FairDP can outperform other private learning methods on both model fairness and accuracy and balance model fairness and accuracy.
the comparison on four fairness indexes (Bureau 2016). in-
4.2 PRIVACY PERFORMANCE
Figure 3 shows the empirical tests for measuring potential memorization from the training data. Same as (Song& & Marn 2020). the attackers can use four classifiers, including Logistic Regression (LR), Multi-Layer Perception (MLP), Random Forest (RF), and K-Nearest Neighbors (KNN). The vulnerability score (Song & Marn 2020 set be the Area Under the ROC-Curv Cur-Curve&&a (AUC) and max Irtp- Tupl (Advantage and lower value means more private. Although FairDP employs self- adaptive clipping parameters, it still maintains similar level of privacy protection as DPSGD.
Tip and Ttp denotes the false positive rate and true positive respectively.
7

---

Under review as a conference paper at ICLR 2021
Dec (007)
MB deo
Den ICe t
0M 12000-11
774777
022
3.1
002
1.22
041
000
Learing 14e
Louriin
(a) MNIST (Class 2)
(b) MNIST (Class 8)
(c) Adult (Male)
(d) Adult (Female)
Figure 4: Effect of learning rate on training procedure
(95--
0.0-
Osm 5G4
Clas 10E520
Clis (0mmo)
411y
6.6
Kick
(a) MNIST (Class 2)
(b) MNIST (Class 8)
(c) Adult (Male)
(d) Adult (Female)
Figure 5: Effect of batch size on training procedure
Cle (900
6.0
de P4-
(a) MNIST (Class 2)
(b) MNIST (Class 8)
(c) Adult (Male)
(d) Adult (Female)
Figure 6: Effect of noise on training procedure
4.3 ADAPTIVE PERFORMANCE
McMahan et al. 2018) claimed that the proper choice for the clipping parameters might depend on the learning rate. If the learning rate changes, the clipping parameter also needs to be re-evaluated. In this experiment, we consider not only the learning rate (Figure 4 but the batch size (Figure (5) and noise (Figure 6. to show the sensitivity of compared private methods on these three hyper- parameters. 55 6 show that FairDP is insensitive to variations in the hyper-parameted Because of the space limitation, more results on the Dutch dataset are moved to Appendix B
5 CONCLUSION
Gradient clipping and noise addition, which are the core techniques in DPSGD, disproportionately affect underrepresented and complex classes. As consequence, the accuracy of model trained using DPSGD tends to decrease more on these classes vs. the original, non-private model. If the original model is unfair because its accuracy is not the same across all subgroups, DPSGD may exacerbate this unfaimess. We propose FairDP, which aims to remove the potential disparate impact of differential privacy mechanisms on the protected group. FairDP adjusts the influence of samples in a group depending on the group clipping bias such that differential privacy has no disparate impact on group utility. In future work, we can further improve our adaptive clipping method from group- wise adaptive clipping to an element-wise adaptive clipping from the user and/or parameter perspectives, and then the model could be fair even to the unseen minority class.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Martín Abadi, Andy Chu, lan J. Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In CCS. pp. 308-318, 2016.
Kareem Amin, Alex Kulesza, Andres Muñoz Medina, and Sergei Vassilvitskii. Bounding user contributions: A bias-variance trade-off in differential privacy. In ICML, pp. 263-271, 2019.
Eugene Bagdasaryan, Omid Poursaeed, and Vitaly Shmatikov. Differential privacy has disparate impact on model accuracy. In NeurIPS, pp. 15453-15462, 2019.
United States Census Bureau. Income inequality metrics, 2016. URL https: www census. att.://ttttttttttttteteeeee
United States Census Bureau. Disclosure avoidance and the 2020 census, 2020.
URL
https::/www.ccet http://nnssssoooobbooooooppaaaaa 2a0p:nnccce2200--eususee htmll
sa
Kamalika Chaudhuri, Claire Monteleoni, and Anand D. Sarwate. Differentially private empirical risk minimization. Journal of Machine Learning Research, 12:96-11 2011.
Stephan Dempe, Nguyen Dinh, Joydeep Dutta, and Tanushree Pandit. Simple bilevel programming and extensions part-i: Theory. CoRR, 2019.
Jiahao Ding, Xinyue Zhang, Xiaohuan Li, Junyi Wang, Rong Yu, and Miao Pan. Differentially private and fair classification via calibrated functional mechanism. In AAAI, pp. 622-629, 2020.
Min Du, Ruoxi Jia, and Dawn Song. Robust anomaly detection and backdoor attack detection via differential privacy. In ICLR, 2020.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. UtLhtttp///rcch
ics. uci edu/ml
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith. Calibrating noise sensitiv- ity in private data analysis. In TCC, pp. 265-284. Springer, 2006.
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard S. Zemel. Fairness through awareness. In ITCS, pp. 214-226, 2012.
Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning. In NIPS, pp. 3315-3323, 2016.
Matthew Jagielski, Michael J. Kearns, Jieming Mao, Alina Oprea, Aaron Roth, Saeed Sharifi- Malvajerdi, and Jonathan Ullman. Differentially private fair learning. In ICML., pp. 3000-3008, 2019.
Mimansa Jaiswal and Emily Mower Provost. Privacy enhanced multimodal neural representations for emotion recognition. In AAAI, pp. 7985-7993, 2020.
Faisal Kamiran and Toon Calders. Data preprocessing techniques for classification without discrim- ination, 2011. URL https: google, com wttpoo//le..oomsi//eeeeaae.
ran/
Matt J. Kusner, Joshua R. Loftus, Chris Russell, and Ricardo Silva. Counterfactual fairness. In NIPS, pp. 4066 2017.
Matt Kusner, Chris Russell, Joshua R. Loftus, and Ricardo Silva. Making decisions that reduce discriminatory impacts. In /CMI, 2019.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):228-2324, 1998.
Tian Li, Maziar Sanjabi, Ahmad Beirami, and Virginia Smith. Fair resource allocation in federated learning. In ICLR, 2020.
Risheng Liu, Long Ma. Xiaoming Yuan, Shangzhi Zeng, and Jin Zhang. Bilevel integrative opti- mization for ill-posed inverse problems. CoRR, 2019.

---

Under review as a conference paper at ICLR 2021
H. Brendan McMahan and Galen Andrew. A general approach adding differential privacy to iterative training procedures. PPML@NIPS, 2018.
H. Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang. Learning differentially private recurrent language models. In ICLR, 2018.
Mehryar Mohri, Gary Sivek, and Ananda Theertha Suresh. Agnostic federated learning. JCML, pp. 4615 4625, 2019.
Venkatadheeraj Pichapati, Ananda Theertha Suresh, Felix X. Yu, Sashank J. Reddi, and Sanjiv Ku- mar. AdaCliP: Adaptive clipping for private SGD. CoRR, 2019.
Shuang Song and David Marn.
Introducing a new privacy testing library in https: /bblgg sensorflew..rrg/22000
tensorflow, 2020.
URL
Om Thakkar, Galen Andrew, and H. Brendan McMahan. Differentially private learning with adap- tive clipping. CoRR, 2019.
Koen Lennart van der Veen, Ruben Seggers, Peter Bloem, and Giorgio Patrini. Three tools for practical differential privacy. PPML@NIPS, 2018.
Depeng Xu, Shuhan Yuan, and Xintao Wu. Achieving differential privacy and fairness in logistic regression. In WWW, pp. 594-599, 2019.
Depeng Xu, Wei Du, and Xintao Wu. Removing disparate impact of differentially private stochastic gradient descent on model aceuracy. CoRR, abs/2003.0 03699, 2020.
Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez-Rodriguez, and Krishna P. Gummadi. Fair- ness beyond disparate treatment & disparate impact: Learning classification without disparate mistreatment. In WWW. pp. 1171-1180, 2017.
Richard S. Zemel, Yu Wu, Kevin Swersky, Toniann Pitassi, and Cynthia Dwork. Learning fair representations. In ICML, pp. 325-333, 2013.
Xinyang Zhang, Shouling Ji, and Ting Wang. Differentially private releasing via deep generative model. CoRR, 0tss/800..01555 2018
Tianqing Zhu, Gang Li, Wanlei Zhou, and Philip S. Yu. Differential Privacy and Applications. Advances in Information Security. Springer, 2017.
10


Reviews:
[{"review_id": "o0r1UE35eVk", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Strong Points:\n\n1. Fairness and privacy are both relevant research areas, and knowing how they interact and finding ways to achieve both is certainly important.  \n2. The proposed approach makes sense at a high level, and seems to succeed in achieving the goal.  \n\nWeak Points:\n\n1. Possible problem with DP-SGD (see below).\n2. Some missing details in the algorithm (see below).\n3. Experiments are somewhat confusing (see below).\n\nOther Notes:\n\nThe weak points listed above are more like questions that could use further clarification.  \n\n1. In Equation (2) you describe DP-SGD as adding scalar noise * vector of ones (same noise value to each entry).  However, this is not how DP-SGD usually works.  Is this a typo or can you clarify why you are adding noise in this way?\nHow are you calculating the total privacy cost (eps, delta) at the end of the algorithm.  Do different groups get different levels of privacy protection, and if so what does that mean, and is that considered a fairness violation as well?\n\n\n2. In related work you describe an approach to fairness that works by simply reweighting the loss function to boost impact of under-represented classes.  Wouldn’t that be a simpler approach than what you are doing but provide the same benefits?  Should potentially be considered as a baseline.  \n\n3. \na) Fig 3 doesn’t really make sense as a line plot to me.  \nb) Also measuring privacy by strength of adversaries does not seem natural here, I would prefer to measure privacy using the parameters eps/delta. \nb) Why is DPSGD doing so poorly on the total loss?  I have to wonder if it is just not well-tuned?  My expectation is that mechanisms that don’t impose fairness requirements would achieve better total loss, although more uneven between the classes.  Results differing from this are surprising, and warrant further discussion/explanation.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "iujbUSo9BCB", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper introduces an algorithm for mitigating disparate impact of private learning (DP-SGD) on different groups of a given population. In each iteration of DP-SGD, instead of using a uniform gradient clipping threshold for all groups, the proposed Fair DP-SGD algorithm uses an optimal clipping threshold (one that minimizes the bias-variance tradeoff) for each group separately. The authors include experimental results to show how well their algorithm performs compared to state-of-the-art algorithms.\n\nWhile the problem considered by the authors is very interesting and has impact on real world, I recommend rejection. The major concern I have with this work is that it lacks a formal (differential) privacy statement. I am not even entirely sure that the proposed algorithm is actually differentially private because the step that finds the optimal clipping thresholds seems to use the non-noisy mini-batch gradients without any privatization (please clarify if my understanding is not correct). In any case, if the proposed algorithm is claimed to be (epsilon, delta)-DP then there must be a rigorous proof for it. Also, in the experiments I don't see any reported values for epsilon? Are different methods compared with the same value of epsilon?\n\nOther comments:\n\n-In addition to a formal privacy statement, the authors should formally define the notions of \"privacy\" and \"fairness\" that they use in the paper. Overall, I believe this work can have a better formalization.\n\n-As mentioned earlier, I cannot find the values of epsilon in the experiments. The authors could for e.g. use moments accountant to find the total privacy loss in their experiments.\n\n-When the model is logistic regression (which is the adopted model for 2/3 of the datasets in the experiments) and if the input data is normalized, then the Lipschitz constant L of the (logistic) loss function is a small constant. So in this case clipping the gradients is not necessary because the norm of gradients is always bounded by the Lipschitz constant L which is small and the added noise can be calibrated to L. I think in the case of logistic regression, the authors should also compare their method with a private SGD algorithm that simply adds noise with scale ~ L without any clipping.\n\n-I'm not sure if I understand the optimization problem given in 6a, 6b and how the algorithm is solving it. In particular, the constraint set of the problem seems to be all models with optimal risk (absent any fairness, privacy). But are you actually solving this problem? I.e., does the model output by the algorithm fall into this constraint set?\n\n-The gradients are sometimes denoted by g^t := \\nabla L and other times by \\nabla f (see for e.g. section 2.2). Is f the same as the loss function L? It would be better if a consistent notation was picked for gradients.", "extra_scores": {}, "extra_text": {}}, {"review_id": "ISGQUuNFRGu", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "==== Summary of the problems considered and paper contribution\n\nThis paper studies an important problem: that differentially private algorithms can have disparate impact on model accuracy for different sub communities. This is an important problem because minority populations often suffer the worst decrease in model accuracy. This paper attempts to solve this problem for supervised learning by introducing an adaptive algorithm version of SGD that attempts to equalize the “bias-variance” trade-off at each iteration. Through experiments they show that their algorithm does indeed result in an improvement in fairness, according to a variety of fairness metrics.\n\n==== Comments \n\nMy main concern with the paper is that the privacy claims of Algorithm 1 are not clearly discussed. From my reading, the authors never state whether it is differentially private or not, and this definitely needs clarification. My understanding is that it is NOT differentially private, since the clipping bound is data dependent (according to equation 5), and essentially released in the clear. It’s difficult to tell because I couldn’t find a description of zeta, the amount of noise being added to maintain privacy. If the claim isn’t that Algorithm 1 is DP, then the privacy guarantee is restricted to the results in Figure 3, that attack algorithms perform similarly well on DPSGD, FairDP, and significantly better on SGD (non-private). This is certainly nice to see, but it makes a direct comparison to prior work (that is DP) difficult, and a little unfair.\n\nThe experiments are well designed and nicely show how FairDP improves fairness. I am not a fairness expert, so I’m not sure how representative the fairness metrics used in Table 2 are, but it does seem like FairDP improves on prior work in this regard. \n\n==== Presentation\n\nThe presentation could use some work. There are many grammatical errors, and occasionally sentences that I couldn’t make sense of (“The self-adaptive threshold parameters should be utilized to learn the original machine learning privately with the DP mechanism”). Mathematical sections are often hard to follow, e.g. algorithm 1 is not self contained, what are N and zeta? I didn’t understand what Figure 1 was trying to show?\n\nThe first sentence of section 3.1 seems like a bit dismissive, there is certainly more to the DP ML literature than those three techniques.", "extra_scores": {}, "extra_text": {}}, {"review_id": "HVWLTPCESfx", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper addresses the problem of an unbalanced data set. In particular, the accuracy on the well-represented classes is higher than the accuracy in underrepresented classes in an unbalanced dataset. This paper shows that DPSGD makes the problem of an unbalanced dataset even worse and decreases accuracy on the underrepresented class significantly. Further, this paper introduces a modification of DPSGD, which can increase the underrepresented class's accuracy.\n\nStrengths:  \n1. This paper a self-adaptive DP mechanism to address the problem of an unbalanced dataset.\n2. Extensive numerical examples that demonstrate the performance of FairDP.\n\nWeaknesses:\n1. This paper situates itself in Fairness literature. In the fairness literature, we should have a dataset that includes sensitive attributes and equalize a fairness measure across different (demographic groups). This paper addresses the problem of an unbalanced dataset and tries to equalize the accuracy for different classes (labels). \n2. This paper modifies the DPSGD method without providing that the modified method can achieve differential privacy. In order to make sure the FairDP is $(\\epsilon,\\delta)$-differentially private, they have to theoretically find the privacy parameters with respect to the training datasets. DPSGD (Abadi et al. (2016)) uses the Gaussian mechanism and calculates privacy cost using differential privacy definition. In the current paper, we do not see any privacy analysis, and we are not sure whether FairDP satisfies the differential privacy definition. If FairDP does not satisfy the DP definition or has a very large privacy loss compared to DPSGD, it is not fair to compare FairDP with DPSGD.\n3. This paper compares its own method with other methods that their goal is not to address the problem of an unbalanced dataset. In order to make the experiment more informative, I suggest authors compared FairDP with other algorithms that have been designed for addressing unbalanced datasets. \n  ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes an algorithm to address the disparate effect that DP has on the accuracy of minority/low-frequency sub-populations. Unfortunately the work does not actually guarantee or analyze the resulting privacy guarantees. In particular it may provide much worse privacy (or no privacy at all) to the minority subpopulation.
The paper also calls their algorithm "fair" without using an accepted term or a careful discussion of what an algorithm needs to satisfy to be considered "fair". Using a more technical term such "reducing the accuracy disparity" would make much more sense.

 
Decision: Reject