Is it known what is the LIBSVM time complexity when using RBF kernel functions?


The training complexity for nonlinear kernels is roughly between $O(n^2)$ and $O(n^3)$ where n is the number of training data points.

If you are using scikit-learn's implementation of LIBSVM the documentation claims (http://scikit-learn.org/stable/modules/generated/sklearn.svm.SVC.html):

The fit time complexity is more than quadratic with the number of samples which makes it hard to scale to dataset with more than a couple of 10000 samples.

A reference you can use is: http://colt2009.cs.mcgill.ca/papers/021.pdf

Also, the LIBSVM reference which explains the computational complexity can be found in section 4.3 of: http://fbim.fh-regensburg.de/~saj39122/Diplomarbeiten/Miklos/SVM%20Toolboxes/libsvm.pdf

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.