Loss Balancing for Fair Supervised Learning

As machine learning (ML) algorithms are increasingly being used in applications such as education, lending, recruitment, healthcare, criminal justice, etc., there is a growing concern that the algorithms may exhibit discrimination against protected population groups. For example, speech recognition products such as Google Home and Amazon Alexa were shown to have accent bias (Harwell, 2018). The COMPAS recidivism prediction tool, used by courts in the US in parole decisions, has been shown to have a substantially higher false positive rate for African Americans compared to the general population (Dressel and Farid, 2018). Amazon had been using automated software since 2014 to assess applicants’ resumes, which were found to be biased against women (Dastin, 2018). As a result, there have been several works focusing on interpreting machine learning models to understand how features and sensitive attributes contribute to the output of the model (Ribeiro et al., 2016; Lundberg and Lee, 2017; Abroshan et al., 2023).

Various fairness notions have been proposed in the literature to measure and remedy the biases in ML systems; they can be roughly classified into two categories: 1) individual fairness focuses on equity at the individual level and it requires similar individuals to be treated similarly (Dwork et al., 2012; Biega et al., 2018; Jung et al., 2019; Gupta and Kamble, 2019); 2) group fairness requires certain statistical measures to be (approximately) equalized across different groups distinguished by some sensitive attributes (Hardt et al., 2016; Conitzer et al., 2019; Khalili et al., 2020; Zhang et al., 2020; Khalili et al., 2021; Diana et al., 2021; Williamson and Menon, 2019; Zhang et al., 2022).

Several approaches have been developed to satisfy a given definition of fairness; they fall under three categories: 1) pre-processing, by modifying the original dataset such as removing certain features and reweighing, (e.g., (Kamiran and Calders, 2012; Celis et al., 2020; Abroshan et al., )); 2) in-processing, by modifying the algorithms such as imposing fairness constraints or changing objective functions during the training process, (e.g., (Zhang et al., 2018; Agarwal et al., 2018, 2019; Reimers et al., 2021; Calmon et al., 2017)); 3) post-processing, by adjusting the output of the algorithms based on sensitive attributes, (e.g., (Hardt et al., 2016)).

In this paper, we focus on group fairness, and we aim to mitigate unfairness issues in supervised learning using an in-processing approach. This problem can be cast as a constrained optimization problem by minimizing a loss function subject to a group fairness constraint. We are particularly interested in the Equalized Loss (EL) fairness notion proposed by Zhang et al. (2019), which requires the expected loss (e.g., Mean Squared Error (MSE), Binary Cross Entropy (BCE) Loss) to be equalized across different groups.¹¹1 Zhang et al. (2019) propose the EL fairness notion without providing an efficient algorithm for satisfying this notion.

The problem of finding fair predictors by solving constrained optimizations has been largely studied. Komiyama et al. (2018) propose the coefficient of determination constraint for learning a fair regressor and develop an algorithm for minimizing the mean squared error (MSE) under their proposed fairness notion. Agarwal et al. (2019) propose an approach to finding a fair regression model under bounded group loss and statistical parity fairness constraints. Agarwal et al. (2018) study classification problems and aim to find fair classifiers under various fairness notions including statistical parity and equal opportunity. In particular, they consider zero-one loss as the objective function and train a randomized fair classifier over a finite hypothesis space. They show that this problem can be reduced to a problem of finding the saddle point of a linear Lagrangian function. Zhang et al. (2018) propose an adversarial debiasing technique to find fair classifiers under equalized odd, equal opportunity, and statistical parity. Unlike the previous works, we focus on the Equalized Loss fairness notion which has not been well studied. Finding an EL fair predictor requires solving a non-convex optimization. Unfortunately, there is no algorithm in fair ML literature with a theoretical performance guarantee that can be properly applied to EL fairness (see Section 2 for detailed discussion).

Our main contribution can be summarized as follows,

• •

  We develop an algorithm with a theoretical performance guarantee for EL fairness. In particular, we propose the $(\texttt{ELminimizer})$ algorithm to solve a non-convex constrained optimization problem that finds the optimal fair predictor under EL constraint. We show that such a non-convex optimization problem can be reduced to a sequence of convex constrained optimizations. The proposed algorithm finds the global optimal solution and is applicable to both regression and classification problems. Importantly, it can be easily implemented using off-the-shelf convex programming tools.

