On Fairness and Calibration

Introduction

Recently, there has been growing concern about errors of machine learning algorithms in sensitive domains – including criminal justice, online advertising, and medical testing – which may systematically discriminate against particular groups of people . A recent high-profile example of these concerns was raised by the news organization ProPublica, who studied a risk-assessment tool that is widely used in the criminal justice system. This tool assigns to each criminal defendant an estimated probability that they will commit a future crime. ProPublica found that the risk estimates assigned to defendants who did not commit future crimes were on average higher among African-American defendants than Caucasian defendants . This is a form of false-positive error, and in this case it disproportionately affected African-American defendants. To mitigate issues such as these, the machine learning community has proposed different frameworks that attempt to quantify fairness in classification . A recent and particularly noteworthy framework is Equalized Odds (also referred to as Disparate Mistreatment ), For the remainder of the paper, we will use Equalized Odds to refer to this notion of non-discrimination. which constrains classification algorithms such that no error type (false-positive or false-negative) disproportionately affects any population subgroup. This notion of non-discrimination is feasible in many settings, and researchers have developed tractable algorithms for achieving it .

When risk tools are used in practice, a key goal is that they are calibrated: if we look at the set of people who receive a predicted probability of $p$, we would like a $p$ fraction of the members of this set to be positive instances of the classification problem . Moreover, if we are concerned about fairness between two groups $G_{1}$ and $G_{2}$ (e.g. African-American defendants and white defendants) then we would like this calibration condition to hold simultaneously for the set of people within each of these groups as well . Calibration is a crucial condition for risk tools in many settings. If a risk tool for evaluating defendants were not calibrated with respect to groups defined by race, for example, then a probability estimate of $p$ could carry different meaning for African-American and white defendants, and hence the tool would have the unintended and highly undesirable consequence of incentivizing judges to take race into account when interpreting its predictions. Despite the importance of calibration as a property, our understanding of how it interacts with other fairness properties is limited. We know from recent work that, except in the most constrained cases, it is impossible to achieve calibration while also satisfying Equalized Odds . However, we do not know how best to achieve relaxations of these guarantees that are feasible in practice.

Our goal is to further investigate the relationship between calibration and error rates. We show that even if the Equalized Odds conditions are relaxed substantially – requiring only that weighted sums of the group error rates match – it is still problematic to also enforce calibration. We provide necessary and sufficient conditions under which this calibrated relaxation is feasible. When feasible, it has a unique optimal solution that can be achieved through post-processing of existing classifiers. Moreover, we provide a simple post-processing algorithm to find this solution: withholding predictive information for randomly chosen inputs to achieve parity and preserve calibration. However, this simple post-processing method is fundamentally unsatisfactory: although the post-processed predictions of our information-withholding algorithm are “fair” in expectation, most practitioners would object to the fact that a non-trivial portion of the individual predictions are withheld as a result of coin tosses – especially in sensitive settings such as health care or criminal justice. The optimality of this algorithm thus has troubling implications and shows that calibration and error-rate fairness are inherently at odds (even beyond the initial results by and ).

Finally, we evaluate these theoretical findings empirically, comparing calibrated notions of non-discrimination against the (uncalibrated) Equalized Odds framework on several datasets. These experiments further support our conclusion that calibration and error-rate constraints are in most cases mutually incompatible goals. In practical settings, it may be advisable to choose only one of these goals rather than attempting to achieve some relaxed notion of both.

Related Work

are considered necessary for empirical risk analysis tools . In practical applications, uncalibrated probability estimates can be misleading in the sense that the end user of these estimates has an incentive to mistrust (and therefore potentially misuse) them. We note however that calibration does not remove all potential for misuse, as the end user’s biases might cause her or him to treat estimates differently based on group membership. There are several post-processing methods for producing calibrated outputs from classification algorithms. For example, Platt Scaling passes outputs through a learned sigmoid function, transforming them into calibrated probabilities. Histogram Binning and Isotonic Regression learn a general monotonic function from outputs to probabilities. See and for empirical comparisons of these methods.

Equalized Odds

, also referred to as Disparate Mistreatment , ensures that no error type disproportionately affects any particular group. Hardt et al. provide a post-processing technique to achieve this framework, while Zafar et al. introduce optimization constraints to achieve non-discrimination at training time. Recently, this framework has received significant attention from the algorithmic fairness community. Researchers have found that it is incompatible with other notions of fairness . Additionally, Woodworth et al. demonstrate that, under certain assumptions, post-processing methods for achieving non-discrimination may be suboptimal.

Alternative fairness frameworks

