Using the Nyström Method to Speed Up Kernel Machines

By Christopher K. I. Williams, Matthias W. Seeger. 2000

2,760 citations recorded by the source corpus.

Subfields: Optimization & Training, Statistical Learning Theory

How researchers see this paper

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

In Optimization & Training

In Statistical Learning Theory

Citations in the corpus

Kernel Mean Embedding of Distributions: A Review and Beyonds (2016, methodology): “This survey will deal mostly with the embedding of distributions in a Hilbert space, while extensions to Banach spaces are investigated in Zhang et al. (2009) and Sriperumbudur et al.”
Invariant Causal Prediction for Nonlinear Models (2017, methodology): “In order to generalize the method to settings where an appropriate basis expansion of f is unknown, we look at ways to ﬁnd such a suitable basis expansion automatically by using random features (Williams and Seeger, 2001; Rahimi and Recht, 2008).”
Optimal Rates for Random Fourier Features (2015, background): “We also propose a RFF approximation to derivatives of a kernel with a theoretical study on its approximation quality.”
On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions (2015, methodology): “We consider the empirical risk P and the expected risk L ( f ) = E ℓ ( y, f ( x )) , with x having the marginal distribution dρ that we consider in earlier sections.”
Sharp analysis of low-rank kernel matrix approximations (2012, neutral): “This appears through different formulations within numerical linear algebra or machine learning, e.g., Nystr¨om method (Williams and Seeger, 2001), sparse greedy approximations (Smola and Sch¨olkopf, 2000), incomplete Cholesky decomposition ( Fine and Scheinberg, 2001; Bach and Jordan, 2005),…”
Functional Regularisation for Continual Learning using Gaussian Processes (2019, methodology): “(9) This quantity appears in the ELBO in (Titsias, 2009) and it has deep connections with the Nystróm approximation (Williams & Seeger, 2001) and principal component analysis (PCA).”
A Kernel Method for the Two-Sample-Problem (2006, background): “iance Varz,z′[h(z,z′)]. We end by noting another potential approach to reducing the computational cost of the MMD, by computing a low rank approximation to the Gram matrix (Fine and Scheinberg, 2001; Williams and Seeger, 2001; Smola and Scho¨lkopf, 2000). An incremental computation of the MMD based ”
Convolutional Kernel Networks (2014, methodology): “Several schemes have been proposed for approximating a non-linear kernel with a linear one, such as the Nyström method and its variants [5, 30], which consist of projecting the data onto a finitedimensional subspace of the Hilbert space for which the kernel is reproducing.”
Scalable Kernel Methods via Doubly Stochastic Gradients (2014, neutral): “Many works, such as Greedy basis selection techniques [1], Nyström approximation [2] and incomplete Cholesky decomposition [3], all followed this strategy.”
Divide and conquer kernel ridge regression: a distributed algorithm with minimax optimal rates (2013, methodology): “One family of approaches is based on low-rank approximation of the kernel matrix; examples include kernel PCA (Sch¨olkopf et al., 1998), the incomplete Cholesky decomposition (Fine and Scheinberg, 2002), or Nystr¨om sampling (Williams and Seeger, 2001).”
Nyströmformer: A Nystöm-based Algorithm for Approximating Self-Attention (2021, methodology): “The starting point of our work is to reduce the computational cost of self-attention in Transformers using the Nystr¨om method, widely adopted for matrix approximation (Williams and Seeger 2001; Drineas and Mahoney 2005; Wang and Zhang 2013).”
Fundamental Limits of Online and Distributed Algorithms for Statistical Learning and Estimation (2013, background): “There has been considerable effort in developing and analyzing algorithms for such problems with reduced memory footprint (e.g. [43, 5, 10, 54, 49]).”
Thoughts on Massively Scalable Gaussian Processes (2015, methodology): “…process model, including a full GP, inducing points methods such as FITC (Snel-son and Ghahramani, 2006), or the Big Data GP (Hensman et al., 2013), or ﬁnite basis models (e.g., Yang et al., 2015; L´azaro-Gredilla et al., 2010; Rahimi and Recht, 2007; Le et al., 2013; Williams and Seeger, 2001).”
Biological Sequence Modeling with Convolutional Kernel Networks (2017, positive): “A typical workaround is the Nystr¨om approximation [Williams and Seeger, 2001], which builds an explicit q -dimensional mapping ψ : X → R q for a reasonably small q approximating the kernel, i.e. , such that ψ ( x ) , ψ ( x ′ ) R q ≃ K ( x , x ′ ).”
Network Embedding as Matrix Factorization: Unifying DeepWalk, LINE, PTE, and node2vec (2017, methodology): “In our algorithm, we first approximate D − 1 / 2 AD − 1 / 2 with its top-h h Since only top-h eigenpairs are required and the matrix is sparse, we can perform decomposition using the Arnoldi method [19] which achieves significant time reduction [45].”
The Multiscale Laplacian Graph Kernel (2016, methodology): “…of the projection of φ ( v g j ) onto ˜ W G , i.e., The above procedure is similar to the popular Nystr¨om approximation for kernel matrices (Williams & Seeger, 2001; Drineas & Mahoney, 2005), except that in our case the ultimate goal is not to approximate the Gram matrix (12) itself, but…”
The Vendi Score: A Diversity Evaluation Metric for Machine Learning (2022, methodology): “When embeddings aren’t available, the Vendi Score can be approximated using column sampling methods (i.e. the Nyström method; Williams and Seeger, 2000).”