Timezone: »

 
Oral
Metric-Free Individual Fairness in Online Learning
Yahav Bechavod · Christopher Jung · Steven Wu

Wed Dec 09 06:15 AM -- 06:30 AM (PST) @ Orals & Spotlights: Social/Adversarial Learning
in Orals & Spotlights Track 20: Social/Adversarial Learning »

We study an online learning problem subject to the constraint of individual fairness, which requires that similar individuals are treated similarly. Unlike prior work on individual fairness, we do not assume the similarity measure among individuals is known, nor do we assume that such measure takes a certain parametric form. Instead, we leverage the existence of an auditor who detects fairness violations without enunciating the quantitative measure. In each round, the auditor examines the learner's decisions and attempts to identify a pair of individuals that are treated unfairly by the learner. We provide a general reduction framework that reduces online classification in our model to standard online classification, which allows us to leverage existing online learning algorithms to achieve sub-linear regret and number of fairness violations. Surprisingly, in the stochastic setting where the data are drawn independently from a distribution, we are also able to establish PAC-style fairness and accuracy generalization guarantees (Rothblum and Yona (2018)), despite only having access to a very restricted form of fairness feedback. Our fairness generalization bound qualitatively matches the uniform convergence bound of Rothblum and Yona (2018), while also providing a meaningful accuracy generalization guarantee. Our results resolve an open question by Gillen et al. (2018) by showing that online learning under an unknown individual fairness constraint is possible even without assuming a strong parametric form of the underlying similarity measure.

Author Information

Yahav Bechavod (Hebrew University)

Yahav Bechavod is a PhD student at the School of Computer Science and Engineering at the Hebrew University, advised by Prof. Amit Daniely. His research explores foundational questions in the fields of machine learning, algorithmic fairness, and learning in the presence of strategic behavior. He is an Apple Scholar in AI\ML, and a recipient of the Charles Clore Foundation PhD Fellowship and the KLA Award for Research Excellence in PhD. He also holds an MS (Computer Science, Summa Cum Laude) and BS (Mathematics and Computer Science) from the Hebrew University.

Christopher Jung (University of Pennsylvania)
Steven Wu (Carnegie Mellon University)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors