Timezone: »

Equal Opportunity in Online Classification with Partial Feedback
Yahav Bechavod · Katrina Ligett · Aaron Roth · Bo Waggoner · Steven Wu

Thu Dec 12 05:00 PM -- 07:00 PM (PST) @ East Exhibition Hall B + C #108

We study an online classification problem with partial feedback in which individuals arrive one at a time from a fixed but unknown distribution, and must be classified as positive or negative. Our algorithm only observes the true label of an individual if they are given a positive classification. This setting captures many classification problems for which fairness is a concern: for example, in criminal recidivism prediction, recidivism is only observed if the inmate is released; in lending applications, loan repayment is only observed if the loan is granted. We require that our algorithms satisfy common statistical fairness constraints (such as equalizing false positive or negative rates --- introduced as "equal opportunity" in Hardt et al. (2016)) at every round, with respect to the underlying distribution. We give upper and lower bounds characterizing the cost of this constraint in terms of the regret rate (and show that it is mild), and give an oracle efficient algorithm that achieves the upper bound.

Author Information

Yahav Bechavod (Hebrew University)

Yahav Bechavod is a PhD candidate at the School of Computer Science and Engineering at the Hebrew University of Jerusalem, advised by Amit Daniely and Katrina Ligett. He is an Apple PhD fellow in AI/ML, and a recipient of the Charles Clore Foundation PhD Fellowship. He also holds an MS (Computer Science) and a BS (Mathematics and Computer Science), both from the Hebrew University. Yahav's research explores foundational questions in the field of algorithmic fairness, such as: (1) characterizing the amount of friction between utility and fairness in various settings, (2) providing novel algorithms guaranteeing high utility and fairness in the face of limited or partial feedback, and (3) making clever use of human feedback in the learning loop in auditing for unfairness.

Katrina Ligett (Hebrew University)
Aaron Roth (University of Pennsylvania)
Bo Waggoner (U. Colorado, Boulder)
Steven Wu (University of Minnesota)


More from the Same Authors