Metric-Free Individual Fairness in Online Learning

2020·Arxiv

Abstract

Abstract

We study an online learning problem subject to the constraint of individual fairness, which requires that similar individuals are treated similarly. Unlike prior work on individual fairness, we do not assume the similarity measure among individuals is known, nor do we assume that such measure takes a certain parametric form. Instead, we leverage the existence of an auditor who detects fairness violations without enunciating the quantitative measure. In each round, the auditor examines the learner’s decisions and attempts to identify a pair of individuals that are treated unfairly by the learner. We provide a general reduction framework that reduces online classification in our model to standard online classification, which allows us to leverage existing online learning algorithms to achieve sub-linear regret and number of fairness violations. Surprisingly, in the stochastic setting where the data are drawn independently from a distribution, we are also able to establish PAC-style fairness and accuracy generalization guarantees (Rothblum and Yona [2018]), despite only having access to a very restricted form of fairness feedback. Our fairness generalization bound qualitatively matches the uniform convergence bound of Rothblum and Yona [2018], while also providing a meaningful accuracy generalization guarantee. Our results resolve an open question by Gillen et al. [2018] by showing that online learning under an unknown individual fairness constraint is possible even without assuming a strong parametric form of the underlying similarity measure.

1 Introduction

As machine learning increasingly permeates many critical aspects of society, including education, healthcare, criminal justice, and lending, there is by now a vast literature that studies how to make machine learning algorithms fair (see, e.g., Chouldechova and Roth [2018]; Podesta et al. [2014]; Corbett-Davies and Goel [2018]). Most of the work in this literature tackles the problem by taking the statistical group fairness approach that first fixes a small collection of high-level groups defined by protected attributes (e.g., race or gender) and then asks for approximate parity of some statistic of the predictor, such as positive classifi-cation rate or false positive rate, across these groups (see, e.g., Hardt et al. [2016], Chouldechova [2017], Kleinberg et al. [2017], Agarwal et al. [2018]). While notions of group fairness are easy to operationalize, this approach is aggregate in nature and does not provide fairness guarantees for finer subgroups or individuals [Dwork et al., 2012, H´ebert-Johnson et al., 2018, Kearns et al., 2018].

In contrast, the individual fairness approach aims to address this limitation by asking for explicit fairness criteria at an individual level. In particular, the compelling notion of individual fairness proposed in the seminal work of Dwork et al. [2012] requires that similar people are treated similarly. The original formulation of individual fairness assumes that the algorithm designer has access to a task-specific fairness metric that captures how similar two individuals are in the context of the specific classification task at hand. In practice, however, such a fairness metric is rarely specified, and the lack of metrics has been a major obstacle for the wide adoption of individual fairness. There has been recent work on learning the fairness metric based on different forms of human feedback. For example, Ilvento [2019] provides an algorithm for learning the metric by presenting human arbiters with queries concerning the distance between individuals, and Gillen et al. [2018] provide an online learning algorithm that can eventually learn a Mahalanobis metric based on iden-tified fairness violations. While these results are encouraging, they are still bound by several limitations. In particular, it might be difficult for humans to enunciate a precise quantitative similarity measure between individuals. Moreover, their similarity measure across individuals may not be consistent with any metric (e.g., it may not satisfy the triangle inequality) and is unlikely to be given by a simple parametric form (e.g., Mahalanobis metric function).

To tackle these issues, this paper studies metric-free online learning algorithms for individual fairness that rely on a weaker form of interactive human feedback and minimal assumptions on the similarity measure across individuals. Similar to the prior work of Gillen et al. [2018], we do not assume a pre-specified metric, but instead assume access to an auditor, who observes the learner’s decisions over a group of individuals that show up in each round and attempts to identify a fairness violation—a pair of individuals in the group that should have been treated more similarly by the learner. Since the auditor only needs to identify such unfairly treated pairs, there is no need for them to enunciate a quantitative measure – to specify the distance between the identified pairs. Moreover, we do not impose any parametric assumption on the underlying similarity measure, nor do we assume that it is actually a metric since we do not require that similarity measure to satisfy the triangle inequality. Under this model, we provide a general reduction framework that can take any online classification algorithm (without fairness constraint) as a black-box and obtain a learning algorithm that can simultaneously minimize cumulative classification loss and the number of fairness violations. Our results in particular remove many strong assumptions in Gillen et al. [2018], including their parametric assumptions on linear rewards and Mahalanobis distances, and answer several questions left open in their work. We now provide an overview of the results.

1.1 Overview of Model and Results

We study an online classification problem: over rounds t = 1, . . . , T, a learner observes a small set of k individuals1 with their feature vectors . The learner tries to predict the label of each individual with a “soft” predictor that predicts and incurs classification loss . Then an auditor investigates whether the learner has violated the individual fairness constraint on any pair of individuals within this round, that is, if there exists is an unknown distance function and denotes the auditor’s tolerance. If such a violation has occurred on any number of pairs, the auditor identifies one such pair and incurs a fairness loss of 1; otherwise, the fairness loss is 0. The learner then updates the predictive policy based on the observed labels and the received fairness feedback. Under this model, our results include:

Our reduction-based algorithm can take any no-regret online (batch) classification learner as a black-box and achieve sub-linear cumulative fairness loss and sub-linear regret on mis-classification loss compared to the most accurate policy that is fair on every round. In particular, our framework can leverage the generic exponential weights method [Freund and Schapire, 1997, Cesa-Bianchi et al., 1997, Arora et al., 2012] and also oracle-efficient methods, including variants of Follow-the-Perturbed-Leader (FTPL) (e.g., Syrgkanis et al. [2016], Suggala and Netrapalli [2019], Agarwal et al. [2019]), that further reduces online learning to standard supervised learning or optimization problems. We instantiate our framework using two online learning algorithms (exponential weights and CONTEXT-FTPL), both of which obtain a regret rate.

