Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairness

Introduction

As machine learning is being deployed in increasingly consequential domains (including policing (Rudin, 2013), criminal sentencing (Barry-Jester et al., 2015), and lending (Koren, 2016)), the problem of ensuring that learned models are fair has become urgent.

Approaches to fairness in machine learning can coarsely be divided into two kinds: statistical and individual notions of fairness. Statistical notions typically fix a small number of protected demographic groups $\mathcal{G}$ (such as racial groups), and then ask for (approximate) parity of some statistical measure across all of these groups. One popular statistical measure asks for equality of false positive or negative rates across all groups in $\mathcal{G}$ (this is also sometimes referred to as an equal opportunity constraint (Hardt et al., 2016)). Another asks for equality of classification rates (also known as statistical parity). These statistical notions of fairness are the kinds of fairness definitions most common in the literature (see e.g. Kamiran and Calders (2012); Hajian and Domingo-Ferrer (2013); Kleinberg et al. (2017); Hardt et al. (2016); Friedler et al. (2016); Zafar et al. (2017); Chouldechova (2017)).

One main attraction of statistical definitions of fairness is that they can in principle be obtained and checked without making any assumptions about the underlying population, and hence lead to more immediately actionable algorithmic approaches. On the other hand, individual notions of fairness ask for the algorithm to satisfy some guarantee which binds at the individual, rather than group, level. This often has the semantics that “individuals who are similar” should be treated “similarly” (Dwork et al., 2012), or “less qualified individuals should not be favored over more qualified individuals” (Joseph et al., 2016). Individual notions of fairness have attractively strong semantics, but their main drawback is that achieving them seemingly requires more assumptions to be made about the setting under consideration.

The semantics of statistical notions of fairness would be significantly stronger if they were defined over a large number of subgroups, thus permitting a rich middle ground between fairness only for a small number of coarse pre-defined groups, and the strong assumptions needed for fairness at the individual level. Consider the kind of fairness gerrymandering that can occur when we only look for unfairness over a small number of pre-defined groups:

Imagine a setting with two binary features, corresponding to race (say black and white) and gender (say male and female), both of which are distributed independently and uniformly at random in a population. Consider a classifier that labels an example positive if and only if it corresponds to a black man, or a white woman. Then the classifier will appear to be equitable when one considers either protected attribute alone, in the sense that it labels both men and women as positive 50% of the time, and labels both black and white individuals as positive 50% of the time. But if one looks at any conjunction of the two attributes (such as black women), then it is apparent that the classifier maximally violates the statistical parity fairness constraint. Similarly, if examples have a binary label that is also distributed uniformly at random, and independently from the features, the classifier will satisfy equal opportunity fairness with respect to either protected attribute alone, even though it maximally violates it with respect to conjunctions of two attributes.

We remark that the issue raised by this toy example is not merely hypothetical. In our experiments in Section 5, we show that similar violations of fairness on subgroups of the pre-defined groups can result from the application of standard machine learning methods applied to real datasets. To avoid such problems, we would like to be able to satisfy a fairness constraint not just for the small number of protected groups defined by single protected attributes, but for a combinatorially large or even infinite collection of structured subgroups definable over protected attributes.

In this paper, we consider the problem of auditing binary classifiers for equal opportunity and statistical parity, and the problem of learning classifiers subject to these constraints, when the number of protected groups is large. There are exponentially many ways of carving up a population into subgroups, and we cannot necessarily identify a small number of these a priori as the only ones we need to be concerned about. At the same time, we cannot insist on any notion of statistical fairness for every subgroup of the population: for example, any imperfect classifier could be accused of being unfair to the subgroup of individuals defined ex-post as the set of individuals it misclassified. This simply corresponds to “overfitting” a fairness constraint. We note that the individual fairness definition of Joseph et al. (2016) (when restricted to the binary classification setting) can be viewed as asking for equalized false positive rates across the singleton subgroups, containing just one individual eachIt also asks for equalized false negative rates, and that the false positive rate is smaller than the true positive rate. Here, the randomness in the “rates” is taken entirely over the randomness of the classifier. — but naturally, in order to achieve this strong definition of fairness, Joseph et al. (2016) have to make structural assumptions about the form of the ground truth. It is, however, sensible to ask for fairness for large structured subsets of individuals: so long as these subsets have a bounded VC dimension, the statistical problem of learning and auditing fair classifiers is easy, so long as the dataset is sufficiently large. This can be viewed as an interpolation between equal opportunity fairness and the individual “weakly meritocratic” fairness definition from Joseph et al. (2016), that does not require making any assumptions about the ground truth. Our investigation focuses on the computational challenges, both in theory and in practice.

Formalization of the problem of auditing and learning classifiers for fairness with respect to rich classes of subgroups $\mathcal{G}$.

Results proving (under certain assumptions) the computational equivalence of auditing $\mathcal{G}$ and (weak) agnostic learning of $\mathcal{G}$. While these results imply theoretical intractability of auditing for some natural classes $\mathcal{G}$, they also suggest that practical machine learning heuristics can be applied to the auditing problem.

Provably convergent algorithms for learning classifiers that are fair with respect to $\mathcal{G}$, based on a formulation as a two-player zero-sum game between a Learner (the primal player) and an Auditor (the dual player). We provide two different algorithms, both of which are based on solving for the equilibrium of this game. The first provably converges in a polynomial number of steps and is based on simulation of the game dynamics when the Learner uses Follow the Perturbed Leader and the Auditor uses best response; the second is only guaranteed to converge asymptotically but is computationally simpler, and involves both players using Fictitious Play.

An implementation and empirical evaluation of the Fictitious Play algorithm demonstrating its effectiveness on a real dataset in which subgroup fairness is a concern.

In more detail, we start by studying the computational challenge of simply checking whether a given classifier satisfies equal opportunity and statistical parity. Doing this in time linear in the number of protected groups is simple: for each protected group, we need only estimate a single expectation. However, when there are many different protected attributes which can be combined to define the protected groups, their number is combinatorially largeFor example, as discussed in a recent Propublica investigation (Angwin and Grassegger, 2017), Facebook policy protects groups against hate speech if the group is definable as a conjunction of protected attributes. Under the Facebook schema, “race” and “gender” are both protected attributes, and so the Facebook policy protects “black women” as a distinct class, separately from black people and women. When there are $d$ protected attributes, there are $2^{d}$ protected groups. As a statistical estimation problem, this is not a large obstacle — we can estimate $2^{d}$ expectations to error $\varepsilon$ so long as our data set has size $O(d/\varepsilon^{2})$, but there is now a computational problem..

We model the problem by specifying a class of functions $\mathcal{G}$ defined over a set of $d$ protected attributes. $\mathcal{G}$ defines a set of protected subgroups. Each function $g\in\mathcal{G}$ corresponds to the protected subgroup $\{x:g_{i}(x)=1\}$For example, in the case of Facebook’s policy, the protected attributes include “race, sex, gender identity, religious affiliation, national origin, ethnicity, sexual orientation and serious disability/disease” (Angwin and Grassegger, 2017), and $\mathcal{G}$ represents the class of boolean conjunctions. In other words, a group defined by individuals having any subset of values for the protected attributes is protected.. The first result of this paper is that for both equal opportunity and statistical parity, the computational problem of checking whether a classifier or decision-making algorithm $D$ violates statistical fairness with respect to the set of protected groups $\mathcal{G}$ is equivalent to the problem of agnostically learning $\mathcal{G}$ (Kearns et al., 1994), in a strong and distribution-specific sense. This equivalence has two implications:

