# Monotone Individual Fairness

arXiv: https://arxiv.org/abs/2403.06812 · HTML: https://mlsanity.com/paper/2403.06812/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 55 references that are in the map.
- First posted on arXiv 11 Mar 2024.

## Builds on (most cited first, 28 of 28)

- [A Reductions Approach to Fair Classification](https://mlsanity.com/paper/1803.02453/) (2018)
- [Fairness in Learning: Classic and Contextual Bandits](https://mlsanity.com/paper/1605.07139/) (2016)
- [Runaway Feedback Loops in Predictive Policing](https://mlsanity.com/paper/1706.09847/) (2017)
- [Online Convex Optimization with Stochastic Constraints](https://mlsanity.com/paper/1708.03741/) (2017)
- [Training individually fair ML models with Sensitive Subspace Robustness](https://mlsanity.com/paper/1907.00020/) (2019)
- [Adaptive Algorithms for Online Convex Optimization with Long-term Constraints](https://mlsanity.com/paper/1512.07422/) (2015)
- [Characterizing Fairness Over the Set of Good Models Under Selective Labels](https://mlsanity.com/paper/2101.00352/) (2021)
- [Operationalizing Individual Fairness with Pairwise Fair Representations](https://mlsanity.com/paper/1907.01439/) (2019)
- [Online Learning with an Unknown Fairness Metric](https://mlsanity.com/paper/1802.06936/) (2018)
- [Fairness Through Computationally-Bounded Awareness](https://mlsanity.com/paper/1803.03239/) (2018)
- [Two Simple Ways to Learn Individual Fairness Metrics from Data](https://mlsanity.com/paper/2006.11439/) (2020)
- [Metric Learning for Individual Fairness](https://mlsanity.com/paper/1906.00250/) (2019)
- [Online convex optimization for cumulative constraints](https://mlsanity.com/paper/1802.06472/) (2018)
- [Interpretable Classification Models for Recidivism Prediction](https://mlsanity.com/paper/1503.07810/) (2015)
- [An Online Convex Optimization Approach to Dynamic Network Resource Allocation](https://mlsanity.com/paper/1701.03974/) (2017)
- [A Unifying Framework for Online Optimization with Long-Term Constraints](https://mlsanity.com/paper/2209.07454/) (2022)
- [SenSeI: Sensitive Set Invariance for Enforcing Individual Fairness](https://mlsanity.com/paper/2006.14168/) (2020)
- [Efficient Algorithms for Adversarial Contextual Learning](https://mlsanity.com/paper/1602.02454/) (2016)
- [Individual Fairness in Hindsight](https://mlsanity.com/paper/1812.04069/) (2018)
- [Online Primal-Dual Mirror Descent under Stochastic Constraints](https://mlsanity.com/paper/1908.00305/) (2019)
- [Metric-Free Individual Fairness in Online Learning](https://mlsanity.com/paper/2002.05474/) (2020)
- [Probably Approximately Metric-Fair Learning](https://mlsanity.com/paper/1803.03242/) (2018)
- [Distributed Online Convex Optimization with Time-Varying Coupled Inequality Constraints](https://mlsanity.com/paper/1903.04277/) (2019)
- [Bandit Convex Optimization for Scalable and Dynamic IoT Management](https://mlsanity.com/paper/1707.09060/) (2017)
- [Learning under selective labels in the presence of expert consistency](https://mlsanity.com/paper/1807.00905/) (2018)
- [Individually Fair Gradient Boosting](https://mlsanity.com/paper/2103.16785/) (2021)
- [Individually Fair Learning with One-Sided Feedback](https://mlsanity.com/paper/2206.04475/) (2022)
- [Matrix Estimation for Individual Fairness](https://mlsanity.com/paper/2302.02096/) (2023)

## Built on by (most cited first, 3 of 3)

- [Intersectional Divergence: Measuring Fairness in Regression](https://mlsanity.com/paper/2505.00830/) (2025)
- [A Critical Review of Predominant Bias in Neural Networks](https://mlsanity.com/paper/2502.11031/) (2025)
- [Cost Efficient Fairness Audit Under Partial Feedback](https://mlsanity.com/paper/2510.03734/) (2025)

## Abstract (arXiv)

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 (O(T1/2+2b),O(T3/4-b)) respectively for regret, number of fairness 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 frontier of (O(T2/3+2b),O(T5/6-b)) for regret, number of fairness 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 tildeO(α-2) in the full information setting, and tildeO(α-2 + k2T1/3) in the partial information setting, where α is the sensitivity for reporting fairness violations, and k is the number of individuals in a round.