• •

  In addition to ELminimizer which finds the global optimal solution, we develop a simple algorithm for finding a sub-optimal predictor satisfying EL fairness. We prove there is a sub-optimal solution satisfying EL fairness that is a linear combination of the optimal solutions to two unconstrained optimizations, and it can be found without solving any constrained optimizations.

• •

  We conduct sample complexity analysis and provide a generalization performance guarantee. In particular, we show the sample complexity analysis found in (Donini et al., 2018) is applicable to learning problems under EL.

• •

  We also examine (in the appendix) the relation between Equalized Loss (EL) and Bounded Group Loss (BGL), another fairness notion proposed by (Agarwal et al., 2019). We show that under certain conditions, these two notions are closely related, and they do not contradict each other.

Consider a supervised learning problem where the training dataset consists of triples $(\boldsymbol{X},A,Y)$ from two social groups.²²2We use bold letters to represent vectors. Random variable $\boldsymbol{X}\in\mathcal{X}$ is the feature vector (in the form of a column vector), $A\in\{0,1\}$ is the sensitive attribute (e.g., race, gender) indicating the group membership, and $Y\in\mathcal{Y}\subseteq\mathbb{R}$ is the label/output.We denote realizations of random variables by small letters (e.g., $(\boldsymbol{x},a,y)$ is a realization of $(\boldsymbol{X},A,Y)$). Feature vector $\boldsymbol{X}$ may or may not include sensitive attribute $A$. Set $\mathcal{Y}$ can be either $\{0,1\}$ or $\mathbb{R}$: if $\mathcal{Y}=\{0,1\}$ (resp. $\mathcal{Y}=\mathbb{R}$), then the problem of interest is a binary classification (resp. regression) problem.

Let $\mathcal{F}$ be a set of predictors $f_{\boldsymbol{w}}:\mathcal{X}\to\mathbb{R}$ parameterized by weight vector $\boldsymbol{w}$ with dimension $d_{\boldsymbol{w}}$.³³3Predictive models such as logistic regression, linear regression, deep learning models, etc., are parameterized by a weight vector. If the problem is binary classification, then $f_{\boldsymbol{w}}(\boldsymbol{x})$ is an estimate of $\Pr(Y=1|\boldsymbol{X}=\boldsymbol{x})$.⁴⁴4Our framework can be easily applied to multi-class classifications, where $f_{\boldsymbol{w}}(\boldsymbol{X})$ becomes a vector. Because it only complicates the notations without providing additional insights about our algorithm, we present the method and algorithm in a binary setting. Consider loss function $l:\mathcal{Y}\times\mathbb{R}\to\mathbb{R}$ where $l(Y,f_{\boldsymbol{w}}(\boldsymbol{X}))$ measures the error of $f_{\boldsymbol{w}}$ in predicting $\boldsymbol{X}$. We denote the expected loss with respect to the joint probability distribution of $(\boldsymbol{X},Y)$ by $L(\boldsymbol{w}):=\mathbb{E}\{l(Y,f_{\boldsymbol{w}}(\boldsymbol{X}))\}$. Similarly, $L_{a}(\boldsymbol{w}):=\mathbb{E}\{l(Y,f_{\boldsymbol{w}}(\boldsymbol{X}))|A=a\}$ denotes the expected loss of the group with sensitive attribute $A=a$. In this work, we assume that $l(y,f_{\boldsymbol{w}}(\boldsymbol{x}))$ is differentiable and strictly convex in ${\boldsymbol{w}}$ (e.g., binary cross entropy loss).⁵⁵5We do not consider non-differentiable losses (e.g., zero-one loss) as they have already been extensively studied in the literature, e.g., (Hardt et al., 2016; Zafar et al., 2017; Lohaus et al., 2020).

Without fairness consideration, a predictor that simply minimizes the total expected loss, i.e., $\operatorname*{arg\,min}_{\boldsymbol{w}}L(\boldsymbol{w})$, may be biased against certain groups. To mitigate the risks of unfairness, we consider Equalized Loss (EL) fairness notion, as formally defined below.

