Equal Opportunity in Online Classification with Partial Feedback

By Yahav Bechavod, Katrina Ligett, Aaron Roth, Bo Waggoner, Zhiwei Steven Wu. 2019

67 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

Citations in the corpus

Characterizing Fairness Over the Set of Good Models Under Selective Labels (2021, background): “Finally, a related work is [40], which studies fairness properties in an online classification problem that suffers from the selective labels problem.”
A survey of algorithmic recourse: definitions, formulations, solutions, and prospects (2020, background): “For example, it has been demonstrated that for models trained on selective labels , fair and optimal decisions should be made stochastically [25, 96].”
Minimizing Human Intervention in Online Classification (2025, unknown): “Bechavod et al. (2019) further studied one-sided feedback, revealing labels only upon positive predictions in an i.i.d. stream.”