First, it allows us to import computational hardness results from the learning theory literature. Agnostic learning turns out to be computationally hard in the worst case, even for extremely simple classes of functions $\mathcal{G}$ (like boolean conjunctions and linear threshold functions). As a result, we can conclude that auditing a classifier $D$ for statistical fairness violations with respect to a class $\mathcal{G}$ is also computationally hard. This means we should not expect to find a polynomial time algorithm that is always guaranteed to solve the auditing problem.

However, in practice, various learning heuristics (like boosting, logistic regression, SVMs, backpropagation for neural networks, etc.) are commonly used to learn accurate classifiers which are known to be hard to learn in the worst case. The equivalence we show between agnostic learning and auditing is distribution specific — that is, if on a particular data set, a heuristic learning algorithm can solve the agnostic learning problem (on an appropriately defined subset of the data), it can be used also to solve the auditing problem on the same data set.

Next, we consider the problem of learning a classifier that equalizes false positive or negative rates across all (possibly infinitely many) sub-groups, defined by a class of functions $\mathcal{G}$. As per the reductions described above, this problem is computationally hard in the worst case.

However, under the assumption that we have an efficient oracles which solves the agnostic learning problem, we give and analyze algorithms for this problem based on a game-theoretic formulation. We first prove that the optimal fair classifier can be found as the equilibrium of a two-player, zero-sum game, in which the (pure) strategy space of the “Learner” player corresponds to classifiers in $\mathcal{H}$, and the (pure) strategy space of the “Auditor” player corresponds to subgroups defined by $\mathcal{G}$. The best response problems for the two players correspond to agnostic learning and auditing, respectively. We show that both problems can be solved with a single call to a cost sensitive classification oracle, which is equivalent to an agnostic learning oracle. We then draw on extant theory for learning in games and no-regret algorithms to derive two different algorithms based on simulating game play in this formulation. In the first, the Learner employs the well-studied Follow the Perturbed Leader (FTPL) algorithm on an appropriate linearization of its best-response problem, while the Auditor approximately best-responds to the distribution over classifiers of the Learner at each step. Since FTPL has a no-regret guarantee, we obtain an algorithm that provably converges in a polynomial number of steps.

While it enjoys strong provable guarantees, this first algorithm is randomized (due to the noise added by FTPL), and the best-response step for the Auditor is polynomial time but computationally expensive. We thus propose a second algorithm that is deterministic, simpler and faster per step, based on both players adopting the Fictitious Play learning dynamic. This algorithm has weaker theoretical guarantees: it has provable convergence only asymptotically, and not in a polynomial number of steps — but is more practical and converges rapidly in practice. The derivation of these algorithms (and their guarantees) appear in Section 4.

Finally, we implement the Fictitious Play algorithm and demonstrate its practicality by efficiently learning classifiers that approximately equalize false positive rates across any group definable by a linear threshold function on 18 protected attributes in the “Communities and Crime” dataset. We use simple, fast regression algorithms as heuristics to implement agnostic learning oracles, and (via our reduction from agnostic learning to auditing) auditing oracles. Our results suggest that it is possible in practice to learn fair classifiers with respect to a large class of subgroups that still achieve non-trivial error. Full details are contained in Section 5, and for a substantially more comprehensive empirical investigation of our method we direct the interested reader to Kearns et al. (2018).

2 Further Related Work

Independent of our work, Hébert-Johnson et al. (2017) also consider a related and complementary notion of fairness that they call “multicalibration”. In settings in which one wishes to train a real-valued predictor, multicalibration can be considered the “calibration” analogue for the definitions of subgroup fairness that we give for false positive rates, false negative rates, and classification rates. For a real-valued predictor, calibration informally requires that for every value $v\in$ predicted by an algorithm, the fraction of individuals who truly have a positive label in the subset of individuals on which the algorithm predicted $v$ should be approximately equal to $v$. Multicalibration asks for approximate calibration on every set defined implicitly by some circuit in a set $\mathcal{G}$. Hébert-Johnson et al. (2017) give an algorithmic result that is analogous to the one we give for learning subgroup fair classifiers: a polynomial time algorithm for learning a multi-calibrated predictor, given an agnostic learning algorithm for $\mathcal{G}$. In addition to giving a polynomial-time algorithm, we also give a practical variant of our algorithm (which is however only guaranteed to converge in the limit) that we use to conduct empirical experiments on real data.

Thematically, the most closely related piece of prior work is Zhang and Neill (2016), who also aim to audit classification algorithms for discrimination in subgroups that have not been pre-defined. Our work differs from theirs in a number of important ways. First, we audit the algorithm for common measures of statistical unfairness, whereas Zhang and Neill (2016) design a new measure compatible with their particular algorithmic technique. Second, we give a formal analysis of our algorithm. Finally, we audit with respect to subgroups defined by a class of functions $\mathcal{G}$, which we can take to have bounded VC dimension, which allows us to give formal out-of-sample guarantees. Zhang and Neill (2016) attempt to audit with respect to all possible sub-groups, which introduces a severe multiple-hypothesis testing problem, and risks overfitting. Most importantly we give actionable algorithms for learning subgroup fair classifiers, whereas Zhang and Neill (2016) restrict attention to auditing.

Technically, the most closely related piece of work (and from which we take inspiration for our algorithm in Section 4) is Agarwal et al. (2017), who show that given access to an agnostic learning oracle for a class $\mathcal{H}$, there is an efficient algorithm to find the lowest-error distribution over classifiers in $\mathcal{H}$ subject to equalizing false positive rates across polynomially many subgroups. Their algorithm can be viewed as solving the same zero-sum game that we solve, but in which the “subgroup” player plays gradient descent over his pure strategies, one for each sub-group. This ceases to be an efficient or practical algorithm when the number of subgroups is large, as is our case. Our main insight is that an agnostic learning oracle is sufficient to have the both players play “fictitious play”, and that there is a transformation of the best response problem such that an agnostic learning algorithm is enough to efficiently implement follow the perturbed leader.

There is also other work showing computational hardness for fair learning problems. Most notably, Woodworth et al. (2017) show that finding a linear threshold classifier that approximately minimizes hinge loss subject to equalizing false positive rates across populations is computationally hard (assuming that refuting a random $k$-XOR formula is hard). In contrast, we show that even checking whether a classifier satisfies a false positive rate constraint on a particular data set is computationally hard (if the number of subgroups on which fairness is desired is too large to enumerate).

Model and Preliminaries

We model each individual as being described by a tuple $((x,x^{\prime}),y)$, where $x\in\mathcal{X}$ denotes a vector of protected attributes, $x^{\prime}\in\mathcal{X}^{\prime}$ denotes a vector of unprotected attributes, and $y\in\{0,1\}$ denotes a label. Note that in our formulation, an auditing algorithm not only may not see the unprotected attributes $x^{\prime}$, it may not even be aware of their existence. For example, $x^{\prime}$ may represent proprietary features or consumer data purchased by a credit scoring company.

We will be concerned with learning and auditing classifiers $D$ satisfying two common statistical fairness constraints: equality of classification rates (also known as statistical parity), and equality of false positive rates (also known as equal opportunity). Auditing for equality of false negative rates is symmetric and so we do not explicitly consider it. Each fairness constraint is defined with respect to a set of protected groups. We define sets of protected groups via a family of indicator functions $\mathcal{G}$ for those groups, defined over protected attributes. Each $g:\mathcal{X}\to\{0,1\}\in\mathcal{G}$ has the semantics that $g(x)=1$ indicates that an individual with protected features $x$ is in group $g$.

