Abstract

Complex performance measures, beyond the popular measure of accuracy, are increasingly being used in the context of binary classification. Thes complex performance measures are typically not even decomposable, that is, the loss evaluated on batch of samples cannot typically be expressed as a sum or average of losses evaluated at individual samples, which in turn requires new theoretical and methodological developments beyond standard treatments of supervised learning. In this pa per, we advance this understanding of binary classification for complex performance measures by identifying two key properties: a so-called Karmic property, and a more technical threshold-quasiconcavity property, which we show is milder than existing structural assumptions imposed on performance measures. Under these properties, we show that the Bayes optimal classifier is a thresh old function of the conditional probability of pos itive class. We then leverage this result to come up with a computationally practical plug-in classifier, via a novel threshold estimator, and furth provide a novel statistical analysis of classifica tion error with respect to complex performance measures.