# fairness_through_matching__2291b52b.pdf

Published in Transactions on Machine Learning Research (12/2024)

Fairness Through Matching

Kunwoong Kim kwkim.online@gmail.com Department of Statistics Seoul National University

Insung Kong insung.kong@utwente.nl Department of Applied Mathematics University of Twente

Jongjin Lee jjlee_.lee@samsung.com Samsung Research

Minwoo Chae mchae@postech.ac.kr Department of Industrial and Management Engineering Pohang University of Science and Technology (POSTECH)

Sangchul Park parks@snu.ac.kr School of Law Seoul National University

Yongdai Kim ydkim0903@gmail.com Department of Statistics Interdisciplinary Program in Artificial Intelligence Seoul National University

Reviewed on Open Review: https: // openreview. net/ forum? id= d Hljja NHh1

Group fairness requires that different protected groups, characterized by a given sensitive attribute, receive equal outcomes overall. Typically, the level of group fairness is measured by the statistical gap between predictions from different protected groups. In this study, we reveal an implicit property of existing group fairness measures, which provides an insight into how the group-fair models behave. Then, we develop a new group-fair constraint based on this implicit property to learn group-fair models. To do so, we first introduce a notable theoretical observation: every group-fair model has an implicitly corresponding transport map between the input spaces of each protected group. Based on this observation, we introduce a new group fairness measure termed Matched Demographic Parity (MDP), which quantifies the averaged gap between predictions of two individuals (from different protected groups) matched by a given transport map. Then, we prove that any transport map can be used in MDP to learn group-fair models, and develop a novel algorithm called Fairness Through Matching (FTM)1, which learns a group-fair model using MDP constraint with an user-specified transport map. We specifically propose two favorable types of transport maps for MDP, based on the optimal transport theory, and discuss their advantages. Experiments reveal that FTM successfully trains group-fair models with certain desirable properties by choosing the transport map accordingly.

1The source code of FTM is publicly available at https: // github. com/ kwkimonline/ FTM . This research was conducted while the author was affiliated with Seoul National University. Corresponding author.

Published in Transactions on Machine Learning Research (12/2024)

1 Introduction

Artificial Intelligence (AI) technologies based on machine learning algorithms have become increasingly prevalent as crucial decision-making tools across diverse areas, including credit scoring, criminal risk assessment, and college admissions. However, when observed data contains unfair biases, the resulting trained models may produce discriminatory decisions (Calders et al., 2009; Feldman et al., 2015; Angwin et al., 2016; Barocas & Selbst, 2016; Chouldechova, 2016; Kleinberg et al., 2018; Mehrabi et al., 2019; Zhou et al., 2021). For instance, several cases of unfair preferences favoring specific groups, such as white individuals or males, have been reported (Angwin et al., 2016; Ingold & Soper, 2016; Dua & Graff, 2017). In response, there is a growing trend in non-discrimination laws that calls for the consideration of fair models (Hellman, 2019).

Under this social circumstance, ensuring algorithmic fairness in AI-based decision-making has become a crucial mission. Among several notions of algorithmic fairness, the notion of group fairness is the most explored one, which requires that certain statistics of each protected group should be similar. For example, the ratio of positive predictions should be similar across each protected group (Calders et al., 2009; Barocas & Selbst, 2016; Zafar et al., 2017; Donini et al., 2018; Agarwal et al., 2018).

Various algorithms have been proposed to learn models achieving group fairness. Existing methods for group fairness are roughly categorized into three: pre-processing, in-processing and post-processing. Pre-processing approaches (Zemel et al., 2013; Feldman et al., 2015; Webster et al., 2018; Xu et al., 2018; Madras et al., 2018; Creager et al., 2019; Kim et al., 2022a) aim to debias a given dataset, typically by learning fair representations whose distribution is independent of a given sensitive attribute. The debiased data (or fair representation) is then used to learn models. In-processing approaches (Kamishima et al., 2012; Goh et al., 2016; Zafar et al., 2017; Agarwal et al., 2018; Wu et al., 2019; Cotter et al., 2019; Celis et al., 2019; Zafar et al., 2019; Jiang et al., 2020a; Kim et al., 2022b) train models by minimizing a given objective function under a specified group fairness constraint. Post-processing approaches (Kamiran et al., 2012; Hardt et al., 2016b; Fish et al., 2016; Corbett-Davies et al., 2017; Pleiss et al., 2017; Chzhen et al., 2019; Wei et al., 2020; Jiang et al., 2020a) transform given prediction scores, typically provided by an unfair model, to satisfy a certain fairness level.

Most group-fair algorithms correspond to specific group fairness measures, typically defined by explicit quantities such as prediction scores and sensitive attributes. For example, demographic parity (Calders et al., 2009; Feldman et al., 2015; Angwin et al., 2016) considers the gap between two protected groups in terms of the positive prediction ratio.

However, a shortcoming of such group fairness measures is that they only concern statistical disparities without accounting for implicit mechanisms about how a given model achieves group fairness. Consequently, models can achieve high levels of group fairness in very undesirable ways (see Section B of Appendix for an example). Dwork et al. (2012) also noted that focusing solely on group fairness can lead to issues such as subset targeting and the self-fulfilling prophecy. These observations serve as the motivation of this study. Moreover, our empirical investigations on real-world datasets reveal that unfairness on subsets can be observed in group-fair models learned by existing algorithms, which are designed to achieve group fairness merely (see Section 5).

In this paper, we first propose a new group fairness measure that reveals implicit behaviors of group-fair models. Based on the proposed measure, we develop an in-processing algorithm to learn group-fair models with less undesirable properties (e.g., unfairness on subsets), that cannot be explored or controlled by existing fairness measures.

To do so, we begin by introducing a notable mathematical finding: every group-fair model implicitly corresponds to a transport map, which moves the measure of one protected group to another. Building on this observation, we propose a new measure for group fairness called Matched Demographic Parity (MDP), which quantifies the average prediction gap between two individuals from different protected groups matched by a given transport map. We further prove that the reverse of this finding also holds: any transport map can be used in MDP to learn a group-fair model. Consequently, we develop an algorithm called Fairness Through Matching (FTM), designed to learn a group-fair model under a fairness constraint based on MDP with a given transport map. FTM can provide group-fair models having specific desirable properties (e.g., higher fairness on subsets) by selecting a transport map accordingly. Note that FTM is not designed to achieve the

Published in Transactions on Machine Learning Research (12/2024)

optimal fairness-prediction trade-off, rather, the focus is on mitigating undesirable properties when achieving group fairness (e.g., unfairness on subsets).

In contrast, existing algorithms that focus solely on group fairness may lack such flexibility. In fact, FTM with a transport map that is not carefully selected could result in unreasonable group-fair models, even though group fairness is achieved.

Therefore, the key to effectively using FTM lies in selecting a good transport map. To this end, we propose two specific options for the transport map: one is the optimal transport (OT) map in the input space, and the other is the OT map in the product space of input and output. Each is designed to achieve specific goals. For example, the former achieves higher fairness levels on subsets, while the latter yields better prediction performance and attains higher levels of equalized odds compared to the former. Experiments on real benchmark datasets support our theoretical findings, showing that FTM successfully learns group-fair models with more desirable properties, than those learned by existing algorithms for group fairness.

Main contributions

1. We introduce a notable mathematical observation: every group-fair model has a corresponding implicit transport map. Building on this finding, we present a novel measure of group fairness called Matched Demographic Parity (MDP).

2. We prove that any transport map can be used in MDP to learn group-fair models. Subsequently, we devise a novel algorithm called Fairness Through Matching (FTM), designed to find a group-fair model using a constraint based on MDP with a given transport map. We propose two favorable transport maps tailored for specific purposes.

3. Experiments on benchmark datasets illustrate that FTM successfully learns group-fair models. Furthermore, we examine the benefits of the two proposed transport maps in learning more desirable group-fair models, compared to those learned by existing algorithms that focus solely on achieving group fairness.

2 Preliminaries

2.1 Notations & Problem setting

In this section, we outline the mathematical notations used throughout this paper. We focus on binary classification task in this study. We denote X X Rd and Y Y = {0,1} as the d-dimensional input vector and the binary label, respectively. Whenever necessary, we split X, i.e., the domain of X, with respect to S and write Xs as the domain of X S = s. For given s {0,1}, we let s = 1 s. Assuming the pre-defined sensitive attribute is binary, we denote S {0,1} as the binary sensitive attribute. For a given s {0,1}, the realization of S, we write s = 1 s. For the probability distributions of these variables, let P and PX represent the joint distribution of (X,Y,S) and the marginal distribution of X, respectively. Furthermore, let Ps = PX S=s,s {0,1} be the conditional distributions of X given S = s. We write E and Es as the corresponding expectations of P and Ps, respectively. For observed data, denote D = {(xi,yi,si)}n i=1 as the training dataset, consisting of n independent copies of the random tuple (X,Y,S) P. Let p denote the Lp norm. We also write the L2 norm by , i.e., = 2 for simplicity.

We denote the prediction model as f = f( ,s),s {0,1}, which is an estimator of Ps(Y = 1 X = ), belonging to a given hypothesis class F {f X {0,1} [0,1]}. Note that the output of f is restricted to the interval [0,1], making f bounded. For simplicity, we sometimes write f( ,s) = fs( ) whenever necessary. For given f and s {0,1}, we denote Pfs as the conditional distribution of f(X,s) given S = s. Furthermore, let Cfs = I(f( ,s) τ) be the classification rule based on f, where τ is a specific threshold (typically, τ = 0.5).

2.2 Measures for group fairness & Definition of group-fair model

In the context of group fairness, various measures have been introduced to quantify the gap between predictions of each protected group. The original measure for Demographic Parity (DP), DP(f) =

Published in Transactions on Machine Learning Research (12/2024)

P(Cf0(X) = 1 S = 0) P(Cf1(X) = 1 S = 1) , has been initially considered in various studies (Calders et al., 2009; Feldman et al., 2015; Donini et al., 2018; Agarwal et al., 2019; Zafar et al., 2019). Its relaxed version, DP(f) = E(f0(X)) S = 0) E(f1(X)) S = 1) , has also been explored widely (Madras et al., 2018; Chuang & Mroueh, 2021; Kim et al., 2022a).

However, DP(f) has a limitation as it relies on a specific threshold τ (Silvia et al., 2020). To overcome this issue, the concept of strong DP (which requires similarity in the distributions of prediction values of each protected group) along with several measures for quantifying the discrepancy between Pf0 and Pf1, has been considered (Jiang et al., 2020b; Chzhen et al., 2020; Silvia et al., 2020; Barata et al., 2021). WDP(f) = W(Pf0,Pf1), TVDP(f) = TV(Pf0,Pf1), and KSDP(f) = KS(Pf0,Pf1) are the examples of the measure for strong DP. Here, W,TV, and KS represent the Wasserstein distance, the Total Variation, and the Kolmogorov-Smirnov distance, respectively. For given two probability distributions Q1 and Q2, the three distributional distances are defined as follows. The (1-)Wasserstein distance is defined as W(Q1,Q2) = infγ Γ(Q1,Q2) E(x,y) γ x y 1, where Γ(Q1,Q2) is the set of joint probability distributions of marginals Q1 and Q2. The Total Variation is defined as TV(Q1,Q2) = sup A A Q1(A) Q2(A) , where A is the collection of measurable sets. The Kolmogorov-Smirnov distance is defined as KS(Q1,Q2) = supx R FQ1(x) FQ2(x) , where FQ(x) = Q(X x) is the cumulative distribution function of Q.

Let = ( ) be a given fairness measure. A given model f is said to be group-fair (with level ϵ) if it satisfies (f) ϵ. Furthermore, if (f) = 0, we say f is perfectly group-fair (with respect to ).

2.3 Optimal transport

The concept of the Optimal Transport (OT) provides an approach for geometric comparison between two probability measures. For given two probability measures Q1 and Q2, a map T from Supp(Q1) to Supp(Q2) is called a transport map from Q1 to Q2 if the push-forward measure T#Q1 is equal to Q2 (Villani, 2008). Here, the push-forward measure is defined by T#Q1(A) = Q1(T 1(A)) for any measurable set A. In other words, T#Q1 is the measure of T(X),X Q1. For given source and target distributions Q1 and Q2, the OT map from Q1 to Q2 is the optimal one among all transport maps from Q1 to Q2. In this context, optimal means minimizing transport cost, such as Lp distance in Euclidean space.

Monge (1781) originally formulates this OT problem: for given source and target distributions Q1,Q2 in Rd and a cost function c (e.g., L2 distance), the OT map from Q1 to Q2 is defined by the solution of min T T#Q1=Q2 EX Q1 (c(X,T(X))). If both Q1 and Q2 are discrete with the same number of support points, the OT map exists as a one-to-one mapping. For the case when Q1 and Q2 are discrete but have different numbers of supports, Kantorovich relaxed the Monge problem by seeking the optimal coupling between two distributions (Kantorovich, 2006). The Kantorovich problem is formulated as infπ Π(Q1,Q2) EX,Y π (c(X,Y)), where Π(Q1,Q2) is the set of all joint measures of Q1 and Q2. Note that this formulation can be also applied to the case of Q1 and Q2 with an identical number of support. See Section C of Appendix for more details about the Kantorovich problem.

Various feasible estimators for the OT map have been developed (Cuturi, 2013; Genevay et al., 2016), and applied to diverse tasks such as domain adaptation (Damodaran et al., 2018; Forrow et al., 2019) and computer vision (Su et al., 2015; Li et al., 2015; Salimans et al., 2018), to name a few.

2.4 Related works

Algorithmic fairness Group fairness is a fairness notion aimed at preventing discriminatory predictions over protected (demographic) groups divided by pre-defined sensitive attributes. Among various notions of group fairness, Demographic Parity (DP) (Calders et al., 2009; Feldman et al., 2015; Agarwal et al., 2019; Jiang et al., 2020b; Chzhen et al., 2020) quantifies the statistical gap in predictions between two different protected groups. Other measures, including Equal opportunity (Eqopp) and Equalized Odds (EO), consider groups conditioned on both the label and the sensitive attribute (Hardt et al., 2016a). Various algorithms have been proposed to learn group-fair model satisfying these group fairness notions (Zafar et al., 2017; Donini et al., 2018; Agarwal et al., 2018; Madras et al., 2018; Zafar et al., 2019; Chuang & Mroueh, 2021; Kim et al., 2022a).

Published in Transactions on Machine Learning Research (12/2024)

