Information-Theoretic Bounds on The Removal of Attribute-Specific Bias
  From Neural Networks
Ensuring a neural network is not relying on protected attributes (e.g., race,
sex, age) for predictions is crucial in advancing fair and trustworthy AI.
While several promising methods for removing attribute bias in neural networks
have been proposed, their limitations remain under-explored. In this work, we
mathematically and empirically reveal an important limitation of attribute bias
removal methods in presence of strong bias. Specifically, we derive a general
non-vacuous information-theoretical upper bound on the performance of any
attribute bias removal method in terms of the bias strength. We provide
extensive experiments on synthetic, image, and census datasets to verify the
theoretical bound and its consequences in practice. Our findings show that
existing attribute bias removal methods are effective only when the inherent
bias in the dataset is relatively weak, thus cautioning against the use of
these methods in smaller datasets where strong attribute bias can occur, and
advocating the need for methods that can overcome this limitation.
Jiazhi Li, Mahyar Khayatkhoei, Jiageng Zhu, Hanchen Xie, Mohamed E. Hussein, Wael AbdAlmageed
# Information-Theoretic Bounds on The Removal of Attribute-Specific Bias From Neural Networks

###### Abstract

Ensuring a neural network is not relying on protected attributes (_e.g._, race, sex, age) for predictions is crucial in advancing fair and trustworthy AI. While several promising methods for removing attribute bias in neural networks have been proposed, their limitations remain under-explored. In this work, we mathematically and empirically reveal an important limitation of attribute bias removal methods in presence of strong bias. Specifically, we derive a general non-vacuous information-theoretical upper bound on the performance of any attribute bias removal method in terms of the bias strength. We provide extensive experiments on synthetic, image, and census datasets to verify the theoretical bound and its consequences in practice. Our findings show that existing attribute bias removal methods are effective only when the inherent bias in the dataset is relatively weak, thus cautioning against the use of these methods in smaller datasets where strong attribute bias can occur, and advocating the need for methods that can overcome this limitation.

## 1 Introduction

_Protected attributes_ is a term originating from Sociology [30] referring to a finite set of attributes that must not be used in decision-making to prevent exacerbating societal biases against specific demographic groups [9]. For example, in deciding whether or not someone should be qualified for a bank loan, race (as one of the protected attributes) must not influence the decision. Given the widespread use of neural networks in real-world decision-making, developing methods capable of explicitly excluding protected attributes from the decision process - more generally referred to as removing attribute bias [34] - is of paramount importance.

While many promising methods for removing attribute bias in neural networks have been proposed in the recent years [2; 20; 39; 29; 35; 41; 17], the limitations of these methods remain under-explored. In particular, existing studies explore the performance of these methods only in cases where the protected attribute (_e.g._, race) is _not strongly predictive_ of the prediction target (_e.g._, credit worthiness). However, this implicit assumption does not always hold in practice, especially in cases where training data is scarce. For example, in diagnosing Human Immunodeficiency Virus (HIV) from Magnetic Resonance Imaging (MRI), HIV subjects were found to be significantly older than control subjects, making age a strong attribute bias for this task [1]. Another example is the Pima Indians Diabetes Database which contains only 768 samples where several spurious attributes become strongly associated with diabetes diagnosis [33; 27]. Even the widely-used CelebA dataset [28] contains strong attribute biases: for example in predicting blond hair, sex is a strong predictor 1. Therefore, it is crucial to study the
performance of bias removal methods beyond the moderate bias region to understand their limitations and the necessary conditions for their effectiveness.

