{'fraction_non_alphanumeric': 0.03758420683018181, 'fraction_numerical': 0.010065804874242464, 'mean_word_length': 4.33851707858928, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Optimal Transport of Classifiers to Fairness

In past work on fairness in machine learning, the focus has been on forcing the prediction of classifiers to have similar statistical properties for people of different demographics. To reduce the violation of these properties, fairness methods usually simply rescale the classifier scores, ignoring similarities and dissimilarities between members of different groups. Yet, we hypothesize that such information is relevant in quantifying the unfairness of a given classifier. To validate this hypothesis, we introduce Optimal Transport to Fairness (OTF), a method that quantifies the violation of fairness constraints as the smallest Optimal Transport cost between a probabilistic classifier and any score function that satisfies these constraints. For a flexible class of linear fairness constraints, we construct a practical way to compute OTF as a differentiable fairness regularizer that can be added to any standard classification setting. Experiments show that OTF can be used to achieve an improved trade-off between predictive power and fairness.


Introduction
Machine learning methods are increasingly being deployed for automated decision making due to the potential benefits in terms of efficiency and effectiveness. Yet, making automated decisions about people comes with substantial legal and ethical risks, as evidenced by more and more cases of undesirable algorithmic discrimination [27,13,10] with respect to the protected traits of individuals. Even decisions that appear neutral because they do not use such sensitive information, may still disproportionately affect certain groups indirectly [41].
The research field of fairness in machine learning [30] therefore studies ways in which a model's discrimination with respect to a person's sensitive features can be reduced or removed. Many notions of fairness have been proposed for binary classification tasks [40]. A popular example is demographic parity, which is expressed as a constraint that enforces equality between the rates at which positive decisions are made for each protected group [6].
Motivation For a given fairness notion, we would like to tune a model that satisfies the constraint that expresses the notion. To this end, it can be practical to quantify the violation of this constraint as a fairness regularization term that can be added to any probabilistic classifier [26]. Such an approach provides an incentive to the model to learn parameters that result in fair probability scores, e.g. by learning to ignore highly biased features. A straightforward fairness regularizer is the norm of the difference between the quantities that should be equal according to the fairness notion [44,32].
However, such a quantification of unfairness may be limiting, as it only considers the statistical properties of the model's output, while ignoring the input features for which those scores were computed. We argue that, to quantify the unfairness of a model as a fairness regularizer, it can be beneficial to more strongly consider data points with similar features but significant unfair discrepancies in probability scores. To this end, we employ Optimal Transport (OT) [34] as a way to measure these discrepancies while taking feature similarity into account.

Contributions
• We propose to quantify the unfairness of a probabilistic classifier as the Optimal Transport to Fairness (OTF) cost, which is defined as the smallest OT cost between the score function of the classifier and any fair score function over the same data. • We make novel derivations to compute OTF as a differentiable fairness regularizer that can be added to the training loss of any probabilistic classifier and is efficiently computed for popular notions of fairness such as demographic parity and equalised odds. Our approach is capable of handling multiple sensitive variables, that can be categorical or continuous. • In experiments, our method shows its benefit of increased flexibility over other OT methods.
In some cases, it also achieves a trade-off between predictive power and fairness that is significantly more effective for equalized odds.

Fair Classification
Let Z X × S × {0, 1} denote the sample space, from which we draw samples Z (X, S, Y ) and try to estimate the output label Y ∈ {0, 1} from input features X ∈ X , without discriminating with respect to sensitive features S ∈ S. It is assumed that X ⊂ R d X and S ⊂ R d S .We sample binary predictionsŶ ∈ {0, 1} from a probabilistic classifier h : X → [0, 1] that assigns a score h(X) to the belief that a sample with features X belongs to the positive class. Our general goal in fair classification is to minimize a loss function L Y (h), in our case the cross-entropy between h(X) and Y , while also scoring well on a fairness measurement of h(X).

Group Fairness
The fairness of classifiers is commonly enforced through some notion of independence from sensitive information S ∈ S. In particular, group fairness is concerned with constraints over statistical measurements of this independence over all members of a protected group [30]. For now, assume that S consists of a single, categorical feature with d S values. We denote S ∈ S as the one-hot encoding 1 with values S k ∈ {0, 1}. This encoding is indexed by values from Assuming that the predictionsŶ | X are randomly sampled from a probabilistic classifier h(X), then the traditional fairness notion of demographic parity (DP) is equivalent to enforcing zero covariance between h(X) and each group in S, which we refer to as Probabilistic Demographic Parity (PDP): Remark 1. IfŶ is not sampled from h(X) but instead decided by a threshold (e.g.Ŷ = 1 if h(X) > 0.5), then Eq. (1) is a relaxation of the actual DP notion and may therefore admit unfair models [29]. However, such a threshold introduces a discontinuity with respect to the input, making it difficult to efficiently find fair classifiers in practice [38,1]. Moreover, by considering the probabilities directly, we account for the uncertainty expressed by the probabilistic classifier.
The notation in Eq. (1) is easily extended to fairness notions that condition on other variables. For example, the equalized odds (EO) [21] fairness notion conditions DP on the actual label Y . We apply EO to probabilistic classifiers by conditioning the covariance constraint of PDP on the one-hot encoding of Y and retrieve the following expression for Probabilistic Equalized Odds (PEO):

Linear Fairness
The PDP and PEO covariance constraints in Eq. (1) and Eq. (2) are practical, because they can be written as linear sums over the probabilities given by the classifier h. As was done in past work [1], we are generally interested in all fairness notions that can be enforced through such linear constraints.
Definition 1 (Linear fairness notion). A notion of fairness is a linear fairness notion when the set F of all score functions f : X → [0, 1] that satisfy it is given by with 0 d F a vector of d F zeros and the vector-valued function g(Z) : PDP and PEO are clearly linear fairness notions, with their g function listed in Table 1. Linear constraints are practical because the set of fair score functions F is convex. Moreover, multiple linear fairness notions can be combined into a new linear fairness notion by concatenating their constraint vectors. Sensitive information that is inherently continuous, like age, can be considered as a single dimension in S, thereby allowing for a mix of categorical and continuous sensitive attributes.
However, under linear fairness, a non-linear dependence between a score function f (X) and continuous sensitive attributes S can remain undetected. Also, some well-known fairness notions are not linear. For example, notions related to sufficiency involve conditioning on f (X), meaning that f (X) also shows up in the g function. To this end, approaches have been proposed [9] that can approximate classifiers with non-linear fairness through a reduction to problems with linear constraints.

Optimal Transport of Score Functions
Optimal Transport (OT) [33] theory considers the problem of moving a mass from one measure to another at the smallest possible total cost. Here, we let every score function f correspond with the measure θ f defined over the input space X endowed with the Borel σ-algebra: θ f x∈D X f (x)δ x , with δ x the Dirac measure and D X the input features of samples in a collection D. Note that the input space measure θ f is not normalized, though this is not necessary to apply OT theory. In what follows, we implicitly consider the score functions h and f as their corresponding input space measures θ h and θ f when used in the OT problem. See the Appendix C.1 for further clarification.
For a collection D of n samples (e.g. a full dataset or only a batch from it), let h and f denote the n-dimensional vectors of score function values for all data points, i.e. h i = h(x i ) and f i = f (x i ). Furthermore, for a non-negative transport cost function c defined over X ×X , let C ∈ R n×n + represent the matrix of cost terms, i.e. C ij = c(x i , x j ). Similarly, with π(x i , x j ) the coupling that reflects how much score mass was transported from x i to x j , define the matrix P ∈ R n×n The OT cost is then simplified to with where 1 n is the n-dimensional vector of ones and C, P = ij C ij P ij .

Optimal Transport to Fairness
Assume that a set F is available that denotes all score functions which satisfy the required notion of fairness. We would like to quantify the unfairness of a classifier's score function h as the amount of 'work' minimally required to make it a member of this set by measuring how far h is from its fair projection onto F, i.e. the f ∈ F that is closest to h. We measure this closeness as the OT cost between h and f , as we then assign a higher unfairness cost to h if scores need to be transported between highly dissimilar individuals in order to reach a fair function f ∈ F.
Thus, we propose to quantify unfairness as the Optimal Transport to Fairness (OTF) cost, i.e. the cost of the OT-based projection of h onto F: In what follows, we expand on the OTF method by constructing it in three steps. For all derivations and proofs, we refer to Appendix A.

Optimal Transport to Linear Fairness
To compute the minimization in Eq. (5), first note that in the OT(h, f ) cost in Eq. (4), f only shows up in the constraint P T 1 n = f on the column marginals of coupling matrix P. It therefore suffices to weaken this constraint to P T 1 n ∈ F. Next, recall that a linear fairness notion is enforced through a vector of constraints on the expectation of g(Z)f (X). For a collection D of n samples, let G cj = g c (z j ), i.e. G ∈ R d F ×n is the constraints matrix with a row for every constraint and a column for every data point. It defines the linear fairness notion for D. Definition 2 (OTF). For a linear fairness notion expressed through constraints matrix G for n samples and with non-negative cost matrix C, the Optimal Transport to Fairness cost for score function h : X → [0, 1] is computed as with The optimal coupling computed for OTF(h) implicitly transports the scores of h to the fair vector f given the coupling's column marginals (i.e. f = P T 1 n ). Note that for any coupling matrix that satisfies the first constraint (P1 n = h), we have that h T 1 n = 1 T n P T 1 n = f T 1 n , meaning that h and this implicitly found vector f sum to the same value. Scores of h are therefore only transported to a fair score function and no extra scores are created or destroyed.
For P ij ≥ 0, the optimization problem in Eq. (6) can be solved through linear programming. However, its solution is not differentiable with respect to the score function h [12,17]. It is thus impractical as a fairness regularization term.

Entropic Smoothing
A well-known trick to make OT costs differentiable is to apply entropic regularization or smoothing [12,34], which is done by maximizing the entropy of the coupling while optimizing the OT cost. We apply the same principle to make OTF differentiable. Definition 3 (OTF ). For a linear fairness notion expressed through constraints matrix G for n samples and with non-negative cost matrix C, the smooth OTF cost with smoothing strength > 0 for score function h : X → (0, 1] is computed as with H(P) = − ij P ij (log (P ij ) − 1) the entropy of coupling P and > 0 a hyperparameter that regulates the strength of entropic smoothing.
The use of an entropy term in Eq. (7) requires some justification, since we do not assume that h represents a normalized probability distribution (i.e. sums to one). Therefore, P also does not represent a normalized joint distribution. However, the H(P) term still provides the practical advantage that it only admits couplings with P ij > 0, which is why we require that h i > 0. Furthermore, the addition of H(P) makes the objective cost strongly convex.

Duality
The OTF problem for a linear fairness notion has n + d F constraints, which is usually far fewer in number than the n 2 variables that make up the couplings in the primal problem. Because OTF is also strongly convex, we will derive and then maximize the dual function instead.
problem has a unique solution for any h : X → (0, 1]. Moreover, the OTF problem is strongly convex and then enjoys strong duality. Its dual function is with λ ∈ R n and µ ∈ R d F the dual variable vectors for the marginalization and fairness constraints.

Optimization
Though Eq. (8) could be maximized directly, we follow standard OT approaches [34] and perform our optimization with exact coordinate ascent. This strategy is particularly useful here, because the λ i variable that maximizes L(λ, µ) while µ is fixed, is found independently of other variables in λ.
All variables in λ can therefore be updated at the same time: where we can use the stabilized log-sum-exp operation.
Unfortunately, there is no closed form expression for the µ c that maximizes L(λ, µ). Instead, we preprocess L(λ, µ) and numerically solve for each µ c :

Complexity
The dual problem involves two variable vectors: λ with length n the number of samples and µ with length d F the number of linear fairness constraints. It is commonly the case that d F n, because the number of distinguished protected groups is limited. This is in contrast with the traditional OT problem, where the dual problem involves two dual variable vectors of length n.
In terms of computational complexity, the update of the full λ has complexity O(n(n + d F )). However, we stress that each λ i can be updated in parallel with complexity O(n + d F ). When keeping the λ vector fixed, we can perform a O(n 2 ) operation to precompute the η j (λ) values for the µ updates. Though these updates no closed form, the inner loop of the update for µ c only has complexity complexity O(n + d F ) for each inner loop, and should only be performed for d F variables. By permitting a high tolerance on the convergence of λ, the necessary number of updates is also limited. In our experiments, we found that a single update is often enough.
We can achieve a memory complexity of O(n + d F ). However, we can perform efficient matrix computations by storing the cost matrix C and the fairness constraints matrix G. The memory required for practical use is therefore O(n(n + d F )).

Adjusted OTF
A cause for concern with the smooth OTF cost is that, as opposed to the standard OTF, it does not necessarily equal zero if h is already a fair score function. Indeed, while it may be feasible to achieve C, P = 0, it is generally the case that the entropy H(P) > 0. We would thus like to find an interesting lower bound on OTF that is tight when h ∈ F. Definition 4 (OTFR ). The OTF cost in Def. 3 is relaxed to the OTFR cost as with Definition 5 (OTF 0 ). For a score function h : X → (0, 1], the adjusted OTF cost is computed as Whereas the OTF (h) problem involved transport to fair score vectors (GP T 1 n = 0 d F ), the OTFR (h) problem relaxes this constraint by allowing unfairness up to the unfairness already present in h. It is thus easily seen that OTF (h) ≥ OTFR (h). Interestingly, because this relaxation is bounded by the unfairness of h, we have that OTFR (h) is a tight lower bound if h is already fair.
In Appendix B.1, we provide empirical intuition for this theoretical result by using OTF 0 (h) as a postprocessing approach and illustrate that OTF (h) gradually converges to OTFR (h) as the fairness of h improves.
The adjustment term OTFR can be computed by using strong duality in a similar way as OTF (h), though now with two dual variables φ ∈ R d F and ψ ∈ R d F that enforce the fairness inequality, in addition to the dual variable vector, here denoted by κ ∈ R n , that enforces the row constraint on the coupling. The dual function of OTFR is For a full discussion, we refer to Appendix A.4.

Minimising Unfairness
Given an efficient way to compute the parameters of the adjusted, smooth OTF 0 (h) cost, we can now jointly minimize the weighted sum of the classifier's loss and unfairness cost with respect to h.
Let L Y (h) denote the cross-entropy loss of h(X) for the output labels Y . To add our OTF 0 (h) cost to this objective, we can pose the following optimization problem: with 0 ≤ α ≤ 1 a hyperparameter that regulates the importance of the unfairness cost term OTF 0 (h).
So far, we considered the scores vector of h as constant with respect to the OTF 0 (h) problem. However, the solutions for OTF (h) and OTFR (h) clearly depend on h. Let λ * , µ * , κ * , φ * and ψ * denote the fully converged dual variables. Then Even if we did not update the dual variables until convergence, we can still use intermediate values to approximate the true gradient [18,16]. We further approximate the true OTF 0 (h) cost by only computing it for a subset of the dataset, e.g. when batching is already used to optimize L Y (h). The OTF 0 (h) can be optimized on a batch by only using the values of C and the columns of G that relate to these data points. For large datasets (including those we use in experiments), it is then unnecessary to precompute the C matrix between all pairs of data points, since most pairs will never actually co-occur in randomly sampled batches.

Related Work
Fairness in machine learning is commonly understood in two (extreme) ways [30]. First, the notion of individual fairness states that similar individuals should be treated similarly [15]. Second, group fairness requires that as a group, people are treated equally. The primary goal of our work is to achieve group fairness by measuring the distance of a score function to a set of group-fair functions. Yet, to an extent we also approach individual fairness because our unfairness quantification takes the features of each individual into account in its cost function c. By appropriately choosing c, it may be possible to further improve upon individual fairness in future work.
Methods that aim to improve fairness can be categorized into three types: those that perform preprocessing where the data is made more fair [25,8], as opposed to those that do postprocessing where the model's predictions are modified to fit a notion of fairness [21]. As a fairness regularization term, our work clearly fits in the class of inprocessing methods, i.e where the machine learning model or its training is directly altered to reduce unfairness [7,44,43,1,9]. However, we highlight that the OTF cost could also be used as a postprocessing approach by setting α = 1.
Our work draws inspiration from two kinds of inprocessing methods. First, with those methods where a (still unfair) model is explicitly projected unto the set of fair models. A popular definition of distance for this projection is the Kullback-Leibler divergence [2,23,5]. Second, our work uses Optimal Transport (OT) [34] theory. Several works have applied OT to fairness, though they almost all do so by finding barycenters [36]: measures that are 'equally far' from the measures belonging to each demographic. This type of method has been applied to preprocessing [19], classification [23,45] and regression [11,20], with the overarching goal being to move each group's measure closer to the barycenter. Such methods require fairness notions to be encoded in the format of explicit equality, between a limited amount of groups. They do not allow for more complex constraints such as those involving continuous or multiple sensitive attributes, and make strong assumption that the cost function is a distance metric.
Our proposed method instead combines the idea of projecting the model to a fairness-constrained set and the use of OT to measure the cost of this projection. In this manner, our work is most similar to [35], which computes the OT projection onto such a fair set. However, they only use the method as a group fairness test. Our method has the advantage that it computes a differentiable cost that can be added to the loss of any probabilistic classifier.

Experiments
Our experiments were performed on four datasets from fair binary classification literature [14,28] with different kinds of sensitive information. First, the UCI Adult Census Income dataset with two binary sensitive attributes SEX and RACE. Second, the UCI Bank Marketing dataset, where we measure fairness with respect to the original continuous AGE values and the binary, quantized version AGE_BINNED. Third, the Dutch Census dataset with sensitive attribute SEX. Fourth, the Diabetes dataset with sensitive attribute GENDER. Additional information on datasets and hyperparameters is given in Appendix C.2 and C.3 respectively.

Methods
All experiments were performed using a logistic regression classifier. To achieve fairness, we jointly optimize fairness regularizers with the cross-entropy loss as in Eq. (13), and compute the gradient of their sum with respect to the parameters of the classifier.
The OTF cost is the adjusted version from Def. 5, with = 10 −3 (different choices for are illustrated in Appendix B.2). For the cost function c, we use the Euclidean distance between non-protected features. The fairness constraints for both sensitive features in the Adult dataset were combined by concatenating their G matrices.
As a first baseline, we use the L 1 norm of the PDP and PEO fairness constraints and will refer to this method as the Norm cost. This simple type of fairness regularizer is frequently proposed in literature [26,44,42,32]. In our experiments, it thus represents the class of methods that can accommodate a flexible range of fairness constraints while only considering the output of a classifier and not the input features.
Our second baseline is an OT Barycenter 2 approach [24]. This method directly minimizes the OT cost between the score distributions of two sensitive groups. However, the implementation can only minimize PDP, and does not admit a composition of linear fairness notions or continuous attributes. We therefore only minimize unfairness with respect to SEX and AGE_BINNED. To show the drawbacks of this limitation, we also report PDP unfairness with respect to RACE and the continuous AGE.
The third baseline is Unfair, which was a classifier trained without a fairness cost term.

Evaluation
To measure the predictive power of the methods, the ROC AUC score was measured. Violation of PDP is quantified as the absolute value of the maximal Pearson correlation between the scores h(X) and each dimension of the sensitive attributes S k . For PEO, the violation is computed as the maximal PDP for the data points of each one-hot encoded output label Y l . These measures mirror the requirements in Eq. (1) and Eq. (2) that the covariances ought to equal zero, though we choose the Pearson correlation instead such that the violation is normalized between 0 and 1. Thus we avoid that a method may improve on linear fairness notions by squeezing the variance of its scores.
All methods were tested for various strengths of α (see Eq. (13)). Each configuration of each method (i.e. each α value and fairness notion) was tested for 10 train-test splits with proportions 80/20. We report mean test set scores in Fig. 1 and show the confidence ellipse 3 of their estimator for the first standard deviation. The train set results are reported in Appendix B.3 and show the same trends.
Note that for the OTF and Norm regularizers, we omit fairness scores for notions that were not optimized in that configuration. While SEX and RACE are minimized at the same time for the Adult dataset, the AGE and AGE_BINNED attributes were minimized in separate training runs.
All experiments were conducted using half the hyperthreads on an internal machine equipped with a 12 Core Intel(R) Xeon(R) Gold processor and 256 GB of RAM. In total, all experiments, including preliminary and failed experiments, used this machine for approximately 200 hours.

Results
On all datasets, our OTF method makes a similar trade-off between AUC and PDP fairness as the baselines for various α values. However, OTF clearly outperforms Norm for both sensitive attributes on the Adult dataset in Fig. 1a when they are trained to minimize PEO, especially in the lower violation range. Similarly, OTF achieves a better trade-off between AUC and PEO violation on the Diabetes dataset in Fig. 1d, especially on the train set (see Appendix B.3). This advantage in minimizing PEO may be due to the fact that OTF has the incentive to achieve fairness by exchanging classifier scores between similar individuals. Conditioning on the output label rewards such exchanges, as individuals with similar labels can be expected to have similar features.
Furthermore, we remark that our OTF method is as flexible as the Norm baseline in minimizing either PDP or PEO with respect to multiple sensitive attributes on the Adult dataset and the continuous AGE attribute on the Bank dataset in Fig 1b. Implementations of differentiable regularizers that can accommodate such attributes are scarcely available. For example, the Barycenter method was not trained to improve fairness with respect to RACE, as its implementation can not handle multiple sensitive attributes. Since it can only minimize the OT cost between a limited number of score distributions, it is naturally ill-equipped for continuous attributes. In separate runs on the Bank dataset, we therefore also trained OTF and Norm to minimize unfairness with respect to AGE_BINNED. Though the results are subject to noise, we observe similar trends as for the other non-continuous attributes: our method is clearly on par with the baselines. On the train set results (see Appendix B.3) the OTF method significantly outperforms the Norm baseline for PEO.
On the Adult, Bank and Diabetes datasets, the proposed OTF method thus displays its advantage in both an effective AUC-fairness trade-off, and a flexible capacity for fairness. However, we note that on the Dutch dataset in Fig. 1c, no method seems to display a significantly better trade-off. We hypothesize that no such advantage is seen here because PEO, the fairness notion where our method usually achieves superior results, may be relatively easy to satisfy on this dataset.

Limitations and Impact
We nuance our results by pointing out that the OTF method has a higher computation complexity (O(n(n + d F ))) than Norm, which has complexity O(nd F ) with n the batch size and d F the number of fairness constraints. Furthermore, as discussed in Sec. 2.1, we only evaluate linear fairness notions and leave an extension to non-linear notions of fairness [9] for future work.
The fairness of a system should always be judged based on a holistic consideration of the context of the system [3] and relevant ethical principles [4]. Without it, any method to improve fairness may reinforce the underlying injustice that led to the risks of discrimination that we aim to solve [22].

Conclusion
In this paper, we constructed the Optimal Transport to Fairness (OTF) method as a differentiable fairness regularization term, which combines the advantages of flexible linear fairness constraints with Optimal Transport theory, thereby taking non-protected similarities between individuals into account. In experiments, we show that our final method achieves a similar AUC-fairness trade-off as other cost terms for notions of fairness inspired by demographic parity, and significantly better for notions inspired by equalized odds. At the same time, OTF empirically displays why its increased flexibility, i.e. its ability to improve all linear fairness notions with respect to multiple sensitive attributes that may be categorical or continuous, provides an advantage over previous fairness applications of OT.
In the future, we hope to further investigate the properties of OT-based fairness, inspired by its clear advantage in achieving equalized odds. Though our method was only applied to linear fairness notions, OT may provide an opportunity to better achieve non-linear notions of fairness, e.g. through a creative choice of the cost function that directs the transport of classifier scores.

A.1 Proof of Proposition 1
With h i > 0, we assume that the null-space of G is non-empty, i.e. ∃f ∈ R n : f = 0 n ∧ Gf = 0 d F .
Then, Gf = 0 d F implies that uniformly rescaled score vectors sf with s ∈ R are also fair. One of those fair, rescaled score vectors will have the same total mass as h: Therefore, for such a G there is always a fair score function that h can be transported to (i.e. Π F (h) = ∅). Such OT problems always have a solution coupling [33]. Thus, there exists an optimal coupling for the OTF problem.
The objective cost of OTF is the strictly convex functional C, P − H(P) and the equality constraints that define the valid set of couplings Π F (h) are affine. The OTF problem is thus convex and enjoys strong duality. Due to the strict convexity of the objective cost, the optimal coupling solution is unique.
Recall that H(P) = − ij P ij (log (P ij ) − 1). The Lagrangian of the OTF problem is given by where λ ∈ R n and µ ∈ R d F denote the dual variable vectors for the marginalization and fairness constraints respectively.
The Lagrangian, which is continuously differentiable around the optimal coupling, is written as a sum over the elements of P. We can thus minimize Λ(P, λ, µ) by setting the derivative ∂Λ(P,λ,µ) ∂Pij = 0: This results in the dual function Due to the strong duality, the values of the optimal coupling in OTF are given by P * ij (λ * , µ * ), with the optimal dual variables (λ * , µ * ) = argmax (λ,µ) L(λ, µ).
A.2 Derivation of the Update Eq. (9) and Eq. (10) We aim to update the λ i and µ c variables through exact coordinate ascent of the dual function L(λ, µ). To this end, we derive expressions for the univariate updates of L(λ, µ). For λ i , the update is given by where λ * i (λ 1 , ..., λ i−1 , λ i+1 , ..., λ n , µ) denotes the value of λ i that maximizes L(λ, µ). This update has the useful property that it is independent of other variables in λ, i.e. λ * i (λ 1 , ..., λ i−1 , λ i+1 , ..., λ n , µ) = λ * i (µ) The update for µ c generally does not have a closed form expression, because it can not be isolated from the expression of the gradient: Instead, we maximize the dual function L(λ, µ) with respect to µ c numerically.
c denote the variables at the end of iteration t. In every iteration t, we set

A.3 Proof of Proposition 2
Per Definition 1, we have that h ∈ F ⇐⇒ Gh = 0 d F . In this case, the column constraints upon the set of valid couplings for OTFR (h) are simplified as follows: These simplified column constraints are equal to those posed upon couplings for OTF (h). Since the other constraints and objective cost were already the same, we thus have that Thus, for h ∈ F, the adjusted OTF 0 (h) cost is We leave a study of the assumptions needed for the opposite implication OTF 0 (h) = 0 ? =⇒ h ∈ F for future work. For now, we observe that OTF (h) = OTFR (h) is possible for a non-fair h / ∈ F if the optimal coupling of the relaxed OTFR (h) cost coincidentally happens to transport h to a score vector that is fair.

A.4 Computation of OTFR (h)
The only difference between the OTF and OTFR problems is in the column constraints posed upon the couplings. The equality constraint in OTF (i.e. GP T 1 n = 0 d F ) is relaxed to bounds on the unfairness of h in OTFR (i.e. |GP T 1 n | ≤ |Gh|). Because the objective of OTFR remains strongly convex, and the relaxed constraints are still affine, we maintain the existence, uniqueness and strong duality properties from Proposition 1. Similarly to OTF , we thus solve the dual problem for OTFR .
For OTFR , we write out the Lagrangian as follows: with κ ∈ R n the dual variable vector for the row constraints and φ ∈ R d F and ψ ∈ R d F the dual variable vectors for the fairness bounds, where we require that φ c < 0 and ψ c < 0. We also use γ c = | j G cj h j | to simplify notation.

B.2 Impact of Smoothing Factor
We aim to provide some empirical intuition for how the smoothing factor impacts the use of the OTF 0 cost as a fairness regularizer. For this experiment, we used OTF 0 for varying strengths of α and in order to minimize the violation of PDP with respect to only the SEX attribute in the Adult dataset. All other settings are the same as those described in Sec. 5. The score distributions of these configurations are reported in Fig. 3.
It can be seen that for = 0.001 and = 0.01 the score distributions are made more similar for stronger α values. However, some properties, such as the more noticeable 'peak' for the samples in the female group compared to the male group, are maintained to some extent. For = 0.1 and = 1, the scores appear to be squished to very low or very high values, and they do not appear fair. We hypothesize that the relatively high value of the entropy term in the OTF (h) and OTFR (h) objectives overshadows the C, P term, which assigns a cost to how much score mass needs to be moved to make h fair. Thus, the model may try to minimize OTF 0 (h) mainly by minimizing the entropy term. This can indeed be accomplished by assigning very low or high element-wise probability scores.
For the even stronger smoothing with = 10, we see that the fairness regularizer has no impact at all, because changes in α do not impact the score distributions that are eventually learned. For such a high , both the OTF (h) and OTFR (h) solutions almost only strive to maximize entropy, causing these costs to cancel out. This causes OTF 0 (h) to be close to zero even though h itself may not yet be fair.
We conclude that high values should be avoided, as the strong smoothing causes the unfairness signal in OTF 0 (h) to be lost. It is then longer interesting as a fairness regularization term.

B.3 Train Set Results for the Main Experiment
As discussed in Sec. 5.2, we only report the test set results in the main paper. Results on the train set, which is far larger, are shown in Fig 4. They follow the same mean trends but are less noisy due to the larger amount of samples. We thus draw the same conclusions as for the test set results discussed in Sec. 5.3.

C.1 Tying Measures to Score Functions
A score function f : X → [0, 1] is involved in two domains: it operates on elements from the input space X , but then produces a probability for value 1 in the output space {0, 1}. In some prior work on OT for classifiers, [17,24], the OT problem was posed using measures and a cost function over the output space. Yet, our intention is to avoid transports between inputs that are highly dissimilar. We therefore tie classifiers to measures over the input space X endowed with the Borel σ-algebra: measure θ f is not normalized (i.e. θ f (X ) = 1), though this is not necessary to apply OT theory, which is most generally defined without any constraints on the total mass of the measures [33].
In our formulation, we use Eq. (15) to implicitly consider the score functions h and f as their corresponding input space measures θ h and θ f when used in the OT problem.

C.2 Datasets
All datasets are well-known in fairness literature [28] and highly anonymized. The datasets are popularly used Both datasets are some of the most popular datasets hosted by the UCI repository [14]. The data is highly anonymized.
For the Adult 4 dataset, gathered from the American Housing Survey. The task is to predict whether an individual earns more than $50K/yr. We follow the default data preprocessing implemented by the AI Fairness 360 5 framework and retain 45222 samples. The sensitive features are simplified to two binary sensitive attributes: SEX (with values {male, female}) and RACE (with values {white, non-white}).
In the Bank 6 dataset [31], the target is whether a client will subscribe to a product offered by a bank. For the 41188 data samples of individuals, the sensitive attribute is the age of the clients, which is traditionally converted to a categorical value by dividing the age into a limited number of bins. As sensitive attributes, we study both the original continuous AGE values and the quantized version based on the median age of 38, i.e. AGE_BINNED (with values {< 38, ≥ 38}).
The Dutch Census dataset 7 [39] involves predicting whether the occupation of individuals is classified as 'prestigious' or not. We followed the preprocessing outlined in [28] and end up with 60420 samples. For this dataset, we only consider one sensitive attribute, the binary SEX with values {male, female}.
Finally, samples in the Diabetes dataset 8 [37], represents features of patients for whom it should be predicted whether they will be readmitted within 30 days. Again following the preprocessing from [28], we end up with 45715 samples and use the listed GENDER of the patient as sensitive attribute with values {male, female}.

C.3 Hyperparameters
For all methods, we used an unregularized, logistic regression model as the probabilistic classifier. We trained for 100 epochs with a learning rate of 10 −3 and a batch size of 1000. The sensitive features were not included in the input X to the model. For the OTF and Norm methods, we evaluated fairness regularization strengths α ∈ {0.1, 0.3, 0.5, 0.7, 0.9}.
Also for OTF, we chose = 10 −3 from {10 −4 , 10 −3 , 10 −2 , 10 −1 }. We chose this value because it consistently resulted in an effective trade-off between AUC and fairness. For a discussion on the impact of setting too high, we refer to Sec. B.2.