Linear Constraint in SVM optimization

Question

$\newcommand{\loss}{\operatorname{loss}}$Recently I am surveying different SVM optimization algorithms. I came across a strange scenario:

When we formulate the SVM primal problem like the following, $$\min_w \frac{1}{2}w^Tw + C\sum_{i=1}^{m}\loss(w, x_i, y_i),$$ $$\text{such that }\quad y_i(w^Tx_i + b) \ge 1 - c_i,$$ because of the linear constraint, we will have the following constraint in the dual formulation: $$\alpha^Ty = 0,$$ and this means that we need to optimize at least two variables at a time.

But some papers will formulate the SVM problem in the unconstrained version, simply: $$\min_w \frac{1}{2}w^Tw + C\sum_{i=1}^{m}\loss(w, x_i, y_i).$$ Then because we no longer have the linear constraint, we can apply method such as coordinate descent, which updates only one variable at a time.

I am confused, what is the difference between these two formulations of SVM?

Answer 1

Note that generally, the loss$(w,x_i,y_i)$ term you have written would actually be the $c_i$ value from the constraint, in both versions.

The dual-formulation constraint $\alpha^T y = 0$ arises from the bias term $b$ which offsets the solution plane from the origin. The most common alternative to using the bias term is extending all the inputs $x_i$ by adding on a dimension with constant value $1$. A less commonly used approach is to use a slightly modified kernel function formulation to replicate $b$ (i.e., so that calculating $<w,x>_{k'}$ with the modified kernel $k'$ is similar to evalutating $<w,x>_k + b$ with the original kernel).

From a practical perspective, there is little difference in the classifier performance between biased and unbiased SVM. Specific algorithms differ of course, and the time it takes to learn a classifier can be different. From a theoretical perspective, it is often easier to determine bounds for the unbiased version.