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.
Figures & tables
Objects
Accuracy notion
predictor R~:X→Y , decision rule ρ:Y→{0,1}
MAD: On every group, the positive-decision rate induced by applying ρ to R~ matches that induced by applying ρ to R∗ .
action function h:X→{0,1}
MAC: On every group, the positive-classification rate of h matches that of the loss-minimizing action function.
Table 1: New accuracy notions: Multi-Accuracy-on-Decision (MAD, Equation 1 ) and Multi-Accuracy-on-Classification (MAC, Equation 2 ).
Figure 1: Positive and negative results. MC: Multi-Calibration, MA: Multi-Accuracy, MAD: Multi-Accuracy-on-Decision, MAC: Multi-Accuracy-on-Classification. The top row contains properties defined over a predictor and the bottom row contains properties defined over the action function obtained by applying a decision rule. A green arrow from X to Y means that satisfying X implies satisfying Y . A green dashed arrow from X to Y means that applying a decision rule to a predictor satisfying X yields an action function satisfying Y . A red arrow between X and Y means that achieving both simultaneously is computationally hard. The implication marked (∗) holds for affine decision rules, and the impossibility marked (∗∗) holds for rules that are far from affine. The dashed implication from MAD to MAC additionally assumes that Nature is deterministic.
Figure 2: Choice in how to use a predictor. While a single predictor may enable both loss minimization and MAC, these goals cannot always be achieved simultaneously. This leads to two distinct paths: applying the loss-minimizing decision rule to the full distribution R~ to directly minimize loss (left), or first sampling from R~ and then applying the decision rule to achieve MAC (right). The MAC guarantee for the right-hand path assumes that Nature is deterministic.
Algorithmic fairness studies how automated decisions distribute errors, opportunities, and harms across groups, and how to measure and reduce disparities.
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.
Alireza Fallah, Michael I. Jordan, Annie Ulichney
Department of Computer Science and Ken Kennedy Institute, Rice University · Departments of Electrical Engineering and Computer Sciences and Statistics, University of California, Berkeley; Inria Paris · Department of Statistics, University of California, Berkeley
Ensuring fair and equitable treatment across diverse groups, particularly in multi-class classification tasks, poses a significant challenge due to the persistent biases inherent in machine learning models. Most existing bias mitigation techniques are tailored to binary settings, and the presence of multi-dimensional outputs and complex fairness mechanisms makes their extension to multi-class scenarios neither straightforward nor effective. In this paper, we investigate two fundamental, unresolved challenges in fair classification: (i) characterizing the optimal accuracy-fairness frontier in multi-class settings, and (ii) designing practical algorithms that attain this optimum in different training phases. To tackle these challenges, we first specify an analytically tractable probabilistic formulation of the optimal classifier under fairness constraints. Building upon this, we propose two attribute-blind algorithms to enforce fairness requirements in practice: an in-processing approach for fairness intervention during training via the reduction approach, and a post-processing approach for fine-tuning output probabilities with plug-in estimation. Theoretical analysis reveals that both methods converge to the optimal accuracy-fairness Pareto frontier. Experiments conducted on multiple datasets demonstrate the superior performance of our methods in balancing accuracy and fairness.
Li Zhang, Yuyuan Li, XiaoHua Feng +3
College of Computer Science and Technology, Zhejiang University · School of Communication Engineering, Hangzhou Dianzi University
Omniprediction is a learning guarantee which requires a single predictor to be competitive relative to the best hypothesis from a benchmark class for any loss chosen from a family of loss functions. Loss Outcome Indistinguishability (loss OI for short) is a stronger notion that implies omniprediction. It requires the predicted distribution on labels to be indistinguishable from the true distribution to tests that depend on the loss functions and the benchmark class. Multiaccuracy and multicalibration are multigroup fairness notions that generalize classical notions of calibration and accuracy in expectation. Most known learning algorithms for omniprediction (both for the standard notion and for strengthenings like loss OI) rely on some version of these multigroup fairness notions, or on an intermediate notion called calibrated multiaccuracy. We ask if this is necessary: Does omniprediction require some form of multigroup fairness? We show that the answer is no for (plain) omniprediction, and yes for loss OI. First, a sequence of works shows that multicalibration or calibrated multiaccuracy imply omniprediction. We rule out even a weak converse, by showing that omniprediction for proper losses does not imply even accuracy in expectation, a much weaker notion than any of calibration, multiaccuracy, or multicalibration. Second, prior work showed how to achieve loss OI from a combination of calibration and multiaccuracy. We show a converse: loss OI is equivalent to a form of calibrated multiaccuracy.