Scaling hinge loss in SVM 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?
 A: 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. 


*

*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. 

*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.
A: 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.
