# Number of kernel evaluations in SVM training

What is the typical number of kernel evaluations (between two training vectors) performed during a (kernelized) Support Vector Machine (SVM) training?

I am asking this question because I need to determine how much I need to optimize the kernel in order to have some hope to do the training in a reasonable amount of time. The current kernel calculation time is prohibitive (1+ hour), but there is room for improvement (by many orders of magnitude).

Note: There are about 60k vectors in one class and 10k vectors in the other one.

• Useful reference, indeed. It reads "(…) the computational cost of solving the SVM problem has both a quadratic and a cubic component. It grows at least like $n^2$ when C is small and $n^3$ when C gets large." It also reads "In practice, computing kernel values often accounts for more than half the total computing time." The only missing information is the typical factors in front of these asymptotic complexities in practical implementations: do you have any information on this? – Eric O Lebigot Apr 8 '13 at 12:00