FairALM: Augmented Lagrangian Method for Training Fair Models with
Little Regret

Recall that a fairness constraint corresponds to a performance requirement of a classifier $h$ on subgroups of features $x$ induced by a protected attribute $s$. For instance, say that $h$ predicts the credit-worthiness $y$ of an individual $x$. Then, we may require that $e_{h}$ be “approximately” the same across individuals for different races given by $s$. Does it follow that functions/metrics that are used to evaluate fairness may be written in terms of the error of a classifier $e_{h}$ conditioned on the protected variable $s$ (or in other words $e_{h}^{s}$)? Indeed, it does turn out to be the case! In fact, many widely used functions in practice can be viewed as imposing constraints on the confusion matrix as our intuition suggests. We will now discuss few common fairness metrics to illustrate this idea.

(a) Demographic Parity (DP) [37]. A classifier $h$ is said to satisfy Demographic Parity (DP) if $h(x)$ is independent of the protected attribute $s$. Equivalently, $h$ satisfies DP if $d_{h}=0$ where we set $\mu_{h}^{s_{i}}=e_{h}^{s_{i}}$ (using notations introduced above). DP can be seen as equating the total false positives and false negatives between the confusion matrices of the two groups. We denote DDP by the difference of the demographic parity between the two groups.

(b) Equality of Opportunity (EO) [23]. A classifier $h$ is said to satisfy EO if $h(x)$ is independent of the protected attribute $s$ for $y\in\{0,1\}$. Equivalently, $h$ satisfies EO if $d_{h}^{y}=0$ where we set $\mu_{h}^{s_{i}}=e_{h}^{s_{i}}|(y\in\{0,1\})=:e_{h}^{s_{i},y_{j}}$ conditioning on both $s$ and $y$. Depending on the choice of $y$ in $\mu_{h}^{s_{i}}$, we get two different metrics: (i) $y=0$corresponds to $h$ with equal False Positive Rate (FPR) across $s_{i}$ [14], whereas (ii) $y=1$corresponds to $h$ with equal False Negative Rate (FNR) across $s_{i}$ [14]. Moreover, $h$ satisfies Equality of Odds if $d_{h}^{0}+d_{h}^{1}=0$, i.e., $h$ equalizes both TPR and FPR across $s$ [23]. We denote the difference in EO by DEO.

(c) Predictive Parity (PP) [11]. A classifier $h$ satisfies PP if the likelihood of making a misclassification among the positive predictions of the classifier is independent of the protected variable $s$. Equivalently, $h$ satisfies PP if $d_{h}^{\hat{y}}=0$ where we set $\mu_{h_{i}}^{s_{i}}=e_{h}^{s_{i}}|(\hat{y}=1)$. It corresponds to matching the False Discovery Rate between the confusion matrices of the two groups.

The starting point of our development is based on the following simple result that follows directly from the definitions of fairness metrics in Section 2:

Observation 1 immediately implies that $\mathcal{F}_{d_{h}}$ can be represented using linear (fractional) equations in $h$. To simplify the discussion, we will focus on the case when $\mathcal{F}_{d_{h}}$ is given by the DP metric. Hence, we can reformulate (1) as,

where $q$ represents a distribution over $\mathcal{H}$.

In general, there are two ways of treating the $N$ constraints $q_{i}d_{h_{i}}=0$ in Problem (2) viz., (i) as hard constraints; or (ii) as soft constraints. Algorithms that can handle explicit constraints efficiently require access to an efficient oracle that can minimize a linear or quadratic function over the feasible set in each iteration. Consequently, algorithms that incorporate hard constraints come with high per-iteration computational cost since the number of constraints is (at least) linear in $N$, and is not applicable in large scale settings. Hence, we propose to use algorithms that incorporate fairness as soft constraints. With these two minor modifications, we will now describe our approach to solve problem (2).

As the game with respect to $\lambda$ is a maximization problem, we get a reverse regret bound as shown in the following Lemma. Due to space, proofs appear in the Appendix.

