Training complexity of Linear SVM

Question

Which is the actual computational complexity of the learning phase of SVM (let's say, that implemented in LibSVM)?

Thank you

Tamarau

Answer 1

Training complexity of nonlinear SVM is generally between O(n^2) and O(n^3) with n the amount of training instances. The following papers are good references:

• Support Vector Machine Solvers by Bottou and Lin
• SVM-optimization and steepest-descent line search by List and Simon

PS: If you want to use linear kernel, do not use LIBSVM. LIBSVM is a general purpose (nonlinear) SVM solver. It is not an ideal implementation for linear SVM. Instead, you should consider things like LIBLINEAR (by the same authors as LIBSVM), Pegasos or SVM^perf. These have much better training complexity for linear SVM. Training speed can be orders of magnitude better than using LIBSVM.

Carbonous

Link 2 is dead, and for link 1 the document seems to have been removed – Gilli

And what is the complexity of liblinear svm? – Alsup

Answer 2

This is going to be heavily dependent on svm type and kernel. There is a rather technical discussion http://www.csie.ntu.edu.tw/~cjlin/papers/libsvm.pdf. For a quick answer, http://www.csie.ntu.edu.tw/~cjlin/papers/libsvm.pdf, says expect it to be n^2.

Barefaced