Probably Approximately Metric-Fair Learning

Introduction

Machine learning is increasingly used to make consequential classification decisions about individuals. Examples range from predicting whether a user will enjoy a particular article, to estimating a felon’s recidivism risk, to determining whether a patient is a good candidate for a medical treatment. Automated classification comes with great benefits, but it also raises substantial societal concerns (cf. [O’N16] for a recent perspective). One prominent concern is that these algorithms might discriminate against individuals or groups in a way that violates laws or social and ethical norms. This might happen due to biases in the training data or due to biases introduced by the algorithm. To address these concerns, and to truly unleash the full potential of automated classification, there is a growing need for frameworks and tools to mitigate the risks of algorithmic discrimination. A growing literature attempts to tackle these challenges by exploring different fairness criteria.

Discrimination can take many guises. It can be difficult to spot and difficult to define. Imagine a protected minority population $P$ (defined by race, gender identity, political affiliation, etc). A natural approach for protecting the members of $P$ from discrimination is to make sure that they are not mistreated on average. For example, that on average members of $P$ and individuals outside of $P$ are classified in any particular way with roughly the same probability. This is a “group-level” notion of fairness, sometimes referred to as statistical parity.

Pointing out several weakness of group-level notions of fairness, the seminal work of [DHP+12] introduced a notion of individual fairness. Their notion relies on a task-specific similarity metric that specifies, for every two individuals, how similar they are with respect to the specific classification task at hand. Given such a metric, similar individuals should be treated similarly, i.e. assigned similar classification distributions (their focus was on probabilistic classifiers, as will be ours). In this work, we refer to their fairness notion as perfect metric-fairness.

Given a good metric, perfect metric-fairness provides powerful protections from discrimination. Furthermore, the metric provides a vehicle for specifying social norms, cultural awareness, and task-specific knowledge. While coming up with a good metric can be challenging, metrics arise naturally in prominent existing examples (such as credit scores and insurance risk scores), and in natural scenarios (a metric specified by an external regulator). Dwork et al. studied the goal of finding a (probabilistic) classifier that minimizes utility loss (or maximizes accuracy), subject to satisfying the perfect metric-fairness constraint. They showed how to phrase and solve this optimization problem for a given collection of individuals.

Building on these foundations, we study metric-fair machine learning. Consider a learner that is given a similarity metric and a training set of labeled examples, drawn from an underlying population distribution. The learner should output a fair classifier that (to the extent possible) accurately classifies the underlying population.

This goal departs from the scenario studied in [DHP+12], where the focus was on guaranteeing metric-fairness and utility for the dataset at hand. Generalization of the fairness guarantee is a key difference: we focus on guaranteeing fairness not just for the (training) data set at hand, but also for the underlying population from which it was drawn. We note that perfect metric-fairness does not, as a rule, generalize from a training set to the underlying population. This presents computational difficulties for constructing learning algorithms that are perfectly metric-fair for the underlying population. Indeed, we exhibit a simple learning task that, while easy to learn without fairness constraints, becomes computationally infeasible under the perfect metric-fairness constraint (given a particular metric).We remark that perfect metric-fairness can always be obtained trivially by outputting a constant classifier that treats all individuals identically, the challenge is achieving metric-fairness together with non-trivial accuracy. See below and in Section 1.6 for further details.

We develop a relaxed approximate metric-fairness framework for machine learning, where fairness does generalize from the training set to the underlying population, and present polynomial-time fair learning algorithms in this framework. We proceed to describe our setting and contributions.

A metric-fair learning problem is defined by a domain ${\cal X}$ and a similarity metric $d$. A metric-fair learning algorithm gets as input the metric $d$ and a sample of labeled examples, drawn i.i.d. from a distribution ${\cal D}$ over labeled examples from $({\cal X}\times\pm 1)$, and outputs a classifier $h$. To accommodate fairness, we focus on probabilistic classifiers $h:{\cal X}\rightarrow$, where we interpret $h(x)$ as the probability of label 1 (the probability of $-1$ is thus $(1-h(x))$). We refer to these probabilistic classifiers as predictors.

Taking inspiration from Valiant’s celebrated PAC learning model [Val84], we allow a small fairness error, which opens the door to generalization. We require that for two individuals sampled from the underlying population, with all but a small probability, if they are similar then they should be treated similarly. Similarity is measured by the statistical distance between the classification distributions given to the two individuals (we also allow a small additive slack in the similarity measure). We refer to this condition as approximate metric-fairness (MF). Similarly to PAC learning, we also allow a small probability of a complete fairness failure.

Given a well-designed metric, approximate metric-fairness guarantees that almost every individual gets fair treatment compared to almost every other individual. In particular, it provides discrimination-protections to every group $P$ that is not too small. However, this guarantee also has limitations: particular individuals and even small groups might encounter bias and discrimination. There are certainly settings in which this is problematic, but in other settings protecting all groups that are not too small is an appealing guarantee. The relaxation is well-motivated because approximate fairness opens the door to fairness-generalization bounds, as well as efficient learning algorithms for a rich collection of problems (see below). We elaborate on these choices and their consequences in Section 1.2.

Turning our attention to the accuracy objective, we follow [DHP+12] in considering fairness to be a hard constraint (e.g. imposed by a regulator). Given the fairness constraint, what is a reasonable accuracy objective? Ideally, we would like the predictor’s accuracy to approach (as the sample size grows) that of the most accurate approximately MF predictor. This is analogous to the accuracy guarantee pioneered in [DHP+12]. A probably approximately correct and fair (PACF) learning algorithm guarantees both approximate MF and “best-possible” accuracy. A more relaxed accuracy benchmark is approaching the accuracy of the best classifier that is approximately MF for a tighter (more restrictive) fairness-error. We refer this as a relaxed PACF learning algorithm (looking ahead, our efficient algorithms achieve this relaxed accuracy guarantee). We note that even relaxed PACF guarantees that the classifier is (at the very least) competitive with the best perfectly metric-fair classifier. We elaborate in Section 1.3.

A key issue in learning theory is that of generalization: to what extent is a classifier that is accurate on a finite sample $S\sim{\cal D}^{m}$ also guaranteed to be accurate w.r.t the underlying distribution? We develop strong generalization bounds for approximate metric-fairness, showing that for any class of predictors with bounded Rademacher complexity, approximate MF on the sample $S$ implies approximate MF on the underlying distribution (w.h.p. over the choice of sample $S$). The use of Rademacher complexity guarantees fairness-generalization for finite classes and also for many infinite classes. Proving that approximate metric-fairness generalizes well is a crucial component in our analysis: it opens the door to polynomial-time algorithms that can focus on guaranteeing fairness (and accuracy) on the sample. Generalization also implies information-theoretic sample-complexity bounds for PACF learning that are similar to those known for PAC learning (without any fairness constraints). We elaborate in Section 1.4.

We construct polynomial-time (relaxed) PACF algorithms for linear and logistic regression. Recall that (for fairness) we focus on regression problems: learning predictors that assign a probability in $$to each example. For linear predictors, the probability is a linear function of an example’s distance from a hyperplane. Logistic predictors compose a linear function with a sigmoidal transfer function. This allows logistic predictors to exhibit sharper transitions from low predictions to high predictions. In particular, a logistic predictor can better approximate a classifier that labels examples that are below a hyperplane by$-1$, and examples that are above the hyperplane by 1. Linear and logistic predictors can be more powerful than they first seem: by embedding a learning problem into a higher-dimensional space, linear functions (over the expanded space) can capture the power of many of the function classes that are known to be PAC learnable [HS07]. We overview these results in Section 1.5. We note that a key challenge in efficient metric-fair learning is that the fairness constraints are neither Lipschitz nor convex (even when the predictor is linear). This is also a challenge for proving generalization and sample complexity bounds. Berk et al. [BHJ+17] also study fair regression and formulate a measure of individual fairness loss, albeit in a different setting without a metric (see Section 1.7).