exist and are continuously proposed. We highlight several of these works, though by no means offer a comprehensive list. (More thorough reviews can be found in ). It has been shown that, under most frameworks of fairness, there is a trade-off between algorithmic performance and non-discrimination . Several works approach fairness through the lens of Statistical Parity . Under this definition, group membership should not affect the prediction of a classifier, i.e. members of different groups should have the same probability of receiving a positive-class prediction. However, it has been argued that Statistical Parity may not be applicable in many scenarios , as it attempts to guarantee equal representation. For example, it is inappropriate in criminal justice, where base rates differ across different groups. A related notion is Disparate Impact , which states that the prediction rates for any two groups should not differ by more than $80\%$ (a number motivated by legal requirements). Dwork et al. introduce a notion of fairness based on the idea that similar individuals should receive similar outcomes, though it challenging to achieve this notion in practice. Fairness has also been considered in online learning , unsupervised learning , and causal inference .

Problem Setup

If the classifier were to output either or $1$, this represents the standard notions of false-positive and false-negative rates. We now define the Equalized Odds framework (generalized for probabilistic classifiers), which aims to ensure that errors of a given type are not biased against any group.

Classifiers $h_{1}$ and $h_{2}$ exhibit Equalized Odds for groups $G_{1}$ and $G_{2}$ if $c_{fp}(h_{1})=c_{fp}(h_{2})$ and $c_{fn}(h_{1})=c_{fn}(h_{2})$.

As stated in the introduction, these two conditions do not necessarily prevent discrimination if the classifier predictions do not represent well-calibrated probabilities. Recall that calibration intuitively says that probabilities should carry semantic meaning: if there are 100 people in $G_{1}$ for whom $h_{1}(\mathbf{x})=0.6$, then we expect $60$ of them to belong to the positive class.

A classifier $h_{t}$ is perfectly calibrated if $\forall p\in$, \operatorname*{P}_{(\mathbf{x},y)\sim G_{t}}\bigl{[}y\!=\!1\mid h_{t}(\mathbf{x})\!=\!p\bigr{]}=p.

It is commonly accepted amongst practitioners that both classifiers $h_{1}$ and $h_{2}$ should be calibrated with respect to groups $G_{1}$ and $G_{2}$ to prevent discrimination . Intuitively, this prevents the probability scores from carrying group-specific information. Unfortunately, Kleinberg et al. (as well as , in a binary setting) prove that a classifier cannot achieve both calibration and Equalized Odds, even in an approximate sense, except in the most trivial of cases.

1 Geometric Characterization of Constraints

We now will characterize the calibration and error-rate constraints with simple geometric intuitions. Throughout the rest of this paper, all of our results can be easily derived from this interpretation. We begin by defining the region of classifiers which are trivial, or those that output a constant value for all inputs (i.e. $h^{c}(\mathbf{x})=c$, where $0\leq c\leq 1$ is a constant). We can visualize these classifiers on a graph with generalized false-positive rates on one axis and generalized false-negatives on the other. It follows from the definitions of generalized false-positive/false-negative rates and calibration that all trivial classifiers $h$ lie on the diagonal defined by $c_{fp}(h)+c_{fn}(h)=1$ (1(a)). Therefore, all classifiers that are “better than random” must lie below this diagonal in false-positive/false-negative space (the gray triangle in the figure). Any classifier that lies above the diagonal performs “worse than random,” as we can find a point on the trivial classifier diagonal with lower false-positive and false-negative rates.

Now we will characterize the set of calibrated classifiers for groups $G_{1}$ and $G_{2}$, which we denote as $\mathcal{H}^{*}_{1}$ and $\mathcal{H}^{*}_{2}$. Kleinberg et al. show that the generalized false-positive and false-negative rates of a calibrated classifier are linearly related by the base rate of the group: Throughout this work we will treat the calibration constraint as holding exactly; however, our results generalize to approximate settings as well. See the Supplementary Materials for more details.

In other words, $h_{1}$ lies on a line with slope $(1-\mu_{1})/\mu_{1}$ and $h_{2}$ lies on a line with slope $(1-\mu_{2})/\mu_{2}$ (1(a)). The lower endpoint of each line is the perfect classifier, which assigns the correct prediction with complete certainty to every input. The upper endpoint is a trivial classifier, as no calibrated classifier can perform “worse than random” (see Section S2 in Section S2). The only trivial classifier that satisfies the calibration condition for a group $G_{t}$ is the one that outputs the base rate $\mu_{t}$. We will refer to $h^{\mu_{1}}$ and $h^{\mu_{2}}$ as the trivial classifiers, calibrated for groups $G_{1}$ and $G_{2}$ respectively. It follows from the definitions that $c_{fp}(h^{\mu_{1}})=\mu_{1}$ and $c_{fn}(h^{\mu_{1}})=1-\mu_{1}$, and likewise for $h^{\mu_{2}}$.

