# Metric-Free Individual Fairness in Online Learning

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

## Key facts

- Cited by 30 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Feb 2020.

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

- [A Sociotechnical View of Algorithmic Fairness](https://mlsanity.com/paper/2110.09253/) (2021)
- [Fairness and Accuracy under Domain Generalization](https://mlsanity.com/paper/2301.13323/) (2023)
- [What-is and How-to for Fairness in Machine Learning: A Survey, Reflection, and Perspective](https://mlsanity.com/paper/2206.04101/) (2022)
- [Imagining new futures beyond predictive systems in child welfare: A qualitative study with impacted stakeholders](https://mlsanity.com/paper/2205.08928/) (2022)
- [Fair Decision-making Under Uncertainty](https://mlsanity.com/paper/2301.12364/) (2023)
- [Preventing Discriminatory Decision-making in Evolving Data Streams](https://mlsanity.com/paper/2302.08017/) (2023)
- [Learning to Predict Trustworthiness with Steep Slope Loss](https://mlsanity.com/paper/2110.00054/) (2021)
- [Multi-disciplinary fairness considerations in machine learning for clinical trials](https://mlsanity.com/paper/2205.08875/) (2022)
- [Doubly Fair Dynamic Pricing](https://mlsanity.com/paper/2209.11837/) (2022)
- [Toward Operationalizing Pipeline-aware ML Fairness: A Research Agenda for Developing Practical Guidelines and Tools](https://mlsanity.com/paper/2309.17337/) (2023)
- [What Is Fairness? On the Role of Protected Attributes and Fictitious Worlds](https://mlsanity.com/paper/2205.09622/) (2022)
- [BanditQ: Fair Bandits with Guaranteed Rewards](https://mlsanity.com/paper/2304.05219/) (2023)
- [Robust No-Regret Learning in Min-Max Stackelberg Games](https://mlsanity.com/paper/2203.14126/) (2022)
- [Individually Fair Learning with One-Sided Feedback](https://mlsanity.com/paper/2206.04475/) (2022)
- [Human-Guided Fair Classification for Natural Language Processing](https://mlsanity.com/paper/2212.10154/) (2022)
- [Fair Streaming Principal Component Analysis: Statistical and Algorithmic Viewpoint](https://mlsanity.com/paper/2310.18593/) (2023)
- [FEAMOE: Fair, Explainable and Adaptive Mixture of Experts](https://mlsanity.com/paper/2210.04995/) (2022)
- [Manifestations of Xenophobia in AI Systems](https://mlsanity.com/paper/2212.07877/) (2022)
- [Causal Fair Machine Learning via Rank-Preserving Interventional Distributions](https://mlsanity.com/paper/2307.12797/) (2023)
- [Long-Term Fairness Inquiries and Pursuits in Machine Learning: A Survey of Notions, Methods, and Challenges](https://mlsanity.com/paper/2406.06736/) (2024)
- [Enhancing Group Fairness in Online Settings Using Oblique Decision Forests](https://mlsanity.com/paper/2310.11401/) (2023)
- [Causal Fair Metric: Bridging Causality, Individual Fairness, and Adversarial Robustness](https://mlsanity.com/paper/2310.19391/) (2023)
- [Monotone Individual Fairness](https://mlsanity.com/paper/2403.06812/) (2024)
- [Matrix Estimation for Individual Fairness](https://mlsanity.com/paper/2302.02096/) (2023)
- [On Comparing Fair Classifiers under Data Bias](https://mlsanity.com/paper/2302.05906/) (2023)
- [On the Power of Randomization in Fair Classification and Representation](https://mlsanity.com/paper/2406.03142/) (2024)
- [Identifying, measuring, and mitigating individual unfairness for supervised learning models and application to credit risk models](https://mlsanity.com/paper/2211.06106/) (2022)
- [Cost Efficient Fairness Audit Under Partial Feedback](https://mlsanity.com/paper/2510.03734/) (2025)
- [Near-Optimal Cryptographic Hardness of Learning With Homogeneous Halfspaces Under Gaussian Marginals](https://mlsanity.com/paper/2604.26446/) (2026)
- [Why Global LLM Leaderboards Are Misleading: Small Portfolios for Heterogeneous Supervised ML](https://mlsanity.com/paper/2605.06656/) (2026)

## Abstract (arXiv)

We study an online learning problem subject to the constraint of individual fairness, which requires that similar individuals are treated similarly. Unlike prior work on individual fairness, we do not assume the similarity measure among individuals is known, nor do we assume that such measure takes a certain parametric form. Instead, we leverage the existence of an auditor who detects fairness violations without enunciating the quantitative measure. In each round, the auditor examines the learner's decisions and attempts to identify a pair of individuals that are treated unfairly by the learner. We provide a general reduction framework that reduces online classification in our model to standard online classification, which allows us to leverage existing online learning algorithms to achieve sub-linear regret and number of fairness violations. Surprisingly, in the stochastic setting where the data are drawn independently from a distribution, we are also able to establish PAC-style fairness and accuracy generalization guarantees (Rothblum and Yona [2018]), despite only having access to a very restricted form of fairness feedback. Our fairness generalization bound qualitatively matches the uniform convergence bound of Rothblum and Yona [2018], while also providing a meaningful accuracy generalization guarantee. Our results resolve an open question by Gillen et al. [2018] by showing that online learning under an unknown individual fairness constraint is possible even without assuming a strong parametric form of the underlying similarity measure.