Do kernel methods "scale" with the amount of data?

Question

I've been reading about kernel methods, where you map original $N$ data points to a feature spaces, compute the kernel or gram matrix and plug that matrix into a standard, linear algorithm. This all sounds good when the feature space is infinite dimensional or otherwise very high-dimensional (much much larger than $N$), BUT the kernel matrix itself is also pretty large at $N \times N$, meaning if you double the number of points you quadruple the amount of memory required. Does this mean kernel methods do not scale well to larger data sets? Or is it not necessary to compute the entire kernel matrix and hold the whole thing in memory for most algorithms?

Answer 1

It's not necessary to hold the whole kernel matrix in memory at all times, but ofcourse you pay a price of recomputing entries if you don't. Kernel methods are very efficient in dealing with high input dimensionality thanks to the kernel trick, but as you correctly note they don't scale up that easily to large numbers of training instances.

Nonlinear SVM, for example, has a $\Omega(n^2)$ training complexity ($n$ number of instances). This is no problem for data sets up to a few million instances, but after that it is no longer feasible. At that point, approximations can be used such as fixed-size kernels or ensemble of smaller SVM base models.

Answer 2

There is a rich history of literature about dealing with large kernels.

"Random features for large-scale kernel machines" by Rahimi and Recht is an important milestone. They embed the input in a lower dimension in a randomized fashion to achieve scalability. This work has spawned further interesting works in dealing with different types of kernels etc.

The Nystrom method based approach is another way to deal with large kernels. Again, this approach has been addressed by several works.

Recently, Divide-and-conquer kernel SVM has addressed this problem in distributed setting. Check out: www.cs.utexas.edu/~cjhsieh/dcsvm/

Answer 3

I think some kernel computation can be distributed to the cluster. Then this algorithm could be regarded as scalable, since there are huge amount of memory and cpu in the computing cluster.