Individual fairness, initially introduced by Dwork et al. (2012), is another fairness notion based on the philosophy of treating similar individuals similarly. It is noteworthy that Dwork et al. (2012) highlighted that focusing solely on group fairness is not always a complete answer, pointing out issues such as subset targeting and the self-fulfilling prophecy. Subsequent researches (Yona & Rothblum, 2018; Yurochkin et al., 2020; Yurochkin & Sun, 2021; Petersen et al., 2021) have been studied in both theories and methodologies. However, individual fairness has two bottlenecks: (i) it strongly depends on the choice of the similarity metric, which hinders its practical applicability, and (ii) by itself, it does not ensure group fairness when the distributions of protected groups differ significantly. See Section 3.3 for detailed comparison between individual fairness and our proposed framework.

Counterfactual fairness, which requires treating a counterfactual individual similarly to the original individual, has been studied by Kusner et al. (2017); Chiappa & Gillam (2018); von Kügelgen et al. (2022); Nilforoshan et al. (2022). Its application, however, is limited since it requires causal models, which are difficult to obtain only with observed data. Instead of using graphical models to define counterfactuals, this paper suggests using a transport map from Xs to Xs having certain desirable properties. See Proposition 4.3 in Section 4.1 for the relationship between counterfactual fairness and our proposed algorithm.

On the other hand, in presence of multiple sensitive attributes, the concept of subgroup fairness can be considered (Kearns et al., 2018a;b; Shui et al., 2022; Mehrotra et al., 2022; Molina & Loiseau, 2022; Carvalho et al., 2022), emphasizing the need for models that satisfy fairness for all subgroups defined over the multiple sensitive attributes. In addition, Wachter et al. (2020); Simons et al. (2021); Mougan et al. (2024) have suggested that not only statistically equal outcome but also the notion of equal treatment, i.e., treating individuals with equal reasons, should be considered in algorithmic fairness.

Fair representation learning (FRL) FRL algorithm aims at searching a fair representation space, in the sense that the conditional distributions of the encoded representation with respect to the sensitive attribute are similar (Zemel et al., 2013). After learning the fair representation, FRL constructs a fair model by applying a supervised learning algorithm to the fair representation space. Initiated by Edwards & Storkey (2016), various FRL algorithms have been developed (Madras et al., 2018; Zhang et al., 2018) motivated by the adversarial-learning technique used in GAN (Goodfellow et al., 2014). See Section 3.3 for the detailed comparison between FRL and our proposed framework.

Applications of the OT map to algorithmic fairness Several studies, including Gordaliza et al. (2019); Jiang et al. (2020b); Chzhen et al. (2020); Silvia et al. (2020); Buyl & Bie (2022), have employed the OT map for algorithmic fairness. Gordaliza et al. (2019) introduced a fair representation learning method that aligns inputs from different protected groups using the OT map. Jiang et al. (2020b); Chzhen et al. (2020); Silvia et al. (2020) proposed aligning prediction scores from different protected groups using the OT map or OT-based barycenter. Buyl & Bie (2022) developed a method that projects prediction scores onto a fair space by optimizing the projection through minimizing the transport cost calculated on all pairs of inputs.

Most of these algorithms (e.g., Jiang et al. (2020b); Chzhen et al. (2020); Silvia et al. (2020)) focus on applying the OT map in the prediction space, i.e., aligning two conditional distributions Pf0 and Pf1. These methods fundamentally differ from our proposed approach, which focuses on applying the OT map in the input space. On the other hand, Gordaliza et al. (2019) and our approach are particularly similar in the sense that both apply the OT map on the input space. See the detailed comparison between Gordaliza et al. (2019) and our approach in Section 3.3.

It is worth noting that our proposed algorithm becomes the first to define a group fairness measure based on the transport map in the input space and to propose reasonable choices for the transport map.

3 Learning group-fair model through matching

The goal of this section is to explore and specify the correspondence between group-fair models and transport maps. In Section 3.1, we show that every group-fair model has a corresponding implicit transport map in the input space that matches two individuals from different protected groups. We then introduce a new fairness measure based on the correspondence. In Section 3.2, we show the reverse, i.e., any given

Published in Transactions on Machine Learning Research (12/2024)

transport map can be used to learn a group-fair model, then present our proposed algorithm for learning group-fair models under a fairness constraint based on a given transport map.

3.1 Matched Demographic Parity (MDP)

Proposition 3.1 below shows that for a given perfectly group-fair model f (i.e., Pf0 = Pf1 or equivalently = 0), there exists an corresponding transport map in the input space that matches two individuals from different protected groups. Its proof is in Section A of Appendix. Throughout this section, we assume a condition (C): Ps,s = 0,1, are absolutely continuous with respect to the Lebesgue measure. This regularity condition is assumed to simplify the discussion, since it guarantees the existence of transport maps between two distributions. See Proposition A.1 in Section A of Appendix, which presents a similar result for the case where Ps,s = 0,1 are discrete. Let T trans s be the set of all transport maps from Ps to Ps .

Proposition 3.1 (Fair model Transport map: perfect fairness case). For any perfectly group-fair model f, i.e., Pf0 = Pf1, there exists a transport map Ts T trans s satisfying f (X,s) = f (Ts(X),s ),a.e.

The key implication of this mathematical proposition is that all perfectly group-fair models are not the same and the differences can be identified by their corresponding transport maps. We can similarly define a transport map corresponding to a given not-perfectly group-fair model (i.e., > 0), by using a novel fairness measure termed Matched Demographic Parity (MDP) defined as below.

Definition 3.2 (Matched Demographic Parity). For a given model f F and a transport map Ts T trans s , the measure for MDP is defined as

MDP(f,Ts) = Es f(X,s) f(Ts(X),s ) . (1)

The idea behind MDP is that two individuals from different protected groups are matched by Ts, and MDP(f,Ts) quantifies the similarity between the predictions of these two matched individuals. Subsequently, Theorem 3.3 below presents a relaxed version of Proposition 3.1, showing that any group-fair model f has a transport map Ts such that MDP(f,Ts) is small. Refer to Section A of Appendix for the proof of Theorem 3.3 and see Figure 1 for the illustration of MDP.

Theorem 3.3 (Fair model Transport map: relaxed fairness case). Fix a fairness level δ 0. For any given group-fair model f such that TVDP(f) δ, there exists a transport map Ts T trans s satisfying MDP(f,Ts) 2δ.

Figure 1: Simplified illustration of MDP. Once two individuals A and B are matched ( ), a model treats the pair of matched individuals A and B similarly (as well as all the other pairs). This implicit mechanism contributes to making the model fair.

We define the fair matching function for a given f as the transport map that attains the infimum of equation (1), as formulated in Definition 3.4 below. The term fair is used because MDP is minimized by this transport map. Through investigating the fair matching function, we can understand the mechanism behind how a group-fair model behaves. That is, the fair matching function specifically reveals which pairs of individuals from two protected groups are treated similarly by the given group-fair model.

Published in Transactions on Machine Learning Research (12/2024)

Definition 3.4 (Fair matching function of f). For a given f, denote Tf s = arg min Ts T trans s MDP(f,Ts),s

{0,1}. For ˆs = arg mins {0,1} MDP(f,Tf s), the fair matching function of f is defined as Tf = Tf ˆs.

Note that the existence of this fair matching function is guaranteed by Brenier s theorem (Villani, 2008; Hütter & Rigollet, 2021). To be specific, since Ps,s {0,1} are absolutely continuous by (C), and the cost function in MDP, i.e., c(x,y) = f(x,s) f(y,s ) , is lower semi-continuous and bounded from below, the minimizer of MDP(f,Ts) uniquely exists.

Practical computation of the fair matching function In practice, we estimate the fair matching function using the observed data D = {(xi,yi,si)}n i=1. Let D0 = {xi si = 0} = {x(0) i }n0 i=1 and D1 = {xj sj = 1} = {x(1) j }n1 j=1 be the set of inputs given the sensitive attribute, where n0 +n1 = n. We here introduce practical methods for computing the fair matching function in Definition 3.4, by considering two cases:

1. Case of n0 = n1: When the sizes of two protected groups are equal (n0 = n1), we can easily find the fair matching function by quantile matching. We first sort the scores in {fs(x)}x Ds for each group s {0,1}. Then, we match the individuals having the same rank (i.e., quantile) in each set, thereby obtaining the fair matching function of f. This straightforward procedure is theoretically guaranteed by the definition of 1-Wasserstein distance, which is calculated by quantile matching (Rachev & Rüschendorf, 1998; Chzhen et al., 2020; Jiang et al., 2020b). We formally present this procedure in Proposition 3.5 below. Its proof is provided in Section A of Appendix. Let Fs represents the cumulative distribution function of fs(x),x Ds. For technical simplicity, we assume that there is no tie in {fs(x) x Ds}.

Proposition 3.5. Let Tf be the fair matching function of f on D0 and D1 (where the empirical distributions with respect to D0 and D1 are used in Definition 3.4). Then, the matched individual Tf(x) of any x Ds is obtained by Tf(x) = f 1 s F 1 s Fs fs(x).

2. Case of n0 n1: When the sizes differ, we can consider a stochastic fair matching function (a stochastic transport map that minimizes MDP), which matches individuals with probability, not deterministically. In fact, a stochastic transport map corresponds to a joint distribution between two protected groups, i.e., a stochastic transport map can be defined by a joint distribution, as follows:

Denote Q as a joint distribution between D0 and D1, and let X0 and X1 be the random variables following the empirical distributions on D0 and D1, respectively. For a given joint distribution Q, the stochastic transport map Ts (corresponding to the Q) is defined by Ts(x(s) i ) = x(s ) j with probability

Q(Xs = x(s) i ,Xs = x(s ) j ). Once we find the stochastic fair matching function, i.e., the stochastic transport map (joint distribution Q) minimizing MDP(f,Q) = E(X0,X1) Q f(X0,0) f(X1,1) , we can compute its transport cost as E(X0,X1) Q X0 X1 2. Note that the minimization of MDP with respect to the stochastic transport map is technically equivalent to solving the Kantorovich problem, which can be easily solved by the use of linear programming. See Section A and Section C for more details about the stochastic transport map and the Kantorovich problem, respectively.

Alternatively, in practice, we can apply a mini-batch sampling technique. We first sample two random mini-batches D0 D0 and D1 D1 with identical size m. Then, we follow the process in (1) Case of n0 = n1 above. The transport cost of the fair matching function can be then estimated by the average transport costs computed on many random mini-batches. See Remark A.2 in Section A for the statistical validity of this mini-batch technique.

Furthermore, Remark 3.6 below explains how the transport cost can serve as a metric for assessing the desirability of given group-fair models.

Remark 3.6 (Usage of the transport cost of the fair matching function). Furthermore, the transport cost of the fair matching function can serve as a measure to assess whether a given group-fair model is desirable. For example, when choosing a model between two group-fair models with similar levels of group fairness or/and prediction accuracies, the model with the lower transport cost would be preferred. In Section 5.3.2, we compare transport costs of fair matching functions for two different group-fair models, using the mini-batch technique.

Published in Transactions on Machine Learning Research (12/2024)

3.2 Fairness Through Matching (FTM): learning a group-fair model with a transport map

The goal of this section is to formulate our proposed algorithm. Before introducing it, we provide a theoretical support, which shows that a group-fair model can be constructed by MDP using any transport map. Theorem 3.7 below, which is the reverse of Theorem 3.3, shows that any transport map in the input space can construct a group-fair model. Precisely, for a given transport map, if a model provides similar predictions for two individuals who are matched by the transport map, then it is group-fair. The proof is given in Section A of Appendix.

Theorem 3.7 (Transport map Group-fair model). For a given Ts T trans s , if MDP(f,Ts) δ, then we have WDP(f) δ and DP(f) δ.

Again, it is remarkable that a group-fair model and its corresponding transport map are closely related, i.e., every group-fair model has its corresponding implicit transport map, and vice versa. This finding can be mathematically expressed as follows. Let be a given (existing) fairness measure, and define F (δ) = {f F (f) δ} as the set of group-fair models of level δ (with respect to ). Similarly, for MDP, define F MDP(Ts,δ) = {f F MDP(f,Ts) δ}. Then, following from Theorem 3.3 and 3.7, we can conclude that the three measures (i.e., TVDP, WDP, and MDP) are closely related: F TVDP(δ) Ts T trans s {f MDP(f,Ts) 2δ} F WDP(2δ).

As discussed in Section 1 as well as several previous works (e.g., Dwork et al. (2012)), there exist group-fair models having undesirable properties such as subset targeting or self-fulfilling prophecy. The advantage of MDP is that we can screen out such undesirable group-fair models during the learning phase, to consider desirable group fair models only. And, using MDP achieves this goal by considering group-fair models whose transport maps have low transport costs. That is, we can search for a group-fair model only on Ts T good trans s {f MDP(f,Ts) 2δ}, where T good trans s T trans s is a set of specified good transport maps. See Section 4 for such good transport maps that we specifically propose. It is worth noting that such screening would be challenging with existing group-fair measures.

FTM algorithm Based on Theorem 3.7, we develop a learning algorithm named Fairness Through Matching (FTM), which learns a group-fair model subject to MDP being small with a given transport map. FTM consists of two steps. First, we select a (good) transport map. Then, we learn a model under the MDP constraint with the selected transport map. The precise objective of FTM is formulated below.

Suppose a transport map Ts is selected (see Section 4 for the proposed transport maps). FTM solves the following objective for a given loss function l (e.g., cross-entropy) and a pre-defined fairness level δ 0

f FTM(Ts) = arg min f F El(Y,f(X,S)) subject to min s {0,1} MDP(f,Ts) δ. (2)

Unless there is any confusion, we write f FTM instead of f FTM(Ts) for simplicity. By Theorem 3.7, it is clear that f FTM is fair (i.e., WDP(f FTM), DP(f FTM) δ) for any transport map Ts. In practice, we estimate f FTM with observed data D using mini-batch technique along with a stochastic gradient descent based algorithm (see Section 4 for details).

3.3 Conceptual comparison of existing approaches and FTM

Individual fairness FTM and individual fairness are similar in the sense that they try to treat similar individuals similarly. A difference is that FTM aims to treat two individuals from different protected groups similarly, while the individual fairness tries to treat similar individuals similarly regardless of sensitive attribute (even when it is unknown). That is, similar individuals in FTM could be dissimilar in view of individual fairness, especially when the two protected groups are significantly different.

On the other hand, a limitation of individual fairness is that group fairness is not guaranteed. FTM can be also understood as a tool to address this limitation by finding models with higher individual fairness among group-fair models. Empirical results support this conjecture that FTM improves individual fairness compared to baseline methods for group fairness (see Table 4 in Section 5.4.2).

Published in Transactions on Machine Learning Research (12/2024)

Fair representation learning FTM and FRL (Fair Representation Learning) are similar in the sense that they align two conditional distributions. However, the role of the alignment in FTM and FRL are different: FTM builds a prediction model in the original input space, using transport map in the MDP constraint only. In contrast, FRL methods first learn fair representation by aligning the conditional distributions of representation, and then use the learned fair representation as input.

