Fair learning with Wasserstein barycenters for non-decomposable performance measures

Our\blfootnote${}^{\ast }$ Equal contribution experience of life is increasingly and insidiously being influenced by algorithmic predictions. It is now well accepted that such predictions might replicate or even amplify societal biases and discrimination because of machine learning algorithms’ training process (barocas-hardt-narayanan). A key difficulty in overcoming the effect of those biases is the lack of a precise understanding of how statistical algorithms make predictions: these algorithms are often designed to minimize a user-specified data-dependent loss and yield a highly complex prediction rule, leaving practitioners—and theoreticians—unable to understand and explain the issued predictions. Our goal is to provide a sound and simple mathematical characterization of the prediction process in the presence of fairness constraints.

In this paper we study the demographic parity fairness constraint (calders2009building; barocas-hardt-narayanan) in the awareness framework—allowing the prediction rules to explicitly take the sensitive attribute as an input. Even though this constraint is relatively well understood from algorithmic perspective in both classification (Agarwal_Beygelzimer_Dubik_Langford_Wallach18; menon2018cost; zeng2022bayes; schreuder2021classification; yang2020fairness; jiang2019wasserstein; silvia2020general; feldman2015certifying; gordaliza2019obtaining) and regression (chzhen2020fair; chzhen2020fairTV; gouic2020price; jiang2019wasserstein; agarwal2019fair; chiappa2021fairness), the connection between the two setups remains opaque. The main goal of the current paper is to unveil it.

In contrast, in the traditional unconstrained learning setup, the relation between classification and its regression counterpart is well understood and can be found in all standard books on the subject (see, e.g., hastie2009elements; devroye2013probabilistic; james2013introduction; mohri2018foundations). For instance, the most standard result illustrating this connection states that if $\eta$ minimizes the squared risk, the classifier $g^{\ast }(\cdot )=\text{ind}\eta (\cdot )\ge 1/2$ minimizes the misclassification error. Such results form the first building block of many theoretical and practical studies (see, e.g., Audibert_Tsybakov07; Yang99; massart2006risk; biau2008consistency). More recently, the connection between regression and classification was pushed even further. For instance, replacing the misclassification error by the $F$-score (van1974foundation; Chinchor92), Zhao_Edakunni_Pocock_Brown13 showed that the solution of the associated regression problem still plays a crucial role as an $F$-score maximizer can be obtained by properly thresholding the solution of the regression problem. Moreover, a recent thread of results establish this fundamental relation for a large variety of performance measures including AM measure, the Jaccard similarity coefficient, and G-mean to name a few (menon2013statistical; koyejo2014consistent; Koyejo_Natarajan_Ravikumar_Dhillon15; Yan_Koyejo_Zhong_Ravikumar18). Again, akin to the standard minimization of misclassification error problem, all these developments led to many theoretical and practical advances (see, e.g., jasinska2016extreme; chzhen2020optimal; narasimhan2015optimizing; kotlowski2016surrogate; bascol2019cost; boughorbel2017optimal). Interestingly, some works that consider group fairness constraints actually report $F$-score as a performance measure in their empirical studies without actually tailoring an algorithm to optimize it directly (see, e.g., BiswasR20; BiswasR21; abs-2207-03277; wang2021analyzing; dablain2022towards; wick2019unlocking). A possible cause of this is the absence of characterization of fair ($F$-score) optimal classifiers in the fairness literature. In this paper we fill this gap for the demographic parity constraint and a large class of performance measures.

Literature that treats group fairness notions is typically distinguished by two features: exact notion of fairness and access to the sensitive attribute at prediction time. While this work considers only demographic parity, we discuss both awareness and unawareness setups—allowing or not the access to the sensitive attribute at prediction time respectively. Unlike the case of awareness, in which a significant understanding has been achieved from theoretical perspective, the case of unawareness remains opaque with contributions mainly focusing on algorithmic constructions (see e.g., Agarwal_Beygelzimer_Dubik_Langford_Wallach18; agarwal2019fair; oneto2019general; Donini17; narasimhan2018learning). A notable work of lipton2018does puts forward several empirical evidences highlighting critical issues connected of the unawareness framework. Our work makes a step towards a more explicit and transparent description of the optimal classifier under the demographic parity constraint with unawareness by introducing a simple theoretical reduction scheme to the awareness setup for binary protected attribute. Consequently, our results support theoretically the empirical claims made by lipton2018does.

