Year: 2020

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 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 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.

heading: 1 INTRODUCTION
text: Protecting data privacy is a significant concern in many data-driven decision-making 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 et al., 2006). However, DP intentionally restricts the instance influence and introduces noise into the learning procedure. When we enforce DP to a model, DP may amplify the discriminative effect towards the underrepresented and relatively complicated classes (Bagdasaryan et al., 2019; Du et al., 2020; Jaiswal & Provost, 2020). That is, reduction in accuracy from nonprivate learning to private learning may be uneven for each class. There are several empirical studies on utility reduction: (Bagdasaryan et al., 2019; Du et al., 2020) show that the model accuracy in private learning tends to decrease more on classes that already have lower accuracy in non-private learning. (Jaiswal & Provost, 2020) shows different observations that the inequality in accuracy is not consistent for classes across multiple setups and datasets. It needs to 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 a hypothesis f(x; θ) parameterized by θ, which predicts the label y given the unprotected attributes x. Each instance’s label y belongs to a class k. The model aims to minimize the objective (loss) function L(θ;x, y), i.e.,
θ∗ := arg min θ E [L(θ;x, y)] . (1)
Our work builds on a recent advance in machine learning models’ training that uses the differentially private mechanism, i.e., 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
θ̃t+1 = θ̃t − µt · 1 n (∑ i∈St
gt(xi)
max(1, ‖g t(xi)‖2 C )
+ ξ1 ) , (2)
where n and µt denote the batch size and step-size (learning rate) respectively; St denotes the randomly chosen instance set; the vector 1 denotes the vector filled with scalar value one; and gt(xi) denotes the gradient of the loss function in (1) at iteration t, i.e., ∇L(yi; θt,xi). The two key operations of DPSGD are: i) clipping each gradient gt(xi) in `2-norm based on the threshold parameter C; ii) adding noise ξ drawn from Gaussian distribution N (0, σ2C2) with a variance of noise scale σ and the clipping threshold parameter C. These operations enable training machine learning models with non-convex objectives at a manageable privacy cost. Based on the result of traditional SGD, we theoretically analyze the sufficient decrease type scheme of DPSGD, i.e.,
E [ f(θt+1) ] 6 f(θt) + E [〈 ∇f(θt), θt+1 − θt 〉] + L 2 E [∥∥θt+1 − θt∥∥2]+ τ(C, σ; θt), (3)
where the last term τ(C, σ; θt) denotes the gap of loss expectation compared with ideal SGD at this (t+ 1)-th iteration, and related with parameters C, and σ. The term τ(C, σ; θ), which can be called bias-variance term, can be calculated mathematically as
2(1 + 1
µtL ) ‖∇f(θ)‖ · η + η2︸ ︷︷ ︸
Clipping bias
+ 1
n2 · σ2C2|1|︸ ︷︷ ︸
Noise variance
, (4)
where L denotes the Lipschitz constant of f ; |1| denotes the vector dimension; and we have
η := 1
n ∑ I‖gt(xi)‖>C ( ‖gt(xi)‖ − C ) ,
where I‖gt(xi)‖>C denotes the cardinality number of satisfying ‖gt(xi)‖ > C. The detailed proof of (3) and (4) can be found in Appendix A. τ(C, σ) is consist of clipping bias and noise variance terms, which means the amount that the private gradient differs from the non-private gradient due to the influence truncation and depending on the scale of the noise respectively. As a result, we call τ(C, σ) the bias-variance term.
As underrepresented class instances or complicated instances manifest differently from common instances, a uniform threshold parameter C may incur significant accuracy disparate for different classes. In Figure 1(a), we employ DPSGD(Abadi et al., 2016) on the unbalanced MNIST dataset (Bagdasaryan et al., 2019) to numerical study the inequality of utility loss (i.e., the prediction accuracy 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 in a 6.74% decrease in 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 1(b) shows the classification accuracy of different sub-classes for τ(C, σ; θ) on the unbalanced MNIST dataset. Larger bias-variance term τ(C, σ; θ) (determined by C and σ) results in more serious accuracy bias on different classes, while similar results are also shown in (Bagdasaryan et al., 2019; Du et al., 2020; Jaiswal & Provost,
2020). Both theoretical analysis and experimental discussion suggest that minimizing the clipping bias and noise variance simultaneously could learn “better” DP parameters, which mitigates the accuracy bias between different classes. This motivates us to pursue fairness with a self-adaptive differentially privacy scheme1.
This paper proposes a fair differential privacy algorithm (FairDP) to mitigate the disparate impact problem. FairDP introduces a self-adaptive DP mechanism and automatically adjusts instance influence in each class. The main idea is to formulate the problem as bilevel programming by minimizing the bias-variance term as the upper-level objective with a lower-level differential privacy machine learning model. The self-adaptive clipping threshold parameters are calculated by balancing the fairness bias-variance and per-class accuracy terms simultaneously. Our contributions can be summarized as follows:
• FairDP uses a self-adaptive clipping threshold to adjust the instance influence in each class, so the model accuracy for each class is calibrated based on their privacy cost through fairness balancing. The class utility reduction is semblable for each class in 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-adaptive clipping and private model simultaneously.
• Our experimental evaluation shows that FairDP strikes a balance among privacy, fairness, 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-aware learning, and the intersection of differential privacy and fairness. Extensive experiments are further presented in Section 4, and we finally conclude this paper and discuss some future work in Section 5.

heading: 2 FAIRDP: FAIR DIFFERENTIAL PRIVACY

heading: 2.1 THE BILEVEL FAIRDP FORMULATION
text: 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 biasvariance terms arise from capping instance influences to reduce the sensitivity of a machine learning algorithm. In detail, a self-adaptive DP mechanism is designed to balance the bias-variance difference 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 (4) for class k ∈ {1, · · · , `} can be denoted as
τk(Ck, σ; θ ∗) := 2(1 +
1
µtL ) ‖∇f(θ∗)‖ · ηk + ηk2 +
|Gk|2
n2 · σ2Ck2|1|, (5)
where Ck denotes the clipping parameter for class k; Gk denotes the data sample set for class k. As motivated by Section 1, we aim to minimize the associated bias-variance term to obtain a 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 original machine learning privately with the DP mechanism. A simple bilevel programming problem2 (Dempe et al., 2019; Liu et al., 2019) is introduced to model these two goals which influence each
1Note that we do not attempt to optimize the bias-variance bound in a differentially private way, and we are most interested in understanding the forces at play.
2The simple bilevel programming is not to say that the bilevel problem is simple, and it denotes a specific bilevel programming problem.
other. The formulation can be denoted as follows, i.e.,
min {Ck},θ ∑̀ k=1 τk(Ck, σ; θ), (6a)
s.t. θ ∈ arg min θ L(θ; {Gk}`k=1), (6b)
where the upper-level problem (6a) aims to fairly adjust the clipping threshold parameters for all classes, which is related to the classification model θ; as for the lower-level problem (6b), we aim to learn the classification model based on the differential privacy schema with the self-adaptive clipping threshold {Ck}. These two objectives are coupled together, although the model of the lower-level problem is determined only by θ. 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: The FairDP Method Input : Instances {(x1, y1), · · · , (xN , yN )}, objective function L(θ;x, y), learning rate µt;
1 Initialize θ0; 2 for t← 1 to T do 3 Randomly sample a batch of instances St with probability |S
t| N ;
Compute gradient 4 for xi ∈ St do 5 Compute gt(xi)← ∇θtL(yi; θt,xi); 6 end Minimize bias-variance 7 Ct+1k ← arg minCk τk(Ck, σ; θ
t); 8 for xi ∈ St and yi = k do Clip gradient 9 ḡt(xi)← g t(xi)
max ( 1,
‖gt(xi)‖2 C t+1 k ) ; 10 end Add noise 11 g̃t ← 1n ( ∑ i ḡ t(xi) + ξI); Noise Gradient Descent 12 θt+1 ← θt − µtg̃t; 13 end
Output: θT , accumulated privacy cost ( , δ).

heading: 2.2 THE FAIRDP METHOD
text: Calculating the optimal θ∗ and {C∗k} require two nested loops of optimization, and we adopt an alternating strategy to update θ and {Ck} respectively. The FairDP method is summarized in Algorithm 1, while Figure 2 illustrates its main process (i.e., Steps 4-12 in Algorithm 1). For the self-adaptive clipping step (6a) in upper-level, given the current obtained model parameter θt, we
can calculate optimal {Ck} directly by solving a quadratic programming problem. Based on a batch of training samples St (Step 3), the overall gradient∇f(θt) are approximately estimated by∇f̂(θt) with the samples in St. As for private training step (6b) in lower-level, the updating equation of the classifier parameter can be formulated by moving the current θt along the descent direction of the objective loss in (6b) on a batch training data (Step 4-6):
gt(xi) := ∇θtL(yi; θt,xi) (7)
After receiving the classifier parameter updating gt(xi) from (7), the updated θt+1 is employed to ameliorate the parameter θ of the classifier in a DP way as (2) with the obtained clipping parameters {Ck} from Step 7 (Step 8-12). All the details can be found in Algorithm 1.

heading: 3 RELATED WORK

heading: 3.1 PRIVACY-AWARE LEARNING
text: Existing literature in differentially private machine learning can be divided into three main categories, input perturbation, output perturbation, and inner perturbation. The input perturbation approach adds noise to 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 procedure. 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 to 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 ) as a cap can yield suboptimal estimations of a sum (Amin et al., 2019). DP-FEDAVG (McMahan et al., 2018) proposes per-layer clipping, which chooses to distribute the clipping budget across layers. (van der Veen et 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 a pre-processing step via the scaling operation. DP-GAN (Zhang et al., 2018) assumes that we have access to a 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 are above or below the cutoff, only that a fixed number of values are clipped. (Thakkar et al., 2019) 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.
Previous work either ignores computing the trade-off completely (DPSGD(Abadi et al., 2016) simply 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 accessibility of public data).

heading: 3.2 FAIRNESS-AWARE LEARNING
text: Fairness is a broad topic that has received much attention in the machine learning community. However, 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 discrimination against the protected attribute in the predictive decision made by machine learning model (Dwork 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 et al., 2013), optimize the objective function under some fairness constraints during training (Zafar et al., 2017), or post-process the model by adjusting the prediction threshold after classifiers are trained (Hardt
et al., 2016). The others study the discriminatory impact problem (Kusner et al., 2019): how can we reduce the discrimination arising from the impact of decisions.
In federated learning, AFL (Mohri et al., 2019) has taken a step towards addressing accuracy parity by introducing good-intent fairness. The goal is to ensure that the training procedure does not overfit a model to any one class at another’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 a 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.

heading: 3.3 DIFFERENTIAL PRIVACY AND FAIRNESS
text: Recent works study the connection between achieving privacy protection and fairness. (Dwork et al., 2012) proposes a notion of fairness that is a generalization of differential privacy. ADFC (Ding et al., 2020), DP-POSTPROCESSING/DP-ORACLE-LEARNER (Jagielski et al., 2019), PFLR* (Xu et al., 2019) achieve fairness in addition to enforcing differential privacy in the private model. Most existing work focuses on 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.

heading: 4 EXPERIMENTS
text: This section reports our 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.
Datasets: three datasets are used, including the Adult (Dua & Graff, 2017), the Dutch (Kamiran & Calders, 2011) and the Unbalanced MNIST (LeCun et al., 1998)3. The details can be found in Appendix B.
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): private learning with per-layer clipping; 4) Opt-Q: private learning with (1− √ 2/π · σ/e)quantile clipping, which is adapted from (Amin et al., 2019) and details can be found in 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 C.
Settings and hyper-parameters: Without loss of generalization, we assume that the function f is 1-Lipschitz. For the Adult and Dutch datasets, we employ a logistic regression machine learning model. Then for logistic regression, the DP-FedAvg will degenerate to classical DPSGD. The noise scale σ, clipping bound and δ are set to be 1, 0.5 and 10−5 respectively. For the Unbalanced MNIST dataset, we employ a neural network with 2 convolutional layers and 2 fully-connected layers. The noise scale σ, 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) Fairness 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 hyper-parameters on compared private methods.
3The original MNIST dataset is modified by reducing the number of training samples in Class 8 to 500

heading: 4.1 FAIRNESS PERFORMANCE
text: Table 1 and Table 2 provides the comparison results on model accuracy and fairness after implementing different DP methods. Table 1 presents the utility loss of different private learning methods w.r.t. classical SGD. Table 2 presents the comparison on four fairness indexes (Bureau, 2016), including Atkinson Index, Gini Index, MLD and Theil Index (Appendix D.4). 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, it 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.

heading: 4.2 PRIVACY PERFORMANCE
text: 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) is set to be the Area Under the ROC-Curve (AUC) and max |rfp − rtp| (Advantage)4, and lower value means more private. Although FairDP employs selfadaptive clipping parameters, it still maintains a similar level of privacy protection as DPSGD.
4rfp and rtp denotes the false positive rate and true positive rate respectively.

heading: 4.3 ADAPTIVE PERFORMANCE
text: (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 hyperparameters. Figure 4,5 and 6 show that FairDP is insensitive to variations in the hyper-parameters. Because of the space limitation, more results on the Dutch dataset are moved to Appendix E.

heading: 5 CONCLUSION
text: Gradient clipping and noise addition, which are the core techniques in DPSGD, disproportionately affect underrepresented and complex classes. As a consequence, the accuracy of a 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 unfairness. 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.

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

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.