Poster
Ensemble Nystrom Method
Sanjiv Kumar · Mehryar Mohri · Ameet S Talwalkar

Wed Dec 9th 07:00 -- 11:59 PM @ None #None
in Poster Session »

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 significant performance improvements gained over the standard Nystrom approximation.

Author Information

Sanjiv Kumar (Google Research)
Mehryar Mohri (Courant Inst. of Math. Sciences & Google Research)
Ameet S Talwalkar (CMU)

More from the Same Authors