Furthermore, FTM and FRL methods are motivated by fundamentally different objectives. FTM is designed to learn group-fair models with desirable properties (e.g., higher fairness on subsets), whereas FRL methods aim to obtain fair representations which can be used for downstream tasks requiring fairness. The FRL approach proposed by Gordaliza et al. (2019) is particularly similar to FTM, as both apply the OT map on the input space. However, unlike FTM, it trains a prediction model on the (pre-trained) fair representation space derived from the OT map. On the contrary, FTM builds the prediction model on the original input space and utilizes the OT map solely within the fairness constraint. As a result, the prediction model of FTM is not tied to the OT map, making it more flexible and leading to improved prediction accuracy. Empirical evidence supporting this claim is provided in Table 5 in Section 5.4.3, which demonstrates the superior performance of FTM compared to several FRL methods, including Gordaliza et al. (2019).

4 Empirical algorithm with transport map selection

The implication of Theorems 3.3 and 3.7 is that any transport map corresponds to a group-fair model. However, an improperly chosen transport map can result in undesirable outcomes, even if group fairness is satisfied, as shown in Theorem 3.7 (see Section B of Appendix for an example of a problematic group-fair model due to an unreasonable transport map). Thus, selecting an appropriate transport map is crucial when using FTM, which is the primary focus of this section.

Specifically, we propose two favorable choices of the transport map Ts used in FTM. In Section 4.1, we suggest using the OT map in the input space X, resulting in a group-fair model with a higher fairness level on subsets. In Section 4.2, we propose using the OT map in the product space X Y, to improve prediction performance and the level of equalized odds, when compared to the OT map in the input space.

4.1 OT map on X

For a given Ts T trans s , the transport cost (on X) of Ts is defined by Es X Ts(X) 2. First, we propose using the OT map between the two input spaces, which is the minimizer of the transport cost on X among all transport maps. From now on, we call this OT map on X as the marginal OT map.

In this section, we explore a benefit of using the marginal OT map (i.e., low transport cost) by showing a theoretical relationship between the transport cost and fairness on subsets. Many undesirable behaviors of group-fair models have been recognized and discussed (Dwork et al., 2012; Kearns et al., 2018a; Wachter et al., 2020; Mougan et al., 2024). Subset fairness, which is a similar concept to subset targeting in Dwork et al. (2012), is one of such undesirable behaviors. We say that a group-fair model is subset-unfair if it is not group-fair against a certain subset (e.g., aged over 60s) even if it is group-fair overall. The definition of subset fairness can be formulated as follows. Definition 4.1 (Subset fairness). Let A be a subset of X. The level of subset fairness over A is defined as

DPA(f) = E(f(X,0) S = 0,X A) E(f(X,1) S = 1,X A) .

Intuitively, we expect that a group-fair model with a low transport cost would exhibit a high level of subset fairness. This is because the chance of two matched individuals (from different protected groups) belonging to the same subset A tends to be higher when the transport cost is smaller. Theorem 4.2 theoretically supports this conjecture, whose proof is provided in Section A of Appendix. Theorem 4.2 (Low transport cost benefits subset fairness). Suppose F is the collection of L-Lipschitz2

functions. Let A be a given subset in X. Then, for all f satisfying MDP(f,Tf s) δ, we have

DPA(f) L(Es X Tf s(X) 2)

1 2 + TV(P0,A,P1,A) + Uδ, (3)

2A function g X R is L-Lipschitz if g(x1) g(x2) L x1 x2 for all x1, x2 X.

Published in Transactions on Machine Learning Research (12/2024)

where Ps,A is the distribution of X S = s,X A, and U > 0 is a constant only depending on A and Ps,s = 0,1.

The first term of RHS, L(Es X Tf s(X) 2) 1/2 , implies that using a transport map with a small transport cost helps improve the level of subset fairness. The uncontrollable term TV(P0,A,P1,A) can be small for certain subsets. For example, for disjoint sets A1, ,AK of A, suppose that Ps is a mixture of uniform distribution given as Ps( ) = K k=1 psk I( Ak) with psk 0 and K k=1 psk = 1 (e.g., the histogram). Then, TV(P0,A,P1,A) becomes zero for all Ak,k [K]. The last term Uδ becomes small when δ is small.

Connection to counterfactual fairness The concept of FTM is also related to counterfactual fairness (Kusner et al., 2017). In specific, under a simple Structural Causal Model (SCM), the input transported by the marginal OT map is equivalent to the counterfactual input. Particularly, let Xs = X S = s for s {0,1} and consider an SCM

Xs = µs + AXs + ϵs (4)

for given A Rd d, µs Rd with Gaussian random noise ϵs N(0,σ2 s D) of a diagonal matrix D Rd d and variance scaler σ2 s. An example DAG (Directed Acyclic Graph) for equation (4) is Figure 2.

ϵs N(0,σ2 s D)

Figure 2: An example DAG of the SCM in equation (4).

Let xs be a realization of Xs and assume (Id A) has its inverse B = (Id A) 1, where Id Rd d is the identity matrix. Then, its counterfactual becomes x CF s = Bµs + σs σ 1 s Id(xs Bµs) (proved with Proposition 4.3 together in Section A of Appendix). On the other hand, by Lemma A.3 in Section A of Appendix, the image of xs by the marginal OT map is given as x OT s = Bµs + Ws(xs Bµs) for some Ws Rd d. Proposition below 4.3 shows x CF s = x OT s , whose proof is deferred to Section A of Appendix.

Proposition 4.3 (Counterfactual fairness and the marginal OT map). For all A having (Id A) 1, Ws becomes σs σ 1 s Id. That is, x CF s = x OT s .

We further present an example in Section B of Appendix showing that a transport map with a high transport cost can lead to a problematic group-fair model. Moreover, Section 5.2.2 empirically shows that group-fair models learned by FTM with the marginal OT map attain higher fairness levels on various subsets that are not explicitly considered in the training phase, compared to group-fair models learned by existing algorithms.

Estimation of the marginal OT map To estimate the marginal OT map in practice, we sample two random mini-batches D0 = {x(0) i }m i=1 D0 and D1 = {x(1) j }m j=1 D1 with an identical size m n. For given two empirical distributions on D0 and D1, the cost matrix between the two is defined by C = [ci,j] Rm m + where ci,j = x(0) i x(1) j 2. The optimal coupling is then defined by the matrix Γ = [γi,j] Rm m + , which solves the following objective:

min Γ C Γ 1 = min γi,j ci,jγi,j s.t. m i=1 γi,j = m j=1 γi,j = 1

m,γi,j 0. (5)

Due to the equal sample sizes of Ds,s {0,1}, the optimal coupling has only one non-zero (positive) entry for each row and column (i.e., Γ is a doubly stochastic matrix scaled by a constant factor of 1/m). Then, the marginal OT map for each x(0) i D0 is defined by T0, D(x(0) i ) = x(1) j 1(γi,j > 0) and T1, D is defined similarly.

4.2 OT map on X Y

One might argue that using the marginal OT map could degrade the prediction performance much, since the matchings done by the marginal OT map do not consider the similarity in Y. As a remedy for this issue, we consider incorporating the label Y into the cost matrix calculation to avoid substantial degradation in prediction performance.

For this purpose, we define a new cost function on X Y. Let α be a given positive constant. The new cost function cα Rd+1 Rd+1 R+ is defined by: cα((x1,y1),(x2,y2)) = x1 x2 2 + α y1 y2 , for given

Published in Transactions on Machine Learning Research (12/2024)

x1,x2 Rd and y1,y2 R. Among all transport maps from the distribution of X,Y S = s to the distribution of X,Y S = s , we find the OT map that minimizes this modified transport cost on X Y (i.e., the expected value of cα, where the expectation is taken over the distribution of X,Y S = s). We call this OT map on X Y as the joint OT map.

Using this joint OT map with a positive α can contribute to the improvement in prediction accuracy compared to the marginal OT map. This is because, while the marginal OT map does not care labels when matching individuals, the joint OT map tends to match individuals with the same label as much as possible when α is sufficiently large.

Not only the prediction accuracy, but also the level of equalized odds (i.e., demographic parities on the subsets consisting of those with Y = 0 and Y = 1, respectively) can be improved. This is because, FTM with the joint OT map tends to predict similarly for individuals with the same labels but from different protected groups, which directly aligns with the concept of equalized odds. We can theoretically prove this claim as follows. First, we decompose MDP(f,Ts) as MDP(f,Ts) = w0Es ( f(X,s) f(Ts(X),s ) Y = 0) + w1Es ( f(X,s) f(Ts(X),s ) Y = 1), where wy = P(Y = y S = s),y {0,1}. Note that by the definition of the joint OT map, we have for almost all x with respect to the distribution of X S = s, P(Y = y X = x,S = s) = P(Y = y X = Ts(x),S = s ) for all y {0,1} when α . Then, we have that C max{ TPR(f), FPR(f)} w0 TPR(f) + w1 FPR(f) MDP(f,Ts), where C = min{w0,w1} is a constant. Here, TPR(f) = E(f0(X) Y = 1,S = 0) E(f1(X) Y = 1,S = 1) and FPR(f) = E(f0(X) Y = 0,S = 0) E(f1(X) Y = 0,S = 1) are the smooth versions of TPR(f) and FPR(f), respectively. Hence, we can conclude that using the joint OT map with large α can improve EO, compared to the marginal OT map.

We empirically confirm this claim in Section 5.3, by showing that group-fair models learned by FTM with the joint OT map offer improved prediction accuracies as well as improved levels of equalized odds, when compared to FTM with the marginal OT map.

Estimation of the joint OT map We apply a similar technique to the marginal OT map case, starting by sampling two random mini-batches D0 and D1 with an identical size m n. Let y(0) i and y(1) j be the

corresponding labels of x(0) i D0 and x(1) j D1, respectively. For a given α 0, we modify the cost matrix as

follows: Cα = [cα i,j] Rm m + where cα i,j = x(0) i x(1) j 2 + α y(0) i y(1) j . Note that when α = 0, this problem becomes equivalent to the case of the marginal OT map in equation (5). We similarly calculate the optimal coupling the matrix by solving the following objective:

min Γ Cα Γ 1 = min γi,j cα i,jγi,j s.t. m i=1 γi,j = m j=1 γi,j = 1

m,γi,j 0. (6)

Then, the joint OT map for each x(0) i D0 is defined by T0, D(x(0) i ) = x(1) j 1(γi,j > 0) and T1, D is defined similarly.

4.3 Empirical algorithm for FTM

In practice, we learn f with a stochastic gradient descent algorithm. For each update, to calculate the expected loss, we sample a random mini-batch D D of size n n. Then, we update the solution using the gradient of the following objective function

n (xi,yi,si) D l(yi,f(xi,si)) + λ 1

x(s) i Ds f(x(s) i ,s) f(Ts, D(x(s) i ),s ) (7)

for any s {0,1}, where λ > 0 is the Lagrange multiplier and Ts, D is a pre-specified transport map from Ds to Ds (e.g., the marginal OT map from Section 4.1 or the joint OT map from Section 4.2).

Published in Transactions on Machine Learning Research (12/2024)

5 Experiments

This section presents our experimental results, showing that FTM with the proposed transport maps in Section 4 empirically works well to learn group-fair models. The key findings throughout this section are summarized as follows.

FTM with the marginal OT map successfully learns group-fair models that exhibit (i) competitive prediction performance (Section 5.2.1) and (ii) higher levels of subset fairness (Section 5.2.2), when compared to other group-fair models learned by existing baseline algorithms. Beyond subset fairness, we further evaluate the self-fulfilling prophecy (Dwork et al., 2012) as an additional benefit of low transport cost (see Table 10 and 11 in Section E of Appendix).

FTM with the joint OT map has the ability to learn group-fair models with improved prediction performance as well as improved levels of equalized odds, when compared to FTM with the marginal OT map (Section 5.3).

5.1 Settings

Datasets We use four real-world benchmark tabular datasets in our experiments: Adult (Dua & Graff, 2017), German (Dua & Graff, 2017), Dutch (Van der Laan, 2001), and Bank (Moro et al., 2014). The basic information about these datasets is provided in Table 6 in Section D.1 of Appendix. We randomly partition each dataset into training and test datasets with the 8:2 ratio. For each split, we learn models using the training dataset and evaluate the models on the test dataset. This process is repeated 5 times, and the average performance on the test datasets is reported.

Baseline algorithms and implementation details For the baseline algorithms, we consider three most popular state-of-the-art methods: Reduction (Agarwal et al., 2018), Reg (minimizing cross-entropy + λ DP 2, which is considered in Donini et al. (2018); Chuang & Mroueh (2021)), and Adv (adversarial learning for ensuring that the model s predictions are independent of sensitive attributes, which is proposed by Zhang et al. (2018)). Additionally, we consider the unfair baseline (abbr. Unfair), the ERM model trained without any fairness regularization or constraint. For the measure of prediction performance, we use the classification accuracy (abbr. Acc). For fairness measures, we consider DP, DP and WDP, which are defined in Section 2.2.

For all algorithms, we employ MLP networks with Re LU activation and two hidden layers, where the hidden size is equal to the input dimension. We run all algorithms for 200 epochs and report their final performances on the test dataset. The Adam optimizer (Kingma & Ba, 2014) with the initial learning rate of 0.001 is used. To obtain the OT map for each mini-batch, we solve the linear program by using the POT library (Flamary et al., 2021). We utilize several Intel Xeon Silver 4410Y CPU cores and RTX 3090 GPU processors. More implementation details with Pytorch-style psuedo-code are provided in Section D.2 and D.3 of Appendix.

Figure 3: Fairness-prediction trade-offs: WDP vs. Acc on (Left to right) Adult, German, Dutch, Bank datasets. Similar results are observed for DP and DP in Figure 8 in Section E of Appendix.

5.2 FTM with the marginal OT map

This section presents the performance of FTM with the marginal OT map, in terms of (i) fairness-prediction trade-off and (ii) improvement in subset fairness.

Published in Transactions on Machine Learning Research (12/2024)

5.2.1 Fairness-prediction trade-off

In this section, we empirically verify that learned models by FTM successfully achieves group fairness (demographic parity). Figure 3 below shows that FTM successfully learns group-fair models for various fairness levels.

Another main implication is that using the marginal OT map does not hamper prediction performance much. Figure 3 supports this assertion in terms of fairness-prediction trade-off, that is, FTM is competitive with the three baselines. In most datasets, the performance of FTM is not significantly worse than that of the top-performing algorithm (i.e., Reduction). Notably, on German dataset, FTM performs the best, whereas Reduction fails to learn group-fair models with fairness level under 0.06. Additionally, FTM mostly outperforms the other two baseline algorithms, Reg and Adv. Hence, we can conclude that FTM is also a promising algorithm for achieving group fairness.

5.2.2 Improvement in subset fairness