Fix any classifier $D$, distribution $\mathcal{P}$, collection of group indicators $\mathcal{G}$, and parameter $\gamma\in$. For each $g\in\mathcal{G}$, define

Note that our definition references two approximation parameters, both of which are important. We are allowed to ignore a group $g$ if it (or its complement) represent only a small fraction of the total probability mass. The parameter $\alpha$ governs how small a fraction of the population we are allowed to ignore. Similarly, we do not require that the probability of a positive classification in every subgroup is exactly equal to the base rate, but instead allow deviations up to $\beta$. Both of these approximation parameters are necessary from a statistical estimation perspective. We control both of them with a single parameter $\gamma$.

Fix any classifier $D$, distribution $\mathcal{P}$, collection of group indicators $\mathcal{G}$, and parameter $\gamma\in$. For each $g\in\mathcal{G}$, define

We say $D$ satisfies $\gamma$-False Positive (FP) Fairness with respect to $\mathcal{P}$ and $\mathcal{G}$ if for every $g\in\mathcal{G}$

This definition is symmetric to the definition of statistical parity fairness, except that the parameter $\alpha$ is now used to exclude any group $g$ such that negative examples ($y=0$) from $g$ (or its complement) have probability mass less than $\alpha$. This is again necessary from a statistical estimation perspective.

For either statistical parity and false positive fairness, if the algorithm $D$ fails to satisfy the $\gamma$-fairness condition, then we say that $D$ is $\gamma$-unfair with respect to $\mathcal{P}$ and $\mathcal{G}$. We call any subgroup $g$ which witnesses this unfairness an $\gamma$-unfair certificate for $(D,\mathcal{P})$.

As we will show, our definition of auditing is closely related to weak agnostic learning.

Let $Q$ be a distribution over $\mathcal{X}\times\{0,1\}$ and let $\varepsilon,\varepsilon^{\prime}\in(0,1/2)$ such that $\varepsilon\geq\varepsilon^{\prime}$. We say that the function class $\mathcal{G}$ is $(\varepsilon,\varepsilon^{\prime})$-weakly agnostically learnable under distribution $Q$ if there exists an algorithm $L$ such that when given sample access to $Q$, $L$ runs in time $\operatorname{poly}(1/\varepsilon^{\prime},1/\delta)$, and with probability $1-\delta$, outputs a hypothesis $h\in\mathcal{G}$ such that

where $err(h,Q)=\Pr_{(x,y)\sim Q}[h(x)\neq y]$.

A crucial property of a CSC problem is that the solution is invariant to translations of the costs.

We note that cost-sensitive classification is polynomially equivalent to agnostic learning Zadrozny et al. (2003). We give both definitions above because when describing our results for auditing, we wish to directly appeal to known hardness results for weak agnostic learning, but it is more convenient to describe our algorithms via oracles for cost-sensitive classification.

Follow the Perturbed Leader.

where the randomness is taken over the perturbations $\xi^{t}$ across rounds.

1 Generalization Error

In this section, we observe that the error rate of a classifier $D$, as well as the degree to which it violates $\gamma$-fairness (for both statistical parity and false positive rates) can be accurately approximated with the empirical estimates for these quantities on a dataset (drawn i.i.d. from the underlying distribution $\mathcal{P}$) so long as the dataset is sufficiently large. Once we establish this fact, since our main interest is in the computational problem of auditing and learning, in the rest of the paper, we assume that we have direct access to the underlying distribution (or equivalently, that the empirical data defines the distribution of interest), and do not make further reference to sample complexity or overfitting issues.

A standard VC dimension bound (see, e.g. Kearns and Vazirani (1994)) states:

Fix a class of functions $\mathcal{H}$. For any distribution $\mathcal{P}$, let $S\sim\mathcal{P}^{m}$ be a dataset consisting of $m$ examples $(X_{i},y_{i})$ sampled i.i.d. from $\mathcal{P}$. Then for any $0<\delta<1$, with probability $1-\delta$, for every $h\in\mathcal{H}$, we have:

Fix a class of functions $\mathcal{H}$ and a class of group indicators $\mathcal{G}$. For any distribution $\mathcal{P}$, let $S\sim\mathcal{P}^{m}$ be a dataset consisting of $m$ examples $(X_{i},y_{i})$ sampled i.i.d. from $\mathcal{P}$. Then for any $0<\delta<1$, with probability $1-\delta$, for every $h\in\mathcal{H}$ and $g\in\mathcal{G}$

where $\mathcal{P}_{S}$ denotes the empirical distribution over the realized sample $S$.

Fix a class of functions $\mathcal{H}$ and a class of group indicators $\mathcal{G}$. For any distribution $\mathcal{P}$, let $S\sim\mathcal{P}^{m}$ be a dataset consisting of $m$ examples $(X_{i},y_{i})$ sampled i.i.d. from $\mathcal{P}$. Then for any $0<\delta<1$, with probability $1-\delta$, for every $h\in\mathcal{H}$ and $g\in\mathcal{G}$, we have:

where $\mathcal{P}_{S}$ denotes the empirical distribution over the realized sample $S$.

Equivalence of Auditing and Weak Agnostic Learning

In this section, we give a reduction from the problem of auditing both statistical parity and false positive rate fairness, to the problem of agnostic learning, and vice versa. This has two implications. The main implication is that, from a worst-case analysis point of view, auditing is computationally hard in almost every case (since it inherits this pessimistic state of affairs from agnostic learning). However, worst-case hardness results in learning theory have not prevented the successful practice of machine learning, and there are many heuristic algorithms that in real-world cases successfully solve “hard” agnostic learning problems. Our reductions also imply that these heuristics can be used successfully as auditing algorithms, and we exploit this in the development of our algorithmic results and their experimental evaluation.

We make the following mild assumption on the class of group indicators $\mathcal{G}$, to aid in our reductions. It is satisfied by most natural classes of functions, but is in any case essentially without loss of generality (since learning negated functions can be simulated by learning the original function class on a dataset with flipped class labels).

We assume the set of group indicators $\mathcal{G}$ satisfies closure under negation: for any $g\in\mathcal{G}$, we also have $\neg g\in\mathcal{G}$.

Recalling that $X=(x,x^{\prime})$ and the following notions will be useful for describing our results:

$\alpha_{SP}(g,\mathcal{P})=\Pr_{\mathcal{P}}[g(x)=1]$ and $\alpha_{FP}(g,\mathcal{P})=\Pr_{\mathcal{P}}[g(x)=1,y=0]$.

$P^{D}$: the marginal distribution on $(x,D(X))$.

$P_{y=0}^{D}$: the conditional distribution on $(x,D(X))$, conditioned on $y=0$.

We give our reduction first for SP subgroup fairness. The reduction for FP subgroup fairness will follow as a corollary, since auditing for FP subgroup fairness can be viewed as auditing for statistical parity fairness on the subset of the data restricted to $y=0$.

Fix any distribution $\mathcal{P}$, and any set of group indicators $\mathcal{G}$. Then for any $\gamma,\varepsilon>0$, the following relationships hold:

We will prove Theorem 3.2 in two steps. First, we show that any unfair certificate $f$ for $D$ has non-trivial error for predicting the decision made by $D$ from the sensitive attributes.

In the first case, we know $\Pr[D(X)=1\mid f(x)=0]<b$, and so $\Pr[D(X)=0\mid f(x)=0]>1-b$. It follows that

