1 Introduction↩︎

Although algorithmic bias and distribution shifts are often considered separate problems, there is a recent body of empirical work that shows many instances of algorithmic bias are caused by distribution shifts. Broadly speaking, there are two ways distribution shifts cause algorithmic biases obermeyer2021algorithmic?: (i) The model is trained to predict the wrong target; (ii) The model is trained to predict the correct target, but its predictions are inaccurate for demographic groups that are underrepresented in the training data.

From a statistical perspective, the first type of algorithmic bias is caused by concept or posterior drift between the training data and the real-world. This leads to a mismatch between the model’s predictions and actual data. This type of algorithmic bias is also known as label choice bias obermeyer2019dissecting?. The second type of algorithmic biases arises when ML models are trained or evaluated with non-diverse data, causing the models to perform poorly on underserved groups. This type of algorithmic bias is caused by a covariate shift between the training data and the real-world data. In this paper, we mostly focus on algorithmic biases caused by covariate shift. The overlap between the problems of algorithmic bias and distribution shift suggests two questions:

1. Is it possible to overcome distribution shifts with algorithmic fairness interventions?

2. Is it possible to mitigate biases caused by distribution shifts with domain adaptation methods?

For a concrete example, consider building an ML model to predict a person’s occupation from their biography. For this task, Yurochkin et al. yurochkin2021sensei? showed that ML models trained on top of pre-trained language models without any algorithmic fairness intervention can be unfair: they can change prediction (e.g., from attorney to paralegal or vice versa), when the name and gender pronouns are changed in the input biography. This is a violation of individual fairness (IF), in part caused by underrepresentation of female attorneys in the train (source) data. Consequently, this model underperforms on female attorneys, in particular when female attorneys are better represented in the target domain. This is a type of distribution shift known as subpopulation shift in the domain adaptation literature koh2021wilds?. In this case, enforcing IF will not only result in a fairer model, but can also improve performance in the target domain, i.e., solve the domain adaptation problem.

Now, under the same source and target domains, consider applying a domain adaptation (DA) method that matches the distributions of representations on the domains (see Appendix 11 for a brief review of DA and algorithmic fairness under distribution shifts). Assuming class marginals are the same¹, i.e., source and target have the same fraction of attorneys, any differences between the source and the target distribution are due to different fractions of male to female attorneys. Learning a feature (representation) extractor that is invariant to gender pronouns and names will align the two domains and result in a model that is individually fair. For group fairness, Schumann et al. schumann2019transfer? and Creager et al. creager2021environment? show that it is possible to leverage DA algorithms to enforce group fairness. The goal of this paper is to complement these results by precisely characterizing the cases in which enforcing IF achieves domain generalization and vice a versa. Our contributions can be summarized as:

1. We show that methods designed for IF can help ML models adapt/generalize to new domains, i.e., improve the accuracy of the trained ML model on out-of-distribution samples.

2. Conversely, we show that DA algorithms that align the feature distributions in the source and target domains can be used to improve IF under certain probabilistic conditions on the features.

We verify our theory on the Bios de2019bias? and the Toxicity dixon2018measuring? datasets: enforcing IF via the methods of Yurochkin et al. yurochkin2021sensei? and Petersen et al. petersen2021post? improves accuracy on the target domain, and DA methods ganin2016domain?, shu2018dirtt?, shen2018wasserstein? trained with appropriate source and target domains improve IF.

2 Overcoming Distribution Shift by Enforcing Individual Fairness↩︎