Finally, it is worth noting that for calibrated classifiers, a lower false-positive rate necessarily corresponds to a lower false-negative rate and vice-versa. In other words, for a given base rate, a “better” calibrated classifier lies closer to the origin on the line of calibrated classifiers.

With this geometric intuition, we can provide a simplified proof of the main impossibility result from :

Let $h_{1}$ and $h_{2}$ be classifiers for groups $G_{1}$ and $G_{2}$ with $\mu_{1}\neq\mu_{2}$. $h_{1}$ and $h_{2}$ satisfy the Equalized Odds and calibration conditions if and only if $h_{1}$ and $h_{2}$ are perfect predictors.

Intuitively, the three conditions define a set of classifiers which is overconstrained. Equalized Odds stipulates that the classifiers $h_{1}$ and $h_{2}$ must lie on the same coordinate in the false-positive/false-negative plane. As $h_{1}$ must lie on the blue line of calibrated classifiers for $\mathcal{H}_{1}^{*}$ and $h_{2}$ on the red line $\mathcal{H}_{2}^{*}$ they can only satisfy EO at the unique intersection point — the origin (and location of the perfect classifier). This implies that unless the two classifiers achieve perfect accuracy, we must relax the Equalized Odds conditions if we want to maintain calibration.

Relaxing Equalized Odds to Preserve Calibration

In this section, we show that a substantially simplified notion of Equalized Odds is compatible with calibration. We introduce a general relaxation that seeks to satisfy a single equal-cost constraint while maintaining calibration for each group $G_{t}$. We begin with the observation that Equalized Odds sets constraints to equalize false-positives $c_{fp}(h_{t})$ and false-negatives $c_{fn}(h_{t})$. To capture and generalize this, we define a cost function $g_{t}$ to be a linear function in $c_{fp}(h_{t})$ and $c_{fn}(h_{t})$ with arbitrary dependence on the group’s base rate $\mu_{t}$. More formally, a cost function for group $G_{t}$ is

where $a_{t}$ and $b_{t}$ are non-negative constants that are specific to each group (and thus may depend on $\mu_{t}$): see 1(d). We also make the assumption that for any $\mu_{t}$, at least one of $a_{t}$ and $b_{t}$ is nonzero, meaning $g_{t}(h_{t})=0$ if and only if $c_{fp}(h_{t})=c_{fn}(h_{t})=0$. By calibration, we cannot have one of $c_{fp}(h_{t})=0$ or $c_{fn}(h_{t})=0$ without the other, see 1(a). This class of cost functions encompasses a variety of scenarios. As an example, imagine an application in which the equal false-positive condition is essential but not the false-negative condition. Such a scenario may arise in our recidivism-prediction example, if we require that non-repeat offenders of any race are not disproportionately labeled as high risk. If we plot the set of calibrated classifiers $\mathcal{H}^{*}_{1}$ and $\mathcal{H}^{*}_{2}$ on the false-positive/false-negative plane, we can see that ensuring the false-positive condition requires finding classifiers $h_{1}\in\mathcal{H}^{*}_{1}$ and $h_{2}\in\mathcal{H}^{*}_{2}$ that fall on the same vertical line (1(b)). Conversely, if we instead choose to satisfy only the false-negative condition, we would find classifiers $h_{1}$ and $h_{2}$ that fall on the same horizontal (1(c)). Finally, if both false-positive and false-negative errors incur a negative cost on the individual, we may choose to equalize a weighted combination of the error rates , which can be graphically described by the classifiers lying on a convex and negatively-sloped level set (1(d)). With these definitions, we can formally define our relaxation:

Given a cost function $g_{t}$ of the form in $\eqref{eqn:cost_general}$, classifiers $h_{1}$ and $h_{2}$ achieve Relaxed Equalized Odds with Calibration for groups $G_{1}$ and $G_{2}$ if both classifiers are calibrated and satisfy the constraint $g_{1}(h_{1})=g_{2}(h_{2})$.

It is worth noting that, for calibrated classifiers, an increase in cost strictly corresponds to an increase in both the false-negative and false-positive rate. This can be interpreted graphically, as the level-order cost curves lie further away from the origin as cost increases (2(a)). In other words, the cost function can always be used as a proxy for either error rate. This holds even for approximately calibrated classifiers — see Section S3.

It is easy to see that Definition 4 is always satisfiable – in Figures 1(b), 1(c), and 1(d) we see that there are many such solutions that would lie on a given level-order cost curve while maintaining calibration, including the case in which both classifiers are perfect. In practice, however, not all classifiers are achievable. For the rest of the paper, we will assume that we have access to “optimal” (but possibly discriminatory) calibrated classifiers $h_{1}$ and $h_{2}$ such that, due to whatever limitations there are on the predictability of the task, we are unable to find other classifiers that have lower cost with respect to $g_{t}$. We allow $h_{1}$ and $h_{2}$ to be learned in any way, as long as they are calibrated. Without loss of generality, for the remainder of the paper, we will assume that $g_{1}(h_{1})\geq g_{2}(h_{2})$.

