Which loss function has a less optimal answer for w?

I'm studying machine learning and I came into a challenging question.

The answer is 2. But why is 2 correct? Is it correct because of the regularization term?

• Welcome to this site. Please consider adding the self-study tag as those questions get a special treatment. – chl Dec 19 '20 at 8:02
• Shouldn't the information from the image be translated into text and MathJax? – Peter Mortensen Dec 19 '20 at 21:32

Since the data is linearly separable, other loss functions can be made $$0$$ via a suitable choice of weights, $$w$$. However, second one has a regularisation term, so the loss function doesn't only favor the linear separability, but the norm of the weights as well.

Notes: Given a loss function, I assumed the chosen optimizer with initial condition will find the optimum point for that loss. So, it'll optimize $$L_2$$ as well (i.e. $$L_2$$ will reach its minimum). Although it's typically not a good idea to compare the values of the loss functions since the expressions are different, $$L_2$$ will always be $$\geq L_i$$ for other $$i$$, since other loss functions can be made $$0$$, but $$L_2$$ most probably won't be. If the optimality is measured wrt separability of the dataset, i.e. a $$w$$ that separates the dataset is called optimum and another that doesn't is not, $$L_2$$ will probably be less optimum as well because it's not guaranteed to separate the dataset.

• So, in this particular case by less optimum it means that $L(\hat{w}) \geq L(w)$? – Fiodor1234 Dec 19 '20 at 10:42
• @Fiodor1234 I think the question needs to explain the sense of optimality, but I've given my answer considering the possible choices. I've added some notes to my answer because it was too long for a comment. – gunes Dec 19 '20 at 10:53
• Yes, it is vague on that point. What do you think about my following assumption which is quite similar with what you wrote, just to make sure that I'm on the same page: 1) The data are linear separable, 2) Any linear classifier with a regularizer or not will classify them correctly 3) the regularizer due to penatly will have larger loss function, so in that sense will be less optimal. And the key point is that all linear classifier with regularizer or not do the work, in order to compare their Loss functions? – Fiodor1234 Dec 19 '20 at 11:07
• Yes, those are the assumptions I made, too, with an alternative addition to the meaning of optimality in the third one. – gunes Dec 19 '20 at 11:08
• @EvaB yes, based on the two optimality ideas presented. – gunes Dec 19 '20 at 13:26

Your data are lineary separable, this means that all linear classifier will make accurate separation of the data. A linear regression is a linear classifier, i.e it uses a line to separate data. So either you use a linear regression with no penalty or a linear regression with penalty you are still going to separate correctly your data.

However, what a penalty means, is that you will have an additional term in your loss function.

So, a loss function $$L$$ will be $$L^{'} = L+\frac{1}{2}f(w)$$ in penalty case, where $$f(w)$$ can be what ever norm you prefer.

So, you will have that $$L^{'} > L$$. But as we said both linear classifier separate the data accurately (the one that correspond to $$L^{'}$$ and the one that correspond to $$L$$) but we know that $$L^{'}$$ is less optimal, in the sense that it is larger than the $$L$$.

I'm not quite sure however, if that is the optimality meaning that you refer to. I hope that helps.

Some further discussion, for the exact loss functions that you have:

1. $$L_{1}(w)= \frac{1}{n}\sum_{i=1}^{n}max(0,-y_{i}w^{T}x)$$

A correct classification means that $$y_{i}>0$$ and $$w^{T}x>0$$ or $$y_{i}<0$$ and $$w^{T}x<0$$. In both cases the $$max(0,-y_{i}w^{T}x)=0$$ because you do not have to minimize something on correct classifications. Thus, because your data are linearly separable the $$L_{1}(w)=0$$.

1. For the $$L_{3}(w)$$, for this loss function to be meaningful I assume that the step function $$u$$ is defined as follows:

if $$y_{i}w^{T}x>0$$ then $$u=0$$ and if $$y_{i}w^{T}x<0$$ then $$u=1$$, i.e for misclassifications the loss function is increased. Again, because your data are linearly separable you will not have missclasifications so the $$L_{3}(w)=0$$

1. Similar for the $$L_{4}(w)=0$$

2. Lastly, for the $$L_{2}(w)$$, the term $$C\sum_{i=1}^{n}max(0,-y_{i}w^{T}x)$$ is equal to zero prior of $$C$$ reaching infinity, because the sum is zero due to linear separability. So, the $$L_{2}(w)$$ is left with the penalty term, and that penalty term cannot be zero, because then all your weights will be zero so you will be full of misclassifications. Hence, with that in mind $$L_{2}(w)>0$$.

• @EvaB I edit my answer, to include some more information that I found interesting. – Fiodor1234 Dec 19 '20 at 15:53