In Fig. 1, we will illustrate by a specific example the limitation in bias removal methods that we will later investigate theoretically and empirically in several real-world datasets. In this example, we conduct an extended version of a popular controlled experiment for evaluating the performance of attribute bias removal [20; 31; 41]. The task is to predict digits from colored MNIST images [20] where color is considered a protected attribute. During training, each digit is assigned a unique RGB color with a variance (_i.e._, the smaller the color variance, the more predictive the color is of the digit, and the stronger the attribute bias). To measure how much the trained model relies on the protected attribute in its predictions, model accuracy is reported on a held-out subset of MNIST with uniformly random color assignments (_i.e._, where the color is not predictive of the digit). While state-of-the-art methods [20; 31; 35; 41] report results for the color variance only in the range \([0.02,0.05]\) (without providing any justification for this particular range), we explore the results for the missing range of \([0,0.02]\), which we denote as the _strong bias region_. As shown in Fig. 1, in the strong bias region, we observe that the effectiveness of all existing methods sharply declines and that there exists a _breaking point_ in their effectiveness. The breaking point of a method is defined as the weakest bias strength at which its performance becomes indistinguishable from the baseline under a two-sample one-way Kolmogorov-Smirnov test with significance level of \(0.05\). The main goal of this paper is to study the cause and extent of this limitation empirically and theoretically.

## 2 Related Work

**Bias in Neural Networks.** Mitigating bias and improving fairness in neural networks has received considerable attention in recent years [14; 7; 22; 12; 8; 25]. The methods proposed for mitigating bias in neural networks can be broadly grouped into two categories: 1) methods that aim to mitigate the uneven performance of neural networks between majority and minority groups; and 2) methods that aim to reduce the dependence of neural network prediction on specific attributes. Most notable examples of the former group are methods for constructing balanced training set [6; 19], synthesizing additional samples from the minority group [4; 26], importance weighting the under-represented samples [37], and domain adaption techniques that adapt well-learnt representations from the majority group to the minority group [38; 13; 18]. In this work, our focus is on the second group of methods,

Figure 1: Accuracy of attribute bias removal methods under different levels of bias strength in Colored MNIST, showing results on the previously unexplored region of color variance \(<0.02\). The breaking point of each method, where its performance becomes statistically similar to the baseline classifier, is labeled with \(\blacktriangle\) on the x-axis. While all methods clearly outperform baseline in moderate bias region, their effectiveness sharply declines to baseline as bias strength increases. The plot shows average accuracy (lines) with one standard deviation error (shaded) over 15 randomized training runs.
which we will further divide into two subgroups discussed below: methods that implicitly or explicitly minimize the mutual information between learnt latent features and the specific protected attribute.

**Explicit Mutual Information Minimization.** Several methods aim to directly minimize mutual information (MI) between a latent representation for the target classification and the protected attributes, in order to learn a representation that is predictive of the target but independent of the protected attributes, hence removing attribute bias. These methods mainly differ in the way they estimate MI. Most notable examples include LNL [20] which minimizes the classification loss together with a MI regularization loss estimated by an auxiliary distribution; BackMI [31] which minimizes classification loss and MI estimated by a neural estimator [5] through the statistics network; and, CSAD [41] which minimizes MI estimated by [16] between a latent representation to predict target and another latent representation to predict the protected attributes.

**Implicit Mutual Information Minimization.** Another group of methods aims to remove attribute bias by constructing surrogate losses that implicitly reduce the mutual information between protected attributes and the target of classification. Most notably, LfF [29] proposes training two models simultaneously, where the first model will prioritize easy features for classification by amplifying the gradient of cross-entropy loss with the predictive confidence (softmax score), and the second model will down-weight the importance of samples that are confidently classified by the first model, therefore avoiding features that are learnt easily during training, which are likely to be spurious features leading to large MI with protected attributes; EnD [35] adds regularization terms to the typical cross-entropy loss that push apart the feature vectors of samples with the same protected attribute label to become orthogonal (thereby increasing the conditional entropy of them given the protected attribute); BlindEye [2] pushes the distribution obtained by the attribute classifier operating on latent features towards uniform distribution by minimizing the entropy between them; and, domain independent training (DI) [39] learns a shared representation with an ensemble of separate classifiers per domain to ensure that the prediction from the unified model is not biased towards any domain.