Consider a triplet $(\text{bX},S,Y)\in \times \left[K\right]\times \{0,1\}$, following some joint distribution $\text{Prob}$, consisting of the nominally non-sensitive and sensitive features, and the label, respectively. Classifiers are functions of the form $g:\times \left[K\right]\mapsto \{0,1\}$ and score functions take the form $f:\times \left[K\right]\mapsto [0,1]$. The set of all classifiers is denoted by and the set of all score functions is denoted by . Before proceeding let us introduce additional notation that is related to the unknown distribution $\text{Prob}$. We set $\eta (\text{bX},S)\triangleq \text{Exp}[Y\mid \text{bX},S]$ and recall that $\eta$ minimizes the squared risk without any constraint. For each $s\in \left[K\right]$, we define $p_s\triangleq \text{Prob}(S=s)$. The central object of this work is the optimal fair score function, defined as: {highlighted}

An explicit expression for $f^{\ast }$ under standard assumptions was derived in (chzhen2020fair; gouic2020price) using the univariate optimal transport theory and the reduction of the problem in Eq. (1) to a multi-marginal optimal transport formulation. In particular, they showed that, under mild assumptions, there is a one-to-one correspondence between the problem in Eq. (1) and the problem

where $W_2$ is the Wasserstein-2 distance (villani2009optimal, Definition 6.1) and denotes the space of univariate probability measures with finite second moment. Denoting by ${\nu }^{\star }$ the solution of the above problem, it was shown that

where $T_{\text{Law}\left(\eta \right(\text{bX},S)\mid S=s)\to {\nu }^{\star }}$ is the optimal transport map from $\text{Law}\left(\eta \right(\text{bX},S)\mid S=s)$ to ${\nu }^{\star }$. Up until now, unlike in the regression setting, it was not clear if a direct link between optimal transport and the fair binary classification problem existed–or even made sense. Our work shows that such a connection exists and that it is fundamental.

In this section, we begin by tackling the classical minimization of the misclassification risk problem and highlight the main novelties and advances with respect to previous works. To this end, we consider the following optimal (in terms of the misclassification risk) fair classifier {highlighted}

We work under the following assumption. {assumption} For every $s\in \left[K\right]$, assume that $\text{Law}\left(\eta \right(\text{bX},S)\mid S=s)$ is continuous and supported on an interval. A slightly modified version of the above was used in the context of fairness in (chzhen2020fair; chzhen2020fairTV; gouic2020price; jiang2019wasserstein) and also also in the classical unconstrained classification with generalized performance measures (Yan_Koyejo_Zhong_Ravikumar18). In Section A, we relax the above assumption and provide a proof that unifies the awareness case considered just below with the unawareness case presented in Section 5, Theorem 5.

The first warm-up result is reminiscent of those recently obtained by (zeng2022bayes; schreuder2021classification). The proof based on the $minmax$ duality and is very similar to the classical Neyman-Pearson lemma. While it does not allow to immediately reach our goals, it gives several fundamental insights that were already invoked in previous works on the demographic parity constraint (lipton2018does; hardt2016equality). {theorem} Let Assumption 3 be satisfied. Then, an optimal fair classifier $g^{\ast }:\times \left[K\right]\to \{0,1\}$ defined in Eq. (2) can be expressed for all $(\text{bx},s)\in \times \left[K\right]$ as

where ${\text{blambda}}^{\ast }=({\lambda }_1^{\ast },\dots ,{\lambda }_K^{\ast }{)}^{\top }\in {\text{bbR}}^K$ is a solution of

The main takeaway message from the above theorem is: under the stated assumption, the optimal fair classifier can be derived as a group-wise thresholding of the regression function $\eta$, with thresholds eventually depending on the sensitive groups. For a similar statement without the continuity assumption, we refer the reader to zeng2022bayes who derived optimal randomized classifiers using the Neyman-Pearson lemma. Let us now provide a novel characterization of an optimal fair classifier. {mytheo}Wasserstein based fair optimal classifierequivalence Let Assumption 3 be satisfied. Then, an optimal fair classifier $g^{\ast }:\times \left[K\right]\to \{0,1\}$ defined in Eq. (2) can be expressed for all $(\text{bx},s)\in \times \left[K\right]$ as

In this part we extend the analysis of the previous section to a broader class of performance measures, which includes the $F$-score, the AM-mean, and the misclassification risk among others. We follow the framework put forward by koyejo2014consistent, who introduced the so-called linear fractional performance measures. Formally, given coefficients $({\text{sfn}}_0,{\text{sfn}}_1,{\text{sfn}}_2)\in {\text{bbR}}^3$ and $({\text{sfd}}_0,{\text{sfd}}_1,{\text{sfd}}_2)\in {\text{bbR}}^3$, the performance of a classifier $g:\times \left[K\right]\to \{0,1\}$ is measured by its utility

