CLASSIFICATION WITH A REJECT OPTION USING A HINGE LOSS

Abstract. We consider the problem of binary classification where the classifier can, for a particular cost, choose not to classify an observation. Just as in the conventional classification problem, minimization of the sample average of the cost is a difficult optimization problem. As an alternative, we propose the optimization of a certain convex loss function φ, analogous to the hinge loss used in support vector machines (SVMs). Its convexity ensures that the sample average of this surrogate loss can be efficiently minimized. We study its statistical properties. We show that minimizing the expected surrogate loss—the φ-risk— also minimizes the risk. We also study the rate at which the φ-risk approaches its minimum value. We show that fast rates are possible when the conditional probability P(Y = 1|X) is unlikely to be close to certain critical values. Key words and phrases: Bayes classifiers; classification; convex surrogate loss; empirical risk minimization; hinge loss; large margin classifiers; margin condition; reject option; support vector machines. MSC 2000: Primary 62C05; secondary 62G05, 62G08 1