In the second case, we have $\Pr[D(X)=0\mid f(x)=1]=(1-b)+\beta$ and $\Pr[D(X)=1\mid f(x)=0]>b$. We can then bound

In both cases, we have $(1-2b)\geq 0$ by our assumption on the base rate. Since $\alpha\in$, we know

In the next step, we show that if there exists any function $f$ that accurately predicts the decisions made by the algorithm $D$, then either $f$ or $\neg f$ can serve as an unfairness certificate for $D$.

Suppose that $\left(\Pr[D(X)=1\mid f(x)=1]-b\right)\Pr[f(x)=1]\geq\gamma/2$, then our claim holds with $g=f$. Suppose not, then we must have

Note that by our assumption $b\geq(1-b)$. This means

which implies that our claim holds with $g=\neg f$. ∎

In the reverse direction, consider the auditing problem on the classifier $D$. We can treat each pair $(x,D(X))$ as a labelled example and learn a hypothesis in $\mathcal{G}$ that approximates the decisions made by $D$. Suppose that $D$ is $\gamma$-unfair. Then by Lemma 3.3, we know that there exists some $g\in\mathcal{G}$ such that $\Pr[D(X)=g(x)]\geq 1/2+\gamma$. Therefore, the weak agnostic learning algorithm from the hypothesis of the theorem will return some $g^{\prime}$ with $\Pr[D(X)=g^{\prime}(x)]\geq 1/2+(\gamma-\varepsilon)$. By Lemma 3.4, we know $g^{\prime}$ or $\neg g^{\prime}$ is a $(\gamma-\varepsilon)/2$-unfair certificate for $D$. ∎

2 False Positive Fairness

A corollary of the above reduction is an analogous equivalence between auditing for FP subgroup fairness and agnostic learning. This is because a FP fairness constraint can be viewed as a statistical parity fairness constraint on the subset of the data such that $y=0$. Therefore, Theorem 3.2 implies the following:

Fix any distribution $\mathcal{P}$, and any set of group indicators $\mathcal{G}$. The following two relationships hold:

3 Worst-Case Intractability of Auditing

While we shall see in subsequent sections that the equivalence given above has positive algorithmic and experimental consequences, from a purely theoretical perspective the reduction of agnostic learning to auditing has strong negative worst-case implications. More precisely, we can import a long sequence of formal intractability results for agnostic learning to obtain:

Under standard complexity-theoretic intractability assumptions, for $\mathcal{G}$ the classes of conjunctions of boolean attributes, linear threshold functions, or bounded-degree polynomial threshold functions, there exist distributions $P$ such that the auditing problem cannot be solved in polynomial time, for either statistical parity or false positive fairness.

The proof of this theorem follows from Theorem 3.2, Corollary 3.5, and the following negative results from the learning theory literature. Feldman et al. (2012) show a strong negative result for weak agnostic learning for conjunctions: given a distribution on labeled examples from the hypercube such that there exists a monomial (or conjunction) consistent with $(1-\varepsilon)$-fraction of the examples, it is NP-hard to find a halfspace that is correct on $(1/2+\varepsilon)$-fraction of the examples, for arbitrary constant $\varepsilon>0$. Diakonikolas et al. (2011) show that under the Unique Games Conjecture, no polynomial-time algorithm can find a degree-$d$ polynomial threshold function (PTF) that is consistent with $(1/2+\varepsilon)$ fraction of a given set of labeled examples, even if there exists a degree-$d$ PTF that is consistent with a $(1-\varepsilon)$ fraction of the examples. Diakonikolas et al. (2011) also show that it is NP-Hard to find a degree-2 PTF that is consistent with a $(1/2+\varepsilon)$ fraction of a given set of labeled examples, even if there exists a halfspace (degree-1 PTF) that is consistent with a $(1-\varepsilon)$ fraction of the examples.

While Theorem 3.6 shows that certain natural subgroup classes $\mathcal{G}$ yield intractable auditing problems in the worst case, in the rest of the paper we demonstrate that effective heuristics for this problem on specific (non-worst case) distributions can be used to derive an effective and practical learning algorithm for subgroup fairness.

A Learning Algorithm Subject to Fairness Constraints 𝒢𝒢\mathcal{G}

In this section, we present an algorithm for training a (randomized) classifier that satisfies false-positive subgroup fairness simultaneously for all protected subgroups specified by a family of group indicator functions $\mathcal{G}$. All of our techniques also apply to a statistical parity or false negative rate constraint.

Let $S$ denote a set of $n$ labeled examples $\{z_{i}=(x_{i},x^{\prime}_{i}),y_{i})\}_{i=1}^{n}$, and let $\mathcal{P}$ denote the empirical distribution over this set of examples. Let $\mathcal{H}$ be a hypothesis class defined over both the protected and unprotected attributes, and let $\mathcal{G}$ be a collection of group indicators over the protected attributes. We assume that $\mathcal{H}$ contains a constant classifier (which implies that there is at least one fair classifier to be found, for any distribution).

Our goal will be to find the distribution over classifiers from $\mathcal{H}$ that minimizes classification error subject to the fairness constraint over $\mathcal{G}$. We will design an iterative algorithm that, when given access to a CSC oracle, computes an optimal randomized classifier in polynomial time.

Let $D$ denote a probability distribution over $\mathcal{H}$. Consider the following Fair ERM (Empirical Risk Minimization) problem:

where $err(h,\mathcal{P})=\Pr_{\mathcal{P}}[h(x,x^{\prime})\neq y]$, and the quantities $\alpha_{FP}$ and $\beta_{FP}$ are defined in Definition 2.3. We will write $\operatorname{OPT}$ to denote the objective value at the optimum for the Fair ERM problem, that is the minimum error achieved by a $\gamma$-fair distribution over the class $\mathcal{H}$.

Observe that the optimization is feasible for any distribution $\mathcal{P}$: the constant classifiers that labels all points 1 or 0 satisfy all subgroup fairness constraints. At the moment, the number of decision variables and constraints may be infinite (if $\mathcal{H}$ and $\mathcal{G}$ are infinite hypothesis classes), but we will address this momentarily.

Our main theoretical result is an computationally efficient oracle-based algorithm for solving the Fair ERM problem.

Step 1: Fair ERM as LP. First, we rewrite the Fair ERM problem as a linear program with finitely many decision variables and constraints even when $\mathcal{H}$ and $\mathcal{G}$ are infinite. To do this, we take advantage of the fact that Sauer’s Lemma lets us bound the number of labellings that any hypothesis class $\mathcal{H}$ of bounded VC dimension can induce on any fixed dataset. The LP has one variable for each of these possible labellings, rather than one variable for each hypothesis. Moreover, again by Sauer’s Lemma, we have one constraint for each of the finitely many possible subgroups induced by $\mathcal{G}$ on the fixed dataset, rather than one for each of the (possibly infinitely many) subgroups definable over arbitrary datasets. This step is important — it will guarantee that strong duality holds.

Step 2: Formulation as Game. We then derive the partial Lagrangian of the LP, and note that computing an approximately optimal solution to this LP is equivalent to finding an approximate minmax solution for a corresponding zero-sum game, in which the payoff function $U$ is the value of the Lagrangian. The pure strategies of the primal or “Learner” player correspond to classifiers $h\in\mathcal{H}$, and the pure strategies of the dual or “Auditor” player correspond to subgroups $g\in\mathcal{G}$. Intuitively, the Learner is trying to minimize the sum of the prediction error and a fairness penalty term (given by the Lagrangian), and the Auditor is trying to penalize the fairness violation of the Learner by first identifying the subgroup with the greatest fairness violation and putting all the weight on the dual variable corresponding to this subgroup. In order to reason about convergence, we restrict the set of dual variables to lie in a bounded set: $C$ times the probability simplex. $C$ is a parameter that we have to set in the proof of our theorem to give the best theoretical guarantees — but it is also a parameter that we will vary in the experimental section.

