{'fraction_non_alphanumeric': 0.03539279869067103, 'fraction_numerical': 0.009819967266775777, 'mean_word_length': 4.42597474677397, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 14, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
FairGrad: Fairness Aware Gradient Descent

We tackle the problem of group fairness in classification, where the objective is to learn models that do not unjustly discriminate against subgroups of the population. Most existing approaches are limited to simple binary tasks or involve difficult to implement training mechanisms. This reduces their practical applicability. In this paper, we propose FairGrad, a method to enforce fairness based on a reweighting scheme that iteratively learns group specific weights based on whether they are advantaged or not. FairGrad is easy to implement and can accommodate various standard fairness definitions. Furthermore, we show that it is comparable to standard baselines over various datasets including ones used in natural language processing and computer vision.


Introduction
Fair Machine Learning addresses the problem of learning models that are free from any discriminative behaviour against a subset of the population. For example, assume that a hiring company develops a model to predict which job would suit a person based on its biography. The competent individuals should get the same opportunity to get each job regardless of their gender, ethnicity, or of other sensitive attributes. This is Equalized Odds. Similarly, the probability of getting accepted to a university should be the same regardless of whether an individual belongs to a subgroup of the population or not. This is Equality of Opportunity. In this paper, we focus on learning fair models for classification tasks.
Several fairness notions have been proposed in the literature as different problems call for different measures. These definitions may be divided into two main families. On the one hand, the idea behind Individual Fairness [12,30] is that similar individual should be treated similarly regardless of the sensitive group they belong to. On the other hand, in Group Fairness [3,20,41,9] the underlying idea is that the different sensitive groups should not be disadvantaged compared to the overall reference population. In this paper, we focus on group fairness. More precisely, we assume that we have access to a fairness measure that is positive when a group is advantaged compared to the overall population and negative otherwise. We show that this definition encompasses several existing group fairness definitions including Equalized Odds or Accuracy Parity.
The existing approaches for group fairness in Machine Learning may be divided into three main paradigms. First, pre-processing methods aim at modifying a dataset to remove any intrinsic unfairness that may exist in the examples. The underlying idea is that a model learned on this modified data is more likely to be fair [12,25,43,15,5]. Then, post-processing approaches modify the predictions of an accurate but unfair model so that it becomes fair [26,20,39,22,7]. Finally, in-processing methods aim at learning a model that is fair and accurate in a single step [4,27,17,41,42,10,29,1,40,8,23,24,33,38,35]. In this paper, we propose a new in-processing approach based on a reweighting scheme that may also be used as a kind of post-processing approach by fine-tuning existing classifiers.
Motivation. In-processing approaches can be further divided into several sub-categories [6]. Common amongst them are methods based on relaxations of the fairness constraints under consideration [41, 10,40]. Indeed, standard fairness notions are usually difficult to handle as they are often arXiv:2206.10923v1 [cs.LG] 22 Jun 2022 non-convex and non-differentiable. The goal is thus to propose surrogates that are easier to handle. Unfortunately, these relaxations may be far from the actual fairness measures, leading to sub-optimal models [33]. Similarly, several approaches address the fairness problem by designing specific algorithms and solvers. This is for example done by reducing the optimization procedure to a simpler problem [1], altering the underlying solver [8], or using adversarial learning [36]. Unfortunately, these approaches are often difficult to implement in practice and may be limited in the range of problems that they can be applied to (binary classification, two sensitive groups, . . . ). Furthermore, they may come with several hyper-parameters that need to be carefully tuned in order to obtain fair models.
Contributions. In this paper, we propose FairGrad, a general purpose approach to enforce fairness for gradient descent based methods. Our method follows from the idea that fairness can be achieved by simply changing the importance of each group while learning a model [29,23,24]. Hence, instead of using the same weight for all the examples, the idea is to use lower weights for examples coming from advantaged groups than for examples coming from disadvantaged groups. More precisely, we propose to dynamically update the weights of the examples after each gradient descent update in order to precisely reflect the fairness level of the models obtained after each iteration. A key advantage of our approach is that it is easy to incorporate in standard gradient based solvers that support reweighting of the examples. Furthermore, it does not bring forth any new hyper-parameters beside the usual optimization ones (learning rates, batch size, . . . ), can be used for various group fairness notions, including exact and approximate fairness, and is able to handle both multiple sensitive groups and multiclass problems. Through extensive experiments, we show that FairGrad is competitive with several standard baselines in fairness on standard fairness datasets and complex natural language processing and computer vision tasks.

Problem Setting and Notations
In the remainder of this paper, we assume that we have access to a feature space X , a finite discrete label space Y, and a finite discrete sensitive attribute space S. We further assume that there exists an unknown distribution D ∈ D Z where D Z is the set of all distributions over Z = X × Y × S and that we only get to observe a finite dataset T = {(x i , y i , s i )} n i=1 of n examples drawn i.i.d. from D. Our goal is then to learn an accurate model h θ ∈ H, with learnable parameters θ ∈ R D , such that h θ : X → Y is fair with respect to a given fairness definition that depends on the sensitive attribute. In Section 3.1, we formally define the fairness measures that are compatible with our approach and provide several examples of popular notions that are compatible with our method. Finally, for the ease of presentation, throughout this paper we slightly abuse the notation P (E) and use it to represent both the true probability of an event E and its estimated probability from a finite sample.

Related Work
The fairness literature is extensive and we refer the interested reader to recent surveys [6,34] to get an overview of the subject. In this section, we focus on recent works that are more closely related to our approach.
BiFair [35]. This paper proposes a bilevel optimization scheme for fairness. The idea is to use an outer optimization scheme that learns weights for each example so that the trade-off between fairness and accuracy is as favorable as possible while an inner optimization scheme learns a model that is as accurate as possible. One of the limits of this approach is that it does not directly optimize the fairness level of the model but rather a relaxation that does not provide any guarantees on the goodness of the learned predictor. Furthermore, it is limited to binary classification with binary sensitive attribute. In this paper, we also learn weights for the examples in an iterative way. However, we use a different update rule. Furthermore, we focus on proper fairness definitions rather than relaxations and our objective is to learn accurate models with given levels of fairness rather than a trade-off between the two. Finally, our approach is not limited to the binary setting.
FairBatch [38]. This paper proposes a batch gradient descent approach that can be used to learn fair models. More precisely, the idea is to draw the batch examples from a skewed distribution that favors the disadvantaged groups by oversampling them. In this paper, we propose to use a reweighting approach which could also be interpreted as altering the distribution of the examples based on their fairness level if all the weights were positive. However, we allow the use of negative weights, and we prove that they are sometimes necessary to achieve fairness. Furthermore, we use a different update rule for the weights.
AdaFair [23]. This paper proposes a boosting based framework to learn fair models. The underlying idea is to modify the weights of the examples depending on both the performances of the current strong classifier and the group memberships. Hence, examples that belong to the disadvantaged group and are incorrectly classified receive higher weights than the examples that belong to the advantaged group and are correctly classified. In this paper, we propose to use a similar update rule from a fairness point of view but we do not modify the weights of the examples given the performance of the current model. Furthermore, rather than a boosting based approach, we consider problems that can be solved using gradient descent. Finally, while AdaFair only focuses on Equalized Odds, we show that our approach works with several fairness notions.
Identifying and Correcting Label Bias in Machine Learning [24]. This paper considers the fairness problem from an original point of view as it assumes that the observed labels are biased compared to the true labels. The goal is then to learn a model with respect to the true labels using only the observed labels. To this end, the paper proposes to use an iterative reweighting procedure where positive weights for the examples and updated models are alternatively learned. In this paper, we also propose a reweighting approach. However, we use different weights that are not necessarily positive. Furthermore, our approach is not limited to binary labels and can handle multiclass problems.

FairGrad
In this section, we present FairGrad, the main contribution of this paper. To this end, we first formally introduce the fairness notions that we may consider, then we present FairGrad for exact fairness before discussing an extension able to handle -fairness.

Fairness Definitions
We assume that the data may be partitioned into K disjoint groups denoted T 1 , . . . , T k , . . . , T K such that K k=1 T k = T and K k=1 T k = ∅. These groups highly depend on the fairness notion under consideration. They might correspond to the usual sensitive groups, as in Accuracy Parity (see Example 3), or might be subgroups of the usual sensitive groups, as in Equalized Odds (see Example 1). For each group, we further assume that we have access to a function F k : D Z ×H → R such that F k > 0 when the group k is advantaged and F k < 0 when the group k is disadvantaged. Furthermore, we assume that the magnitude of F k represents the degree to which the group is (dis)advantaged. Finally, we assume that each F k can be rewritten as follows: where the terms C · k are group specific constants independent of h θ and the probabilities P (h θ (x) = y|T k ) represent the error rates of h θ (x) over each group T k with a slight abuse of notation. In the next few examples, we present several standard group fairness notions that respect this definition.
Example 1 (Equalized Odds (EOdds) [20]). A model h θ is fair for Equalized Odds when the probability of predicting the correct label is independent of the sensitive attribute, that is, ∀l ∈ Y, ∀r ∈ S It means that we need to partition the space into K = |Y × S| groups and, ∀l ∈ Y, ∀r ∈ S, we define F (l,r) as where the law of total probability was used to obtain the last equation. Thus, Equalized Odds satisfies all our assumptions with C (l,r) (l,r) = P (s = r|y = l)−1, C (l,r ) (l,r) = P (s = r |y = l) and C (l ,r ) (l,r) = 0 with r = r and l = l.
Example 2 (Equality of Opportunity (EOpp) [20]). A model h θ is fair for Equality of Opportunity when the probability of predicting the correct label is independent of the sensitive attribute for a given subset Y ⊂ Y of labels called the desirable outcomes, that is, ∀l ∈ Y , ∀r ∈ S P (h θ (x) = l | s = r, y = l) = P (h θ (x) = l | y = l) .
It means that we need to partition the space into K = |Y × S| groups and, ∀l ∈ Y, ∀r ∈ S, we define F (l,r) as which can then be rewritten in the correct form in the same way as Equalized Odds, the only difference being that C · (l,r) = 0, ∀(l, r) ∈ Y × S \ Y × S.

Example 3 (Accuracy Parity (AP) [41]).
A model h θ is fair for Accuracy Parity when the probability of being correct is independent of the sensitive attribute, that is, ∀r ∈ S It means that we need to partition the space into K = |S| groups and, ∀r ∈ S, we define F (r) as where the law of total probability was used to obtain the last equation. Thus Accuracy Parity satisfies all our assumptions with C (r)

FairGrad for Exact Fairness
To introduce our method, we first start with the following optimization problem that is standard in fair machine learning [8] arg min Then, using Lagrange multipliers we obtain the following unconstrained problem arg min where λ 1 , . . . , λ K are the Lagrange multipliers. One of the main assumption of this paper is then that there exists a set of multipliers λ * 1 , . . . , λ * K such that where h * θ is the most accurate and fair model. This directly implies that It means that we can use an alternating approach where the hypothesis and the multipliers are updated one after the other.
Updating the Multipliers. To update λ 1 , . . . , λ K , we will use a standard gradient ascent procedure. Hence, given that the gradient of Problem (3) is we have the following update rule ∀k ∈ [1, K]: where η λ is a learning rate that controls the importance of each weight update. In the experiments, we chose to use a constant learning rate of 0.01 and we believe that a good rule of thumb is to only use large values of η λ when the fairness levels may be accurately estimated.
Updating the Model. To update the parameters θ ∈ R D of the model h θ , we use a standard gradient descent approach. However, first, we notice that given the fairness notions that we consider, Problem (3) is equivalent to for b in batches do 4: Compute the predictions of the current model on the current batch b. 5: Compute the group-wise losses using the predictions. 6: Compute the current fairness level using the predictions and update the group-wise weights.

7:
Compute the overall weighted loss using the group-wise weights.

8:
Compute the gradients based on the loss and update the model. 9: end for 10: end for 11: return trained model h * θ Hence, at iteration t, the update rule becomes where η θ is the usual learning rate that controls the importance of each parameter update. Here, we obtain our group specific weights ∀ k , w k = P (T k ) + K k =1 C k k λ k , that depend on the current fairness level of the model through λ 1 , . . . , λ K , the relative size of each group through P (T k ), and the fairness notion under consideration through the constants C · · . The exact values of these constants were given in Section 3.1 for various fairness notions. Overall, they are such that, at each iteration, the weights of the advantaged groups are reduced and the weights of the disadvantaged groups are increased.
The main limitation of the above update rule is that one needs to compute group-wise gradients as ∇ θ P (h θ (x) = y|T k ) = 1 n k (x,y)∈T k ∇ θ I {h θ (x) =y} where I {h θ (x) =y} is the indicator function, also called the 0−1-loss, that is 1 when h θ (x) = y and 0 otherwise. Unfortunately, this usually does not provide meaningful optimization directions. To address this issue, we follow the usual trend in machine learning and replace the 0−1-loss with one of its continuous and differentiable counterparts that provides more meaningful gradients. For example, in all our experiments, we use the cross entropy loss.
Computational Overhead of FairGrad. We summarize our approach in Algorithm 1. We consider batch gradient descent rather than full gradient descent as it is a popular optimization scheme. We empirically investigate the impact of the batch size in Section 4.7. We use italic font to highlight the steps inherent to FairGrad that do not appear in classic batch gradient descent. The main difference is Step 6, that is the computation of the fairness levels for each group. However, these can be cheaply obtained from the predictions of h (t) θ on the current batch which are always available since they are also needed to compute the gradient. Hence, the computational overhead of FairGrad is very limited.
Importance of Negative Weights. A key property of FairGrad is that we allow the use of negative weights, that is P (T k ) + K k =1 C k k λ k may be negative, while existing methods often restrict themselves to positive weights [38,23,24]. Furthermore, we show that these negative weights are sometimes necessary. Hence, in the next lemma, we provide sufficient conditions so that negative weights are mandatory to learn a fair model with respect to Accuracy Parity.
Lemma 1 (Negative weights are necessary.). Assume that the fairness notion under consideration is Accuracy Parity (see Example 3). Let h * θ be the most accurate and fair model. Then using negative weights is necessary as long as Proof. The proof is provided in the supplementary material.
The previous condition can sometimes be verified in practice. As a motivating example, assume a binary setting with two groups T 1 and T −1 . Let h −1 θ be the model minimizing P (h θ (x) = y|T −1 ) and assume that P (h θ (x) = y) < P (h θ (x) = y|T −1 ), that is group T −1 is disadvantaged for accuracy parity. Given h * θ the most accurate and fair model, we have as otherwise we would have a contradiction since the fair model would also be the most accurate model for group T −1 . Indeed, P (h * θ (x) = y) = P (h * θ (x) = y|T −1 ) by definition of Accuracy Parity. In other words, a dataset were the most accurate model for a given group still disadvantages this group requires negative weights.

FairGrad for -fairness
In the previous section, we mainly considered exact fairness and we showed that this could be achieved by using a reweighting approach. In fact, we can extend this procedure to the case offairness where the fairness constraints are relaxed and a controlled amount of violations is allowed. Usually, is a user defined parameter but it can also be set by the law, as it is the case with the 80% rule in the US. The main difference with the exact fairness case is that each equality constraint in Problem (2) is replaced with two inequalities of the form The main consequence is that we need to maintain twice as many Lagrange multipliers and that the group-wise weights are slightly different. Since the two procedures are similar, we omit the details here but provide them in the supplementary material for the sake of completeness.

Experiments
In this section, we present several experiments that demonstrate the competitiveness of FairGrad as a procedure to learn fair models in a classification setting. We begin by presenting results over standard fairness datasets and a Natural language Processing (NLP) dataset in Section 4.4. We then showcase the fine-tuning ability of FairGrad on a Computer Vision (CV) dataset in Section 4.6. Next, we study the behaviour of the -fairness variant of FairGrad in Section 4.5. Finally, we investigate the impact of batch size on the learned model in Section 4.7.

Datasets
In the main paper, we consider 4 different datasets and postpone the results on another 5 datasets to the supplementary material as they follow similar trends. We also postpone the detailed descriptions of these datasets as well as the pre-processing steps.
On the one hand, we consider commonly used fairness datasets, namely the Adult Income dataset [28] and the CelebA dataset [32]. Both datasets are binary classification datasets with binary sensitive attributes (gender). We also consider a variant of the Adult Income dataset where we add a second binary sensitive attribute (race) to obtain a dataset with 4 sensitive groups.
On the other hand, to showcase the wide applicability of FairGrad, we employ datasets from the NLP and CV communities. For NLP, we consider the Twitter Sentiment 1 [2] dataset which consists of 200k tweets with binary sensitive attribute (race) and binary sentiment score. For CV, we employ the UTKFace dataset 2 [44], which consists of 23, 708 images tagged with race, age, and gender.

Performance Measures
For fairness, we consider the three measures introduced in Section 3.1, namely Equalized Odds (EOdds), Equality of Opportunity (EOpp), and Accuracy Parity (AP). For each specific fairness notion, we report the average absolute fairness level of the different groups over the test set, that is 1 K K k=1 |F k (T , h θ )| (lower is better). To assess the utility of the learned models, we use their accuracy levels over the test set, that is 1 n n i=1 I h θ (xi)=yi (higher is better). All the results reported are averaged over 5 independent runs and standard deviations are provided. Note that, in the main paper, we graphically report a subset of the results over the aforementioned datasets. We provide detailed results in the supplementary material, including the missing pictures as well as complete tables with accuracy levels, fairness levels, and fairness level of the most well-off and worst-off groups for all the relevant methods.

Methods
We compare FairGrad to 5 different baselines, namely (i) Unconstrained, which is oblivious to any fairness measure and trained using a standard batch gradient descent method, (ii) an Adversarial mechanism [18] using a gradient reversal layer [16], similar to GRAD-Pred [36], where an adversary, with an objective to predict the sensitive attribute, is added to the unconstrained model, (iii) BiFair [35], (iv) FairBatch [38], and (v) Constraints [8], a non-convex constrained optimization method.
In all the experiments, we consider two different hypothesis classes. On the one hand, we use linear models implemented in the form of neural networks with no hidden layers. On the other hand, we use a more complex, non-linear architecture with three hidden layers of respective sizes 128, 64, and 32. Furthermore, the ReLU as our activation function with batch norm normalization and dropout set to 0.2. In both cases, we optimize the cross-entropy loss. We provide the exact setup and hyper-parameter tuning details for all the methods in the supplementary.
In several experiments, we only consider subsets of the baselines due to the limitations of the methods. Hence, BiFair was designed to handle binary labels and binary sensitive attributes and thus is not considered for the datasets with more than two sensitive groups or more than two labels. Furthermore, we implemented it using the authors code that is freely available online but does not include Accuracy Parity as a fairness measure, thus we do not report results related to this measure for BiFair. Similarly, we also implemented FairBatch from the authors code which does not support Accuracy Parity as a fairness measure, thus we also exclude it from the comparison for this measure. For Constraints, we based our implementation on the publicly available authors library but were only able to reliably handle linear models and thus we do not consider this baseline for non-linear models. Finally, for Adversarial, we used our custom made implementation. However, it is only applicable when learning non-linear models since it requires at least one hidden layer to propagate its reversed gradient.

Results for Exact Fairness
We report the results over the Adult Income dataset using a linear model, the Adult Income dataset with multiple groups with a nonlinear model, and the Twitter sentiment dataset using both linear and nonlinear models in Figures 1, 2, and 3 respectively. In these figures, the best methods are closer to the bottom right corner. If a method is closer to the bottom left corner, it has good fairness but reduced accuracy. Similarly, a method closer to the top right corner has good accuracy but poor fairness, that is it is close to the unconstrained model.
The main take-away from these experiments is that there is no fairness enforcing method that is consistently better than the others and all of them have strengths, that is datasets and fairness measures were they obtain good results, and weaknesses, that is datasets and fairness measures for which they are sub-optimal. For instance, over the Twitter Sentiment dataset with a nonlinear model and EOpp, FairGrad outperforms all the other approaches in terms of accuracy and fairness. However, on the same dataset, it pays a price in terms of accuracy for marginal fairness gains when considering the other two fairness measures. Similarly, FairBatch induces accurate models in Adult with multiple groups but is sub-optimal in terms of fairness. Finally, BiFair is sub-optimal on Adult with EOpp, while being comparable to the other approaches on the Twitter Sentiment dataset. We observed similar trends on other datasets, available in the supplementary, with different methods coming out on top for different datasets and fairness measures.

Accuracy Fairness Trade-off
In this second experiment, we demonstrate the capability of FairGrad to support approximate fairness (see Section 3.3). In Figure 4, we show the performances, as accuracy-fairness pairs, of several models learned on the CelebA dataset by varying the fairness level parameter . These results suggest that FairGrad respects the constraints well. Indeed, the average absolute fairness level (across all the constraints, see Section 4.2 for the exact measure) achieved by FairGrad is   either the same or less than the given threshold. It is worth mentioning that FairGrad is designed to enforce -fairness for each constraint individually which is slightly different from the summarized quantity displayed here. Finally, as the fairness constraint is relaxed, the accuracy of the learned model increases, reaching the same performances as the Unconstrained classifier when the fairness level of the latter is below .

FairGrad as a Fine-Tuning Procedure
While FairGrad has primarily been designed to learn fair classifiers from scratch, it can also be used to fine-tune an existing classifier to achieve better levels of fairnes. In this experiment, we showcase this possibility on a computer vision dataset. More specifically, we fine-tune the ResNet18 [21] model, developed for image recognition, over the UTKFace [44] dataset, consisting of human face images tagged with Gender, Age, and Race information. Following the same process as [38], we use Race as the sensitive attribute and consider two scenarios where either the gender (binary) or age (multi-valued) are used as the target label. The results are displayed in Table 1. In both settings, FairGrad is able to learn models that are more fair than an Unconstrained fine-tuning procedure, albeit at the expense of a decrease in terms of accuracy when the target label is the gender.

Impact of the Batch-size
In this last set of experiment, we evaluate the impact of batch size on the fairness and accuracy level of the learned model. Indeed, at each iteration, in order to minimize the overhead associated with FairGrad (see Section 3.2), we update the weights using the fairness level of the model estimated solely on the current batch. When these batches are small, these estimates are unreliable and might lead the model astray. This can be observed in Table 2 where we present the performances of several linear models learned with different batch sizes on the CelebA dataset. On the one hand, for very small batch sizes, the learned models tends to have lower accuracy and slightly worse fairness levels with high standard deviations. On the other hand, with sufficiently large batch size, in this case 64 and above, the learned models are close to be perfectly fair. Furthermore, they obtain reasonable levels of accuracy since the Unconstrained model has an accuracy of 0.8529 for this problem.

Conclusion
In this paper, we proposed FairGrad, a fairness aware gradient descent approach based on a reweighting scheme. We showed that it can be used to learn fair models for various group fairness definitions and is able to handle multiclass problems as well as settings where there is multiple sensitive groups. We empirically showed the competitiveness of our approach against several baselines on standard fairness datasets and on a Natural Language Processing task. We also showed that it can be used to fine-tune an existing model on a Computer Vision task. Finally, since it is based on gradient descent and has a small overhead, we believe that FairGrad could be used for a wide range of applications, even beyond classification.
Limitations and Societal Impact. While appealing, FairGrad also has limitations. It inherently assumes that a set of weights that would lead to a fair model exists but this might be difficult to verify in practice. Thus, even if in our experiments FairGrad seems to behave quite well, a practitioner using this approach should not trust it blindly. It remains important to always check the actual fairness level of the learned model. On the other hand, we believe that, due to its simplicity and its versatility, FairGrad could be easily deployed in various practical contexts and, thus, could contribute to the dissemination of fair models.

APPENDIX
In this supplementary we provide several details that were omitted in the main paper. First, in Section 6, we prove Lemma 1. Then, in Section 7, we derive the update rules for FairGrad with -fairness. Finally, in Section 8, we provide additional experiments.
6 Proof of Lemma 1 Lemma 2 (Negative weights are necessary.). Assume that the fairness notion under consideration is Accuracy Parity. Let h * θ be the most accurate and fair model. Then using negative weights is necessary as long as Proof. To prove this Lemma, one first need to notice that, for Accuracy Parity, since This implies that, whatever our choice of λ, the weights will always sum to one. In other words, for a given hypothesis h θ , we have that where, given w 1 , . . . , w K , the original values of lambda can be obtained by solving the linear system which is guaranteed to have infinitely many solutions since the rank of the matrix C is K − 1 and the rank of the augmented matrix (C|w) is also K −1. Here we are using the fact that P (T k ) = 0, ∀k since all the groups have to be represented to be taken into account.
We will now assume that all the weights are positive, that is w k > 0, ∀k. Then, the best strategy to solve Problem (6) is to put all the weight on the worst off group k, that is set w k = 1 and w k = 0, ∀k = k. It implies that Furthermore, notice that, for fair models with respect to Accuracy Parity, we have that P (h θ (x) = y|T k ) = P (h θ (x) = y) , ∀k. Thus, if it holds that where h * θ is the most accurate and fair model, then the optimal solution of Problem (3) in the main paper will be unfair. It implies that, in this case, using positive weights is not sufficient and negative weights are necessary.

FairGrad for -fairness
To derive FairGrad for -fairness we first consider the following standard optimization problem arg min We, once again, use a standard multipliers approach to obtain the following formulation arg min where λ 1 , . . . , λ K and δ 1 , . . . , δ K are the multipliers that belong to R + , that is the set of positive reals. We now assume that there exists multipliers such that where h * θ is the most accurate and fair model. As for exact fairness, this directly implies that the min-max solution is equal to the max-min solution and thus that we can use an alternating approach where the hypothesis and the multipliers are updated one after the other.
Updating the Multipliers. To update the values λ 1 , . . . , λ K , we will use a standard gradient ascent procedure. Hence, noting that the gradient of the previous formulation is we have the following update rule ∀k ∈ [1, K] where η is a learning rate that controls the importance of each weight update.
Updating the Model. To update the parameters θ ∈ R D of the model h θ , we proceed as before, using a gradient descent approach. However, first, we notice that given the fairness notions that we consider, solving Problem (8) is equivalent to solving arg min Since the additional terms in the optimization problem do not depend on h θ , the main difference between exact and -fairness is the nature of the weights. More precisely, at iteration t, the update rule becomes where η θ is a learning rate. Once again, we obtain a simple reweighting scheme where the weights depend on the current fairness level of the model through λ 1 , . . . , λ K and δ 1 , . . . , δ K , the relative size of each group through P (T k ), and the fairness notion under consideration through the constants C · · .

Extended Experiments
In this section, we provide additional details related to the baselines and the hyper-parameters tuning procedure. We then provide descriptions of the datasets and finally the results.

Baselines
-Adversarial: One of the common ways of removing sensitive information from the model's representation is via adversarial learning. Broadly, it consists of three components, namely an encoder, a task classifier, and an adversary. One the on hand, the objective of the adversary is to predict sensitive information from the encoder. On the other hand, the encoder aims to create representations that are useful for the downstream task (task classifier) and, at the same time, fool the adversary. The adversary is generally connected to the encoder via a gradient reversal layer [16] which acts like an identity function during the forward pass and scales the loss with a parameter −λ during the backward pass. In our setting, the encoder is a Multi-Layer Perceptron with two hidden layers of size 64 and 128 respectively, and the task classifier is another Multi-Layer Perceptron with a single hidden layer of size 32. The adversary is the same as the main task classifier. We use a ReLU as the activation function with the dropout set to 0.2 and employ batch normalization with default PyTorch parameters. As a part of the hyper-parameter tuning, we did a grid search over λ, varying it between 0.1 to 3.0 with an interval of 0.2. In our initial experiments, we varied the batch size and learning rates for both Constraints and FairBatch. However, we found that the default hyper-parameters as specified by the authors result in the best performances. In the spirit of being comparable in terms of hyper-parameter search budget, we also fix all hyper-parameters of FairGrad, apart from the batch size. We experiment with two different batch sizes namely, 64 or 512 for the standard fairness dataset. However, for UTKFace with fix it to 32, due to limited GPU memory. For all our experiments, apart from BiFair, we use Batch Gradient Descent as the optimizer with a learning rate of 0.1 and a gradient clipping of 0.05 to avoid exploding gradients. For BiFair, we employ the Adam optimizer as suggested by the authors with a learning rate of 0.001.
In all our experiments, we choose the model with the lowest fairness scores between certain accuracy intervals. More specifically, let α * be the highest validation accuracy achieved by the given method over all the hyper-parameters search space, and let β be the relaxation threshold. Instead of choosing the model with the best validation accuracy, we choose a model with lowest validation fairness score amongst all models with the validation accuracy in the interval [α * −β, α * ]. We fix β to 0.03 for all our experiments.

Datasets
Here, we provide additional details on the datasets used in our experiments. We begin by describing the standard fairness datasets for which we follow the pre-processing procedure as described in [33]. The goal is to predict if the defendant will be arrested again within two years of the decision. The sensitive attribute is race, which has been merged into "White" and "Non White" categories. -Communities and Crime 7 : The dataset [37] is composed of 1994 instances with 128 features, of which 29 have been dropped. The objective is to predict the number of violent crimes in the community, with race being the sensitive attribute. -German Credit 8 : The dataset [11] consists of 1000 instances, with each having 20 attributes.
The objective is to predict a person's creditworthiness (binary), with gender being the sensitive attribute. -Gaussian 9 : It is a toy dataset with binary task label and binary sensitive attribute, introduced in [33]. It is constructed by drawing points from different Gaussian distributions. We follow the same mechanism as described in [33], and sample 50000 data points for each class.
For all the dataset, we use a 20% of the data as a test set and 80% as a train set. We further divide the train set into two and keep 25% of the training examples as a validation set. For each repetition, we randomly shuffle the data before splitting it, and thus we had unique splits for each random seed. As a last pre-processing step, we centered and scaled each feature independently by substracting the mean and dividing by the standard deviation both of which were estimated on the training set.
Twitter Sentiment Analysis 10 : The dataset [2] consists of 200k tweets with binary sensitive attribute (race) and binary sentiment score. We follow the setup proposed by [19] and [13] and create bias in the dataset by changing the proportion of each subgroup (race-sentiment) in the training set. With two sentiment classes being happy and sad, and two race classes being AAE and SAE, the training data consists of 40% AAE-happy, 10% AAE-sad, 10% SAE-happy, and 40% SAE-sad. The test set remains balanced. The tweets are encoded using the DeepMoji [14] encoder with no fine-tuning, which has been pre-trained over millions of tweets to predict their emoji, thereby predicting the sentiment. Note that the train-test splits are pre-defined and thus do not change based on the random seed of the repetition.                Table 9: Results for the Adult with multiple groups dataset with Linear Models. All the results are averaged over 5 runs. Here MEAN ABS., MAXIMUM, and MINIMUM represent the mean absolute fairness value, the fairness level of the most well-off group, and the fairness level of the worst-off group, respectively.                      Table 19: Results for the Twitter Sentiment dataset with Non Linear Models. All the results are averaged over 5 runs. Here MEAN ABS., MAXIMUM, and MINIMUM represent the mean absolute fairness value, the fairness level of the most well-off group, and the fairness level of the worst-off group, respectively.