A review of Nyström methods for large-scale machine learning

Shiliang Sun, Jing Zhao, Jiang ZhuInformation Fusion 2015 · DOI

TL;DR

This paper provides a comprehensive review of Nyström methods, a class of algorithms for efficiently approximating large matrices in machine learning. It categorizes various Nyström methods and sampling techniques, discusses their theoretical underpinnings and practical performance, and highlights their applications in areas like manifold learning and spectral clustering.

What Problem Does This Paper Address?

Many machine learning tasks, especially those involving large datasets, require operations on massive matrices. Computing inverses or performing eigenvalue decompositions on these matrices can be computationally prohibitive, leading to high time and space complexities (e.g., O(n³) and O(n²)). This paper addresses the challenge of making these operations scalable by reviewing Nyström methods, which offer efficient low-rank approximations of these large matrices.

Methods

The paper reviews various Nyström methods, which generally involve sampling a subset of columns from the original matrix to construct an approximation. Key methods discussed include:

  • Standard Nyström Method: A foundational technique that samples columns, computes a pseudo-inverse, and reconstructs the matrix.
  • Enhanced Nyström Methods: Several variations are presented, such as:
  • Density-weighted Nyström (DW-Nyström): Incorporates a density function to weight samples.
  • Ensemble Nyström: Combines multiple Nyström approximations with mixture weights.
  • Modified Nyström: Borrows techniques from CUR decomposition for improved accuracy.
  • SS-Nyström (Spectral Shifting): Addresses issues with bottom eigenvalues and can handle matrix inverses.
  • Sampling Methods: A crucial component of Nyström methods, these are categorized into:
  • Uniform Sampling: Samples columns with equal probability.
  • Informative-Column Sampling: Selects columns based on their information content. This is further divided into:
  • Fixed Sampling: Uses a predetermined sampling distribution.
  • Adaptive Sampling: Modifies the sampling distribution iteratively.
  • Specific sampling techniques like diagonal sampling, column-norm sampling, leverage-score sampling, determinant sampling, SMGA, ICL, K-means sampling, adaptive-full, adaptive-partial, and deterministic sampling are detailed.

Datasets

Not discussed in the paper. The paper focuses on theoretical aspects and general algorithmic approaches rather than specific empirical evaluations on particular datasets.

Key Insights and Ideas

  • The Tradeoff Between Efficiency and Accuracy: A recurring theme is the inherent tradeoff between the computational efficiency of sampling methods (like uniform sampling) and the accuracy of the resulting matrix approximation. Informative-column sampling generally yields better accuracy but at a higher computational cost.
  • The Importance of Sampling: The choice of sampling method significantly impacts the performance of Nyström methods. The paper highlights how different sampling strategies are better suited for matrices with varying structural properties (e.g., coherence).
  • Nyström Methods as Information Fusion: The paper frames Nyström methods as a form of information fusion, leveraging partial data to approximate desired matrix properties.
  • Adaptability is Key: Adaptive sampling methods, which adjust their strategy based on intermediate results, often provide better accuracy than fixed sampling methods, though they can be more computationally intensive.
  • Addressing Specific Challenges: Different Nyström variants are designed to tackle specific issues, such as handling large bottom eigenvalues (SS-Nyström) or improving accuracy in specific scenarios (Modified Nyström).

Key Results

  • Scalability: Nyström methods enable the scaling of previously intractable machine learning tasks, such as Gaussian process regression, from O(n³) to O(l²n) complexity, where 'l' is the number of sampled columns.
  • Theoretical Guarantees: The paper presents various theorems detailing deterministic and lower error bounds for different Nyström methods and sampling strategies, providing theoretical justification for their performance.
  • Empirical Performance: While not detailing specific experiments, the paper references studies showing that Nyström methods can effectively extract low-dimensional structures from large datasets (e.g., millions of images) and outperform traditional methods in applications like spectral clustering.
  • Application Breadth: Nyström methods are shown to be applicable to a wide range of machine learning tasks, including manifold learning, spectral clustering, Gaussian processes, kernel SVMs, and kernel ridge regression.

Limitations and Future Work

  • Computational Cost of Sampling: While Nyström methods offer scalability, some advanced sampling techniques (e.g., determinant sampling) can still be computationally expensive.
  • Matrix Approximation for Non-SPSD Matrices: The standard Nyström methods are primarily designed for Symmetric Positive Semidefinite (SPSD) matrices. Extending these methods to arbitrary matrices is an ongoing area of research.
  • Open Problems: The paper identifies several open problems, including:
  • Multiple-Kernel Learning: Developing new methods to determine optimal parameters for combining multiple kernels using ensemble Nyström.
  • Multi-task Learning: Approximating large covariance matrices in multi-task learning, especially when kernels are in free-form.
  • Multiple-Output Models: Developing more efficient strategies for approximating large covariance matrices in multiple-output models, particularly when the number of outputs is large.
  • Cascade Nyström Approximation: Further research and experimental verification are needed for cascade Nyström approximation strategies.

Summary updated

BibTeX
@article{sun2015review,
  author = {Shiliang Sun and Jing Zhao and Jiang Zhu},
  title = {{A review of Nyström methods for large-scale machine learning}},
  journal = {Information Fusion},
  year = {2015},
  doi = {10.1016/j.inffus.2015.03.001},
}
Figure