This section highlights the key advantages of using the marginal OT map in terms of subset fairness, which is theoretically supported by Theorem 4.2. We examine two scenarios for the subset A in Definition 4.1: (1) random subsets and (2) subsets defined by specific input variables.

Random subsets First, we generate a random subset Dsub from the test data defined as Dsub = {i v xi 0}, using a random vector v drawn from the uniform distribution on [ 1,1]d. Then, we calculate DP on Dsub. Figure 4 presents boxplots of the DP values calculated on 1,000 randomly generated Dsub. Outliers in the boxplots (points in red boxes) represent the example instances of subset unfairness. For a fair comparison, we evaluate under a given DP for each dataset: 0.06 for Adult, 0.01 for German, 0.07 for Dutch, and 0.04 for Bank. Notably, FTM consistently has the fewest outliers than all the baselines, indicating that FTM achieves higher fairness on random subsets.

Figure 4: Fairness on random subsets: Boxplots of the levels of DP on 1,000 randomly generated subsets Dsub of test datasets. (Left to right) Adult, German, Dutch and Bank. The values presented under the algorithm name (e.g., 0.0151 for FTM in German) are the standard deviations.

Subsets defined by specific input variables Second, we focus on subsets defined by a specific input variable. For this scenario, we construct two subsets by binarizing a specific input variable using its median value. Note that we learn models considering only gender as the sensitive attribute. Table 1 presents the fairness levels (with respect to gender) in the two subsets of the learned models. We consider German and Dutch datasets for this analysis. For German dataset, the two subsets are defined by {x of high age} and {x of low age}. For Dutch dataset, the two subsets are defined by {x who is married} and {x who is not married}. The results highlight the superiority of FTM in achieving higher fairness in these specific subsets.

5.3 FTM with the joint OT map

This section shows the effect of using the joint OT map, in terms of improvement in (i) prediction accuracy, level of equalized odds (Section 5.3.1), and (ii) the transport cost (Section 5.3.2). We use Adult dataset for this analysis. For FTM with the joint OT map, we fix α = 100, because the results with α > 100 are almost identical to those with α = 100. In other words, 100 is the minimum value for α where α y(0) i y(1) j fully

dominates the transport cost x(0) i x(1) j 2.

Published in Transactions on Machine Learning Research (12/2024)

Table 1: Fairness levels on the subsets defined by specific input variables: Bold faced ones highlight the best results, and underlined ones are the second best ones. Standard errors are provided in Table 8 and 9 in Section E of Appendix. (Left) The subsets are defined by the input variable age on German dataset under a given DP = 0.045. (Right) The subsets are defined by the input variable marital status on Dutch dataset under a given DP = 0.120.

German Dutch

Measure Subset Reduction Reg Adv FTM Subset Reduction Reg Adv FTM

0.073 0.077 0.048 0.045

0.258 0.372 0.237 0.204 DP 0.049 0.029 0.028 0.026 0.182 0.164 0.187 0.152 WDP 0.053 0.039 0.042 0.038 0.183 0.172 0.193 0.152

0.118 0.116 0.122 0.077

Not married

0.061 0.131 0.095 0.068 DP 0.047 0.050 0.053 0.047 0.045 0.062 0.098 0.036 WDP 0.058 0.059 0.061 0.054 0.045 0.072 0.098 0.045

5.3.1 Improvement in prediction accuracy and equalized odds

Table 2: Comparison between (i) the marginal OT map and (ii) the joint OT map in terms of prediction accuracy and level of equalized odds, with the two fixed fairness level DPs at 0.033 and 0.054.

DP = 0.033 Acc ( ) TPR ( ) FPR ( ) EO ( )

Marginal OT map 0.806 0.052 0.012 0.032 Joint OT map 0.810 0.043 0.013 0.028

DP = 0.054 Acc ( ) TPR ( ) FPR ( ) EO ( )

Marginal OT map 0.826 0.031 0.023 0.027 Joint OT map 0.830 0.021 0.019 0.020

Table 2 shows that FTM with the joint OT map can provide higher prediction performance than FTM with the marginal OT map in certain scenarios, where more accurate group-fair models than FTM with the marginal OT map exist (e.g., DP 0.06 in Figure 3). Furthermore, we observe that the level of equalized odds can also be improved in these scenarios. To assess the level of equalized odds, we basically use the differences in TPR and FPR, defined as TPR = P(Cf0(X) = 1 S = 0,Y = 1) P(Cf1(X) = 1 S = 1,Y = 1) and FPR = P(Cf0(X) = 1 S = 0,Y = 0) P(Cf1(X) = 1 S = 1,Y = 0) , respectively. Note that TPR is also a measure for equal opportunity. We additionally use an overall measure defined as EO = 1 2 y=0,1 P(Cf0(X) = 1 S = 0,Y = y) P(Cf1(X) = 1 S = 1,Y = y) , which is also considered in previous works (Donini et al., 2018; Chuang & Mroueh, 2021).

Figure 5: Fairness-prediction trade-offs: DP vs. Acc on (Left to right) Adult, German, Dutch, Bank datasets. FTM (joint) = FTM with the joint OT map. FTM (marginal) = FTM with the marginal OT map.

In addition, we compare FTM using the marginal OT map, FTM using the joint OT map, and other baseline methods, in terms of the overall fairness-prediction trade-off. As shown in Figure 5, FTM with the joint OT map achieves performance comparable to the best-performing baseline. This result suggests that using FTM with an appropriate transport map can empirically achieve the optimal trade-off, highlighting the flexibility of FTM in controlling the fairness-prediction trade-off, by selecting an appropriate transport map.

Published in Transactions on Machine Learning Research (12/2024)

5.3.2 Increase in transport cost

On the other hand, using the joint OT map can result in a higher transport cost (of the fair matching function) compared to the marginal OT map. To compute the transport cost of the fair matching function, we follow the mini-batch technique introduced in Section 3.1. We use 100 random mini-batches with batch size of m = 1024. The left panel of Figure 6 illustrates that increasing α can improve prediction accuracy, though this improvement comes with a higher transport cost, especially when group-fair models more accurate than FTM with the marginal OT map exist. That is, at DP = 0.025, a point where a group-fair model more accurate than FTM with the marginal OT map exists (e.g., Reduction in Figure 3), both accuracy and transport cost increase, as α increases.

In contrast, the right panel of Figure 6 shows that increasing α does not significantly improve prediction accuracy while still incurring a higher transport cost, when FTM with the marginal OT map is competitive with other group-fair models in terms of accuracy. That is, at DP = 0.073, a point where the accuracy of FTM with the marginal OT map is similar to that of other group-fair models, increasing α does not yield notably beneficial results.

Figure 6: Transport cost-prediction trade-offs: Transport cost of the fair matching function vs. Acc of FTM with the joint OT map of α {0,1,5,10,50,100} on Adult dataset.

Overall, FTM with the joint OT map using an appropriately tuned α could be a desirable solution, especially when seeking for a group-fair model that is more accurate than a group-fair model learned by FTM with the marginal OT map. However, tuning α can be challenging, and compromising subset fairness would be generally not advisable. Additionally, as discussed in Section 5.2.1, using the marginal OT map is also competitive with other baselines in terms of prediction accuracy. Therefore, we basically recommend using the marginal OT map for FTM, while considering the joint OT map is particularly useful when the prediction accuracy of a group-fair model learned by FTM with the marginal OT map is suboptimal.

5.4 Further comparisons

To further assess the validity of FTM from various perspectives, we consider three scenarios for empirical comparison with baseline algorithms: (i) FTM is robust under a group imbalance setting (i.e., P(S = 0) << P(S = 1)). (ii) FTM can improve the level of individual fairness, compared to existing group fairness algorithms. (iii) FTM outperforms several existing FRL methods, by achieving higher prediction accuracy for a given level of fairness. For simplicity, we employ the marginal OT map in this section for these analyses.

5.4.1 Comparison of stability under imbalance setting

We evaluate the stability of FTM and existing algorithms under an imbalanced scenario for the sensitive attribute. For this purpose, after training/test data split, we construct an imbalanced training dataset with a 5:95 ratio (5% for S = 0 and 95% for S = 1) by randomly sampling data from D0 and fully using D1. Then, we measure the performances on test dataset, where the models are learned on this imbalanced training dataset. We use Adult dataset for this analysis. For a fixed fairness level of DP 0.064, we calculate the corresponding prediction accuracy. This procedure is repeated five times, and we calculate the average as well as the standard deviation.

In Table 3, we present the average, standard deviation, and coefficient of variation (standard deviation average) for each algorithm. The results indicate that FTM offers comparable stability to the baselines, showing that FTM is not particularly unstable under this group imbalance setting.

Published in Transactions on Machine Learning Research (12/2024)

Table 3: Stability under imbalance setting: For a fixed fairness level DP 0.064, average (Avg), standard deviation (Std), and coefficient of variation (CV) of the prediction accuracy (Acc) over five random training imbalanced datasets are provided.

Measure Reduction Reg Adv FTM

Avg 0.835 0.836 0.819 0.827 Std 0.003 0.003 0.021 0.002 CV 0.004 0.004 0.026 0.002

Table 4: Comparison in view of individual fairness: Given a fixed DP, the level of individual fairness (i.e., Con) and corresponding Acc are provided. The bold faced values are the best values of Con.

Dataset ( DP) Con (Acc) Reduction Reg Adv FTM

Adult ( 0.08) 0.915 (0.839) 0.902 (0.802) 0.899 (0.829) 0.935 (0.838)

German ( 0.06) 0.950 (0.743) 0.932 (0.745) 0.944 (0.672) 0.965 (0.744)

Dutch ( 0.17) 0.952 (0.824) 0.914 (0.815) 0.921 (0.778) 0.980 (0.824)

Bank ( 0.04) 0.927 (0.885) 0.978 (0.885) 0.911 (0.884) 0.972 (0.885)

5.4.2 Comparison in view of individual fairness

As discussed in Section 3.3, as FTM is conceptually similar to the individual fairness, we here compare FTM to baseline algorithms for group fairness, in view of individual fairness. For the measure of individual fairness, we use the consistency (Con) from Yurochkin et al. (2020); Yurochkin & Sun (2021), which is the ratio of consistently predicted labels when we only flip the sensitive variable among the input variables. Table 4 presents the results, showing that FTM consistently achieves higher individual fairness than baselines.

5.4.3 Comparison with FRL methods

Table 5: Comparison between FTM and FRL methods: Given a fixed DP, the prediction accuracy (Acc) is provided. The bold faced values are the best values of Acc.

Dataset ( DP) Acc LAFTR s IPM-LFR Gordaliza et al. (2019) FTM

Adult ( 0.06) 0.823 0.820 0.815 0.835

German ( 0.04) 0.721 0.741 0.728 0.743

Dutch ( 0.15) 0.810 0.813 0.811 0.820

Bank ( 0.02) 0.877 0.878 0.876 0.878

In this section, we experimentally compare FTM with several existing FRL methods. The baseline FRL methods include three approaches: two adversarial learning-based FRL methods, LAFTR (Madras et al., 2018) and s IPM-LFR (Kim et al., 2022a), as well as the FRL method proposed by Gordaliza et al. (2019), which is particularly similar to FTM in that both utilize the OT map for aligning distributions. Note that in FRL, fair representations are first obtained (via barycentric mapping for Gordaliza et al. (2019) and adversarial learning for LAFTR and s IPM-LFR), and then we learn a prediction model on the fair representation space.

The results are presented in Table 5, showing the superior prediction performance of FTM compared to the baseline FRL methods. This outperformance of FTM is due to the fact that FRL methods are pre-processing approaches (i.e., using fair representation as a new input feature for the prediction model), whereas FTM is an in-processing approach.

Published in Transactions on Machine Learning Research (12/2024)

6 Conclusion and discussion

In this paper, we have discussed the existence of implicit transport maps corresponding to each group-fair model. Specifically, we have introduced a novel group fairness measure named MDP. Building upon MDP, we propose a novel algorithm, FTM, designed for learning group-fair models with high levels of subset fairness. Experimental results demonstrate that FTM with the marginal OT map effectively produces group-fair models with improved levels of subset fairness on various subsets compared to baseline models, while maintaining reasonable prediction performance. Moreover, we have proposed to use the joint OT map to improve the prediction accuracy and equalized odds, compared to the marginal OT map.

We suggest several promising topics for future research: (1) Expanding FTM to incorporate other fairness notions would be a valuable avenue for future work. For example, while this paper has focused DP (demographic parity) for simplicity and clarity, but applying FTM to Eqopp (equal opportunity) would be straightforward by restricting the calculation of MDP to instances where Y = 1. (2) Exploring scenarios with multiple sensitive attributes, a topic frequently studied in group fairness research, is another valuable direction. Such cases require matching individuals from more than two protected groups, which would be challenging and is therefore left for future work. (3) There may be other transport maps that yield different types of group-fair models, while this paper has only considered two transport maps. Exploring other useful transport maps would yield interesting insights and applications.

Broader Impact Statement

The broad goal of this study is to caution users of fair AI models such as social planners and courts against focusing solely on group fairness without accounting for the risks of potential discrimination, such as subset fairness. Additionally, our study aims to equip them with tools to address these aspects. Even though our study is rather technical, we believe that it can provide a new perspective on algorithmic fairness and could potentially impact policy-making and regulation in related fields.

A key social benefit of the proposed methods is that we can train group-fair models with higher levels of subset fairness without needing to collect and process additional sensitive data. By doing so, the proposed algorithm is expected to transcend the fairness-privacy trade-off, making it practical for use without conflicting with data protection laws.

Another social impact of our study is that the relationship between transport maps and group-fair models may help us form a new concept of fairness that can be readily accepted by society. Our approach explores the micro-level behavior of a given group-fair model (i.e., how the model matches individuals rather than simply looking at the statistics), which could facilitate finding reasonable compromises for existing fairness concepts that may appear paradoxical.

Acknowledgments

YK was partly supported by the National Research Foundation of Korea(NRF) grant funded by the Korea government(MSIT)(No. 2022R1A5A7083908), Institute of Information & communications Technology Planning & Evaluation (IITP) grant funded by the Korea government(MSIT) (No.RS-2022-II220184, Development and Study of AI Technologies to Inexpensively Conform to Evolving Policy on Ethics), and Institute of Information & communications Technology Planning & Evaluation (IITP) grant funded by the Korea government(MSIT) [NO.RS-2021-II211343, Artificial Intelligence Graduate School Program (Seoul National University)]. MC was supported by a Korea Institute for Advancement of Technology (KIAT) grant funded by the Korea Government (MOTIE) (RS-2024-00409092, 2024 HRD Program for Industrial Innovation).

Published in Transactions on Machine Learning Research (12/2024)

Alekh Agarwal, Alina Beygelzimer, Miroslav Dudik, John Langford, and Hanna Wallach. A reductions approach to fair classification. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 60 69. PMLR, 10 15 Jul 2018. URL https://proceedings.mlr.press/v80/agarwal18a.html.