**Trade-offs between Bias Removal and Model Utility.** The trade-offs between fairness and accuracy in machine learning models have garnered significant discussion. Most notably, Kleinberg _et al_. [21] prove that except in highly constrained cases, no method can simultaneously satisfy three fairness conditions: _calibration within groups_ which requires that the expected number of individuals predicted as positive should be proportional to a group-specific fraction of individuals in each group, _balance for the negative class_ which requires that the average score of individuals predicted as negative should be equal across groups, and _balance for the positive class_ which requires the balance for the positive class across groups; and, Dutta _et al_. [11] theoretically demonstrate that, under certain conditions, it is possible to simultaneously achieve optimal accuracy and fairness in terms of _equal opportunity_[14] which requires even false negative rates or even true positive rates across groups. Different from the above-mentioned fairness criteria, we focus on another well-known fairness criterion, _demographic parity_[22; 12], which requires even prediction probability across groups, _i.e_., independence between model prediction and protected attributes. Regarding this criterion, Zhao and Gordon [40] show that any method designed to learn fair representations, while ensuring model predictions are independent of protected attributes, faces an information-theoretic lower bound on the joint error across groups. In contrast, we derive a general information-theoretic upper bound on the best attainable performance, which is not limited to the case where model predictions are independent of protected attributes and considers different levels of the retained protected attribute information in the learnt features.

## 3 Bounding the Performance of Attribute Bias Removal Methods

The observations in Fig. 1 revealed that the existing methods are not effective when the attribute bias is too strong, _i.e_., they all have a breaking point, and that there is a continuous connection between their effectiveness and the strength of the attribute bias. However, so far, these observations are limited to the particular Colored MNIST dataset. In this section, we show that this situation is in fact much more general. By deriving an upper bound on the classification performance of any attribute bias removal method in terms of the bias strength, regardless of the dataset and domain, we will elucidate the cause and extent of the limitation we observed in Fig. 1.

We first need to formalize the notions of performance, attribute bias strength, and attribute bias removal. Let \(X\) be a random variable representing the input (_e.g_., images) with support \(\mathcal{X}\), \(Y\) a random variable representing the prediction target (_e.g_., hair color) with support \(\mathcal{Y}\), and \(A\) a
random variable representing the protected attribute (_e.g._, sex). We define the attribute bias removal method as a function \(f:\mathcal{X}\rightarrow\mathcal{Z}\) that maps input data to a latent bottleneck feature space \(\mathcal{Z}\) inducing the random variable \(Z\), and consider the prediction model as a function \(g:\mathcal{Z}\rightarrow\mathcal{Y}\) inducing the random variable \(\hat{Y}\). According to the information bottleneck theory [36, 32], the goal of classification can be stated as maximizing the mutual information between prediction and target, namely \(I(\hat{Y};Y)\), which is itself bounded by the mutual information between feature and target due to the data processing inequality [10], _i.e._, \(I(\hat{Y};Y)\leq I(Z;Y)\). Intuitively, \(I(Z;Y)\) measures how informative the features learnt by the model are of the target, with \(I(Z;Y)=0\) indicating completely uninformative learnt features: the best attainable prediction performance is no better than chance. Therefore, the optimization objective of attribute bias removal methods can be formalized as learning \(f\) parameterized by \(\theta\) that minimizes mutual information between feature and attribute \(I(Z_{\theta};A)\), while maximizing mutual information between feature and target \(I(Z_{\theta};Y)\).

Given the above definitions, we can state our goal in this section concretely: to derive a connection between \(I(Z;Y)\) (the best attainable performance), \(H(Y|A)\) (the attribute bias strength measured by the conditional entropy of target given attribute), and \(I(Z;A)\) (the amount of remaining attribute bias in the learnt feature). Note that the stronger the attribute bias is, the better the attribute can predict the target, hence the lower \(H(Y|A)\). So the extreme attribute bias happens when \(H(Y|A)=0\). In this particular extreme setting, the following proposition shows that no classifier can outperform random guess if the attribute is removed from the feature, _i.e._, \(I(Z;A)=0\).

Figure 2: Empirically verifying the bound in Theorem 1 on CelebA. The x-axis shows \(H(Y|A)\), which we vary directly by adjusting the fraction of bias-conflicting images while ensuring a constant number of biased images in the training set. We empirically compute \(H(Y|A)\) based on the distribution of \(Y\) and \(A\) in the modified training set, and estimate mutual information using [5]. The bound \(0\leq I(Z;Y)\leq I(Z;A)+H(Y|A)\) holds in all cases.
**Proposition 1**.: _Given random variables \(Z,Y,A\), in case of the extreme attribute bias \(H(Y|A)=0\), if the attribute is removed from the feature \(I(Z;A)=0\), then \(I(Z;Y)=0\), i.e., no classifier can outperform random guess. 2_