Note that if $l(Y,f_{\boldsymbol{w}}(\boldsymbol{X}))$ is a (strictly) convex function in $\boldsymbol{w}$, both $L_{0}(\boldsymbol{w})$ and $L_{1}(\boldsymbol{w})$ are also (strictly) convex in ${\boldsymbol{w}}$. However, $L_{0}(\boldsymbol{w})-L_{1}(\boldsymbol{w})$ is not necessary convex⁶⁶6As an example, consider two functions $h_{0}(x)=x^{2}$ and $h_{1}(x)=2\cdot x^{2}-x$. Although both $h_{0}$ and $h_{1}$ are convex, their difference $h_{0}(x)-h_{1}(x)$ is not a convex function. . As a result, the following optimization problem for finding a fair predictor under $\gamma$-EL is not a convex programming,

We say a group is disadvantaged group if it experiences higher loss than the other group. Before discussing how to find the global optimal solution of the above non-convex optimization problem and train a $\gamma$-EL fair predictor, we first discuss why $\gamma$-EL is an important fairness notion and why the majority of fair learning algorithms in the literature cannot be used for finding $\gamma$-EL fair predictors.

In this section, we consider optimization problem (1) under EL fairness constraint. Note that this optimization problem is non-convex and finding the global optimal solution is difficult. We propose an algorithm that finds the solution to non-convex optimization (1) by solving a sequence of convex optimization problems. Before presenting the algorithm, we first introduce two assumptions, which will be used when proving the convergence of the proposed algorithm.

Let $\boldsymbol{w}_{G_{a}}$ be the optimal weight vector minimizing the loss associated with group $A=a$. That is,

Since problem (5) is an unconstrained, convex optimization problem, $\boldsymbol{w}_{G_{a}}$ can be found efficiently by common convex solvers. We make the following assumption about $\boldsymbol{w}_{G_{a}}$.

Assumption 3.2 implies that when a group experiences its lowest possible loss, this group is not the disadvantaged group. Under Assumptions 3.1 and 3.2, the optimal 0-EL fair predictor can be easily found using our proposed algorithm (i.e., function $\texttt{ELminimizer}(\boldsymbol{w}_{G_{0}},\boldsymbol{w}_{G_{1}},\epsilon,\gamma)$ with $\gamma=0$); the complete procedure is shown in Algorithm 1, in which parameter $\epsilon>0$ specifies the stopping criterion: as $\epsilon\to 0$, the output approaches to the global optimal solution.

Intuitively, Algorithm 1 solves non-convex optimization (1) by solving a sequence of convex and constrained optimizations. When $\gamma>0$ (i.e., relaxed fairness), the optimal $\gamma$-EL fair predictor can be found with Algorithm 2 which calls function ELminimizer twice. The convergence of Algorithm 1 for finding the optimal 0-EL fair solution, and the convergence of Algorithm 2 for finding the optimal $\gamma$-EL fair solution are stated in the following theorems.

Theorem 3.3 implies that when $\gamma=\epsilon=0$ and $i$ goes to infinity, the solution to convex problem (4) is the same as the solution to (1).

Complexity Analysis. The While loop in Algorithm 1 is executed for $\mathcal{O}(\log(1/\epsilon))$ times. Therefore, Algorithm 1 needs to solve a constrained convex optimization problem for $\mathcal{O}(\log(1/\epsilon))$ times. Note that constrained convex optimization problems can be efficiently solved via sub-gradient methods (Nedić and Ozdaglar, 2009), brier methods (Wright, 2001), stochastic gradient descent with one projection (Mahdavi et al., 2012), interior point methods (Nemirovski, 2004), etc. For instance, (Nemirovski, 2004) shows that several convex optimization problems can be solved in polynomial time. Therefore, the time complexity of Algorithm 1 depends on the convex solver. If the time complexity of solving (4) is $\mathcal{O}(p(d_{\boldsymbol{w}}))$, then the overall time complexity of Algorithm 1 is $\mathcal{O}(p(d_{\boldsymbol{w}})\log(1/\epsilon))$.

Regularization. So far we have considered a supervised learning model without regularization. Next, we explain how Algorithm 2 can be applied to a regularized problem. Consider the following optimization problem,

where $R(\boldsymbol{w})$ is a regularizer function. In this case, we can re-write the optimization problem as follows,