The above lemma indicates that the cumulative reward grows in time as $\mathcal{O}(\log T)$. The proximal term in the augmented Lagrangian gives us a better bound than an $\ell_{2}$ or an entropic regularizer (which provides a $\sqrt{T}$ bound [34]).

Next, we evaluate the cost function $L_{T}(q,\lambda)$ after $T$ rounds of the game. We observe that the average play of both the players converges to a saddle point with respect to $L_{T}(q,\lambda)$. We formalize this in the following theorem,

The above theorem indicates that the average play of the $q$-player and the $\lambda$-player reaches a $\nu$-approximate saddle point. Our bounds for $\nu=\frac{1}{T}$ and $\lambda\in\mathbb{R}$ are strictly better than [1].

The key difficulty from the analysis standpoint we face in extending these results to the deep networks setting is that the number of classifiers $|\mathcal{H}|$ may be exponential in number of nodes/layers. This creates a potential problem in computing Step 5 of Algorithm 1 – if viewed mechanistically, is not practical since an epsilon net over the family $\mathcal{H}$ (representable by a neural network) is exponential in size. Interestingly, notice that we often use over-parameterized networks for learning. This is a useful fact here because it means that there exists a solution where $\mathrm{argmin}_{i}(e_{h_{i}}+\lambda_{t}d_{h_{i}})$ is $0$. While iterating through all $h_{i}$s will be intractable, we may still able to obtain a solution via standard stochastic gradient descent (SGD) procedures [42]. The only unresolved question then is if we can do posterior inference and obtain classifiers that are “fair”. It turns out that the above procedure provides us an approximation if we leverage two facts: first, SGD can find the minimum of $L(h,\lambda)$ with respect to $h$ and second, recent results show that SGD, in fact, performs variational inference, implying that the optimization provides an approximate posterior [12]. Having discussed the issue of the exponential sized $|\mathcal{H}|$ – for which we settle for an approximate posterior – we make three additional adjustments to the algorithm to make it suitable for training deep networks. First, the non-differentiable indicator function $\mathbbm{1}[\cdot]$ is replaced with a smooth surrogate function (such as a logistic function). Second, as it is hard to evaluate $e_{h}/\mu_{h}^{s}$ due to unavailability of the true data distribution, we instead calculate their empirical estimates $z=(x;y;s)$, and denote it by $\hat{e}_{h}(z)/\hat{\mu}_{h}^{s}(z)$. Third, by exchanging the “$\max$” and “$\min$” in (3), we obtain an objective that upper-bounds our current objective in (3). This provides us with a closed-form solution to $\lambda$ thus reducing the minmax objective to a single simpler minimization problem. We present the algorithm for deep neural network training in Alg. 2 and call it FairALM: DeepNet Classifier.

Data and Setup. CelebA [28] consists of $200$K celebrity face images from the internet annotated by a group of paid adult participants [7]. There are up to $40$ labels available in the dataset, each of which is binary-valued.

Quantitative results. We begin our analysis by predicting each of the $40$ labels with a $3$-layer ReLU network. The protected variable, $s$, are the binary attributes like Male and Young representing gender and age respectively. We train the SGD algorithm for $5$-epochs and select the labels predicted with at least at $70\%$ precision and with a DEO of at least $4\%$ across the protected variables. The biased set of labels thus estimated are shown in Table 1. These labels are consistent with other reported results [32]. It is important to bear in mind that the bias in the labels should not be attributed to its relatedness to a specific protected attributed alone. The cause of bias could also be due to the skew in the label distributions. When training a $3$-layer ReLU net with FairALM, the precision of the model remained almost the same ($\pm 5\%$ ) while the DEO measure reduced significantly as indicated in the Table 1. Next, choosing the most unfair label in Table 1 (i.e., attractive), we train a ResNet18 for a longer duration of about $100$ epochs and contrast the performance with a simple $\ell_{2}$-penalty baseline. The training profile is observed to be more stable for FairALM as indicated in Fig. 2. This finding is consistent with the seminal works such as [5, 29] that discuss the ill-conditioned landscape of non-convex penalties. Comparisons to more recent works such as [33, 31] is provided in Table 2. Here, we present a new state-of-the-art result for the DEO measure with the label attractive and protected attribute gender.

