Minimizing The Misclassification Error Rate Using a Surrogate Convex Loss

By Shai Ben-David, David Loker, Nati Srebro, Karthik Sridharan. 2012

66 citations recorded by the source corpus.

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. We consider the agnostic setting, and investigate guarantees on the misclassification error of the loss-minimizer in terms of the margin error rate of the best predictor. We show that, aiming for such a guarantee, the hinge loss is essentially optimal among all convex losses.

Subfields: Artificial Intelligence, Statistics and Probability, Optimization & Training, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistics and Probability

In Optimization & Training

In Signal Processing

Citations in the corpus

Quantifying Learning Guarantees for Convex but Inconsistent Surrogates (2018, background): “[3] worked in the agnostic setting for binary classification (no assumptions on the underlying D) and provided guarantees on the error of linear predictors when the margin was bounded by some constant (their work reduces to consistency in the limit case, but is more general).”
Complexity theoretic limitations on learning halfspaces (2015, background): “A few results [17, 53, 32] showing hardness of approximation results for several concrete families of algorithms (linear methods).”
Classification vs regression in overparameterized regimes: Does the loss function matter? (2020, background): “For example, the theory of surrogate losses (Zhang, 2004; Bartlett et al., 2006; Ben-David et al., 2012) gives theoretical arguments favoring the logistic and hinge losses over other convex surrogates, including the square loss.”
Consistency versus Realizable H-Consistency for Multiclass Classification (2013, background): “(The hinge loss was shown to be optimally noise-tolerant for binary classification, in a certain sense, in (Ben-David et al., 2012).)”
On the Consistency of Multi-Label Learning (2011, unknown): “, 2010), and (Ben-David et al., 2012) may shed some light.”
Cost-sensitive Multiclass Classification Risk Bounds (2013, result): “Ben-David et al. (2012) studied surrogate loss risk bounds for linear binary classifiers, which is related but complementary to our results.”
Contrastive Pessimistic Likelihood Estimation for Semi-Supervised Classification (2015, background): “Similar phenomena for other classifiers have been described in [74], [75], where simple artificial examples are provided of how such behavior can be realized.”
Projected estimators for robust semi-supervised classification (2016, background): “Much work is currently being done to understand the relationship between surrogate losses and 0-1 loss (Bartlett et al., 2006; Ben-David et al., 2012).”