A Reductions Approach to Fair Classification

Introduction

Over the past few years, the media have paid considerable attention to machine learning systems and their ability to inadvertently discriminate against minorities, historically disadvantaged populations, and other protected groups when allocating resources (e.g., loans) or opportunities (e.g., jobs). In response to this scrutiny—and driven by ongoing debates and collaborations with lawyers, policy-makers, social scientists, and others (Barocas & Selbst 2016, e.g.,)—machine learning researchers have begun to turn their attention to the topic of “fairness in machine learning,” and, in particular, to the design of fair classification and regression algorithms.

In this paper we study the task of binary classification subject to fairness constraints with respect to a pre-defined protected attribute, such as race or sex. Previous work in this area can be divided into two broad groups of approaches.

The first group of approaches incorporate specific quantitative definitions of fairness into existing machine learning methods, often by relaxing the desired definitions of fairness, and only enforcing weaker constraints, such as lack of correlation (Woodworth et al. 2017; Zafar et al. 2017; Johnson et al. 2016; Kamishima et al. 2011; Donini et al. 2018, e.g.,). The resulting fairness guarantees typically only hold under strong distributional assumptions, and the approaches are tied to specific families of classifiers, such as SVMs.

The second group of approaches eliminate the restriction to specific classifier families and treat the underlying classification method as a “black box,” while implementing a wrapper that either works by pre-processing the data or post-processing the classifier’s predictions (Kamiran & Calders 2012; Feldman et al. 2015; Hardt et al. 2016; Calmon et al. 2017, e.g.,). Existing pre-processing approaches are specific to particular definitions of fairness and typically seek to come up with a single transformed data set that will work across all learning algorithms, which, in practice, leads to classifiers that still exhibit substantial unfairness (see our evaluation in Section 4). In contrast, post-processing allows a wider range of fairness definitions and results in provable fairness guarantees. However, it is not guaranteed to find the most accurate fair classifier, and requires test-time access to the protected attribute, which might not be available.

We present a general-purpose approach that has the key advantage of this second group of approaches—i.e., the underlying classification method is treated as a black box—but without the noted disadvantages. Our approach encompasses a wide range of fairness definitions, is guaranteed to yield the most accurate fair classifier, and does not require test-time access to the protected attribute. Specifically, our approach allows any definition of fairness that can be formalized via linear inequalities on conditional moments, such as demographic parity or equalized odds (see Section 2.1). We show how binary classification subject to these constraints can be reduced to a sequence of cost-sensitive classification problems. We require only black-box access to a cost-sensitive classification algorithm, which does not need to have any knowledge of the desired definition of fairness or protected attribute. We show that the solutions to our sequence of cost-sensitive classification problems yield a randomized classifier with the lowest (empirical) error subject to the desired fairness constraints.

Corbett-Davies et al. 2017 and Menon & Williamson 2018 begin with a similar goal to ours, but they analyze the Bayes optimal classifier under fairness constraints in the limit of infinite data. In contrast, our focus is algorithmic, our approach applies to any classifier family, and we obtain finite-sample guarantees. Dwork et al. 2018 also begin with a similar goal to ours. Their approach partitions the training examples into subsets according to protected attribute values and then leverages transfer learning to jointly learn from these separate data sets. Our approach avoids partitioning the data and assumes access only to a classification algorithm rather than a transfer learning algorithm.

A preliminary version of this paper appeared at the FAT/ML workshop (Agarwal et al. 2017), and led to extensions with more general optimization objectives (Alabi et al. 2018) and combinatorial protected attributes (Kearns et al. 2018).

In the next section, we formalize our problem. While we focus on two well-known quantitative definitions of fairness, our approach also encompasses many other previously studied definitions of fairness as special cases. In Section 3, we describe our reductions approach to fair classification and its guarantees in detail. The experimental study in Section 4 shows that our reductions compare favorably to three baselines, while overcoming some of their disadvantages and also offering the flexibility of picking a suitable accuracy–fairness tradeoff. Our results demonstrate the utility of having a general-purpose approach for combining machine learning methods and quantitative fairness definitions.

Problem Formulation

We consider a binary classification setting where the training examples consist of triples $(X,A,Y)$, where $X\in\mathcal{X}$ is a feature vector, $A\in\mathcal{A}$ is a protected attribute, and $Y\in\{0,1\}$ is a label. The feature vector $X$ can either contain the protected attribute $A$ as one of the features or contain other features that are arbitrarily indicative of $A$. For example, if the classification task is to predict whether or not someone will default on a loan, each training example might correspond to a person, where $X$ represents their demographics, income level, past payment history, and loan amount; $A$ represents their race; and $Y$ represents whether or not they defaulted on that loan. Note that $X$ might contain their race as one of the features or, for example, contain their zipcode—a feature that is often correlated with race. Our goal is to learn an accurate classifier $h:\mathcal{X}\to\{0,1\}$ from some set (i.e., family) of classifiers $\mathcal{H}$, such as linear threshold rules, decision trees, or neural nets, while satisfying some definition of fairness. Note that the classifiers in $\mathcal{H}$ do not explicitly depend on $A$.

We focus on two well-known quantitative definitions of fairness that have been considered in previous work on fair classification; however, our approach also encompasses many other previously studied definitions of fairness as special cases, as we explain at the end of this section.