Consider the range of values that $g_{t}$ can take. As noted above, $g_{t}(h_{t})\geq 0$, with equality if and only if $h_{t}$ is the perfect classifier. On the other hand, the trivial classifier (again, which outputs the constant $\mu_{t}$ for all inputs) is the calibrated classifier that achieves maximum cost for any $g_{t}$ (see Section S2 in Section S2). As a result, the cost of a classifier for group $G_{t}$ is between 0 and $g_{t}(h^{\mu_{t}})$. This naturally leads to a characterization of feasibility: Definition 4 can be achieved if and only if $h_{1}$ incurs less cost than group $G_{2}$’s trivial classifier $h^{\mu_{2}}$; i.e. if $g_{1}(h_{1})\leq g_{2}(h^{\mu_{2}})$. This can be seen graphically in Figure 2(c), in which the level-order curve for $g_{1}(h_{1})$ does not intersect the set of calibrated classifiers for $G_{2}$. Since, by assumption, we cannot find a calibrated classifier for $G_{1}$ with strictly smaller cost than $h_{1}$, there is no feasible solution. On the other hand, if $h_{1}$ incurs less cost than $h^{\mu_{2}}$, then we will show feasibility by construction with a simple algorithm.

An Algorithm.

While it may be possible to encode the constraints of Definition 4 into the training procedure of $h_{1}$ and $h_{2}$, it is not immediately obvious how to do so. Even naturally probabilistic algorithms, such as logistic regression, can become uncalibrated in the presence of optimization constraints (as is the case in ). It is not straightforward to encode the calibration constraint if the probabilities are assumed to be continuous, and post-processing calibration methods would break equal-cost constraints by modifying classifier scores. Therefore, we look to achieve the calibrated Equalized Odds relaxation by post-processing existing calibrated classifiers.

Implications.

We find two primary objections to this solution. First, it equalizes costs simply by making a classifier strictly worse for one of the groups. Second, it achieves this cost increase by withholding information on a randomly chosen population subset, making the outcome inequitable within the group (as measured by a standard measure of inequality like the Gini coefficient). Due to the optimality of the algorithm, the former of these issues is unavoidable in any solution that satisfies Definition 4. The latter, however, is slightly more subtle, and brings up the question of individual fairness (what guarantees we would like an algorithm to make with respect to each individual) and how it interacts with group fairness (population-level guarantees). While this certainly is an important issue for future work, in this particular setting, even if one could find another algorithm that distributes the burden of additional cost more equitably, any algorithm will make at least as many false-positive/false-negative errors as Algorithm 1, and these misclassifications will always be tragic to the individuals whom they affect. The performance loss across the entire group is often significant enough to make this combination of constraints somewhat worrying to use in practice, regardless of the algorithm.

Impossibility of Satisfying Multiple Equal-Cost Constraints.

It is natural to argue there might be multiple cost functions that we would like to equalize across groups. However, satisfying more than one distinct equal-cost constraint (i.e. different curves in the F.P./F.N. plane) is infeasible.

Let $h_{1}$ and $h_{2}$ be calibrated classifiers for $G_{1}$ and $G_{2}$ with equal cost with respect to $g_{t}$. If $\mu_{1}\neq\mu_{2}$, and if $h_{1}$ and $h_{2}$ also have equal cost with respect to a different cost function $g_{t}^{\prime}$, then $h_{1}$ and $h_{2}$ must be perfect classifiers.

(Proof in Section S5). Note that this is a generalization of the impossibility result of . Furthermore, we show in Theorem 4 (in Section S5) that this holds in an approximate sense: if calibration and multiple distinct equal-cost constraints are approximately achieved by some classifier, then that classifier must have approximately zero generalized false-positive and false-negative rates.

Experiments

Health Prediction.

Criminal Recidivism Prediction.