Under mild cryptographic assumptions, we exhibit a learning problem and a similarity metric where: $(i)$ there exists a perfectly fair and perfectly accurate simple (linear) predictor, but $(ii)$ any polynomial-time perfectly metric-fair learner can only find a trivial predictor, whose error approaches 1/2. In contrast, $(iii)$ there does exist a polynomial-time (relaxed) PACF learning algorithm for this task. This is an important motivation for our study of approximate metric-fairness. We elaborate in Section 1.6.

In the remainder of this section we provide an overview of our contributions. Section 1.2 details and discusses the definition of approximate metric-fairness and its relationship to related works. Accurate and fair (PACF) learning is discussed in Section 1.3. We state and prove fairness-generalization bounds in Section 1.4. Our polynomial-time PACF learning algorithms for linear and logistic regression are in Section 1.5. Section 1.6 elaborates on the hardness of perfectly metric-fair learning. Further related work is discussed in Section 1.7.

Full and formal details are in Sections 2 through 6. Conclusions and a discussion of future directions are in Section 7.

2 Approximate Metric-Fairness

We require that metric-fairness holds for all but a small $\alpha$ fraction of pairs of individuals. That is, with all but $\alpha$ probability over a choice of two individuals from the underlying distribution, if the two individuals are similar then they get similar classification distributions. We think of $\alpha\in[0,1)$ as a small constant, and note that setting $\alpha=0$ recovers the definition of perfect metric-fairness (thus, setting $\alpha$ to be a small constant larger than 0 is indeed a relaxation). Similarity is measured by the statistical distance between the classification distributions given to the two individuals, where we also allow a small additive slack $\gamma$ in the similarity measure. The larger $\gamma$ is, the more “differently” similar individuals might be treated. We think of $\gamma$ as a small constant, close to 0.

A predictor $h$ is $(\alpha,\gamma$) approximately metric-fair (MF) with respect to a similarity metric $d$ and a data distribution ${\cal D}$ if:

Similarly to the PAC learning model, we also allow a small $\delta$ probability of failure. This probability is taken over the choice of the training set and over the learner’s coins. For example, $\delta$ bounds the probability that the randomly sampled training set is not representative of the underlying population. We think of $\delta$ as very small or even negligible. A learning algorithm is probably approximately metric-fair if with all but $\delta$ probability over the sample (and the learner’s coins), it outputs a classifier that is $(\alpha,\gamma)$-approximately MF. Further details are in Section 2.

Given a well-designed metric, approximate metric-fairness (for sufficiently small $\alpha,\gamma$) guarantees that almost every individual gets fair treatment compared to almost every other individual (see Section 2.3 for a quantitative discussion). Every protected group $P$ of fractional size significantly larger than $\alpha$ is protected in the sense that, on average, members of $P$ are treated similarly to similar individuals outside of $P$. We note, however, that this guarantee does not protect single individuals or small groups (see the discussion in Section 1.1).

Recent works [HJKRR17, KNRW17] study fairness notions that aim to protect large collections of sufficiently-large groups. Similarly to our work, these can be viewed as falling between individual and group notions of fairness. A distinction from these works is that approximate metric-fairness protects every sufficiently-large group, rather than a large collection of groups that is fixed a priori. Recent works [GJKR18, KRR18] extend the study of metric fairness to settings where the metric is not known (whereas we focus on a setting where the metric is fixed and known in its entirety), and consider relaxed fairness notions that allow individual fairness to be violated.

3 Accurate and Fair Learning

Our goal is to obtain learning algorithms that are probably approximately metric-fair, and that simultaneously guarantee non-trivial accuracy. Recall that fairness, on its own, can always be obtained by outputting a constant predictor that ignores its input and treats all individuals identically (indeed, such a classifier is perfectly metric-fair). It is the combination of the fairness and the accuracy objectives that makes for an interesting task. As discussed above, we follow [DHP+12] in focusing on finding a predictor that maximizes accuracy, subject to the approximate metric-fairness constraint. This is a natural formulation, as we think of fairness as a hard requirement (imposed, for example, by a regulator), and thus fairness cannot be traded off for better accuracy.

As discussed above, the goal in metric-fair and accurate learning is optimizing the predictor’s accuracy subject to the fairness constraint. Ideally, we aim to approach (as the sample size grows) the error rate of the most accurate classifier that satisfies the fairness constraints. A more relaxed benchmark is guaranteeing $(\alpha,\gamma)$-approximate metric-fairness, while approaching the accuracy of the best classifier that is $(\alpha^{\prime},\gamma^{\prime})$-approximately metric-fair, for $\alpha^{\prime}\in[0,\alpha]$ and $\gamma^{\prime}\in[0,\gamma]$. Our efficient learning algorithms will achieve this more relaxed accuracy goal (see below). We note that even relaxed competitiveness means that the classifier is (at the very least) competitive with the best perfectly metric-fair classifier.

These goals are captured in the following definition of probably approximately correct and fair (PACF) learning. Crucially, both fairness and accuracy goals are stated with respect to the (unknown) underlying distribution.

A learning algorithm ${\cal A}$ PACF-learns a hypothesis class $\mathcal{H}$ if for every metric $d$ and population distribution ${\cal D}$, every required fairness parameters $\alpha,\gamma\in[0,1)$, every failure probability $\delta\in(0,1)$, and every error parameters $\epsilon,\epsilon_{\alpha},\epsilon_{\gamma}\in(0,1)$ the following holds:

There exists a sample complexity $m={\rm poly}\left({\frac{\log|{\cal X}|\cdot\log(1/\delta)}{\alpha\cdot\gamma\cdot\epsilon_{\cdot}\epsilon_{\alpha}\cdot\epsilon_{\gamma}}}\right)$ and constants $\alpha^{\prime},\gamma^{\prime}\in[0,1)$ (specified below), such that with all but $\delta$ probability over an i.i.d. sample of size $m$ and ${\cal A}$’s coin tosses, the output predictor $h$ satisfies the following two conditions:

Fairness: $h$ is $(\alpha,\gamma)$-approximately metric-fair w.r.t. the metric $d$ and the distribution ${\cal D}$.

Accuracy: Let $\mathcal{H}_{F}^{\prime}$ denote the subclass of hypotheses in $\mathcal{H}$ that are $(\alpha^{\prime}-\epsilon_{\alpha},\gamma^{\prime}-\epsilon_{\gamma})$-approximately metric-fair, then:

We say that ${\cal A}$ is efficient if it runs in time ${\rm poly}(m)$. If accuracy holds for $\alpha^{\prime}=\alpha$ and $\gamma^{\prime}=\gamma$, then we stay that ${\cal A}$ is a strong PACF learning algorithm. Otherwise, we say that ${\cal A}$ is a relaxed PACF learning algorithm.

See Section 3 and Definitions 3.2 and 3.3 for a full treatment. Note that the accuracy guarantee is agnostic: we make no assumptions about the way the training labels are generated. Agnostic learning is particularly well suited to our metric-fairness setting: since we make no assumptions about the metric $d$, even if the labels are generated by $h\in{\cal H}$, it might be the case that $d$ does not allow for accurate predictions, in which case a fair learner cannot compete with $h$’s accuracy.

4 Generalization

Generalization is a key issue in learning theory. We develop strong generalization bounds for approximate metric-fairness, showing that with high probability, guaranteeing empirical approximate MF on a training set also guarantees approximate MF on the underlying distribution (w.h.p. over the choice of sample $S$). This generalization bound opens the door to polynomial-time algorithms that can focus on guaranteeing fairness (and accuracy) on the sample and effectively rules out the possibility of creating a “false facade” of fairness (i.e, a classifier that appears fair on a random sample, but is not fair w.r.t new individuals).

Towards proving generalization, we define the empirical fairness loss on a sample $S$ (a training set). Fixing a fairness parameter $\gamma$, a predictor $h$ and a pair of individuals $x,x^{\prime}$ in the training set, consider the MF loss on the “edge” between $x$ and $x^{\prime}$ (recall that the MF loss is 1 if the “internal” inequality of Equation (1) holds, and 0 otherwise). Observe that the losses on the $\binom{|S|}{2}$ edges are not independent random variables (over the choice of $S$), because each individual $x\in S$ affects many edges. Thus, rather than count the empirical MF loss over all edges, we restrict ourselves to a “matching” $M(S)$ in the complete graph whose vertices are $S$: a collection of edges, where each individual is involved in exactly one edge. The empirical MF loss of $h$ on $S$ is defined as the average MF loss over edges in $M(S)$.The choice of which matching is used does not affect any of the results. Note that we could also choose to average over all the edges in the graph induced by $S$. Generalization bounds still follow, but the rate of convergence is not faster than restricting our attention to a matching. Note that, since we restricted our attention to a matching, the MF losses on these edges are now independent random variables (over the choice of $S$). A classifier is empirically $(\alpha,\gamma)$-approximately MF if its empirical MF loss is at most $\alpha$. We are now ready to state our generalization bound:

