Surrogate losses for cost-sensitive classification with example-dependent costs
Clayton D. Scott · 2011
We study surrogate losses in the context of cost-sensitive classification with example-dependent costs, a problem also known as regression level set estimation. We give sucient conditions on the surrogate loss for the existence of a surrogate regret bound. Such bounds imply that as the surrogate risk tends to its optimal value, so too does the expected misclassification cost. These kinds of bounds are not only intuitively natural requirements of the surrogate loss, but have also emerged in recent years as critical tools when proving consistency of algorithms based on surrogate losses. Our sucient conditions encompass example-dependent versions of the hinge, exponential, and other common losses. These results provide theoretical justification for some previously proposed surrogate-based algorithms, and suggests others that have not yet been developed.