Monotone Individual Fairness
Yahav Bechavod
We revisit the problem of online learning with individual fairness, where an
online learner strives to maximize predictive accuracy while ensuring that
similar individuals are treated similarly. We first extend the frameworks of
Gillen et al. (2018); Bechavod et al. (2020), which rely on feedback from human
auditors regarding fairness violations, as we consider auditing schemes that
are capable of aggregating feedback from any number of auditors, using a rich
class we term monotone aggregation functions. We then prove a characterization
for such auditing schemes, practically reducing the analysis of auditing for
individual fairness by multiple auditors to that of auditing by
(instance-specific) single auditors. Using our generalized framework, we
present an oracle-efficient algorithm achieving an upper bound frontier of
$(\mathcal{O}(T^{1/2+2b}),\mathcal{O}(T^{3/4-b}))$ respectively for regret,
number of fairness violations, for $0\leq b \leq 1/4$. We then study an online
classification setting where label feedback is available for
positively-predicted individuals only, and present an oracle-efficient
algorithm achieving an upper bound frontier of
$(\mathcal{O}(T^{2/3+2b}),\mathcal{O}(T^{5/6-b}))$ for regret, number of
fairness violations, for $0\leq b \leq 1/6$. In both settings, our algorithms
improve on the best known bounds for oracle-efficient algorithms. Furthermore,
our algorithms offer significant improvements in computational efficiency,
greatly reducing the number of required calls to an (offline) optimization
oracle per round, to $\tilde{\mathcal{O}}(\alpha^{-2})$ in the full information
setting, and $\tilde{\mathcal{O}}(\alpha^{-2} + k^2T^{1/3})$ in the partial
information setting, where $\alpha$ is the sensitivity for reporting fairness
violations, and $k$ is the number of individuals in a round.