Let $\mathcal{H}$ be a hypothesis class with Rademacher complexity $R_{m}(\mathcal{H})=(r/\sqrt{m})$. For every $\delta\in(0,1)$ and every $\epsilon_{\alpha},\epsilon_{\gamma}\in(0,1)$, there exists a sample complexity $m=O\left(\frac{r^{2}\cdot\ln(1/\delta)}{\epsilon^{2}_{\alpha}\cdot\epsilon^{2}_{\gamma}}\right)$, such that the following holds:

With probability at least $1-\delta$ over an i.i.d sample $S\sim{\cal D}^{m}$, simultaneously for every $h\in\mathcal{H}$: if $h$ is $(\alpha,\gamma)$-approximately metric-fair on the sample $S$, then $h$ is also $(\alpha+\epsilon_{\alpha},\gamma+\epsilon_{\gamma})$-approximately metric-fair on the underlying distribution ${\cal D}$.

See Section 2.5 and Theorem 2.12 for a full statement and discussion (and see Definition 2.11 for a definition of Rademacher complexity). Rademacher complexity differs from the celebrated VC-dimension in several respects: first, it is defined for any class of real-valued functions (making it suitable for our setting of learning probabilistic classifiers); second, it is data-dependent and can be measured from finite samples (indeed, Theorem 1.3 can be stated w.r.t. the empirical Rademacher complexity on a given sample); third, it often results in tighter uniform convergence bounds (see, e.g, [KP02]). We note that for every finite hypothesis class $\mathcal{H}$ whose range is $$, the Rademacher complexity is bounded by$O(\sqrt{\log|\mathcal{H}|/m})$.

4.1 Information-Theoretic Sample Complexity

The fairness-generalization result of Theorem 1.3 implies that, from a sample-complexity perspective, any hypothesis class is strongly PACF learnable, with sample complexity comparable to that of standard PAC learning. An exponential-time PACF learning algorithm simply finds the predictor in ${\cal H}$ that minimizes the empirical error, while also satisfying empirical approximate metric-fairness.

Let $\mathcal{H}$ be a hypothesis class with Rademacher complexity $R_{m}(\mathcal{H})=(r/\sqrt{m})$. Then $\mathcal{H}$ is information-theoretically strongly PACF learnable with sample complexity $m=O\left(\frac{r^{2}\ln(1/\delta)}{\left(\epsilon^{\prime}\right)^{2}}\right)$, for $\epsilon^{\prime}=\min\left\{\epsilon,\epsilon_{\alpha},\epsilon_{\gamma}\right\}$ .

5 Efficient Fair Learning

One of our primary contributions is the construction of polynomial-time relaxed-PACF learning algorithms for expressive hypothesis classes. We focus on linear classification tasks, where the labels are determined by a separating hyperplane. Learning linear classifiers, also referred to as halfspaces or linear threshold functions, is a central tool in machine learning. By embedding a learning problem into a higher-dimensional space, linear classifiers (over the expanded space) can capture surprisingly strong classes, such as polynomial threshold functions (see, for example, the discussion in [HS07]). The “kernel trick” (see, e.g, [SSBD14]) can allow for efficient solutions even over very high (or infinite) dimensional embeddings. Many of the known (distribution-free) PAC learning algorithms can be derived by learning linear threshold functions [HS07].

Recall that in metric-fair learning, we aim to learn a probabilistic classifier, or a predictor, that outputs a real value in $$. We interpret the output as the probability of assigning the label$1$. We are thus in the setting of regression. We show polynomial-time relaxed-PACF learning algorithms for linear regression and for logistic regression. See Section 5 for full and formal details.

Linear regression, the task of learning linear predictors, is an important and well-studied problem in the machine learning literature. In terms of accuracy, this is an appealing class when we expect a linear relationship between the probability of the label being $1$ and the distance from a hyperplane. Taking the domain ${\cal X}$ to be the unit ball, we define the class of linear predictors as:

We restrict $w$ to the unit ball to guarantee that $\left\langle\mathbf{w},\mathbf{x}\right\rangle\in$. We then invoke a linear transformation so that the final prediction is in $$, as required. Restricting the predictor’s output to the range$$ is important. In particular, it means that a linear predictor must be $(1/2)$-Lipschitz, which might not be appropriate for certain classification tasks (see the discussion of logistic regression below).

We show a relaxed PACF learning algorithm for $H_{\mathit{lin}}$:

$H_{\mathit{lin}}$ is relaxed PACF learnable with sample and time complexities of $poly(\frac{1}{\epsilon_{\gamma}},\frac{1}{\epsilon_{\alpha}},\frac{1}{\epsilon},\log\frac{1}{\delta})$. For every $\gamma^{\prime}\in[0,1)$ and $\alpha^{\prime}=(\alpha\cdot\gamma-\gamma^{\prime})$, the accuracy of the learned predictor approaches (or beats) the most accurate $(\alpha^{\prime},\gamma^{\prime})$-approximately MF predictor.

Since the Rademacher complexity of (bounded) linear functions is small [KST09], Theorem 1.3 implies that empirical approximate metric-fairness on the training set generalizes to the underlying population. Thus, given the metric and a training set, our task is to find a linear predictor that is as accurate as possible, conditioned on the empirical fairness constraint. We use $H=H_{\mathit{lin}}$ to denote the class of linear predictors defined above. Fixing desired fairness parameters $\alpha,\gamma\in(0,1)$, let $\widehat{H}^{\alpha,\gamma}\subseteq H$ be the subset of linear functions that are also $(\alpha,\gamma)$-approximately MF on the training set. Given a training set $S$ of $m$ labeled examples, we would like to solve the following optimization problem:

Thus, by picking $\tau=\alpha\cdot\gamma$ we guarantee (empirical) $(\alpha,\gamma)$-approximate metric-fairness. Moreover, for any choice of $\sigma$, the set over which we optimize contains all of the predictors that are $((\alpha\gamma-\sigma),\sigma)$-approximately MF. Thus, our (empirical) accuracy is competitive with all such predictors, and we obtain a relaxed PACF algorithm. The empirical fairness and accuracy guarantees generalize beyond the training set by Theorem 1.3 (fairness-generalization) and a standard uniform convergence argument for accuracy.

5.2 Logistic Regression

The sigmoidal transfer function gives the predictor the power to exhibit sharper transitions from low predictions to high predictions around a certain distance (or decision) threshold. For example, suppose a distance from the hyperplane provides a quality score for candidates with respect to a certain task. Suppose also that an employer wants to hire candidates whose quality scores are above some threshold $\eta\in[-1,+1]$. The class $H_{\phi,L}$ can give probabilities close to 0 to candidates whose quality scores are under $\eta-1/L$, and probabilities close to 1 to candidates whose quality scores are over $\eta+1/L$. Linear predictors, on the other hand, need to be $(1/2)$-Lipschitz (since we restrict their output to be in $$, see Section 1.5.1).This might, at first glance, seem like a technicality. After all, why not simply consider linear predictors whose output can be in a larger range? The problem is that it isn’t clear how to plug these larger values into the fairness constraints in a way that keeps the optimization problem convex and also has competitive accuracy. Logistic predictors seem considerably better-suited to this type of scenario. Indeed, the class$H_{\phi,L}$can achieve good accuracy on linearly separable data whose margin (i.e. the expected distance from the hyperplane) is larger than$1/L$. Moreover, similarly to linear threshold functions, logistic regression can be applied after embedding the learning problem into a higher-dimensional space. For example, in the “quality score” example above, the score could be computed by a low-degree polynomial.