Finally, we examine the frameworks in the context of our motivating example: criminal recidivism. As mentioned in the introduction, African Americans ($G_{1}$) receive a disproportionate number of F.P. predictions as compared with Caucasians ($G_{2}$) when automated risk tools are used in practice. Therefore, we aim to equalize the generalized F.P. rate. In this experiment, we modify the predictions made by the COMPAS tool , a risk-assessment tool used in practice by the American legal system. Additionally, we also see if it is possible to improve the classifiers with training-time Equalized Odds constraints using the methods of Zafar et al. (EO-Trained). In 3(c), we first observe that the original classifiers $h_{1}$ and $h_{2}$ have large generalized F.P. and F.N. rates. Both methods of achieving Equalized Odds — training constraints (left plot) and post-processing (middle plot) match the error rates while sacrificing calibration. However, we observe that, assuming $h_{1}$ and $h_{2}$ cannot be improved, it is infeasible to achieve the calibrated relaxation (3(c) right). This is an example where matching the F.P. rate of $h_{1}$ would require a classifier worse than the trivial classifier $h^{\mu_{2}}$. This example therefore represents an instance in which calibration is completely incompatible with any error-rate constraints. If the primary concern of criminal justice practitioners is calibration , then there will inherently be discrimination in the form of F.P. and F.N. rates. However, if the Equalized Odds framework is adopted, the miscalibrated risk scores inherently cause discrimination to one group, as argued in the introduction. Therefore, the most meaningful change in such a setting would be an improvement to $h_{2}$ (the classifier for African Americans) either through the collection of more data or the use of more salient features. A reduction in overall error to the group with higher cost will naturally lead to less error-rate disparity.

Discussion and Conclusion

We have observed cases in which calibration and relaxed Equalized Odds are compatible and cases where they are not. When it is feasible, the penalty of equalizing cost is amplified if the base rates between groups differ significantly. This is expected, as base rate differences are what give rise to cost-disparity in the calibrated setting. Seeking equality with respect to a single error rate (e.g. false-negatives, as in the income prediction experiment) will necessarily increase disparity with respect to the other error. This may be tolerable (in the income prediction case, some employees will end up over-paid) but could also be highly problematic (e.g. in criminal justice settings). Finally, we have observed that the calibrated relaxation is infeasible when the best (discriminatory) classifiers are not far from the trivial classifiers (leaving little room for interpolation). In such settings, we see that calibration is completely incompatible with an equalized error constraint.

In summary, we conclude that maintaining cost parity and calibration is desirable yet often difficult in practice. Although we provide an algorithm to effectively find the unique feasible solution to both constraints, it is inherently based on randomly exchanging the predictions of the better classifier with the trivial base rate. Even if fairness is reached in expectation, for an individual case, it may be hard to accept that occasionally consequential decisions are made by randomly withholding predictive information, irrespective of a particular person’s feature representation. In this paper we argue that, as long as calibration is required, no lower-error solution can be achieved.

Acknowledgements

GP, FW, and KQW are supported in part by grants from the National Science Foundation (III-1149882, III-1525919, III-1550179, III-1618134, and III-1740822), the Office of Naval Research DOD (N00014-17-1-2175), and the Bill and Melinda Gates Foundation. MR is supported by an NSF Graduate Research Fellowship (DGE-1650441). JK is supported in part by a Simons Investigator Award, an ARO MURI grant, a Google Research Grant, and a Facebook Faculty Research Grant.

References

S1 Linearity of Calibrated Classifiers

In Section 3, we claim that the set of all calibrated classifiers $\mathcal{H}_{t}^{*}$ for group $G_{t}$ form a line in the generalized false-positive/false-negative plane. The following proof of this claim is adapted from .

For a group $G_{t}$, if a classifier $h_{t}$ has $\epsilon(h_{t})\leq\delta_{cal}$, then

where $c_{fp}(h_{t})$ and $c_{fn}(h_{t})$ are the generalized false-positive and false-negative and $\mu_{t}$ is the base rate of group $G_{t}$.

We follow a similar procedure for $c_{fn}(h_{t})$:

We can get a similar lower bound for $c_{fn}(h_{t})$ as

Multiplying these inequalities by $\mu_{t}$ completes this proof. ∎

Let $\mathcal{H}_{t}$ be the set of perfectly calibrated classifiers for group $G_{t}$ — i.e. for any $h^{*}_{t}\in\mathcal{H}_{T}$, we have $\epsilon(h^{*}_{t})=0$. The generalized false-positive and false-negative rates of $h^{*}_{t}$ are given by

This is a direct consequence of (S3) and (S4). ∎

For a group $G_{t}$, any perfectly calibrated classifier $h^{*}_{t}$ satisfies

In other words, all perfectly calibrated classifiers $h^{*}_{t}\in\mathcal{H}_{t}$ for group $G_{t}$ lie on a line in the generalized false-positive/false-negative plane, where the slope of the line is uniquely determined by the group’s base-rate $\mu_{t}$.

S2 Cost Functions

We will prove a few claims about cost functions $g_{t}$ of the form given by (2) — i.e.

for some non-negative constants $a_{t}$ and $b_{t}$. First, we show that $h^{\mu_{t}}$ is the calibrated classifier that maximizes $g_{t}$.

