# Fair for All: Best-effort Fairness Guarantees for Classification

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Dec 2020.

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

- [Beyond Adult and COMPAS: Fairness in Multi-Class Prediction](https://mlsanity.com/paper/2206.07801/) (2022)
- [Input-agnostic Certified Group Fairness via Gaussian Parameter Smoothing](https://mlsanity.com/paper/2206.11423/) (2022)
- [FaiREE: Fair Classification with Finite-Sample and Distribution-Free Guarantee](https://mlsanity.com/paper/2211.15072/) (2022)
- [Non-Invasive Fairness in Learning through the Lens of Data Drift](https://mlsanity.com/paper/2303.17566/) (2023)
- [Fairness Through Counterfactual Utilities](https://mlsanity.com/paper/2108.05315/) (2021)
- [Fair Decision-Making for Food Inspections](https://mlsanity.com/paper/2108.05523/) (2021)
- [Regret Minimization with Noisy Observations](https://mlsanity.com/paper/2207.09435/) (2022)
- [Understanding and Reducing the Class-Dependent Effects of Data Augmentation with A Two-Player Game Approach](https://mlsanity.com/paper/2407.03146/) (2024)

## Abstract (arXiv)

Standard approaches to group-based notions of fairness, such as parity and equalized odds, try to equalize absolute measures of performance across known groups (based on race, gender, etc.). Consequently, a group that is inherently harder to classify may hold back the performance on other groups; and no guarantees can be provided for unforeseen groups. Instead, we propose a fairness notion whose guarantee, on each group g in a class G, is relative to the performance of the best classifier on g. We apply this notion to broad classes of groups, in particular, where (a) G consists of all possible groups (subsets) in the data, and (b) G is more streamlined. For the first setting, which is akin to groups being completely unknown, we devise the sc PF (Proportional Fairness) classifier, which guarantees, on any possible group g, an accuracy that is proportional to that of the optimal classifier for g, scaled by the relative size of g in the data set. Due to including all possible groups, some of which could be too complex to be relevant, the worst-case theoretical guarantees here have to be proportionally weaker for smaller subsets. For the second setting, we devise the sc BeFair (Best-effort Fair) framework which seeks an accuracy, on every g ∈ G, which approximates that of the optimal classifier on g, independent of the size of g. Aiming for such a guarantee results in a non-convex problem, and we design novel techniques to get around this difficulty when G is the set of linear hypotheses. We test our algorithms on real-world data sets, and present interesting comparative insights on their performance.