If we define $\bar{L}_{a}({\boldsymbol{w}}):=L_{a}(\boldsymbol{w})+R(\boldsymbol{w})$ and $\bar{L}(\boldsymbol{w}):=\Pr(A=0)\bar{L}_{0}(\boldsymbol{w})+\Pr(A=1)\bar{L}_{1}(\boldsymbol{w}),$ then problem (6) can be written in the form of problem (1) using $(\bar{L}_{0}({\boldsymbol{w}}),\bar{L}_{1}({\boldsymbol{w}}),\bar{L}({\boldsymbol{w}}))$ and solved by Algorithm 2.

In Section 3, we have shown that non-convex optimization problem (1) can be reduced to a sequence of convex constrained optimizations (4), and based on this we proposed Algorithm 2 that finds the optimal $\gamma$-EL fair predictor. However, the proposed algorithm still requires solving a convex constrained optimization in each iteration. In this section, we propose another algorithm that finds a sub-optimal solution to optimization (1) without solving constrained optimization in each iteration. The algorithm consists of two phases: (1) finding two weight vectors by solving two unconstrained convex optimization problems; (2) generating a new weight vector satisfying $\gamma$-EL using the two weight vectors found in the first phase.

Phase 1: Unconstrained optimization. We ignore EL fairness and solve the following unconstrained problem,

Because $L(\boldsymbol{w})$ is strictly convex in $\boldsymbol{w}$, the above optimization problem can be solved efficiently using convex solvers. Predictor $f_{\boldsymbol{w}_{O}}$ is the optimal predictor without fairness constraint, and $L(\boldsymbol{w}_{O})$ is the smallest overall expected loss that is attainable. Let $\hat{a}=\arg\max_{a\in\{0,1\}}L_{a}(\boldsymbol{w}_{O})$, i.e., group $\hat{a}$ is disadvantaged under predictor $f_{\boldsymbol{w}_{O}}$. Then, for the disadvantaged group $\hat{a}$, we find $\boldsymbol{w}_{G_{\hat{a}}}$ by optimization (5).

Phase 2: Binary search to find the fair predictor. For $\beta\in[0,1]$, we define the following two functions,

where function $g(\beta)$ can be interpreted as the loss disparity between two demographic groups under predictor $f_{(1-\beta)\boldsymbol{w}_{O}+\beta\boldsymbol{w}_{G_{\hat{a}}}}$, and $h(\beta)$ is the corresponding overall expected loss. Some properties of functions $g(.)$ and $h(.)$ are summarized in the following theorem.

Theorem 4.1 implies that in a $d_{\boldsymbol{w}}$-dimensional space if we start from $\boldsymbol{w}_{O}$ and move toward $\boldsymbol{w}_{G_{\hat{a}}}$ along a straight line, the overall loss increases and the disparity between two groups decreases until we reach $(1-\beta_{0})\boldsymbol{w}_{O}+\beta_{0}\boldsymbol{w}_{G_{\hat{a}}}$, at which 0-EL fairness is satisfied. Note that $\beta_{0}$ is the unique root of $g$. Since $g(\beta)$ is a strictly decreasing function, $\beta_{0}$ can be found using binary search.

For the approximate $\gamma$-EL fairness, there are multiple values of $\beta$ such that $(1-\beta)\boldsymbol{w}_{O}+\beta\boldsymbol{w}_{G_{\hat{a}}}$ satisfies $\gamma$-EL. Since $h(\beta)$ is strictly increasing in $\beta$, among all $\beta$ that satisfy $\gamma$-EL fairness, we would choose the smallest one. The method for finding a sub-optimal solution to optimization (1) is described in Algorithm 3.

Note that while loop in Algorithm 3 is repeated for $\mathcal{O}(\log(1/\epsilon))$ times. Since the time complexity of operations (i.e., evaluating $g_{\gamma}(\beta_{mid}^{(i)})$) in each iteration is $\mathcal{O}(d_{\boldsymbol{w}})$ , the total time complexity of Algorithm 3 is $\mathcal{O}(d_{\boldsymbol{w}}\log(1/\epsilon))$. We can formally prove that the output returned by Algorithm 3 satisfies $\gamma$-EL constraint.

Note that since $h(\beta)$ is increasing in $\beta$, we only need to find the smallest possible $\beta$ such that $(1-\beta)\boldsymbol{w}_{O}+\beta\boldsymbol{w}_{G_{\hat{a}}}$ satisfies $\gamma$-EL, which is $\beta_{mid}^{(\infty)}$ in Theorem 4.2. Since Algorithm 3 finds a sub-optimal solution, it is important to investigate the performance of this sub-optimal fair predictor, especially in the worst case scenario. The following theorem finds an upper bound of the expected loss of $f_{\boldsymbol{\underline{w}}}$, where $\boldsymbol{\underline{w}}$ is the output of Algorithm 3.

