Demystifying the Optimal Fair Classifier in Multi-Class Classification
Li Zhang, Yuyuan Li, XiaoHua Feng, Jiaming Zhang, Fengyuan Yu, Chaochao Chen · 2026
Read Demystifying the Optimal Fair Classifier in Multi-Class Classification by Li Zhang, Yuyuan Li, XiaoHua Feng, Jiaming Zhang, Fengyuan Yu, Chaochao Chen (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-00656.txt.
Introduction
Zhang and co-authors tackle fair machine learning in this 2026 paper. Their focus is multi-class tasks, where a model picks one label from many, not just two. Bias in such models can treat groups in unequal ways. Most past fixes were built for the two-class case and do not carry over well.
The team first writes down, in exact form, the best fair classifier for this setting. That form maps the best trade-off that accuracy and fairness can reach. They then build two ways to hit that trade-off in practice. One acts while the model trains, and one tunes its output scores after training. Both skip the group label of each case. Tests on several datasets show a strong balance of accuracy and fairness, the authors report.
Catalog record
| CREATOR | Li Zhang, Yuyuan Li, XiaoHua Feng, Jiaming Zhang, Fengyuan Yu, Chaochao Chen |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 152 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.00656
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Demystifying the Optimal Fair Classifier in Multi-Class Classification Li Zhang, Yuyuan Li, XiaoHua Feng, Jiaming Zhang, Fengyuan Yu, Chaochao Chen Abstract 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. ,* 1 Introduction In recent decades, machine learning models have become extensively integrated into decision-making applications in high-stakes domains such as healthcare ( 34 ; 63 ; 25 ) , financial services ( 12 ; 27 ; 18 ) , and criminal justice ( 7 ; 6 ; 60 ) . This trend has motivated a growing body of research focused on developing and assessing fairness to mitigate discrimination in models. In this context, group fairness metrics are frequently employed in practice due to their consistency with the intuition that predictions should not systematically discriminate against any group within the population. Widely used group fairness metrics, such as demographic parity (DP; 20 ), equal opportunity (EOP: 23 ), and Equalized Odds (EO; 23 ), vary in their definition of group-wise disparity. Achieving high predictive performance while simultaneously enforcing group-fairness constraints poses a fundamental problem in multi-class fair learning. Most prior studies demonstrate an inherent trade-off between fairness and accuracy, whereby improving fairness typically comes at the cost of reduced accuracy ( 10 ; 50 ; 53 ; 66 ) . However, despite these empirical and theoretical advances, an explicit characterization of the optimal accuracy-fairness frontier in multi-class settings remains elusive . This difficulty stems from the intrinsically non-decomposable and non-differentiable nature of most group-fairness criteria ( 35 ; 57 ) , which becomes further exacerbated by the multi-dimensional output structure ( 2 ) . Consequently, it is unclear whether the performance degradation arises from intrinsic algorithmic limitations or incidental artifacts, and the Pareto boundary between fairness and accuracy has not been established. In practice, fairness calibration is commonly deployed either during training by modifying the model training objective ( in-processing ; 1 ; 58 ) or after training by adjusting the pre-trained model’s outputs ( post-processing ; 50 ; 10 ; 26 ). The current challenge in multi-class fairness calibration lies in the lack of a systematic and consistent framework for approximating the optimal accuracy-fairness trade-off across different training phases . Existing work typically develops in-processing and post-processing methods in isolation, with most approaches focusing on one paradigm exclusively. Moreover, the in-processing methods predominantly rely on surrogate fairness metrics to design objectives or reweighting methods ( 45 ; 29 ; 58 ) , while the inevitable surrogate gap ( 57 ; 35 ) produces suboptimal performance and undermines convergence stability. For multi-class post-processing, certain advanced methods focus on a single fairness criterion ( 50 ; 16 ) , while others lack a precise characterization of the optimal fair classifier, leaving performance gains unexplored ( 64 ; 47 ) . Hence, it remains an open problem to design algorithms that are applicable to multiple fairness criteria and controllable in different training phases. To address these challenges, we theoretically investigate the Pareto frontier in multi-class fair classification and propose a novel group-fairness calibration framework named OptFair , under which we separately develop an in-processing method and a post-processing method to approximate the optimal accuracy-fairness trade-off. We specify the Bayes-optimal classifier under group-fairness constraints in the multi-class setting and introduce an entropic regularizer to render it analytically tractable. Building on this characterization, we develop optimization strategies that achieve the optimal accuracy-fairness trade-off for any specified level of fairness: the in-processing task is reduced to a sequence of cost-sensitive classification problems, while the post-processing problem is reformulated as a convex optimization problem via a plug-in estimator. We further analyze the generalization risk and show that both methods are statistically consistent with the optimal accuracy-fairness equilibrium. Experiments on multiple real-world datasets demonstrate that OptFair offers a more controllable accuracy-fairness balance and competitive classification performance compared to existing methods. Our main contributions are summarized as follows: • We present an analytically tractable formulation of the optimal classifier that achieves the optimal accuracy-fairness frontier in the multi-class setting. • In-processing and post-processing algorithms are developed to approximate optimal fair classifiers, using a reduction-based method for in-processing and plug-in estimation for post-processing. • Theoretically, generalization bounds are provided to demonstrate that both methods are statistically consistent with the optimal fair classifier. • Extensive experiments on various datasets demonstrate that OptFair surpasses existing methods in balancing accuracy and fairness, with the flexibility to adjust the accuracy-fairness trade-off. 2 Related Work Multi-class group-fairness. Multi-class fairness extends classical notions such as demographic parity and equalized odds by imposing distributional constraints on vector-valued prediction outcomes across sensitive groups ( 2 ; 50 ; 16 ; 29 ) . Unlike the binary case, where fairness constraints reduce to scalar rate matching, the multi-class setting induces coupled constraints over the probability simplex, resulting in more complex feasibility regions. Accuracy-fairness trade-off. A growing body of work has investigated the trade-off between predictive utility and fairness through constrained risk minimization and Pareto-optimal frontiers, particularly in the binary classification setting ( 39 ; 61 ; 10 ) . However, theoretical understanding of the multi-class accuracy-fairness trade-off remains limited, with many existing characterizations deriving optimal fair classifiers only under restrictive structural assumptions ( 16 ; 51 ) . Consequently, general multi-class settings still lack analytically tractable characterizations of Bayes-optimal fair classifiers, leaving the induced optimal accuracy-fairness frontier under-specified. In-processing. Training-time fairness interventions typically enforce constraints through regularization ( 30 ; 5 ; 11 ) , dual or bilevel optimization ( 45 ; 58 ) , adversarial objectives ( 67 ; 62 ) , or reduction-based formulations ( 1 ) . While effective in practice, extending these methods to multi-class tasks is nontrivial due to coupled, multi-dimensional constraints, and existing theories seldom imply convergence to the accuracy-fairness frontier. Post-processing. Post-processing approaches aim to correct model outputs without retraining, e.g., by thresholding scores ( 10 ; 61 ) , mapping predictive probabilities ( 47 ; 2 ) , or calibrating group-conditioned distribution ( 50 ; 51 ; 16 ) . Despite their computational appeal, many existing post-processing techniques are either designed for binary settings or depend on attribute-aware adjustments, making them less suitable when sensitive attributes are unavailable at inference time. 3 Preliminaries Table 1 : Recovering Commonly Used Fairness