The first definition—demographic (or statistical) parity---can be thought of as a stronger version of the US Equal Employment Opportunity Commission’s ‘‘four-fifths rule,’’ which requires that the ‘‘selection rate for any race, sex, or ethnic group [must be at least] four-fifths (4/5) (or eighty percent) of the rate for the group with the highest rate.’’ See the Uniform Guidelines on Employment Selection Procedures, 29 C.F.R. §1607.4(D) (2015).

The second definition—equalized odds—was recently proposed by Hardt et al. 2016 to remedy two previously noted flaws with demographic parity (Dwork et al. 2012). First, demographic parity permits a classifier which accurately classifies data points with one value ${A=a}$, such as the value $a$ with the most data, but makes random predictions for data points with ${A\neq a}$ as long as the probabilities of ${h(X)=1}$ match. Second, demographic parity rules out perfect classifiers whenever $Y$ is correlated with $A$. In contrast, equalized odds suffers from neither of these flaws.

We now show how each definition can be viewed as a special case of a general set of linear constraints of the form

where $g_{j}:{\mathcal{X}\times\mathcal{A}\times\{0,1\}\times\{0,1\}}\to$ and $\mathcal{E}_{j}$ is an event defined with respect to $(X,A,Y)$. Crucially, $g_{j}$ depends on $h$, while $\mathcal{E}_{j}$ cannot depend on $h$ in any way.

demographic parity can be expressed as equation (1), where $\mathcal{K}=\mathcal{A}\times\{+,-\}$, $M_{(a,+),a^{\prime}}=\mathbf{1}\{a^{\prime}=a\}$, $M_{(a,+),\star}=-1$, $M_{(a,-),a^{\prime}}=-\mathbf{1}\{a^{\prime}=a\}$, $M_{(a,-),\star}=1$, and $\mathbf{c}=\boldsymbol{0}$. Expressing each equality constraint as a pair of inequality constraints allows us to control the extent to which each constraint is enforced by positing $c_{k}>0$ for some (or all) $k$.

As a result, equalized odds can be expressed as equation (1), where $\mathcal{K}={\mathcal{A}\times\mathcal{Y}\times\{+,-\}}$, $M_{(a,y,+),(a^{\prime},y^{\prime})}=\mathbf{1}\{a^{\prime}\!\!=\!a,\,y^{\prime}\!\!=\!y\}$, $M_{(a,y,+),(\star,y^{\prime})}=-1$, $M_{(a,y,-),(a^{\prime},y^{\prime})}=-\mathbf{1}\{a^{\prime}\!\!=\!a,\,y^{\prime}\!\!=\!y\}$, $M_{(a,y,-),(\star,y^{\prime})}=1$, and $\mathbf{c}=\mathbf{0}$. Again, we can posit $c_{k}>0$ for some (or all) $k$ to allow small violations of some (or all) of the constraints.

Although we omit the details, we note that many other previously studied definitions of fairness can also be expressed as equation (1). For example, equality of opportunity (Hardt et al. 2016) (also known as balance for the positive class; Kleinberg et al. 2017), balance for the negative class (Kleinberg et al. 2017), error-rate balance (Chouldechova 2017), overall accuracy equality (Berk et al. 2017), and treatment equality (Berk et al. 2017) can all be expressed as equation (1); in contrast, calibration (Kleinberg et al. 2017) and predictive parity (Chouldechova 2017) cannot because to do so would require the event $\mathcal{E}_{j}$ to depend on $h$. We note that our approach can also be used to satisfy multiple definitions of fairness, though if these definitions are mutually contradictory, e.g., as described by Kleinberg et al. 2017, then our guarantees become vacuous.

2 Fair Classification

Furthermore, rather than just considering classifiers in the set $\mathcal{H}$, we can enlarge the space of possible classifiers by considering randomized classifiers that can be obtained via a distribution over $\mathcal{H}$. By considering randomized classifiers, we can achieve better accuracy–fairness tradeoffs than would otherwise be possible. A randomized classifier $Q$ makes a prediction by first sampling a classifier $h\in\mathcal{H}$ from $Q$ and then using $h$ to make the prediction. The resulting classification error is $\textup{err}(Q)=\sum_{h\in\mathcal{H}}Q(h)\,\textup{err}(h)$ and the conditional moments are $\boldsymbol{\mu}(Q)=\sum_{h\in\mathcal{H}}Q(h)\boldsymbol{\mu}(h)$ (see Appendix A for the derivation). Thus we seek to solve

where $\Delta$ is the set of all distributions over $\mathcal{H}$.

In practice, we do not know the true distribution over $(X,A,Y)$ and only have access to a data set of training examples $\{(X_{i},A_{i},Y_{i})\}_{i=1}^{n}$. We therefore replace $\textrm{err}(Q)$ and $\boldsymbol{\mu}(Q)$ in equation (3) with their empirical versions $\widehat{\textup{err}}(Q)$ and $\widehat{\boldsymbol{\mu}}(Q)$. Because of the sampling error in $\widehat{\boldsymbol{\mu}}(Q)$, we also allow errors in satisfying the constraints by setting $\widehat{c}_{k}=c_{k}+\varepsilon_{k}$ for all $k$, where $\varepsilon_{k}\geq 0$. After these modifications, we need to solve the empirical version of equation (3):