Alekh Agarwal, Miroslav Dudík, and Zhiwei Steven Wu. Fair regression: Quantitative definitions and reduction-based algorithms. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, 2019. URL http://proceedings.mlr.press/ v97/agarwal19d.html.

Julia Angwin, Jeff Larson, Surya Mattu, and Lauren Kirchner. Machine bias. Pro Publica, May, 23:2016, 2016.

António Pereira Barata, Frank W. Takes, H. Jaap van den Herik, and Cor J. Veenman. Fair tree classifier using strong demographic parity, 2021.

Solon Barocas and Andrew D Selbst. Big data s disparate impact. Calif. L. Rev., 104:671, 2016.

Rachel K. E. Bellamy, Kuntal Dey, Michael Hind, Samuel C. Hoffman, Stephanie Houde, Kalapriya Kannan, Pranay Lohia, Jacquelyn Martino, Sameep Mehta, Aleksandra Mojsilovic, Seema Nagar, Karthikeyan Natesan Ramamurthy, John Richards, Diptikalyan Saha, Prasanna Sattigeri, Moninder Singh, Kush R. Varshney, and Yunfeng Zhang. AI Fairness 360: An extensible toolkit for detecting, understanding, and mitigating unwanted algorithmic bias, October 2018. URL https://arxiv.org/abs/1810.01943.

Sarah Bird, Miro Dudík, Richard Edgar, Brandon Horn, Roman Lutz, Vanessa Milan, Mehrnoosh Sameki, Hanna Wallach, and Kathleen Walker. Fairlearn: A toolkit for assessing and improving fairness in ai. Technical Report MSR-TR-2020-32, Microsoft, May 2020.

Maarten Buyl and Tijl De Bie. Optimal transport of classifiers to fairness. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022. URL https://openreview.net/forum?id=-wel Firj Mss.

Toon Calders, Faisal Kamiran, and Mykola Pechenizkiy. Building classifiers with independency constraints. In 2009 IEEE International Conference on Data Mining Workshops, pp. 13 18. IEEE, 2009.

Jean-Paul Carvalho, Bary Pradelski, and Cole Williams. Affirmative action with multidimensional identities. Available at SSRN 4070930, 2022.

L Elisa Celis, Lingxiao Huang, Vijay Keswani, and Nisheeth K Vishnoi. Classification with fairness constraints: A meta-algorithm with provable guarantees. In Proceedings of the Conference on Fairness, Accountability, and Transparency, pp. 319 328, 2019.

Silvia Chiappa and Thomas P. S. Gillam. Path-specific counterfactual fairness, 2018. URL https://arxiv. org/abs/1802.08139.

Lénaïc Chizat, Pierre Roussillon, Flavien Léger, François-Xavier Vialard, and Gabriel Peyré. Faster wasserstein distance estimation with the sinkhorn divergence. In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS 20, Red Hook, NY, USA, 2020. Curran Associates Inc. ISBN 9781713829546.

Alexandra Chouldechova. Fair prediction with disparate impact: A study of bias in recidivism prediction instruments, 2016. URL https://arxiv.org/abs/1610.07524.

Ching-Yao Chuang and Youssef Mroueh. Fair mixup: Fairness via interpolation. In International Conference on Learning Representations, 2021. URL https://openreview.net/forum?id=DNl5s5BXe Bn.

Evgenii Chzhen, Christophe Denis, Mohamed Hebiri, Luca Oneto, and Massimiliano Pontil. Leveraging labeled and unlabeled data for consistent fair binary classification. In Advances in Neural Information Processing Systems, pp. 12760 12770, 2019.

Published in Transactions on Machine Learning Research (12/2024)

Evgenii Chzhen, Christophe Denis, Mohamed Hebiri, Luca Oneto, and Massimiliano Pontil. Fair regression with wasserstein barycenters. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 7321 7331. Curran Associates, Inc., 2020. URL https://proceedings.neurips.cc/paper/2020/file/ 51cdbd2611e844ece5d80878eb770436-Paper.pdf.

Sam Corbett-Davies, Emma Pierson, Avi Feller, Sharad Goel, and Aziz Huq. Algorithmic decision making and the cost of fairness. In Proceedings of the 23rd acm sigkdd international conference on knowledge discovery and data mining, pp. 797 806, 2017.

Andrew Cotter, Heinrich Jiang, and Karthik Sridharan. Two-player games for efficient non-convex constrained optimization. In ALT, 2019.

Elliot Creager, David Madras, Jörn-Henrik Jacobsen, Marissa Weis, Kevin Swersky, Toniann Pitassi, and Richard Zemel. Flexibly fair representation learning by disentanglement. In International Conference on Machine Learning, pp. 1436 1445. PMLR, 2019.

Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. In C.J. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K.Q. Weinberger (eds.), Advances in Neural Information Processing Systems, volume 26. Curran Associates, Inc., 2013. URL https://proceedings.neurips.cc/paper/2013/ file/af21d0c97db2e27e13572cbf59eb343d-Paper.pdf.

Bharath Bhushan Damodaran, Benjamin Kellenberger, Rémi Flamary, Devis Tuia, and Nicolas Courty. Deepjdot: Deep joint distribution optimal transport for unsupervised domain adaptation. In Computer Vision ECCV 2018: 15th European Conference, Munich, Germany, September 8-14, 2018, Proceedings, Part IV, pp. 467 483, Berlin, Heidelberg, 2018. Springer-Verlag. ISBN 978-3-030-01224-3. doi: 10.1007/ 978-3-030-01225-0_28. URL https://doi.org/10.1007/978-3-030-01225-0_28.

Nabarun Deb, Promit Ghosal, and Bodhisattva Sen. Rates of estimation of optimal transport maps using plug-in estimators via barycentric projections. In Neur IPS, 2021.

Michele Donini, Luca Oneto, Shai Ben-David, John S Shawe-Taylor, and Massimiliano Pontil. Empirical risk minimization under fairness constraints. In Advances in Neural Information Processing Systems, pp. 2791 2801, 2018.

Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL http://archive.ics.uci.edu/ ml.

Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through awareness. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, ITCS 12, pp. 214 226, New York, NY, USA, 2012. Association for Computing Machinery. ISBN 9781450311151. doi: 10.1145/2090236.2090255. URL https://doi.org/10.1145/2090236.2090255.

Harrison Edwards and Amos Storkey. Censoring representations with an adversary. In International Conference in Learning Representations (ICLR2016), pp. 1 14, May 2016. URL https://iclr.cc/archive/www/ doku.php%3Fid=iclr2016:main.html. 4th International Conference on Learning Representations, ICLR 2016 ; Conference date: 02-05-2016 Through 04-05-2016.

Michael Feldman, Sorelle A Friedler, John Moeller, Carlos Scheidegger, and Suresh Venkatasubramanian. Certifying and removing disparate impact. In proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pp. 259 268, 2015.

Benjamin Fish, Jeremy Kun, and Ádám D Lelkes. A confidence-based approach for balancing fairness and accuracy. In Proceedings of the 2016 SIAM International Conference on Data Mining, pp. 144 152. SIAM, 2016.

Rémi Flamary, Nicolas Courty, Alexandre Gramfort, Mokhtar Z. Alaya, Aurélie Boisbunon, Stanislas Chambon, Laetitia Chapel, Adrien Corenflos, Kilian Fatras, Nemo Fournier, Léo Gautheron, Nathalie T.H. Gayraud, Hicham Janati, Alain Rakotomamonjy, Ievgen Redko, Antoine Rolet, Antony Schutz, Vivien Seguy, Danica J.

Published in Transactions on Machine Learning Research (12/2024)

Sutherland, Romain Tavenard, Alexander Tong, and Titouan Vayer. Pot: Python optimal transport. Journal of Machine Learning Research, 22(78):1 8, 2021. URL http://jmlr.org/papers/v22/20-451.html.

Aden Forrow, Jan-Christian Hütter, Mor Nitzan, Philippe Rigollet, Geoffrey Schiebinger, and Jonathan Weed. Statistical optimal transport via factored couplings. In Kamalika Chaudhuri and Masashi Sugiyama (eds.), Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, volume 89 of Proceedings of Machine Learning Research, pp. 2454 2465. PMLR, 16 18 Apr 2019. URL https://proceedings.mlr.press/v89/forrow19a.html.

Aude Genevay, Marco Cuturi, Gabriel Peyré, and Francis Bach. Stochastic optimization for large-scale optimal transport. In Proceedings of the 30th International Conference on Neural Information Processing Systems, NIPS 16, pp. 3440 3448, Red Hook, NY, USA, 2016. Curran Associates Inc. ISBN 9781510838819.

Gabriel Goh, Andrew Cotter, Maya Gupta, and Michael P Friedlander. Satisfying real-world goals with dataset constraints. In Advances in Neural Information Processing Systems, pp. 2415 2423, 2016.

Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K.Q. Weinberger (eds.), Advances in Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014. URL https://proceedings.neurips.cc/paper/2014/file/ 5ca3e9b122f61f8f06494c97b1afccf3-Paper.pdf.

Paula Gordaliza, Eustasio Del Barrio, Gamboa Fabrice, and Jean-Michel Loubes. Obtaining fairness using optimal transport theory. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 2357 2365. PMLR, 09 15 Jun 2019. URL https://proceedings.mlr.press/v97/gordaliza19a.html.

Moritz Hardt, Eric Price, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning. In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 29. Curran Associates, Inc., 2016a. URL https://proceedings.neurips.cc/ paper/2016/file/9d2682367c3935defcb1f9e247a97c0d-Paper.pdf.

Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning. In Advances in neural information processing systems, pp. 3315 3323, 2016b.

Deborah Hellman. Measuring algorithmic fairness. Criminal Procedure e Journal, 2019. URL https: //api.semanticscholar.org/Corpus ID:199002104.

Jan-Christian Hütter and Philippe Rigollet. Minimax estimation of smooth optimal transport maps. The Annals of Statistics, 49(2):1166 1194, 2021. doi: 10.1214/20-AOS1997. URL https://doi.org/10.1214/ 20-AOS1997.

David Ingold and Spencer Soper. Amazon doesn t consider the race of its customers. should it. Bloomberg, April, 1, 2016.

Ray Jiang, Aldo Pacchiano, Tom Stepleton, Heinrich Jiang, and Silvia Chiappa. Wasserstein fair classification. In Uncertainty in Artificial Intelligence, pp. 862 872. PMLR, 2020a.

Ray Jiang, Aldo Pacchiano, Tom Stepleton, Heinrich Jiang, and Silvia Chiappa. Wasserstein fair classification. In Ryan P. Adams and Vibhav Gogate (eds.), Proceedings of The 35th Uncertainty in Artificial Intelligence Conference, volume 115 of Proceedings of Machine Learning Research, pp. 862 872. PMLR, 22 25 Jul 2020b. URL https://proceedings.mlr.press/v115/jiang20a.html.

Faisal Kamiran, Asim Karim, and Xiangliang Zhang. Decision theory for discrimination-aware classification. In 2012 IEEE 12th International Conference on Data Mining, pp. 924 929. IEEE, 2012.

Toshihiro Kamishima, Shotaro Akaho, Hideki Asoh, and Jun Sakuma. Fairness-aware classifier with prejudice remover regularizer. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 35 50. Springer, 2012.

Published in Transactions on Machine Learning Research (12/2024)

Lev Kantorovich. On the translocation of masses. Journal of Mathematical Sciences, 133:1381 1382, 2006.

Michael Kearns, Seth Neel, Aaron Roth, and Zhiwei Steven Wu. An empirical study of rich subgroup fairness for machine learning, 2018a.

Michael Kearns, Seth Neel, Aaron Roth, and Zhiwei Steven Wu. Preventing fairness gerrymandering: Auditing and learning for subgroup fairness. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 2564 2572. PMLR, 10 15 Jul 2018b. URL https://proceedings.mlr.press/v80/kearns18a.html.

Dongha Kim, Kunwoong Kim, Insung Kong, Ilsang Ohn, and Yongdai Kim. Learning fair representation with a parametric integral probability metric. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 11074 11101. PMLR, 17 23 Jul 2022a. URL https://proceedings.mlr.press/v162/kim22b.html.

Kunwoong Kim, Ilsang Ohn, Sara Kim, and Yongdai Kim. Slide: A surrogate fairness constraint to ensure fairness consistency. Neural Networks, 154:441 454, 2022b. ISSN 0893-6080. doi: https: //doi.org/10.1016/j.neunet.2022.07.027. URL https://www.sciencedirect.com/science/article/pii/ S0893608022002891.

Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization, 2014. URL https: //arxiv.org/abs/1412.6980.

Jon Kleinberg, Jens Ludwig, Sendhil Mullainathan, and Ashesh Rambachan. Algorithmic fairness. In Aea papers and proceedings, volume 108, pp. 22 27, 2018.

Martin Knott and C. S. Smith. On the optimal mapping of distributions. Journal of Optimization Theory and Applications, 43:39 49, 1984.

Matt J. Kusner, Joshua R. Loftus, Chris Russell, and Ricardo Silva. Counterfactual fairness, 2017. URL https://arxiv.org/abs/1703.06856.

Yujia Li, Kevin Swersky, and Rich Zemel. Generative moment matching networks. In Francis Bach and David Blei (eds.), Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pp. 1718 1727, Lille, France, 07 09 Jul 2015. PMLR. URL https://proceedings.mlr.press/v37/li15.html.

David Madras, Elliot Creager, Toniann Pitassi, and Richard S. Zemel. Learning adversarially fair and transferable representations. In ICML, 2018.

Ninareh Mehrabi, Fred Morstatter, Nripsuta Saxena, Kristina Lerman, and Aram Galstyan. A survey on bias and fairness in machine learning. ar Xiv preprint ar Xiv:1908.09635, 2019.

Anay Mehrotra, Bary S. R. Pradelski, and Nisheeth K. Vishnoi. Selection in the presence of implicit bias: The advantage of intersectional constraints. In Proceedings of the 2022 ACM Conference on Fairness, Accountability, and Transparency, FAcc T 22, pp. 599 609, New York, NY, USA, 2022. Association for Computing Machinery. ISBN 9781450393522. doi: 10.1145/3531146.3533124. URL https://doi.org/10. 1145/3531146.3533124.

Mathieu Molina and Patrick Loiseau. Bounding and approximating intersectional fairness through marginal fairness. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022. URL https://openreview.net/forum?id=Lff Wu Gt C9BE.

Gaspard Monge. Mémoire sur la théorie des déblais et des remblais. De l Imprimerie Royale, 1781.

Sérgio Moro, Paulo Cortez, and Paulo Rita. A data-driven approach to predict the success of bank telemarketing. Decision Support Systems, 62:22 31, 2014. ISSN 0167-9236. doi: https://doi.org/10.1016/j.dss.2014. 03.001. URL https://www.sciencedirect.com/science/article/pii/S016792361400061X.

