Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published June 27, 2019 | Submitted
Report Open

Equal Opportunity in Online Classification with Partial Feedback

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.

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.

Attached Files

Submitted - 1902.02242.pdf

Files

1902.02242.pdf
Files (284.2 kB)
Name Size Download all
md5:e282096b751c611f492f87c71275fb58
284.2 kB Preview Download

Additional details

Created:
August 19, 2023
Modified:
October 20, 2023