# Will an SVM break down for sufficiently small values of C?

Consider the soft-margin SVM formulation. \begin{align} \mbox{min}_{\mathbf{w},b,\boldsymbol{\xi}} & & \frac{1}{2}\|\mathbf{w}\|_2^2 + C\sum_i \xi_i \\ \mbox{s.t.} & & y_i(\mathbf{w}^Tx_i+b) \geq1-\xi_i \\ & & \xi_i\geq0 \end{align} If $C$ is sufficiently small, the $\xi_i$'s can grow large, and therefore the constraints can be honored by a plethora of grossly misclassified points. Therefore, the minimization of $\|\mathbf{w}\|^2_2$ no longer seems that helpful in the pursuit of a separating hyperplane.

I have done a quick test with scikit-learn's SVC and a toy (and admittedly a bit pathological) dataset.

So in this case I think we can say it breaks down badly (unless it is due to the implementation).

The SVM objective (minimize $\|\mathbf{w}\|$) arises from the consideration of the constraints in the original, natural objective (maximize the margin to the closest point). Doesn't it cease to be a natural formulation once we introduce the slack variables? Is there something intrinsic to the minimization of $\|\mathbf{w}\|$ that provides better separating hyperplanes in less extreme cases, or will this pathology happen in general?

EDIT: The corresponding slack variables for each of the above cases are:

y  point     xi
1  [ 0.  1.] 0.000276941610509
1  [ 1.  1.] 9.22304236668e-05
1  [ 2.  1.] 9.24807631741e-05
1  [ 3.  1.] 0.000277191950016
-1 [ 0. -1.] 0.000461843532213
-1 [ 1. -1.] 0.000277132345372
-1 [ 2. -1.] 9.24211585298e-05
-1 [ 3. -1.] 9.22900283107e-05
1  [ 1.5 -0.9] 1.90017553166

1  [ 0.  1.] 2.38418573772e-09
1  [ 1.  1.] 3.57627882863e-09
1  [ 2.  1.] 9.53674317294e-09
1  [ 3.  1.] 1.54972079613e-08
-1 [ 0. -1.] 0.779999997616
-1 [ 1. -1.] 0.780000003576
-1 [ 2. -1.] 0.780000009537
-1 [ 3. -1.] 0.780000015497
1  [ 1.5 -0.9] 1.15899999344

1  [ 0.  1.] 2.38418618181e-10
1  [ 1.  1.] 1.5894552341e-10
1  [ 2.  1.] 5.56309887045e-10
1  [ 3.  1.] 9.53674250681e-10
-1 [ 0. -1.] 1.87799999976
-1 [ 1. -1.] 1.87800000016
-1 [ 2. -1.] 1.87800000056
-1 [ 3. -1.] 1.87800000095
1  [ 1.5 -0.9] 0.115899999642

• For reference, what are the $\xi_i$ produced for each plot? – Alex R. Sep 19 '17 at 20:04
• @AlexR. Good point. I added them. – cangrejo Sep 19 '17 at 20:19

As $C \rightarrow 0$, $w \rightarrow 0$ (independent of the data, of course the precise results for specific values of $C$ will be data dependent). Note that your implementation though will generally be $\epsilon$-accurate for some expression (this may be the objective, or it may be on something related, like a bound on the duality-gap), and it might be sensitive to how it started the optimization.
• This answer certainly introduces interesting elements. However, can we expect data-independent $\epsilon$-accuracy considering the $\xi$'s can grow arbitrarily? – cangrejo Jan 24 '18 at 14:44
• This depends on the optimization approach. For example, some algorithms explicitly take $\epsilon$ as a parameter and thus guarantee this bound - i.e, its guaranteed that the objective is within $\epsilon$ of optimal - however the precise value that you exceed the objective by is definitely data dependent; if the algorithm is stochastic it would even be dependent on the randomization there – MotiN Jan 25 '18 at 15:29