Our primary technical contribution is a polynomial-time relaxed PACF learner for $H_{\phi,L}$ where $L$ is constant.

For every constant $L>0$, $H_{\phi,L}$ is relaxed PACF learnable with sample and time complexities of $poly(\frac{1}{\epsilon_{\gamma}},\frac{1}{\epsilon_{\alpha}},\frac{1}{\epsilon},\log\frac{1}{\delta})$. For every $\gamma^{\prime}\in[0,1)$ and $\alpha^{\prime}=(\alpha\cdot\gamma-\gamma^{\prime})$, the accuracy of the learned predictor approaches (or beats) the most accurate $(\alpha^{\prime},\gamma^{\prime})$-approximately MF predictor.

More generally, our algorithm is exponential in the parameter $L$. Recall that we expect to have good accuracy on linearly separable data whose margins are larger than $(1/L$). Thus, one can interpret the algorithm as having runtime that is exponential in the reciprocal of the (expected) margin.

We note that fair learning of logistic predictors is considerably more challenging than the linear case, because the sigmoidal transfer function specifies non-convex fairness constraints. In standard logistic regression, where fairness is not a concern, polynomial-time learning is achieved by replacing the standard loss with a convex logistic loss. In metric-fair learning, however, it not clear how to replace the sigmoidal transfer function by a convex surrogate.

To overcome these barriers, we use improper learning. We embed the linear problem at hand into a higher-dimensional space, where logistic predictors and their fairness constraints can be approximated by convex expressions. To do so, we use a beautiful result of Shalev-Schwartz et al. [SSSS11] that presents a particular infinite-dimensional kernel space where our fairness constraints can be made convex.

In particular, we replace the problem of PACF learning $H_{\phi,L}$ with the problem of PACF learning $H_{B}$, a class of linear predictors with norm bounded by B in a RHKS defined by Vovk’s infinite-dimension polynomial kernel, $k(x,x^{\prime})=\left(1-\left\langle x,x^{\prime}\right\rangle\right)^{-1}$. We learn the linear predictor in this RHKS using the result of Theorem 1.5 to obtain a relaxed PACF algorithm for $H_{B}$. We use the kernel trick to argue that the sample complexity is $m=O(B/(\epsilon^{\prime})^{2})$, where $\epsilon^{\prime}=\min(\epsilon,\epsilon_{\alpha},\epsilon_{\gamma})$, and the time complexity is $poly(m)$.

For every $B\geq 0$, we can thus learn a linear predictor (in the above RHKS) that is (empirically) sufficiently fair, and whose (empirical) accuracy is competitive with all the linear predictors with norm bounded by $B$ that are $\left(\left(\alpha\gamma-\sigma\right),\sigma\right)$-approximately MF, for any choice of $\sigma$. To prove PACF learnability of $H_{\phi,L}$, we build on the polynomial approximation result of Shalev-Schwartz et al. [SSSS11] to show that taking $B$ to be sufficiently large ensures that the accuracy of the set of $\left(\alpha,\gamma\right)$-AMF predictors in $H_{\phi,L}$ is comparable to the accuracy of the set of $\left(\alpha,\gamma\right)$-AMF predictors in $H_{B}$. This requires a choice of $B$ that is $\exp(O(L\cdot\ln(L/\epsilon^{\prime}))$, which is where the exponential dependence on $L$ comes in.

6 Hardness of Perfect Metric-Fairness

As discussed above, perfect metric-fairness does not generalize from a training set to the underlying population. For example, consider a very small subset of the population that isn’t represented in the training set. A classifier that discriminates against this small subset might be perfectly metric-fair on the training set. The failure of generalization poses serious challenges to constructing learning algorithms. Indeed, we show that perfect metric-fairness can make simple learning tasks computationally intractable (with respect to a particular metric).

We present a natural learning problem and a metric where, even though a perfectly fair and perfectly accurate simple (linear) classifier exists, it cannot be found by any polynomial-time learning algorithm that is perfectly metric-fair. Indeed, any such algorithm can only find trivial classifiers with error rate approaching 1/2 (not much better than random guessing). The learner can tell that a particular (linear) classifier is empirically perfectly fair (and perfectly accurate). However, even though the classifier is perfectly fair on the underlying distribution, the (polynomial-time) learner cannot certify that this is the case, and thus it has to settle for outputting a trivial classifier. We note that there does exist an exponential-time perfectly metric-fair learning algorithm with a competitive accuracy guarantee,For example, an exponential-time algorithm could learn by enumerating all possible classifiers, discarding all the ones that are not perfectly metric-fair (using a brute-force search over all pairs of individuals for each candidate classifier), and then output the most-accurate classifier among the perfectly metric-fair ones. It is important to note that this algorithm doesn’t try to guarantee empirical perfect metric-fairness, which we know does not generalize. Rather, the learner has to consider the fairness behavior over all pairs of individuals. the issue is the computational complexity of this task. In contrast, the relaxed notion of approximate metric-fairness does allow for polynomial-time relaxed-PACF learning algorithms that obtain competitive accuracy for this task (as it does for a rich class of learning problems, see Section 1.5).

We present an overview of the hard learning task and discuss its consequences below. See Section 6 and Theorem 6.1 for a more formal description. Since we want to argue about computational intractability, we need to make computational assumptions (in particular, if $P=NP$, then perfectly metric-fair learning would be tractable). We will make the minimal cryptographic hardness assumption that one-way functions exist, see [Gol01] for further background.

For this sketch, we take a uniform distribution ${\cal D}$ over a domain ${\cal X}=\{\pm 1\}^{n}$. For an item (or individual) $x\in{\cal X}$, its label will be given by the linear classifier $w(x)=x_{1}$. Note that the linear classifier $w$ indeed is perfectly accurate.Note that the expected margin in this distribution is small compared to the norms of the examples. This is for simplicity and readability. The full hardness result is shown (in a very similar manner) for data where the margins are large. In particular, this means that the class of predictors $H_{\phi,L}$ can achieve good accuracy with constant $L$. See Section 6.

To argue that fair learning is intractable, we construct two metrics $d_{U}$ and $d_{V}$ that are computationally indistinguishable: no polynomial-time algorithm can tell them apart (even given the explicit description of the metric).More formally, we construct two distribution on metrics, such that no polynomial-time algorithm can tell whether a given metric was sampled from the first distribution or from the second. For readability, we mostly ignore this distinction in this sketch. We construct these metrics so that $d_{U}$ does not allow any non-trivial accuracy, whereas $d_{V}$ essentially imposes no fairness constraints. Thus, $w$ is a perfectly fair and perfectly accurate classifier w.r.t. $d_{V}$. Now, since a polynomial-time learning algorithm ${\cal A}$ cannot tell $d_{U}$ and $d_{V}$ apart, it has to output the same (distribution on) classifiers given either of these two metrics. If ${\cal A}$, given $d_{U}$, outputs a classifier with non-trivial accuracy, then it violates perfect metric-fairness. Thus, when given $d_{U}$, ${\cal A}$ must (with high probability) output a classifier with error close to $1/2$. This remains the case even when ${\cal A}$ is given the metric $d_{V}$ (by indistinguishability), despite the fact perfect metric-fairness under $d_{V}$ allows for perfect accuracy.

We construct the metrics as follows. The metric $d_{V}$ gives every pair of individuals $x,x^{\prime}\in{\cal X}$ distance 1. The metric $d_{U}$, on the other hand, partitions the items in ${\cal X}$ into disjoint pairs $(x,x^{\prime})$ where the label of $x$ is $1$, the label of $x^{\prime}$ is $-1$, but the distance between $x$ and $x^{\prime}$ is 0.Formally, $d_{U}$ is a pseudometric, since it has distinct items at distance 0. We can make $d_{U}$ be a true metric by replacing the distance 0 with an arbitrarily small positive quantity. The hardness result is essentially unchanged. Thus, the metric $d_{U}$ assigns to each item $x\in X$ a “hidden counterpart” $x^{\prime}$ that is identical to $x$, but has the opposite label. The distance between any two distinct elements that are not “hidden counterparts” is 1 (as in $d_{V}$). The metric $d_{U}$ specifies that hidden counterparts $(x,x^{\prime})$ are identical, and thus any perfectly metric-fair classifier $h$ must treat them identically. Since $x$ and $x^{\prime}$ have opposing labels, $h$’s average error on the pair must be $1/2$. The support of ${\cal D}$ is partitioned into disjoint hidden counterparts, and thus we conclude that $\mathit{err}_{\cal D}(h)=1/2$. Note that this is true regardless of $h$’s complexity (in particular, it also rules out improper learning). We construct the metrics using a cryptographic pseudorandom generator (PRG), which specifies the hidden counterparts (in $d_{U}$) or their absence (in $d_{V}$). See the full version for details.

We make several remarks about the above hardness result. First, note that the data distribution is fixed, and the optimal classifier is linear and very simple: it only considers a single coordinate. This makes the hardness result sharper: without fairness, the learning task is trivial (indeed, since the classifier is fixed there is nothing to learn). It is the fairness constraint (and only the fairness constraint) that leads to intractability. The computational hardness of perfectly fair learning applies also to improper learning. Finally, the metrics for which we show hardness are arguably contrived (though we note they do obey the triangle inequality). This rules out perfectly metric-fair learners that work for any given metric. A natural direction for future work is restricting the choice of metric, which may make perfectly metric-fair learning feasible.

7 Further Related Work

There is a growing body of work attempting to study the question of algorithmic discrimination, particularly through the lens of machine learning. This literature is characterized by an abundance of definitions, each capturing different discrimination concerns and notions of fairness. This literature is vast and growing, and so we restrict our attention to the works most relevant to ours.

One high-level distinction can be drawn between group and individual notions of fairness. Group-fairness notions assume the existence of a protected attribute (e.g gender, race), which induces a partition of the instance space into some small number of groups. A fair classifier is one that achieves parity of some statistical measure across these groups. Some prominent measures include classification rates (statistical parity, see e.g [FFM+15]), calibration, and false positive or negative rates [KMR16, Cho17, HPS16]. It has been established that some of these notions are inherently incompatible with each other, in all but trivial cases [KMR16, Cho17]. The work of [WGOS17] takes a step towards incorporating the fairness notion of [HPS16] into a statistical and computational theory of learning, and considers a relaxation of the fairness definition to overcome the computational intractability of the learning objective. The work of [DIKL17] proposes an efficient framework for learning different classifiers for different groups in a fair manner.

Individual fairness [DHP+12] posits that “similar individuals should be treated similarly”. This powerful guarantee is formalized via a Lipschitz condition (with respect to an existing task-specific similarity metric) on the classifier mapping individuals to distributions over outcomes. Recent works [JKMR16, JKM+] study different individual-level fairness guarantees in the contexts of reinforcement and online learning. The work of [ZWS+13] aims to learn an intermediate “fair” representation that best encodes the data while successfully obfuscating membership in a protected group. See also the more recent work [BCZC17].

Several works have studied fair regression [KAAS12, CKK+13, ZVGRG17, BHJ+17]. The main differences in our work are a focus on metric-based individual fairness, a strong rigorous fairness guarantee, and proofs of competitive accuracy (both stated with respect to the underlying population distribution).

Metric Fairness Definitions

Dwork et al. [DHP+12] introduced individual fairness, a similarity-based fairness notion in which a probabilistic classifier is said to be fair if it assigns similar distributions to similar individuals.

A probabilistic classifier $h:\,{\cal X}\rightarrow\left[0,1\right]$ is said to be perfectly metric-fair w.r.t a distance metric $d:\,{\cal X}\times{\cal X}\rightarrow\left[0,1\right]$, if for every $x,x^{\prime}\in{\cal X}$,

where $h(x)$ is interpreted as the probability $h$ will assign the label $+1$ to $x\in{\cal X}$, $\Lambda$ is a distance measure between distributions and $d$ is a task-specific distance metric that is assumed to be known in advance. Throughout this work we take $\Lambda$ to be the statistical distance, yielding $\Lambda\left(h(x),h(x^{\prime})\right)=\left|h(x)-h(x^{\prime})\right|$).