Published in Transactions on Machine Learning Research (12/2024)

Carlos Mougan, Antonio Ferrara, Laura State, Salvatore Ruggieri, and Steffen Staab. Beyond demographic parity: Redefining equal treatment, 2024. URL https://openreview.net/forum?id=c Vea4KQ4xm.

Hamed Nilforoshan, Johann D Gaebler, Ravi Shroff, and Sharad Goel. Causal conceptions of fairness and their consequences. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 16848 16887. PMLR, 17 23 Jul 2022. URL https://proceedings.mlr.press/v162/nilforoshan22a.html.

I. Olkin and F. Pukelsheim. The distance between two random vectors with given dispersion matrices. Linear Algebra and its Applications, 48:257 263, 1982. ISSN 0024-3795. doi: https://doi.org/10.1016/0024-3795(82) 90112-4. URL https://www.sciencedirect.com/science/article/pii/0024379582901124.

Felix Petersen, Debarghya Mukherjee, Yuekai Sun, and Mikhail Yurochkin. Post-processing for individual fairness, 2021. URL https://arxiv.org/abs/2110.13796.

Geoff Pleiss, Manish Raghavan, Felix Wu, Jon Kleinberg, and Kilian Q Weinberger. On fairness and calibration. In Advances in Neural Information Processing Systems, pp. 5680 5689, 2017.

Tai Le Quy, Arjun Roy, Vasileios Iosifidis, Wenbin Zhang, and Eirini Ntoutsi. A survey on datasets for fairness-aware machine learning. WIREs Data Mining and Knowledge Discovery, 12(3), mar 2022. doi: 10.1002/widm.1452. URL https://doi.org/10.1002%2Fwidm.1452.

Svetlozar T Rachev and Ludger Rüschendorf. Mass Transportation Problems: Volume I: Theory, volume 1. Springer Science & Business Media, 1998.

Tim Salimans, Han Zhang, Alec Radford, and Dimitris Metaxas. Improving gans using optimal transport, 2018.

Changjian Shui, Gezheng Xu, Qi CHEN, Jiaqi Li, Charles Ling, Tal Arbel, Boyu Wang, and Christian Gagné. On learning fairness and accuracy on multiple subgroups. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022. URL https://openreview.net/forum?id=Ys RH6u Vcx2l.

Chiappa Silvia, Jiang Ray, Stepleton Tom, Pacchiano Aldo, Jiang Heinrich, and Aslanides John. A general approach to fairness with optimal transport. Proceedings of the AAAI Conference on Artificial Intelligence, 34(04):3633 3640, Apr. 2020. doi: 10.1609/aaai.v34i04.5771. URL https://ojs.aaai.org/index.php/ AAAI/article/view/5771.

Joshua Simons, Sophia Adams Bhatti, and Adrian Weller. Machine learning and the meaning of equal treatment. In Proceedings of the 2021 AAAI/ACM Conference on AI, Ethics, and Society, AIES 21, pp. 956 966, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 9781450384735. doi: 10.1145/3461702.3462556. URL https://doi.org/10.1145/3461702.3462556.

Zhengyu Su, Yalin Wang, Rui Shi, Wei Zeng, Jian Sun, Feng Luo, and Xianfeng Gu. Optimal mass transport for shape matching and comparison. IEEE Transactions on Pattern Analysis and Machine Intelligence, 37 (11):2246 2259, 2015. doi: 10.1109/TPAMI.2015.2408346.

Paul Van der Laan. The 2001 Census in the Netherlands: Integration of Registers and Surveys, pp. 39 52. 12 2001.

C. Villani. Optimal Transport: Old and New. Grundlehren der mathematischen Wissenschaften. Springer Berlin Heidelberg, 2008. ISBN 9783540710509. URL https://books.google.co.kr/books?id=h V8o5R7_5tk C.

J. von Kügelgen, A.-H. Karimi, U. Bhatt, I. Valera, A. Weller, and B. Schölkopf. On the fairness of causal algorithmic recourse. In Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI), pp. 9584 9594. AAAI Press, February 2022. URL https://sites.google.com/view/recourse21/home. *also at ICML 2021 Workshop Algorithmic Recourse and Neur IPS 2020 Workshop Algorithmic Fairness through the Lens of Causality and Interpretability (AFCI).

Published in Transactions on Machine Learning Research (12/2024)

Sandra Wachter, Brent Mittelstadt, and Chris Russell. Bias preservation in machine learning: the legality of fairness metrics under eu non-discrimination law. W. Va. L. Rev., 123:735, 2020.

Kellie Webster, Marta Recasens, Vera Axelrod, and Jason Baldridge. Mind the gap: A balanced corpus of gendered ambiguous pronouns. Transactions of the Association for Computational Linguistics, 6:605 617, 2018.

Dennis Wei, Karthikeyan Natesan Ramamurthy, and Flavio Calmon. Optimized score transformation for fair classification. volume 108 of Proceedings of Machine Learning Research, pp. 1673 1683, Online, 26 28 Aug 2020. PMLR. URL http://proceedings.mlr.press/v108/wei20a.html.

Yongkai Wu, Lu Zhang, and Xintao Wu. On convexity and bounds of fairness-aware classification. In The World Wide Web Conference, WWW 19, pp. 3356 3362, New York, NY, USA, 2019. Association for Computing Machinery. ISBN 9781450366748. doi: 10.1145/3308558.3313723. URL https://doi.org/10. 1145/3308558.3313723.

Depeng Xu, Shuhan Yuan, Lu Zhang, and Xintao Wu. Fairgan: Fairness-aware generative adversarial networks. In 2018 IEEE International Conference on Big Data (Big Data), pp. 570 575. IEEE, 2018.

Gal Yona and Guy Rothblum. Probably approximately metric-fair learning. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 5680 5688. PMLR, 10 15 Jul 2018. URL https://proceedings.mlr. press/v80/yona18a.html.

Mikhail Yurochkin and Yuekai Sun. Sensei: Sensitive set invariance for enforcing individual fairness. In International Conference on Learning Representations, 2021. URL https://openreview.net/forum?id= Dkt Zb97_Fx.

Mikhail Yurochkin, Amanda Bower, and Yuekai Sun. Training individually fair ml models with sensitive subspace robustness. In International Conference on Learning Representations, 2020. URL https: //openreview.net/forum?id=B1gdkx HFDH.

Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rogriguez, and Krishna P Gummadi. Fairness constraints: Mechanisms for fair classification. In Artificial Intelligence and Statistics, pp. 962 970, 2017.

Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez-Rodriguez, and Krishna P Gummadi. Fairness Constraints: A Flexible Approach for Fair Classification. J. Mach. Learn. Res., 20(75):1 42, 2019.

Rich Zemel, Yu Wu, Kevin Swersky, Toni Pitassi, and Cynthia Dwork. Learning fair representations. In Sanjoy Dasgupta and David Mc Allester (eds.), Proceedings of the 30th International Conference on Machine Learning, volume 28 of Proceedings of Machine Learning Research, pp. 325 333, Atlanta, Georgia, USA, 17 19 Jun 2013. PMLR. URL https://proceedings.mlr.press/v28/zemel13.html.

Brian Hu Zhang, Blake Lemoine, and Margaret Mitchell. Mitigating unwanted biases with adversarial learning. In Proceedings of the 2018 AAAI/ACM Conference on AI, Ethics, and Society, AIES 18, pp. 335 340, New York, NY, USA, 2018. Association for Computing Machinery. ISBN 9781450360128. doi: 10.1145/3278721.3278779. URL https://doi.org/10.1145/3278721.3278779.

Yuyin Zhou, Shih-Cheng Huang, Jason Alan Fries, Alaa Youssef, Timothy J. Amrhein, Marcello Chang, Imon Banerjee, Daniel Rubin, Lei Xing, Nigam Shah, and Matthew P. Lungren. Radfusion: Benchmarking performance and fairness for multimodal pulmonary embolism detection from ct and ehr, 2021. URL https://arxiv.org/abs/2111.11665.

Published in Transactions on Machine Learning Research (12/2024)

A Proofs of theorems

Let N be the set of natural numbers. For s = 0,1 and any measurable set A [0,1], we denote f 1 s (A) = {x Xs f(x,s) A}. Recall that Xs is the domain of X S = s.

Proposition 3.1 For any perfectly group-fair model f, i.e., Pf0 = Pf1, there exists a transport map Ts = Ts(f) satisfying f (X,s) = f (Ts(X),s ),a.e.

Proof of Proposition 3.1. By letting δ = 0, Theorem 3.3 below implies Es f (X,s) f (Ts(X),s ) = 0. This implies that f (X,s) f (Ts(X),s ) = 0 almost everywhere, which concludes the proof.

Theorem 3.3 Fix a fairness level δ 0. For any given group-fair model f such that TVDP(f) δ, there exists a transport map Ts T trans s satisfying MDP(f,Ts) 2δ.

Proof of Theorem 3.3. Without loss of generality, let s = 0 and s = 1. Let F0 [0,1] [0,1] and F1 [0,1] [0,1] denote the cumulative distribution functions (CDFs) of f(X,0) S = 0 and f(X,1) S = 1, respectively. Note that F0 and F1 have at most countably many discontinuity points.

Define Ds as the set of all discontinuity points of Fs, which is countable. For each t Ds, define the jump at t as Fs(t) = Fs(t) Fs(t ), where Fs(t ) denotes the left limit of Fs at t.

Define the sub-CDF (i.e., the continuous part of Fs) as: F cont s (v) = Fs(v) t Ds,t v Fs(t) for v [0,1]. Note that this function F cont s is continuous and non-decreasing on [0,1]. Moreover, for any interval (a,b] [0,1], define F cont s ((a,b]) = F cont s (b) F cont s (a).

We here prove for the case when F cont 1 (1) F cont 0 (1). The other case F cont 1 (1) > F cont 0 (1) can be treated similarly.

1. (Constructing subsets based on F cont s ) Since F cont 1 (1) F cont 0 (1), there exists z 1 such that F cont 1 (1) = F cont 0 (z). We partition the interval [0,z] into subintervals of length at most δ. Let v0 = 0 and define vk = min{vk 1 + δ,z} for k = 1,...,m. Here, m N is the number that satisfies vm = z. Note that F cont 1 (1) = m k=1 F cont 1 ((vk 1,vk]).

For each k {1,...,m}, we compare the measures of the intervals as follows.

If F cont 1 ((vk 1,vk]) F cont 0 ((vk 1,vk]), then there exists zk [vk 1,vk] such that F cont 1 ((vk 1,vk]) = F cont 0 ((vk 1,zk]). Define X0,k = f 1 0 ((vk 1,zk] D0) and X1,k = f 1 1 ((vk 1,vk] D1).

If F cont 1 ((vk 1,vk]) > F cont 0 ((vk 1,vk]), we can define zk, X0,k and X1,k similarly.

2. (Defining probability measures and transport maps on subsets) For each k {1,...,m}, define probability measures Ps,k,s {0,1} such that Ps,k(A) = Ps(A Xs,k)

Ps(Xs,k) for measurable subsets A X.

By Brenier s Theorem (Villani, 2008; Hütter & Rigollet, 2021), there exists a transport map T(1) 0,k from P0,k( ) to P1,k( ), under (C). Since vk vk 1 δ, k, we have that

f(x,0) f(T(1) 0,k(x),1) δ, x X0,k. (8)

3. (Handling discontinuity points) Let D0,1 = D0 D1 be the intersection of D0 and D1, which is the set of common discontinuity points.

Fix d D0,1. Suppose that P1(f 1 1 ({d})) P0(f 1 0 ({d})). Then, there exists f 1 0 ({d}) f 1 0 ({d}) such that P0(f 1 0 ({d}) ) = P1(f 1 1 ({d})). Define X0,d = f 1 0 ({d}) and X1,d = f 1 1 ({d}). We can define X0,d and X1,d similarly when P1(f 1 1 ({d})) > P0(f 1 0 ({d})).

For each d D0,1, we define probability measures Ps,d,s {0,1} such that Ps,d(A) = Ps(A Xs,d)/Ps( Xs,d) for measurable subsets A X. Then, there exists a transport map T(2) 0,d from P0,d( ) to P1,d( ). By the definition of X0,d, we have that

f(x,0) = f(T(2) 0,d(x),1) = d, x X0,d. (9)

Published in Transactions on Machine Learning Research (12/2024)

4. (Constructing the complement parts) We collect the complements as

m k=1 X0,k d D0,1 X0,d and X 1 = X1

m k=1 X1,k d D0,1 X1,d .

Because P0( m k=1 X0,k) = P1( m k=1 X1,k) and P0( d D0,1 X0,d) = P1( d D0,1 X1,d), we have P0(X 0) = 1 P0( k {1,...,m} X0,k) P0( d D0,1 X0,d) = P1(X 1) δ.

Define probability measures P s,s {0,1} on X s,s {0,1} such that P s(A) = Ps(A X s) Ps(X s) for measurable

subsets A X. Then, there exists a transport map T(3) 0 from P 0( ) to P 1( ).

For x X 0, we have P0(X 0) = 1 ( m k=1 P0(X0,k) + d D0,1 P0( X0,d)) δ, since TVDP(f) = TV(Pf(X,0) S=0,Pf(X,1) S=1) δ. Furthermore, since f( ) [0,1], we have that

E0 ( f(X,0) f(T(3) 0 (X),1) 1(X X 0)) = f(X,0) f(T(3) 0 (X),1) 1(X X 0)d P0(X)

1(X X 0)d P0(X) = P0(X 0) δ. (10)

5. (Overall transport map) Finally, combining 2 to 4 above, we define the (overall) transport map T0 as

T0( ) = m k=1 T(1) 0,k( )1( X0,k) + d D0,1 T(2) 0,d( )1( X0,d) + T(3) 0 ( )1( X 0). (11)

We note that {{X0,k}m k=1,{ X0,d}d D0,1,X 0} and {{X1,k}m k=1,{ X1,d}d D0,1,X 1} are partitions of X0 and X1, respectively. Moreover, P0(X0,k) = P1(X1,k), k, P0( X0,d) = P1( X1,d), d, and P0(X 0) = P1(X 1). Hence, T0 is a transport map from P0 to P1.

6. (Calculation of the bound for MDP(f,T0)) Using the constructed transport map T0, we have that

MDP(f,T0) = E0 f(X,0) f(T0(X),1) = f(X,0) f(T0(X),1) d P0(X)

= m k=1 X0,k f(x,0) f(T(1) 0,k(x),1) d P0(x)

+ d D0,1 X0,d f(X,0) f(T(2) 0,d(x),1) d P0(x)

+ X 0 f(x,0) f(T(3) 0 (x),1) d P0(x)

( ) δ m k=1 P0(X0,k) + X 0 f(x,0) f(T(3) 0 (x),1) d P0(x)

