Estimating the Best Accuracy AI Can Achieve Under Fairness Constraints

A machine-learning system can outperform its competitors without approaching the best performance theoretically possible. That distinction becomes especially important when developers must balance predictive accuracy with constraints on differences between groups.

Mohit Sharma and colleagues propose estimating that underlying limit directly from soft labels: probabilities of a positive outcome, paired with group membership. Their paper, Practical Estimation of the Bayes Optimal Fairness-Accuracy Tradeoff with Soft Labels, was posted to arXiv on November 4, 2026. The repository lists this preprint version as accepted at NeurIPS 2026.

The contribution is primarily a benchmarking method, not a new predictive model or a guarantee that a deployed system will be fair.

What counts as the best possible classifier?

The starting point is the Bayes error: the smallest average classification error achievable for a specified data distribution and available information. Even an ideal predictor can make mistakes when those inputs do not determine the outcome with certainty.

For binary classification, if the true probability of a positive outcome is known, the ordinary accuracy-maximizing rule predicts positive whenever that probability is at least one-half. Averaging the smaller of the positive and negative probabilities gives the corresponding minimum error.

Fairness constraints change the problem. The authors examine two definitions. Demographic parity limits differences in the proportion receiving positive predictions across groups. Equal opportunity limits differences in true-positive rates—the proportion of actual positive cases correctly identified within each group.

These definitions are not interchangeable, and neither captures every concern about discrimination. The best achievable error depends on the chosen metric, the permitted disparity and the underlying population. Tightening a constraint can increase that minimum error, although a tradeoff is not inevitable if the unconstrained optimum already satisfies it.

Estimating a boundary without the original features

Building on earlier characterizations of optimal fair classifiers, the researchers use group-specific probability thresholds. Adjusting these thresholds changes both prediction error and group disparity. A parameter called lambda controls that adjustment, allowing different points on the fairness–accuracy boundary to be examined.

The new estimation procedure needs probability scores and group identifiers, but not the original images, records or other input features. It splits the sample into two independent parts: one estimates population quantities and decision thresholds; the other estimates the resulting error and disparity.

This separation matters because the thresholds themselves are uncertain. Treating estimated thresholds as though they were known exactly would overlook a source of statistical error.

The authors derive expressions and estimators for threshold values, cost-sensitive prediction risk, ordinary classification error and fairness disparity. Under their assumptions, they establish consistency: estimates approach the target quantities as sample sizes grow. They also give bounds on bias and the sample sizes needed for specified precision.

Those guarantees concern the estimation stage. If probabilities come from a trained model, producing those scores still requires modeling work.

What the experiments show

The team tests the approach in three settings: synthetic Gaussian data with analytically available probabilities, CIFAR-10H image annotations and the Adult income dataset. For Adult, logistic regression supplies imperfect probability scores.

CIFAR-10H requires an important qualification. The researchers construct binary prediction tasks and artificial groups by partitioning image categories. These groups are not demographic populations, so this experiment tests the statistical machinery rather than demonstrating demographic fairness in an image application.

Across five runs, the authors report comparatively low variability and estimated error–disparity curves generally below those produced by several comparison methods. A lower curve here represents a benchmark suggesting that less error may be attainable at a comparable disparity—not necessarily a trained system delivering that performance.

There is an exception: MIFPO sometimes produces a still-lower curve. The authors attribute this to its optimization of a different lower-bound objective, rather than the same Bayes-optimal tradeoff. The comparison therefore should not be read as an unqualified victory over every baseline.

Where the guarantees stop

The main theory assumes clean soft labels: true conditional outcome probabilities, not merely confident model predictions. Robustness with logistic-regression scores is experimental evidence, not a general proof of reliability under noisy or miscalibrated probabilities.

The analysis also concerns binary outcomes and two known groups, with additional continuity and bounded-density assumptions. Small groups or rare positive outcomes can substantially increase sample requirements. Group-blind estimation remains an extension rather than an established result here.

Another limitation concerns the complete estimated curve. The stated guarantees apply at a fixed lambda. The authors explain how a predetermined grid can receive joint error control, but acknowledge that their adaptive bisection search requires additional uniform analysis.

The practical value is consequently conditional: with sufficiently trustworthy probabilities and appropriate assumptions, the method could help distinguish room for algorithmic improvement from limits imposed by a particular statistical fairness constraint. It does not establish that every observed accuracy loss is unavoidable, or that satisfying one fairness metric resolves the broader question of equitable decisions.