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


1 Answer 1


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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