# Equal Opportunity in Online Classification with Partial Feedback

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

## Key facts

- Cited by 35 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Feb 2019.

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

- [Characterizing Fairness Over the Set of Good Models Under Selective Labels](https://mlsanity.com/paper/2101.00352/) (2021)
- [Fairness of Exposure in Stochastic Bandits](https://mlsanity.com/paper/2103.02735/) (2021)
- [A Stochastic Optimization Framework for Fair Risk Minimization](https://mlsanity.com/paper/2102.12586/) (2021)
- [Fairness-Aware Online Meta-learning](https://mlsanity.com/paper/2108.09435/) (2021)
- [Adaptive Sampling Strategies to Construct Equitable Training Datasets](https://mlsanity.com/paper/2202.01327/) (2022)
- [What-is and How-to for Fairness in Machine Learning: A Survey, Reflection, and Perspective](https://mlsanity.com/paper/2206.04101/) (2022)
- [Stochastic Differentially Private and Fair Learning](https://mlsanity.com/paper/2210.08781/) (2022)
- [Towards Return Parity in Markov Decision Processes](https://mlsanity.com/paper/2111.10476/) (2021)
- [Don't Throw it Away! The Utility of Unlabeled Data in Fair Decision Making](https://mlsanity.com/paper/2205.04790/) (2022)
- [A Classification of Feedback Loops and Their Relation to Biases in Automated Decision-Making Systems](https://mlsanity.com/paper/2305.06055/) (2023)
- [A Unified Approach to Fair Online Learning via Blackwell Approachability](https://mlsanity.com/paper/2106.12242/) (2021)
- [Robustness and Cybersecurity in the EU Artificial Intelligence Act](https://mlsanity.com/paper/2502.16184/) (2025)
- [Strategic Apple Tasting](https://mlsanity.com/paper/2306.06250/) (2023)
- [Group Meritocratic Fairness in Linear Contextual Bandits](https://mlsanity.com/paper/2206.03150/) (2022)
- [Designing Long-term Group Fair Policies in Dynamical Systems](https://mlsanity.com/paper/2311.12447/) (2023)
- [Tier Balancing: Towards Dynamic Fairness over Underlying Causal Factors](https://mlsanity.com/paper/2301.08987/) (2023)
- [Precarity: Modeling the Long Term Effects of Compounded Decisions on Individual Instability](https://mlsanity.com/paper/2104.12037/) (2021)
- [Adaptive Data Debiasing through Bounded Exploration](https://mlsanity.com/paper/2110.13054/) (2021)
- [Fairer LP-based Online Allocation via Analytic Center](https://mlsanity.com/paper/2110.14621/) (2021)
- [Social Bias Meets Data Bias: The Impacts of Labeling and Measurement Errors on Fairness Criteria](https://mlsanity.com/paper/2206.00137/) (2022)
- [Individually Fair Learning with One-Sided Feedback](https://mlsanity.com/paper/2206.04475/) (2022)
- [Fair Online Bilateral Trade](https://mlsanity.com/paper/2405.13919/) (2024)
- [Long-Term Fairness Inquiries and Pursuits in Machine Learning: A Survey of Notions, Methods, and Challenges](https://mlsanity.com/paper/2406.06736/) (2024)
- [Apple Tasting Revisited: Bayesian Approaches to Partially Monitored Online Binary Classification](https://mlsanity.com/paper/2109.14412/) (2021)
- [Neural Pseudo-Label Optimism for the Bank Loan Problem](https://mlsanity.com/paper/2112.02185/) (2021)
- [On the Impact of Performative Risk Minimization for Binary Random Variables](https://mlsanity.com/paper/2502.02331/) (2025)
- [Hard Choices and Hard Limits for Artificial Intelligence](https://mlsanity.com/paper/2105.07852/) (2021)
- [Fair Classification with Partial Feedback: An Exploration-Based Data Collection Approach](https://mlsanity.com/paper/2402.11338/) (2024)
- [Generalization Error Bounds for Learning under Censored Feedback](https://mlsanity.com/paper/2404.09247/) (2024)
- [Fairness with Exponential Weights](https://mlsanity.com/paper/2411.04295/) (2024)

## Abstract (arXiv)

We study an online classification problem with partial feedback in which individuals arrive one at a time from a fixed but unknown distribution, and must be classified as positive or negative. Our algorithm only observes the true label of an individual if they are given a positive classification. This setting captures many classification problems for which fairness is a concern: for example, in criminal recidivism prediction, recidivism is only observed if the inmate is released; in lending applications, loan repayment is only observed if the loan is granted. We require that our algorithms satisfy common statistical fairness constraints (such as equalizing false positive or negative rates -- introduced as "equal opportunity" in Hardt et al. (2016)) at every round, with respect to the underlying distribution. We give upper and lower bounds characterizing the cost of this constraint in terms of the regret rate (and show that it is mild), and give an oracle efficient algorithm that achieves the upper bound.