Statistical Learning and Data Science

Fast Optimization Algorithms for Solving SVM+ 37

Proof We use the ideas of the pr oof of Proposition 7 in (Bordes et al. 2005 [31]) showing

that U = {e

i

− e

j

, i 6= j} is a finite witness family for SVM. The set I

1

∪ I

2

∪ I

3

is finite.

Let x ∈ R

2n

be an arbitrary point in F and u be a feasible direction at x. Recall that the

first n coordinates of x are designated for the values of α’s and the last n coordinates of

x are designated for the values of β’s. There exists λ > 0 such that x

′

= x + λu ∈ F.

We construct a finite path x = z(0) → z(1) → . . . → z(m − 1) → z(m) = x

′

such that

z(j + 1) = z(j) + γ(j)v(j), where z(j + 1) ∈ F and v(j) is a feasible direction at x. We

prove by induction on m that these two conditions are satisfied. As an auxiliary tool, we

also ...