Linear-time approximation to kernel SVM?

Question

Scaling kernel support vector machines to large datasets is a very challenging problem. For linear SVMs, PEGASOS is able to learn efficiently online, so training time scales linearly with the size of the dataset. However, PEGASOS works with the primal formulation of an SVM, and so it can't be extended to kernel methods. To do exact learning of a kernel SVM you must construct the entire Gram matrix, which takes quadratic time in the size of the data. Are there approximate methods for learning kernel SVMs in linear time that don't require the full Gram matrix but still have theoretical guarantees like PEGASOS? Or is this still an open research question?

Answer 1

Update. I just noticed that kernel SVM are now implemented in the Vowpal Wabbit library. The algorithm used is the LASVM algorithm of Bordes et al. (2005)

The following paper: Streamed Learning: One-Pass SVMs remains an interesting reading though.

It does not rely on primal formulation, but on the Minimal Enclosing Ball (MEB) formulation of the problem and proposes a clear algorithm, that trains the SVM in only one pass.

However, the selection of the support vector is not really clear. Besides, no experiment is conducted on the kernelized versions. But it remains the best paper I have read regarding streaming kernel SVM.