In the setting considered by [DHP+12], a finite set of individuals $V$ should be assigned outcomes from a set $A$. Under the assumption that $d$ is known, they demonstrated that the problem of minimizing an arbitrary loss function $L:V\times A\rightarrow R$, subject to the individual fairness constraint can be formulated as an LP and thus can be solved in time poly$(|A|,|V|)$.

2 Approximate Metric-Fairness

We consider a learning setting in which the goal is learning a classifier $h$ that satisfies the fairness constraint in Equation (3) with respect to some unknown distribution ${\cal D}$ over ${\cal X}$, after observing a finite sample $S\sim{\cal D}^{m}$. To this end, we introduce a metric-fairness loss function that, for a given classifier $h$ and a pair of individuals in ${\cal X}$, assigns a penalty of 1 if the fairness constraint is violated by more than a $\gamma$ additive term.

For a metric $d$ and $\gamma\geq 0$, the metric-fairness loss on a pair $(x,x^{\prime})\in{\cal X}$ is

The overall metric-fairness loss for a hypothesis $h$ is the expected violation for a random pair according to ${\cal D}$.

We go on to define the empirical fairness loss, a data-dependent quantity designed to estimate the unknown $\mathcal{L}_{\mathcal{D},d,\gamma}^{F}(h)$. To this end, we think of a sample $S\sim{\cal D}^{m}$ as defining a complete weighed graph, denoted $G(S)$, whose vertices are $S$ and whose edges are weighed by $w(e)=w(x_{i},x_{j})=d(x_{i},x_{j})$. Now, observe that when $S$ is sampled i.i.d from ${\cal D}$, any matching $M\subseteq G(S)$Note that from the structure of $G(S)$, it has exactly $m$ matchings, each of size $\frac{m-1}{2}$ (w.l.o.g, we assume $m$ is odd). is an i.i.d sample from ${\cal D}\times{\cal D}$. We now define the empirical loss by replacing the expectation over ${\cal D}$ in Equation (5) with the expectation over some matching $M\subseteq G(S)$.

Finally, we will say that a classifier $h$ is $\left(\alpha,\gamma\right)$-fair w.r.t ${\cal D}$ (respectively, $S$) and $d$ if its respective metric-fairness loss is at most $\alpha$.

A probabilistic classifier $h:\,{\cal X}\rightarrow\left[0,1\right]$ is said to be $\left(\alpha,\gamma\right)$-fair w.r.t a metric $d$ and ${\cal D}$ (respectively, $S$) if $\mathcal{L}_{\mathcal{D},d,\gamma}^{F}(h)\leq\alpha$ (respectively, $\mathcal{L}_{\mathcal{S},d,\gamma}^{F}(h)\leq\alpha$).

When $S$ and $d$ are clear from context, we will use the more succinct notation $\mathcal{L}^{F}_{\gamma}(h)$ for the true fairness loss and $\widehat{\mathcal{L}}^{F}_{\gamma}(h)$ for the empirical fairness loss. When dealing with a hypothesis class ${\cal H}$, we use ${\cal H}^{\alpha,\gamma}\subseteq{\cal H}$ to denote all the $(\alpha,\gamma)$-fair hypotheses in ${\cal H}$ (w.r.t ${\cal D}$), and $\widehat{H}^{\alpha,\gamma}\subseteq{\cal H}$ for those which are $(\alpha,\gamma)$-fair w.r.t $S$.

3 Approximate Metric Fairness: Interpretation

An $\alpha$-fair classifier (for $\alpha>0$) no longer holds any guarantee for any single individual. To interpret the guarantee it does give, we consider the following definition.

A probabilistic classifier $h:\,{\cal X}\rightarrow\left[0,1\right]$ is said to be $\left(\alpha_{1},\alpha_{2};\gamma\right)$ metric-fair w.r.t $d,{\cal D}$ if