Qualitatively assessing Interpretability. While the DEO measure obtained by FairALM is lower, we can ask an interesting question: when we impose the fairness constraint, precisely which aspects of the image are no longer “legal” for the neural network to utilize? This issue can be approached via visualizing activation maps from models such as CAM [45]. As a representative example, our analysis suggests that in general, an unconstrained model uses the entire face image (including the gender-revealing parts). We find some consistency between the activation maps for attractiveness and activation maps of an unconstrained model trained to predict gender! In contrast, when we impose the fairness constraint, the corresponding activation maps turn out to be clustered around specific regions of the face which are not gender revealing. In particular, a surprising finding was that the left regions in the face were far more prominent which turns out to be consistent with studies in psychology [6].

Summary. FairALM minimized the DEO measure without compromising the test error. It has a more stable training profile than an $\ell_{2}$ penalty and is competitive with recent fairness methods in vision. The activation maps in FairALM concentrate on non-gender revealing features of the face when controlled for gender.

Data and Setup. ImSitu [38] is a situation recognition dataset consisting of $\sim 100$K color images taken from the web. The annotations for the image is provided as a summary of the activity in the image and includes a verb describing it, the interacting agents and their roles. The protected variable in this experiment is gender. Our objective is to classify a pair of verbs associated with an image. The pair is chosen such that if one of the verbs is biased towards males then the other would be biased towards females. The authors in [44] report the list of labels in the ImSitu dataset that are gender biased: we choose our verb pairs from this list. In particular, we consider the verbs Cooking vs Driving, Shaving vs Moisturizing, Washing vs Saluting and Assembling vs Hanging. We compare our results against multiple baselines such as (1) Unconstrained (2) $\ell_{2}$-penalty, the penalty applied on the DEO measure (3) Re-weighting, a weighted loss functions where the weights account for the dataset skew (4) Adversarial[41] (5) Lagrangian[44] (6) Proxy-Lagrangian[15]. The supplement includes more details of the baseline methods.

Quantitative results. From Fig. 5, it can be seen that FairALM reaches a zero DEO measure very early in training and attains better test errors than an unconstrained model. Within the family of Lagrangian methods such as [44, 15], FairALM performs better on verb pair ‘Shaving vs Moisturizing’ in both test error and DEO measure as indicated in Table 3 . While the results on the other verb pairs are comparable, FairALM was observed to be more stable to different hyper-parameter choices. This finding is in accord with recent studies by [2] who prove that proximal function models are robust to step-size selection. Detailed analysis is provided in the supplement. Turning now to an adversarial method such as [44], results in Table 3 show that the DEO measure is not controlled as competently as FairALM. Moreover, complicated training routines and unreliable convergence [3] makes model-training harder.

Interpretable Models. We used CAM [45] to inspect the image regions used by the model for target prediction. We observe that the unconstrained model ends up picking features from locations that may not be relevant for the task description but merely co-occur with the verbs in this particular dataset (and are gender-biased). Fig. 4 highlights this observation for the selected classification tasks. Overall, we observe that the semantic regions used by the constrained model are more aligned with the action verb present in the image, and this adds to the qualitative advantages of the model trained using FairALM in terms of interpretability.

Limitations. We also note that there are cases where both the unconstrained model and FairALM look at incorrect image regions for prediction, owing to the small dataset sizes. However, the number of such cases are far fewer for FairALM than the unconstrained setup.

Summary. FairALM successfully minimizes the fairness measure while classifying verb/action pairs associated with an image. FairALM uses regions in an image that are more relevant to the target class and less gender revealing.

