# What's the difference between $\ell_1$-SVM, $\ell_2$-SVM and LS-SVM loss functions?

Over the years, many developments led to adaptations and variations over the original SVM (here called $\ell_1$-SVM, alluding to the $L_1$ penalty for points across the margin).

Two such formulations one frequently encounters are the LS-SVM1 and the $\ell_2$-SVM2.

What's the differences between the three, from an optimization perspective?

[1] Suykens, Johan AK, and Joos Vandewalle. "Least squares support vector machine classifiers." Neural processing letters 9.3 (1999): 293-300.

[2] Cortes, Corinna, and Vladimir Vapnik. "Support-vector networks." Machine learning 20.3 (1995): 273-297.

Consider the input $\{x_i,y_i\}^N:x_i\in \mathbb{R}^p,y_i\in\{-1,1\}$.

The common $\ell_2$-regularized $\ell_1$-SVM minimizes the following loss:

$$\left\{\begin{matrix} \min_{w_i,e_i}{1\over2}\|w\|_2^2+{C\over2}\sum_{i=1}^n\xi_i \\ \xi_i=\max{(0,1-y_i\cdot w\cdot(\phi(x)+b))}\space\forall i \end{matrix}\right.$$

Only points at the wrong side of the separating hyperplane are (linearly) penalized by the hinge loss. This provides a maximum margin classifier, or, in other words, the classifier tries to keep points at the right side of the classifying margin, regardless of the distance. A byproduct of the hinge formulation is the possibility of sparsity: the number of non-zero supports of the margin often allows this to be less than $N$. Notice though that the loss is non-differentiable. Primal solutions must make use of the subgradient, while dual solutions result in a quadratic problem.

For the $\ell_2$-regularized $\ell_2$-SVM the loss used is:

$$\left\{\begin{matrix} \min_{w_i,e_i}{1\over2}\|w\|_2^2+{C\over2}\sum_{i=1}^n\xi_i^2 \\ \xi_i=\max{(0,1-y_i\cdot w\cdot(\phi(x)+b))}\space\forall i \end{matrix}\right.$$

Again, only points at the wrong side of the separating hyperplane are penalized, but now the penalty for violations is more severe: quadratic. Also, this loss (the squared hinge loss) is differentiable, which means solutions in the primal formulation can use standard Gradient Descent techniques. Sparsity is not preserved, or in other words, all inputs are Support Vectors.

For the traditional $\ell_2$-regularized LS-SVM, the following loss is minimized1:

$$\left\{\begin{matrix} \min_{w_i,e_i}{1\over2}\|w\|_2^2+{C\over2}\sum_{i=1}^ne_i^2 \\ e_i=y_i-w\cdot(\phi(x)+b)\space\forall i \end{matrix}\right.$$

This leads to a linear problem instead of a quadratic problem as in $\ell_1$-SVMs and $\ell_2$-SVMs. But notice the problem penalizes points at either side of the margin, only points which prediction match exactly their true value aren't penalized, so it isn't a maximum margin classifier. The same loss is used for regression and, indeed,the LS-SVM formulation is identical to a Ridge Regression (over Fisher $\{-1,1\}$ labels for classification).

Regression can be analogously compared, but instead usually an epsilon-insensitive loss is used. Regression LS-SVM is Ridge Regression.

[1] Chu, Wei, Chong Jin Ong, and S. Sathiya Keerthi. "A Note on Least Squares Support Vector Machines."