Practical Estimation of the Bayes Optimal Fairness-Accuracy Tradeoff with Soft Labels

AI summary

Overview

• Research area: Fair machine learning and statistical learning theory, specifically Bayes error / Bayes risk estimation and constrained (multi-objective) classification.
• Technical level: Advanced. The paper is theory-heavy, with lemmas, consistency proofs, bias bounds and sample-complexity rates, plus an algorithmic procedure and empirical comparisons.
• Scope (one sentence): The paper derives and empirically demonstrates instance-free estimators, built only from soft labels and group attributes, for the best achievable error rate under demographic-parity or equal-opportunity fairness constraints, thereby tracing the Bayes optimal fairness-accuracy tradeoff curve.

What This Paper Is About

For any data distribution there is a floor on classification error, the Bayes error, and prior work showed it can be estimated from soft labels (predicted positive-class probabilities) alone, without features or model training. That theory breaks down once a fairness constraint is imposed, because the optimal classifier is no longer a fixed 1/2 threshold but a group-dependent, distribution-dependent threshold that shifts with the allowed unfairness δ. The paper's goal is to compute the corresponding fair Bayes error, and the whole fairness-accuracy tradeoff curve, from soft labels plus group information only.

Key Contributions

1. A bound that decouples unfairness from the threshold correction. Lemma 3.8 shows that when the unconstrained classifier's disparity is positive, the dual parameter λ only needs to range over [0, λ_max] with λ_max = 1 / inf_(x,a)|w(x,a)|, and symmetrically for a negative disparity; for Equal Opportunity λ_max = max_a π_{1a} and for Demographic Parity λ_max = max_a π_a. This makes it possible to interpolate the entire Pareto frontier without solving a separate optimization for λ*(δ).
2. Consistent, instance-free estimators of the fair thresholds. Theorem 4.1 gives threshold estimators for Demographic Parity and Equal Opportunity built only from soft labels and group indicators, and proves consistency, explicit bias bounds (including an exponential tail term), and sample-complexity conditions for a given accuracy ε and confidence δ.
3. A generalization of Bayes error estimation to cost-sensitive risk. Theorem 4.3 gives the closed form β_CS = E[min((1-α_A)η(X,A), α_A(1-η(X,A)))], a consistent estimator, and a finite-sample bound, extending the constant-1/2 results of prior Bayes error work; Theorems 4.4, 4.5 and 4.6 then add bias and sample-complexity guarantees when the thresholds themselves are estimated, for the cost-sensitive risk, the expected 0-1 error, and the expected unfairness respectively.
4. A bisection-search algorithm and an empirical lower-bound benchmark. Algorithm 1, inspired by the fair Bayes optimal classifier algorithm of Zeng et al. (2024) but using only soft labels and no instances, traces the tradeoff curve; experiments on synthetic data from Zeng et al. (2022) and on real datasets show the estimated curve lower-bounds those of Delaney et al. (2024), Kozdoba et al. (2024) and the differentiable fair-classification objectives of Buyl et al. (2023), including when the soft scores are noisy and derived from a Logistic Regression model on the Adult dataset (Lichman et al., 2013).

Main Findings

• Fair optimal classifiers are shifted thresholds. Under Assumption 2.1, the Bayes optimal δ-fair classifier takes the form g_δ(x,a) = I(η(x,a) ≥ 1/2 + (λ*(δ)/2)·w(x,a)); for Demographic Parity the threshold becomes 1/2 + (2a-1)λ*(δ)/(2π_a) and for Equal Opportunity it becomes 1/(2 − (2a-1)λ*(δ)/π_{1a}). Because the threshold is no longer 1/2, existing Bayes error estimators do not transfer.
• The Pareto frontier is fully covered by a λ interval. Proposition 3.9 states that any classifier on the Pareto frontier equals g_λ for some λ, and Lemma 3.8 supplies the finite interval of λ values that suffices, which is what legitimizes a bisection search.
• Threshold estimation is provably consistent but non-uniform in unfairness. The bias bounds for the threshold estimators scale with |λ| (and, for Equal Opportunity, with 1/τ² where τ lower-bounds the denominator), so the number of samples needed "may change drastically depending on the degree of correction and the relative group proportions."
• Cost-sensitive Bayes risk remains estimable with a simple plug-in. The estimator β̂_CS averages min((1-α_i)c_i, α_i(1-c_i)) over soft labels and converges in probability to β_CS; with probability at least 1 − δ its absolute error is at most (1/4)·sqrt((1/N_β) log(2/δ)).
• Two-stage sample splitting is needed. N samples are split into N_α soft labels for threshold estimation and N_β for risk and unfairness estimation, with N = N_α + N_β. Sample requirements for the cost-sensitive risk are N_β ≥ (1/(8ε²)) log(4/δ) with N_α = O((λ²/ε²) log(1/δ)) for Demographic Parity and O((λ²/(τ⁴ε²)) log(1/δ)) for Equal Opportunity.
• Error-rate estimation carries the Lipschitz constants. For the expected 0-1 risk the requirement rises to N_β ≥ (18/ε²) log(6/δ), with N_α = O((λ² max{L_0²,L_1²}/ε²) log(1/δ)) for Demographic Parity and O((λ² max{L_0²,L_1²}/(ε²τ⁴)) log(1/δ)) for Equal Opportunity, where L_a bounds the group-conditional density of the soft labels.
• The estimated curve is a lower bound on competitors. In the reported figures the proposed estimate (green curve) sits below competing fairness-tradeoff algorithms, and where it does not (for example the algorithm of Kozdoba et al. (2024)) the paper attributes this to that algorithm optimizing a different lower bound on the Pareto frontier.
• Robustness to noisy soft labels. On the Adult dataset the soft scores were generated by a Logistic Regression model on hard labels, and the method still lower-bounded all other fairness tradeoff algorithms tested.
• No numerical tradeoff values are reported in the provided text. The paper's figures compare curves qualitatively; specific error rates or unfairness numbers per dataset are not given in the content available here.