Data and Setup. The datasets we examine here are publicly available from the U.S. National Library of Medicine [25]. The images come from two sites/sources. Images for the first site are collected from patients in Montgomery county, USA and includes $138$ x-rays. The second set of images includes $662$ images collected at a hospital in Shenzhen, China. Our task is to predict pulmonary tuberculosis (TB) from the x-ray images. The images are collected from different x-ray machines with different characteristics, and have site-specific markings or artifacts, see Fig 6. $25\%$ of the samples from the pooked dataset are set aside for testing.

Quantitative Results. We treat the site information, Montgomery or Shenzhen, as a nuisance/protected variable and seek to decorrelate it from the TB labels. We train a ResNet18 network and compare an unconstrained model with FairALM model. Our datasets of choice are small in size, and so deep models easily overfit to site-specific biases present in the training data. Our results corroborate this conjecture, the training accuracies reach $100\%$ very early and the test set accuracies for the unconstrained model has a large variance over multiple experimental runs. Conversely, as depicted in Fig. 7, a FairALM model not only maintains a lower variance in the test set errors and DEO measure but also attains improved performance on these measures. What stands out in this experiment is that the number of epochs to reach a certain test set error is lower for FairALM indicating that the model generalizes faster compared to an unconstrained model.

Summary. FairALM is effective at learning from datasets from two different sites/sources, minimizes site-specific biases and accelerates generalization.

Data. We consider four standard datasets, Adult, COMPAS, German and Law Schools [17, 1]. The Adult dataset is comprised of demographic characteristics where the task is to predict if a person has an income higher (or lower) than $\$50$K per year. The protected attribute here is gender. In COMPAS dataset, the task is to predict the recidivism of individuals based on features such as age, gender, race, prior offenses and charge degree. The protected attribute here is race, specifically, whether the individual is white or black. The German dataset classifies people as good or bad credit risks with the person being a foreigner or not as the protected attribute. The features available in this dataset are credit history, saving accounts, bonds, etc. Finally, the Law Schools dataset, which comprises of $\sim 20$K examples, seeks to predict a person’s passage of the bar exam. Here, a binary attribute race is considered as the protected attribute.

Setup. We use Alg. $1$ in the paper for experiments in this section. Recall from $\S~{}3$ of the paper that Alg. $1$ requires the specification of $\mathcal{H}$. We use the space of logistic regression classifiers as $\mathcal{H}$. At the start of the algorithm we have an empty set of classifiers. In each iteration, we add a newly trained classifier $h\in\mathcal{H}$ to the set of classifiers only if $h$ has a smaller Lagrangian objective value among all the classifiers already in the set.

Quantitative Results. For the Adult dataset, FairALM attains a smaller test error and smaller DEO compared to the baselines considered in Table 4. We see big improvements on the DEO measure in COMPAS dataset and test error in German dataset using FairALM. While the performance of FairALM on Law Schools is comparable to other methods, it obtains a better false-positive rate than [1] which is a better metric as this dataset is skewed towards it’s target class.

Summary. We train Alg. $1$ on standard datasets specified in [17, 1]. We observe that FairALM is competitive with the popular methods in the fairness literature.

Prior to proving the convergence of primal and dual variables of our algorithm with respect to the augmented lagrangian $L_{T}(q,\lambda)$, we prove a regret bound on the function $f_{t}(\lambda)$ which is defined in the following lemma. As $f_{t}(\lambda)$ is a strongly concave function (which we shall see shortly), we obtain a bound on the negative regret.

Next, using the Cumulative Reward Bound (10), we prove the theorem stated in the paper. The theorem gives us the number of iterations required by Alg. $1$ (in the paper) to reach a $\nu-$approximate saddle point. Our bounds for $\eta=\frac{1}{T}$ and $\lambda\in\mathbb{R}$ are strictly better than [1]. We re-state the theorem here,