CaltechAUTHORS
  A Caltech Library Service

Equal Opportunity in Online Classification with Partial Feedback

Bechavod, Yahav and Ligett, Katrina and Roth, Aaron and Waggoner, Bo and Wu, Zhiwei Steven (2019) Equal Opportunity in Online Classification with Partial Feedback. . (Unpublished) https://resolver.caltech.edu/CaltechAUTHORS:20190626-152715232

[img] PDF - Submitted Version
See Usage Policy.

277Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20190626-152715232

Abstract

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.


Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription
http://arxiv.org/abs/1902.02242arXivDiscussion Paper
ORCID:
AuthorORCID
Ligett, Katrina0000-0003-2780-6656
Additional Information:Supported in part by Israeli Science Foundation (ISF) grant #1044/16, a subcontract on the DARPA Brandeis Project, and the Federmann Cyber Security Center in conjunction with the Israel national cyber directorate. Supported in part by Israeli Science Foundation (ISF) grant #1044/16, a subcontract on the DARPA Brandeis Project, and the Federmann Cyber Security Center in conjunction with the Israel national cyber directorate. Part of this work was done while the author was visiting the Simons Institute for the Theory of Computing. Supported in part by NSF grants AF-1763307, CNS-1253345, a subcontract on the DARPA Brandeis Project, and an Amazon Research award. We thank Nati Srebro for a conversation leading to the question we study here. We thank Michael Kearns for helpful discussions at an early stage of this work.
Funders:
Funding AgencyGrant Number
Israel Science Foundation1044/16
Defense Advanced Research Projects Agency (DARPA)UNSPECIFIED
Hebrew University of JerusalemUNSPECIFIED
NSFAF-1763307
NSFCNS-1253345
AmazonUNSPECIFIED
Record Number:CaltechAUTHORS:20190626-152715232
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20190626-152715232
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:96753
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:27 Jun 2019 01:53
Last Modified:03 Oct 2019 21:25

Repository Staff Only: item control page