For any cost function $g_{t}$ that follows the form of (2), the trivial classifier $h^{\mu_{t}}$ is the calibrated classifier for $G_{t}$ with maximum cost.

Using (S5) and (S6), we have that, for every classifier $h_{t}$ that is perfectly calibrated for group $G_{t}$,

We would like to find, $h^{\max}_{t}\in\mathcal{H}^{*}_{t}$, the calibrated classifier with the highest weighted cost. Because $\left(\frac{a_{t}}{1-\mu_{t}}+\frac{b_{t}}{\mu_{t}}\right)$ and $\mu_{t}$ are non-negative constants, we have

Thus, the calibrated classifier with minimum variance will have the highest cost. This translates to a classifier that outputs the same probability for every sample. By the calibration constraint, this constant must be equal to $\mu_{t}$, so this classifier must be the trivial classifier $h^{\mu_{t}}$ — i.e. for all $\mathbf{x}$

Next, we show that $g_{t}$ is linear under randomized interpolations.

S3 Relationship Between Cost and Error

In Section 3, we claim that there is a tight connection between reducing any cost function $g_{t}(h_{t})$ and reducing the generalized error rates $c_{fp}(h_{t})$ and $c_{fn}(h_{t})$ for approximately calibrated classifiers. In other words, assuming we are approximately calibrated, improving cost will approximately improve our error rates. We formalize this notion in this section:

Let $h_{t}$ be a classifier with $\epsilon(h_{t})=\delta_{cal}$ and cost $g_{t}(h_{t})$. For any other classifier $h_{t}^{\prime}$, if $c_{fp}(h_{t}^{\prime})<c_{fp}(h_{t})-\frac{4\delta_{cal}}{1-\mu_{t}}$ or $c_{fn}(h_{t}^{\prime})<c_{fn}(h_{t})-\frac{4\delta_{cal}}{\mu_{t}}$, then $g_{t}(h_{t}^{\prime})<g_{t}(h_{t})$ or $\epsilon(h_{t})>\delta_{cal}$.

First, assume that $c_{fp}(h_{t}^{\prime})<c_{fp}(h_{t})-\frac{4\delta_{cal}}{1-\mu_{t}}$. Then, there are two cases: either $c_{fn}(h_{t}^{\prime})<c_{fn}(h_{t})$ or $c_{fn}(h_{t}^{\prime})\geq c_{fn}(h_{t})$. In the first case, $g_{t}(h_{t}^{\prime})<g_{t}(h_{t})$ because $c_{fp}(h_{t}^{\prime})<c_{fp}(h_{t})$ and $c_{fn}(h_{t}^{\prime})<c_{fn}(h_{t})$. In the second case, if $\epsilon(h_{t}^{\prime})\leq\delta_{cal}$, we can use Lemma S1 to get

Since this contradicts the initial assumption that $c_{fp}(h_{t}^{\prime})<c_{fp}(h_{t})-\frac{4\delta_{cal}}{1-\mu_{t}}$, it cannot be the case that $\epsilon(h_{t}^{\prime})\leq\delta_{cal}$. This proves the lemma when $c_{fp}(h_{t}^{\prime})<c_{fp}(h_{t})-\frac{4\delta_{cal}}{1-\mu_{t}}$.

To prove the second part, we now assume that $c_{fn}(h_{t}^{\prime})<c_{fn}(h_{t})-\frac{4\delta_{cal}}{\mu_{t}}$. We again break this into two cases. If $c_{fp}(h_{t}^{\prime})<c_{fp}(h_{t})$, then $g_{t}(h_{t}^{\prime})<g_{t}(h_{t})$. If $c_{fp}(h_{t}^{\prime})\geq c_{fp}(h_{t})$, then under the assumption that $\epsilon(h_{t}^{\prime})\leq\delta_{cal}$, we can rearrange Lemma S1 to get

Again, this contradicts the assumption that $c_{fn}(h_{t}^{\prime})<c_{fn}(h_{t})-\frac{4\delta_{cal}}{\mu_{t}}$, so it cannot be the case that $\epsilon(h_{t}^{\prime})\leq\delta_{cal}$. This completes the proof. ∎

From this result we can derive a stronger claim for perfectly calibrated classifiers.

Let $h_{t}$ and $h^{\prime}_{t}$ be perfectly calibrated classifiers with cost $g_{t}(h_{t})\leq g_{t}(h^{\prime}_{t})$ for some cost function $g_{t}$. Then $c_{fp}(h_{t})\leq c_{fp}(h^{\prime}_{t})$ and $c_{fn}(h_{t})\leq c_{fn}(h^{\prime}_{t})$, with equality only if $g_{t}(h_{t})=g_{t}(h^{\prime}_{t})$.

