The Coherent Loss Function for Classification

A prediction rule in binary classification that aims to achieve the lowest probability of mis-classification involves minimizing over a non-convex, 0-1 loss function, which is typically a computationally intractable optimization prob-lem. To address the intractability, previous meth-ods consider minimizing the cumulative loss – the sum of convex surrogates of the 0-1 loss of each sample. We revisit this paradigm and de-velop instead an axiomatic framework by propos-ing a set of salient properties on functions for bi-nary classification and then propose the coherent loss approach, which is a tractable upper-bound of the empirical classification error over the en-tire sample set. We show that the proposed ap-proach yields a strictly tighter approximation to the empirical classification error than any convex cumulative loss approach while preserving the convexity of the underlying optimization prob-lem, and this approach for binary classification also has a robustness interpretation which builds a connection to robust SVMs. 1