Reductions Approach

We now show how the problem (4) can be reduced to a sequence of cost-sensitive classification problems. We further show that the solutions to our sequence of cost-sensitive classification problems yield a randomized classifier with the lowest (empirical) error subject to the desired constraints.

We assume access to a cost-sensitive classification algorithm for the set $\mathcal{H}$. The input to such an algorithm is a data set of training examples $\{(X_{i},C_{i}^{0},C_{i}^{1})\}_{i=1}^{n}$, where $C_{i}^{0}$ and $C_{i}^{1}$ denote the losses—costs in this setting—for predicting the labels $0$ or $1$, respectively, for $X_{i}$. The algorithm outputs

This abstraction allows us to specify different costs for different training examples, which is essential for incorporating fairness constraints. Moreover, efficient cost-sensitive classification algorithms are readily available for several common classifier representations (Beygelzimer et al. 2005; Langford & Beygelzimer 2005; Fan et al. 1999, e.g.,). In particular, equation (5) is equivalent to a weighted classification problem, where the input consists of labeled examples $\{(X_{i},Y_{i},W_{i})\}_{i=1}^{n}$ with $Y_{i}\in\{0,1\}$ and $W_{i}\geq 0$, and the goal is to minimize the weighted classification error $\sum_{i=1}^{n}W_{i}\,\mathbf{1}\{h(X_{i})\neq Y_{i}\}$. This is equivalent to equation (5) if we set $W_{i}=\lvert C_{i}^{0}-C_{i}^{1}\rvert$ and $Y_{i}=\mathbf{1}\{C_{i}^{0}\geq C_{i}^{1}\}$.

2 Reduction

Because $L$ is linear in $Q$ and $\boldsymbol{\lambda}$ and the domains of $Q$ and $\boldsymbol{\lambda}$ are convex and compact, both problems have solutions (which we denote by $Q^{\dagger}$ and $\boldsymbol{\lambda}^{\dagger}$) and the minimum value of (P) and the maximum value of (D) are equal and coincide with $L(Q^{\dagger},\boldsymbol{\lambda}^{\dagger})$. Thus, $(Q^{\dagger},\boldsymbol{\lambda}^{\dagger})$ is the saddle point of $L$ (Rockafellar 1970, Corollary 37.6.2 and Lemma 36.2 of).

We find the saddle point by using the standard scheme of Freund & Schapire 1996, developed for the equivalent problem of solving for an equilibrium in a zero-sum game. From game-theoretic perspective, the saddle point can be viewed as an equilibrium of a game between two players: the $Q$-player choosing $Q$ and the $\boldsymbol{\lambda}$-player choosing $\boldsymbol{\lambda}$. The Lagrangian $L(Q,\boldsymbol{\lambda})$ specifies how much the $Q$-player has to pay to the $\boldsymbol{\lambda}$-player after they make their choices. At the saddle point, neither player wants to deviate from their choice.

Our algorithm finds an approximate equilibrium in which neither player can gain more than $\nu$ by changing their choice (where $\nu>0$ is an input to the algorithm). Such an approximate equilibrium corresponds to a $\nu$-approximate saddle point of the Lagrangian, which is a pair $(\widehat{Q},\widehat{\boldsymbol{\lambda}})$, where

We proceed iteratively by running a no-regret algorithm for the $\boldsymbol{\lambda}$-player, while executing the best response of the $Q$-player. Following Freund & Schapire 1996, the average play of both players converges to the saddle point. We run the exponentiated gradient algorithm (Kivinen & Warmuth 1997) for the $\boldsymbol{\lambda}$-player and terminate as soon as the suboptimality of the average play falls below the pre-specified accuracy $\nu$. The best response of the $Q$-player can always be chosen to put all of the mass on one of the candidate classifiers $h\in\mathcal{H}$, and can be implemented by a single call to a cost-sensitive classification algorithm for the set $\mathcal{H}$.

Algorithm 1 fully implements this scheme, except for the functions $\textsc{Best}_{\boldsymbol{\lambda}}$ and $\textsc{Best}_{h}$, which correspond to the best-response algorithms of the two players. (We need the best response of the $\boldsymbol{\lambda}$-player to evaluate whether the suboptimality of the current average play has fallen below $\nu$.) The two best response functions can be calculated as follows.

The best response of the $\boldsymbol{\lambda}$-player for a given $Q$ is any maximizer of $L(Q,\boldsymbol{\lambda})$ over all valid $\boldsymbol{\lambda}$s. In our setting, it can always be chosen to be either $\mathbf{0}$ or put all of the mass on the most violated constraint. Letting $\widehat{\boldsymbol{\gamma}}(Q)\coloneqq\mathbf{M}\widehat{\boldsymbol{\mu}}(Q)$ and letting $\mathbf{e}_{k}$ denote the $k^{\textrm{th}}$ vector of the standard basis, $\textsc{Best}_{\boldsymbol{\lambda}}(Q)$ returns

Besth​(𝝀)\textsc{Best}_{h}(\boldsymbol{\lambda}): the best response of the QQ-player.

