2015

Randomized sketches for kernels: Fast and optimal non-parametric regression

Yang, Yun, Pilanci, Mert, Wainwright, Martin J.

Understand

Kernel ridge regression (KRR) is a standard method for performing non-parametric regression over reproducing kernel Hilbert spaces.

Given $n$ samples, the time and space complexity of computing the KRR estimate scale as $\mathcal{O}(n^3)$ and $\mathcal{O}(n^2)$ respectively, and so is prohibitive in many cases.
We propose approximations of KRR based on $m$-dimensional randomized sketches of the kernel matrix, and study how small the projection dimension $m$ can be chosen while still preserving minimax optimality of the approximate KRR estimate.
For various classes of randomized sketches, including those based on Gaussian and randomized Hadamard matrices, we prove that it suffices to choose the sketch dimension $m$ proportional to the statistical dimension (modulo logarithmic factors).

Theory of reproducing kernels
N. Aronszajn · 1950
Earlier work this paper cites.
Some results on Tchebycheffian spline functions
G. Kimeldorf and G. Wahba · 1971
Earlier work this paper cites.
Optimal global rates of convergence for non-parametric regression
C. J. Stone · 1982
Earlier work this paper cites.
Spline models for observational data
G. Wahba · 1990
Earlier work this paper cites.
Ridge regression learning algorithm in dual variables
C. Saunders, A. Gammerman, and V. Vovk · 1998
Earlier work this paper cites.
Empirical Processes in M-Estimation
S. van de Geer · 2000
Earlier work this paper cites.
The Elements of Statistical Learning: Data Mining, Inference and Prediction
T. Hastie, R. Tibshirani, and J. H. Friedman · 2001
Earlier work this paper cites.
The Concentration of Measure Phenomenon
M. Ledoux · 2001
Earlier work this paper cites.
Using the Nyström method to speed up kernel machines
C. Williams and M. Seeger · 2001
Earlier work this paper cites.
Smoothing spline ANOVA models
C. Gu · 2002
Earlier work this paper cites.

Lectures on discrete geometry
J. Matousek · 2002
Cited alongside, same era.
Geometric parameters of kernel machines
S. Mendelson · 2002
Cited alongside, same era.
Reproducing kernel Hilbert spaces in probability and statistics
A. Berlinet and C. Thomas-Agnan · 2004
Cited alongside, same era.
Kernel Methods for Pattern Analysis
J. Shawe-Taylor and N. Cristianini · 2004
Cited alongside, same era.
The Random Projection Method
S. Vempala · 2004
Cited alongside, same era.
Local Rademacher complexities
P. L. Bartlett, O. Bousquet, and S. Mendelson · 2005
Cited alongside, same era.
On the Nyström method for approximating a Gram matrix for improved kernel-based learning
P. Drineas and M. W. Mahoney · 2005
Cited alongside, same era.
Local Rademacher complexities and oracle inequalities in risk minimization
V. Koltchinskii · 2006
Cited alongside, same era.
Fast dimension reduction using rademacher series on dual BCH codes
N. Ailon and E. Liberty · 2009
Cited alongside, same era.
Gaussian estimation: Sequence and wavelet models
I. M. Johnstone
Cited in the paper.
Iterative hessian sketch: Fast and accurate solution approximation for constrained least-squares
Original
M. Pilanci and M. J. Wainwright
Cited in the paper.

New and improved Johnson-Lindenstrauss embeddings via the restricted isometry property
F. Krahmer and R. Ward · 2011
Later among the works it cites.
Improved analysis of the subsampled randomized hadamard transform
J. A. Tropp · 2011
Later among the works it cites.
Sharp analysis of low-rank kernel matrix approximations
F. Bach · 2012
Later among the works it cites.
Minimax-optimal rates for sparse additive models over kernel classes via convex programming
G. Raskutti, M. J. Wainwright, and B. Yu · 2012
Later among the works it cites.
User-friendly tail bounds for sums of random matrices
J. A. Tropp · 2012
Later among the works it cites.
Revisiting the nystrom method for improved large-scale machine learning
Original
A. Gittens and M. W. Mahoney · 2013
Later among the works it cites.
Divide and conquer kernel ridge regression
Y. Zhang, J. C. Duchi, and M. J. Wainwright · 2013
Later among the works it cites.
Fast randomized kernel methods with statistical guarantees
Original
A. E. Alaoui and M. W. Mahoney · 2014
Later among the works it cites.
Randomized sketches of convex programs with sharp guarantees
Original
M. Pilanci and M. J. Wainwright · 2014
Later among the works it cites.

alphaXiv searches the wider corpus for related work and actual follow-ups.

alphaXiv is searching for related work…

Reading the bibliography…