• Fairness and Accuracy Generalization Guarantee of the Learned Policy While our algorithmic results hold under adversarial arrivals of the individuals, in the stochastic arrivals setting we show that the uniform average policy over time is probably approximate correct and fair (PACF) [Rothblum and Yona, 2018]—that is, the policy is approximately fair on almost all random pairs drawn from the distribution and nearly matches the accuracy guarantee of the best fair policy. In particular, we show that the average policy with high probability satisfies

for some constant c > 0. In other words, we achieve non-trivial PACF uniform convergence sample complexity as Rothblum and Yona [2018], albeit a slightly worse rate.2 However, we establish our generalization guarantee through fundamentally different techniques. While their work assumes a fully specified metric and i.i.d. data, the learner in our setting can only access the similarity measure through an auditor’s limited fairness violations feedback. The main challenge we need to overcome is that the fairness feedback is inherently adaptive—that is, the auditor only provides feedback for the sequence of deployed policies, which are updated adaptively over rounds. In comparison, a fully known metric allows the learner to evaluate the fairness guarantee of all policies simultaneously. Therefore, we cannot rely on their uniform convergence result to bound the fairness generalization error, but in-

stead we leverage a probabilistic argument that relates the learner’s regret to the distributional fairness guarantee.

1.2 Related Work

Solving open problems in Gillen et al. [2018]. The most related work to ours is Gillen et al. [2018], which studies the linear contextual bandit problem subject to individual fairness constraints with respect to an unknown Mahalanobis metric. Similar to our work, they also assume an auditor who can identify fairness violations in each round and provide an online learning algorithm with sublinear regret and a bounded number of fairness violations. Our results resolve two main questions left open in their work. First, we assume a weaker auditor who is only required to identify a single fairness violation (as opposed to all of the fairness violations in their setting). Second, we remove the strong parametric assumption regarding the Mahalanobis metric and instead work with a broad class of similarity functions that need not take a metric form.

Starting with Joseph et al. [2016], there is a different line of work that studies online learning for individual fairness, but subject to a different notion called meritocratic fairness [Jabbari et al., 2017, Joseph et al., 2018, Kannan et al., 2017]. These results present algorithms that are “fair” within each round but again rely on strong realizability assumptions–their fairness guarantee depends on the assumption that the outcome variable of each individual is given by a linear function. Gupta and Kamble [2019] also studies online learning subject to individual fairness but with a known metric. They formulate a one-sided fairness constraint across time, called fairness in hindsight, and provide an algorithm with regret some distribution-dependent constant M.

Our work is related to several others that aim to enforce individual fairness without a known metric. Ilvento [2019] studies the problem of metric learning by asking human arbiters distance queries. Unlike Ilvento [2019], our algorithm does not explicitly learn the underlying similarity measure and does not require asking auditors numeric queries. The PAC-style fairness generalization bound in our work falls under the framework of probably approximately metric-fairness due to Rothblum and Yona [2018]. However, their work assumes a pre-specified fairness metric and i.i.d. data from a distribution, while we establish our generalization through a sequence of adaptive fairness violations feedback over time. Kim et al. [2018] study a group-fairness relaxation of individual fairness, which requires that similar subpopulations are treated similarly. They do not assume a pre-specified metric for their offline learning problem, but they do assume a metric oracle that returns numeric distance values on random pairs of individuals. Jung et al. [2019] study an offline learning problem with subjective individual fairness, in which the algorithm tries to elicit subjective fairness feedback from human judges by asking them questions of the form “should this pair of individuals be treated similarly or not?” Their fairness generalization takes a different form, which involves taking averages over both the individuals and human judges. We aim to provide a fairness generalization guarantee that holds for almost all individuals from the population.

Our technique of combining the loss and the constraint violation into a Lagrangian loss is very related to the technique used in the online convex optimization with long term constraints Jenatton et al. [2016], Yu and Neely [2020], Yu et al. [2017], Cao and Liu [2019], Mahdavi et al. [2012]. Similarly as in our setting, they are interested in choosing some point in each round and incur some loss chosen by the adversary. Given some collection of constraints , the goal is to simultaneously ensure the total violation of the constraints is sublinear and to achieve sublinear regret against any fixed point in hindsight that satisfies all the constraints — . However, in most of these settings, the constraints are initially known to the learner, and the algorithm requires a projection into the feasible region. This is different than our setting, where we have no knowledge of what the space of fair policies looks like, as the auditor cannot enunciate what the fairness metric is. The only exception among the works cited above is the work of Cao and Liu [2019] and Mahdavi et al. [2012]. They consider a bandit feedback setting where the constraints are not known initially and only the max violation of the constraints with respect to the chosen point is revealed in each round — i.e. . Our setting is still different in that we do not receive the amount of violation in each round but only the point’s feasibility (i.e.) and one of the violated constraints chosen arbitrarily. Furthermore, in their setting, the the point chosen in each round -dimesnional vector (i.e. ), whereas we imagine the policy chosen in each round comes from the simplex of some hypothesis class , which is often much bigger than . In that sense, our use of the Follow-The-Perturbed-Leader approach to make the overall algorithm oracle-efficient is novel.

Our techniques in establishing generalization bounds by leveraging the regret guarantees of online algorithms are closely related to classical online to batch conversion schemes (most notably Helmbold and Warmuth [1995], Cesa-Bianchi et al. [2004]). However, since our fairness violation loss function is threshold-based, and hence not linear with respect to the base classifiers over which the deployed policy is defined, we cannot apply standard analysis regarding the fairness error of the average policy (Cesa-Bianchi et al. [2004]), since, in the worst case, this error rate could be equal to the sum of the error rates of all deployed policies during the run of the online algorithm. Another classical alternative is to randomly select one of the policies in the run of the algorithm (Helmbold and Warmuth [1995]). However, in order to establish a high probability bound, this results in a rate incorporating a linear dependence on the inverse of the failure probability, which we prefer to avoid. In this regard, our generalization technique is novel in its ability to incorporate knowledge about the specifics of the fairness loss in relating the overall number of fairness violations encountered during the run of the algorithm to the probability of encountering slightly larger violations when deploying the average policy over its run.