S4 Proof of Algorithm 1 Optimality and Approximate Optimality

In Section 4, we claim that Algorithm 1 produces optimal non-discriminatory classifiers in exact calibration scenarios, and near-optimal classifiers in approximate calibration scenarios.

We begin with classifiers $h_{1}$ and $h_{2}$ be classifiers for groups $G_{1}$ and $G_{2}$, with calibrations $\epsilon(h_{1})\leq\delta_{cal}$ and $\epsilon(h_{2})\leq\delta_{cal}$. As before, assume that we cannot strictly improve the cost of either $h_{1}$ or $h_{2}$ without worsening calibration: i.e. $h_{1}$ and $h_{2}$ is $g_{t}$ and calibration. We will now show that Algorithm 1 produces classifiers that are near-optimal with respect to both the false-positive and false-negative rates among calibrated classifiers satisfying the equal-cost constraint.

First, we show that interpolation preserves approximate calibration:

Thus, approximately calibrated classifiers will be approximately optimal. From this result, it is easy to derive the optimality result for perfectly-calibrated classifiers.

S5 Proof of Impossibility and Approximate Impossibility

In this section, we prove that it is impossible to satisfy multiple equal-cost constraints while simultaneously satisfying calibration. We will first prove this in an exact sense, and then show that the result holds approximately as well.

Let $h_{1}$ and $h_{2}$ be calibrated classifiers for $G_{1}$ and $G_{2}$ with equal cost with respect to $g_{t}$. If $\mu_{1}\neq\mu_{2}$, and if $h_{1}$ and $h_{2}$ have equal cost with respect to $g_{t}^{\prime}$, then $h_{1}$ and $h_{2}$ must be perfect classifiers.

First, observe that the perfect classifier always satisfies any equal-cost constraint simply because if $c_{fp}(t)=c_{fn}(t)=0$, $g_{t}(h_{t})=0$. Moreover, the perfect classifier is always calibrated.

For any classifier, as shown in , $c_{fp}(h_{t})$ and $c_{fn}(h_{t})$ are linearly related by (S7). Furthermore, each equal-cost constraint is linear in $c_{fp}(h_{t})$ and $c_{fn}(h_{t})$. We define $g_{t}(h_{t})$ and $g^{\prime}_{t}(h_{t})$ to be identical cost functions if the equal-cost constraints that they impose are identical, meaning one constraint is satisfied if and only if the other is satisfied. If this is not the case, then $g_{t}(h_{t})$ and $g^{\prime}_{t}(h_{t})$ are distinct, meaning that the equal-cost constraints are linearly independent for $\mu_{1}\neq\mu_{2}$. Moreover, these are also linearly independent from the calibration constraints because by assumption, they both have nonzero coefficients for at least one of $(c_{fp}(h_{1}),c_{fn}(h_{1}))$ and $(c_{fp}(h_{2}),c_{fn}(h_{2}))$. As a result, we have four linearly independent constraints (2 from calibration and at least 2 equal-cost constraints) on 4 variables ($c_{fp}(h_{1})$, $c_{fn}(h_{1})$, $c_{fp}(h_{2})$, $c_{fn}(h_{2})$), meaning that these constraints yield a unique solution. From above, we know that all the constraints are simultaneously satisfied when $c_{fp}(h_{t})=c_{fn}(h_{t})=0$ for $t=1,2$, meaning that the perfect classifier is the only classifier for which they are simultaneously satisfied. ∎

S5.2 Approximate Impossibility Theorem

Now, we will show that this impossibility result holds in an approximate sense — i.e. approximately satisfying the calibration and equal-cost constraints is only possible if the classifiers approximately perfect.

Since the calibration and equal-cost constraints are all linear, let $A$ be the matrix that encodes them. With two equal-cost constraints $g_{t}$ and $g_{t}^{\prime}$,

Note that the first two rows of $A$ encode the calibration conditions — see (S7). The bottom two rows encode two equal-cost constraints. Furthermore, let

If all constraints are required to hold exactly, then we have $A\vec{q}=0$. Consider the case where the calibration and equal-cost constraints hold approximately.

Let $h_{1}$ and $h_{2}$ be classifiers with calibration $\delta_{cal}$ and cost difference at most $\delta_{cost}$ with respect to distinct cost functions $g_{t}$ and $g_{t}^{\prime}$. Furthermore, assume that every entry of $A$ is rational with some common denominator $D$ and is upper bounded by some maximum value $M$. Then, there is a constant $L$ that depends on $D$ and $M$ such that

Since the first two rows in $A$ correspond to the calibration constraints, and the second to correspond to the equal-cost constraints, it must be the case that