Footnote 2: Proof in Appendix.

This proposition extends and explains the observation on the leftmost location of the x-axis in Fig. 1: when the color variance is zero, color is completely predictive of the digit, \(H(Y|A)=0\), and removing color from the latent feature, \(I(Z;A)=0\), makes the prediction uninformative, \(I(Z;Y)=0\). However, Proposition 1 does not explain the rest of the curve beyond just zero color variance. The following theorem closes this gap by deriving a bound on the performance of attribute bias removal methods in terms of the attribute bias strength, thus providing a more complete picture of the limitation of attribute bias removal, and elucidating the connection of performance and bias strength.

**Theorem 1**.: _Given random variables \(Z,Y,A\), the following inequality holds without exception: 3_

Footnote 3: _Proof in Appendix._

\[0\leq I(Z;Y)\leq I(Z;A)+H(Y|A) \tag{1}\]

**Remark 1**.: _In the extreme bias case \(H(Y|A)=0\), the bound in Eq. (1) shows that the model performance is bounded by the amount of protected attribute information that is retained in the feature, namely \(I(Z;Y)\leq I(Z;A)\). This puts the model in a trade-off: the more the attribute bias is removed, the lower the best attainable performance._

**Remark 2**.: _When the protected attribute is successfully removed from the feature \(I(Z;A)=0\), the bound in Eq. (1) shows that the model's performance is bounded by the strength of the attribute bias, namely \(I(Z;Y)\leq H(Y|A)\). This explains the gradual decline observed in Fig. 1 as we moved from the moderate to the strong bias region (from right to left towards zero color variance)._

**Remark 3**.: _When \(H(Y|A)=0\) and \(I(Z;A)=0\), Eq. (1) reduces to the result of Proposition 1, \(I(Z;Y)=0\), hence no classifier can outperform random guess._

**Remark 4**.: _We emphasize that the provided bound is placed on the best attainable performance. So while decreasing the bound will decrease performance, increasing the bound will not necessarily result in an increased performance. For example, consider the baseline classifier: even though there is no attribute bias removal performed and therefore the bound can be arbitrarily large, \(I(Z;A)\gg 0\), the model declines in the strong bias region since learning the highly predictive protected attribute is likely in the non-convex optimization._

To empirically test our theory in a real-world dataset, we compute the terms in Theorem 1 for several attribute bias removal methods in CelebA and plot the results in Fig. 2. In these experiments, blond hair is the target \(Y\), and sex is the protected attribute \(A\). We vary the bias strength \(H(Y|A)\) by increasing/decreasing the fraction of bias-conflicting images in the training set (images of females with non-blond hair and males with blond hair) while maintaining the number of biased images in the training set at 89754. Then, we compute \(H(Y|A)\) directly and estimate the mutual information terms \(I(Z;A)\) and \(I(Z;Y)\) using mutual information neural estimator [5]. We observe that the bound holds in accordance with Theorem 1 in all cases. Now that we have mathematically and empirically shown the existence of the bound, in the next section, we will investigate the extent of its consequences for attribute bias removal methods in image and census datasets, in addition to the consequence we have already observed in the synthetic Colored MNIST dataset in Fig. 1.

## 4 Experiments

In this section, we empirically study the performance of the existing attribute bias removal methods in the strong bias setting. We conduct experiments with an extensive list of existing state-of-the-art attribute bias removal methods [20; 39; 29; 35; 41; 17] on Colored MNIST as well as two real-world datasets: CelebA [28] and Adult [3]. For all results, we report average performance with one standard deviation over multiple trials (15 trials in Colored MNIST, 5 in CelebA, 25 in Adult).