2 Model and Preliminaries

We define the instance space to be X and its label space to be Y. Throughout this paper, we will restrict our attention to binary labels, that is Y = {0, 1}. Sometimes, we assume the existence of an underlying (but unknown) distribution to denote the hypothesis class and assume that F contains a constant hypothesis — i.e. there exists f such that f(x) = 0 (and/or 1) for all we allow a convex combination of hypotheses for the purpose of randomizing the prediction and denote the simplex of hypotheses by . For consistency, we say , which maps to Y = {0, 1}, is a hypothesis and , which is a mixture of some hypotheses and hence maps to [0, 1], a policy. For each prediction and its true label , there is an associated misclassification loss, simplicity, we overload the notation and write

Note that the loss is linear in and some mixing probability . Then, it is immediate that

2.1 Online Batch Classification

Here, we describe the vanilla online batch classification setting, as we will try to reduce the problem we are interested in to this setting. In each round t = 1, . . . , T, a learner deploys a policy . Upon seeing the deployed policy , the environment chooses a batch of k individuals, . As the environment can adversarially and adaptively choose this batch of individuals, we can think of this as the environment strategically choosing where we write for simplicity. Note that the strategy space for the environment is

The history in each round then will consist of everything observed by the learner up to, but not including, round t:

The space of such histories is denoted by . A learner then defined to be a mapping from history to a policy:

Given some loss that is calculated in each round t, the learner cannot hope to upper-bound the loss by itself over all rounds t = 1, . . . , T, due to the adversarial nature of the environment. Therefore, the learner can only hope to minimize its regret with respect to some fixed policy it could have used.

Definition 2.1. Fix the adversary’s strategy space Z. With respect to some baseline and some loss , we say learner A’s regret with respect to adaptively and adversarially chosen sequence

In this vanilla online batch classification setting, performance is measured solely using the misclassification loss:

Definition 2.2 (Misclassification Loss). The (batch) misclassification loss Err is

In other words, the goal in this setting is to come up with an learner A such that against any adaptively and adversarially chosen , we can achieve

Often, when learner A can guarantee that the regret is sublienar as above, it is said to be a no-regret learner. Examples of such no-regret learners include exponential weights [Freund and Schapire, 1997, Cesa-Bianchi et al., 1997, Arora et al., 2012] and Follow-the-Perturbed-Leader strategies Syrgkanis et al. [2016], Suggala and Netrapalli [2019].

2.2 Online Fair Batch Classification