δ + δ = 2δ,

where (*) holds by the inequalities in (8), (9), and (10).

Published in Transactions on Machine Learning Research (12/2024)

Theorem 3.3 without the condition (C): the case when P0 and P1 are discrete The condition (C) is assumed for easier discussion involving continuous distributions. This is because the existence of (deterministic) transport maps is not guaranteed when the distributions P0 and P1 are discrete and their supports are different. However, by using the notion of stochastic transport map (defined below), we can derive a theoretical result similar to Theorem 3.3 when P0 and P1 are discrete.

Let X0 = {x(0) 1 ,...,x(0) n0 } and X1 = {x(1) 1 ,...,x(1) n1 }. For this time only, define P0 and P1 as the empirical distributions on D0 and D1, respectively. Let X0 and X1 be the random variables following P0 and P1, respectively. Furthermore, let f(X0) = {f(x,0) x X0} and f(X1) = {f(x,1) x X1}. Denote Pf0 and Pf1 be the empirical distributions on f(X0) and f(X1), i.e., the distributions of f(X0),X0 P0 and f(X1),X1 P1, respectively.

For a given joint distribution Q between X0 and X1, we can define MDP(f,Q) = E(X0,X1) Q f(X0,0) f(X1,1) , which is a general version of MDP(f,Ts). That is, instead of the deterministic (one-to-one) transport map, we define the stochastic transport map Ts defined by Ts(x(s) i ) = x(s ) j with probability

Q(Xs = x(s) i ,Xs = x(s ) j ).

In Proposition A.1 below, we show that a stochastic transport map a joint distribution Q (rather than the deterministic transport map) exists and satisfies MDP(f,Q) δ. This is analogous to the result MDP(f,Ts) δ presented in Theorem 3.3. Note that if n0 = n1, there exist transport maps (i.e., one-to-one mappings or permutations) between X0 and X1.

Proposition A.1. Assume the supports of Pf0 and Pf1 share m( n0,n1) number of common points. Then, for any given group-fair model f such that TVDP(f) δ, there exists a joint distribution Q between X0 and X1 satisfying MDP(f,Q) δ.

Proof. If suffices to show that there exists Q such that MDP(f,Q) TVDP(f). Without loss of generality, assume n0 n1 and let f(x(0) i ,0) = f(x(1) i ,1) for i {1,...,m} (i.e., the common points).

First, we calculate TVDP(f) as follows. Recall the definition of TV for discrete measures: TV(Pf0,Pf1) = 1 2 z Pf0(z) Pf1(z) . For the m number of common points, the sum of differences is m 1

n0 1 n1 = m n1 n0

n0n1 . For the points only in f(X0) but not in f(X1), the sum of differences is (n0 m)/n0. Similarly, for the points only in f(X1) but not in f(X0), the sum of differences is (n1 m)/n1. As a result, we have

TVDP(f) = TV(Pf0,Pf1) = 1

n0n1 + n0 m

Then, we construct Q as follows. Let γi,j = Q(X0 = x(0) i ,X1 = x(1) j ) and Γ = [γi,j]i [n0],j [n1] Rn0 n1 + be a matrix based on γi,js, which we construct as below:

1. Build a diagonal matrix Γ11 = 1 n1 Im Rm m + , where Im is the identity matrix of size m m.

2. Build a zero matrix Γ21 = 0(n0 m) m R(n0 m) m + , where 0 denotes the zero matrix.

3. Build matrices Γ12 Rm (n1 m) + and matrix Γ22 R(n0 m) (n1 m) + satisfying Γ121n1 m = ( 1

n0 1 n1 )1m,

Γ221n1 m = 1 n0 1n0 m, and (Γ12 Γ22)

1n0 = 1 n1 1n1 m.

4. Complete Γ = (Γ11 Γ12 Γ21 Γ22) = (

1 n1 Im Γ12 0(n0 m) m Γ22).

Last, note that the Γ is a coupling matrix (i.e., satisfying the constraints n0 i=1 γi,j = 1/n0, j [n1] and n1 j=1 γi,j = 1/n1, i [n0]). Hence, we can define the joint distribution Q by the constructed Γ (i.e., Γ is a

Published in Transactions on Machine Learning Research (12/2024)

matrix representation of Q, see equation (5) for the formulation). Finally, we have

MDP(f,Q) = E(X0,X1) Q f(X0,0) f(X1,1)

= i,j Q(X0 = x(0) i ,X1 = x(1) j ) f(X0,0) f(X1,1) = i,j γi,j f(X0,0) f(X1,1)

= i [m],j [m] γi,j f(X0,0) f(X1,1) + i, {m+1,...,n0},j [m] γi,j f(X0,0) f(X1,1)

+ i [n0],j {m+1,...,n1} γi,j f(X0,0) f(X1,1)

= i [n0],j {m+1,...,n1} γi,j f(X0,0) f(X1,1) i [n0],j {m+1,...,n1} γi,j = 1 m

n1 TVDP(f).

Therefore, any Q constructed by the steps 1-4 above satisfies MDP(f,Q) δ.

Proposition 3.5. Let Tf be the fair matching function of f on D0 and D1 (where the empirical distributions with respect to D0 and D1 are used in Definition 3.4). Then, the matched individual Tf(x) of any x Ds is obtained by Tf(x) = f 1 s F 1 s Fs fs(x).

Proof of Theorem 3.5. First, we aim to find a permutation map M = arg min M m i=1 fs(xi) M(fs (xi)) subject to {M(fs(xi)) xi Ds} = {fs (xj) xj Ds }. By Rachev & Rüschendorf (1998); Chzhen et al. (2020); Jiang et al. (2020b), we have the fact that 1-Wasserstein distance is equivalent to the average of difference between two prediction scores that have same quantiles in each group. That is, M (y) = F 1 s Fs(y) for any y {fs(x) x Ds}.

Second, we have M is one-to-one and {fs (xj) xj Ds } = {fs(Tf(xi)) xi Ds} = {M (fs(xi)) xi Ds}, since Tf is also an exact one-to-one map.

Therefore, we conclude that Tf(x) = f 1 s M fs(x) = f 1 s F 1 s Fs fs(x) for all x Ds.

Remark A.2. Using Proposition 3.5 to estimate the fair matching function is equivalent to estimating the OT map between two score distributions. The statistical convergence rate for estimating the OT map between one-dimensional distributions is fast; it is of the order O( D0 1/2 + D1 1/2) = O(n 1/2 0 + n1/2 1 ) (Chizat et al., 2020; Deb et al., 2021; Hütter & Rigollet, 2021). When we use two mini-batches D0 D0 and D1 D1 with identical size m, the order becomes O(m 1/2). This indicates that sufficiently large mini-batch size m can guarantee accurate estimation.

Published in Transactions on Machine Learning Research (12/2024)

Theorem 3.7 For a given Ts T trans s , if MDP(f,Ts) δ, then we have WDP(f) δ and DP(f) δ.

Proof of Theorem 3.7. Fix f {f F Es f(X,s) f(Ts(X),s ) δ}. Let L1 the set of all 1-Lipschitz functions. Using the fact that Wasserstein-1 distance is equivalent to IPM induced by set of 1-Lipschitz function (Villani, 2008), we have that

WDP(f) = W (Pf(X,0) S=0,Pf(X,1) S=1)

= sup u L1 Es(u f(X,s)) Es (u f(X,s ))

sup u L1 Es(u f(X,s)) Es(u f(Ts(X),s )) + sup u L1 Es(u f(Ts(X),s )) Es (u f(X,s ))

sup u L1 Es u f(X,s) u f(Ts(X),s ) + sup u L1 Es(u f(Ts(X),s )) Es (u f(X,s ))

u L1 Es f(X,s) f(Ts(X),s ) + sup u L1 Es(u f(Ts(X),s )) Es (u f(X,s ))

δ + sup u L1 Es(u f(Ts(X),s )) Es (u f(X,s ))

δ + sup f F sup u L1 Es(u f(Ts(X),s )) Es (u f(X,s ))