Step 3: Best Responses as CSC. We observe that given a mixed strategy for the Auditor, the best response problem of the Learner corresponds to a CSC problem. Similarly, given a mixed strategy for the Learner, the best response problem of the Auditor corresponds to an auditing problem (which can be represented as a CSC problem). Hence, if we have oracles for solving CSC problems, we can compute best responses for both players, in response to arbitrary mixed strategies of their opponents.

Step 4: FTPL for No-Regret. Finally, we show that the ability to compute best responses for each player is sufficient to implement dynamics known to converge quickly to equilibrium in zero-sum games. Our algorithm has the Learner play Follow the Perturbed Leader (FTPL) Kalai and Vempala (2005), which is a no-regret algorithm, against an Auditor who at every round best responds to the learner’s mixed strategy. By the seminal result of Freund and Schapire (1996), the average plays of both players converge to an approximate equilibrium. In order to implement this in polynomial time, we need to represent the loss of the learner as a low-dimensional linear optimization problem. To do so, we first define an appropriately translated CSC problem for any mixed strategy $\lambda$ by the Auditor, and cast it as a linear optimization problem.

1 Rewriting the Fair ERM Problem

To rewrite the Fair ERM problem, we note that even though both $\mathcal{G}$ and $\mathcal{H}$ can be infinite sets, the sets of possible labellings on the data set $S$ induced by these classes are finite. More formally, we will write $\mathcal{G}(S)$ and $\mathcal{H}(S)$ to denote the set of all labellings on $S$ that are induced by $\mathcal{G}$ and $\mathcal{H}$ respectively, that is

We can bound the cardinalities of $\mathcal{G}(S)$ and $\mathcal{H}(S)$ using Sauer’s Lemma.

Given this observation, we can then consider an equivalent optimization problem where the distribution $D$ is over the set of labellings in $\mathcal{H}(S)$, and the set of subgroups are defined by the labellings in $\mathcal{G}(S)$. We will view each $g$ in $\mathcal{G}(S)$ as a Boolean function.

To simplify notations, we will define the following “fairness violation” functions for any $g\in\mathcal{G}$ and any $h\in\mathcal{H}$:

Moreover, for any distribution $D$ over $\mathcal{H}$, for any sign $\bullet\in\{+,-\}$

For any $g\in\mathcal{G}$, $h\in\mathcal{H}$, and any $\nu>0$,

Thus, we will focus on the following equivalent optimization problem.

For each pair of constraints (7) and (8), corresponding to a group $g\in\mathcal{G}(S)$, we introduce a pair of dual variables $\lambda_{g}^{+}$ and $\lambda_{g}^{-}$. The partial Lagrangian of the linear program is the following:

By Sion’s minmax theorem (Sion, 1958), we have

where $\operatorname{OPT}$ denotes the optimal objective value in the fair ERM problem. Similarly, the distribution $\arg\min_{D}\,\max_{\lambda}\mathcal{L}(D,\lambda)$ corresponds to an optimal feasible solution to the fair ERM linear program. Thus, finding an optimal solution for the fair ERM problem reduces to computing a minmax solution for the Lagrangian. Our algorithms will both compute such a minmax solution by iteratively optimizing over both the primal variables $D$ and dual variables $\lambda$. In order to guarantee convergence in our optimization, we will restrict the dual space to the following bounded set:

where $C$ will be a parameter of our algorithm. Since $\Lambda$ is a compact and convex set, the minmax condition continues to hold (Sion, 1958):

Let $(\hat{D},\hat{\lambda})$ be a $\nu$-approximate minmax solution to the $\Lambda$-bounded Lagrangian problem in the sense that

Then $err(\hat{D},\mathcal{P})\leq\operatorname{OPT}+2\nu$ and for any $g\in\mathcal{G}(S)$,

2 Zero-Sum Game Formulation

To compute an approximate minmax solution, we will first view Equation 9 as the following two player zero-sum matrix game. The Learner (or the minimization player) has pure strategies corresponding to $\mathcal{H}$, and the Auditor (or the maximization player) has pure strategies corresponding to the set of vertices $\Lambda_{\text{pure}}$ in $\Lambda$ — more precisely, each vertex or pure strategy either is the all zero vector or consists of a choice of a $g\in\mathcal{G}(S)$, along with the sign $+$ or $-$ that the corresponding $g$-fairness constraint will have in the Lagrangian. More formally, we write

Even though the number of pure strategies scales linearly with $|\mathcal{G}(S)|$, our algorithm will never need to actually represent such vectors explicitly. Note that any vector in $\Lambda$ can be written as a convex combination of the maximization player’s pure strategies, or in other words: as a mixed strategy for the Auditor. For any pair of actions $(h,\lambda)\in\mathcal{H}\times\Lambda_{\text{pure}}$, the payoff is defined as

Let $D\in\Delta_{\mathcal{H}(S)}$ and $\lambda\in\Lambda$ such that $(p,\lambda)$ is a $\nu$-approximate minmax equilibrium in the zero-sum game defined above. Then $(p,\lambda)$ is also a $\nu$-approximate minmax solution for Equation 9.

Our problem reduces to finding an approximate equilibrium for this game. A key step in our solution is the ability to compute best responses for both players in the game, which we now show can be solved by the cost-sensitive classication (CSC) oracles.

Fix any mixed strategy (dual solution) $\lambda\in\Lambda$ of the Auditor. The Learner’s best response is given by:

Note that it suffices for the Learner to optimize over deterministic classifiers $h\in\mathcal{H}$, rather than distributions over classifiers. This is because the Learner is solving a linear optimization problem over the simplex, and so always has an optimal solution at a vertex (i.e. a single classifier $h\in\mathcal{H}$). We can reduce this problem to one that can be solved with a single call to a CSC oracle. In particular, we can assign costs to each example $(X_{i},y_{i})$ as follows:

if $y_{i}=1$, then $c_{i}^{0}=0$ and $c_{i}^{1}=-\frac{1}{n}$;

Auditor’s best response as CSC.

Fix any mixed strategy (primal solution) $p\in\Delta_{\mathcal{H}(S)}$ of the Learner. The Auditor’s best response is given by:

Fix any $\overline{D}\in\Delta_{\mathcal{H}(S)}$ such that that $\max_{g\in\mathcal{G}(S)}\{\Phi_{+}(\overline{D},g),\Phi_{-}(\overline{D},g)\}>0$. Let $\lambda^{\prime}\in\Lambda$ be vector with one non-zero coordinate $(\lambda^{\prime})_{g^{\prime}}^{\bullet^{\prime}}=C$, where

Then $\mathcal{L}(\overline{D},\lambda^{\prime})\geq\max_{\lambda\in\Lambda}\mathcal{L}(\overline{D},\lambda)$.

if $y_{i}=1$, then $c_{i}^{0}=0$ and $c_{i}^{1}=0$;

3 Solving the Game with No-Regret Dynamics