Letting $\rho\coloneqq\max_{h}\lVert\mathbf{M}\widehat{\boldsymbol{\mu}}(h)-\widehat{\mathbf{c}}\rVert_{\infty}$, Algorithm 1 satisfies the inequality

Thus, for $\eta=\!\frac{\nu}{2\rho^{2}B}$, Algorithm 1 will return a $\nu$-approximate saddle point of $L$ in at most $\frac{4\rho^{2}B^{2}\log(\lvert\mathcal{K}\rvert+1)}{\nu^{2}}$ iterations.

Using the matrix $\mathbf{M}$ for demographic parity as described in Section 2, the cost-sensitive reduction for a vector of Lagrange multipliers $\boldsymbol{\lambda}$ uses costs

For equalized odds, the cost-sensitive reduction for a vector of Lagrange multipliers $\boldsymbol{\lambda}$ uses costs

3 Error Analysis

Our ultimate goal, as formalized in equation (3), is to minimize the classification error while satisfying fairness constraints under a true but unknown distribution over $(X,A,Y)$. In the process of deriving Algorithm 1, we introduced three different sources of error. First, we replaced the true classification error and true moments with their empirical versions. Second, we introduced a bound $B$ on the magnitude of $\boldsymbol{\lambda}$. Finally, we only run the optimization algorithm for a fixed number of iterations, until it reaches suboptimality level $\nu$. The first source of error, due to the use of empirical rather than true quantities, is unavoidable and constitutes the underlying statistical error. The other two sources of error, the bound $B$ and the suboptimality level $\nu$, stem from the optimization algorithm and can be driven arbitrarily small at the cost of additional iterations. In this section, we show how the statistical error and the optimization error affect the true accuracy and the fairness of the randomized classifier returned by Algorithm 1—in other words, how well Algorithm 1 solves our original problem (3).

To bound the statistical error, we use the Rademacher complexity of the classifier family $\mathcal{H}$, which we denote by $R_{n}(\mathcal{H})$, where $n$ is the number of training examples. We assume that $R_{n}(\mathcal{H})\leq Cn^{-\alpha}$ for some $C\geq 0$ and $\alpha\leq 1/2$. We note that $\alpha=1/2$ in the vast majority of classifier families, including norm-bounded linear functions (see Theorem 1 of Kakade et al. 2009), neural networks (see Theorem 18 of Bartlett & Mendelson 2002), and classifier families with bounded VC dimension (see Lemma 4 and Theorem 6 of Bartlett & Mendelson 2002).

Recall that in our empirical optimization problem we assume that $\widehat{c}_{k}=c_{k}+\varepsilon_{k}$, where $\varepsilon_{k}\geq 0$ are error bounds that account for the discrepancy between $\boldsymbol{\mu}(Q)$ and $\widehat{\boldsymbol{\mu}}(Q)$. In our analysis, we assume that these error bounds have been set in accordance with the Rademacher complexity of $\mathcal{H}$.

There exists $C,C^{\prime}\geq 0$ and $\alpha\leq 1/2$ such that $R_{n}(\mathcal{H})\leq Cn^{-\alpha}$ and $\varepsilon_{k}=C^{\prime}\sum_{j\in\mathcal{J}}\lvert M_{k,j}\rvert n_{j}^{-\alpha}$, where $n_{j}$ is the number of data points that fall in $\mathcal{E}_{j}$,

The optimization error can be bounded via a careful analysis of the Lagrangian and the optimality conditions of (P) and (D). Combining the three different sources of error yields the following bound, which we prove in Appendix C.

where $\smash{\widetilde{O}(\cdot)}$ suppresses polynomial dependence on $\ln(1/\delta)$. If $np^{\star}_{j}\geq 8\log(2/\delta)$ for all $j$, then, for all $k$,

In other words, the solution returned by Algorithm 1 achieves the lowest feasible classification error on the true distribution up to the optimization error, which grows linearly with $\nu$, and the statistical error, which grows as $n^{-\alpha}$. Therefore, if we want to guarantee that the optimization error does not dominate the statistical error, we should set $\nu\propto n^{-\alpha}$. The fairness constraints on the true distribution are satisfied up to the optimization error $(1+2\nu)\,\,/B$ and up to the statistical error. Because the statistical error depends on the moments, and the error in estimating the moments grows as $n_{j}^{-\alpha}\geq n^{-\alpha}$, we can set $B\propto n^{\alpha}$ to guarantee that the optimization error does not dominate the statistical error. Combining this reasoning with the learning rate setting of Theorem 1 yields the following theorem (proved in Appendix C).

Let $\rho\coloneqq\max_{h}\lVert\mathbf{M}\widehat{\boldsymbol{\mu}}(h)-\widehat{\mathbf{c}}\rVert_{\infty}$. Let Assumption 1 hold for $C^{\prime}\geq 2C+2+\sqrt{\ln(4/\delta)\,/\,2}$, where $\delta>0$. Let $Q^{\star}$ minimize $\textup{err}(Q)$ subject to $\mathbf{M}\boldsymbol{\mu}(Q)\leq\mathbf{c}$. Then Algorithm 1 with $\nu\propto n^{-\alpha}$, $B\propto n^{\alpha}$ and $\eta\propto\rho^{-2}n^{-2\alpha}$ terminates in $O(\rho^{2}n^{4\alpha}\ln{\lvert\mathcal{K}\rvert})$ iterations and returns $\widehat{Q}$, which with probability at least $1-(|\mathcal{J}|+1)\delta$ satisfies

