Regularizing the dual variables in SVM

Question

Consider the the optimization program of the kernelized SVM:

$$\text{maximize}_{\alpha} ~~ \alpha^T1-\alpha^TQ\alpha$$ $$\text{subject to:} \sum_{i=1}^N \alpha_iy_i=0,~0\leq \alpha_i\leq c$$

where for the matrix $Q$, we have: $Q_{ij}=y_iy_j\text{kernel}(x_i,x_j)$.

This optimization program is resulted by taking the dual of the hinge-loss-based SVM with $L_2$ regularization.

Now here is my question: Why no body regularizes $\alpha$ in this optimization program?

I understand that $\alpha$ is just the dual variables' vector, but I'm really curious to know why people have not tried regularizing $\alpha$.

For example, if for what ever reasons we want to force the algorithm to introduce less support vectors, then adding an $L_1$ regularization on $\alpha$ would be usefull right?

I.e.,

$$\text{maximize}_{\alpha} ~~ \alpha^T1-\alpha^TQ\alpha-\|\alpha\|_1$$ $$\text{subject to:} \sum_{i=1}^N \alpha_iy_i=0,~0\leq \alpha_i\leq c$$

Or maybe, a Tikhonov regularization:

$$\text{maximize}_{\alpha} ~~ \alpha^T1-\alpha^T(Q+\gamma I)\alpha$$ $$\text{subject to:} \sum_{i=1}^N \alpha_iy_i=0,~0\leq \alpha_i\leq c$$

I appreciate it if you share any comments that you might have.

Answer 1

From a regularization point of view, SVM is a special case of Tikhonov regularization using hinge loss. We are already inducing sparsity in the $\alpha$ vector by using hinge loss, i.e. the sum of slack variables $\xi$ in the primal:

$$\begin{align} \min_{\alpha, b,\xi}\quad &\frac{1}{2}\|\mathbf{w}\|^2 + C \sum_{i=1}^N \xi_i, \\ s.t.\quad&y_i\big(\langle\mathbf{w},\varphi(\mathbf{x}_i\rangle +b\big) \geq 1- \xi_i,\quad \forall i. \end{align}$$

You can see this by working out the primal Langrangian (which is being minimized): $$ L_p = \frac{1}{2}||\mathbf{w}||^2+C\sum_{i=1}^n\xi_i -\sum_{i=1}^n\alpha_i\Big[y_i\big(\langle\mathbf{w},\varphi(\mathbf{x}_i)\rangle+b\big)-(1-\xi_i)\Big]-\sum_{i=1}^n\mu_i\xi_i. $$ Some of the optimality conditions are: $$\begin{align} \frac{\partial L_p}{\partial \xi_i}=0 \quad \rightarrow \quad &\alpha_i=C-\mu_i, \quad \forall i, \\ \frac{\partial L_p}{\partial \mathbf{w}}=0\quad \rightarrow \quad &\mathbf{w}=\sum_{i=1}^n \alpha_i y_i \varphi(\mathbf{x}_i),\quad \forall i, \end{align}$$ Which leads to $\xi_i = 0 \rightarrow \mu_i = C \rightarrow \alpha_i = 0$: instances $i$ that are correctly classified ($\xi_i=0$), already have a dual weight $\alpha_i=0$ and $\xi$ is essentially $L_1$-regularized.

Adding regularization in the dual would inevitably change the solution and will result in a classifier that is no longer maximum-margin, which is one of the key reasons SVM is so popular.

This is one of the key differences between SVM and LS-SVM (which uses the sum of squares of (regression) errors and therefore loses sparsity in $\alpha$).