**Colored MNIST Dataset** is an image dataset of handwritten digits, where each digit is assigned a unique RGB color with a certain variance, studied by these methods [20; 31; 35; 41]. The training set consists of 50000 images and the testing set of 10000 images with uniformly random color assignment. The color is considered the protected attribute \(A\) and the digit is the target \(Y\). The
variance of color in the training set determines the strength of the bias \(H(Y|A)\). The results on this dataset are reported in Fig. 1 and explained in Sec. 1.

**CelebA Dataset**[28] is an image dataset of human faces studied by these methods [20, 39, 29, 35, 41, 17]. Facial attributes are considered the prediction target \(Y\) (_e.g._, blond hair), and sex is the protected attribute \(A\). For each target, there is a notion of _biased samples_ - images in which \(Y\) is positively correlated with \(A\), _e.g._, images of females with blond hair and males without blond hair - and a notion of _bias-conflicting_ samples - images in which \(Y\) is negatively correlated with \(A\), _e.g._, images of females without blond hair and males with blond hair. The fraction of bias-conflicting images in the training set determines the strength of the bias \(H(Y|A)\). For training, we consider the original training set of CelebA denoted _TrainOri_ consisted of 162770 images with \(H(Y|A)=0.36\), and an extreme bias version in which the bias-conflicting samples are removed from the original training set denoted _TrainEx_ consisted of 89754 images with \(H(Y|A)=0\). Additionally, we construct 16 training sets between TrainOri and TrainEx by maintaining the number of biased samples and varying the fraction of bias-conflicting samples. For testing, we consider two versions of the original testing set: (1) _Unbiased_ consists of 720 images in which all pairs of target and protected attribute labels have the same number of samples, and (2) _Bias-conflicting_ consists of 360 images in which biased samples are excluded from the _Unbiased_ dataset (only bias-conflicting samples remain).

**Adult Dataset**[3] is a census dataset of income which is a well-known fairness benchmark. Income is considered the target \(Y\) and sex is the protected attribute \(A\). To construct training and testing sets, we follow the setup of CelebA explained above, but we further mitigate the effect of data imbalance and the variation in the total number of training samples. For training, we consider the balanced version of the original training set of Adult denoted _TrainOri_ consisted of 7076 records with \(H(Y|A)=0.69\), and an extreme bias version in which the bias-conflicting samples are removed from TrainOri and the same number of biased samples are appended denoted _TrainEx_ with \(H(Y|A)=0\) consisted of the same total number (7076) of records as TrainOri. Additionally, we construct 11 training sets in between TrainOri and TrainEx by varying the fraction of biased samples in TrainEx while maintaining the total size of training set. For testing, we consider two versions of the original testing set: (1) _Unbiased_ consists of 7076 records in which all pairs of target and protected attribute labels have the same number of samples, and (2) _Bias-conflicting_ consists of 3538 records in which biased samples are excluded from the _Unbiased_ dataset (only bias-conflicting samples remain).

**Training Details.** For digit classification on Colored MNIST, we use Lenet-5 [24] as the baseline classifier. For facial attribute classification on CelebA, following CSAD [41], we use ResNet-18 [15] as the baseline classifier. For income prediction on Adult dataset, we use a three-layer MLP as the baseline classifier. For all experiments, we set learning rate to 0.001, batch size to 32, and Adam optimizer with \(\beta_{1}=0.9\) and \(\beta_{2}=0.999\). All hyperparameters are set according to respective papers.

### Analysis of the Extreme Bias Point \(H(y|a)=0\)

In this section, we investigate the consequences of applying existing attribute bias removal methods at the extreme bias point \(H(Y|A)=0\). We study two aspects of each method, the classification

