Online kernel learning with nearly constant support vectors

Nyström method has been widely used to improve the computational efficiency of batch kernel learning. The key idea of Nyström method is to randomly sample M support vectors from the collection of T   training instances, and learn a kernel classifier in the space spanned by the randomly sampled support vectors. In this work, we studied online regularized kernel learning using the Nyström method, with a focus on the sample complexity, i.e. the number of randomly sampled support vectors that are needed to yield the optimal convergence rate O(1/T)O(1/T), where T   is the number of training instances received in online learning. We show that, when the loss function is smooth and strongly convex, only O(log2T) randomly sampled support vectors are needed to guarantee an O(logT/T)O(logT/T) convergence rate, which is almost optimal except for the logT factor. We further validate our theory by an extensive empirical study.