# Regularizing the dual variables in SVM

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.

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$).

• Could you elaborate on this a little bit: "Adding regularization in the dual would inevitably change the solution and will result in a classifier that is no longer maximum-margin". Here is my concern: sure, we have $L_1$ regularization on $\xi_i$'s in the primal, but penalizing the primal by different regularization functions shouldn't hurt either? E.g. if you want to allow large margins, you could use other M-estimator penalties on $\xi$'s. What do you think? – Alt Feb 1 '15 at 19:22
• @Alt that's an interesting idea for sure, though at a glance I fear that a lot of M-estimators would result in non-convex cost functions (not sure about that, though ... I should probably think it over more). – Marc Claesen Feb 1 '15 at 19:36
• Convexity is a separate issue. Since $L_1$ works well, I guess Huber (among the convex ones) would also work well (if not better); although the optimization will be computationally less efficient for sure. – Alt Feb 2 '15 at 8:05