As opposed to only attempting to minimize its misclassification regret, we also want to make sure that the deployed policies satisfy individual fairness constraints (i.e. each policy treats similar individuals similarly according to some fairness metric

Definition 2.3 (is said to be -fair on pair

We say policy -fairness violation on pair

A policy is said to be -fair on distribution

In order to find such fair policies, we rely on an auditor who can give feedback by pointing out when a pair of two similar individuals are not treated similarly according to metric d. However, unlike Gillen et al. [2018], we make no parametric assumption on the metric d nor do we require it to be a proper metric (i.e. it doesn’t need to satisfy the triangle inequality). The only requirement regarding d in our work is that it is non-negative and symmetric3. In addition to removing the parametric assumption on the metric d, we further require the auditor to output only one arbitrary pair where a fairness violation has occurred as opposed to reporting all violations.

Definition 2.4 (Auditor). An auditor , who can have its own internal state, takes in a reference set and a policy . Then, it outputs which is either null or a pair of indices from the provided reference set to denote that there is an -fairness violation on that pair. For some

If there exist multiple pairs on which there is an -violation, the auditor can choose one arbitrarily. We will elide , as we will only focus on the case where d is fixed.

Remark 2.5. We emphasize that the assumptions on the auditor here are greatly relaxed in comparison to the assumptions made in Gillen et al. [2018], which require that the auditor outputs whether the policy is 0-fair (i.e. with no slack) on all pairs exactly. Furthermore, the auditor from Gillen et al. [2018] can only handle Mahalanobis distances. In our setting, because of the internal state of the auditor, the auditor does not have to be a fixed function but rather can be adaptively changing in each round. Our argument actually never relies on the fact the distance function d stays the same throughout rounds, meaning all our results extend to the case where the distance function governing the fairness constraints is changing every round. For simplicity, we focus on the case where d is fixed.

The order in which the learner, the environment, and the auditor interact is as follows. In each round t = 1, . . . , T, a learner deploys a policy . Then, a batch of k individuals arrives. The auditor, upon inspecting , provides a fairness feedback be a pair of indices for which the deployed policy is treating unfairly or null if there does not exist any such pair. As the auditor can essentially choose its reported pair arbitrarily among all pairs on which a violation exists, we can actually fold the auditor into the environment. That is – the environment choose simultaneously, meaning the strategy space of the environment here is

Similarly as in the vanilla online batch classification setting, the history of the interaction is now described as

where and the space of such histories is then learner A is still defined to be a mapping from a history to a policy:

In addition to the misclassification loss, the learner is also has penalized for unfairness, using the unfairness loss.

Definition 2.6 (Unfairness Loss). The -fairness loss Unfair

In other words, the learner incurs misclassification loss Errand unfairness loss Unfaireach round t. Note that unlike the fairness loss defined in Gillen et al. [2018] which counts the total number of pairs with fairness violations, the fairness loss here is either 0 or 1 depending on the existence of such pair in this setting. We compare this online batch classification setting with fairness constraints to the vanilla online batch classification setting in Figure 1.

Finally, the baseline that we compete against will be all policies that are

Given some fixed trade-off slack and an auditor , our goal is to provide a learner A such that for any adversarially and adaptively chosen , regret with respect to each of misclassification and unfairness loss is sublinear against

Algorithm 1: Online Fair Batch Classification

end

Figure 1: Comparison between Online Fair Batch Classification and Online Batch Classification: each is summarized by the interaction between the learner and the environment:

where -fair, guaranteeing sublinear fairness regret is equivalent to guaranteeing the overall fairness loss is sublinear.

3 Lagrangian Regret

As we wish to achieve no-regret with respect to both the misclassification and fairness loss, it is natural to consider a hybrid loss that combines them together. In fact, we define a round-based Lagrangian loss and show that regret with respect to our Lagrangian loss also serves as an upperbound for the misclassification and the unfairness regret multipled by some parameter that balances the misclassification and unfairness losses in the Lagrangian loss.

Then, we show how to achieve no regret with respect to the Lagrangian loss by reducing the problem to an online batch classification where there is no fairness constraint. For concreteness, we show how to leverage exponential weights in order to achieve sublinear misclassification regret and fairness loss.

3.1 Lagrangian Formulation

Here we present a hybrid loss that we call Lagrangian loss that combines the misclassification loss and the fairness violation in round t.

Definition 3.1 (Lagrangian Loss). We say that the C-Lagrangian loss of

Given an auditor that is tasked with detecting any -fairness violation, we can simulate the online fair batch classification setting with an auditor by setting the pair

Now, we show that the Lagrangian regret serves as an upper bound for the sum of the -fairness loss (with some multiplicative factor that depends on ) and the misclassification loss regret with respect to

Theorem 3.2. Given an auditor , fix any sequence . Then, the following holds for any simultaneously:

Proof. Fix -fair policy . Note that for any round we have

because -fair on this pair and

Then we can show

By considering the above theorem statement with , we can always bound the misclassification regret with the Lagrangian regret:

However, note that we cannot always hope to bound the fairness loss with the Lagrangian regret because the misclassification regret may be negative. It alludes to the fact that it is not sufficient to simply come up with a way to bound the Lagrangian regret to be sublinear in T. In fact, we have to tune C according to the exact Lagrangian regret guarantee we wish to get: we want to set C to be large enough so as to give more emphasis to the fairness loss. At the same time, we cannot set it too high, as C also controls the range of the Lagrangian loss and the regret guarantees usually has a linear dependence on the range of the loss. In the next section, we will show exactly how to set C so that we can achieve no regret with respect to each of the unfairness and misclassification losses simultaneously.

4 Achieving No Regret Simultaneously

In Section 4.1, we present an efficient reduction from the setting of online batch classification with fairness constraints to that of online batch classification without constraints. This reduction to the online batch classification without the fairness constraints is not necessary, as the Lagrangian loss is already linear in the first argument, . However, we go through this reduction, as it lets us apply off-the-shelf no-regret algorithms for the online learning setting without fairness constraints.

Then, combining our reduction to the online batch classification without fairness constraints, exponential weights approach, and C that is appropriately set with respect to the regret guarantee of exponential weights, we show how to bound each of the misclassification regret and unfairness regret with in Section 4.2.

Finally, in Section 4.3, we show how we can use the Follow-The-Perturbed-Leader approach, specifically that of Syrgkanis et al. [2016], can be utilized to construct an algorithm which operates in an oracle-efficient manner.

4.1 Reduction to Online Batch Classification without Fairness Constraints

Here we show how to reduce the online batch fair classification problem to the online batch classifica-tion problem in an efficient manner. Once this reduction is complete, we can leverage any online batch algorithm as a black box in order to achieve sublinear Lagrangian regret. At a high level, our reduction involves just carefully transforming our online fair batch classification history up to into some fake online batch classification history and then feeding this artificially created history to a no-regret learner for the online batch classification setting.

Without loss of generality, we assume that C is an integer; if it’s not, then take the ceiling. Now, we describe how the transformation of the history works. For each round

each of to the original pairs to form . In order to keep the batch size the same across each round, even if copies of each of (v, 0) and (v, 1) where v is some arbitrary instance in X. We describe this process in more detail in Algorithm 3.

This reduction essentially preserves the regret, which we formally state in Lemma 4.1.

Lemma 4.1. For any sequence of

Proof. It is sufficient to show that in each round

First, assume

The second equality follows from the fact that for any

If , the same argument as above applies; the only difference is that all the cancel with each other because the number of copies with label 0 is exactly the same as that of label 1.

4.2 Exponential Weights

It is well known that for linear loss functions, exponential weights with appropriately tuned learning rate can achieve no regret [Freund and Schapire, 1997, Cesa-Bianchi et al., 1997, Arora et al., 2012]. We will first describe the setting of the exponential weights. We will then show how the setting of online batch classification we are interested in can be cast to this setting.

For each round t = 1, . . . , T:

1. The learner chooses a distribution

2. The adversary, with full knowledge of , chooses loss vector

3. The learner suffers

We emphasize that since the adversary chooses with full knowledge of can be chosen as a function of

Exponential weights is defined as and for any

and

Then, we have the following guarantee on the regret of exponential weights:

Theorem 4.2 (Arora et al. [2012]). Exponential weights with learning rate has the following guarantee: for any sequence of

In other words, with learning rate

We can easily reduce the online classification setting to that of exponential weights method. Each we deploy can be represented as a probability distribution

Putting everything together, we have

1. The learner deploys where the associated probability distribution over

2. The adversary, with the knowledge of which determines . Remember that is a function of

3. Learner suffers

Note that is formed as a function of exponential weights approach still allows the adversary to form as a function of or equivalently Therefore, we can use the regret guarantee of the exponential weights and appropriately set C to achieve sublinear fairness loss and misclassification regret.

Theorem 4.3. If , exponential weights guarantees the following: for any adaptively and adversarially chosen

where . In other words, misclassification regret and unfairness regret are both bounded by

Proof. First, we apply the regret guarantee of exponential weights. Theorem 4.2 gives us that

because Err. Note that is a function of , but as we emphasized before, the regret guarantee still holds.

Combining our previous lemmas and theorems, we have for any for

simultaneously for all

For the fairness loss, consider , and fix any . We then have

where the first implication follows from the fact that

As for the misclassification regret, consider

We remark that C is set to be exactly so as to bound both the misclassification regret and the fairness loss with , but other trade-off between the two is still possible.

4.3 Follow-The-Perturbed-Leader

Running exponential weights as in Section 4.2 in general cannot be done in an efficient manner, as such methods need to calculate the loss for each hypothesis or for each possible labeling in the case F has bounded VC-dimension. In this section, we aim to design an algorithm for our problem setting that is oracle-efficient.

Specifically, we show how the algorithm proposed by Syrgkanis et al. [2016] can be used as an achieve sublinear regret in the online batch classification setting in an oracle efficient manner. However, we remark that our approach of leveraging CONTEXT-FTPL requires us to relax how adaptive the environment can be in terms of choosing . Previously, we allowed the environment to choose full knowledge of the deployed policy . Here, we make an assumption that can be formed as a function of

Let us now consider the setting that Syrgkanis et al. [2016] study. They consider an adversarial contextual learning setting where in each round t, the learner randomly deploys some hypothesis5 , and the environment chooses indicates the number of possible actions that can be taken for the context whose associated loss vector is . The only knowledge at round t not available to the environment is the randomness that the learner uses to choose , but the environment may know the actual distribution that the learner has in round t just not the realization of it. At the end of the round, the learner suffers some loss

Syrgkanis et al. [2016] show that, in the small separator setting, they can achieve sublinear regret given that they can compute a separator set prior to learning. We first give the definition of a separator set and then state their regret guarantee.

Definition 4.4. A set is called a seperator set for if for any different and , there exists

Theorem 4.5 (Syrgkanis et al. [2016]). For any adversarially and adaptively chosen sequence of CONTEXT-FTPL initialized with a separator set S and parameter with the following re-

gret: for any

where is the implicit distribution over CONTEXT-FTPLhas in each round t.

Our online batch classification setting can be easily reduced to their setting by simply considering the batch of instances by setting , meaning we set and form the associated loss vector as . And we view each hypothesis as words, we can define the hypothesis class induced by F as

Note that . And we can use the following linear loss

Note that by construction, the difference in preserves the difference in misclassification loss over

Lemma 4.6. Write

Proof.

Syrgkanis et al. [2016] assume an optimization oracle with respect to L

which in our case corresponds to the following oracle:

Note that this is equivalent to a weighted empirical risk minimization oracle:

where . We remark that not all that we feed to the oracle will be of the form requires calling the oracle not just on the set of that we create from — for stability reasons, it also adds in contexts from the separator set and associate each of those contexts with a random vector where each coordinate is drawn from the Laplace distribution.

Furthermore, we can turn any separator set into an equal size separator set fact, the construction is as follows:

where v is some arbitrary instance in X.

Lemma 4.7. If S is the separator set for is a separator set for

Proof. Fix any . Note that by definition of S, there exists . As a result,

Because the loss we use is linear, we take a slightly different view on the interaction between the learner and the environment. Instead of the learner sampling a hypothesis and having the no-regret guarantee in expectation over the randomness of sampling the hypothesis, we imagine the learner playing the actual distribution over it has at round t. We note this distribution over and write the loss experienced by deploying a policy

However, CONTEXT-FTPL never explicitly keeps track of the distribution but only allows a way to sample from this distribution. Therefore, we form an empirical distribution by calling into CONTEXT-FTPL E many times to approximate — i.e. we write to denote the uniform distribution over

where is the result of our . We describe the overall reduction to CONTEXT-FTPL more formally in Algorithm 4.

Algorithm 4: Reduction to CONTEXT-FTPL

Unlike before, we have the environment choose without the knowledge of . This is so that the randomness used to form multiple times is not revealed to the environment. If the randomness is revealed, it is possible that the auditor can take advantage of the direction in which the empirical distribution that we deploy is off from the distribution maintained by CONTEXT-FTPL — more specifically, we would have to take a union bound over all possible that the environment can choose after the environment knows how has been chosen, which we can’t do because there are infinitely many possible (x, y).

Instead, we could argue about the concentration of the policy itself to its expected value instead of over the loss first and use the concentration over the distribution of hypotheses to argue for the concentration of the loss. However, the loss needs to average over each hypothesis or each possible labeling in the case of bounded VC-dimension, so our estimation error in the distribution over each hypothesis will add up over each , resulting in linear dependence on |F|, or over each possible labeling induced by F incurring estimation error linear in is the VC-dimension of F.

Hence, by hiding the randomness used to sample the empirical distribution from the environment (i.e. has to be chosen without access to ), the only thing in the loss that is adaptive to the deployed policy is the auditor. However, the auditor only has options (i.e. choose a pair out of

pair or output null), so we can easily union bound over these options.

Lemma 4.8. With probability over the randomness of (i.e. sampling

for every round is distributed according uniform distribution over is determined according to where is the corresponding policy for that is deployed in round t as shown in Algorithm 4.

Proof. Fix the round . Note that

Note that just by the construction of , we know that there are only possible options for . More specifically, if and always. Furthermore, by construction, we have

Write

Note that . Therefore, union bounding over all possible Chernoff bound, we have

Union bounding over all round , we have with probability

Now, we can combine all the arguments we have developed so far in order to prove that Algorithm 4 achieves sublinear fairness loss and misclassification regret:

Theorem 4.9. Set is the size of the separator set S. Algorithm 4 guarantees that with probability , the following holds true:

where . In other words, the misclassification regret and fairness loss is both bounded by with high probability.

Proof.

Then, applying Lemma 4.6 yields with probability

. In other words, we have . Theorem 4.5 gives us that a sequence of distribution achieves the following, where is equivalent to the distribution of CONTEXT-FTPL

Therefore, writing , we have with probability

With the same argument as in the proof of Theorem 4.3, we get that for

As for the misclassification regret, we have with

We only focus on their small separator set setting, although their transductive setting (i.e. the contexts are known in advance) should naturally follow as well.

5 Generalization

We observe that until this point, all of our results apply to the more general setting where individuals arrive in any adversarial fashion. In order to argue about generalization, in this section, we will assume the existence of an (unknown) data distribution from which individual arrivals are drawn:

In spite of the data being drawn i.i.d., there are two main technical challenges in establishing generalization guarantee: (1) the auditor’s fairness feedback at each round is limited to only incorporate reported fairness violations (as opposed to stronger forms of feedback of, for example, the distances between arriving individuals, etc.), where it only entails a single fairness violation with regards to the policy deployed in that round, and (2) both the deployed policies and the auditor are adaptive over rounds. To overcome these challenges, we will draw a connection between our established regret guarantees in Section 4 and the learner’s distributional accuracy and fairness guarantees.

As formerly discussed in Section 1, such strategies of leveraging regret guarantees to prove distributional bounds are known in the online learning literature as online to batch conversion schemes (see, e.g. Cesa-Bianchi et al. [2004], Helmbold and Warmuth [1995]). As we will see next, while accuracy generalization follows from standard such arguments, the fairness generalization bound we wish to establish does not, and will require a more elaborate technique.

In particular, we will analyze the generalization bounds for the average policy over rounds.

Definition 5.1 (Average Policy). Let be the policy deployed by the algorithm at round t. The average policy is defined by:

We denote the set of policies which are fair on the entire space of pairs of individuals by

Note that

5.1 Accuracy Generalization

We begin by stating the accuracy generalization guarantee for the average policy.

Theorem 5.2 (Accuracy Generalization). Suppose we are given an algorithm such that for any sequence , it produces such that with probability

Then, with probabilty , the misclassification loss of is upper bounded by

The high level proof idea for the accuracy generalization bound of Theorem 5.2 is as follows. While fix-ing the randomness of the algorithm, we apply the Azuma’s inequality over the randomness of sampling and similarly the Chernoff bound for any fixed in order to show that our empirical misclassification regret is concentrated around the true misclassification regret over the distribution D. Separately, for any fixed , we know that over the randomness of the algorithm, the misclassification regret must be bounded by . Then, we can union bound to argue that our true misclassification regret must be concentrated around . The full proof is given in Appendix A.

5.2 Fairness Generalization

A more challenging task is, however, to argue about the fairness generalization guarantee of the average policy. To provide some intuition for why this is the case, let us first attempt to upper bound the probability of running into an -fairness violation by the average policy on a randomly selected pair of individuals:

This bound is very dissatisfying, as the statement is vacuous when . The reason for such a weak guarantee is that by aiming to upper bound the unfairness probability for the original fairness violation threshold , we are subject to worst-case compositional guarantees6 in the sense that the average policy may result to have an -fairness violation on any fraction of the distribution (over pairs) where one or more of the deployed policies induces an -fairness violation. This bound is tight, and we refer the reader to Appendix A for the full example.

Interpolating To circumvent the above setback, our strategy will be to relax the target violation threshold of the desired fairness guarantee of the average policy to . How big should we set ? A good intuition may arrive from considering the following thought experiment: assume worst-case compositional guarantees, and then, select a pair of individuals on which the average policy has an -fairness violation. We aim to lower bound the number of policies from that have an fairness violation on this pair. As we will see, setting to be sufficiently larger will force the number of these policies required to produce an -fairness violation of the average policy on to be high, resulting in the following improved bound:

Lemma 5.4. Suppose that for all . For any integer

High-Level Proof Idea Setting has the following implication: for any pair of individuals , in order for -fairness violation on of the policies in must have an -fairness violation on . We will then say a subset -covered by a policy -violation on every element in A. We will denote by the subset of pairs of elements from -covered by at least q policies in . Next, consider the probability space over pairs of individuals. The lemma then follows from observing that for any , as this will allow us to upper bound the probability of an -fairness violation by the stated bound.

Then, we have

In other words, we must have that

Transition (2) stems from the following argument: for any , denote by

the rounds where the deployed policy would have an -fairness violation on . We know that

where denotes the probability measure of

Equipped with Lemma 5.4, we next note that the stochastic assumption allows us to link the distributional fairness guarantees of the deployed policies to the algorithm’s regret. The implication of this, which we state next, is that the case of deploying too many highly unfair policies along the interaction must result in a contradiction to the algorithm’s proven regret guarantee. Hence, we will be able to bound the sum of the distributional -fairness guarantees of all the policies deployed by the algorithm.

Lemma 5.5. With probability

Proof. We first prove the following concentration inequality.

Lemma 5.6. For any fixed randomness of the algorithm,

Proof. Consider the following sequence

Note that this is a martingale: is fixed. Now, we apply Azuma’s inequality. Since

Lemma 5.7. Fix the sequence of policies . Suppose that each -fair. Then:

Proof. We will lower bound the probability of having an -fairness violation on a pair of individuals among those who have arrived in a single round. Because all possible pairs within a single batch of independently arrived individuals are not independent, we resort to a weaker lower bound by dividing all of the arrivals into independent pairs. As we go through the batch, we take every two individuals to form a pair, and note that these pairs must be independent.

Next, we combine Lemma 5.6 and Lemma 5.7. With probability over the randomness of for any fixed randomness of the algorithm, we have

Suppose we write seed to denote the random seed used for the algorithm. For simplicity, write to denote the event that the following equality holds

We have that

Therefore, we can use union bound to show

In other words, we have that with probability

Finally, we combine the above lemmas to state our fairness generalization guarantee.

Theorem 5.8 (Fairness Generalization). Suppose we are given an algorithm such that for any sequence , it produces such that with probability

Then, with probability , for any integer -fair where

Proof. The theorem follows immediately by combining Lemma 5.4 and Lemma 5.5.

5.3 Bounds for Specific Algorithms

Next, we plug in the regret guarantees we have established in Section 4 to yield the following accuracy and fairness generalization bounds:

5.3.1 Exponential Weights

Applying Theorem 5.2 and Theorem 5.8 to Theorem 4.3 (and set for fairness), we get

Corollary 5.9. With probability , exponential weights with learning rate

5.3.2 Follow-The-Perturbed-Leader

Similarly for CONTEXT-FTPL, we can get the following generalization guarantee for CONTEXT-FTPL by noting that, with probability

and

We set for fairness here, to yield to following guarantee:

Corollary 5.10. Using CONTEXT-FTPL from Syrgkanis et al. [2016] with a separator set of size n, with probability , the average policy has the following guarantee:

Remark 5.11. Corollaries 5.9 and 5.10 imply that the average policy has a non-trivial accuracy guarantee and a fairness generalization bound despite having much weaker feedback than considered in the setting of Rothblum and Yona [2018], albeit worse rate than their uniform convergence bound.

6 Conclusion and Future Directions

In this work, we have removed several binding restrictions in the context of learning with individual fairness. We hope that relieving the metric assumption as well as the assumption regarding full access to the similarity measure, and only requiring the auditor to detect a single violation for every time interval, will be helpful in making individual fairness more achievable and easier to implement in practice. As for future work -first of all, it would be interesting to explore the interaction with different models of feedback (one natural variant being one-sided feedback). Second, thinking about a model where the auditor only has access to binary decisions may be helpful in further closing the gap to practical use. Third, as most of the literature on individual fairness (including this work) is decoupling the similarity measure from the distribution over the target variable, it would be desirable to try to explore and quantify the compatibility of the two in specific instances.

7 Acknowledgments

We thank Sampath Kannan, Akshay Krishnamurthy, Katrina Ligett, and Aaron Roth for helpful conversations at an early stage of this work. Part of this work was done while YB, CJ, and ZSW were visiting the Simons Institute for the Theory of Computing. YB is supported in part by Israel Science Foundation (ISF) grant #1044/16, the United States Air Force and DARPA under contracts FA8750-16-C-0022 and FA8750-19-2-0222, the Federmann Cyber Security Center in conjunction with the Israel National Cyber Directorate, and the Apple Scholars in AI/ML PhD Fellowship. CJ is supported in part by NSF grant AF-1763307. ZSW is supported in part by the NSF FAI Award #1939606, an Amazon Research Award, a Google Faculty Research Award, a J.P. Morgan Faculty Award, a Facebook Research Award, and a Mozilla Research Grant. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the United States Air Force and DARPA.

References

Alekh Agarwal, Alina Beygelzimer, Miroslav Dud´ık, John Langford, and Hanna M. Wallach. A reductions approach to fair classification. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsm¨assan, Stockholm, Sweden, July 10-15, 2018, pages 60–69, 2018. URL http://proceedings.mlr.press/v80/agarwal18a.html.

Naman Agarwal, Alon Gonen, and Elad Hazan. Learning in non-convex games with an optimization oracle. In Alina Beygelzimer and Daniel Hsu, editors, Conference on Learning Theory, COLT 2019, 25-28 June 2019, Phoenix, AZ, USA, volume 99 of Proceedings of Machine Learning Research, pages 18–29. PMLR, 2019. URL http://proceedings.mlr.press/v99/agarwal19a.html.

Sanjeev Arora, Elad Hazan, and Satyen Kale. The multiplicative weights update method: a meta-algorithm and applications. Theory of Computing, 8(1):121–164, 2012.

Xuanyu Cao and K. J. Ray Liu. Online convex optimization with time-varying constraints and bandit feedback. IEEE Trans. Autom. Control., 64(7):2665–2680, 2019. doi: 10.1109/TAC.2018.2884653. URL https://doi.org/10.1109/TAC.2018.2884653.

Nicol`o Cesa-Bianchi, Yoav Freund, David Haussler, David P. Helmbold, Robert E. Schapire, and Manfred K. Warmuth. How to use expert advice. J. ACM, 44(3):427–485, May 1997. ISSN 0004-5411. doi: 10.1145/258128.258179. URL https://doi.org/10.1145/258128.258179.

Nicol`o Cesa-Bianchi, Alex Conconi, and Claudio Gentile. On the generalization ability of on-line learning algorithms. IEEE Trans. Inf. Theory, 50(9):2050–2057, 2004. doi: 10.1109/TIT.2004.833339. URL https://doi.org/10.1109/TIT.2004.833339.

Alexandra Chouldechova. Fair prediction with disparate impact: A study of bias in recidivism prediction instruments. Big Data, Special Issue on Social and Technical Trade-Offs, 2017.

Alexandra Chouldechova and Aaron Roth. The frontiers of fairness in machine learning. CoRR, abs/1810.08810, 2018. URL http://arxiv.org/abs/1810.08810.

Sam Corbett-Davies and Sharad Goel. The measure and mismeasure of fairness: A critical review of fair machine learning. arXiv, 2018.

Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard S. Zemel. Fairness through awareness. In Innovations in Theoretical Computer Science 2012, Cambridge, MA, USA, January 8-10, 2012, pages 214–226, 2012. doi: 10.1145/2090236.2090255. URL https://doi.org/10.1145/2090236.2090255.

Yoav Freund and Robert E. Schapire. A decision-theoretic generalization of on-line learning and an ap- plication to boosting. J. Comput. Syst. Sci., 55(1):119–139, 1997. doi: 10.1006/jcss.1997.1504. URL https://doi.org/10.1006/jcss.1997.1504.

Stephen Gillen, Christopher Jung, Michael J. Kearns, and Aaron Roth. Online learning with an unknown fairness metric. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, 3-8 December 2018, Montr´eal, Canada., pages 2605–2614, 2018. URL http://papers.nips.cc/paper/7526-online-learning-with-an-unknown-fairness-metric.

Swati Gupta and Vijay Kamble. Individual fairness in hindsight. In Proceedings of the 2019 ACM Conference on Economics and Computation, EC 2019, Phoenix, AZ, USA, June 24-28, 2019, pages 805–806, 2019. doi: 10.1145/3328526.3329605. URL https://doi.org/10.1145/3328526.3329605.

Moritz Hardt, Eric Price, and Nathan Srebro. Equality of opportunity in supervised learning. In Neural Information Processing Systems (NIPS), 2016.

´Ursula H´ebert-Johnson, Michael P. Kim, Omer Reingold, and Guy N. Rothblum. Multicalibration: Calibra- tion for the (computationally-identifiable) masses. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsm¨assan, Stockholm, Sweden, July 10-15, 2018, pages 1944– 1953, 2018. URL http://proceedings.mlr.press/v80/hebert-johnson18a.html.

David P. Helmbold and Manfred K. Warmuth. On weak learning. J. Comput. Syst. Sci., 50(3):551–573, 1995. doi: 10.1006/jcss.1995.1044. URL https://doi.org/10.1006/jcss.1995.1044.

Christina Ilvento. Metric learning for individual fairness. CoRR, abs/1906.00250, 2019. URL http://arxiv.org/abs/1906.00250.

Shahin Jabbari, Matthew Joseph, Michael J. Kearns, Jamie Morgenstern, and Aaron Roth. Fairness in reinforcement learning. In Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, pages 1617–1626, 2017. URL http://proceedings.mlr.press/v70/jabbari17a.html.

Rodolphe Jenatton, Jim Huang, and C´edric Archambeau. Adaptive algorithms for online convex optimization with long-term constraints. In International Conference on Machine Learning, pages 402–411. PMLR, 2016.

Matthew Joseph, Michael J. Kearns, Jamie Morgenstern, Seth Neel, and Aaron Roth. Meritocratic fairness for infinite and contextual bandits. In Proceedings of the 2018 AAAI/ACM Conference on AI, Ethics, and Society, AIES 2018, New Orleans, LA, USA, February 02-03, 2018, pages 158–163, 2018. doi: 10.1145/3278721.3278764. URL https://doi.org/10.1145/3278721.3278764.

Christopher Jung, Michael J. Kearns, Seth Neel, Aaron Roth, Logan Stapleton, and Zhiwei Steven Wu. Eliciting and enforcing subjective individual fairness. CoRR, abs/1905.10660, 2019. URL http://arxiv.org/abs/1905.10660.

Sampath Kannan, Michael J. Kearns, Jamie Morgenstern, Mallesh M. Pai, Aaron Roth, Rakesh V. Vohra, and Zhiwei Steven Wu. Fairness incentives for myopic agents. In Proceedings of the 2017 ACM Conference on Economics and Computation, EC ’17, Cambridge, MA, USA, June 26-30, 2017, pages 369–386, 2017. doi: 10.1145/3033274.3085154. URL https://doi.org/10.1145/3033274.3085154.

Michael J. Kearns, Seth Neel, Aaron Roth, and Zhiwei Steven Wu. Preventing fairness gerrymandering: Auditing and learning for subgroup fairness. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsm¨assan, Stockholm, Sweden, July 10-15, 2018, pages 2569– 2577, 2018. URL http://proceedings.mlr.press/v80/kearns18a.html.

Jon Kleinberg, Sendhil Mullainathan, and Manish Raghavan. Inherent trade-offs in the fair determination of risk scores. In Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017.

Mehrdad Mahdavi, Rong Jin, and Tianbao Yang. Trading regret for efficiency: online convex optimization with long term constraints. J. Mach. Learn. Res., 13:2503–2528, 2012. URL http://dl.acm.org/citation.cfm?id=2503322.

John Podesta, Penny Pritzker, Ernest J. Moniz, John Holdren, and Jefrey Zients. Big data: Seizing opportu- nities and preserving values. 2014.

Guy N. Rothblum and Gal Yona. Probably approximately metric-fair learning. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsm¨assan, Stockholm, Sweden, July 10-15, 2018, pages 5666–5674, 2018. URL http://proceedings.mlr.press/v80/yona18a.html.

Arun Sai Suggala and Praneeth Netrapalli. Online non-convex learning: Following the perturbed leader is optimal. CoRR, abs/1903.08110, 2019. URL http://arxiv.org/abs/1903.08110.

Vasilis Syrgkanis, Akshay Krishnamurthy, and Robert E. Schapire. Efficient algorithms for adversarial contextual learning. In Proceedings of the 33nd International Conference on Machine Learning, ICML 2016, New York City, NY, USA, June 19-24, 2016, pages 2159–2168, 2016. URL http://proceedings.mlr.press/v48/syrgkanis16.html.

Hao Yu and Michael J. Neely. A low complexity algorithm with o(t) regret and O(1) constraint violations for online convex optimization with long term constraints. J. Mach. Learn. Res., 21:1:1–1:24, 2020. URL http://jmlr.org/papers/v21/16-494.html.

A Omitted Details from Section 5

Theorem 5.2 (Accuracy Generalization). Suppose we are given an algorithm such that for any sequence , it produces such that with probability

Then, with probabilty , the misclassification loss of is upper bounded by

Proof. Fix

quence

Lemma A.1. For any fixed randomness of the algorithm, we must have

Proof. Define

Note thatis a martingale: is deterministically determined in each round as a result of the fixed randomness. Also, we have . Therefore, applying Azuma’s inequality yields

Applying the Chernoff bound, we get a similar concentration bound for

Next, using triangle inequality, with probability only over the randomness of , it holds that for any fixed randomness of the algorithm

Suppose we write seed to denote the random seed used for the algorithm. For simplicity, write

to denote the event that inequality (5) doesn’t hold true.

And we write to denote the event that

We have that

Therefore, we can use union bound to show

In other words, we have that with probability

For the left hand side of the inequality, observe that the following holds:

Transition 6 stems from the fact that our misclassification loss is linear with respect to the base classifiers in F. Hence, taking the uniform distribution over

Also, assume the dissimilarity measure by the auditor is:

Assume the algorithm deploys policies in the following manner: