Metric-Free Individual Fairness in Online 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.
