I've seen some statement where I got the impression that SVM with a quadratic loss is no more than having a kernel matrix where a multiple of the unit matrix is subtracted from the kernel. It was shown that in the dual problem the L2 loss constant can be merged into the kernel. But it wasn't clear to me. So the question:

Are L1 and L2 loss for SVM substantially different? (Is L2 loss for SVM convex?) Or does L2 loss correspond to L1 loss with a shifted kernel? Or anything else?

They are different specially in the case of regression. The effect of the quadratic loss is to average errors (so it is more sensitive to outliers). To see this, if you minimize, $$L_{2}(y) = \sum_{i}(y-x_{i})^{2}$$ you get the mean value. The effect of the L1 loss function is to , so that it leads to sparse solutions robust against outliers. Again, consider, $$L_{1}(y) = \sum_{i}|y-x_{i}|$$ The derivative gives you $$\sum_{i}\operatorname{sign}(y-x_{i}) = 0$$, which is true for the median. And the median is robust against outliers.

Now, how does this translate for SVMs?

The loss function affects how the kernel function is regularized (i.e. how you compare samples). This is specially critical in the case of regression, since when using the $$L_{2}$$ the solution is no longer sparse! (which is one of the aspects of SVMs which makes them interesting in practice).

The optimization problem in that case reads, $$\min_{w} \sum_{i=1}^{l} \xi_{i}^{2} \\ \text{subject to } y_{i}- = \xi_{i} \\ ||w|| \leq B \text{ and } i = 1,...,l$$

After deriving with respect to the primal variables and substituting, you get, $$\min_{\alpha} -\lambda \sum_{i=1}^{l}\alpha_{i}^{2}-\sum_{i,j}\alpha_{i}\alpha_{j}\kappa(x_{i},x_{j}) + 2\sum_{i}\alpha_{i}y_{i}$$ for a detailed derivation see for example here. Notice that the first two terms can be grouped in we define as, $$\min_{\alpha} -\sum_{i,j}\alpha_{i}\alpha_{j}\hat{\kappa}(x_{i},x_{j}) + 2\sum_{i}\alpha_{i}y_{i}$$ where $$\hat{\kappa} = (\kappa + \lambda I)$$. Notice that this forces the $$\alpha$$'s not to be sparse anymore.

• What about an equivalent derivation with L1? I believe I saw someone do a similar derivation for L1 and after also grouping terms, showing that L1 SVM isn't much different from L2 SVM mathematically.
– Gere
Commented Jun 17, 2015 at 5:58
• In the paper I refer to there is a derivation for the epsilon-sensitive loss, which is based in the L1 loss. What you mean is the case of classification, where L2 does not loose the sparsity property. There the difference is not so critical, that is why I decided to stress the case of regression. I'll expand my reply a bit in order to clear out those points, but again, for a detailed answer please see the paper I referred to in my answer. Commented Jun 17, 2015 at 7:43
• The sparsity of SVMs is generally overstated IMHO, if you tune the hyper-parameters properly then optimal generalisation is often achieved with hyper-parameter values that leave the majority of patterns lying with the margins and hence as support vectors. If you want a sparse model, it is better to opt for a model where sparsity is an explicit design goal rather than a handy by-product. Commented Sep 2, 2021 at 11:27
• If it is a squared slack penalty then the solution should still be sparse, shouldn't it? I think the sparsity comes from the constraint being <= rather than == (c.f. kernel ridge regression and least-squares support vector machine)? Commented Sep 2, 2021 at 11:29

"In the dual problem the L2 loss constant can be merged into the kernel." It can be done in the hinge loss too. You only need to rephrase the formulation.

It is done here, for instance: A nested heuristic for parameter tuning in Support Vector Machines E Carrizosa, B Martín-Barragán, D Romero Morales Computers & Operations Research 43, 328-334