Learning with Finite Samples. So far we proposed algorithms for solving optimization (1). In practice, the joint probability distribution of $(\boldsymbol{X},A,Y)$ is unknown and the expected loss needs to be estimated using the empirical loss. Specifically, given $n$ i.i.d. samples $\{(\boldsymbol{X}_{i},A_{i},Y_{i})\}_{i=1}^{n}$ and a predictor $f_{\boldsymbol{w}}$, the empirical losses of the entire population and each group are defined as follows,

where $n_{a}=|\{i|A_{i}=a\}|$. Because $\gamma$-EL fairness constraint is defined in terms of expected loss, the optimization problem of finding an optimal $\gamma$-EL fair predictor using empirical losses is as follows,

In this section, we aim to investigate how to determine $\hat{\gamma}$ so that with high probability, the predictor found by solving problem (8) satisfies $\gamma$-EL fairness, and meanwhile $\boldsymbol{\hat{w}}$ is a good estimate of the solution $\boldsymbol{w}^{*}$ to optimization (1). We aim to show that we can set $\hat{\gamma}=\gamma$ if the number of samples is sufficiently large. To understand the relation between (8) and (1), we follow the general sample complexity analysis found in (Donini et al., 2018) and show their sample complexity analysis is applicable to EL. To proceed, we make the assumption used in (Donini et al., 2018).

Note that according to (Shalev-Shwartz and Ben-David, 2014), if the class $\mathcal{F}$ is learnable with respect to loss function $l(.,.)$, then always there exists such a bound $B(\delta,n,\mathcal{F})$ that goes to zero as $n$ goes to infinity.⁹⁹9As an example, if $\mathcal{F}$ is a compact subset of linear predictors in Reproducing Kernel Hilbert Space (RKHS) and loss $l(y,f(x))$ is Lipschitz in $f(x)$ (second argument), then Assumption 4.4 can be satisfied (Bartlett and Mendelson, 2002). Vast majority of linear predictors such as support vector machine and logistic regression can be defined in RKHS.

Theorem 4.5 shows that as $n_{0}$, $n_{1}$ go to infinity, $\hat{\gamma}\to\gamma$, and both empirical loss and expected loss satisfy $\gamma$-EL. In addition, as $n$ goes to infinity, the expected loss at $\hat{\boldsymbol{w}}$ goes to the minimum possible expected loss. Therefore, solving (8) using empirical loss is equivalent to solving (1) if the number of data points from each group is sufficiently large.

So far, we have assumed that the loss function is strictly convex. This assumption is mainly valid for training linear models (e.g., Ridge regression, regularized logistic regression). However, it is known that training deep models lead to minimizing non-convex objective functions. To train a deep model under the equalized loss fairness notion, we can take advantage of Algorithm 2 for fine-tuning under EL as long as the objective function is convex with respect to the parameters of the output layer.¹⁰¹⁰10In classification or regression problems with l2 regularizer, the objective function is strictly convex with respect to the parameters of the output layer. This is true regardless of the network structure before the output layer. To clarify how Algorithm 2 can be used for deep models, for simplicity, consider a neural network with one hidden layer for regression. Let $W$ be an $m$ by $d$ matrix ($d$ is the size of feature vector $\boldsymbol{X}$ and $m$ is the number of neurons in the first layer) denoting the parameters of the first layer of the Neural Network, and $\boldsymbol{w}$ be a vector corresponding to the output layer. To find a neural network satisfying the equalized loss fairness notion, first, we train the network without any fairness constraint using common gradient descent algorithms (e.g., stochastic gradient descent). Let $\tilde{W}$ and $\tilde{\boldsymbol{w}}$ denote the network parameters after training the network without fairness constraint. Now we can take advantage of Algorithm 2 to fine-tune the parameters of the output layer under the equalized loss fairness notion. Let us define $\tilde{\boldsymbol{X}}:=[1,\tilde{W}\cdot\boldsymbol{X}]^{T}$. The problem for fine-tuning the output layer can be written as follows,

