Scaling hinge loss in SVM

Question

Recall the functional of primal SVM problem: $\|w\|^2 + C \sum_i \xi_i \to \min$.

Suppose I have 1000 training objects, and want to find optimal $C$ by 2-fold cross-validation. As a result of cross-validation I'll get $C$ that is optimal for certain scale of $\sum_i \xi_i$. When I use this $C$ to train SVM on full training sample, there will be 1000 summands in $\sum_i \xi_i$ instead of 500, so the scale of this penalty component will be different.

The question is: will my $C$ be optimal for sample with 1000 objects if it was trained on sample with 500 objects? Why shouldn't we scale the penalties:

$\|w\|^2 + \frac{C}{L} \sum_i \xi_i \to \min$,

where $L$ is the size of sample?

Answer 1

Because of the following reasoning I would say that you don't want to scale $C$ by the number of examples because you do want to the loss term to take over for a lot of data points.

1. The regularizer $||w||^2$ is basically for the situation where the data does not uniquely determine the hyperplane. For large $L$ the loss function should give sufficient information to find the best separation. Therefore, for large $L$ you want the loss term to dake over. Scaling down the $C$ by the number of data points on the other hand causes the regularizer to be always as important as the loss function.

2. The regularizer and the loss term basically correspond to a prior over $w$ and a noise model, respectively. The $C$ loosely corresponds to the noise level. Therefore, if you choose the correct noise level $C$ with cross validation it should be the best parameter no matter how many data points you have. The question is, of course, whether your estimate of $C$ during the cross validation was good.

I know that this not a solid mathematical answer, but maybe it's helpful anyway.

Answer 2

In practice, the optimal value for $C$ unfortunately depends on the size of the training set (but not linearly, so your proposed approach is a heuristic at best).

For typical cross-validation setups with a reasonable amount of folds this is no issue and you can use the obtained $C$. For $k=2$ folds, however, you can run into problems as your folds are much smaller than the full training set. That said, two-fold cross-validation won't give you a reasonable estimate of generalization performance anyway, which is another reason to increase the amount of folds.