Definition 2.6 is very similar to 2.5 but it lends itself to a more intuitive interpretation of fairness for groups. Informally, we will say that an individual feels $\alpha_{2}$-discriminated against by $h$ if the proportion of individuals with whom his constraint is violated (think: individuals who are equally qualified to him but receive different treatment) exceeds $\alpha_{2}$; now, $\left(\alpha_{1},\alpha_{2}\right)$-fairness ensures that the proportion of individuals who find $h$ to be $\alpha_{2}$-discriminatory does not exceed $\alpha_{1}$. Hence, this is a guarantee for groups: an $\left(\alpha_{1},\alpha_{2}\right)$-fair classifier cannot cause an entire group of fractional mass $\alpha_{1}$ to be discriminated against. The strength of this guarantee is that it holds for any such group (even for those formed “ex-ante”). In this sense, $\left(\alpha_{1},\alpha_{2}\right)$-fairness represents a middle-ground between the strict notion of individual fairness and the loose notions of group-fairness.

Finally, we show that the two definitions are related: any $\alpha$-fair classifier is also $\left(\alpha_{1},\alpha_{2}\right)$-fair, for every $\alpha_{1},\alpha_{2}$ for which $\alpha_{1}\cdot\alpha_{2}\geq\alpha$. This demonstrates that optimizing for accuracy under an $\alpha$-fairness constraint is a flexible way of achieving interpretable fairness guarantees for a range of desired $\alpha_{1},\alpha_{2}$ values.

For every $\alpha,\gamma\in(0,1)$, and $\alpha_{1},\alpha_{2}\in(0,1)$ for which $\alpha_{1}\cdot\alpha_{2}\geq\alpha$, if $h$ is $\left(\alpha,\gamma\right)$-fair then it is also $\left(\alpha_{1},\alpha_{2};\gamma\right)$-fair.

Proof of Claim 2.7. For simplicity, we define the following indicator function,

Let $\alpha,\gamma,\alpha_{1},\alpha_{2}\in(0,1)$ such that $\alpha_{1}\cdot\alpha_{2}\geq\alpha$, and assume that $h$ is $(\alpha,\gamma)$-fair w.r.t $\mathcal{D}$. Assume for contradiction that $h$ is not $\left(\alpha_{1},\alpha_{2};\gamma\right)$-fair w.r.t $\mathcal{D}$. That means that

If we denote the subset of “$\alpha_{2}$-discriminated” individuals as $B$,

then the assumption is equivalent to $Pr_{x\sim\mathcal{D}}\left[x\in S\right]>\alpha_{1}$. We now obtain:

where the first transition is from the assumption that $h$ is $\left(\alpha,\gamma\right)$-fair, and the final transition is from the assumption that $h$ is not $\left(\alpha_{1},\alpha_{2};\gamma\right)$-fair. We therefore have that $\alpha>\alpha_{1}\cdot\alpha_{2}$, which contradicts our assumption. $\Box$

In this work we focus on approximate metric-fairness and the $\left(\alpha,\gamma\right)$ metric fairness loss (Definition 2.2). We find that this notion provides appealing and interpretable protections from discrimination: as discussed above, for small enough $\alpha,\gamma$, every sufficiently large group is protected from blatant discrimination (see Section 2.3). However, in turning to design efficient metric-fair learning algorithms, working directly with this definition presents difficulties (see Section 5). In particular, the “0/1” nature of the metric fairness loss means that the set $\widehat{H}^{\alpha,\gamma}$ is not a convex set. Trying to learn an empirically $(\alpha,\gamma)$ metric-fair that optimizes accuracy is a non-convex optimization problem, and it isn’t clear how to optimize using convex-optimization tools.

In light of this difficulty, we introduce a different metric-fairness loss definition. It overcomes the non-convexity by replacing the bound on the expected number of fairness violations with a bound on the expected sum of the fairness violations.

Similarly to the regular metric-fairness loss, the loss for a hypothesis $h$ is the expected violation for a random pair according to $\mathcal{D}$, and the empirical loss replaces the expectation over $\mathcal{D}$ with the expectation over some matching $M\subseteq G(S)$.

Proof of Lemma 2.10. We begin by defining the induced violation vector of a classifier $h\in H$. For a sample $S$, a matching $M\subseteq G(S)$ and a value $\gamma\in(0,1)$, the induced violation vector $\xi_{\gamma}(h)\in\left\{0,1\right\}^{\left|M\right|}$ is defined as:

where $(\mathbf{x},\mathbf{x^{\prime}})$ is the $i$-th edge in the matching $M$.

5 Generalization

A key issue in learning theory is that of generalization: to what extent is a classifier that is accurate on a finite sample $S\sim{\cal D}^{m}$ also guaranteed to be accurate w.r.t the underlying distribution? In this section, we work to develop similar generalization bounds for our metric-fairness loss function. Proving that fairness can generalize well is a crucial component in our analysis - it effectively rules out the possibility of creating a “false facade” of fairness (i.e, a classifier that only appears fair on a sample, but is not fair w.r.t new individuals).

The generalization bounds will be based on proving uniform convergence of the empirical estimates (in our case, $\widehat{\mathcal{L}}^{F}_{\gamma}(h)$) to the fairness loss, simultaneously for every $h\in{\cal H}$, in terms of the Rademacher complexity of the hypotheses class ${\cal H}$. Rademacher complexity differs from celebrated VC-dimension complexity measure in three aspects: first, it is defined for any class of real-valued functions (making it suitable for our setting of learning probabilistic classifiers); second, it is data-dependent and can be measured from finite samples; third, it often results in tighter uniform convergence bounds (see, e.g, [KP02]).

Let $Z$ be an input space, ${\cal D}$ a distribution on $Z$, and $\mathcal{F}$ a real-valued function class defined on $Z$. The empirical Rademacher complexity of $\mathcal{F}$ with respect to a sample $S=\left\{z_{1}\dots z_{m}\right\}$ is the following random variable:

The expectation is taken over $\sigma=\left(\sigma_{1},\dots,\sigma_{m}\right)$ where the $\sigma_{i}$’s are independent uniformly random variables taking values in $\{{\pm 1}\}$. The Rademacher complexity of $\mathcal{F}$ is defined as the expectation of $\widehat{\mathcal{R}}_{m}(\mathcal{F})$ over all samples of size $m$:

Let $\mathcal{H}$ be a hypotheses class with Rademacher complexity $R_{m}(\mathcal{H})$. For every $\delta,\gamma\in(0,1)$, every $G\geq 1$ and every $m\geq 0$ (w.l.o.g assume $m$ is odd), with probability at least $1-\delta$ over an i.i.d sample $S\sim{\cal D}^{m}$, simultaneously for every $h\in\mathcal{H}$:

where $\Delta_{m}=2G\cdot\left(4\widehat{R}_{\frac{m-1}{2}}\left(\mathcal{H}\right)+\frac{4+17\sqrt{\ln(4/\delta)}}{\sqrt{m-1}}\right)$.

Let $H_{\psi,C}$ as above, for any $C\geq 0$ and kernel $K$. For every $\delta,\gamma\in(0,1)$, every $G\geq 1$ and every $m\geq 0$, w.p at least $1-\delta$, simultaneously for every $h\in H_{\psi,C}$

where $M=\sup K(\mathbf{x},\mathbf{x}^{\prime})$ and $\Delta_{m}=2G\cdot\frac{4+4\sqrt{2}\sqrt{CM}+17\sqrt{\ln(4/\delta)}}{\sqrt{m-1}}$.

Proof of Corollary 2.13. The proof follows from Theorem 2.12 and the fact that the Rademacher complexity ${R}_{m}{(H_{\psi,C})}$ is bounded by $\sqrt{\frac{C\cdot M}{m}}$ (see [KST09]).

To set the stage for proving Theorem 2.12, we state some useful properties of the Rademacher complexity notion, see [BM02].

Consider a set of functions $\mathcal{F}$ mapping $Z$ to $\left[0,1\right]$. For every $\delta>0$, with probability at least $1-\delta$ over a random draw of a sample $S$ of size $m$, every $f\in F$ satisfies

Let $F$ be a class of real functions. Then, for any sample $S$ of size $m$:

For every $\delta\in(0,1)$, w.p at least $1-\delta$ over the choice of $S$,

Denote the threshold function at $\gamma$:

Observe that $\mathcal{G}$ can be further decomposed as