δ + TV(Ts#Ps,Ps ) = δ. (15)

The last equality holds since TV(Ts#Ps,Ps ) = 0 for any transport map Ts. For DP(f), because the identity map is 1-Lipschitz, we have that DP(f) WDP(f), which completes the proof.

Published in Transactions on Machine Learning Research (12/2024)

Theorem 4.2 Suppose F is the collection of L-Lipschitz functions. Let A be a given subset in X. Then, for all f satisfying MDP(f,Tf s) δ, we have

DPA(f) L(Es X Tf s(X) 2)

1 2 + TV(P0,A,P1,A) + Uδ, (16)

where Ps,A is the distribution of X S = s,X A, and U > 0 is a constant only depending on A and Ps,s = 0,1.

Proof. We write Ts = Tf s for notational simplicity.

E(f(X,0) S = 0,X A) E(f(X,1) S = 1,X A)

E(f(X,0) S = 1,X A) E(f(T1(X),0) S = 1,X A)

+ E(f(T1(X),0) S = 1,X A) E(f(X,1) S = 1,X A)

+ E(f(X,0) S = 0,X A) E(f(X,0) S = 1,X A) .

By (C1), the first term is bounded by LE1 X T1(X) , which is also bounded by L(E1 X T1(X) 2) 1/2 .

The second term is bounded by δ up to a constant for all f satisfying MDP(f,Ts) δ. That is, we have

E(f(T1(X),0) S = 1,X A) E(f(X,1) S = 1,X A)

= f(T1(X),0)I(X A)d P1(X)

I(X A)d P1(X) f(X,1)I(X A)d P1(X)

I(X A)d P1(X)

I(X A)d P1(X) X A f(T1(X),0) f(X,1) d P1(X)

I(X A)d P1(X) X X f(T1(X),0) f(X,1) d P1(X)

= U (A,P1) E1 f(T1(X),0) f(X,1)

where U (A,P1) = 1/ I(X A)d P1(X) = 1/P(X A S = 1) is a constant only depending on P1 and A.

The third term E(f(X,0) S = 0,X A) E(f(X,0) S = 1,X A) is not controllable by either the transport map or δ but depends on the given distributions and A. That is,

E(f(X,0) S = 0,X A) E(f(X,0) S = 1,X A)

= A f(X,0)d P0(X) A f(X,0)d P1(X)

sup f F A f(X,0)d P0(X) A f(X,0)d P1(X)

TV(P0,A,P1,A).

Hence, we have

E(f(X,0) S = 0,X A) E(f(X,1) S = 1,X A)

L(E1 X T1(X) 2)1/2 + TV(P0,A,P1,A) + U (A,P1)δ. (20)

We can similarly derive

E(f(X,0) S = 0,X A) E(f(X,1) S = 1,X A)

L(E0 X T0(X) 2)1/2 + TV(P0,A,P1,A) + U (A,P0)δ. (21)

Letting U = max {U (A,P0),U (A,P1)} completes the proof.

Published in Transactions on Machine Learning Research (12/2024)

Lemma A.3 (Optimal transport map between two Gaussians). For mean vectors µX,µY Rd and covariance matrices ΣX,ΣY Rd d, the OT map from N(µX,ΣX) to N(µY,ΣY) is given as TOT(x) = WOTx + b OT

where WOT = Σ 1

2 X and b OT = µY WOTµX.

Proof. Consider the centered Gaussians, i.e., µX = µY at first. Based on Theorem 4 of Olkin & Pukelsheim

(1982), we have that W2 (N(0,ΣX),N(0,ΣY)) = Tr(ΣX + ΣY 2(Σ1/2 X ΣYΣ1/2 X ) 1/2 ) = Σ1/2 X Σ1/2 Y 2 F where is the Frobenius norm. Correspondingly, Knott & Smith (1984) derived the optimal transport map as

x Σ 1/2 X (Σ 1/2 X ΣYΣ1/2 X ) 1/2 Σ 1/2 X x.

Combining these results, we can extend the OT map formula of Gaussians with nonzero means as follows. Since E X Y 2 = E (X µX) (Y µY)+(µX µY) 2 = E (X µX) (Y µY) 2+ µX µY 2, the Wasserstein distance is given as W2 (N(µX,ΣX),N(µY,ΣY)) = µX µY 2+ Σ1/2 X Σ1/2 Y 2 F , and so the corresponding opti-

mal transport map is also given as x Σ 1/2 X (Σ 1/2 X ΣYΣ1/2 X ) 1/2 Σ 1/2 X x+µY Σ 1/2 X (Σ 1/2 X ΣYΣ1/2 X ) 1/2 Σ 1/2 X µX, which completes the proof.

Proposition 4.3 (Counterfactual fairness and the OT map) For all A having (Id A) 1, Ws becomes σs σ 1 s Id. That is, x CF s = x OT s .

Proof of Proposition 4.3. Once we observe x0, the randomness ϵ0 is observed as ϵ0 = B 1x0 µ0. By replacing the sensitive attribute on the randomness ϵ0, we obtain σ 1 1 (B 1 x CF 0 µ1) = σ 1 0 (B 1x0 µ0). Then, its counterfactual becomes x CF 0 = Bµ1 + σ1σ 1 0 Id(x0 Bµ0). Then, we prove Proposition 4.3 by showing the if and only if condition as follows.

W0 = (σ2 0BDB ) 1/2 ((σ2 0BDB )1/2σ2 1BDB (σ2 0BDB )1/2) 1/2 (σ2 0BDB ) 1/2

= σ1σ 1 0 (BDB ) 1/2 ((BDB )1/2BDB (BDB )1/2) 1/2 (BDB ) 1/2

= σ1σ 1 0 (BDB ) 1/2 ((BDB )2) 1/2 (BDB ) 1/2

= σ1σ 1 0 Id.

The same result can be done for x1. Hence, we conclude Ws = σs σ 1 s Id.

Published in Transactions on Machine Learning Research (12/2024)

B Disadvantage of high transport cost

This section presents an example of two completely different group-fair models where one is unreasonable and the other is reasonable, particularly in terms of subset fairness. This example suggests that not all group-fair models are acceptable, thereby emphasizing the necessity of finding group-fair models corresponding to favorable implicit transport maps.

Suppose that the distribution of the input variable is given as X S = s Unif(0,1), for s {0,1}. Consider the following two classification models: ˆf(x,s) = sign(2x 1)(1 2s)+1

2 and f(x,s) = sign(2x 1)+1

Figure 7: (Top) A group-fair model with the risk of discrimination on subsets. (Bottom) A group-fair model without the risk of discrimination on subsets.

It is clear that both ˆf and f are perfectly fair, i.e., P ˆ f0 = P ˆ f1 and P f0 = P f1. However, ˆf has a notable unfairness issue in its treatments of individuals within the subset {x 1/2} (as well as {x < 1/2}); for when x > 1/2, ˆf assigns label 1 for all individuals of s = 0 while it assigns label 0 for all individuals of s = 1. This indicates that ˆf discriminates against individuals in the subset {x 1/2} (and also {x < 1/2}). In contrast, f does not exhibit such undesirable discrimination against the subsets. Hence, we can say that f has less discrimination on the subsets than ˆf. Figure 7 provides a comparative illustration of ˆf and f.

The observed discrimination of ˆf on subsets can be attributed to the unreasonable fair matching function of ˆf. It turns out that the fair matching function of ˆf is T ˆ f(x) = x sign((2x 1)(1 2s))

2 . This function matches an individual in {x < 1

2,S = s} with one in {x 1

2,S = s }, who are far apart from each other. In contrast, the fair matching function of f is T f(x) = x. This example emphasizes the need of group-fair models whose fair matching function have low transport costs.

C The Kantorovich problem

As shortly introduced in Section 2.4, the Kantorovich problem is to find the optimal coupling (i.e., joint distribution) between two given distributions. It can be mathematically expressed as the following. For two given distributions Q1 and Q2, infπ Π(Q1,Q2) EX,Y π (c(X,Y)) where Π(Q1,Q2) is the set of all joint measures with marginals Q1 and Q2. Let c be the L2 cost function.

For given two empirical distributions on D0 = {x(0) i }n0 i=1 and D1 = {x(1) j }n1 j=1, we first define the cost matrix as

C = [ci,j] Rn0 n1 + , where ci,j = x(0) i x(1) j 2. Then, the solution of the Kantorovich problem, i.e., optimal joint distribution between the two distributions, is defined by the coupling matrix Γ = [γi,j] Rn0 n1 + , which is the minimizer of the following objective:

min Γ C Γ 1 = min γi,j ci,jγi,j s.t. γi,j 0,

n0 i=1 γi,j = 1

n1 j=1 γi,j = 1

In fact, the Kantorovich problem can be solved by linear programming (Kantorovich, 2006; Villani, 2008). To solve the linear program, we use practical implementation such as POT library in Python.

Published in Transactions on Machine Learning Research (12/2024)

D Implementation details

In this section, we provide detailed descriptions for the implementation of the experiments.

D.1 Datasets

First, the URLs of these datasets are provided.

Adult: the Adult income dataset (Dua & Graff, 2017) can be downloaded from the UCI repository3.

German: the German credit dataset (Dua & Graff, 2017) can be downloaded from the UCI repository4.

Dutch: the Dutch census dataset can be downloaded from the public Github of Quy et al. (2022) 5.

Bank: the Bank marketing dataset can be downloaded from the UCI repository6.

The following Table 6 describes the basic information of the four datasets. Table 6: The description of the real benchmark tabular datasets: Adult, German, Bank, and Dutch. X,S,Y and d denote the input features, the sensitive attribute, the target label information, and the dimension of X, respectively. Train/Test sizes are the number of samples in the training and test datasets, respectively.

Dataset Variable Description Dataset Variable Description

X Personal attributes

X Personal attributes S Gender S Gender Y Outcome over $50k Y High credit score d 101 d 60 Train/Test size 30,136/15,086 Train/Test data size 800/200

X Personal attributes

X Personal attributes S Binarized age S Gender Y Subscribing a term deposit Y High-level occupation d 57 d 58 Train/Test size 24,390/6,098 Train/Test data size 48,336/12,084

Second, we describe pre-processing method of the datasets used. For Adult, German, and Bank datasets, we follow the pre-processing of the implementation of IBM s AIF360 (Bellamy et al., 2018) 7. For Dutch dataset, we follow the pre-processing of Quy et al. (2022) s Github8. Basically, continuous input variables are normalized by min-max scaling and categorical input variables are one-hot encoded. We set batch size as 1024, 200, 1024, and 512 for Adult, German, Dutch, and Bank datasets, respectively.

D.2 Algorithms

This section provides more detailed descriptions of the baseline algorithms used in our experiments.

Reduction (Agarwal et al., 2018): This algorithm is an in-processing method that learns a fair classifier with the lowest empirical fairness level DP. To implement this method for MLP model architecture, we employ Fair Torch9. It minimizes cross-entropy + λ Reduction regularizer for a given λ > 0.

Reg (Donini et al., 2018; Chuang & Mroueh, 2021): This method is a regularizing approach that minimizes cross-entropy + λ DP 2 for a given λ > 0. In Chuang & Mroueh (2021), they call this algorithm Gap Reg. This is also similar to the approach of Donini et al. (2018) in the sense that the model is learned with a constraint having a given level of DP.

3https://archive.ics.uci.edu/ml/datasets/adult 4https://archive.ics.uci.edu/ml/datasets/statlog+(german+credit+data) 5https://github.com/tailequy/fairness_dataset/tree/main/experiments/data/dutch.csv 6https://archive.ics.uci.edu/dataset/222/bank+marketing 7https://aif360.readthedocs.io/en/stable/ 8https://github.com/tailequy/fairness_dataset/tree/main/experiments/data/ 9https://github.com/wbawakate/fairtorch

Published in Transactions on Machine Learning Research (12/2024)

Adv (Zhang et al., 2018): This algorithm is an in-processing method that regularizes the model outputs with an adversarial network so that the adversarial network is learned to predict the sensitive attribute using the model outputs as the inputs. It minimizes cross-entropy + λ Adversarial loss for a given λ > 0.

Note that Reduction and Adv are ones of the most popular in-processing algorithms, as widely-used libraries AIF360 (Bellamy et al., 2018) and Fairlearn (Bird et al., 2020) provide the usage and implementation of the two algorithms. Reg is a vanilla approach of adding the regularization term in the loss function to learn the most accurate model among models satisfying a given level of group fairness.

We basically train models with various fairness levels by controlling the Lagrangian multiplier λ. The values are presented in the following table.

Table 7: Hyper-parameters used for controlling fairness levels for each algorithm.

Algorithm λ

Reduction {0.5, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 8.0, 10.0, 20.0, 30.0, 40.0, 50.0, 60.0, 80.0, 100.0, 150.0, 200.0, 300.0, 500.0} Reg {0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0, 1.2, 1.5, 1.8, 2.0, 3.0, 5.0, 10.0, 20.0, 50.0, 100.0} Adv {0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0, 1.1, 1.2, 1.3, 1.5, 2.0, 3.0, 5.0, 10.0, 15.0, 20.0, 30.0, 50.0, 100.0} FTM {0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0, 1.1, 1.2, 1.3, 1.5, 2.0, 3.0, 5.0, 10.0}

The Adam optimizer (Kingma & Ba, 2014) with an initial learning rate of 0.001 is used, and the learning rate is scheduled by multiplying 0.95 at each epoch.

D.3 Pseudo-code

Here, we provide a Pytorch-style psuedo code of calculating the MDP constraint in FTM.

Algorithm 1: Py Torch-style pseudo-code of calculating the MDP constraint in FTM. # xs, xt: input vectors from the source, target distribution, respectively. # model: a classifier to be trained import ot # The matching constraint: matching with the OT map weight_s = torch.ones(size=(xs.size(0), )) / xs.size(0) weight_t = torch.ones(size=(xt.size(0), )) / xt.size(0) # identical to weight_s M = ot.dist(xs, xt) G = ot.emd(weight_s, weight_t, M) matched_xs = xt[torch.argmax(G, dim=1)] output, matched_output = model(xs), model(matched_xs) FTM_REG = (output - matched_output).abs().mean()

Published in Transactions on Machine Learning Research (12/2024)

E Auxillary experimental results

In this section, we provide auxillary experimental results that are not displayed in the main body.

E.1 Fairness-prediction trade-off (Section 5.2.1)

Figure 8 shows the trade-offs between the fairness levels with respect to DP, DP and classification accuracy.

Figure 8: Fairness-prediction trade-offs: (Left to right) Adult, German, Dutch, Bank. (Top to bottom) DP vs. Acc, DP vs. Acc.

E.2 Improvement in subset fairness (Section 5.2.2)

Here, we provide experimental results showing fairness levels on subsets defined by input variables. Table 8 and 9 are copies of Table 1 with standard errors.

Table 8: Fairness on subsets defined by the input variable age: Fairness levels on subsets defined by the input variable age on German dataset under a given DP = 0.045 with standard errors (s.e.).

Algorithm Reduction Reg Adv FTM

DP (s.e.) 0.073 (0.015) 0.077 (0.013) 0.048 (0.020) 0.045 (0.021) DP (s.e.) 0.049 (0.006) 0.029 (0.008) 0.028 (0.012) 0.026 (0.006) WDP (s.e.) 0.053 (0.005) 0.039 (0.003) 0.042 (0.008) 0.038 (0.003)

DP (s.e.) 0.118 (0.035) 0.116 (0.037) 0.122 (0.047) 0.077 (0.032) DP (s.e.) 0.047 (0.015) 0.050 (0.009) 0.053 (0.017) 0.047 (0.007) WDP (s.e.) 0.058 (0.011) 0.059 (0.007) 0.061 (0.015) 0.054 (0.006)

Table 9: Fairness on subsets defined by the input variable marital status: Fairness levels on subsets defined by the input variable marital status on Dutch dataset under a given DP = 0.12 with standard errors (s.e.).

Algorithm Reduction Reg Adv FTM

DP (s.e.) 0.258 (0.005) 0.372 (0.003) 0.237 (0.083) 0.204 (0.003) DP (s.e.) 0.182 (0.002) 0.164 (0.001) 0.187 (0.073) 0.152 (0.002) WDP (s.e.) 0.183 (0.002) 0.172 (0.001) 0.193 (0.071) 0.152 (0.002)

Not married

DP (s.e.) 0.061 (0.007) 0.131 (0.006) 0.095 (0.038) 0.068 (0.005) DP (s.e.) 0.045 (0.002) 0.062 (0.003) 0.098 (0.035) 0.036 (0.003) WDP (s.e.) 0.045 (0.003) 0.072 (0.002) 0.098 (0.034) 0.045 (0.005)

Published in Transactions on Machine Learning Research (12/2024)

E.3 An additional advantage of using the marginal OT map: reducing the risk of self-fulfilling prophecy

We compare the risks of discrimination in the context of self-fulfilling prophecy in Dwork et al. (2012), a critical limitation that can arise when focusing solely on group fairness: unqualified individuals with relatively low scores can be chosen to be qualified, while other individuals with relatively high scores are chosen to be unqualified. To quantify the risk of self-fulfilling prophecy, we assume that the unfair model is optimal for predicting the true score of each individual. We consider the following two evaluation approaches under this assumption. For the transport map used in MDP constraint, we choose the marginal OT map.

(Evaluation 1) The first measure for the risk of self-fulfilling prophecy is the Spearman s rank correlation between unfair and fair prediction scores at each protected group: a higher rank correlation implies a lower risk of self-fulfilling prophecy. Table 10 shows that FTM has lower risks of suffering from self-fulfilling prophecy, in most cases.

Table 10: Spearman s correlation coefficients between the scores of the unfair model and group-fair models under fixed levels of DP with standard errors (s.e.). Bold faces are the best ones, and underlined ones are the second bests.

Dataset Adult German

DP 0.10 0.05

Sensitive attribute S 0 1 0 1

Reduction (s.e.) 0.935 (0.006) 0.987 (0.001) 0.996 (0.001) 0.997 (0.001) Reg (s.e.) 0.762 (0.087) 0.806 (0.084) 0.997 (0.000) 0.998 (0.000) Adv (s.e.) 0.876 (0.003) 0.979 (0.001) 0.986 (0.009) 0.986 (0.010) FTM (s.e.) 0.968 (0.003) 0.989 (0.001) 0.993 (0.002) 0.995 (0.001)

Dataset Dutch Bank

DP 0.01 0.02

Sensitive attribute S 0 1 0 1

Reduction (s.e.) 0.940 (0.001) 0.922 (0.001) 0.958 (0.010) 0.978 (0.005) Reg (s.e.) 0.872 (0.003) 0.972 (0.003) 0.784 (0.031) 0.974 (0.003) Adv (s.e.) 0.659 (0.171) 0.693 (0.185) 0.603 (0.207) 0.505 (0.238) FTM (s.e.) 0.973 (0.002) 0.991 (0.000) 0.964 (0.007) 0.979 (0.004)

Published in Transactions on Machine Learning Research (12/2024)

(Evaluation 2) For the second approach, we employ 2 2 confusion matrices to compare the predicted labels of the unfair and the group-fair models. In specific, in the privileged group S = 1, individuals predicted as ˆY = 0 (i.e., unqualified) by the unfair model but ˆY = 1 (i.e., chosen to be qualified) by the group-fair model are considered as undesirable instances in the context of self-fulfilling prophecy. Likewise, in the unprivileged group S = 0, individuals predicted as ˆY = 1 by the unfair model but ˆY = 0 by the group-fair model are similarly considered undesirable.

That is, for the risk of self-fulfilling prophecy, we count the number of individuals whose prediction is undesirably flipped (i.e., # of ˆY = 0 (Unfair) ˆY = 1 (Fair) for S = 1, and # of ˆY = 1 (Unfair) ˆY = 0 (Fair) for S = 0). Table 11 shows that the undesirable treatments of FTM are less observed than those of baseline methods, in most cases.

Table 11: 2 2 confusion matrices comparing the predicted labels of the unfair model and the group-fair models. The encircled numbers are the counts of undesirable instances. Bold faces are the best ones and underlined ones are the second bests.

Dataset ( DP) Adult (0.05) German (0.05) Dutch (0.15) Bank (0.04)

Unfair S = 1 ˆY = 0 ˆY = 1 ˆY = 0 ˆY = 1 ˆY = 0 ˆY = 1 ˆY = 0 ˆY = 1

Reduction ˆY = 0 6124 629 98 1 2170 662 5220 62 ˆY = 1 22 1701 1 32 8 3158 62 579

Reg ˆY = 0 6144 2198 99 8 2164 311 5265 229 ˆY = 1 2 132 0 25 14 3509 17 412

Adv ˆY = 0 6121 977 95 0 2152 1127 5255 516 ˆY = 1 25 1353 4 33 26 2693 27 125

FTM ˆY = 0 6146 1364 99 1 2174 862 5279 397 ˆY = 1 0 966 0 32 4 2958 3 244

Unfair S = 0 ˆY = 0 ˆY = 1 ˆY = 0 ˆY = 1 ˆY = 0 ˆY = 1 ˆY = 0 ˆY = 1

Reduction ˆY = 0 3486 13 54 3 4137 0 129 14 ˆY = 1 262 341 0 11 226 1723 1 31

Reg ˆY = 0 3748 104 54 4 4300 13 128 45 ˆY = 1 0 250 0 10 63 1710 2 0

Adv ˆY = 0 3655 52 53 3 3917 85 125 34 ˆY = 1 93 302 1 11 446 1638 5 11

FTM ˆY = 0 3719 11 54 3 4217 6 120 10 ˆY = 1 29 343 0 11 146 1717 10 35