If $n_{a}$ denotes the number of training examples with $A_{i}=a$, then Assumption 1 states that we should set $\varepsilon_{(a,+)}=\varepsilon_{(a,-)}=C^{\prime}(n_{a}^{-\alpha}+n^{-\alpha})$ and Theorem 3 then shows that for a suitable setting of $C^{\prime}$, $\nu$, $B$, and $\eta$, Algorithm 1 will return a randomized classifier $\widehat{Q}$ with the lowest feasible classification error up to $\widetilde{O}(n^{-\alpha})$ while also approximately satisfying the fairness constraints

Similarly, if $n_{(a,y)}$ denotes the number of examples with $A_{i}=a$ and $Y_{i}=y$ and $n_{(\star,y)}$ denotes the number of examples with $Y_{i}=y$, then Assumption 1 states that we should set $\varepsilon_{(a,y,+)}=\varepsilon_{(a,y,-)}=C^{\prime}(n_{(a,y)}^{-\alpha}+n_{(\star,y)}^{-\alpha})$ and Theorem 3 then shows that for a suitable setting of $C^{\prime}$, $\nu$, $B$, and $\eta$, Algorithm 1 will return a randomized classifier $\widehat{Q}$ with the lowest feasible classification error up to $\widetilde{O}(n^{-\alpha})$ while also approximately satisfying the fairness constraints

4 Grid Search

In some situations, it is preferable to select a deterministic classifier, even if that means a lower accuracy or a modest violation of the fairness constraints. A set of candidate classifiers can be obtained from the saddle point $(Q^{\dagger},\boldsymbol{\lambda}^{\dagger})$. Specifically, because $Q^{\dagger}$ is a minimizer of $L(Q,\boldsymbol{\lambda}^{\dagger})$ and $L$ is linear in $Q$, the distribution $Q^{\dagger}$ puts non-zero mass only on classifiers that are the $Q$-player’s best responses to $\boldsymbol{\lambda}^{\dagger}$. If we knew $\boldsymbol{\lambda}^{\dagger}$, we could retrieve one such best response via the reduction to cost-sensitive learning introduced in Section 3.2.

We can compute $\boldsymbol{\lambda}^{\dagger}$ using Algorithm 1, but when the number of constraints is very small, as is the case for demographic parity or equalized odds with a binary protected attribute, it is also reasonable to consider a grid of values $\boldsymbol{\lambda}$, calculate the best response for each value, and then select the value with the desired tradeoff between accuracy and fairness.

When the protected attribute is binary, e.g., $A\in\{a,a^{\prime}\}$, then the grid search can in fact be conducted in a single dimension. The reduction formally takes two real-valued arguments $\lambda_{a}$ and $\lambda_{a^{\prime}}$, and then adjusts the costs for predicting $h(X_{i})=1$ by the amounts

respectively, on the training examples with $A_{i}=a$ and $A_{i}=a^{\prime}$. These adjustments satisfy $p_{a}\delta_{a}+p_{a^{\prime}}\delta_{a^{\prime}}=0$, so instead of searching over $\lambda_{a}$ and $\lambda_{a^{\prime}}$, we can carry out the grid search over $\delta_{a}$ alone and apply the adjustment $\delta_{a^{\prime}}=-p_{a}\delta_{a}/p_{a^{\prime}}$ to the protected attribute value $a^{\prime}$.

With three attribute values, e.g., $A\in\{a,a^{\prime},a^{\prime\prime}\}$, we similarly have $p_{a}\delta_{a}+p_{a^{\prime}}\delta_{a^{\prime}}+p_{a^{\prime\prime}}\delta_{a^{\prime\prime}}=0$, so it suffices to conduct grid search in two dimensions rather than three.

If $A\in\{a,a^{\prime}\}$, we obtain the adjustment

for an example with protected attribute value $a$ and label $y$, and similarly for protected attribute value $a^{\prime}$. In this case, separately for each $y$, the adjustments satisfy

so it suffices to do the grid search over $\delta_{(a,0)}$ and $\delta_{(a,1)}$ and set the parameters for $a^{\prime}$ to $\delta_{(a^{\prime},y)}=-p_{(a,y)}\delta_{(a,y)}/p_{(a^{\prime},y)}$.

Experimental Results

We now examine how our exponentiated-gradient reduction https://github.com/Microsoft/fairlearn performs at the task of binary classification subject to either demographic parity or equalized odds. We provide an evaluation of our grid-search reduction in Appendix D.

We compared our reduction with the score-based post-processing algorithm of Hardt et al. 2016, which takes as its input any classifier, (i.e., a standard classifier without any fairness constraints) and derives a monotone transformation of the classifier’s output to remove any disparity with respect to the training examples. This post-processing algorithm works with both demographic parity and equalized odds, as well as with binary and non-binary protected attributes.

