Revisiting the Nystrom Method for Improved Large-scale Machine Learning

By Alex Gittens, Michael W. Mahoney. 2013

461 citations recorded by the source corpus.

We reconsider randomized algorithms for the low-rank approximation of SPSD matrices such as Laplacian and kernel matrices that arise in data analysis and machine learning applications. Our main results consist of an empirical evaluation of the performance quality and running time of sampling and projection methods on a diverse suite of SPSD matrices. Our results highlight complementary aspects of sampling versus projection methods, and they point to differences between uniform and nonuniform sampling methods based on leverage scores. We complement our empirical results with a suite of worst-case theoretical bounds for both random sampling and random projection methods. These bounds are qualitatively superior to existing bounds--e.g., improved additive-error bounds for spectral and Frobenius norm error and relative-error bounds for trace norm error.

Subfields: Artificial Intelligence, Computational Mechanics, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Statistics and Probability

Citations in the corpus

Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm (2013, methodology): “See [14, 24,48] for applications of importance sampling to the Nyström method.”
GIANT: Globally Improved Approximate Newton Method for Distributed Optimization (2017, methodology): “Such a notation has been used in compressed sensing [3], matrix completion [2], and randomized linear algebra [6, 40, 39].”
An Introduction to Matrix Concentration Inequalities (2015, unknown): “The paper [56] provides the first theoretical analysis, and the survey [70] contains more complete results.”
Fast Randomized Kernel Methods With Statistical Guarantees (2014, methodology): “Alternatively, S could also be a random projection matrix; or S could be constructed with some other (perhaps deterministic) method, as long as it verifies some structural properties, depending on the application [6, 1, 4, 3].”
Distributed Learning with Regularized Least Squares (2016, background): “Furthermore, (Gittens and Mahoney, 2016) provided a practical reason for avoiding unform boundedness assumption on the eigenfunctions (or eigenvectors) in terms of localization and sparseness.”
When Gaussian Process Meets Big Data: A Review of Scalable GPs (2018, methodology): “K Hence, we approximate the eigen-functions of nn using m data points, leading to the Nystr¨om approximation which greatly improves large-scale kernel learning [53], and enables naive Nystr¨om GP [54].”
Fast Randomized Kernel Ridge Regression with Statistical Guarantees (2015, background): “That is, `i = diag(KkK † k)i, where Kk is the best rank k approximation of K and where K † k is the MoorePenrose inverse of Kk.”
Model Compression and Hardware Acceleration for Neural Networks: A Comprehensive Survey (2020, methodology): “A number of research studies utilize the CUR decomposition [95] for machine-learning applications, especially a variant similar to CUR called Nyström method [96].”
Memory Efficient Kernel Approximation (2014, methodology): “Unfortunately, to approximate kernel matrices, all the above approaches need to compute the entire kernel matrix, so the time complexity is at least O ( dn 2 ).”
Stat260/cs294: Randomized Algorithms for Matrices and Data (methodology): “…Today, we will use the concentration results of the last few classes to go back and make statements about approximating the product of two matrices; and we will also describe an important topic we will spend a great deal more time on, i.e., random projections and Johnson-Lindenstrauss lemmas.”
Sketching as a Tool for Numerical Linear Algebra (2014, background): “The running time of the method in [41] is O(mnmin{m,n}), since subspace sampling is based on sampling with probabilities proportional to the so-called leverage scores, i.e., the row norms of the matrix Vk from the SVD of A. Mahoney and Drineas [87], using again subspace sampling, improved slightly u”
Less is More: Nyström Computational Regularization (2015, methodology): “Nyström with sketching matrices [6] We cover this family by choosing Zm = RmSn, where Sn is the same operator as in the plain Nyström case where we select all the points of the training set and Rm a m × n sketching matrix.”
Less is More: Nystr\"om Computational Regularization (2015, methodology): “tal Nystrom¨ model selection on the computational time. Predictive performance comparison Finally, we consider the performance of the algorithm on several large scale benchmark datasets considered in [6], see Table 1. σ has been chosen on the basis of preliminary data analysis. m and λ have been cho”
Local Group Invariant Representations via Orbit Embeddings (2016, background): “Several schemes for identifying the landmark points have been studied in the literature, including random sampling, sampling based on leverage scores, and clustering based landmark selection [19,21].”
A statistical perspective on algorithmic leveraging (2013, methodology): “plementation of the Hadamard-based random projection, this algorithm runs faster than traditional deterministic algorithms based on Lapack for matrices as small as several thousand by several hundred [3, 17]. We have implemented in the software environment R two variants of this fast algorithm of [1”