To compute an approximate equilibrium of the zero-sum game, we will simulate the following no-regret dynamics between the Learner and the Auditor over rounds: over each of the $T$ rounds, the Learner plays a distribution over the hypothesis class according to a no-regret learning algorithm (Follow the Perturbed Leader), and the Auditor plays an approximate best response against the Learner’s distribution for that round. By the result of Freund and Schapire (1996), the average plays of both players over time converge to an approximate equilibrium of the game, as long as the Learner has low regret.

Let $D^{1},D^{2},\ldots,D^{T}\in\Delta_{\mathcal{H}(S)}$ be a sequence of distributions played by the Learner, and let $\lambda^{1},\lambda^{2},\ldots,\lambda^{T}\in\Lambda_{\textrm{pure}}$ be the Auditor’s sequence of approximate best responses against these distributions respectively. Let $\overline{D}=\frac{1}{T}\sum_{t=1}^{T}D^{t}$ and $\overline{\lambda}=\frac{1}{T}\sum_{t=1}^{T}\lambda^{t}$ be the two players’ empirical distributions over their strategies. Suppose that the regret of the Learner satisfies

Then $(\overline{D},\overline{\lambda})$ is an $(\gamma_{L}+\gamma_{A})$-approximate minimax equilibrium of the game.

To run the FTPL algorithm, the Learner will optimize a “perturbed” version of the problem above. In particular, the Learner will play a distribution $D^{t}$ over the hypothesis class $\mathcal{H}(S)$ that is implicitely defined by the following sampling operation. To sample a hypothesis $h$ from $D^{t}$, the learner solves the following randomized optimization problem:

where $\eta$ is a parameter and $\xi$ is a noise vector drawn from the uniform distribution over $^{n}$. Note that while it is intractable to explicitly represent the distribution $D^{t}$ (which has support size scaling with $|\mathcal{H}(S)|$), we can sample from $D^{t}$ efficiently given access to a cost-sensitive classification oracle for $\mathcal{H}$. By instantiating the standard regret bound of FTPL for online linear optimization (Theorem 2.9), we get the following regret bound for the Learner.

Let $T$ be the time horizon for the no-regret dynamics. Let $D^{1},\ldots,D^{T}$ be the sequence of distributions maintained by the Learner’s FTPL algorithm with $\eta=\frac{n}{(1+C)}\sqrt{\frac{1}{\sqrt{n}T}}$, and $\lambda^{1},\ldots,\lambda^{T}$ be the sequence of plays by the Auditor. Then

Now we consider how the Auditor (approximately) best responds to the distribution $D^{t}$. The main obstacle is that we do not have an explicit representation for $D^{t}$. Thus, our first step is to approximate $D^{t}$ with an explicitly represented sparse distribution $\hat{D}^{t}$. We do that by drawing $m$ i.i.d. samples from $D^{t}$, and taking the empirical distribution $\hat{D}^{t}$ over the sample. The Auditor will best respond to this empirical distribution $\hat{D}^{t}$. To show that any best response to $\hat{D}^{t}$ is also an approximate best response to $D^{t}$, we will rely on the following uniform convergence lemma, which bounds the difference in expected payoff for any strategy of the auditor, when played against $D^{t}$ as compared to $\hat{D}^{t}$.

Fix any $\xi,\delta\in(0,1)$ and any distribution $D$ over $\mathcal{H}(S)$. Let $h^{1},\ldots,h^{m}$ be $m$ i.i.d. draws from $p$, and $\hat{D}$ be the empirical distribution over the realized sample. Then with probability at least $1-\delta$ over the random draws of $h^{j}$’s, the following holds,

Using Lemma 4.11, we can derive a regret bound for the Auditor in the no-regret dynamics.

Let $T$ be the time horizon for the no-regret dynamics. Let $D^{1},\ldots,D^{T}$ be the sequence of distributions maintained by the Learner’s FTPL algorithm. For each $D^{t}$, let $\hat{D}^{t}$ be the empirical distribution over $m$ i.i.d. draws from $D^{t}$. Let $\lambda^{1},\ldots,\lambda^{T}$ be the Auditor’s best responses against $\hat{D}^{1},\ldots,\hat{D}^{T}$. Then with probability $1-\delta$,

Finally, let $\overline{D}$ and $\overline{\lambda}$ be the average of the strategies played by the two players over the course of the dynamics. Note that $\overline{D}$ is an average of many distributions with large support, and so $\overline{D}$ itself has support size that is too large to represent explicitely. Thus, we will again approximate $\overline{D}$ with a sparse distribution $\hat{D}$ estimated from a sample drawn from $\overline{D}$. Note that we can efficiently sample from $\overline{D}$ given access to a CSC oracle. To sample, we first uniformly randomly select a round $t\in[T]$, and then use the CSC oracle to solve the sampling problem defined in (14), with the noise random variable $\xi$ freshly sampled from its distribution. The full algorithm is described in Algorithm 2 and we present the proof for Theorem 4.2 below.

By Theorem 4.5, it suffices to show that with probability at least $1-\delta$, $(\hat{D},\overline{\lambda})$ is a $\nu$-approximate equilibrium in the zero-sum game. As a first step, we will rely on Theorem 4.9 to show that $(\overline{D},\overline{\lambda})$ forms an approximate equilibrium.

By Lemma 4.10, the regret of the sequence $D^{1},\ldots,D^{T}$ is bounded by:

By Lemma 4.12, with probability $1-\delta/2$, we have

We will condition on this upper-bound event on $\gamma_{A}$ for the rest of this proof, which is the case except with probability $\delta/2$. By Theorem 4.9, we know that the average plays $(\overline{D},\overline{\lambda})$ form an $(\gamma_{L}+\gamma_{A})$-approximate equilibrium.

Finally, we need to bound the additional error for outputting the sparse approximation $\hat{D}$ instead of $\overline{D}$. We can directly apply Lemma 4.11, which implies that except with probability $\delta/2$, the pair $(\hat{D},\overline{\lambda})$ form a $R$-approximate equilibrium, with

Note that $R\leq\nu$ as long as we have $C=1/\nu$,

Experimental Evaluation