For demographic parity, we also compared our reduction with the reweighting and relabeling approaches of Kamiran & Calders 2012. Reweighting can be applied to both binary and non-binary protected attributes and operates by changing importance weights on each example with the goal of removing any statistical dependence between the protected attribute and label. Although reweighting was developed for demographic parity, the weights that it induces are achievable by our grid search, albeit the grid search for equalized odds rather than demographic parity. Relabeling was developed for binary protected attributes. First, a classifier is trained on the original data (without considering fairness). The training examples close to the decision boundary are then relabeled to remove all disparity while minimally affecting accuracy. The final classifier is then trained on the relabeled data.

As the base classifiers for our reductions, we used the weighted classification implementations of logistic regression and gradient-boosted decision trees in scikit-learn (Pedregosa et al. 2011). In addition to the three baselines described above, we also compared our reductions to the “unconstrained” classifiers trained to optimize accuracy only.

We used four data sets, randomly splitting each one into training examples (75%) and test examples (25%):

The adult income data set (Lichman 2013) (48,842 examples). Here the task is to predict whether someone makes more than $50k per year, with gender as the protected attribute. To examine the performance for non-binary protected attributes, we also conducted another experiment with the same data, using both gender and race (binarized into white and non-white) as the protected attribute. Relabeling, which requires binary protected attributes, was therefore not applicable here.

ProPublica’s COMPAS recidivism data (7,918 examples). The task is to predict recidivism from someone’s criminal history, jail and prison time, demographics, and COMPAS risk scores, with race as the protected attribute (restricted to white and black defendants).

Law School Admissions Council’s National Longitudinal Bar Passage Study (Wightman 1998) (20,649 examples). Here the task is to predict someone’s eventual passage of the bar exam, with race (restricted to white and black only) as the protected attribute.

The Dutch census data set (Dutch Central Bureau for Statistics, 2001) (60,420 examples). Here the task is to predict whether or not someone has a prestigious occupation, with gender as the protected attribute.

While all the evaluated algorithms require access to the protected attribute $A$ at training time, only the post-processing algorithm requires access to $A$ at test time. For a fair comparison, we included $A$ in the feature vector $X$, so all algorithms had access to it at both the training time and test time.

We ran our reduction across a wide range of tradeoffs between the classification error and fairness constraints. We considered $\varepsilon\in\{0.001,\dotsc,0.1\}$ and for each value ran Algorithm 1 with $\widehat{c}_{k}=\varepsilon$ across all $k$. As expected, the returned randomized classifiers tracked the training Pareto frontier (see Figure 2 in Appendix D). In Figure 1, we evaluate these classifiers alongside the baselines on the test data.

For all the data sets, the range of classification errors is much smaller than the range of constraint violations. Almost all the approaches were able to substantially reduce or remove disparity without much impact on classifier accuracy. One exception was the Dutch census data set, where the classification error increased the most in relative terms.

Our reduction generally dominated or matched the baselines. The relabeling approach frequently yielded solutions that were not Pareto optimal. Reweighting yielded solutions on the Pareto frontier, but often with substantial disparity. As expected, post-processing yielded disparities that were statistically indistinguishable from zero, but the resulting classification error was sometimes higher than achieved by our reduction under a statistically indistinguishable disparity. In addition, and unlike the post-processing algorithm, our reduction can achieve any desired accuracy–fairness tradeoff, allows a wider range of fairness definitions, and does not require access to the protected attribute at test time.

Our grid-search reduction, evaluated in Appendix D, sometimes failed to achieve the lowest disparities on the training data, but its performance on the test data very closely matched that of our exponentiated-gradient reduction. However, if the protected attribute is non-binary, then grid search is not feasible. For instance, for the version of the adult income data set where the protected attribute takes on four values, the grid search would need to span three dimensions for demographic parity and six dimensions for equalized odds, both of which are prohibitively costly.

Conclusion

We presented two reductions for achieving fairness in a binary classification setting. Our reductions work for any classifier representation, encompass many definitions of fairness, satisfy provable guarantees, and work well in practice.

Our reductions optimize the tradeoff between accuracy and any (single) definition of fairness given training-time access to protected attributes. Achieving fairness when training-time access to protected attributes is unavailable remains an open problem for future research, as does the navigation of tradeoffs between accuracy and multiple fairness definitions.

Acknowledgements

We would like to thank Aaron Roth, Sam Corbett-Davies, and Emma Pierson for helpful discussions.

References

Appendix A Error and Fairness for Randomized Classifiers

where the last equality follows because $\mathcal{E}_{j}$ is independent of the choice of $h$.

Appendix B Proof of Theorem 1

The proof follows immediately from the analysis of Freund & Schapire 1996 applied to the Exponentiated Gradient (EG) algorithm (Kivinen & Warmuth 1997), which in our specific case is also equivalent to Hedge (Freund & Schapire 1997).

We interpret $\mathbf{r}^{\prime}_{t}$ as the reward vector for the $\boldsymbol{\lambda}$-player. The choices of $\boldsymbol{\lambda}^{\prime}_{t}$ then correspond to those of the EG algorithm with the learning rate $\eta$. By the assumption of the theorem we have $\lVert\mathbf{r}^{\prime}_{t}\rVert_{\infty}=\lVert\mathbf{r}_{t}\rVert_{\infty}\leq\rho$. The regret bound for EG, specifically, Corollary 2.14 of Shalev-Shwartz 2012, then states that for any $\boldsymbol{\lambda}^{\prime}\in\Lambda^{\prime}$,

