What is a surrogate loss function?

Question

Can anybody please clarify what a surrogate loss function is? I'm familiar with what a loss function is, and that we want to bring about a convex function that is differentiable, but I don't understand the theory behind how you can satisfactorily use a surrogate loss function and actually trust its results.

Answer 1

In the context of learning, say you have a classification problem with data set $\{(X_1, Y_1), \dots, (X_n, Y_n)\}$, where $X_n$ are your features and $Y_n$ are your true labels.

Given a hypothesis function $h(x)$, the loss function $l: (h(X_n), Y_n) \rightarrow \mathbb{R}$ takes the hypothesis function's prediction (i.e. $h(X_n)$) as well as the true label for that particular input and returns a penalty. Now, a general goal is to find a hypothesis such that it minimizes the empirical risk (that is, it minimizes the chances of being wrong):

$$R_l(h) = E_{\text{empirical}}[l(h(X), Y)] = \dfrac{1}{m}\sum_i^m{l(h(X_i), Y_i)}$$

In the case of binary classification, a common loss function that is used is the $0$-$1$ loss function:

$$ l(h(X), Y) = \begin{cases} 0 & Y = h(X) \\ 1 & \text{otherwise} \end{cases} $$

In general, the loss function that we care about cannot be optimized efficiently. For example, the $0$-$1$ loss function is discontinuous. So, we consider another loss function that will make our life easier, which we call the surrogate loss function.

An example of a surrogate loss function could be $\psi(h(x)) = \max(1 - h(x), 0)$ (the so-called hinge loss in SVM), which is convex and easy to optimize using conventional methods. This function acts as a proxy for the actual loss we wanted to minimize in the first place. Obviously, it has its disadvantages, but in some cases a surrogate loss function actually results in being able to learn more. By this, I mean that once your classifier achieves optimal risk (i.e. highest accuracy), you can still see the loss decreasing, which means that it is trying to push the different classes even further apart to improve its robustness.

Answer 2

On a very general note, this function is used to penalize the misclassifications. In the end, your aim is to classify the data in correct classes and to evaluate your results. To train the model you develop the loss functions and most frequently Mean Squared Error. But in MSE the accuracy may not reflect the true accuracy of the classifier. So we would like a loss function (like 0-1 loss function) which gives error as 1 if the class is wrong and 0 if the prediction is right. This is used in svm and called as Hinge Loss. But in broader terms if you look at the formula

∑max(0,1−y(i)(w⊺ x(i)+b))

It essentially applies the same. You may want to read more about how L1 and L2 regularizations come in the picture but intuitively that is what I understood.