Why does the training time of SVMs dramatically decrease after applying dimensionality reduction to the features? Training an SVM with an RBF kernel model with c = 5.5 and gamma = 1.06, for a 5-class classification problem on the NSL-KDD train data-set with 122 features using one vs rest strategy takes $2162$ seconds. Also, considering binary classification (c = 10, gamma = 4), it takes $520.56$ seconds.
After dimensionality reduction, from 122 to 30, using a sparse auto-encoder, the training time falls dramatically, from $2162$ to $240$ and $520$ to $170$, while using the same hyperparameters for the RBF-kernel.
What is the reason for that? Is it not true that using kernel neutralized the effect of high dimensions?
SVM complexity is $O(\max(n,d)\min(n,d)^2)$ according to Chapelle, Olivier. &quot;Training a support vector machine in the primal.&quot; Neural Computation 19.5 (2007): 1155-1178.
$n$ is the number of instances and $d$ is the number of dimensions. I'm assuming that you have more instances than dimensions giving a complexity of $O(nd^2)$. Hopefully this explains fully why reducing the number of dimensions will reduce the training time.