\begin{table}
\begin{tabular}{l c c c c} \hline \hline \multirow{2}{*}{Method} & \multicolumn{2}{c}{Test Accuracy} & \multicolumn{2}{c}{Mutual Information} \\ \cline{2-5}  & Unbiased \(\uparrow\) & Bias-conflicting \(\uparrow\) & \(I(Z;A)\downarrow\) & \(\Delta\) (\%) \(\uparrow\) \\ \hline Random guess & 50.00 & 50.00 & 0.57 & 0.00 \\ Baseline & 66.11\(\pm\)0.32 & 33.89\(\pm\)0.45 & 0.57\(\pm\)0.01 & 0.00 \\ \hline LNL [20] & 64.81\(\pm\)0.17 & 29.72\(\pm\)0.26 & 0.56\(\pm\)0.06 & 1.75 \\ DI [39] & 66.83\(\pm\)0.44 & 33.94\(\pm\)0.65 & 0.55\(\pm\)0.02 & 3.51 \\ LfF [29] & 64.43\(\pm\)0.43 & 30.45\(\pm\)1.63 & 0.57\(\pm\)0.03 & 0.00 \\ EnD [35] & 66.53\(\pm\)0.23 & 31.34\(\pm\)0.89 & 0.57\(\pm\)0.05 & 0.00 \\ CSAD [41] & 63.24\(\pm\)2.36 & 29.13\(\pm\)1.26 & 0.55\(\pm\)0.04 & 3.51 \\ BCL [17] & 65.30\(\pm\)0.51 & 33.44\(\pm\)1.31 & 0.56\(\pm\)0.07 & 1.75 \\ \hline \hline \end{tabular}
\end{table}
Table 1: Performance of attribute bias removal methods trained under extreme bias in CelebA (_TrainEx_ training set) to predict _blond hair_. \(\Delta\) indicates the difference from baseline. None of the methods can effectively remove the bias \(I(Z;A)\) compared to baseline.
performance (measured by accuracy on Unbiased and Bias-conflicting settings) and its ability to remove bias (measured by estimating \(I(Z;A)\) using [5] on the training set). Ideally, a method must achieve on-par or better accuracy than the baseline while learning a representation \(Z\) that does not reflect the attribute bias present in the training set (\(I(Z;A)=0\)), hence successfully removing the bias. However, in Tab. 1, we observe that none of the existing methods applied to CelebA can significantly reduce the bias \(I(Z;A)\) in the extreme bias setting. Similarly, in Tab. 2, we observe that none of the methods applied to Adult dataset can reduce \(I(Z;A)\). These observations are explained by Proposition 1 which states that maintaining classification performance above random guess while achieving \(I(Z;A)=0\) at \(H(Y|A)=0\) is impossible.

\begin{table}
\begin{tabular}{l c c c c} \hline \hline \multirow{2}{*}{Method} & \multicolumn{2}{c}{Test Accuracy} & \multicolumn{2}{c}{Mutual Information} \\ \cline{2-5}  & Unbiased \(\uparrow\) & Bias-conflicting \(\uparrow\) & \(I(Z;A)\downarrow\) & \(\Delta\) (\%) \(\uparrow\) \\ \hline Random guess & 50.00 & 50.00 & 0.69 & 0.00 \\ Baseline & 50.59\(\pm\)0.54 & 1.19\(\pm\)0.83 & 0.69\(\pm\)0.00 & 0.00 \\ \hline LNL [20] & 50.10\(\pm\)0.18 & 0.43\(\pm\)0.46 & 0.69\(\pm\)0.01 & 0.00 \\ DI [39] & 50.61\(\pm\)0.28 & 0.65\(\pm\)0.64 & 0.69\(\pm\)0.01 & 0.00 \\ LfF [29] & 50.33\(\pm\)0.34 & 0.78\(\pm\)0.65 & 0.69\(\pm\)0.01 & 0.00 \\ EnD [35] & 50.59\(\pm\)0.75 & 1.18\(\pm\)0.96 & 0.69\(\pm\)0.00 & 0.00 \\ CSAD [41] & 50.76\(\pm\)2.22 & 1.43\(\pm\)2.46 & 0.69\(\pm\)0.01 & 0.00 \\ BCL [17] & 50.83\(\pm\)1.34 & 0.52\(\pm\)0.83 & 0.69\(\pm\)0.00 & 0.00 \\ \hline \hline \end{tabular}
\end{table}
Table 2: Performance of attribute bias removal methods trained under extreme bias in Adult (_TrainEx_ training set) to predict income. \(\Delta\) indicates the difference from baseline. None of the methods can effectively remove the bias \(I(Z;A)\) compared to baseline.

