Nyström Method vs Random Fourier Features: A Theoretical and Empirical Comparison

By Tianbao Yang, Yu-Feng Li, Mehrdad Mahdavi, Rong Jin, Zhi-Hua Zhou. 2012

369 citations recorded by the source corpus.

How researchers see this paper

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

Citations in the corpus

On the Error of Random Fourier Features (2015, methodology): “Analyses of generalization error in the induced RKHS , such as Rahimi and Recht (2008a); Yang et al. (2012), are more useful in this case.”
Sharp analysis of low-rank kernel matrix approximations (2012, neutral): “Note however that the dimension reduction is then independent of the particular distributions of the input data points, while the column sampling approach is; see Yang et al. (2012) for more discussion.”
Orthogonal Random Features (2016, methodology): “In this paper, we focus on approximating Gaussian kernels following the seminal Random Fourier Features (RFF) framework [19], which has been extensively studied both theoretically and empirically [26, 20, 23].”
Randomness in neural networks: an overview (2017, background): “Yang et al.(72) introduced “a rejection procedure that rejects the sample Fourier components when they do not align well with the top eigenfunctions estimated from the sampled data” as a possible future line of research.”
Randomized Nonlinear Component Analysis (2014, methodology): “We also compare to the Nyström method, set to construct an m−dimensional feature space formed by the evaluations of the Gaussian kernel on m random points from the training set (Yang et al., 2012).”
Fast and scalable polynomial kernels via explicit feature maps (2013, methodology): “Instead of approximating the kernel matrix, recent approaches [10, 12, 16, 20, 21, 24] approximate the kernels by explicitly mapping data into a relatively low-dimensional random feature space.”
Fast geometric learning with symbolic matrices (2020, unknown): “To speed up this operation, a ﬁrst idea is to rely on low-rank decompositions of the kernel matrix ( K i,j ) [90, 111, 116].”
A Survey of Multi-View Representation Learning (2016, unknown): “Consequently, a deep canonically correlated autoencoder (DCCAE) [20] is introduced through jointly optimizing the objectives of the deep CCA and the separate autoencoders from multiple views.”
EPIC: Efficient Private Image Classification (or: Learning from the Masters) (2019, background): “Although Nyström approximations outperform randomly extracted features [55] in terms of accuracy, the fact that they are data dependent makes them unfit for our purposes, as they can only be computed by applying non-linear functions on the private inputs.”
Less is More: Nyström Computational Regularization (2015, background): “Results in this direction, albeit suboptimal, were first derived in [20] (see also [21,22]), and more recently in [23,24].”
A Survey of Modern Questions and Challenges in Feature Extraction (2015, methodology): “Common algorithms for metric learning include local LDA (Hastie and Tibshirani, 1996), relevance component analysis (Bar-Hillel et al., 2003), large margin nearest neighbor (Weinberger et al., 2005), and Bayesian active distance metric learning (Yang et al., 2012a).”
Kernel methods match Deep Neural Networks on TIMIT (2014, methodology): “Although the Nyström method has shown better performance theoretically [7], it involves more expensive computations and larger memory requirements for large-scale tasks.”
Improved Bounds for the Nyström Method With Application to Kernel Classification (2011, unknown): “Parameter ρ is introduced to characterize the eigengap which is given by Evidently, the smaller the ρ , the larger the eigengap.”
Memory Efficient Kernel Approximation (2014, methodology): “Recently, Yang et al. (2012) showed that the Nystr¨om method has a better generalization error bound than the RKS approach if the gap in the eigen-spectrum of the kernel matrix is large.”
Generalization Properties of Learning with Random Features (2016, background): “[20, 21, 22], essentially confirm these considerations, albeit the analysis in [22] suggests that fewer random features could suffice if sampled in a problem dependent way.”
On Deep Multi-View Representation Learning (2015, methodology): “As described in Section 3.2, in both FKCCA/NKCCA, we transform the original inputs to an M -dimensional feature space where the inner products between samples approximate the kernel similarities (Yang et al., 2012).”
Hybrid Random Features (2021, methodology): “Several other techniques such as Nystr¨om method (Yang et al., 2012; Williams & Seeger, 2000; Rudi et al., 2015) were proposed to construct data-dependent feature representations.”
From Dependence to Causation (2016, background): “This adaptation results in a reduction of the Nyström approximation error from O( n√ m ) to O( nm) when the gap between the two largest eigenvalues of the true kernel matrix K is large (Yang et al., 2012).”