Demystifying the Optimal Fair Classifier in Multi-Class Classification

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 across 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.

Machine learning models are increasingly used in high-stakes settings, but they may treat different groups unfairly. This problem becomes more challenging in multi-class tasks, where each input can belong to one of many possible categories. In this paper, we study how to better balance prediction accuracy and group fairness in such settings. We first characterize what an ideal fair predictor should look like, and then develop two practical methods: one that improves fairness during training and another that adjusts predictions after training. Our methods do not require sensitive attributes at prediction time, making them easier to deploy in real-world applications. Experiments on several datasets show that our approach achieves a more reliable balance between accuracy and fairness than existing methods.