Timezone: »

Individually Fair Learning with One-Sided Feedback
Yahav Bechavod · Aaron Roth

Wed Jul 26 05:00 PM -- 06:30 PM (PDT) @ Exhibit Hall 1 #712
We consider an online learning problem with one-sided feedback, in which the learner is able to observe the true label only for positively predicted instances. On each round, $k$ instances arrive and receive classification outcomes according to a randomized policy deployed by the learner, whose goal is to maximize accuracy while deploying individually fair policies. We first present a novel auditing scheme, capable of utilizing feedback from dynamically-selected panels of multiple, possibly inconsistent, auditors regarding fairness violations. In particular, we show how our proposed auditing scheme allows for algorithmically exploring the resulting accuracy-fairness frontier, with no need for additional feedback from auditors. We then present an efficient reduction from our problem of online learning with one-sided feedback and a panel reporting fairness violations to the contextual combinatorial semi-bandit problem (Cesa-Bianchi & Lugosi, 2009; Gyorgy et al., 2007), allowing us to leverage algorithms for contextual combinatorial semi-bandits to establish multi-criteria no regret guarantees in our setting, simultaneously for accuracy and fairness. Our results eliminate two potential sources of bias from prior work: the “hidden outcomes” that are not available to an algorithm operating in the full information setting, and human biases that might be present in any single human auditor, but can be mitigated by selecting a well-chosen panel.

Author Information

Yahav Bechavod (UPenn)

Yahav Bechavod is a Postdoctoral Researcher in the School of Engineering and Applied Science at the University of Pennsylvania, working with Prof. Aaron Roth. Prior to joining Penn, He was a PhD student at the School of Computer Science and Engineering at the Hebrew University of Jerusalem and an Apple Scholar in AI/ML. His research interests are primarily in algorithms, machine learning, and game theory, and specifically in the areas of fairness in machine learning, online learning, and learning in the presence of strategic behavior. He is the recipient of several awards and fellowships, including the Israeli Council for Higher Education Postdoctoral Fellowship, the Apple Scholars in AI/ML PhD Fellowship, and the Charles Clore Foundation PhD Fellowship. He holds an MS (Computer Science, Summa Cum Laude), and a BS (Mathematics and Computer Science, double major), both from the Hebrew University.

Aaron Roth (University of Pennsylvania)

More from the Same Authors