The objective function of the above optimization problem is strictly convex, and the optimization problem can be solved using Algorithm 2. After solving the above problem, $[\tilde{W},\boldsymbol{w}^{*}]$ will be the final parameters of the neural network model satisfying the equalized loss fairness notion. Note that a similar optimization problem can be written for fine-tuning any deep model with classification/regression task.

We conduct experiments on two real-world datasets to evaluate the performance of the proposed algorithm. In our experiments, we used a system with the following configurations: 24 GB of RAM, 2 cores of P100-16GB GPU, and 2 cores of Intel Xeon [email protected] GHz processor. More information about the experiments and the instructions on reproducing the empirical results are provided in Appendix. The codes are available at https://github.com/KhaliliMahdi/Loss_Balancing_ICML2023.

Baselines. As discussed in Section 2, not all the fair learning algorithms are applicable to EL fairness. The followings are three baselines that are applicable to EL fairness.

Penalty Method (PM): The penalty method (Ben-Tal and Zibulevsky, 1997) finds a fair predictor under $\gamma$-EL fairness constraint by solving the following problem,

where $t$ is the penalty parameter, and $R(\boldsymbol{w})=0.002\cdot||\boldsymbol{w}||_{2}^{2}$ is the regularizer. The above optimization problem cannot be solved with a convex solver because it is not generally convex. We solve problem (10) using Adam gradient descent (Kingma and Ba, 2014) with a learning rate of $0.005$. We use the default parameters of Adam optimization in Pytorch. We set the penalty parameter $t=0.1$ and increase this penalty coefficient by a factor of $2$ every $100$ iteration.

Linear Relaxation (LinRe): Inspired by (Donini et al., 2018), for the linear regression, we relax the EL constraint as $-\gamma\leq\frac{1}{n_{0}}\sum_{i:A_{i}=a}(Y_{i}-\boldsymbol{w}^{T}\boldsymbol{X}_{i})-\frac{1}{n_{1}}\sum_{i:A_{i}=1}(Y_{i}-\boldsymbol{w}^{T}\boldsymbol{X}_{i})\leq\gamma$. For the logistic regression, we relax the constraint as $-\gamma\leq\frac{1}{n_{0}}\sum_{i:A_{i}=a}(Y_{i}-0.5)\cdot(\boldsymbol{w}^{T}\boldsymbol{X}_{i})-\frac{1}{n_{1}}\sum_{i:A_{i}=1}(Y_{i}-0.5)\cdot(\boldsymbol{w}^{T}\boldsymbol{X}_{i})\leq\gamma$. Note that the sign of $(Y_{i}-0.5)\cdot(\boldsymbol{w}^{T}\boldsymbol{X}_{i})$ determines whether the binary classifier makes a correct prediction or not.

FairBatch (Roh et al., 2020): This method was originally proposed for equal opportunity, statistical parity, and equalized odds. With some modifications (see the appendix for more details), this can be applied to EL fairness. This algorithm measures the loss of each group in each epoch and changes the Minibatch sampling distribution in favor of the group with a higher empirical loss. When implementing FairBatch, we use Adam optimization with default parameters, a learning rate of $0.005$, and a batch size of $100$.

Linear Regression and Law School Admission Dataset. In the first experiment, we use the law school admission dataset, which includes the information of 21,790 law students studying in 163 different law schools across the United States (Wightman, 1998). This dataset contains entrance exam scores (LSAT), grade-point average (GPA) prior to law school, and the first year average grade (FYA). Our goal is to train a $\gamma$-EL fair regularized linear regression model to estimate the FYA of students given their LSAT and GPA. In this study, we consider Black and White Demographic groups. In this dataset, $18285$ data points belong to White students, and $1282$ data points are from Black students. We randomly split the dataset into training and test datasets (70% for training and 30% for testing), and conduct five independent runs of the experiment. A fair predictor is found by solving the following optimization problem,

with $\hat{L}$ and $\hat{L}_{a}$ being the overall and the group specific empirical MSE, respectively. Note that $0.002\cdot||\boldsymbol{w}||_{2}^{2}$ is the regularizer. We use Algorithm 2 and Algorithm 3 with $\epsilon=0.01$ to find the optimal linear regression model under EL and adopt CVXPY python library (Diamond and Boyd, 2016; Agrawal et al., 2018) as the convex optimization solver in ELminimizer algorithm.

