Ensemble Nystrom Method

Part of Advances in Neural Information Processing Systems 22 (NIPS 2009)

Bibtex Metadata Paper


Sanjiv Kumar, Mehryar Mohri, Ameet Talwalkar


A crucial technique for scaling kernel methods to very large data sets reaching or exceeding millions of instances is based on low-rank approximation of kernel matrices. We introduce a new family of algorithms based on mixtures of Nystrom approximations, ensemble Nystrom algorithms, that yield more accurate low-rank approximations than the standard Nystrom method. We give a detailed study of multiple variants of these algorithms based on simple averaging, an exponential weight method, or regression-based methods. We also present a theoretical analysis of these algorithms, including novel error bounds guaranteeing a better convergence rate than the standard Nystrom method. Finally, we report the results of extensive experiments with several data sets containing up to 1M points demonstrating the signi´Čücant performance improvements gained over the standard Nystrom approximation.