acceptodds
Under review as a conference paper at ICLR 2027

Why are Biases Not Rare in AI Systems? Theoretical impossibility and Trade-offs

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 imperfect algorithm, 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.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
AI fairness, impossibility, tradeoff

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_iohBOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper presents a series of three impossibility results related to fairness in machine learning. The authors identify three separate sources of disparity and analyze their impact:

  1. Task-specific (Theorem 2.1): they show that, given a problem that is inherently uncertain for a subgroup, no model can achieve both exact parity and Bayes-optimal performance.
  2. Algorithmic and Statistical (Theorem 2.2): for a binary classification task with a 0-1 loss, the authors provide a minimax lower bound on the "cost ratio" quantity εS=abˉ(hS)/max⁡(ab(hS),c)\varepsilon_S = a_{\bar b}(h_S)/\max ( a_b(h_S), c ) and the overall population risk; they also argue that overall risk and fairness are in conflict when learning from finite data.
  3. Structural (Theorem 2.3). In a similar result to Theorem 2.1, they provide a lower bound on the performance of a model that satisfies exact parity based on the model's capacity.

The authors place their work in the context of well-known prior impossibility results (e.g., Kleinberg et al., 2017; Chouldechova, 2017). The paper is purely theoretical and contains no experiments.

Critical strengths
  1. The paper identifies significant impossibility results in fair machine learning.
  • Theorem 2.1 establishes the price of parity, giving a task-dependent lower bound on the performance of any model that achieves exact parity across subgroups.
  • Theorem 2.3 obtains a similar result with respect to model capacity.
  1. The paper is clearly written and easy to parse, with well-structured proofs.
Critical weaknesses

The sample complexity and convergence results, presented among the main contributions of the paper, are not supported.

The results are presented in detail in Section 2.3.1, and are derived from Corollary 2.2, which states that

inf⁡Asup⁡P∈Preal(pb)ES[a(hS)]≥1−pb4c(n)for every n and c(n)∈(0,1]\inf_{\mathcal{A}} \sup_{P \in \mathcal{P}_{real}(p_b)} \mathbb{E}_S[a(h_S)] \geq \frac{1-p_b}{4} c(n) \quad \textbf{for every } n \text{ and } c(n) \in (0, 1]

The authors then claim, e.g., that "enforcing a relatively strict and slowly decaying floor (e.g., $ c(n) = 1/ \log n $) yields correspondingly slow convergence rates", and "achieving vanishing cost necessitates c(n)→0c(n) \rightarrow 0".

However, the left-hand side of Corollary 2.2 does not depend on c(n)c(n). Since the statement of the corollary holds for any choice of c(n)∈(0,1]c(n) \in (0, 1], we may substitute c(n)=1c(n) = 1, which gives

inf⁡Asup⁡P∈Preal(pb)ES[a(hS)]≥1−pb4\inf_{\mathcal{A}} \sup_{P \in \mathcal{P}_{real}(p_b)} \mathbb{E}_S[a(h_S)] \geq \frac{1-p_b}{4}

Neither side depends on c(n)c(n). Same result can be obtained by combining (28) and (30) in Theorem B.1, then taking the sup and inf on both sides as in the existing proof.

This shows that uniform statistical consistency over realizable distributions $ \sup_{P \in \mathcal{P}_{real}(p_b)} \mathbb{E}[a(h_s)] \rightarrow 0 $ is impossible for any learner regardless of the choice of c(n)c(n). As a consequence, the sample complexity would be infinite for any $ \nu < \frac{1-p_b}{4} $. All results in 2.3.1 concerning the convergence rate and sample complexity depend on the premise that varying c(n)c(n) influences the minimax risk on the left-hand side, when it does not.

Minor issues:

  • Note that the definition of statistical consistency after Corollary 2.2 does not refer to the uniform-over-realizable-distributions, or indeed "distribution-free" consistency, as it lacks the supremum over distributions.
Questions for authors

Regarding the sample complexity and convergence results (see Weaknesses):

  1. The left-hand side of Corollary 2.2 is independent of the regularization parameter $ c $ or $ c(n) $. Could the authors clarify if $ c $ is meant to constrain the set of learners in the statement of the Corollary? If so, this should be stated explicitly.

  2. Theorem B.1 yields $ \inf_{\mathcal{A}} \sup_{P \in \mathcal{P}_{real}(p_b)} \mathbb{E}_S[a(h_S)] \geq \frac{1-p_b}{4} $. This is a stricter lower bound than that in Corollary 2.2, overriding the sample complexity results of Section 2.3.1. Could the authors clarify how are the sample complexity results obtained?

  3. Lines 310, 311 state:

Bounding the maximum possible disparity requires a non-vanishing c(n)c(n)''.