We denote by the set of all classifiers $g:\times \left[K\right]\to \{0,1\}$ for which the denominator of $U_{(\text{sfn},\text{sfd})}$ is non-zero. It is important to emphasize that both $\text{sfn}$ and $\text{sfd}$ are allowed to depend on the unknown distribution of the data $\text{Prob}$ but not on the classifier $g$. For instance, the $F_1$-score (van1974foundation) corresponds to the choice $({\text{sfn}}_0,{\text{sfn}}_1,{\text{sfn}}_2)=(0,2,0)$ and $({\text{sfd}}_0,{\text{sfd}}_1,{\text{sfd}}_2)=\left(\text{Prob}\right(Y=1),0,1)$. We refer to (choi2010survey) for additional examples of different choices of $(\text{sfn},\text{sfd})$ corresponding to different classification performance measures. Recently, yang2020fairness studied linear performance measures in the context of fairness, which essentially corresponds to the special case of the above linear fractional formulation with $({\text{sfd}}_0,{\text{sfd}}_1,{\text{sfd}}_2)=(1,0,0)$—which, for instance, does not encompass the $F_1$-score. In another direction, celis2019classification considered linear fractional formulation of fairness constraints while optimizing the misclassification risk. However, given the structure of the constraints, this problem can essentially be re-formulated as misclassification risk minimization under linear fairness constraints.
As it is common in the literature on generalized performance measures, we view $U_{(\text{sfn},\text{sfd})}$ as a utility to be maximized, contrary to the minimization of the risk viewpoint from the previous section. Thus, our goal is to study{highlighted}

A remarkable property of linear fractional measures is that the unconstrained maximizer can still be obtained by thresholding the regression function $\eta$. Yet, the threshold in this case might depend on the unknown distribution $\text{Prob}$ and ought to be estimated. Let us provide couple of standard examples. {example} Consider the problem of maximizing the accuracy:

Setting $({\text{sfn}}_0,{\text{sfn}}_1,{\text{sfn}}_2)=(1-\text{Prob}(Y=1),2,-1)$ and $({\text{sfd}}_0,{\text{sfd}}_1,{\text{sfd}}_2)=(1,0,0)$, we see that the above formulation falls within the considered framework. {example} Consider the problem of maximizing the $F_1$-score:

Zhao_Edakunni_Pocock_Brown13 showed that the solution $g^{\ast }$ of the above optimization problem can be written as

where ${\theta }^{\ast }\in [0,1]$ is the unique solution of $\theta \text{Prob}(Y=1)=\text{Exp}\left(\eta \right(\text{bX},S)-\theta {)}_{+}$. koyejo2014consistent pushed further these results demonstrating that the “thresholding principle” remains true for the whole family of linear fractional measures. In what follows, we will show that their result is still valid if one replaces $\eta$ by $f^{\ast }$—the solution of the fair regression problem. This validity is established in a strong sense, meaning that even the equation (as in Example 4) determining the threshold is preserved.

Wasserstein based fair optimal classifier for non-decomposable measuresfair_optimal_LF Let Assumption 3 be satisfied. Assume that $\text{sfd}\in {\text{bbR}}^3$ is such that

Assume that the coefficients $(\text{sfn},\text{sfd})\in {\text{bbR}}^3\times {\text{bbR}}^3$ satisfy one of the following mutually exclusive conditions:

Then, $g_{(\text{sfn},\text{sfd})}^{\ast }$ defined in Eq. (7) can be expressed for all $(\text{bx},s)\in \times \left[K\right]$ as

where ${\theta }_{(\text{sfn},\text{sfd})}^{\ast }$ is either the unique solution of

if ${\text{sfn}}_2{\text{sfd}}_1\ne {\text{sfd}}_2{\text{sfn}}_1$ or ${\theta }_{(\text{sfn},\text{sfd})}^{\ast }=\frac{{\text{sfd}}_0{\text{sfn}}_2-{\text{sfn}}_0{\text{sfd}}_2}{{\text{sfn}}_0{\text{sfd}}_1-{\text{sfd}}_0{\text{sfn}}_1}$ otherwise.

A few comments are in order. First of all, Theorem LABEL:thm:fair_optimal_LF states that the pre-cited “thresholding principle” still holds for optimizing linear-fractional performance measures under the demographic parity constraint: optimal fair classifiers can be obtained by thresholding the optimal fair regression function $f^{\ast }$ at the right threshold level ${\theta }_{(\text{sfn},\text{sfd})}^{\ast }$. Moreover, in the case ${\text{sfn}}_2{\text{sfd}}_1={\text{sfd}}_2{\text{sfn}}_1$ an explicit expression is provided, while if ${\text{sfn}}_2{\text{sfd}}_1\ne {\text{sfd}}_2{\text{sfn}}_1$ one needs to solve a fixed-point equation to find the optimal threshold. Given that the function defining the fixed-point equation is univariate, monotone and continuous, the bisection method (or any other univariate root-finding method) can be used to obtain an approximation of the optimal threshold up to arbitrary precision. Finally, since the conditions on the coefficients might seem opaque at first sight, let us argue why they are harmless and meaningful. Intuitively, these conditions specify only two requirements:

