cs.LGNov 4, 2026

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

Authors: Mohit Sharma, Okan Koç, Amit Deshpande, Takashi Ishida, Gang Niu, Rajiv Ratn Shah, Masashi Sugiyama

Organizations: IIIT Delhi · RIKEN-AIP · Microsoft Research · The University of Tokyo · 

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.

Figures & tables

Explore similar work

May 22, 2025

Accuracy vs. Accuracy: Computational Tradeoffs Between Classification Rates and Utility

We revisit the foundations of fairness and its interplay with utility and efficiency in settings where the training data contain richer labels, such as individual types, rankings, or risk estimates, rather than just binary outcomes. In this context, we propose algorithms that achieve stronger notions of evidence-based fairness than are possible in standard supervised learning. Our methods support classification and ranking techniques that preserve accurate subpopulation classification rates, as suggested by the underlying data distributions, across a broad class of classification rules and downstream applications. Furthermore, our predictors enable loss minimization, whether aimed at maximizing utility or in the service of fair treatment. Complementing our algorithmic contributions, we present impossibility results demonstrating that simultaneously achieving accurate classification rates and optimal loss minimization is, in some cases, computationally infeasible. Unlike prior impossibility results, our notions are not inherently in conflict and are simultaneously satisfied by the Bayes-optimal predictor. Furthermore, we show that each notion can be satisfied individually via efficient learning. Our separation thus stems from the computational hardness of learning a sufficiently good approximation of the Bayes-optimal predictor. These computational impossibilities present a choice between two natural and attainable notions of accuracy that could both be motivated by fairness.
Aug 25, 2025

The Statistical Fairness-Accuracy Frontier

We study fairness-accuracy tradeoffs when a single predictive model must serve multiple demographic groups. A useful tool for understanding this tradeoff is the fairness-accuracy (FA) Pareto frontier, which characterizes the set of models that cannot be improved in either fairness or accuracy without worsening the other. While characterizing the FA frontier requires full knowledge of the data distribution, we focus on the finite-sample regime, quantifying how well a designer can approximate any point on the frontier from limited data and bounding the worst-case gap. In particular, we derive worst-case-optimal estimators that depend on the designer's knowledge of the covariate distribution. For each estimator, we characterize how finite-sample effects asymmetrically impact each group's welfare and identify optimal sample allocation strategies. Finally, we provide uniform finite-sample bounds along the entire FA frontier, quantifying finite-sample deviations across alternative fairness-accuracy tradeoffs.
Oct 19, 2026

Fair Regression under Approximate Demographic Parity

Exact demographic parity requires the same prediction distribution across sensitive groups. In regression, this can be too restrictive and reduce predictive accuracy. We instead bound every pairwise Wasserstein distance between group-specific prediction distributions by a chosen tolerance, allowing the groups to differ while keeping fairness tunable. On the real line, the prediction and constrained transport problems have the same infimum. If the transport problem attains this value and suitable Monge maps exist, a deterministic transport-form predictor realizes it. Under a standard one-dimensional condition, the problem becomes a bounded quantile optimization that is convex when the conditional expected loss is convex in prediction. Under squared loss with two positively weighted groups, the W1W_1, W2W_2, and W∞W_\infty constraints yield soft-thresholding, shrinkage, and clipping. Under the stated conditions, we establish rates for the known-cost plug-in estimator. When the cost is unavailable, we describe an observed-loss computational proxy. Synthetic and California 2018 ACS studies illustrate the tunable fairness-accuracy trade-off and distinguish calibration feasibility from held-out fairness and accuracy.