Methodology in Plain English

The starting point is that a soft label c is already an estimate of the probability that the true label is 1, so a great deal can be computed from a list of (soft label, group) pairs without ever seeing the inputs. For ordinary classification the best possible error is just the average of min(c, 1 − c).

Fairness complicates this because the best fair classifier uses a different cutoff per group, and that cutoff depends on quantities of the distribution (group sizes and group positive rates) plus a single tuning parameter λ that controls how much fairness is being bought. The authors first show that only a bounded, computable range of λ values matters, so the whole tradeoff curve can be swept rather than optimized over an unbounded space.

They then build plug-in estimators: replace the unknown group proportions and positive rates with averages over a first chunk of soft labels, giving estimated per-group cutoffs; replace the unknown expectations in the risk and unfairness formulas with averages over a second chunk. Because each estimate is a smooth or well-behaved function of empirical averages, the authors can prove the estimates converge, bound how far off they are on average, and state how many samples make the error small with high probability. A bisection search over λ then walks along the curve until the estimated unfairness meets the requested tolerance δ, yielding the whole frontier in one pass.

The empirical protocol feeds the method only soft scores and group labels and plots its curve against curves produced by recent fairness-tradeoff and differentiable fair-classification methods; because the method targets a theoretical floor, its curve should lie beneath methods that actually train classifiers.

Why This Matters

• Research impact: The paper supplies the fairness analogue of the Bayes error as a diagnostic. Just as Bayes error estimation is used to benchmark trained models and detect overfitting, the estimated fair Bayes risk gives a target against which any fair classifier can be judged, and the authors argue that future fair-learning methods "should always close the gap" to this estimated floor.
• Credit scoring and lending: Models that approve or reject applicants must satisfy near-equal approval or true-positive rates across groups; the tradeoff curve tells a practitioner how much accuracy a given fairness tolerance actually costs, before any model is trained.
• Hiring and admissions screening: Ranking or shortlisting systems need comparable selection rates across demographic groups, and this method quantifies the accuracy ceiling once such a constraint is imposed.
• Healthcare resource allocation: Risk models that flag patients for extra care are often assessed on equal true-positive rates across groups (the Equal Opportunity constraint studied here), and the frontier gives the best achievable error under that requirement.
• Facial analysis and criminal-justice risk assessment: The disparate error patterns documented in prior fairness literature (Angwin et al., 2016; Buolamwini and Gebru, 2018; Barocas et al., 2023) motivate knowing whether a deployed model is far from the achievable optimum or already near it.
• Industry relevance: Because the method is model-free and consumes only soft scores plus a sensitive attribute, it can be run as an audit on top of an existing production model's probability outputs, with no retraining and no access to raw features — attractive for privacy-sensitive or vendor-supplied models.

Future Directions

• Extending beyond binary attributes and two groups. The theory is developed for A ∈ {0, 1} and binary labels; generalizing the threshold bounds and estimators to multiple groups and multi-class problems is left open.
• Other fairness metrics and cost-sensitive settings. The paper handles Demographic Parity and Equal Opportunity explicitly and notes the proof technique can be generalized to other cost-sensitive applications (Koyejo et al., 2014; Singh and Khim, 2022), but those instantiations are not worked out.
• Alternative Bayes error estimators. Methods that estimate Bayes error indirectly (Berisha et al., 2015; Noshad et al., 2019; Theisen et al., 2021; Renggli et al., 2021) are explicitly named as future work to bring under constrained optimization, since they do not rely on soft labels or thresholding rules.
• Tighter behavior under noisy or miscalibrated soft labels. The experiments include scores from a Logistic Regression model on hard labels, but a formal treatment of how label noise and miscalibration propagate into the estimated frontier, and how many samples are then required, is not provided.

Target Audience

Researchers and graduate students in fair machine learning and statistical learning theory who are familiar with Bayes error, cost-sensitive classification and threshold characterizations of fair optimal classifiers; fairness practitioners and ML engineers auditing deployed models who want a model-free benchmark computed from probability outputs and group labels; and reviewers or method developers who need a principled lower bound against which new fair-classification algorithms can be measured.

Authors’ abstract

There is a fundamental limit to the best prediction error of any model for a given data distribution. In classification, the Bayes error quantifies this limit and serves as both a benchmark for trained models and a criterion to detect overfitting. The state-of-the-art Bayes error estimation techniques for binary classification use only soft labels (positive class probabilities) and require no input features or auxiliary training. We extend such notions to constrained classification problems, such as fairness. Fair classification is an important case of constrained or multi-objective classification. It requires a model not only to be accurate but also to yield fair outcomes (equal or near-equal true positive rates) across different demographic groups (e.g., race and gender). This leads to an inherent fairness-accuracy tradeoff or a Pareto frontier that is used to compare fair classifiers against each other. The focus of our work is to estimate the fundamental limit for this fairness-accuracy tradeoff. We derive an explicit expression for the fair Bayes error rate (i.e., best achievable error rate subject to given fairness constraints), and construct consistent, instance-free estimators for it using only soft labels and group information. We provably bound the bias and the sample complexity of our estimators. Empirically, our method produces a robust, low-variance estimate of the optimal fairness-accuracy tradeoff curve, even when the soft labels are noisy and derived from a classification model on hard labels.