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

• URL: http://arxiv.org/abs/2606.17810v1
• Date: Tue, 16 Jun 2026 11:37:52 GMT
• Title: No-Free-Fairness: Fundamental Limits and Trade-offs in Learning Systems
• Abstract summary: We show that when a task exhibits irreducible cost on a subgroup, any decision rule must trade off overall performance with disparity.<n>We show that even in ideal, noise-free settings where a perfectly fair and accurate solution exists, finite-sample learning alone induces nontrivial subgroup disparity.
• Score: 3.2356128177594363
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: 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.

Related papers

• Post-hoc Provider Fairness Adaptation via Hierarchical Exposure Alignment [54.58748721533078]
  Post-hoc Fairness Adaptation (PFA) is a lightweight framework that equips a frozen recommender with a fairness adapter.<n>It learns personalized additive score adjustments from user-item embeddings to steer provider exposure toward fairness.<n>PFA achieves substantial fairness gains with negligible accuracy loss, consistently outperforming strong baselines.
  arXiv  Detail & Related papers  (2026-05-02T16:32:52Z)
• On the use of graph models to achieve individual and group fairness [0.6299766708197883]
  We provide a theoretical framework based on Sheaf Diffusion to leverage tools based on dynamical systems and homology to model fairness.<n>We present a collection of network topologies handling different fairness metrics, leading to a unified method capable of dealing with both individual and group bias.<n>The paper showcases the performance of the proposed models in terms of accuracy and fairness.
  arXiv  Detail & Related papers  (2026-01-13T18:17:43Z)
• Fairness-Aware Reinforcement Learning (FAReL): A Framework for Transparent and Balanced Sequential Decision-Making [41.53741129864172]
  Equity in real-world sequential decision problems can be enforced using fairness-aware methods.<n>We propose a framework where multiple trade-offs can be explored.<n>We show that our framework learns policies that are more fair across multiple scenarios, with only minor loss in performance reward.
  arXiv  Detail & Related papers  (2025-09-26T11:42:14Z)
• FedFACT: A Provable Framework for Controllable Group-Fairness Calibration in Federated Learning [23.38141950440522]
  We propose a controllable federated group-fairness calibration framework, named FedFACT.<n>FedFACT identifies the Bayes-optimal classifiers under both global and local fairness constraints.<n>We show that FedFACT consistently outperforms baselines in balancing accuracy and global-local fairness.
  arXiv  Detail & Related papers  (2025-06-04T09:39:57Z)
• Towards Harmless Rawlsian Fairness Regardless of Demographic Prior [57.30787578956235]
  We explore the potential for achieving fairness without compromising its utility when no prior demographics are provided to the training set. We propose a simple but effective method named VFair to minimize the variance of training losses inside the optimal set of empirical losses.
  arXiv  Detail & Related papers  (2024-11-04T12:40:34Z)
• Finite-Sample and Distribution-Free Fair Classification: Optimal Trade-off Between Excess Risk and Fairness, and the Cost of Group-Blindness [14.421493372559762]
  We quantify the impact of enforcing algorithmic fairness and group-blindness in binary classification under group fairness constraints. We propose a unified framework for fair classification that provides distribution-free and finite-sample fairness guarantees with controlled excess risk.
  arXiv  Detail & Related papers  (2024-10-21T20:04:17Z)
• Fair Few-shot Learning with Auxiliary Sets [53.30014767684218]
  In many machine learning (ML) tasks, only very few labeled data samples can be collected, which can lead to inferior fairness performance. In this paper, we define the fairness-aware learning task with limited training samples as the emphfair few-shot learning problem. We devise a novel framework that accumulates fairness-aware knowledge across different meta-training tasks and then generalizes the learned knowledge to meta-test tasks.
  arXiv  Detail & Related papers  (2023-08-28T06:31:37Z)
• DualFair: Fair Representation Learning at Both Group and Individual Levels via Contrastive Self-supervision [73.80009454050858]
  This work presents a self-supervised model, called DualFair, that can debias sensitive attributes like gender and race from learned representations. Our model jointly optimize for two fairness criteria - group fairness and counterfactual fairness.
  arXiv  Detail & Related papers  (2023-03-15T07:13:54Z)
• Arbitrariness and Social Prediction: The Confounding Role of Variance in Fair Classification [31.392067805022414]
  Variance in predictions across different trained models is a significant, under-explored source of error in fair binary classification. In practice, the variance on some data examples is so large that decisions can be effectively arbitrary. We develop an ensembling algorithm that abstains from classification when a prediction would be arbitrary.
  arXiv  Detail & Related papers  (2023-01-27T06:52:04Z)
• Pushing the limits of fairness impossibility: Who's the fairest of them all? [6.396013144017572]
  We present a framework that pushes the limits of the impossibility theorem in order to satisfy all three metrics to the best extent possible. We show experiments demonstrating that our post-processor can improve fairness across the different definitions simultaneously with minimal model performance reduction.
  arXiv  Detail & Related papers  (2022-08-24T22:04:51Z)
• Fairness in Semi-supervised Learning: Unlabeled Data Help to Reduce Discrimination [53.3082498402884]
  A growing specter in the rise of machine learning is whether the decisions made by machine learning models are fair. We present a framework of fair semi-supervised learning in the pre-processing phase, including pseudo labeling to predict labels for unlabeled data. A theoretical decomposition analysis of bias, variance and noise highlights the different sources of discrimination and the impact they have on fairness in semi-supervised learning.
  arXiv  Detail & Related papers  (2020-09-25T05:48:56Z)
• Beyond Individual and Group Fairness [90.4666341812857]
  We present a new data-driven model of fairness that is guided by the unfairness complaints received by the system. Our model supports multiple fairness criteria and takes into account their potential incompatibilities.
  arXiv  Detail & Related papers  (2020-08-21T14:14:44Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.