# Individually Fair Learning with One-Sided Feedback

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 72 references that are in the map.
- First posted on arXiv 9 Jun 2022.

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

- [Equality of Opportunity in Supervised Learning](https://mlsanity.com/paper/1610.02413/) (2016)
- [Fairness in Learning: Classic and Contextual Bandits](https://mlsanity.com/paper/1605.07139/) (2016)
- [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)
- [Interpretable Classification Models for Recidivism Prediction](https://mlsanity.com/paper/1503.07810/) (2015)
- [Equal Opportunity in Online Classification with Partial Feedback](https://mlsanity.com/paper/1902.02242/) (2019)
- [Efficient Algorithms for Adversarial Contextual Learning](https://mlsanity.com/paper/1602.02454/) (2016)
- [Individual Fairness in Hindsight](https://mlsanity.com/paper/1812.04069/) (2018)
- [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)
- [Fair Algorithms for Learning in Allocation Problems](https://mlsanity.com/paper/1808.10549/) (2018)
- [An efficient algorithm for learning with semi-bandit feedback](https://mlsanity.com/paper/1305.2732/) (2013)
- [Learning under selective labels in the presence of expert consistency](https://mlsanity.com/paper/1807.00905/) (2018)
- [How to Use Heuristics for Differential Privacy](https://mlsanity.com/paper/1811.07765/) (2018)
- [Learning the Truth From Only One Side of the Story](https://mlsanity.com/paper/2006.04858/) (2020)

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

- [Omnipredictors for Constrained Optimization](https://mlsanity.com/paper/2209.07463/) (2022)
- [Group-blind optimal transport to group parity and its constrained variants](https://mlsanity.com/paper/2310.11407/) (2023)
- [Monotone Individual Fairness](https://mlsanity.com/paper/2403.06812/) (2024)
- [Online Learning with Multiple Fairness Regularizers via Graph-Structured Feedback](https://mlsanity.com/paper/2508.14311/) (2025)
- [Near-Optimal Cryptographic Hardness of Learning With Homogeneous Halfspaces Under Gaussian Marginals](https://mlsanity.com/paper/2604.26446/) (2026)

## Abstract (arXiv)

We consider an online learning problem with one-sided feedback, in which the learner is able to observe the true label only for positively predicted instances. On each round, k instances arrive and receive classification outcomes according to a randomized policy deployed by the learner, whose goal is to maximize accuracy while deploying individually fair policies. We first extend the framework of Bechavod et al. (2020), which relies on the existence of a human fairness auditor for detecting fairness violations, to instead incorporate feedback from dynamically-selected panels of multiple, possibly inconsistent, auditors. We then construct an efficient reduction from our problem of online learning with one-sided feedback and a panel reporting fairness violations to the contextual combinatorial semi-bandit problem (Cesa-Bianchi & Lugosi, 2009, Gy"orgy et al., 2007). Finally, we show how to leverage the guarantees of two algorithms in the contextual combinatorial semi-bandit setting: Exp2 (Bubeck et al., 2012) and the oracle-efficient Context-Semi-Bandit-FTPL (Syrgkanis et al., 2016), to provide multi-criteria no regret guarantees simultaneously for accuracy and fairness. Our results eliminate two potential sources of bias from prior work: the "hidden outcomes" that are not available to an algorithm operating in the full information setting, and human biases that might be present in any single human auditor, but can be mitigated by selecting a well chosen panel.