Gaussian Kernel faster than Linear

Question

I have a Dataset with 580 samples and 7 features. I compared the time between three kernels: Linear, Quadratic and Gaussian and using RandomizedSearchCV as the following:

from sklearn.model_selection import RandomizedSearchCV
from sklearn.preprocessing import StandardScaler

paramSVMLinear = {
        'kernel': ['linear'],
        'C': [ii for ii in np.linspace(1,1e7,50000)]
        }

scal = StandardScaler()
X = scal.fit_transform(X)

RandomizedSearchCV(SVC(), paramSVMLinear, n_iter=1, cv=2, scoring='accuracy', verbose=4).fit(X_train,Y_train)

SVC(kernel = 'linear').fit(X_train,Y_train)
SVC(kernel = 'poly',degree=2).fit(X_train,Y_train)
SVC(kernel = 'rbf').fit(X_train,Y_train)

The elapsed time in each fit is 187.64 sec, 0.001672 sec, 0.00187 sec, 0.001586 sec. Why the randomized search take so long for 1 iteration and 2 CV? Why the linear kernel take a longer time than RBF? Thanks!

Answer 1

A plausible reason that linear kernel takes longer is that data are not linearly separable, thus it takes longer to fit than a non-linear kernel like RBF.

The kernel trick avoids the explicit mapping that is needed to get linear learning algorithms to learn a nonlinear function or decision boundary. [..] Some algorithms that depend on arbitrary relationships in the native space $X$ would, in fact, have a linear interpretation in a different setting: the range space of $\varphi$. The linear interpretation gives us insight about the algorithm. Furthermore, there is often no need to compute $\varphi$ directly during computation, as is the case with support-vector machines. Some cite this running time shortcut as the primary benefit.

(emphasis mine)

References:

1. Kernel trick

Answer 2

Not inherently faster: Gaussian kernels are not inherently faster than linear kernels. The efficiency of a kernel depends on various factors, including the specific problem and implementation.

Implicit dimensionality reduction: Gaussian kernels can implicitly perform dimensionality reduction, making them efficient in some cases by mapping data to a higher-dimensional space without explicitly transforming the data.

Kernel trick: Gaussian kernels use the kernel trick, which can save computational resources by operating in the feature space without explicitly calculating transformed feature vectors.

Sparse support vectors: In some scenarios, Gaussian kernels result in a sparse set of support vectors, leading to faster prediction times during testing.