Metric-Free Individual Fairness in Online Learning

  • 2022-01-13 18:59:42
  • Yahav Bechavod, Christopher Jung, Zhiwei Steven Wu
  • 0


We study an online learning problem subject to the constraint of individualfairness, which requires that similar individuals are treated similarly. Unlikeprior work on individual fairness, we do not assume the similarity measureamong individuals is known, nor do we assume that such measure takes a certainparametric form. Instead, we leverage the existence of an auditor who detectsfairness violations without enunciating the quantitative measure. In eachround, the auditor examines the learner's decisions and attempts to identify apair of individuals that are treated unfairly by the learner. We provide ageneral reduction framework that reduces online classification in our model tostandard online classification, which allows us to leverage existing onlinelearning algorithms to achieve sub-linear regret and number of fairnessviolations. Surprisingly, in the stochastic setting where the data are drawnindependently from a distribution, we are also able to establish PAC-stylefairness and accuracy generalization guarantees (Yona and Rothblum [2018]),despite only having access to a very restricted form of fairness feedback. Ourfairness generalization bound qualitatively matches the uniform convergencebound of Yona and Rothblum [2018], while also providing a meaningful accuracygeneralization guarantee. Our results resolve an open question by Gillen et al.[2018] by showing that online learning under an unknown individual fairnessconstraint is possible even without assuming a strong parametric form of theunderlying similarity measure.


Quick Read (beta)

loading the full paper ...