Therefore, by equations (7) and (8), we also have for any $\boldsymbol{\lambda}\in\Lambda$,

This regret bound can be used to bound the suboptimality of $L(\widehat{Q}_{T},\widehat{\boldsymbol{\lambda}}_{T})$ in $\widehat{\boldsymbol{\lambda}}_{T}$ as follows:

Equation (10) follows from the regret bound (9). Equation (11) follows because $L(h_{t},\boldsymbol{\lambda}_{t})\leq L(Q,\boldsymbol{\lambda}_{t})$ for all $Q$ by the choice of $h_{t}$ as the best response of the $Q$-player. Finally, equation (12) follows by linearity of $L(Q,\boldsymbol{\lambda})$ in $\boldsymbol{\lambda}$. Thus, we have for all $\boldsymbol{\lambda}\in\Lambda$,

where equation (14) follows by linearity of $L(Q,\boldsymbol{\lambda})$ in $\boldsymbol{\lambda}$, equation (15) follows by the optimality of $h_{t}$ with respect to $\widehat{\boldsymbol{\lambda}}_{t}$, equation (16) from the regret bound (9), and equation (17) by linearity of $L(Q,\boldsymbol{\lambda})$ in $Q$. Thus, for all $Q$,

Equations (13) and (18) immediately imply that for any $T\geq 1$,

The second part of the theorem follows by plugging in $\eta=\frac{\nu}{2\rho^{2}B}$ and verifying that if $T\geq\frac{4\rho^{2}B^{2}\log(\lvert\mathcal{K}\rvert+1)}{\nu^{2}}$ then

Appendix C Proofs of Theorems 2 and 3

The bulk of this appendix proves the following theorem, which will immediately imply Theorems 2 and 3.

Let $(\widehat{Q},\boldsymbol{\widehat{\lambda}})$ be any $\nu$-approximate saddle point of $L$ with

Let $Q^{\star}$ minimize $\textup{err}(Q)$ subject to $\mathbf{M}\boldsymbol{\mu}(Q)\leq\mathbf{c}$. Then with probability at least $1-(|\mathcal{J}|+1)\delta$, the distribution $\widehat{Q}$ satisfies

We first establish that the pair $(\widehat{Q},\boldsymbol{\widehat{\lambda}})$ satisfies an approximate version of complementary slackness. For the statement and proof of the following lemma, recall that $\widehat{\boldsymbol{\gamma}}(Q)=\mathbf{M}\widehat{\boldsymbol{\mu}}(Q)$, so the empirical fairness constraints can be written as $\widehat{\boldsymbol{\gamma}}(Q)\leq\widehat{\mathbf{c}}$ and the Lagrangian $L$ can be written as

The pair $(\widehat{Q},\boldsymbol{\widehat{\lambda}})$ satisfies

where we abbreviate $x_{+}=\max\{x,0\}$ for any real number $x$.

We show that the lemma follows from the optimality conditions (19). We consider a dual variable $\boldsymbol{\lambda}$ defined as

where $\mathbf{e}_{k}$ denotes the $k$th vector of the standard basis. Then we have by equations (19) and (20) that

and the lemma follows by our choice of $\boldsymbol{\lambda}$. ∎

Next two lemmas bound the empirical error of $\widehat{Q}$ and also bound the amount by which $\widehat{Q}$ violates the empirical fairness constraints.

The distribution $\widehat{Q}$ satisfies $\widehat{\textup{err}}(\widehat{Q})\leq\widehat{\textup{err}}(Q)+2\nu$ for any $Q$ satisfying the empirical fairness constraints, i.e., any $Q$ such that $\widehat{\boldsymbol{\gamma}}(Q)\leq\widehat{\mathbf{c}}$.

Assume that $Q$ satisfies $\widehat{\boldsymbol{\gamma}}(Q)\leq\widehat{\mathbf{c}}$. Since $\boldsymbol{\widehat{\lambda}}\geq\mathbf{0}$, we have

The optimality conditions (19) imply that

We next invoke Lemma 1 to lower bound $L(\widehat{Q},\widehat{\boldsymbol{\lambda}})$ as

Combining the upper and lower bounds on $L(\widehat{Q},\widehat{\boldsymbol{\lambda}})$ completes the proof. ∎

Assume that the empirical fairness constraints $\widehat{\boldsymbol{\gamma}}(Q)\leq\widehat{\mathbf{c}}$ are feasible. Then the distribution $\widehat{Q}$ approximately satisfies all empirical fairness constraints:

Let $Q$ satisfy $\widehat{\boldsymbol{\gamma}}(Q)\leq\widehat{\mathbf{c}}$. Applying the same upper and lower bound on $L(\widehat{Q},\boldsymbol{\widehat{\lambda}})$ as in the proof of Lemma 2, we obtain

We can further upper bound $\widehat{\textup{err}}(Q)-\widehat{\textup{err}}(\widehat{Q})$ by 1 and use $x\leq x_{+}$ for any real number $x$ to complete the proof. ∎