Figure 3: Accuracy and mutual information under different bias strengths in CelebA. As bias strength increases (moving from right to left), the performance of all methods degrades and sharply declines to baseline at the breaking point (labeled by \(\blacktriangle\)).
In Tab. 1, we also observe a trade-off between \(I(Z;A)\) and accuracy, where reducing the bias (when \(\Delta>0\)) results in a reduction in accuracy. This is explained by Theorem 1, which states that when \(H(Y|A)=0\), the amount of remained bias in the learnt feature \(Z\) is an upper bound to the best performance, _i.e._, \(I(Z;Y)\leq I(Z;A)\), and therefore removing more bias can result in lower performance. The only exception to this trade-off seems to be DI [39]. We conjecture that this is due to its enhanced ability in achieving the best attainable classification performance (see Remark 4).

### Analysis of the Strong Bias Region \(H(y|a)>0\)

In this section, we go beyond the extreme bias point, and more generally investigate the consequences of applying existing bias removal methods on the entire range of bias strength, _i.e._, connecting the extreme bias training setting (TrainEx) we studied in Sec. 4.1 to the moderate bias in the original training setting (TrainOri) commonly studied in existing methods. We again study two aspects of each method, its classification performance (measured by accuracy on Unbiased and Bias-conflicting settings) and its ability to remove bias (measured by estimating \(I(Z;A)\) using [5] on the training set). In Figs. 3 and 4, we observe a decline in the performance of all methods as the bias becomes stronger, in both CelebA and Adult datasets, similar to our observation in Colored MNIST in Fig. 1. This observation is consistent with Theorem 1, which states that the bias strength determines an upper bound on the best performance of bias removal methods, regardless of the dataset and method.

In Figs. 2(c) and 3(c), we use breaking points to approximately divide the strong bias region into three phases and explain the observed changes in the performance of methods from the perceptive of Theorem 1. In phase 1, as \(H(Y|A)\) increases from zero to the breaking point (bias strength decreases), we observe that the attribute bias \(I(Z;A)\) is not minimized because of the trade-off between best attainable performance \(I(Z;Y)\) and attribute bias removal when bias is very strong: the methods choose to increase accuracy towards the best attainable accuracy \(I(Z;Y)\) rather than removing attribute bias (this choice is most likely due to the larger weight on the accuracy term in

Figure 4: Accuracy and mutual information under different bias strengths in Adult. As bias strength increases (moving from right to left), the performance of all methods degrades and sharply declines to baseline at the breaking point (labeled by \(\blacktriangle\)).
their objectives). Then, in phase 2, as \(H(Y|A)\) increases through the breaking point (bias strength decreases further), the methods start to minimize attribute bias \(I(Z;A)\) because the upper bound on best attainable performance \(I(Z;Y)\) is now large enough to avoid the trade-off between accuracy and attribute bias removal. Finally, in phase 3, as \(H(Y|A)\) further departs from the breaking point, accuracy gradually approaches its best attainable performance, while attribute bias \(I(Z;A)\) is minimized further below that of the baseline because the weaker bias strength now allows the model to distinguish \(Y\) from \(A\) so that minimizing attribute bias and maximizing accuracy do not compete.

## 5 Conclusion and Future Work

In this work, we mathematically and empirically showed the sensitivity of state-of-the-art attribute bias removal methods to the bias strength. This highlights a previously overlooked limitation of these methods. In particular, we empirically demonstrated that when a protected attribute is strongly predictive of a target, these methods become ineffective. To understand the cause and extent of these findings, we derived an information-theoretical upper bound on the performance of any attribute bias removal method, and verified it in experiments on synthetic, image, and census datasets. These findings not only caution against the use of existing attribute bias removal methods in datasets with potentially strong bias (_e.g._, small datasets), but also motivate the design of future methods that can work even in strong bias situations, for example by utilizing external unlabelled datasets to relax the upper bound. Additionally, investigating the role of bias strength in removing attribute bias from generative models is another interesting direction for future research.

## Acknowledgement

This research is based upon work supported in part by the Office of the Director of National Intelligence (ODNI), Intelligence Advanced Research Projects Activity (IARPA), via [2022-21102100007]. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies, either expressed or implied, of ODNI, IARPA, or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for governmental purposes notwithstanding any copyright annotation therein.