• The maximization of $U_{(\text{sfn},\text{sfd})}\left(g\right)$ makes sense—the more the classifier align with $Y$ the better. In particular, these conditions exclude $\text{Prob}(Y\ne g(\text{bX},S\left)\right)$, whose maximization does not make sense.

• The denominator of $U_{(\text{sfn},\text{sfd})}$ is non-negative.

One can verify that all the measures presented in Table 1 do indeed satisfy these conditions as well as many other linear fractional performance measures from choi2010survey. We would also like to point out that while the conditions of Theorem LABEL:thm:fair_optimal_LF are cumbersome, they are easy to check in practice, unlike those given in (koyejo2014consistent), who relied on $\text{sign}({\text{sfn}}_1-U_{(\text{sfn},\text{sfd})}(g_{(\text{sfn},\text{sfd})}^{\ast }\left){\text{sfd}}_1\right)$. Indeed, to check the latter, one needs to know or estimate the optimal value of $U_{(\text{sfn},\text{sfd})}$ beforehand, which is not always feasible in practice. In contrast, conditions ($C1$) and ($C2$) only involve the known coefficients $(\text{sfn},\text{sfd})$. Finally, let us remark that $U_{(\text{sfn},\text{sfd})}$ = $U_{(-\text{sfn},-\text{sfd})}$ and both conditions ($C1$) and ($C2$) are invariant under the $(\text{sfn},\text{sfd})\mapsto (-\text{sfn},-\text{sfd})$ transformation. Yet, to fix only one of them, we additionally require ${\text{sfd}}_0+min\{min\{{\text{sfd}}_1,0\}+{\text{sfd}}_2,0\}\ge 0$, which forces the user to fix the signs of $\text{sfd}$ properly. Let us emphasize that, if ${\text{sfd}}_0+min\{min\{{\text{sfd}}_1,0\}+{\text{sfd}}_2,0\}>0$, then —the denominator does not zero-out—which is a consequence of Lemma B.

The first lemma is similar to the main result of (koyejo2014consistent), while the second one gives an explicit expression for the excess-score of any fair classifier. The actual proof technique shares some similarities with the analysis of $F_1$-score in (chzhen2020optimal) who provided an alternative proof to the result of Zhao_Edakunni_Pocock_Brown13 recalled in Example 4. {mylemma}Fixed point propertyfixed_at_optim_LF Let Assumption 3 be satisfied. Let $g_{(\text{sfn},\text{sfd})}^{\ast }$ be defined in Theorem LABEL:thm:fair_optimal_LF and assume that ${\theta }_{(\text{sfn},\text{sfd})}^{\ast }$ defined in Eq. (9) exists. Then,

The next result provides an explicit expression for the excess score of any fair classifier $g$.

Excess score for fair non-decomposable measuresexcess_score Let Assumption 3 be satisfied. Let $g_{(\text{sfn},\text{sfd})}^{\ast }$ be defined as in Theorem LABEL:thm:fair_optimal_LF and assume that ${\theta }^{\ast }\triangleq {\theta }_{(\text{sfn},\text{sfd})}^{\ast }$ defined in Eq. (9) exists. Let $\overline{\mu }\left(\eta \right)$ be the Wasserstein barycenter of measures ${\mu }_1\left(\eta \right),\dots ,{\mu }_K\left(\eta \right)$ weighted by $p_1,\dots ,p_K$, respectively. Define ${\beta }^{\ast }$ as ${\beta }^{\ast }=F_{\overline{\mu }\left(\eta \right)}\left({\theta }^{\ast }\right)$. Let . Then, for any classifier $g\in \text{dom}\left(U_{(\text{sfn},\text{sfd})}\right)$ such that $g(\text{bX},S)\text{independent}S$, excess score equals to

Furthermore, under the conditions on $(\text{sfn},\text{sfd})$ specified in Theorem LABEL:thm:fair_optimal_LF; we have for all classifiers $g:\times \left[K\right]\to \{0,1\}$. {remark} Lemma LABEL:lem:excess_score, together with Lemma B, stated in appendix, implies that

Hence, the inequality for all $g$ is implied from

The first of the above conditions is ensured if ${\text{sfd}}_0+min\{min\{{\text{sfd}}_1,0\}+{\text{sfd}}_2,0\}\ge 0$ (Lemma B) assumed in Theorem LABEL:thm:fair_optimal_LF and the second one is ensured by ($C1$) or ($C2$), as proved in Lemma B.