This claim is not substantiated explicitly. One can suppose this refers to the trivial upper bound

εS=abˉ(hS)max⁡(ab(hS),c(n))≤abˉ(hS)c(n)≤1c(n)\varepsilon_S = \frac{a_{\bar b}(h_S)}{\max ( a_b(h_S),c(n))} \leq \frac{a_{\bar b}(h_S)}{c(n)} \leq \frac{1}{c(n)}

However, as evident from the derivation, this result does not put a bound on the actual cost ratio $ \frac{a_{\bar b}(h_S)}{ a_b(h_S) } $. Could the authors state how exactly is the maximum possible disparity bounded by c(n)c(n) in this context?

Conclusion

I would be willing to raise my score if the authors could either (i) remove the sample complexity and convergence results from the paper entirely (in my opinion, the contributions of Theorem 2.1 and 2.3 are valuable enough to warrant acceptance), or indeed (ii) provide corrected sample complexity and convergence estimates, which would enhance the paper's contributions even more.

Reviewer_nS3UOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

The authors try to argue that algorithmic disparity stems from structural, sample size, and architectural constraints.. However, I think the technical contribution is zero. The so-called core theoretical results are just a repackaging of standard statistical learning concepts via basic algebra, under a new fairness metric. In addition, the paper based on "worst-case minimax bounds" and unrealistic adversarial assumptions. The authors claim exponential sample complexity is an artifact of extreme situations. Last, there is no experiment or code, making practical applicability and the work unsubstantiated.

Critical strengths

The research problem this work focused on is good and popular

Critical weaknesses
  1. It seems like coursework, no related work, no experiment, not comparing with recent works.

  2. The proposed theory is practically useless. Its bounds depend on an arbitrary relevance threshold c, which lacks alignment with "real-world" guidance or human fairness.

  3. I dont think the proposed theoretical bounds can explain bias in LLMs. Its proofs assume a worst-case, distribution-free setting. That setting is not suitable for structured natural language data.

Questions for authors

No other questions, just hope the authors can respond to the weaknesses I claimed

Reviewer_PTe1OpenReview ↗
Rating
2
Confidence
4
Informativeness
1
Presentation
3
Soundness
2
Read review
Paper summary

The paper introduces a set of theoretical impossibility results, called “No-Free-Fairness” theorems, which explain why biases are not rare in AI systems. The main idea is to isolate three sources of unfairness: data, the learning algorithm, and model capacity constraints. The paper also includes comparisons with existing impossibility theories in the model fairness field.

Critical strengths

The paper has several positive aspects:

  • Identifying the fundamental sources of bias and understanding the limits of fair algorithms is always an important topic.
  • The paper's aim to view group fairness through the risk ratio rather than absolute disparity is a well-motivated choice, especially for class-imbalanced scenarios where proportional harm matters.
Critical weaknesses

However, several key aspects of the paper need to be improved or addressed:

  • Related work and novelty: While the paper discusses some accuracy-fairness impossibility theories and convergence guarantees for fair training, it misses several closely related studies (e.g., Chen et al., 2018; Menon & Williamson, 2018; Zhao & Gordon, 2022). For example, Chen et al. (2018) provided insights into group-level disparities based on noise, bias, and variance terms. Additionally, Menon & Williamson (2018) and Zhao & Gordon (2022) demonstrated the trade-offs between group fairness and accuracy, including for ratio-based metrics. Given that these works are closely related to the paper’s main theoretical results, it is somewhat unclear what new fundamental insights the paper’s theories add.
  • Loss-agnostic claims: The paper claims that Theorems 2.1 and 2.3 are “loss agnostic” and can be applied well beyond binary classification (e.g., to regression and generative modeling). However, in the proofs, the results hold for non-negative losses simply because the derivation is a direct algebraic rearrangement of the law of total expectation. The current results do not consider any structure of the input space, loss functions, or model classes. While the discussions in Sections 2.4 and 3 are reasonable, they do not seem to follow quantitatively from the theorems. Thus, it is somewhat unclear how these results provide actionable insights for complex tasks such as generative AI.
  • Lack of empirical validation: The paper does not provide any empirical results or synthetic experiments to support its theoretical findings (Figure 1 is only a schematic illustration). There are not enough supporting details to show how severe or relevant these theoretical bounds are in practical settings. It would be very helpful if the paper could provide more direct experimental illustrations.

References:

  • Chen et al., Why Is My Classifier Discriminatory? NeurIPS 2018
  • Menon & Williamson, The Cost of Fairness in Binary Classification, FAT* 2018
  • Zhao & Gordon, Inherent Tradeoffs in Learning Fair Representations, JMLR 2022
Questions for authors

Questions are included in the above weaknesses section.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.