4
$\begingroup$

According to "A Note on Support Vector Machine Degeneracy", Theorem 4, if the dual problem for soft-SVM has a solution with $\alpha_i \in \{0,C\}, \forall i$, then $w=0$ for the primal problem.

In "Uniqueness of the SVM solution", there is an example which, I say, contradicts the theorem above:

Data: $x_1 = 1, y_1 = +1; x_2 = -1, y_2 = -1$

$C \in (0,1/2]$

Result: $\alpha_1 = \alpha_2 = C$

$w=2C \neq 0$.

Am I missing something?

$\endgroup$
0
$\begingroup$

Let's check if $w=2C$ is actually primal optimal...

The objective value when $w = 0$ would be $2C$.

When $w=2C$ the objective value would be $\frac{(2C)^2}{2} + (1+b-2C)+(1-b-2C) = 2C^2 - 4C + 2 = 2(C-1)^2$.

Then $w=0$ could be optimal when $C < (C-1)^2$ which happens for $C < \frac{3-\sqrt 5}{2} < \frac{1}{2}$, but not above it.

I'm not quite sure what to make of this - perhaps for this example, strong duality doesn't hold, invalidating both the example and the theorem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.