i.e. the absolute value of each entry in $A\vec{q}$ is bounded by the vector on the right hand side. Let $\vec{\nu}=[2\delta_{cal}/(1-\mu_{1})\;2\delta_{cal}/(1-\mu_{2})\;\delta_{cost}\;\delta_{cost}]^{\top}$. Let $\vec{s}=sign(A\vec{q})$, and multiply the $i$th row of $A$ by the $i$th entry of $\vec{s}$ to produce $\widehat{A}$ This allows us to drop the absolute value, meaning we have

Furthermore, since $g_{t}$ and $g_{t}^{\prime}$ were assumed to be distinct, $\widehat{A}$ is invertible, so this is equivalent to

The $(i,j)$ entry of $\widehat{A}^{-1}$ can be expresed as $\widehat{A}_{ji}/\det(\widehat{A})$, where $\widehat{A}_{ji}$ is the $(j,i)$ cofactor. Note that $\widehat{A}_{ji}$ is a $3\times 3$ determinant, so it is the sum of $6$ cubic polynomials in entries of $\widehat{A}$. However, since every $3\times 3$ submatrix of $\widehat{A}$ has at least one entry, only $4$ of those cubics can be nonnegative. By assumption, the maximum value of any entry of $\widehat{A}$ is $M$, so $|\widehat{A}_{ji}|\leq 4M^{3}$.

We can lower bound $\det(\widehat{A})$ by noting that since $\widehat{A}$ is not singular, its determinant is nonzero. However, because the determinant can be expressed as a $4\times 4$ polynomial, and each term has common denominator $D$ by assumption, $|\det(\widehat{A})|\geq 1/D^{4}$. As a result, $|\widehat{A}_{ji}/\det(\widehat{A})|\leq 4M^{3}D^{4}$.

Let $d_{ij}$ be the $(i,j)$ entry of $\widehat{A}$. We know that

Note that Theorem 4 is not intended to be a tight bound. It simply shows that impossibility result degrades smoothly for approximate constraints.

S6 Details on Experiments

To derive classifiers that satisfy the Equalized Odds notion of fairness, we use the method introduced by Hardt et al. . Essentially, the false-positive and false-negative constraints are satisfied by randomly flipping some of the predictions of the original classifiers. Let $q^{(t)}_{\text{n2p}}$ be the probability for group $G_{t}$ of “flipping” a negative prediction to positive, and $q^{(t)}_{\text{p2n}}$ be that of flipping a positive prediction to negative. The derived classifiers ${h}^{eo}_{1}$ and ${h}^{eo}_{2}$ essentially flip predictions according to these probabilities:

where $B^{(t)}_{\text{n2p}}$ and $B^{(t)}_{\text{p2n}}$ are Bernoulli random variables with expectations $q^{(t)}_{\text{n2p}}$ and $q^{(t)}_{\text{p2n}}$ respectively. Note that this is a probabilistic generalization of the derived classifiers presented in . If all outputs of $h_{t}$ were either or $1$ we would arrive at the original formulation.

We can find the best rates $q^{(1)}_{\text{n2p}}$, $q^{(1)}_{\text{p2n}}$, $q^{(2)}_{\text{n2p}}$, and $q^{(2)}_{\text{p2n}}$ through the following optimization problem:

where $\mathcal{L}$ represents the /$1$ loss of the classifier:

The two constraints enforce the Equalized Odds constraints. Hardt et al. show that this can be solved via a linear program.

Constrained-learning for Equalized Odds

Zafar et al. introduce a method to achieve Equalized Odds (under the name Disparate Mistreatment) at training time using optimization constraints. The problem is set up at learning a logistic classifier under the Equalized Odds constraints. While these constraints make the problem non-convex, Zafar et al. show how to formulate the problem as a disciplined convex-concave program. Though this is generally intractable, it can be solved in many instances. We refer the reader to for details.

Training Procedure for Income Prediction.

We train three models: a random forest, a multi-layer perceptron, and a SVM with an RBF kernel. We convert the categorical features into one-hot enocodings. $10\%$ of the data is reserved for hyperparameter tuning and post-processing, and an additional $10\%$ is saved for final evaluation. The random forest and MLP are naturally probabilistic and well calibrated. We use Platt scaling to calibrate the SVM. The hyperparameters were tuned by grid search based on 3-fold cross validation. 3(a) displays the average false-positive and false-negative costs across all models.

Training Procedure for Health Prediction.

We train a random forest and a linear SVM on this dataset. We use the same dataset split and hyperparameter selection as with Income Prediction. 3(b) displays the average false-positive and false-negative costs across all models.

Training Procedure for Health Prediction.

For the trained Equalized Odds baseline we train a constrained logistic classifier using the method proposed by . We derive the post-processed classifiers (both for Equalized Odds and its calibrated relaxation) from the original COMPAS classifier .