Monotone Individual Fairness

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 this function class, 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 of O( √ T ) for regret and O(T 3 4 ) for the number of fairness violations (and more generally, a frontier of (O(T 1 2 +2b ), O(T 3 4 -b )) for regret, number of violations, for 0 ≤ b ≤ 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 of O(T 2 3 ) for regret and O(T 5 6 ) for the number of fairness violations (and more generally, a frontier of (O(T 2 3 +2b ), O(T 5 6 -b )) for regret, number of violations, for 0 ≤ b ≤ 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 Õ(α -2 ) in the full information setting, and Õ(α -2 + k 2 T 1 3 ) in the partial information setting, where α is the sensitivity for reporting fairness violations, and k is the number of individuals in a round. This stands in contrast to previous algorithms which required making T such oracle calls every round.