Monotone Individual Fairness
This work addresses fairness in online learning for machine learning practitioners by providing more efficient algorithms with better theoretical guarantees, though it is incremental as it builds on prior frameworks.
The paper tackles online learning with individual fairness by extending auditing frameworks to aggregate feedback from multiple auditors using monotone functions, and presents oracle-efficient algorithms that improve regret and fairness violation bounds, achieving O(T^{1/2+2b}) and O(T^{3/4-b}) in full information and O(T^{2/3+2b}) and O(T^{5/6-b}) in partial information settings, while reducing oracle calls to O(α^{-2}) and O(α^{-2} + k^2T^{1/3}) respectively.
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}}(α^{-2})$ in the full information setting, and $\tilde{\mathcal{O}}(α^{-2} + k^2T^{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.