Run-Time difference between linear and RBF kernels in SVM

Question

I'm using kernlab package in R. I trained an SVM using linear kernel and RBF kernel with same data set (the number of instances is 3000). When I use a linear kernel, it takes much longer to train the model compared to when I use an RBF kernel (accuracies are similar). Why does this run-time difference exist?

Answer 1

Time difference arises from various sources with SVMs.

First, you need to compute the kernel matrix (i.e. the matrix populated with $K(x_i,x_j)$). Normally, this should take longer for the RBF kernel than for the linear kernel (the linear kernel does not have to call $\exp$ which is the most expansive part).

However, the time of the training part is also a significant part of the training process which consists of solving the quadratic program is variable in $C$ the cost parameters and the kernel matrix of the training samples.

The difference in total training time that you is likely due to the fact that the kernel matrices that you obtain from RBF and linear kernel are different and the optimization problem with the latter one happens to be a much harder problem in this case.