Equality of optimization problems of the soft-margin SVM (moving constraint to objective function)

Question

I'm reading the derivation of the soft-margin SVM optimization problem in Elements of Statistical learning. In it, the authors claim that \begin{align} \min_{} \quad & \| \mathbf{w}\| \\ \text{s.t.} \quad & y_i(\mathbf{w}\cdot\mathbf{x_i}+b) \geq (1-\epsilon_i) \\ \quad & \epsilon_i \geq 0 \quad \forall i \\ \quad & \sum_{i=1}^m\epsilon_i \leq C\\ \ \end{align}

(which is equation 12.7 in the book) is equal to this \begin{align} \min_{b, \mathbf{w}, \mathbf{\epsilon}} \quad & \frac{1}{2}\| \mathbf{w}\|^2 + C\sum_{i=1}^m\epsilon_i \\ \text{s.t.} \quad & y_i(\mathbf{w}\cdot\mathbf{x_i}+b) \geq 1-\epsilon_i \\ \quad & \epsilon_i \geq 0 \quad \forall i \end{align}

(which is equation 12.8 in the book).

My question is how can you move the constraint $\sum_{i=1}^m\epsilon_i \leq C$ to the objective function in this way?

Answer 1

You are right in your suspicion: you cannot. But, I believe the confusion stems from your misquoting the authors. In (12.7) they don't use 𝐶, but constant. Using your variables (in the original, the authors use $\beta$'s and $\xi$'s instead of $w$, $b$ and the $\epsilon$'s, but that's not the issue), the condition is:

$$ \sum \epsilon_i \leq \text{constant} $$

and below (12.8) the authors state:

where the "cost" parameter $C$ replaces the constant in (12.7); the separable case corresponds to $C = \infty$.

So $C$ and constant are not the same. It is easy to see that, in a linearly non-separable case, if you choose a small enough constant the problem becomes unsolvable. As the constant $ \rightarrow 0$, all $\epsilon_i$ must approach zero, too. For sufficiently small $\epsilon_i$'s, the condition

$$ y_i(\mathbf{w}\cdot\mathbf{x_i}+b) \geq 1-\epsilon_i $$

becomes unsatisfiable, unless the data set is separable. For $C$ it's the opposite: As $C \rightarrow 0$, all falsely classified points are being ignored, and any separation boundary satisfies the conditions.

Interestingly, equivalent formulas in machine learning literature (e.g. the formula above (6.3) in Cristianini and Shawe-Taylor, "Support Vector Machines" or (7.19-20) in Bishop, "Pattern Recognition and Machine Learning") don't have that constraint on $\epsilon_i$'s. In their seminal paper, Cortes and Vapnik (the inventors of the SVMs) also don't use this notation.

The formula (12.8) is nevertheless correct, i.e. congruent with other literature ((6.3) in Cristianini and Shawe-Taylor, (7.21) in Bishop, (24) in Cortes and Vapnik).