Fast Randomized Kernel Methods With Statistical Guarantees

By A. Alaoui, Michael W. Mahoney. 2014

93 citations recorded by the source corpus.

One approach to improving the running time of kernel-based machine learning methods is to build a small sketch of the input and use it in lieu of the full kernel matrix in the machine learning task of interest. Here, we describe a version of this approach that comes with running time guarantees as well as improved guarantees on its statistical performance. By extending the notion of \emph{statistical leverage scores} to the setting of kernel ridge regression, our main statistical result is to identify an importance sampling distribution that reduces the size of the sketch (i.e., the required number of columns to be sampled) to the \emph{effective dimensionality} of the problem. This quantity is often much smaller than previous bounds that depend on the \emph{maximal degrees of freedom}. Our main algorithmic result is to present a fast algorithm to compute approximations to these scores. This algorithm runs in time that is linear in the number of samples---more precisely, the running time is $O(np^2)$, where the parameter $p$ depends only on the trace of the kernel matrix and the regularization parameter---and it can be applied to the matrix of feature vectors, without having to form the full kernel matrix. This is obtained via a variant of length-squared sampling that we adapt to the kernel setting in a way that is of independent interest. Lastly, we provide empirical results illustrating our theory, and we discuss how this new notion of the statistical leverage of a data point captures in a fine way the difficulty of the original statistical learning problem.

Subfields: Artificial Intelligence, Computational Mechanics

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

Citations in the corpus

Optimal Rates for Random Fourier Features (2015, neutral): “In order to resolve this bottleneck, numerous solutions have been proposed, such as low-rank matrix approximations [28, 9, 1], explicit feature maps designed for additive kernels [26, 14], hashing [22, 12], and random Fourier features (RFF) [16] constructed for shift-invariant kernels, the focus of…”
Fast Randomized Kernel Ridge Regression with Statistical Guarantees (2015, background): “All the proofs are deferred to the appendix (or see [1]).”
On the Equivalence between Quadrature Rules and Random Features (2015, methodology): “Then, Bernstein concentration inequalities for operators (Minsker, 2011) can be used in a way similar to the work of Bach (2013); El Alaoui and Mahoney (2014) on column sampling.”
Randomized sketches for kernels: Fast and optimal non-parametric regression (2015, background): “In this vein, recent work by Alaoui and Mahoney [2] suggests a Nyström approximation nonuniform sampling of the columns of kernel matrix involving the leverage scores.”
Less is More: Nyström Computational Regularization (2015, background): “Extensive experimental analysis shows that the considered approach achieves state of the art performances on benchmark large scale datasets.”
Less is More: Nystr\"om Computational Regularization (2015, background): “hod. In NIPS, pages 1060–1068. Curran Associates, Inc., 2009. [10] Mu Li, James T. Kwok, and Bao-Liang Lu. Making Large-Scale Nystro¨m Approximation Possible. In ICML, pages 631–638. Omnipress, 2010. [11] Kai Zhang, Ivor W. Tsang, and James T. Kwok. Improved Nystro¨m Low-rank Approximation and Error”
Generalization Properties of Learning with Random Features (2016, methodology): “[1] Ahmed Alaoui and Michael W Mahoney.”
The Statistics of Streaming Sparse Regression (2014, background): “Meanwhile, we can check that L is a quadratic function with leading term 12w >E [ xx> ] w, and so (2) holds as long as Cov [x[S]] αI.”