where $\mathcal{H}^{\prime}=\left\{(x,x^{\prime})\mapsto h(x)-h(x^{\prime})\right\}_{h\,\in\,\mathcal{H}}\triangleq\left\{g_{h}\right\}_{h\,\in\,\mathcal{H}}$, abs$(\cdot)$ is the absolute value function (which is 1-Lipschitz), and $f=f(x,x^{\prime})=-d(x,x^{\prime})$.

$R_{\widetilde{m}}(\mathcal{H}^{\prime})\leq 2R_{\widetilde{m}}(\mathcal{H})$.

Proof of Claim 2.16. Denote $M(S)=\left\{z_{1},\dots,z_{\widetilde{m}}\right\},$where $z_{i}=\left(x_{i}^{1},x_{i}^{2}\right)$. By definition,

where the transition marked by $(\star)$ is due to the fact that negating a Rademacher variable does not change its distribution. $\Box$

$R_{\widetilde{m}}(\mathcal{G})\leq 4R_{\widetilde{m}}(\mathcal{H})+\frac{2}{\sqrt{\widetilde{m}}}$

$\Box$ Now, had the threshold function $\sigma_{\gamma}$ been Lipschitz, we could again use Fact 2 in Lemma 2.15 to finish the proof. Unfortunately, $\sigma_{\gamma}$ is not Lipschitz. We therefore instead approximate it using a piecewise linear function with Lipschitz constant $G$, which we denote with $\tau_{\gamma}^{G}$:

For every $G\geq 0$, every $\gamma\in(0,1)$ and every function $h$,

Proof of Proposition 2.18. The proof follows directly from the fact that from the construction of $\tau_{\gamma}^{G}$, it holds that for every $u$, $\sigma_{\gamma+\frac{1}{G}}(u)\leq\tau_{\gamma}^{G}(u)\leq\sigma_{\gamma}(u)$. $\Box$

We can use the Lipschitzness of $\tau_{\gamma}^{G}$ to obtain

By plugging $\mathcal{\widetilde{\mathcal{F}}}$ into Theorem 2.14 (Equation 12), we’d have that with probability at least $1-\frac{\delta}{2}$ over random draws of samples of size $\widetilde{m}$, every $h\in H$ satisfies

Since we eventually want a data-dependent bound, we’ll Fact 3 in Lemma 2.15 to deduce that w.p at least $1-\frac{\delta}{2}$,

Combining both the previous inequalities and using the union bound, we obtain that for every $G\geq 0$, with probability at least $1-\delta$, simultaneously $\forall h\in\mathcal{H}$

where $\Delta_{m}=2G\cdot\left(4\widehat{R}_{\frac{m-1}{2}}\left(\mathcal{H}\right)+\frac{4+17\sqrt{\ln(4/\delta)}}{\sqrt{m-1}}\right)$, as required.

(Fair and Accurate) Learning Objectives

We will consider a learning problem as given by a 5-tuple $\left({\cal X},\left({\cal Y},{\cal Y}^{\prime}\right),\mathcal{H},\left(\mathcal{L}^{U},{\cal L}^{F}\right)\right)$. In this notation, ${\cal X}$ is the set of instances; ${\cal Y}$ is the set of possible labels assigned to instances; ${\cal Y}^{\prime}\supseteq{\cal Y}$ is the set of labels the learner is allowed to return; ${\cal H}$ is a fixed family of predictors $h:{\cal X}\rightarrow{\cal Y}^{\prime}$ which we require the learner to compete with (in terms of the returning a classifier with loss comparable to the best loss in ${\cal H}$); ${\cal L}^{U}$ is a univariate (“utility”) loss function used to measure the discrepancy between the predicted outputs and the true labels; and finally, ${\cal L}^{F}$ is a bivariate (“fairness”) loss function. We denote $\mathcal{L}_{\mathcal{D}}^{U}\left(\mathcal{H}\right)=\min_{h\in\mathcal{H}}\left(\mathcal{L}_{\mathcal{D}}^{U}(h)\right)$.

2 PAC Learnability under a fairness constraint

From a learning perspective, we say that a learning algorithm is fair if w.h.p, it returns a sufficiently-fair classifier.

Note that any learning algorithm $A$ that completely disregards the sample and simply outputs a constant predictor (e.g, $h(x)\equiv 1$) satisfies the condition in Equation 2.1 and is therefore a (0,0)-fair learning algorithm. In other words, fair learning is, in itself, trivial. It is the combination of a fairness and an accuracy objective that makes for an interesting task. In this work, we focus on the objective of maximizing utility subject to a constraint on the fairness loss. This is a natural formulation, because we think of fairness as a hard (often externally imposed) requirement that cannot necessarily be traded off for better accuracy. The objective of finding the most accurate sufficiently-fair hypothesis is summarized in the following definition. Crucially, both fairness and accuracy goals are stated w.r.t the unknown underlying distribution.

We consider the above definition as strong PACF learnability, and also define a relaxed notion, in which the learner must still output an hypothesis that is $\alpha$ fair, but in terms of accuracy is only required to compete with $\mathcal{H}^{\alpha^{\prime}}$, for some $0\leq\alpha^{\prime}\leq\alpha$, that does not need to approach $\alpha$ as $m\rightarrow\infty$. We formalize this using a function $g:^{2}\rightarrow^{2}$ that captures the degradation in the accuracy guarantee.

Information Theoretic PACF Learnability

Using the generalization result from Theorem 2.12, we can now derive the sample complexity for strong PACF learnability in the information theoretic setting.

Suppose ${\cal H}$ is PAC learnable with sample complexity $m_{PAC}(\epsilon,\delta)$. Then it is PACF learnable with sample complexity

Let $\alpha,\gamma\in(0,1)$ required fairness parameters, $\delta\in(0,1)$ required failure probability and $\epsilon,\epsilon_{\alpha},\epsilon_{\gamma}\in(0,1)$ error parameters. Let $m,G$ be parameters to be determined later. Set $\widetilde{\gamma}=\gamma-\frac{1}{G}$ and $\widetilde{\alpha}=\alpha-\Delta_{m}$, for $\Delta_{m}=2G\cdot\left(4\widehat{R}_{\frac{m-1}{2}}\left(\mathcal{H}\right)+\frac{4+17\sqrt{\ln(4/\delta)}}{\sqrt{m-1}}\right)$.

Let $h^{\star}$ denote the solution to the fairness-constrained ERM,

Let $m_{F}=\left(\frac{8+34\sqrt{\ln(4/\delta)}}{\epsilon_{\alpha}\epsilon_{\gamma}-8\widehat{R}_{\frac{m-1}{2}}(\mathcal{H})}\right)^{2}+1$ and $m_{PAC}=m_{PAC}(\epsilon,\delta)$.,

For fairness, we use Theorem 2.12 to prove that for every $m,G$, w.p at least $1-\frac{\delta}{2}$ over the choice of $S\sim\mathcal{D}^{m}$, $h^{\star}$ is $\left(\alpha,\gamma\right)$-fair w.r.t $\mathcal{D}$:

For accuracy, we note that the known equivalence of learnability and uniform convergence in the regression setting [ABDCBH97] implies that for $m\geq m_{PAC}$, w.p at least $1-\delta/2$, for every $h\in{\cal H}$, $\mathcal{L}^{U}(h)\leq\mathcal{\widehat{L}}^{U}(h)+\epsilon$. Using this we obtain that w.p at least $1-\delta/2$, for $m\geq\max\left\{m_{PAC},m_{PACF}\right\}$:

We now use the union bound to conclude that setting $m\geq\max\left\{m_{PAC},m_{F}\right\}$ yields that with probability at least $1-\delta$ over the choice of $S\sim\mathcal{D}^{m}$, $h$ satisfies all the conditions in Definition 3.2, and is therefore (exact) PACF learnable.

Efficient relaxed-PACF Learnability of Linear Predictors

