Why don't kernel SVMs scale well to millions of samples?

medium

Answer

$O(n^{2})$
$For n = 1M, that's a trillion entries — impossible.$
$Workarounds: (1) linear SVM (LinearSVC / liblinear) which is O(nd) via primal optimization; (2) approximate kernels via random Fourier features / Nyström before feeding to a linear SVM; (3) switch entirely to gradient-boosted trees or neural nets, which routinely handle millions of samples.$

Check yourself — multiple choice

SVMs scale linearly with n
Kernel matrix is $O(n^{2})$ ; at large n use LinearSVC, random features, or switch models
SVMs are always the fastest
Their scaling only depends on the number of features

$O(n^{2})$ kernel matrix + up to $O(n^{3})$ training ⇒ kernel SVMs don't scale to millions of rows.

#svm#optimization

215 interview questions in this topic.