Consistent Multiclass Algorithms for Complex Metrics and Constraints

We present consistent algorithms for multiclass learning with complex performance metrics and constraints, where the objective and constraint are defined by arbitrary functions of the confusion matrix. This setting includes many common performance metrics such as the multiclass G-mean and micro F1-measure, and constraints such as those on the classifier's precision and recall and more recent measures of fairness discrepancy. We give a general framework for designing consistent algorithms for such complex design goals by viewing the learning problem as an optimization problem over the set of feasible confusion matrices. We provide multiple instantiations of our framework under different assumptions on the performance metrics and constraints, and in each case show rates of convergence to the optimal (feasible) classifier (and this asymptotic consistency). Experiments on a variety of multiclass classification and fairness-constrained problems show that our algorithms compare favorably to the state-of-the-art baselines.