In this section, we present our main result, which is that the classes of (linear and logistic) predictorsSince we interpret the output of the linear and logistic regression models are probabilities for a classification model, we refer to them as linear and logistic classifiers, rather than regressors. are efficiently $g(\cdot)$-relaxed PACF-learnable, with $g(\alpha,\gamma)=(\alpha\cdot\gamma-\gamma^{\star},\gamma^{\star})$, for every $\gamma^{\star}\in(0,1)$. We begin with the proof for the class of linear classifiers, which demonstrates the idea of a relaxation that allows for efficient solving of the optimization problem associated with the relaxed PACF learnability requirement. We then proceed to the case of logistic predictors, which is more involved due to the non-convexity of the fairness objective induced by a logistic transfer function. We overcome this difficulty using improper learning.

For the remainder of this section, we consider the problem of efficiently PACF learning the problem $\allowbreak\left(\mathcal{X},\left(\mathcal{Y},\mathcal{Y}^{\prime}\right),H,\left(\mathcal{L}^{U},\mathcal{L}^{F}\right)\right)$, where: $\mathcal{X}$ is a compact subset of an RKHS, which w.l.o.g. will be taken to be the unit ball around the origin; $\mathcal{Y=}\left\{\pm 1\right\}$ and $\mathcal{Y}^{\prime}=\left[0,1\right]$, since we’re interested in performing classification using probabilistic classifiers; the utility loss $\mathcal{L}^{U}$ is the absolute value loss function and $\mathcal{L}^{F}$ is the approximate metric-fairness loss w.r.t some known metric $d$. We define hypothesis classes $H_{lin}$ and $H_{\phi}$, corresponding to linear and logistic regression predictors, as follows. $H_{lin}$ is the class of linear predictors, The norm bound on $\mathbf{w}$ is so to ensure that $h(x)\in\left[-1,1\right]=\mathcal{Y}$

And $H_{\phi,L}$ is the class of logistic predictors, formed by composing a linear function with a sigmoidal transfer function:

2 Linear Regression

For every $\gamma^{\star}\in(0,1)$, $H_{lin}$ is relaxed PACF learnable with $g(\alpha,\gamma)=(\alpha\cdot\gamma-\gamma^{\star},\gamma^{\star})$ and sample and time complexities of $poly(\frac{1}{\epsilon_{\gamma}},\frac{1}{\epsilon_{\alpha}},\frac{1}{\epsilon},\log\frac{1}{\delta})$

The proof is structured as follows. First, we discuss why the immediate optimization problem associated with PACF learning $H_{lin}$ is not efficiently solvable. We then show a convex problem whose solution can be shown to meet the fairness and competitiveness requirements in Definition 3.3, but with respect to the sample. We conclude the proof by proving generalization of both the fairness and the competitiveness requirements.

For simplicity, we use $H=H_{lin}$ throughout the proof. Fix a sample $S$. The straight-forward approach to PACF learn $\allowbreak\left(\mathcal{X},\left(\mathcal{Y},\mathcal{Y}^{\prime}\right),H,\left(\mathcal{L}^{U},\mathcal{L}^{F}\right)\right)$ would be to search $H$ for an hypothesis that minimizes the empirical risk, subject to being sufficiently fair w.r.t the pairs from $M(S)$ (a random matching induced by the sample $S$). This is equivalent to solving the following optimization problem, for some appropriate setting of $\alpha,\gamma\in(0,1)$:

here, $\xi_{e}(\mathbf{w})\in{0,1}$ is an indicator for whether the metric-fairness constraint on the sample pair $e=\left(\mathbf{x},\mathbf{x}^{\prime}\right)$ is violated by more than an additive $\gamma$ term or not, $\xi(\mathbf{w})\in\left\{0,1\right\}^{\left|M(S)\right|}$ is the vector of violations on $M(S)$ induced by the linear classifier parametrized by $\mathbf{w}$, and $\|\xi(\mathbf{w})\|_{0}\leq\alpha\cdot\left|M(S)\right|$ ensures that the overall fraction of such violations does not exceed $\alpha$. We formalize the definition of a fairness-violation vector as follows:

For every $\mathbf{w}\in{\cal X}$ and $\gamma\in(0,1)$, the induced violation vector $\xi^{\gamma}(\mathbf{w})\in\left\{0,1\right\}^{\left|M(S)\right|}$ is defined as

Let $e=\left(\mathbf{x},\mathbf{x}^{\prime}\right)\in M(S)$. Then,

this implies that for every $e\in M(S)$, $\xi_{e}(\mathbf{w})=t\cdot\xi_{e}(\mathbf{w}_{1})+(1-t)\cdot\xi_{e}(\mathbf{w}_{2})$. Observe that since $t\in\left[0,1\right]$ and $0\leq\xi_{e}(\mathbf{w}_{1}),\xi_{e}(\mathbf{w}_{2})\leq 1$, we also have that $0\leq\xi_{e}(\mathbf{w})\leq 1$. Finally, the third constraint also holds, since we have that:

To arrive at satisfying the conditions of relaxed metric-fair learning, it’s left to prove that these guarantees can be extended to also hold for the underlying distribution ${\cal D}$. To this end, we employ generalization arguments for both the utility and fairness loss. For utility (Claim 5.4), we use a standard Rademacher-based uniform convergence result, stated for the general setting of a class of linear predictors with bounded norm in a RHKS; for fairness (Claim 5.5) we use the generalization result from Corollary 2.13.

For every $\alpha,\gamma\in(0,1)$, $G\geq 1$ and $\delta\in(0,1)$, with probability at least $1-\frac{\delta}{2}$ over an i.i.d sample $S\sim{\cal D}^{m}$,

where $\rho=2G\cdot\frac{4+4\sqrt{2}+17\sqrt{\ln(4/\delta)}}{\sqrt{m-1}}$.

Proof of Claim 5.5. Let $G\geq 1$ and $\gamma\in(0,1)$. From Corollary 2.13 (recall that in our setting, $C=M=1$), we obtain that w.p at least $1-\frac{\delta}{2}$ over an i.i.d sample $S\sim{\cal D}^{m}$,

This implies that with all but $\frac{\delta}{2}$ probability, for every $\alpha\in(0,1)$, the following holds:

We are now prepared to prove relaxed PACF learnability of $H$. Let $\alpha,\gamma\in(0,1)$ be the required fairness parameters, $\delta\in(0,1)$ required failure probability and $\epsilon,\epsilon_{\alpha},\epsilon_{\gamma}\in(0,1)$ error parameters. Let $G,m$ be parameters to be determined later. Define $\widetilde{\alpha}=\left(\alpha-\rho\right)\cdot\widetilde{\gamma}$ and $\widetilde{\gamma}=\gamma-\frac{1}{G}$, and denote with $\mathbf{w}$ the solution to the program in Equation 23 using the parameter $\widetilde{\alpha}$.

with probability at least $1-\tfrac{\delta}{2}$, $\mathbf{w}$ is $\left(\alpha,\gamma\right)$-fair w.r.t $\mathcal{D}$.

ensures that with probability at least $1-\tfrac{\delta}{2}$ over an i.i.d sample $S\sim{\cal D}^{m}$, for every $\gamma^{\star}$,

First, let $m^{1}=\left(\frac{2\cdot\left(\sqrt{2}+\sqrt{\ln(8/\delta)}\right)}{\sqrt{2}\epsilon}\right)^{2}$.

It is left to show that there is some setting of $G$ and a sufficiently large sample size $m$ for which it holds that

Denote $\epsilon^{\prime}=\min\left\{\epsilon_{\alpha},\frac{\epsilon_{\gamma}}{2}\right\}$ and set $G=\frac{1}{\epsilon^{\prime}}$. The second equation is now satisfied, because $\frac{1}{G}=\epsilon^{\prime}\leq\frac{\epsilon_{\gamma}}{2}\leq\epsilon_{\gamma}$. Plugging this into the first equation and simplifying, we obtain:

For simplicity, denote $\rho=\frac{G\overbrace{\left(8+8\sqrt{2}+34\sqrt{\ln(4/\delta)}\right)}^{z(\delta)}}{\sqrt{m-1}}=\frac{z(\delta)}{\epsilon^{\prime}\cdot\sqrt{m-1}}$ and note that $\frac{\epsilon_{\alpha}-\alpha\cdot\epsilon^{\prime}}{1+\gamma-\epsilon^{\prime}}\geq\frac{(1-\alpha)\cdot\epsilon_{\alpha}}{2}$. It therefore suffices to choose $m$ such that: