Minimizing The Misclassification Error Rate Using a Surrogate Convex Loss

Abstract

We carefully study how well minimizing convex surrogate loss functions, corresponds to minimizing the misclassification error rate for the problem of binary classification with linear predictors. In particular, we show that amongst all convex surrogate losses, the hinge loss gives essentially the best possible bound, of all convex loss functions, for the misclassification error rate of the resulting linear predictor in terms of the best possible margin error rate. We also provide lower bounds for specific convex surrogates that show how different commonly used losses qualitatively differ from each other.

Appears in Proceedings of the 29th International Conference on Machine Learning (ICML 2012)

Cited by in corpus (10)

• Classification vs regression in overparameterized regimes: Does the loss function matter?
• A Farewell to the Bias-Variance Tradeoff? An Overview of the Theory of Overparameterized Machine Learning
• Supervised Metric Learning with Generalization Guarantees
• Minimizers of the Empirical Risk and Risk Monotonicity
• Efficient Learning of Linear Separators under Bounded Noise
• Binary Excess Risk for Smooth Convex Surrogates
• Agnostic Learning of Halfspaces with Gradient Descent via Soft Margins
• Exploiting Smoothness in Statistical Learning, Sequential Prediction, and Stochastic Optimization
• Risk-Monotonicity in Statistical Learning
• Beating the Minimax Rate of Active Learning with Prior Knowledge