We now describe an experimental evaluation of our proposed algorithmic framework on a dataset in which fairness is a concern, due to the preponderance of racial and other sensitive features. For far more detailed experiments on four real datasets investigating the convergence properties of our algorithm, evaluating its accuracy vs. fairness tradeoffs, and comparing our approach to the recent algorithm of Agarwal et al. (2017), we direct the reader to Kearns et al. (2018). Python code and an illustrative Jupyter notebook are provided here (https://github.com/algowatchpenn/GerryFair).

While the no-regret-based algorithm described in the last section enjoys provably polynomial time convergence, for the experiments we instead implemented a simpler yet effective algorithm based on Fictitious Play dynamics. We first describe and discuss this modified algorithm.

Like the algorithm given in the last section, the algorithm we implemented works by simulating a game dynamic that converges to Nash equilibrium in the zero-sum game that we derived, corresponding to the Fair ERM problem. Rather than using a no-regret dynamic, we instead use a simple iterative procedure known as Fictitious Play (Brown, 1949). Fictitious Play dynamics has the benefit of being more practical to implement: at each round, both players simply need to compute a single best response to the empirical play of their opponents, and this optimization requires only a single call to a CSC oracle. In contrast, the FTPL dynamic we gave in the previous section requires making many calls to a CSC oracle per round — a computationally expensive process — in order to find a sparse approximation to the Learner’s mixed strategy at that round. Fictitious Play also has the benefit of being deterministic, unlike the randomized sampling required in the FTPL no-regret dynamic, thus eliminating a source of experimental variance.

The disadvantage is that Fictitious Play is only known to converge to equilibrium in the limit Robinson (1951), rather than in a polynomial number of rounds (though it is conjectured to converge quickly under rather general circumstances; see Daskalakis and Pan (2014) for a recent discussion). Nevertheless, this is the algorithm that we use in our experiments — and as we will show, it performs well on real data, despite the fact that it has weaker theoretical guarantees compared to the algorithm we presented in the last section.

Fictitious play proceeds in rounds, and in every round each player chooses a best response to his opponent’s empirical history of play across previous rounds, by treating it as the mixed strategy that randomizes uniformly over the empirical history. Pseudocode for the implemented algorithm is given below.

2 Description of Data

The dataset we use for our experimental valuation is known as the “Communities and Crime” (C&C) dataset, available at the UC Irvine Data Repositoryhttp://archive.ics.uci.edu/ml/datasets/Communities+and+Crime. Each record in this dataset describes the aggregate demographic properties of a different U.S. community; the data combines socio-economic data from the 1990 US Census, law enforcement data from the 1990 US LEMAS survey, and crime data from the 1995 FBI UCR. The total number of records is 1994, and the number of features is 122. The variable to be predicted is the rate of violent crime in the community.

While there are larger and more recent datasets in which subgroup fairness is a potential concern, there are properties of the C&C dataset that make it particularly appealing for the initial experimental evaluation of our proposed algorithm. Foremost among these is the relatively high number of sensitive or protected attributes, and the fact that they are real-valued (since they represent aggregates in a community rather than specific individuals). This means there is a very large number of protected sub-groups that can be defined over them. There are distinct continuous features measuring the percentage or per-capita representation of multiple racial groups (including white, black, Hispanic, and Asian) in the community, each of which can vary independently of the others. Similarly, there are continuous features measuring the average per capita incomes of different racial groups in the community, as well as features measuring the percentage of each community’s police force that falls in each of the racial groups. Thus restricting to features capturing race statistics and a couple of related ones (such as the percentage of residents who do not speak English well), we obtain an 18-dimensional space of real-valued protected attributes. We note that the C&C dataset has numerous other features that arguably could or should be protected as well (such as gender features), which would raise the dimensionality of the protected subgroups even further. Ongoing experiments on other datasets where fairness is a concern will be reported on in a forthcoming experimental paper.

We convert the real-valued rate of violent crime in each community to a binary label indicating whether the community is in the 70th percentile of that value, indicating that it is a relatively high-crime community. Thus the strawman baseline that always predicts 0 (lower crime) has error approximately 30% or 0.3 on this classification problem. We chose the 70th percentile since it seems most natural to predict the highest crime rates.

As in the theoretical sections of the paper, our main interest and emphasis is on the effectiveness of our proposed algorithm FairFictPlay on a given dataset, including:

Whether the algorithm in fact converges, and does so in a feasible amount of computation. Recall that formal convergence is only guaranteed under the assumption of oracles that do not exist in practice, and even then is only guaranteed asymptotically.

Whether the classifier learned by the algorithm has nontrivial accuracy, as well as strong subgroup fairness properties.

Whether the algorithm and dataset permits nontrivial tuning of the trade-off between accuracy and subgroup fairness.

As discussed in Section 2.1, we note that all of these issues can be investigated entirely in-sample, without concern for generalization performance. Thus for simplicity, despite the fact that our algorithm enjoys all the usual generalization properties depending on the VC dimension of the Learner’s hypothesis space and the Auditor’s subgroup space (see Theorems 2.12 and 2.11), we report all results here on the full C&C dataset of 1994 points, treating it as the true distribution of interest.

3 Algorithm Implementation

The main details in the implementation of FairFictPlay are the identification of the model classes for Learner and Auditor, the implementation of the cost sensitive classification oracle and auditing oracle, and the identification of the protected features for Auditor. For our experiments, at each round Learner chooses a linear threshold function over all 122 features. We implement the cost sensitive classification oracle via a two stage regression procedure. In particular, the inputs to the cost sensitive classification oracle are cost vectors $c_{0},c_{1}$, where the $i^{th}$ element of $c_{k}$ is the cost of predicting $k$ on datapoint $i$. We train two linear regression models $r_{0},r_{1}$ to predict $c_{0}$ and $c_{1}$ respectively, using all $122$ features. Given a new point $x$, we predict the cost of classifying $x$ as and $1$ using our regression models: these predictions are $r_{0}(x)$ and $r_{1}(x)$ respectively. Finally we output the prediction $\hat{y}$ corresponding to lower predicted cost: $\hat{y}=\text{argmin}_{i\in\{0,1\}}r_{i}(x)$.

Auditor’s model class consists of all linear threshold functions over just the 18 aforementioned protected race-based attributes. As per the algorithm, at each iteration $t$ Auditor attempts to find a subgroup on which the false positive rate is substantially different than the base rate, given the Learner’s randomized classifier so far. We implement the auditing oracle by treating it as a weighted regression problem in which the goal is find a linear function (which will be taken to define the subgroup) that on the negative examples, can predict the Learner’s probabilistic classification on each point. We use the same regression subroutine as Learner does, except that Auditor only has access to the $18$ sensitive features, rather than all $122$.

Recall that in addition to the choices of protected attributes and model classes for Learner and Auditor, FairFictPlay has a parameter $C$, which is a bound on the norm of the dual variables for Auditor (the dual player). While the theory does not provide an explicit bound or guide for choosing $C$, it needs to be large enough to permit the dual player to force the minmax value of the game. For our experiments we chose $C=10$, which despite being a relatively small value seems to suffice for (approximate) convergence.

The other and more meaningful parameter of the algorithm is the bound $\gamma$ in the Fair ERM optimization problem implemented by the game, which controls the amount of unfairness permitted. If on a given round the subgroup disparity found by the Auditor is greater than $\gamma$, the Learner must react by adding a fairness penalty for this subgroup to its objective function; if it is smaller than $\gamma$, the Learner can ignore it and continue to optimize its previous objective function. Ideally, and as we shall see, varying $\gamma$ allows us to trace out a menu of trade-offs between accuracy and fairness.

4 Results

Particularly in light of the gaps between the idealized theory and the actual implementation, the most basic questions about FairFictPlay are whether it converges at all, and if so, whether it converges to “interesting” models — that is, models with both nontrivial classification error (much better than the 30% or 0.3 baserate), and nontrivial subgroup fairness (much better than ignoring fairness altogether). We shall see that at least for the C&C dataset, the answers to these questions is strongly affirmative.

We begin by examining the evolution of the error and unfairness of Learner’s model. In the left panel of Figure 1 we show the error of the model found by Learner vs. iteration for values of $\gamma$ ranging from 0 to 0.029. Several comments are in order.

First, after an initial period in which there is a fair amount of oscillatory behavior, by 6000 iterations most of the curves have largely flattened out, and by 8,000 iterations it appears most but not all have reached approximate convergence. Second, while the top-to-bottom ordering of these error curves is approximately aligned with decreasing $\gamma$ — so larger $\gamma$ generally results in lower error, as expected — there are many violations of this for small $t$, and even a few at large $t$. Third, and as we will examine more closely shortly, the converged values at large $t$ do indeed exhibit a range of errors.

In the right panel of Figure 1, we show the corresponding unfairness $\gamma_{t}$ of the subgroup found by the Auditor at each iteration $t$ for the same runs and values of the parameter $\gamma$ (indicated by horizontal dashed lines), with the same color-coding as for the left panel. Now the ordering is generally reversed — larger values of $\gamma$ generally lead to higher $\gamma_{t}$ curves, since the fairness constraint on the Learner is weaker. We again see a great deal of early oscillatory behavior, with most $\gamma_{t}$ curves then eventually settling at or near their corresponding input $\gamma$ value, as Learner and Auditor engage in a back-and-forth struggle for lower error for Learner and $\gamma$-subgroup fairness for Auditor.

For any choice of the parameter $\gamma$, and each iteration $t$, the two panels of Figure 1 yield a pair of realized values $\langle\varepsilon_{t},\gamma_{t}\rangle$ from the experiment, corresponding to a Learner model whose error is $\varepsilon_{t}$, and for which the worst subgroup the Auditor was able to find had unfairness $\gamma_{t}$. The set of all $\langle\varepsilon_{t},\gamma_{t}\rangle$ pairs across all runs or $\gamma$ values thus represents the different trade-offs between error and unfairness found by our algorithm on the data. Most of these pairs are of course Pareto-dominated by other pairs, so we are primarily interested in the undominated frontier.

In the left panel of Figure 2, for each value of $\gamma$ we show the Pareto-optimal pairs, color-coded for the value of $\gamma$. Each value of $\gamma$ yields a set or cloud of undominated pairs that are usually fairly close to each other, and as expected, as $\gamma$ is increased, these clouds generally move leftwards and upwards (lower error and higher unfairness).

We anticipate that the practical use of our algorithm would, as we have done, explore many values of $\gamma$ and then pick a model corresponding to a point on the aggregated Pareto frontier across all $\gamma$, which represents the collection of all undominated models and the overall error-unfairness trade-off. This aggregate frontier is shown in the right panel of Figure 2, and shows a relatively smooth menu of options, ranging from error about 0.21 and no unfairness at one extreme, to error about 0.12 and unfairness 0.025 at the other, and an appealing assortment of intermediate trade-offs. Of course, in a real application the selection of a particular point on the frontier should be made in a domain-specific manner by the stakeholders or policymakers in question.

We thank Alekh Agarwal, Richard Berk, Miro Dudík, Akshay Krishnamurthy, John Langford, Greg Ridgeway and Greg Yang for helpful discussions and suggestions.

References

Appendix A Chernoff-Hoeffding Bound

We use the following concentration inequality.

Appendix B Generalization Bounds

We give a proof of Theorem 2.11. The proof of Theorem 2.12 is identical, as false positive rates are just positive classification rates on the subset of the data for which $y=0$.

Given a set of classifiers $\mathcal{H}$ and protected groups $\mathcal{G}$, define the following function class:

We can relate the VC-dimension of $\mathcal{F}_{\mathcal{H},\mathcal{G}}$ to the VC-dimension of $\mathcal{H}$ and $\mathcal{G}$:

This bound, together with a standard VC-Dimension based uniform convergence theorem (see e.g. Kearns and Vazirani ) implies that with probability $1-\delta$, for every $f_{h,g}\in\mathcal{F}_{\mathcal{H},\mathcal{G}}$:

Note that the left hand side of the above inequality can be written as:

Appendix C Missing Proofs in Section 4

Let $D^{*}$ be the optimal feasible solution for our constrained optimization problem. Since $D^{*}$ is feasible, we know that $\mathcal{L}(D^{*},\hat{\lambda})\leq err(D^{*},\mathcal{P})$.

We will first focus on the case where $\hat{D}$ is not a feasible solution, that is

Note that $\mathcal{L}(D^{*},\hat{\lambda})\leq err(D^{*},\mathcal{P})$, and so

Note that $C\,\Phi_{\hat{\bullet}}(\hat{D},\hat{g})\geq 0$, so we must have $err(\hat{D},\mathcal{P})\leq err(D^{*},\mathcal{P})+2\nu=\operatorname{OPT}+2\nu$. Furthermore, since $err(\hat{D},\mathcal{P}),err(D^{*},\mathcal{P})\in$, we know

which implies that maximum constraint violation satisfies $\Phi_{\hat{\bullet}}(\hat{D},\hat{g})\leq(1+2\nu)/C$. By applying 4.4, we get

Now let us consider the case in which $\hat{D}$ is a feasible solution for the optimization problem. Then it follows that there is no constraint violation by $\hat{D}$ and $\max_{\lambda}\mathcal{L}(\hat{D},\lambda)=err(\hat{D},\mathcal{P})$, and so

Therefore, the stated bounds hold for both cases. ∎

Also note that the dimension of the optimization is the size of the dataset $n$. This means if we set $\eta=\frac{n}{(1+C)}\sqrt{\frac{1}{\sqrt{n}T}}$, the regret of the learner will then be bounded by $2n^{1/4}{(1+C)}\sqrt{T}$. ∎

Recall that for any distribution $D^{\prime}$ over $\mathcal{H}(S)$ the expected payoff function is defined as

The first part follows directly from a simple application of the Chernoff-Hoeffding bound (Theorem A.1): with probability $(1-\delta/2)$, $A\leq\xi/2$, as long as $m\geq 2\ln(4/\delta)/\xi^{2}$.

To bound the second part, we first note that by Hölder’s inequality, we have

Since for all $\lambda\in\Lambda$ we have $\|\lambda\|_{1}\leq C$, it suffices to show that with probability $1-\delta/2$, $|\Phi_{\bullet}(D,g)-\Phi_{\bullet}(\hat{D},g)|\leq\xi/(2C)$ holds for all $\bullet\in\{-,+\}$ and $g\in\mathcal{G}(S)$. Note that

We can rewrite the absolute value of first term:

where the last inequality follows from $\Pr[g(x)=1\mid y=0]\leq 1$.

In the following, we will let $\delta_{0}=2\exp\left(-\frac{\xi^{2}m}{8C^{2}}\right)$. Similarly, we also have for each $g\in\mathcal{G}(S)$,

By taking the union bound over (17) and (18) over all choices of $g\in\mathcal{G}(S)$, we have with probability at least $(1-\delta_{0}(1+|\mathcal{G}(S)|))$,

Note that by Sauer’s lemma (Lemma 4.3), $|\mathcal{G}(S)|\leq O\left(n^{d_{2}}\right)$. Thus, there exists an absolute constant $c_{0}$ such that $m\geq c_{0}\frac{C^{2}\left(\ln(1/\delta)+d_{2}\ln(n)\right)}{\xi^{2}}$ implies that failure probability above $\delta_{0}(1+|\mathcal{G}(S)|)\leq\delta/2$. We will assume $m$ satisifies such a bound, and so the events of (19) and (20) hold with probaility at least $(1-\delta/2)$. Then by the triangle inequality we have for all $(g,\bullet)\in\mathcal{G}(S)\times\{\pm\}$, $|\Phi_{\bullet}(D,g)-\Phi_{\bullet}(\hat{D},g)|\leq\xi/(2C)$, which implies that $B\leq\xi/2$. This completes the proof. ∎

Suppose there are two distributions $D$ and $\hat{D}$ over $\mathcal{H}(S)$ such that

By instantiating Lemma 4.11 and applying union bound across all $T$ steps, we know with probability at least $1-\delta$, the following holds for all $t\in[T]$:

Note that by C.1, the Auditor is performing a $\gamma_{A}^{t}$-approximate best response at each round $t$. Then we can bound the Auditor’s regret as follows:

It follows that with probability $1-\delta$, we have