Ensemble Nystrom Method

Sanjiv Kumar, Mehryar Mohri, Ameet TalwalkarNeurIPS 2009 · OpenReview

Introduction

The Ensemble Nyström Method scales kernel-based machine learning to massive datasets by combining multiple low-rank approximations into a single, highly accurate "ensemble" estimate. This approach significantly outperforms the standard Nyström method in accuracy while remaining naturally parallelizable and efficient enough to handle datasets with over a million instances.

The Bottleneck of Kernel Methods

Kernel methods—like Support Vector Machines (SVMs) and Kernel Ridge Regression—are staples of machine learning, but they suffer from a major "curse of dimensionality." As the number of data points ($n$) grows, the kernel matrix grows at $O(n^2)$, making storage and computation ($O(n^3)$) impossible for datasets with millions of points.

The standard solution is the Nyström method, which approximates the full matrix using a small, random sample of $m$ columns. However, a single random sample can be "hit or miss" in terms of accuracy. To get a better approximation, you usually need to increase $m$, which quickly becomes computationally expensive. The authors sought a way to achieve higher accuracy without the steep computational climb of the standard approach.

The Ensemble Nyström Approach

The authors propose treating individual Nyström approximations as "experts" and combining them into an ensemble.

  1. The Ensemble Approach: Instead of taking one large sample of columns, the algorithm takes $p$ smaller subsamples. Each subsample is used to create a rank-$k$ Nyström approximation (an "expert").
  2. Weighting Schemes: The experts are combined using a weighted average ($\sum \mu_r \tilde{\mathbf{K}}_r$). The paper explores three ways to choose these weights ($\mu$):
  3. Uniform: Simple averaging ($1/p$). Surprisingly, even this often beats any single expert.
  4. Exponential Weight: Weights are assigned based on how well an expert reconstructs a small, separate validation set of columns.
  5. Ridge Regression: This "learns" the optimal weights by solving a regression problem to minimize reconstruction error on a validation set. This proved to be the most effective method.
  6. Theoretical Innovation: The paper provides new, tighter theoretical error bounds for both the standard and ensemble Nyström methods in both Frobenius and spectral norms, proving that the ensemble approach converges faster than the standard version.

Key Insights and Results

The researchers evaluated their method on a variety of benchmarks (including face images, handwritten digits, protein data, and text) to ensure robustness across different data types.

  • The "Wisdom of the Crowd" for Matrices: Much like ensemble methods in classification (like Random Forests), combining multiple "weak" matrix approximations leads to a "strong" approximation that is more stable and accurate than its components.
  • Superior Accuracy and Rapid Convergence: Across all datasets, the ensemble method (especially with Ridge Regression weights) consistently yielded lower reconstruction errors than the best single Nyström expert. Most of the accuracy gains were realized quickly, typically by the time 10 experts ($p=10$) were combined.
Ensemble methods, particularly Ridge Regression, consistently achieve lower Frobenius error than the best single Nyström expert across multiple datasets.
  • Parallelism by Design: Because each "expert" is calculated independently, the method is perfectly suited for distributed computing. You can train 10 experts on 10 different machines simultaneously, making the time cost nearly identical to a single standard Nyström run.
  • Efficiency over K-Means & 1M Point Scalability: While some researchers use $k$-means clustering to pick "better" columns for Nyström, the authors show that for very large datasets (1M+ points), $k$-means becomes too slow. On the massive SIFT-1M dataset, the ensemble method achieved a 10% relative error using only about 1% of the total columns, outperforming both the mean standard Nyström and the $k$-means sampling approach in "fixed-time" experiments.
Large-scale study demonstrating the Ridge ensemble method outperforming k-means sampling as dataset size scales up to 1 million points.

Limitations and Future Work

  • Memory Overhead: While computationally efficient, the ensemble method requires $p$ times more memory to store the experts during the combination phase compared to a single Nyström approximation. However, the authors note that for $p \approx 10$, this is still well within the limits of modern distributed systems.
  • Validation Set Requirement: The most accurate weighting schemes require a small additional sample of columns (a validation set) to tune the weights.
  • Future Directions: The authors suggest that further refining the error bounds and exploring more sophisticated ways to select or combine experts could lead to even more efficient large-scale kernel machines.

Summary updated

Abstract

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.
BibTeX
@inproceedings{kumar2009ensemble,
  author = {Sanjiv Kumar and Mehryar Mohri and Ameet Talwalkar},
  title = {{Ensemble Nystrom Method}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2009},
  url = {https://openreview.net/forum?id=BJZ1FuWdZr},
}
Figure