mlsanityData to 14 Oct 2026

Monotone Individual Fairness

arXiv 2403.06812 ↗First posted 11 Mar 2024cs.LG cs.CY stat.MLcited by 3

Not on the map. Why?

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.

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

28 of 55 references.

References · 28

  1. 2018A Reductions Approach to Fair Classificationcited by 587
  2. 2016Fairness in Learning: Classic and Contextual Banditscited by 168
  3. 2017Runaway Feedback Loops in Predictive Policingcited by 97
  4. 2017Online Convex Optimization with Stochastic Constraintscited by 95
  5. 2019Training individually fair ML models with Sensitive Subspace Robustnesscited by 73
  6. 2015Adaptive Algorithms for Online Convex Optimization with Long-term Constraintscited by 65
  7. 2021Characterizing Fairness Over the Set of Good Models Under Selective Labelscited by 65
  8. 2019Operationalizing Individual Fairness with Pairwise Fair Representationscited by 64
  9. 2018Online Learning with an Unknown Fairness Metriccited by 62
  10. 2018Fairness Through Computationally-Bounded Awarenesscited by 55
  11. 2020Two Simple Ways to Learn Individual Fairness Metrics from Datacited by 54
  12. 2019Metric Learning for Individual Fairnesscited by 52
16 more
  1. 2018Online convex optimization for cumulative constraintscited by 47
  2. 2015Interpretable Classification Models for Recidivism Predictioncited by 44
  3. 2017An Online Convex Optimization Approach to Dynamic Network Resource Allocationcited by 42
  4. 2022A Unifying Framework for Online Optimization with Long-Term Constraintscited by 41
  5. 2020SenSeI: Sensitive Set Invariance for Enforcing Individual Fairnesscited by 37
  6. 2016Efficient Algorithms for Adversarial Contextual Learningcited by 33
  7. 2018Individual Fairness in Hindsightcited by 33
  8. 2019Online Primal-Dual Mirror Descent under Stochastic Constraintscited by 31
  9. 2020Metric-Free Individual Fairness in Online Learningcited by 30
  10. 2018Probably Approximately Metric-Fair Learningcited by 29
  11. 2019Distributed Online Convex Optimization with Time-Varying Coupled Inequality Constraintscited by 28
  12. 2017Bandit Convex Optimization for Scalable and Dynamic IoT Managementcited by 24
  13. 2018Learning under selective labels in the presence of expert consistencycited by 18
  14. 2021Individually Fair Gradient Boostingcited by 12
  15. 2022Individually Fair Learning with One-Sided Feedbackcited by 5
  16. 2023Matrix Estimation for Individual Fairnesscited by 1

Built on by

Cited by year

Citing papers per year: 2025: 3.

3 papers.

  1. 2025Intersectional Divergence: Measuring Fairness in Regressioncited by 1
  2. 2025A Critical Review of Predominant Bias in Neural Networkscited by 0
  3. 2025Cost Efficient Fairness Audit Under Partial Feedbackcited by 0