Table 1 illustrates the means and standard deviations of empirical loss and the loss difference between Black and White students. The first row specifies desired fairness level ($\gamma=0$ and $\gamma=0.1$) used as the input to each algorithm. Based on Table 1, when desired fairness level is $\gamma=0$, the model fairness level trained by LinRe and FairBatch method is far from $\gamma=0$. We also realized that the performance of FairBatch highly depends on the random seed. As a result, the fairness level of the model trained by FairBatch has a high variance (0.1933 in this example) in these five independent runs of the experiment, and in some of these runs, it can achieve desired fairness level. This is because the FairBatch algorithm does not come with any performance guarantee, and as stated in (Roh et al., 2020), FairBatch calculates a biased estimate of the gradient in each epoch, and the mini-batch sampling distribution keeps changing from one epoch to another epoch. We observed that FairBatch has better performance with a non-linear model (see Table 3). Both Algorithms 2 and 3 can achieve a fairness level close to $\gamma=0$. However, Algorithm 3 finds a sub-optimal solution and achieves higher MSE compared to Algorithm 2. For $\gamma=0.1$, in addition to Algorithms 2 and 3, the penalty method also achieves a fairness level close to desired fairness level $\gamma=0.1$ (i.e., $|\hat{L}_{1}-\hat{L}_{0}|=0.0892$). Algorithm 2 still achieves the lowest MSE compared to Algorithm 3 and the penalty method. The model trained by FairBatch also suffers from high variance in the fairness level. We want to emphasize that even though Algorithm 3 has a higher MSE compared to Algorithm 2, it is much faster, as stated in Section 3.

We also investigate the trade-off between fairness and overall loss under different algorithms. Figure 2 illustrates the MSE loss as a function of the loss difference between Black and White students. Specifically, we run Algorithm 2, Algorithm 3, and the baselines under different values of $\gamma=[0.0250,0.05,0.1,0.15,0.2]$. For each $\gamma$, we repeat the experiment five times and calculate the average MSE and average MSE difference over these five runs using the test dataset. Figure 2 shows the penalty method, linear relaxation, and FairBatch are not sensitive to input $\gamma$. However, Algorithm 2 and Algorithm 3 are sensitive to $\gamma$; As $\gamma$ increases, $|\hat{L}_{0}(\boldsymbol{w}^{*})-\hat{L}_{1}(\boldsymbol{w}^{*})|$ increases and MSE decreases.

Logistic Regression and Adult Income Dataset. We consider the adult income dataset containing the information of 48,842 individuals (Kohavi, 1996). Each data point consists of 14 features, including age, education, race, etc. In this study, we consider race (White or Black) as the sensitive attribute and denote the White demographic group by $A=0$ and the Black group by $A=1$. We first pre-process the dataset by removing the data points with a missing value or with a race other than Black and White; this results in 41,961 data points. Among these data points, 4585 belong to the Black group. For each data point, we convert all the categorical features to one-hot vectors with $110$ dimension and randomly split the dataset into training and test data sets (70% of the dataset is used for training). The goal is to predict whether the income of an individual is above $\$50K$ using a $\gamma$-EL fair logistic regression model. In this experiment, we solve optimization problem (11), with $\hat{L}$ and $\hat{L}_{a}$ being the overall and the group specific empirical average of binary cross entropy (BCE) loss, respectively.

The comparison of Algorithm 2, Algorithm 3, and the baselines is shown in Table 2, where we conduct five independent runs of experiments, and calculate the mean and standard deviation of overall loss and the loss difference between two demographic groups. The first row in this table shows the value of $\gamma$ used as an input to the algorithms. The results show that linear relaxation, algorithm 2 and Algorithm 3 have very similar performances. All of these three algorithms are able to satisfy the $\gamma$-EL with small test loss. Similar to Table 1, we observe the high variance in the performance of FairBatch, which highly depends on the random seed.

In Figure 2, we compare the performance-fairness trade-off. We focus on binary cross entropy on the test dataset. To generate this figure, we run Algorithm 2, Algorithm 3, and the baselines (we do not include the curve for FairBatch due to large overall loss and high variance in performance) under different values of $\gamma=[0.02,0.04,0.06,0.08,0.1]$ for five times and calculate the average BCE and the average BCE difference. We observe Algorithms 2 and 3 and the linear relaxation have a similar trade-off between $\hat{L}$ and $|\hat{L}_{0}-\hat{L}_{1}|$.