It remains to lift the bounds on empirical classification error and constraint violation into the corresponding bounds on true classification error and the violation of true constraints. We will use the standard machinery of uniform convergence bounds via the (worst-case) Rademacher complexity.

Let $\mathcal{F}$ be a class of functions $f:\mathcal{Z}\to$ over some space $\mathcal{Z}$. Then the (worst-case) Rademacher complexity of $\mathcal{F}$ is defined as

We first prove concentration of generic moments derived from classifiers $h\in\mathcal{H}$ and then move to bounding the deviations from true classification error and true fairness constraints.

Let $g:\mathcal{X}\times\mathcal{A}\times\{0,1\}\times\{0,1\}\to$ be any function and let $D$ be a distribution over $(X,A,Y)$. Then with probability at least $1-\delta$, for all $h\in\mathcal{H}$,

where the expectation is with respect to $D$ and the empirical expectation is based on $n$ i.i.d. draws from $D$.

Let $\mathcal{F}\coloneqq\{f_{h}\}_{h\in\mathcal{H}}$ be the class of functions $f_{h}:(x,y,a)\mapsto g\bigl(x,y,a,h(x)\bigr)$. By Theorem 3.2 of Boucheron et al. 2005, we then have with probability at least $1-\delta$, for all $h$,

We will next bound $R_{n}(\mathcal{F})$ in terms of $R_{n}(\mathcal{H})$. Since $h(x)\in\{0,1\}$, we can write

Since $\bigl\lvert g(x,a,y,0)\bigr\rvert\leq 1$ and $\bigl\lvert g(x,a,y,1)-g(x,a,y,0)\bigr\rvert\leq 1$, we can invoke Theorem 12(5) of Bartlett & Mendelson 2002 for bounding function classes shifted by an offset, in our case $g(x,a,y,0)$, and Theorem 4.4 of Ledoux & Talagrand 1991 for bounding function classes under contraction, in our case $g(x,a,y,1)-g(x,a,y,0)$, yielding

Together with the bound (21), this proves the lemma. ∎

With probability at least $1-\delta$, for all $Q\in\Delta$,

We first use Lemma 4 with $g:(x,a,y,\hat{y})\mapsto\mathbf{1}\{y\neq\hat{y}\}$ to obtain, with probability $1-\delta$, for all $h$,

For any $j\in\mathcal{J}$, with probability at least $1-\delta$, for all $Q$,

If $np^{\star}_{j}\geq 8\log(2/\delta)$, then with probability at least $1-\delta$, for all $Q$,

Our proof largely follows the proof of Lemma 2 of Woodworth et al. 2017, with appropriate modifications for our more general constraint definition. Let $S_{j}\coloneqq\{i\in[n]:\>(X_{i},\!A_{i},\!Y_{i})\in\mathcal{E}_{j}\}$ be the set of indices such that the corresponding examples fall in the event $\mathcal{E}_{j}$. Note that we have defined $n_{j}=|S_{j}|$. Let $D(\cdot)$ denote the joint distribution of $(X,A,Y)$. Then, conditioned on $i\in S_{j}$, the random variables $g_{j}(X_{i},\!A_{i},\!Y_{i},\!h(X_{i}))$ are i.i.d. draws from the distribution $D(\cdot\mathbin{|}\mathcal{E}_{j})$, with mean $\mu_{j}(h)$. Applying Lemma 4 with $g_{j}$ and the distribution $D(\cdot\mathbin{|}\mathcal{E}_{j})$ therefore yields, with probability $1-\delta$, for all $h$,

The lemma now follows by taking a convex combination over $h$. ∎

We now use the lemmas derives so far to prove Theorem 4. We first use Lemma 6 to bound the gap between the empirical and population fairness constraints. The lemma implies that with probability at least $1-\lvert\mathcal{J}\rvert\delta$, for all $k\in\mathcal{K}$ and all $Q\in\Delta$,

Note that our choice of $\widehat{\mathbf{c}}$ along with equation (22) ensure that $\widehat{\gamma}_{k}(Q^{\star})\leq\widehat{c}_{k}$ for all $k\in\mathcal{K}$. Using Lemma 2 allows us to conclude that

We now invoke Lemma 5 twice, once for $\widehat{\textup{err}}(\widehat{Q})$ and once for $\widehat{\textup{err}}(Q^{\star})$, proving the first statement of the theorem.

The above shows that $Q^{\star}$ satisfies the empirical fairness constraints, so we can use Lemma 3, which together with equation (22) yields

proving the second statement of the theorem. ∎

We are now ready to prove Theorems 2 and 3

This follows immediately from Theorem 1 and the first part of Theorem 2. ∎

Appendix D Additional Experimental Results

In this appendix we present more complete experimental results. We present experimental results for both the training and test data. We evaluate the exponentiated-gradient as well as the grid-search variants of our reductions. And, finally, we consider extensions of reweighting and relabeling beyond the specific tradeoffs proposed by Kamiran & Calders 2012. Specifically, we introduce a scaling parameter that interpolates between the prescribed tradeoff (specific importance weights or the number of examples to relabel) and the unconstrained classifier (uniform weights or zero examples to relabel). The training data results are shown in Figure 2. The test set results are shown in Figure 3.