# Inherent Tradeoffs in Learning Fair Representations

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

## Key facts

- Cited by 144 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Jun 2019.

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

- [MultiBench: Multiscale Benchmarks for Multimodal Representation Learning](https://mlsanity.com/paper/2107.07502/) (2021)
- [Bias Mitigation for Machine Learning Classifiers: A Comprehensive Survey](https://mlsanity.com/paper/2207.07068/) (2022)
- [Are Gender-Neutral Queries Really Gender-Neutral? Mitigating Gender Bias in Image Search](https://mlsanity.com/paper/2109.05433/) (2021)
- [Mitigating Political Bias in Language Models Through Reinforced Calibration](https://mlsanity.com/paper/2104.14795/) (2021)
- [Causally motivated Shortcut Removal Using Auxiliary Labels](https://mlsanity.com/paper/2105.06422/) (2021)
- [Perturbation Augmentation for Fairer NLP](https://mlsanity.com/paper/2205.12586/) (2022)
- [Fair and Optimal Classification via Post-Processing](https://mlsanity.com/paper/2211.01528/) (2022)
- [Revisiting Scalarization in Multi-Task Learning: A Theoretical Perspective](https://mlsanity.com/paper/2308.13985/) (2023)
- [Differential Privacy and Fairness in Decisions and Learning Tasks: A Survey](https://mlsanity.com/paper/2202.08187/) (2022)
- [Pruning has a disparate impact on model accuracy](https://mlsanity.com/paper/2205.13574/) (2022)
- [Improving Fairness via Federated Learning](https://mlsanity.com/paper/2110.15545/) (2021)
- [Fair Normalizing Flows](https://mlsanity.com/paper/2106.05937/) (2021)
- [Achieving Fairness at No Utility Cost via Data Reweighing with Influence](https://mlsanity.com/paper/2202.00787/) (2022)
- [Probing GNN Explainers: A Rigorous Theoretical and Empirical Analysis of GNN Explanation Methods](https://mlsanity.com/paper/2106.09078/) (2021)
- [Emergent Unfairness in Algorithmic Fairness-Accuracy Trade-Off Research](https://mlsanity.com/paper/2102.01203/) (2021)
- [Understanding and Improving Fairness-Accuracy Trade-offs in Multi-Task Learning](https://mlsanity.com/paper/2106.02705/) (2021)
- [FFB: A Fair Fairness Benchmark for In-Processing Group Fairness Methods](https://mlsanity.com/paper/2306.09468/) (2023)
- [Fairness without Imputation: A Decision Tree Approach for Fair Prediction with Missing Values](https://mlsanity.com/paper/2109.10431/) (2021)
- [A Sociotechnical View of Algorithmic Fairness](https://mlsanity.com/paper/2110.09253/) (2021)
- [Adaptive Test-Time Personalization for Federated Learning](https://mlsanity.com/paper/2310.18816/) (2023)
- [Algorithm Fairness in AI for Medicine and Healthcare](https://mlsanity.com/paper/2110.00603/) (2021)
- [Group-Aware Threshold Adaptation for Fair Classification](https://mlsanity.com/paper/2111.04271/) (2021)
- [Proportional Fairness in Federated Learning](https://mlsanity.com/paper/2202.01666/) (2022)
- [FARE: Provably Fair Representation Learning with Practical Certificates](https://mlsanity.com/paper/2210.07213/) (2022)
- [Counterfactual Fairness with Partially Known Causal Graph](https://mlsanity.com/paper/2205.13972/) (2022)
- [FLAC: Fairness-Aware Representation Learning by Suppressing Attribute-Class Associations](https://mlsanity.com/paper/2304.14252/) (2023)
- [Understanding and Mitigating Accuracy Disparity in Regression](https://mlsanity.com/paper/2102.12013/) (2021)
- [Fair Representation: Guaranteeing Approximate Multiple Group Fairness for Unknown Tasks](https://mlsanity.com/paper/2109.00545/) (2021)
- [Equal Opportunity of Coverage in Fair Regression](https://mlsanity.com/paper/2311.02243/) (2023)
- [FRAPPE: A Group Fairness Framework for Post-Processing Everything](https://mlsanity.com/paper/2312.02592/) (2023)

## Abstract (arXiv)

Real-world applications of machine learning tools in high-stakes domains are often regulated to be fair, in the sense that the predicted target should satisfy some quantitative notion of parity with respect to a protected attribute. However, the exact tradeoff between fairness and accuracy is not entirely clear, even for the basic paradigm of classification problems. In this paper, we characterize an inherent tradeoff between statistical parity and accuracy in the classification setting by providing a lower bound on the sum of group-wise errors of any fair classifiers. Our impossibility theorem could be interpreted as a certain uncertainty principle in fairness: if the base rates differ among groups, then any fair classifier satisfying statistical parity has to incur a large error on at least one of the groups. We further extend this result to give a lower bound on the joint error of any (approximately) fair classifiers, from the perspective of learning fair representations. To show that our lower bound is tight, assuming oracle access to Bayes (potentially unfair) classifiers, we also construct an algorithm that returns a randomized classifier that is both optimal (in terms of accuracy) and fair. Interestingly, when the protected attribute can take more than two values, an extension of this lower bound does not admit an analytic solution. Nevertheless, in this case, we show that the lower bound can be efficiently computed by solving a linear program, which we term as the TV-Barycenter problem, a barycenter problem under the TV-distance. On the upside, we prove that if the group-wise Bayes optimal classifiers are close, then learning fair representations leads to an alternative notion of fairness, known as the accuracy parity, which states that the error rates are close between groups. Finally, we also conduct experiments on real-world datasets to confirm our theoretical findings.