Search papers, labs, and topics across Lattice.
This paper establishes the No-Free-Fairness theorems, revealing that inherent disparities in learning systems stem from three fundamental sources: irreducible subgroup costs, finite-sample learning limitations, and model expressivity constraints. The authors demonstrate that even in optimal conditions, enforcing fairness leads to significant statistical bottlenecks, necessitating exponentially more samples for low-cost solutions. Ultimately, the findings suggest that unfairness is deeply rooted in the decision problem's structure, rather than merely arising from biased data or poor optimization practices.
Achieving fairness in learning systems requires explicit trade-offs, as inherent disparities are dictated by the very structure of decision problems and model limitations.
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.
