Optimal grid search for $C$ in SVM

Question

Say we are training a radial SVM with parameters $C$ and $\gamma$. We would typically do this using grid search and CV. My prof. alluded that one does not have to exhaust all of $C$ values in the grid to obtain the optimal solution and I'm sure the popular packages don't search over all $C$ values either for the sake of speed. So my question is how is it done optimally, i.e. going over the least amount of $C$ values (for a given $\gamma$)?

I'm thinking that if one start from the lowest value of $C$, we may stop once the performance no longer improves. Is this optimal?

Answer 1

I'm sure the popular packages don't search over all C values either for the sake of speed

Hastie et al. made this point obsolete. Using the regularization paths for ordinary SVMs would allow one to explore many values for C faster (at the order of magnitude of the time of a single evaluation). See this paper: The Entire Regularization Path for the Support Vector Machine.

So you can investigate the whole path at once to pick the optimal cost without having to depend on heuristics.

---

While R wasn't mentioned, you can fiddle with the method in the R package svmpath, created by Hastie himself. [CRAN link and manual].

The SVM has a regularization or cost parameter C, which controls the amount by which points overlap their soft margins. Typically either a default large value for C is chosen (allowing minimal overlap), or else a few values are compared using a validation set. This algorithm computes the entire regularization path (i.e. for all possible values of C for which the solution changes), with a cost a small (~3) multiple of the cost of fitting a single model.

Answer 2

When C is very low, the model is biased, and usually produces poor results. When C is very large, the model produces poor results due to high variance. The optimal C is somewhere in between. You can usually start with C's in the range of $2^{-7}$ to $2^7$, using powers of 2 for steps. Usually the sweet spot is included. If needed, you can then increase resolution to search for the optimal C in a smaller range.

Answer 3

Note sure if your prof. meant it, but I'd like to mention another alternative to grid search for hyperparameter tuning: Bayesian optimization.

The idea is to treat $f: (C, \gamma) \rightarrow Result_{svm}$ as an unknown function, which we can evaluate only in certain points and would like to optimize as fast as possible.

Bayesian optimization method builds a model of the function $f$ using a Gaussian Process (GP) and at each step chooses the most "promising" point based on the current GP model. It starts with no information and acts like a random search, but gradually learns that some areas are "better" then others. These methods also try to deal with exploration-exploitation dilemma.

In my research, I use Bayesian optimization a lot, especially when I need to optimize not two, but a dozen of hyperparameters. See this question is you need further details.