# No-Free-Fairness: Fundamental Limits and Trade-offs in Learning Systems

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 29 of its 44 references that are in the map.
- First posted on arXiv 16 Jun 2026.

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

- [On the Opportunities and Risks of Foundation Models](https://mlsanity.com/paper/2108.07258/) (2021)
- [Equality of Opportunity in Supervised Learning](https://mlsanity.com/paper/1610.02413/) (2016)
- [WILDS: A Benchmark of in-the-Wild Distribution Shifts](https://mlsanity.com/paper/2012.07421/) (2020)
- [Man is to Computer Programmer as Woman is to Homemaker? Debiasing Word Embeddings](https://mlsanity.com/paper/1607.06520/) (2016)
- [RealToxicityPrompts: Evaluating Neural Toxic Degeneration in Language Models](https://mlsanity.com/paper/2009.11462/) (2020)
- [Certifying and removing disparate impact](https://mlsanity.com/paper/1412.3756/) (2014)
- [Fair prediction with disparate impact: A study of bias in recidivism prediction instruments](https://mlsanity.com/paper/1610.07524/) (2016)
- [MentorNet: Learning Data-Driven Curriculum for Very Deep Neural Networks on Corrupted Labels](https://mlsanity.com/paper/1712.05055/) (2017)
- [Bias and Fairness in Large Language Models: A Survey](https://mlsanity.com/paper/2309.00770/) (2023)
- [A Reductions Approach to Fair Classification](https://mlsanity.com/paper/1803.02453/) (2018)
- [Inherent Trade-Offs in the Fair Determination of Risk Scores](https://mlsanity.com/paper/1609.05807/) (2016)
- [Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks](https://mlsanity.com/paper/1901.08584/) (2019)
- [Underspecification Presents Challenges for Credibility in Modern Machine Learning](https://mlsanity.com/paper/2011.03395/) (2020)
- [Confident Learning: Estimating Uncertainty in Dataset Labels](https://mlsanity.com/paper/1911.00068/) (2019)
- [On Fairness and Calibration](https://mlsanity.com/paper/1709.02012/) (2017)
- [Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairness](https://mlsanity.com/paper/1711.05144/) (2017)
- [Persistent Anti-Muslim Bias in Large Language Models](https://mlsanity.com/paper/2101.05783/) (2021)
- [Fairness in Machine Learning: A Survey](https://mlsanity.com/paper/2010.04053/) (2020)
- [Fairness Without Demographics in Repeated Loss Minimization](https://mlsanity.com/paper/1806.08010/) (2018)
- [Fairness in Criminal Justice Risk Assessments: The State of the Art](https://mlsanity.com/paper/1703.09207/) (2017)
- [Empirical Risk Minimization under Fairness Constraints](https://mlsanity.com/paper/1802.08626/) (2018)
- [Societal Biases in Language Generation: Progress and Challenges](https://mlsanity.com/paper/2105.04054/) (2021)
- [Delayed Impact of Fair Machine Learning](https://mlsanity.com/paper/1803.04383/) (2018)
- [Generative Language Models Exhibit Social Identity Biases](https://mlsanity.com/paper/2310.15819/) (2023)
- [Large Language Models Still Exhibit Bias in Long Text](https://mlsanity.com/paper/2410.17519/) (2024)
- [Inherent Limitations of AI Fairness](https://mlsanity.com/paper/2212.06495/) (2022)
- [BiasFilter: An Inference-Time Debiasing Framework for Large Language Models](https://mlsanity.com/paper/2505.23829/) (2025)
- [Metamorphic Testing for Fairness Evaluation in Large Language Models: Identifying Intersectional Bias in LLaMA and GPT](https://mlsanity.com/paper/2504.07982/) (2025)
- [Fairness Overfitting in Machine Learning: An Information-Theoretic Perspective](https://mlsanity.com/paper/2506.07861/) (2025)

## Abstract (arXiv)

In this paper, we establish a set of theoretical impossibility results, termed the No-Free-Fairness theorems, that identify three fundamental sources of disparity in learning systems. First, we show that when a task exhibits irreducible cost on a subgroup, any decision rule must trade off overall performance with disparity, yielding an inherent fairness--cost frontier. Second, we prove that even in ideal, noise-free settings where a perfectly fair and accurate solution exists, finite-sample learning alone induces nontrivial subgroup disparity, ruling out distribution-free fairness guarantees. More seriously, enforcing strict relative fairness creates a statistical bottleneck: achieving low cost may require exponentially many samples. Third, we show that limitations of the model class can independently induce disparity: if the model cannot represent accurate solutions for a subgroup, fairness remains unattainable regardless of data or training procedure. Overall, these results demonstrate that unfairness is not solely a consequence of biased data or suboptimal optimization, but arises from the intrinsic structure of decision problems, the constraints of finite data, and the expressivity of models. Our framework applies broadly beyond standard supervised learning, and suggests that achieving fairness requires explicit trade-offs and should be treated as a core design consideration.