The goal of individual fairness is to ensure similar treatment of similar individuals. Dwork et al. dwork2012fairness? formalize this notion using \(L\)-Lipschitz continuity of an ML model \(f:\cX\to\cY\): \[d_{\cY}(f(x),f(x')) \le Ld_{\cX}(x,x') \label{eq:individual-fairness}\tag{1}\] for all \(x,x'\in\cX\). Here, \(d_{\cY}\) is the metric on the output space quantifying the similarity of treatment of individuals, and \(d_{\cX}\) is the metric on the input space quantifying the similarity of individuals.

Algorithms for enforcing IF are similar to algorithms for domain adaptation/generalization. For example, adversarial training/distributionally robust optimization can not only enforce IF yurochkin2020training?, yurochkin2021sensei?, but can also be used for training ML models that are robust to distribution shifts shu2018dirtt?, sagawa2019distributionally?. This similarity is more than a mere coincidence: the goal in both enforcing IF and domain adaptation/generalization is ignoring uninformative dissimilarity. In IF, we wish to ignore variation among inputs that are attributed to variation of the sensitive attribute. In domain adaptation/generalization, we wish to ignore variation among inputs that are attributed to the idiosyncracies of the domains. Mathematically, ignoring uninformative dissimilarity is enforcing invariance/smoothness of the ML model among inputs that are dissimilar in uninformative ways. For example, 1 requires the model to be approximately constant on small \(d_{\cX}\)-balls.

In this section, we exploit this connection between IF and domain adaptation/generalization to show that enforcing IF can improve accuracy in target domain under covariate shift if the regression function is individually fair. In order words, if the inductive bias from enforcing IF is correct, then enforcing IF improves accuracy in the target domain. More concretely, we consider the task of adapting an ML model from a source domain to a target domain. We have \(n_s\) labeled samples from the source domain \(\{(x_{s,i}, y_{s,i})\}_{i=1}^{n_s}\) and \(n_t\) unlabeled samples from the target domain \(\{x_{t,i}\}_{i=1}^{n_t}\). Our goal is to obtain a model \(\widehat{f}\in\cF\) that has comparable accuracy on the source and target domains. We assume the regression function \(f_0(x) \triangleq \Ex\big[y_i\mid x_i = x\big]\) in the source and target domains are identical. \[y_{e,i} = f_0(x_{e,i}) + {\epsilon}_{e,i},\quad e\in\{s,t\}, \label{eq:covariate-shift}\tag{2}\] where \({\epsilon}_i\)’s are exogenous error terms with mean zero and variance \(\sigma_e^2\). This is a special case of distribution shift called covariate shift shimodaira2000improving?. The covariate shift problem is most challenging when the model class is mis-specified (i.e., \(f_0\notin\cF\)) and this is the primary focus of this paper. As an example, consider the Inclusive Images Challenge shankar2017no?. Publicly available image datasets often lack geo-diversity. Thus, ML models trained on such datasets tend to make mistakes on images from underrepresented countries. As a concrete example, while brides in western countries typically wear white dresses at wedding ceremonies, brides in non-western countries may not. An ML model trained on images from mostly western countries may not recognize brides from other parts of the world that are not wearing white dresses. Although there is a function (on images) that recognizes brides from non-western countries (e.g., the function humans implicitly use to recognize brides), the ML model does not learn this function because either the function is not in the model class and/or the inductive bias of the learning algorithm leads the algorithm to pick a different function (i.e., inductive bias of learning algorithm is mis-specified).

To warm up, we consider the transductive (learning) setting before moving on to the inductive setting. Recall that, in the transductive setting, the learner is given a set of labeled samples and another set of unlabeled samples. The goal is correctly predicting the labels of the given unlabeled samples; the learner is unconcerned with the accuracy of the model on new test samples. This is different from the inductive setting, where the goal is correctly predicting the labels of new test samples. The features of the unlabeled samples (but not their labels) are used for training in both settings. We provide theoretical results for both settings.

2.1 Warm Up: The Transductive Setting↩︎

In the transductive setting, we are only concerned with the accuracy of the predictions on the unlabeled samples from the target domain in the training data. The distribution of unlabeled samples is different from the (marginal) distribution of features in the source domain due to covariate shift. Thus, the problem is similar to that of extrapolation/label propagation in which we wish to propagate the labels/signal from the labeled samples in the source domain to the unlabeled samples in the target domain. Towards this goal, we leverage the (labeled) source and (unlabeled) target samples and the inductive bias on the smoothness of the regression function. We encode this inductive bias in a regularizer \(\cR\) and solve the following regularized risk minimization problem \[\textstyle \label{eq:hat95f95reg} \hat{f} = \mathop{\mathrm{arg\,min}}_{f \in \cF} \left[\frac{1}{n_s}\sum_{i=1}^{n_s}\cL\left(y_i, f(x_i)\right) + \lambda \cR_n\left(f(X)\right)\right]\tag{3}\] where \(\cF\) is the model class, \(\cL\) is a loss function, and \(\lambda > 0\) is a regularization parameter. In the transductive setting, the regularizer \(\cR_n\) is a function of the vector of model outputs on the source and target inputs: \(f(X) \triangleq \begin{bmatrix}f(X_s)^\top, f(X_t)^\top\end{bmatrix}^\top\), where \(f(X_s)\in\reals^{n_s}\) (resp. \(f(X_t)\in\reals^{n_t}\)) is the vector of outputs on the source (resp. target) inputs. Intuitively, the regularizer enforces invariance/smoothness of the model outputs on the source and target inputs.

A concrete example of a such a regularizer is the graph Laplacian regularizer. A graph Laplacian regularizer is based on a similarity symmetric kernel \(K\) on the input space \(\cX\). For example, Petersen et al. petersen2021post? take kernel \(K\) to be a decreasing function of a fair metric that is learned from data mukherjee2020Two?, e.g., a metric in which the distance between male and female biographies with similar relevant content is small. In domain adaptation, a similar intuition can be applied. For example, suppose the source train data consists of Poodle dogs and Persian cats (the task is to distinguish cats and dogs), and the target data consists of Dalmatians and Siamese cats santurkar2020breeds?. Then, a meaningful metric for constructing kernel \(K\) assigns small distances to different breeds of the same species.

Given the kernel, we construct the similarity matrix \(\bK = \begin{bmatrix}K\left(X_i, X_j\right)\end{bmatrix}_{i,j= 1}^n\). Note that, here, we are considering all the source and target covariates together. Based on the similarity matrix, the (unnormalized) Laplacian matrix is defined as \(\bL = \bD - \bK\) where \(\bD\) is a diagonal matrix with \(\bD_{i, i} = \sum_j K(X_i, X_j)\), which is often denoted as the degree of the \(i^{th}\) observation. There are also other ways of defining \(\bL\) (e.g., \(\bL = \bD^{-1/2}\bK\bD^{-1/2}\) or \(\bL = \bI - \bD^{-1}\bK\)) which would also lead to the similar conclusion, but we stick to unnormalized Laplacian for the ease of exposition. Based on the Laplacian matrix \(\bL\), we define the graph Laplacian regularizer \(\cR\) as: \[\textstyle \cR_n(f(X)) = \frac{1}{n^2}f(X)^{\top}\bL f(X) = \frac{1}{n^2} \sum_{i, j}K(X_i, X_j)\left(f(X_i) - f(X_j)\right)^2.\] The above regularizer enforces that if \(K(X_i, X_j)\) is large for a pair \((X_i, X_j)\) (i.e., they are similar), \(f(X_i)\) must be close to \(f(X_j)\). As mentioned earlier, for individual fairness, \(K(X_i, X_j)\) is chosen to be a monotonically decreasing function of \(d_{\text{fair}}(X_i, X_j)\), which ensures that \(f(X_i)\) and \(f(X_j)\) are close to each other when \(X_i\) is close to \(X_j\) with respect to the fair metric (for more details, see Petersen et al. petersen2021post?). Recently, Lahoti et al. lahoti2019ifair?, Kang et al. kang2020inform?, and Petersen et al. petersen2021post? used the graph Laplacian regularizer to post-process ML models so that they are individually fair. This is also widely used in semi-supervised learning to leverage unlabeled samples chapelle2006Semisupervised?.

We focus on problems in which the model class \(\cF\) is mis-specified, i.e., \(f_0\notin\cF\). If the model is well-specified (i.e., \(f_0\in\cF\)), the optimal prediction rule in the training and target domains are identical (both are \(f_0\)). It is possible to learn the optimal prediction rule for the target domain from the training domain (e.g., by empirical risk minimization (ERM)), and there is no need to adapt models trained in the source domain to the target. On the other hand, if the model is mis-specified, the transfer learning task is non-trivial because the optimal prediction rule model depends on the distribution of the inputs (which differ in training and target domains). Here, we focus on the non-trivial case. We show that, as long as \(f_0\) satisfies the smoothness structure enforced by the regularizer, \(\widehat{f}\) from 3 remains accurate at the target inputs \(\{x_{t,i}\}_{i=1}^{n_t}\). First, we state our assumptions on the loss function \(\cL\) and the regularizer \(\cR_n\).

This is an assumption on the effect of the smoothness structure enforced by the regularizer being in agreement with the regression function \(f_0\).

This is a regularity assumption on the regularizer to ensure the extrapolation map \(y_t:\reals^{n_s}\to\reals^{n_t}\) \[\textstyle y_t^*(v) \triangleq \mathop{\mathrm{arg\,min}}_{t \in \reals^{n_t}}\cR_n(v, t) \label{eq:extrapolation-map}\tag{4}\] is well-behaved. Intuitively, the extrapolation map extrapolates (hence its name) model outputs on the source domain to the target domain in the smoothest possible way. Next, we state our assumptions on the loss function:

Assumption 3 is standard in learning theory, which provides us control over the curvature of the loss function.

We note that the right side of ?? does not depend on the \(y_{i,s}\)’s in the target domain. Intuitively, Theorem 1 guarantees the accuracy of \(\widehat{f}\) on the inputs from the target domain as long as the following conditions hold.

1. The model class \(\cF\) is rich enough to include an \(f\) that is not only accurate on the training domain, but also satisfies the smoothness/invariance conditions enforced by the regularizer. This implies the first term on the right side of ?? is small.

2. The exact relation between inputs and outputs encoded in \(f_0\) satisfies the smoothness structure enforced by the regularizer. This implies the second term on the right side of ?? is small.

If the model is correctly specified (\(f_0\in\cF\)) and the regression function perfectly satisfies the smoothness conditions enforced by the regularizer (\(\cR_n(f_0) = 0\)), then the bias term vanishes. In other words, Theorem 1 is adaptive to correctly specified model classes.

Example: Laplacian regularizer We now show that the graph Laplacian regularizer satisfies Assumption 2. As \(\cR_n(f(X))\) is a quadratic function of \(\bL\), it is immediate that \(n \nabla^2 \cR_n(f(X)) = \bL\). Therefore, the strong convexity and smoothness of \(\cR\) depend on the behavior of the maximum and minimum eigenvalues of \(\bL\). The maximum eigenvalue of \(\bL\) is bounded above for the fixed design, which plays the role of \(L_\cL/2\) in Assumption 2. For the lower bound, we note that we only assume strong convexity with respect to the target samples fixing the source samples. If we divide the whole Laplacian matrix into four blocks, then the value of the regularizer in terms of these blocks will be: \[\textstyle \cR_n(f(X)) = \sum_{i, j \in \{s, t\}}f(X_i)^{\top}\bL_{ij}f(X_j) \,.\] Therefore, the Hessian of \(\cR_n\) with respect to the model outputs in the target domain is \(\bL_{TT}\) whose minimum eigenvalue is bounded away from 0 as long as the graph is connected, i.e., source inputs have a degree of similarity with target inputs. Thus, \(\cR_n\) satisfies Assumption 2. Graph Laplacian regularizer is often used to achieve individual fairness lahoti2019ifair?, kang2020inform?, petersen2021post? and our Theorem 1 shows that it can also be used for domain adaptation. We further verify this empirically in Section 2.4.

2.2 The Inductive Setting↩︎

We now consider the inductive setting. Previously, in Section 2.1, we focused on the accuracy of the fitted model \(\widehat{f}\) on the inputs from the test domain \(\{x_{t,i}\}_{i=1}^{n_t}\). Here we instead consider the expected loss of \(\widehat{f}\) at a new (previously unseen) input point in the target domain. We consider a problem setup similar to that in Section 2.1: the \(n_s\) labeled samples from the source domain are independently drawn from the source distribution \(P\), while the \(n_t\) unlabeled samples from the target domain are independently drawn from (the marginal of) the target distribution \(Q\). We also assume the covariate shift condition 2 . The method remains the same as before: we learn \(\widehat{f}\) from 3 .

The main difference between the inductive and transductive settings is in the population version of the regularizer: In the transductive setting, we are only concerned with the output of the ML model for the inputs in the source and target domains; thereby, the population version of the regularizer remains a function of (the vector of) model outputs on the inputs in the source and target domains. In the inductive setting, we are also concerned with the output of the ML model on previously unseen points; thus, we consider the regularizer as a functional (i.e., a higher order function): \(\cR:\cF\times\cF\to\reals\) (the two arguments corresponds to \(f(X_s)\) and \(f(X_t)\) in the transductive case). For example, the population version of the graph Laplacian regularizer (in the inductive setting) is \[\textstyle \cR(f,g) \triangleq \Ex\big[\frac{1}{2}(f(X_s) - g(X_t))^2K(X_s, X_t)\big],\] where \(X_s\sim P_X\) and \(X_t\sim Q_X\). The population version of 3 in the inductive setting is \[\tilde{f} \triangleq \mathop{\mathrm{arg\,min}}_{f \in \cF} \label{eq:pop95f}\Ex[\cL(Y_s, f(X_s))] + \lambda \cR \left(f, f\right).\tag{6}\]

Now we state the assumptions to extend Theorem 1 to the inductive setting.

Assumptions 4 and 5 are analogues of Assumptions 1 and 2 in the inductive setting. In fact, it is possible to show that Assumptions 4 and 5 imply Assumptions 1 and 2 with high probability by appealing to (uniform) laws of large numbers (see Appendix 8). The following theorem provides a bound on the population estimation error of \(\tilde{f}\) on the target domain:

The bound obtained in Theorem 2 is comparable to ?? : the right side does not depend on the distribution \(Y_Q\mid X_Q\). The second term denotes the aptness of regularizer \(\cR\), i.e., how well it captures the smoothness of \(f_0\) over the domains. Similar to ?? , we note that the bound in Theorem 2 is adaptive to correctly specified model classes.

To wrap up, we compare our theoretical results to other theoretical results on domain adaptation. There is a long line of work started by Ben-David et al. ben-david2010theory? on out-of-distribution accuracy of ML models mansour2009domain?, ganin2016domain?, saito2018maximum?, zhang2019bridging?, zhang2020localized?. Such bounds are usually of the form \[\bbE_{Q}\big[\cL(f(x), f_0(x)\big] \lesssim \bbE_P\big[\cL(f(x), f_0(x)\big] + \text{disc}(P,Q) \label{eq:domain-adaptation-bound}\tag{7}\] for any \(f \in \cF\), where \(\text{disc}(P,Q)\) is a measure of discrepancy between the source and target domains. For example, Zhang et al. zhang2019bridging? show 7 with \[\text{disc}(P,Q) \triangleq \sup\nolimits_{f,f'\in\cF}\left\{\begin{align}&\Ex_Q\big[\cL(f(X), f'(X)\big]- \Ex_P\big[\cL(f(X), f'(X)\big]\end{align}\right\}.\] A key feature of these bounds is that it is possible to evaluate the right side of the bounds with unlabeled samples from the target domain (and labeled samples from the source domain). Compared to our bounds, there are two main differences:

1. Equation 7 applies to any \(f\in\cF\) (while our bound only applies to a specific \(\widetilde{f}\) from 6 ). Although this uniform applicability is practically desirable (because it allows practitioners to evaluate the bound a posteriori to estimate the out-of-distribution accuracy of the trained model), it precludes the bounds from adapting to correct specification of the model class.

2. The uniform applicability of the bound (to any \(f\in\cF\)) also precludes 7 from capturing the effects of the regularizer.

2.3 Extension to Domain Generalization↩︎

In this subsection, we further extend our results to the domain generalization setup, i.e., when we have no observations from the target domain. In the previous domain adaptation setup, when we had access to unlabeled data from the target domain, we used a suitable regularizer to extrapolate the prediction performance from the source domain to the target domain. However, when we do not have unlabeled data from the target domain, we need to alter the regularizer appropriately, so that we have some uniform guarantee over all domains in the vicinity of the source domain. Here is an example of a regularizer that seeks to improve domain generalization: \[\label{eq:gen95reg} \kern-1.8em \cR(f, g) = \left\{ \max\nolimits_{T} \quad \bbE_{X \sim P}\left[\left(f(X) - g(T(X))\right)^2\right] \qquad \textrm{s.t.} \quad \bbE_{X \sim P}\left[\|X - T(X)\|\right] \le {\epsilon}.\\ \right. \kern-1em\tag{8}\] \(T\) here can be thought as an adversarial map that maps \(X\) to an adversarial example \(X' = T(X)\) that maximizes the difference \(f(X) - g(X')\). As we need some uniform guarantees across all domains in the vicinity of the source domain, \(T\) produces the adversarial test domain example. This regularizer is similar to the SenSeI regularizer originally proposed and studied by Yurochkin et al. yurochkin2021sensei? for enforcing individual fairness. In fact, \(\cR(f,f)\) is exactly the (Mongé form) of the SenSeI regularizer. Note that we can further generalize this regularizer by incorporating a general loss function \(\cL\) in the first equation or a general metric \(d\) in the second equation. However, as this does not add anything to the underlying intuition, we confine ourselves to the \(\ell_2\) metric here. Next, we present our theoretical findings with respect to this regularizer. To this end, we define the set of transformations \(\cT_{{\epsilon}} = \{T: \bbE_{x \sim P}\left[\|x - T(x)\|\right] \le {\epsilon}\}\) and the corresponding set of measures \(\cQ_{\epsilon}= \{Q: T \#P = Q, T \in \cT_{\epsilon}\}\). We show that it is possible to generalize the performance of the estimator \(\hat{f}\) obtained in 3 uniformly over the measures in \(\cQ_{\epsilon}\). As mentioned previously, we only work with the quadratic loss function, but our result can be extended to the general loss function. The following theorem establishes a uniform bound on the estimation error of the population function \(\tilde{f}\) obtained from 3 with the regularizer as defined in 8 :

The bound obtained in the above is the same as the one obtained in Theorem 2 (up to constants) and has analogous interpretation: it consists of the minimum training error achieved on \(\cF\) and the smoothness of \(f_0\) quantified in terms of the regularizer. Moreover, the bound holds uniformly over all the domains \(Q \in \cQ_{\epsilon}\), i.e., the performance of the estimator \(\hat{f}\) can be extrapolated to all the domains in \(\cQ_{\epsilon}\), provided that \(\cR(f_0, f_0)\) is small.

2.4 Empirical Results↩︎

We verify our theoretical findings empirically. Our goal is to improve performance under distribution shifts using individual fairness methods. We consider SenSeI yurochkin2021sensei?, Sensitive Subspace Robustness (SenSR) yurochkin2020training?, Counterfactual Logit Pairing (CLP) garg2018counterfactual?, and GLIF petersen2021post?. GLIF, similar to domain adaptation methods, requires unlabeled samples from the target. The other methods only utilize the source data as in the domain generalization scenario. Our theory establishes guarantees on the target domain performance for SenSeI (Section 2.3) and GLIF (Section 2.1).

2.4.0.1 Datasets and Metrics

We experiment with two textual datasets, Toxicity dixon2018measuring? and Bios de2019bias?. In Toxicity, the goal is to identify toxic comments. This dataset has been considered by both the domain generalization community koh2021wilds?, zhai2021doro?, creager2021environment? (under the name Civil Comments) as well as the individual fairness community garg2018counterfactual?, yurochkin2021sensei?, petersen2021post?. The key difference between the two communities are in the comparison metrics. In domain generalization, it is common to consider performance on underrepresented groups (or simply worst group performance). In individual fairness, a common metric is prediction consistency, i.e., a fraction of test samples where predictions remain unchanged under certain modifications to the inputs, which maintain a similarity from the fairness standpoint.

In Toxicity, the group memberships can be defined either with respect to human annotations provided with the dataset, or with respect to the presence of certain identity tokens. Both groupings aim at highlighting comments that refer to identities that are subject to online harassment. To quantify domain generalization, we evaluate average per group true negative (non-toxic) rate, where each group is weighted equally. We choose true negative rate (TNR) because underrepresented groups tend to have a larger fraction of toxic comments in the train data, thus being spuriously associated with toxicity by the model yielding poor TNR. This is similar to how the background is spurious in the popular domain generalization Waterbirds benchmark sagawa2019distributionally?. We weigh each group equally to ensure that performance on underrepresented groups is factored in (a more robust alternative to worst group performance). We consider both groupings, i.e., TNR (Annotations) and TNR (Identity tokens).

In Bios, the task is to predict the occupation of a person from their biography. This dataset has been mostly studied in the fairness literature de2019bias?, romanov2019what?, prost2019debiasing?, yurochkin2021sensei?, but it can also be considered from the domain generalization perspective. Many of the occupations in the dataset exhibit large gender imbalance associated with historical biases, e.g., most nurses are female and most attorneys are male. Thus, gender pronouns and names can introduce spurious relations with the occupation prediction. To quantify this effect from the domain generalization perspective, we report the average of the worst accuracies with respect to the gender for each occupation (Worst per gender). Since both datasets are class-imbalanced, we also report balanced (by class) test accuracy (BA) on source to ensure that in-distribution performance remains reasonable.

2.4.0.2 Results

In Table 1, we compare methods for enforcing individual fairness with an ERM baseline. IF methods require a fair metric that encodes that changes in identity tokens result in similar comments in Toxicity, and changes in gender pronouns and names result in similar biographies in Bios (except for CLP which instead uses this intuition for data augmentation). We obtained the fair metric as in the original studies of the corresponding methods. We can observe that IF methods consistently improve domain generalization metrics supporting our theoretical findings. They also tend to maintain reasonable in-distribution performance, supporting their overall applicability in practical use-cases where both in- and out-of-distribution performance is important. Among the IF methods, SenSeI performs slightly better overall. We refer to Appendix 10 for additional results verifying that the considered methods also achieve IF.

3 Individual Fairness via Domain Adaptation↩︎

In the previous section, we established that it is possible to use IF regularizers for domain adaptation problems provided that the true underlying signal satisfies some smoothness conditions. In this section, we investigate the opposite direction, i.e., whether the techniques employed for DA can be leveraged to enforce IF. Many DA methods aim at finding a representation \(\Phi(X)\) of the input sample \(X\), such that the source and the target distributions of \(\Phi(X)\) are aligned. In other words, the goal is to make it hard to distinguish \(\Phi(X_{S_i})'s\) from \(\Phi(X_{T_i})'s\). For example, Ganin et al. ganin2016domain? proposed the Domain Adversarial Neural Network (DANN) for learning \(\Phi(X)\), such that the discriminator fails to discriminate between \(\Phi(X_S)\) and \(\Phi(X_T)\). Shu et al. shu2018dirtt? assume that the target distribution is clustered with respect to the classes and consequently the optimal classifier should pass through the low density region. To promote this condition, they modify the previous objective ganin2016domain? with additional regularizers to ensure that the final classifier (which is built on top of \(\Phi(X)\)) has low entropy on the target and is also locally Lipschitz. Sun et al. sun2016return? learn a linear transformation of the source distribution (which was later extended to learn non-linear transformations sun2016deep?), such that the first two moments of the transformed representations are the same in source and target distributions. Shen et al. shen2018wasserstein? learn domain invariant representations by minimizing the Wasserstein distance between the distributions of source and target representations induced by \(\Phi(X)\).

A common underlying theme of all of the above methods is to find \(\Phi(X)\) which has a similar distribution on both the source and the target. In this section, we show that learning this domain invariant map indeed enforces individual fairness under suitable choice of domains. We demonstrate this by the following factor model: suppose we want to achieve individual fairness against a binary protected attribute \(Z\) (say sex). We define two domains as two groups corresponding the protected attribute, e.g., the source domain may consist of all the observations corresponding to the males and the target domain may consist of all the observations corresponding to the females. We assume that the covariates follow a factor model structure \(X = AU + bZ + {\epsilon}\) for three independent random variables \((U, Z, {\epsilon})\) where \(U\) denotes the relevant attribute, \(Z\) denotes the protected attributes and \({\epsilon}\) is the noise. Therefore, according to our design:

In the following theorem, we establish that if we estimate some linear transformation \(\Phi \in \reals^{q \times p}\) (with \(q < p, p\) being the ambient dimension of \(X\)) of \(X\) such that \(\Phi X_S\) and \(\Phi X_T\) has same distribution, then \(\Phi b = 0\). Therefore, \(\Phi X\) ignores the direction corresponding to the protected attribute and consequently is an individually fair representation.

This theorem implies any classifier built on top of the linear representation \(\Phi x\) will be individually fair because \(\Phi x = \Phi x'\) for any \(x,x'\) that share relevant attributes \(U\). The proof of the theorem can be found in the appendix. The above theorem constitutes an example of how domain adaptation methods can be adapted to enforce individual fairness when the covariates follow a factor structure.

3.1 Empirical Results↩︎

In this section, our goal is to train individually fair models using methods popularized in the domain adaptation (DA) literature. We experiment with DANN ganin2016domain?, VADA shu2018dirtt?, and a variation of the Wasserstein-based DA (WDA) shen2018wasserstein? discussed in Section 3. We present experimental details in Apx. 10.

3.1.0.1 Datasets and Metrics

We consider the same two datasets as in our domain generalization experiments in Section 2.4. We use prediction consistency (PC) to quantify individual fairness following prior works studying these datasets yurochkin2021sensei?, petersen2021post?. For the Toxicity dataset, we modify identity tokens in the test comments and compute prediction consistency with respect to all 50 identity tokens dixon2018measuring?. A pair of comments that only differ in an identity token, e.g., “gay” vs “straight”, are intuitively similar and should be assigned the same prediction to satisfy individual fairness. For the Bios dataset, we consider prediction consistency with respect to changes in gender pronouns and names. Such changes result in biographies that should be treated similarly.

In these experiments, we have one labeled training dataset, rather than labeled source and unlabeled target datasets typical for DA setting. As shown in Section 3, the key idea behind achieving individual fairness using DA techniques is to split the available train data into source and target domains such that aligning their representations pertains to the fairness goals. To this end, in the Bios dataset we split the train data into all-male and all-female biographies, and the Toxicity dataset we split into a domain with comments containing any of the aforementioned 50 identity tokens and a domain with comments without any identity tokens. The ERM baseline is trained on the complete training dataset.

r.75

3.1.0.2 Results

We summarize the results in Table 2. Among the considered DA methods, WDA achieves best individual fairness improvements in terms of prediction consistency, while maintaining good balanced accuracy (BA). Comparing to a method designed for training individually fair models, SenSeI, prediction consistency of DA methods is worse; however, the subject understanding required to apply them is milder. Individual fairness methods require a problem-specific fair metric, which can be learned from the data, but even then requires user to define, e.g., groups of comparable samples mukherjee2020Two?. The domain adaptation approach requires a fairness-related splitting of the train data. In our experiments, we adopted straightforward data splitting strategies and demonstrated improvements over the baseline. More sophisticated data splitting approaches can help to achieve further individual fairness improvements. We present additional experimental details in Appendix 10.

4 Conclusion↩︎

We showed that algorithms for enforcing individual fairness (IF) can help ML models generalize to new domains and vice versa. From the lens of algorithmic fairness, the results in Section 2 show that enforcing IF can mitigate algorithmic biases caused by covariate shift as long as the regression function satisfies IF. This complements the recent results on mitigating algorithmic biases caused by subpopulation shift with group fairness maity2021does?. On the other hand, compared to existing results on out-of-distribution accuracy of ML models, the results in Section 2 demonstrate the importance of inductive biases in helping models adapt to new domains. One limitation of our analysis is the assumption of covariate shift. We have relaxed this assumption in Appendix 9 (see Theorem 5), where we establish results for more general distribution shifts (e.g. label shift, posterior drift etc.).

In Section 3, we showed a probabilistic connection between domain adaptation (DA) and IF. As we saw, it is possible to enforce IF by aligning the distributions of the features under a factor model. This factor model is implicit in some prior works on algorithmic fairness bolukbasi2016man?, mukherjee2020Two?, but we are not aware of any results that show it is possible to enforce IF using DA techniques.

Recent DA methods typically leverage many inductive biases through data augmentations and regularizers, and our results suggest that IF can also be leveraged. For example, utilizing annotations to identify similar images ruan2021optimal? can be used to learn a “fair” metric for an IF-based regularizer. We also note that our approach is similar to that of consistency regularization for DA (e.g. see sohn2020fixmatch?, bachman2014learning?, laine2016temporal?, sajjadi2016regularization?) where the key idea is to ensure that similar samples should yield similar labels. We show that regularizer for enforcing IF can also be used as a consistency regularizer for extrapolation on the test domain. Finally, from the perspective of achieving IF, a study of different strategies for data partitioning in combination with modern DA best practices is an interesting direction for future work.

5 Appendix↩︎

5.1 Proof of Theorem 1↩︎

For the proof of this theorem, we need few auxiliary lemmas, which we state below:

The proof of Lemma 1 can be found in Section 6.1 and the proof of Lemma 2 can be found in Section 6.2. For the rest of the proof, we introduce some notations for the ease of presentation: for any two vector \(v_1, v_2\) of the same dimension we use \(\cL(v_1, v_2)\) or its partial derivatives to denote the coordinate wise sum, i.e., \(\sum_{j} \cL(v_{1, j}, v_{2, j})\). From the strong smoothness condition on \(\cL\) we have: \[\begin{align} \label{eq:l95ss} \frac{1}{n_t}\cL\left(\hat{f}(X_t), f_0(X_t)\right) & \le \frac{1}{n_t}\cL\left(y_t^*(\hat{f}(X_s)), f_0(X_t)\right) \notag \\ & \qquad + \frac{1}{n_t}\left\langle \hat{f}(X_t) - y_t^*(\hat{f}(X_s)), \partial_1 \cL\left(y_t^*(\hat{f}(X_s)), f_0(X_t)\right)\right\rangle \notag \\ & \qquad \qquad + \frac{L_\cL}{2 n_t}\left\| \hat{f}(X_t) - y_t^*(\hat{f}(X_s))\right\|_2^2 \end{align}\tag{11}\] We can further bound the first term on the RHS of the above equation as follows: \[\begin{align} \label{eq:l95ss952} \frac{1}{n_t}\cL\left(y_t^*(\hat{f}(X_s)), f_0(X_t)\right) & \le \frac{1}{n_t}\cL\left(y_t^*(\hat{f}(X_s)), y_t^*(f_0(X_s))\right) \notag \\ & \qquad + \frac{1}{n_t} \left \langle f_0(X_t) - y_t^*(f_0(X_s)), \partial_2\cL\left(y_t^*(\hat{f}(X_s)), y_t^*(f_0(X_s))\right)\right \rangle \notag \\ & \qquad \qquad + \frac{L_\cL}{2 n_t} \left\|f_0(X_t) - y_t^*(f_0(X_s)) \right\|^2 \end{align}\tag{12}\] Combining the bounds on Equations 11 and 12 we obtain: \[\begin{align} \label{eq:l95ss95comb} \frac{1}{n_t}\cL\left(\hat{f}(X_t), f_0(X_t)\right) & \le \underbrace{\frac{1}{n_t}\cL\left(y_t^*(\hat{f}(X_s)), y_t^*(f_0(X_s))\right)}_{T_1} \notag \\ & \qquad + \underbrace{\frac{1}{n_t} \left \langle f_0(X_t) - y_t^*(f_0(X_s)), \partial_2\cL\left(y_t^*(\hat{f}(X_s)), y_t^*(f_0(X_s))\right)\right \rangle}_{T_2} \notag \\ & \qquad + \underbrace{\frac{1}{n_t}\left\langle \hat{f}(X_t) - y_t^*(\hat{f}(X_s)), \partial_1 \cL\left(y_t^*(\hat{f}(X_s)), f_0(X_t)\right)\right\rangle}_{T_3} \notag \\ & \qquad \qquad \qquad \qquad + \underbrace{ \frac{L_\cL}{2 n_t} \left\|f_0(X_t) - y_t^*(f_0(X_s)) \right\|^2}_{T_4} \notag \\ & \qquad \qquad \qquad \qquad + \underbrace{ \frac{L_\cL}{2 n_t}\left\| \hat{f}(X_t) - y_t^*(\hat{f}(X_s))\right\|^2}_{T_5} \end{align}\tag{13}\] The term \(T_4, T_5\) can be bounded directly by Lemma 1 as: \[\begin{align} \tag{14} T_4 & \le \frac{L_\cL \;n}{\mu_\cR \; n_t}\cR\left(f_0(X_s), f_0(X_t)\right) \\ \tag{15} T_5 & \le \frac{L_\cL \;n}{\mu_\cR \; n_t}\cR\left(\hat{f}(X_s), \hat{f}(X_t)\right) \end{align}\] To bound \(T_2\), using \(ab \le (a^2 + b^2)/2\) we have: \[\begin{align} T_2 &= \frac{1}{n_t} \left \langle f_0(X_t) - y_t^*(f_0(X_s)), \partial_2\cL\left(y_t^*(\hat{f}(X_s)), y_t^*(f_0(X_s))\right)\right \rangle \\ & \le \frac{1}{n_t}\left\|f_0(X_t) - y_t^*(f_0(X_s))\right\|^2 + \frac{1}{n_t}\left\|\partial_2\cL\left(y_t^*(\hat{f}(X_s)), y_t^*(f_0(X_s))\right)\right\|^2 \\ & \le \frac{2n}{\mu_\cR \;n_t}\cR\left(f_0(X_s), f_0(X_t)\right) + \frac{L_\cL^2}{4n_t} \left\|y_t^*(\hat{f}(X_s)) - y_t^*(f_0(X_s))\right\|^2[\text{Lemma }\ref{lem:sc95L95l295bound}] \\ & \le \frac{2n}{\mu_\cR \;n_t}\cR\left(f_0(X_s), f_0(X_t)\right) + \frac{L_\cL^2 L_\cR^2}{4\mu^2_\cR \;n_t} \left\|\hat{f}(X_s) - f_0(X_s)\right\|^2[\text{Lemma }\ref{lem:minimizer}] \\ & \le \frac{2n}{\mu_\cR \;n_t}\cR\left(f_0(X_s), f_0(X_t)\right) + \frac{L_\cL^2 L_\cR^2}{2\mu^2_\cR \mu_\cL} \times \frac{n_s}{n_t} \times \frac{1}{n_s}\cL\left(\hat{f}(X_s), f_0(X_s)\right)[\text{Lemma }\ref{lem:sc95L95l295bound}] \\\\ \end{align}\] The bound on \(T_3\) follows from a similar line of argument: \[\begin{align} T_3 &= \frac{1}{n_t}\left\langle \hat{f}(X_t) - y_t^*(\hat{f}(X_s)), \partial_1 \cL\left(y_t^*(\hat{f}(X_s)), f_0(X_t)\right)\right\rangle \\ & \le \frac{1}{n_t}\left\|\hat{f}(X_t) - y_t^*(\hat{f}(X_s))\right\|^2 + \frac{1}{n_t}\left\|\partial_1 \cL\left(y_t^*(\hat{f}(X_s)), f_0(X_t)\right)\right\|^2 \\ & \le \frac{2n}{\mu_\cR \;n_t}\cR\left(\hat{f}(X_s), \hat{f}(X_t)\right) + \frac{L_\cL^2}{4 n_t} \left\|y_t^*(\hat{f}(X_s)) - f_0(X_t)\right\|^2[\text{Lemma }\ref{lem:sc95L95l295bound}] \\ & \le \frac{2n}{\mu_\cR \;n_t}\cR\left(\hat{f}(X_s), \hat{f}(X_t)\right) + \frac{L_\cL^2}{2 n_t} \left\|y_t^*(\hat{f}(X_s)) - y_t^*(f_0(X_s))\right\|^2 + \frac{L_\cL^2}{2 n_t}\left\|y_t^*(f_0(X_s)) - f_0(X_t)\right\|^2 \\ & \le \frac{2n}{\mu_\cR \;n_t}\cR\left(\hat{f}(X_s), \hat{f}(X_t)\right) + \frac{L_\cL^2 \;n}{\mu_\cR \;n_t} \cR\left(f_0(X_s), f_0(X_t)\right) + \\ & \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad + \frac{L_\cL^2 L_\cR^2}{\mu^2_\cR \mu_\cL} \times \frac{n_s}{n_t} \times \frac{1}{n_s}\cL\left(\hat{f}(X_s), f_0(X_s)\right)[\text{Lemma }\ref{lem:sc95L95l295bound}] \end{align}\] Finally to bound \(T_1\) we use again Assumption 3, i.e., strong convexity and strong smoothness of \(\cL\) as follows: \[\begin{align} T_1 & = \frac{1}{n_t}\cL\left(y_t^*(\hat{f}(X_s)), y_t^*(f_0(X_s))\right) \\ & \le \frac{L_\cL}{2n_t}\left\|y_t^*(\hat{f}(X_s)) - y_t^*(f_0(X_s))\right\|_2^2 \\ & \le \frac{L_\cL L^2_\cR}{2 \mu^2_\cR \;n_t}\left\|\hat{f}(X_s) - f_0(X_s)\right\|_2^2 \\ & \le \frac{L_\cL L^2_\cR}{2 \mu^2_\cR} \times \frac{n_s}{n_t} \times \frac{1}{n_s}\cL\left(\hat{f}(X_s), f_0(X_s)\right) \end{align}\] Suppose \(\rho_n = n_s/n_t\). Then we have \(n/n_t = 1 + \rho_n\). Using this notation and combining the bound on all \(\{T_i\}_{i=1}^5\), we obtain: \[\begin{align} \frac{1}{n_t}\cL\left(\hat{f}(X_t), f_0(X_t)\right) & \le \frac{L_\cL L_\cR^2\left(\mu_\cL + 3L_\cL \right)}{2\mu_\cR^2 \mu_\cL}\rho_n \;\frac{1}{n_s}\cL\left(\hat{f}(\bX_s), f_0(\bX_s)\right)\notag \\ & \qquad \qquad + \frac{2+L_\cL}{\mu_\cR}(1+\rho_n) \cR(\hat{f}(\bX)) + \frac{2 + L_\cL + L^2_\cL}{\mu_\cR}(1+\rho_n)\cR(f_0(\bX)) \notag \\ \label{eq:bound95first}& \le \alpha_n \left[\frac{1}{n_s}\cL\left(\hat{f}(\bX_s), f_0(\bX_s)\right) + \lambda \cR(\hat{f}(\bX))\right] + \beta_n \cR(f_0(\bX)) \,, \end{align}\tag{16}\] with the values of \(\alpha_n\) and \(\beta_n\) being: \[\begin{align} \tag{17} \alpha_n & = \max\left\{\frac{L_\cL L_\cR^2\left(\mu_\cL + 3L_\cL \right)}{2\mu_\cR^2 \mu_\cL}\rho_n, \; \frac{2+L_\cL}{\lambda \mu_\cR}(1+\rho_n)\right\} \,, \\ \tag{18} \beta_n & = \frac{2 + L_\cL + L^2_\cL}{\mu_\cR}(1+\rho_n) \,. \end{align}\] This completes the proof.

5.2 Proof of Theorem 2↩︎

First, note that, from Assumption 3 we have: \[\begin{align} & \bbE_Q\left[\cL(\tilde{f}(x), f_0(x))\right] \notag \\ & \le \cancelto{0}{\bbE_Q\left[\cL(f_0(x)), f_0(x))\right]} + \cancelto{0}{\bbE\left[(\tilde{f}(x) - f_0(x)))\partial_1 \cL(f_0(x), f_0(x))\right]} + \frac{\cL_\cL}{2}\left\|\tilde{f}(x) - f_0(x)\right\|_Q^2 \notag \\ \label{eq:ind95loss95upper}& = \frac{L_\cL}{2}\left\|\hat{f}(x) - f_0(x)\right\|_Q^2 \,. \end{align}\tag{19}\] and \[\begin{align} & \bbE_P\left[\cL(\tilde{f}(x), f_0(x))\right] \notag \\ & \ge \cancelto{0}{\bbE_P\left[\cL(f_0(x)), f_0(x))\right]} + \cancelto{0}{\bbE_P\left[(\tilde{f}(x) - f_0(x)))\partial_1 \cL(f_0(x), f_0(x))\right]} + \frac{\mu_\cL}{2}\left\|\tilde{f}(x) - f_0(x)\right\|_P^2 \notag \\ \label{eq:ind95loss95lower}& = \frac{\mu_\cL}{2}\left\|\hat{f}(x) - f_0(x)\right\|_P^2 \,. \end{align}\tag{20}\] Therefore, it is enough to bound \(\|\hat{f}(x) - f_0(x)\|_Q^2\). As per Assumption 5, \(\cR\) is strongly convex with respect to its second coordinate, i.e., \[\cR(f, g) \ge \cR(f, \tilde{g}) + \partial_2 \cR((f, g); g - \tilde{g}) + \frac{\mu_\cR}{2}\left\|g - \tilde{g}\right\|_Q^2 \,.\] We now define an operator \(M\) along the line of \(y_t^*\) as \(M(f) = \mathop{\mathrm{arg\,min}}_{g}\cR(f, g)\). As \(M(f)\) is the minimizer over of the second coordinate, we have \(\partial_2 R(f, M(f)) = 0\) and consequently from the strong convexity of \(R\) we have: \[\cR(f, f) \ge \cR(f, M(f)) + \frac{\mu_\cR}{2}\left\| f - M(f)\right\|_Q^2 \,.\] The above inequality implies: \[\left\| f - M(f)\right\|_Q^2 \le \frac{2}{\mu_L}\left[\cR(f, f) - \cR(f, M(f))\right] \le \frac{2}{\mu_L}\cR(f, f) \,.\] which will be used later in our proof.

\(M\) is Lipschitz: By definition of \(M\) we have \(\partial_2 \cR(f, M(f)) = 0\), which further implies for any two functions \(f_1, f_2\): \[\begin{align} 0 & = \partial_2 \cR((f_1, M(f_1)); (M(f_1) - M(f_2))) - \partial_2 \cR((f_2, M(f_2)); (M(f_1) - M(f_2))) \\ & = \partial_2 \cR((f_1, M(f_1)); (M(f_1) - M(f_2))) - \partial_2 \cR((f_1, M(f_2)); (M(f_1) - M(f_2))) \\ & \qquad \qquad + \partial_2 \cR((f_1, M(f_2)); (M(f_1) - M(f_2))) - \partial_2 \cR((f_2, M(f_2)); (M(f_1) - M(f_2))) \end{align}\] Changing side we obtain: \[\begin{align} & \partial_2 \cR((f_2, M(f_2)); (M(f_1) - M(f_2))) - \partial_2 \cR((f_1, M(f_2)); (M(f_1) - M(f_2))) \notag \\ \qquad \qquad & \qquad \qquad = \partial_2 \cR((f_1, M(f_1)); (M(f_1) - M(f_2))) - \partial_2 \cR((f_1, M(f_2)); (M(f_1) - M(f_2))) \notag \\ \label{eq:lb95pop} & \qquad \qquad \ge \mu_\cR \left\|M(f_1) - M(f_2)\right\|^2_Q \end{align}\tag{21}\] where the last inequality follows from the strong convexity of \(\cR\) (Assumption 5). Furthermore, we have: \[\begin{align} & \partial_2 \cR((f_2, M(f_2)); (M(f_1) - M(f_2))) - \partial_2 \cR((f_1, M(f_2)); (M(f_1) - M(f_2))) \notag \\ \label{eq:ub95pop} & \qquad \qquad \le L_\cR \left\|f_1 - f_2\right\|_P \left\|M(f_1) - M(f_2)\right\|_Q \,. \end{align}\tag{22}\] This follows from the second part of Assumption 5. Combining Equation 21 and 22 , we conclude: \[\left\|M(f_1) - M(f_2)\right\|_Q \le \frac{L_\cR}{\mu_\cR} \left\|f_1 - f_2\right\|_P \,.\] We now return to the main proof: \[\begin{align} \left\|\tilde{f}_Q - f_0\right\|_Q^2 & \le \left\|\tilde{f}_Q - M(\tilde{f}_Q)\right\|_Q^2 + \left\|M(\tilde{f}_Q) - M(f_0)\right\|_Q^2 + \left\|f_0 - M(f_0) \right\|_Q^2 \\ & \le \frac{2}{\mu_\cR}\left(\cR(f_0) + \cR(\tilde{f}_Q)\right) + \frac{L_\cR}{\mu_\cR}\left\|\tilde{f}_Q - f_0\right\|^2_P \\ & := C_0 \left[\left\|\tilde{f}_Q - f_0\right\|^2_P + \lambda \cR(\tilde{f}_Q)\right] + C_2 \cR(f_0) \\ & \le C_1 \left[ \bbE_P\left[\cL(\tilde{f}(x), f_0(x))\right] + \lambda \cR(\tilde{f}_Q)\right] + C_2 \cR(f_0) \end{align}\] where the first term on the right hand side is the minimum training error (population version, i.e., in presence of infinite sample) and the second term quantifies the smoothness of \(f_0\) in terms of the regularizer \(R\). The last inequality follows from the strong convexity of the loss function (20 ).

5.3 Proof of Theorem 3↩︎

In this section, we prove Theorem 3. Fix \(Q \in \cQ_{\epsilon}\). Then there exists some \(T \equiv T(Q) \in \cT_{\epsilon}\) such that \(T \# P = Q\). Define an operator \(M_T\) as: \[M_T(f) = \mathop{\mathrm{arg\,min}}_g \cR_T(f, g)\] where \(\cR_T(f, g) = \bbE_{x \sim P}\left[\left(f(x) - g(T(x))\right)^2\right]\). The proof of the strong convexity of \(R_T\) with respect to its second coordinate is straightforward as we have the following double Gateaux derivative: \[\partial_2^2 \cR((f, g): h_1, h_2) = 2\bbE_{x \sim P}\left[h_1(T(x))h_2(T(x))\right] \,.\] Fix \(f \in \cF\) and define \(\Delta = f \circ T - M_T(f) \circ T\). A two step Taylor expansion yields: \[\begin{align} \cR_T(f, f) & = \cR_T(f, M_T(f)) + \cancelto{0}{\partial_2 \cR_T((f, M_T(f)); \Delta)} + \frac{1}{2} \partial_2 \cR_T((f, f^*); \Delta, \Delta) \\ & = \cR_T(f, M_T(f)) + \bbE[\Delta^2] \\ & = \cR_T(f, M_T(f)) + \left\|f - M_T(f)\right\|^2_Q \,. \end{align}\] where the derivative is canceled because \(M_T(f)\) is the minimizer. Therefore, we have: \[\label{eq:pop95bound95reg} \left\|f - M_T(f)\right\|^2_Q = \cR_T(f, f) - \cR_T(f, M_T(f)) \le \cR_T(f, f)\,.\tag{23}\] We use the above bound in our subsequent calculation: \[\begin{align} \left\|\tilde{f} - f_0\right\|^2_Q \notag & \le 4\left[ \left\|\tilde{f} - M_T(\tilde{f})\right\|^2_Q + \left\|M_T(\tilde{f}) - M_T(f_0)\right\|^2_Q + \left\|f_0 - M_T(f_0)\right\|^2_Q \right] \notag \\ \label{eq:T95bound951}& \le 4\left[ \cR_T(\tilde{f}, \tilde{f}) + \left\|M_T(\tilde{f}) - M_T(f_0)\right\|^2_Q + \cR_T(f_0, f_0) \right][\text{From }\eqref{eq:pop95bound95reg}] \end{align}\tag{24}\] We now bound the second term of the RHS of the above equation. Following the similar calculation as in 21 and 22 we have for any function \(f_1, f_2\): \[\left\|M(f_1) - M(f_2)\right\|_Q \le \left\|f_1 - f_2\right\|_P \,.\] In particular for \(f_1 = \tilde{f}\) and \(f_2 = f_0\) we have: \[\label{eq:T95bound952} \left\|M(\tilde{f}) - M(f_0)\right\|_Q \le \left\|\tilde{f} - f_0\right\|_P \,.\tag{25}\] Combining the bound in 24 and 25 we conclude that for any \(Q \in \bbQ_{\epsilon}\): \[\left\|\tilde{f} - f_0\right\|_Q^2 \le 4\left[R_T(\tilde{f}, \tilde{f}) + R_T(f_0, f_0) +\left\|\tilde{f} - f_0\right\|_P^2\right]\] Taking the supremum with respect to \(Q\) on both sides, we conclude the proof of the theorem.

5.4 Proof of Theorem 4↩︎

The proof follows from analyzing the characteristic function of \(X_s\) and \(X_t\). Note that by definition: \[\begin{align} \phi_{\Phi X_s}(t) & = \bbE\left[e^{it^{\top}\Phi X_s}\right] \\ & = \bbE\left[e^{it^{\top}\left(\Phi AU + \Phi b + \Phi {\epsilon}\right)}\right] \\ & = \phi_U(A^{\top}\Phi^{\top}t) \;\phi_{\epsilon}(\Phi^{\top}t) \; e^{it^{\top}\Phi b} \end{align}\] Similarly, for \(X_t\) we have: \[\phi_{\Psi X_t}(t) = \bbE\left[e^{it^{\top}\left(\Phi AU + \Phi {\epsilon}\right)}\right] = \phi_U(A^{\top}\Phi^{\top}t) \; \phi_{\epsilon}(\Phi^{\top}t) = \phi_{\Phi X_s}(t) \;e^{it^{\top}\Phi b} \,.\] Therefore, if \(\Phi X_s \overset{\mathscr{L}}{=}\Phi X_t\), \(\phi_{\Psi X_t}(t) = \phi_{\Phi X_s}(t)\) for all \(t\), which further implies \(e^{it^{\top}\Phi b} = 1\) for all \(t\), which implies \(\Phi b = 0\). This completes the proof.

6 Proof of Auxiliary Lemmas↩︎

6.1 Proof of Lemma 1↩︎

The proof of the second part of the above lemma follows directly from the strong convexity of \(\cR_n\) with respect to the second coordinate, as the strong convexity assumption yields: \[\cR(v_s, v_t) \ge \cR(v_s, y_t^*(v_s)) + \left\langle v_t - y_t^*(v_s), \partial_t \cR(v_s, y_t^*(v_s))\right\rangle + \frac{\mu_\cR}{2n}\left\|v_t - y_t^*(v_s) \right\|^2\,.\] The second term of the RHS of the above equation is \(0\) as \(\partial_t \cR(v_s, y_t^*(v_s)) = 0\) (as the derivative of a smooth function is \(0\) at minima). Therefore, changing sides of the terms, we conclude: \[\left\|v_s - y_t^*(v_s)\right\|^2 \le \frac{2 n}{\mu_\cR}\left(\cR(v_s, v_t) - \cR(v_s, y_t^*(v_s))\right) \le \frac{2 n}{\mu_\cR} \cR(v_s, v_t)\] where the last inequality follows from the non-negativity of \(\cR_n\). This completes the proof of the second part of the lemma.

For the first part of the lemma, first note that we have : \[\left \langle y_t^*(v_2) - y_t^*(v_1), \partial_t \cR_n(v_1, y_t^*(v_1)) - \partial_t \cR_n(v_2, y_t^*(v_2))\right \rangle = 0\] as \(\partial_t \cR_n(v_1, y_t^*(v_1)) = \partial_t \cR_n(v_2, y_t^*(v_2)) = 0\) (derivative is 0 at minima). Adding and subtracting \(\partial_t \cR_n(v_1, y_t^*(v_2))\) from the above equation yields: \[\begin{align} & \left \langle y_t^*(v_2) - y_t^*(v_1), \partial_t \cR_n(v_1, y_t^*(v_1)) - \partial_t \cR_n(v_1, y_t^*(v_2)) \right. \\ & \qquad \qquad \qquad \qquad \qquad \qquad \left. + \partial_t \cR_n(v_1, y_t^*(v_2)) - \partial_t \cR_n(v_2, y_t^*(v_2))\right \rangle = 0 \end{align}\] Changing sides, we have: \[\begin{align} & \left \langle y_t^*(v_2) - y_t^*(v_1), \partial_t \cR_n(v_1, y_t^*(v_2)) - \partial_t \cR_n(v_2, y_t^*(v_2))\right \rangle \notag \\ & \qquad \qquad \qquad \ge \left \langle y_t^*(v_2) - y_t^*(v_1), \partial_t \cR_n(v_1, y_t^*(v_2)) - \partial_t \cR_n(v_1, y_t^*(v_1)) \right \rangle \notag \\ \label{eq:lower95bound} & \qquad \qquad \qquad \ge \frac{\mu_\cR}{2 n}\left\| y_t^*(v_2) - y_t^*(v_1)\right\|^2 \,. \end{align}\tag{26}\] On the other hand, a simple application of the Cauchy-Schwarz inequality yields: \[\begin{align} & \left \langle y_t^*(v_2) - y_t^*(v_1), \partial_t \cR_n(v_1, y_t^*(v_2)) - \partial_t \cR_n(v_2, y_t^*(v_2))\right \rangle \notag \\ & \qquad \qquad \qquad \le \left\| y_t^*(v_2) - y_t^*(v_1)\right\| \left\|\partial_t \cR_n(v_1, y_t^*(v_2)) - \partial_t \cR_n(v_2, y_t^*(v_2)) \right \| \notag \\ \label{eq:upper95bound} & \qquad \qquad \qquad \le \frac{L_\cR}{2n} \left\| y_t^*(v_2) - y_t^*(v_1)\right\|\left\|v_1 - v_2\right\| \,. \end{align}\tag{27}\] Combining the bounds of Equation 26 and 27 , we have: \[\left\| y_t^*(v_2) - y_t^*(v_1)\right\| \le \frac{L_\cR }{\mu_\cR}\left\|v_1 - v_2\right\| \,,\] which completes the proof.

6.2 Proof of Lemma 2↩︎

The proof follows directly from the following properties of the \(\cL\):

1. \(\cL(f_0(X_s), f_0(X_s)) = 0\).

2. \(\partial_1\cL(f_0(X_s), f_0(X_s)) = \partial_2\cL(f_0(X_s), f_0(X_s)) = 0\)

3. \(\cL\) is strongly convex.

From strong convexity of \(\cL\) we have: \[\begin{align} \cL\left(\hat{f}(X_s), f_0(X_s)\right) & \ge \cL\left(f_0(X_s), f_0(X_s)\right) \\ & \qquad + \left\langle \hat{f}(X_s) - f_0(X_s), \partial_1 \cL\left(f_0(X_s), f_0(X_s)\right)\right \rangle \\ & \qquad \qquad \qquad \qquad + \frac{\mu_\cL}{2} \left\|\hat{f}(X_s) - f_0(X_s)\right\|^2 \end{align}\] The first and second term on the RHS will be 0 by the first and second properties of \(\cL\) mentioned above. Therefore, we have: \[\cL\left(\hat{f}(X_s), f_0(X_s)\right) \ge \frac{\mu_\cL}{2} \left\|\hat{f}(X_s) - f_0(X_s)\right\|^2\] which completes the proof.

7 Similarity Kernel-based Regularizer↩︎

A similarity kernel-based regularizer \(\cR\) is defined as: \[\cR(f, g) = \bbE_{\substack{X \sim P \\ X' \sim Q}}\left[(f(X) - g(X'))^2K(X, X')\right]\] where \(K\) is the kernel of similarity. In particular, if an \(x\) from the source domain is similar to an \(x'\) in the target domain in the sense that \(f_0(x) \approx f_0(x')\), then we expect the value of \(K(x, x')\) to be large. In this section, we show that under some mild regularity condition on \(K\), this regularizer satisfies Assumption 2.

Gateaux derivatives of \(\cR(f, g)\): The first order Gateaux derivative of \(\cR\) in the direction of a function \(h\) is defined as: \[\begin{align} \partial_2 \cR((f, g); h) & = \lim_{t \downarrow 0} \frac{\cR(f, g+th) - \cR(f, g)}{t} \\ & = 2\bbE_{\substack{X \sim P \\ X' \sim Q}}\left[(g(X') - f(X))h(X') K(X, X')\right] \end{align}\] Similarly, the second order Gateaux derivative at direction \((h_1, h_2)\) is defined as: \[\begin{align} \partial_2^2 \cR((f, g); h_1, h_2) & = \lim_{t \downarrow 0} \frac{\partial_2 \cR((f, g+th_2); h_1) - \partial_2 \cR((f, g); h_1)}{t} \\ & = 2\bbE_{\substack{X \sim P \\ X' \sim Q}}\left[h_1(X')h_2(X') K_Q( X')\right] \end{align}\] where \(K_Q(X') = \bbE_{X \sim P}[K(X, X')]\). Therefore, the strong convexity follows from Assumption 6.
We next show that \(\cR\) also satisfies the second condition of Assumption 5. Towards that direction: \[\begin{align} & \partial_2 R((f_2, M(f_2)); (M(f_1) - M(f_2))) - \partial_2 R((f_1, M(f_2)); (M(f_1) - M(f_2))) \notag \\ \notag \\ & \qquad \qquad = 2\bbE_{\substack{X \sim P \notag \\ X' \sim Q}}\left[(f_1(X) - f_2(X))(M(f_1)(X') - M(f_2)(X')) K(X, X')\right] \notag \\ \label{rugcqiht} & \qquad \qquad \le K_{\max} \left\|f_1 - f_2\right\|_P \left\|M(f_1) - M(f_2)\right\|_Q \,. \end{align}\tag{28}\] This concludes that the similarity kernel-based population regularizer \(\cR\) satisfies Assumption 5 under Assumption 6 on the kernel function.

8 Population and Sample Version of the Regularizer↩︎

In this section, we show that under a fairly general condition, if \(\cR_n\) (the sample version of the regularization) satisfies Assumptions 1 and 2 and \(\cR\) is the asymptotic limit of \(\cR_n\), i.e., \(\cR_n \overset{a.s.}{\to} \cR\) as \(n_s, n_t \to \infty\), then \(\cR\) will satisfy Assumption 4 and 5. Towards that if \(\cR_n\) satisfies Assumption 1 for all \(n\), then taking the limit \(n \to \infty\), it is immediate that \(\cR\) satisfies Assumption 4.

For the other assumption, suppose \(\cR_n\) satisfies the first part of Assumption 2, i.e., it is strongly convex with respect to its second coordinates (the coordinates corresponding to the target samples), then again, simply taking the limit \(n \to \infty\), we conclude that \(\cR\) is also strongly convex with \(\mu_\cR = \liminf_{n \to \infty} \mu_{\cR_n}\) (as long as \(\mu_\cR > 0\)). By similar argument, the second part of Assumption 5 is also satisfied if \(\cR_n\) satisfies the strong smoothness assumption and \(\cL_{\cR_n}\) does not diverge to infinity.

9 Bound for Non-Covariate Shift↩︎

In this section, we extend the result of Theorem 2 to the setup when the mean function \(f_0\) is different on source and target domain. More precisely, we assume the following data generative process: \[\label{eq:dgp95general} y_s = f_s(x_s) + {\epsilon}_s, \;\;y_t = f_t(x_t) + {\epsilon}_t \,.\tag{29}\] The following theorem extends the bounds obtained in Theorem 2 for the estimator obtained via 3 :

10 Experimental Details↩︎

In Table 3 we compare prediction consistency yurochkin2020training?, yurochkin2021sensei? of the methods compared in Table 1 of the main text to verify that they also achieve individual fairness as intended.

We summarize some additional details regarding the implementation of domain adaptation methods in the experiments in Section 3.1.

• Since the target domains are labeled (they consist of labeled samples from the train data), we also add a loss term to the objective corresponding to the target domain performance when training the domain adaptation methods. Recall that the main mechanisms for achieving individual fairness are the representation alignment regularizers, thus adding loss in the target domain is simply a way to utilize the available labels to improve performance.

• For DANN, we use a ReLU-activated two-layer base model with 2000 hidden neurons and 768 output neurons. Further, we use a ReLU-activated two-layer base model with 100 hidden neurons and one logistically activated neuron as the discriminator. As the prediction head, we use a ReLU-activated two-layer model with 2000 hidden neurons.

• For VADA, we use the same models as for DANN, and the primary difference is the additional virtual adversarial training (VAT) loss.

• For WDA, we replaced the Wasserstein distance utilized by Shen et al. shen2018wasserstein? with the Sinkhorn divergence genevay2018learning?. The Sinkhorn divergence is a computationally more efficient analogue of the Wasserstein distance regularizer. We used the Geomloss package feydy2019interpolating? in our code.

11 Background on Domain Adaptation and Algorithmic Fairness↩︎

Domain adaptation generally refers to the problem of semi-supervised learning under distribution shift. More precisely, in the semi-supervised setting the learner is given a labeled dataset \(\{(X_i,Y_i)\}_{i=1}^n\) and an unlabeled dataset \(\{X_i\}_{i=n+1}^m\). In domain adaptation, we typically assume the labeled samples and unlabeled samples are drawn from a source \(P\) and target distribution \(Q\) that are similar but non-identical. The goal of the learner is to find a prediction rule \(f:\cX\to\cY\) such that \(\Ex_Q\big[\ell(f(X),Y)\big]\) is small. This goal is impossible without additional assumptions restricting the differences between \(P\) and \(Q\). In light of the available data, a natural assumption is covariate shift: \(\Ex_P\big[Y\mid X=x\big] = \Ex_Q\big[Y\mid X=x\big]\). The standard approach to this problem is importance weighing sugiyama2007covariate?. It is based on the observation that \[\Ex_Q\big[\ell(f(X),Y))\big] = \Ex_P\big[w(X)\ell(f(X),Y)\big]], \label{eq:importance-weighing-covariate-shift}\tag{34}\] where \(w(x)\triangleq\frac{dQ_X}{dP_X}(x)\) is the likelihood ratio between the marginal distribution of inputs in the target and that in the source domains. It is possible to estimate \(w\) from the inputs in the labeled and unlabeled datasets sugiyama2012density?, which allows the learner to estimate the right side of 34 .

It is known that many instances of algorithmic bias are caused by distribution shift between the training data and real-world data encountered by the model during deployment. Broadly speaking, research has identified two types of algorithmic bias caused by distributional shifts obermeyer2021algorithmic?:

1. the model is trained to predict the wrong target;

2. the model is trained to predict the correct target, but its predictions are inaccurate for demographic groups that are underrepresented in the training data.

In statistical terms, the first type of algorithmic bias is caused by posterior drift between the training and real-world data. This leads to a mismatch between the model’s predictions and the correct values of the target in the real world. The second type of algorithmic biases arises when ML models are trained or evaluated in non-diverse training data, so the models perform poorly on underserved groups. In statistical terms, this type of algorithmic bias is caused by covariate shift between the training and real-world data.

Several prior works study the effects of enforcing algorithmic fairness under distribution shift. Blum et al. blum2019recovering? consider the effects of enforcing demographic parity and equalized odds under two forms of distribution shift they call under-representation bias and labeling bias. Maity et al. maity2021does? consider the effects of enforcing group fairness in a domain generalization setting when there is subpopulation shift between the source and target domains. Another line of work considers how fairness guarantees (instead of performance guarantees) transfer under distribution shift schumann2019transfer?, schrouff2022maintaining?, chen2022fairness?. Singh et al. singh2021fairness? and Rezaei et al. rezaei2021robust? consider both transferability of performance and fairness guarantees under covariate shift.

---

1. This setting corresponds to a domain shift assumption common in the DA literature.↩︎