2019

Simple and Almost Assumption-Free Out-of-Sample Bound for Random Feature Mapping

Wang, Shusen

Understand

Random feature mapping (RFM) is a popular method for speeding up kernel methods at the cost of losing a little accuracy.

We study kernel ridge regression with random feature mapping (RFM-KRR) and establish novel out-of-sample error upper and lower bounds.
While out-of-sample bounds for RFM-KRR have been established by prior work, this paper's theories are highly interesting for two reasons.
On the one hand, our theories are based on weak and valid assumptions.

Built on

Über die praktische auflösung von integralgleichungen mit anwendungen auf randwertaufgaben
Evert J. Nyström · 1930
Earlier work this paper cites.
Topics in matrix analysis. 1991
Roger A. Horn and Charles R. Johnson · 1991
Earlier work this paper cites.
Nonlinear component analysis as a kernel eigenvalue problem
Bernhard Schölkopf, Alexander Smola, and Klaus-Robert Müller · 1998
Earlier work this paper cites.
Using the Nyström method to speed up kernel machines
Christopher Williams and Matthias Seeger · 2001
Earlier work this paper cites.
Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond
Bernhard Schölkopf and Alexander J. Smola · 2002
Earlier work this paper cites.
On the Nyström method for approximating a Gram matrix for improved kernel-based learning
Petros Drineas and Michael W. Mahoney · 2005
Earlier work this paper cites.
On the eigenspectrum of the Gram matrix and the generalisation error of kernel PCA
John Shawe-Taylor, Christopher K. I. Williams, Nello Cristianini, and Jaz Kandola · 2005
Earlier work this paper cites.
Learning bounds for kernel regression using effective data dimensionality
Tong Zhang · 2005
Earlier work this paper cites.
Statistical properties of kernel principal component analysis
Gilles Blanchard, Olivier Bousquet, and Laurent Zwald · 2007
Earlier work this paper cites.
Optimal rates for the regularized least-squares algorithm
Andrea Caponnetto and Ernesto De Vito · 2007
Earlier work this paper cites.
Random features for large-scale kernel machines
Ali Rahimi and Benjamin Recht · 2007
Earlier work this paper cites.
Weighted sums of random kitchen sinks: replacing minimization with randomization in learning
Ali Rahimi and Benjamin Recht · 2009
Earlier work this paper cites.
Optimal rates for regularized least squares regression
Ingo Steinwart, Don R Hush, Clint Scovel, et al · 2009
Earlier work this paper cites.

Similar

On the impact of kernel approximation on learning accuracy
Corinna Cortes, Mehryar Mohri, and Ameet Talwalkar · 2010
Cited alongside, same era.
Sampling methods for the Nyström method
Sanjiv Kumar, Mehryar Mohri, and Ameet Talwalkar · 2012
Cited alongside, same era.
Nyström method vs random Fourier features: A theoretical and empirical comparison
Tianbao Yang, Yu-Feng Li, Mehrdad Mahdavi, Rong Jin, and Zhi-Hua Zhou · 2012
Cited alongside, same era.
Sharp analysis of low-rank kernel matrix approximations
Francis Bach · 2013
Cited alongside, same era.
Fastfood-computing hilbert space expansions in loglinear time
Quoc Le, Tamás Sarlós, and Alexander Smola · 2013
Cited alongside, same era.
Improving CUR matrix decomposition and the Nyström approximation via adaptive sampling
Shusen Wang and Zhihua Zhang · 2013
Cited alongside, same era.
Kernel methods match deep neural networks on timit
Po-Sen Huang, Haim Avron, Tara N Sainath, Vikas Sindhwani, and Bhuvana Ramabhadran · 2014
Cited alongside, same era.
Randomized nonlinear component analysis
David Lopez-Paz, MPG DE, Suvrit Sra, Zoubin Ghahramani, and Bernhard Schölkopf · 2014
Cited alongside, same era.
Fast Randomized Kernel Ridge Regression with Statistical Guarantees
Ahmed Alaoui and Michael W. Mahoney · 2015
Cited alongside, same era.
Less is more: Nyström computational regularization
Alessandro Rudi, Raffaello Camoriano, and Lorenzo Rosasco · 2015
Cited alongside, same era.
Optimal rates for random Fourier features
Bharath Sriperumbudur and Zoltán Szabó · 2015
Cited alongside, same era.
An introduction to matrix concentration inequalities
Joel A Tropp et al · 2015
Cited alongside, same era.

Then

Divide and conquer kernel ridge regression: a distributed algorithm with minimax optimal rates
Yuchen Zhang, John Duchi, and Martin Wainwright · 2015
Later among the works it cites.
Streaming kernel principal component analysis
Mina Ghashami, Daniel J Perry, and Jeff Phillips · 2016
Later among the works it cites.
Revisiting the Nyström method for improved large-scale machine learning
Alex Gittens and Michael W. Mahoney · 2016
Later among the works it cites.
Random Fourier features for kernel ridge regression: approximation bounds and statistical guarantees
Haim Avron, Michael Kapralov, Cameron Musco, Christopher Musco, Ameya Velingker, and Amir Zandieh · 2017
Later among the works it cites.
On the equivalence between kernel quadrature rules and random feature expansions
Francis Bach · 2017
Later among the works it cites.
Kernel approximation methods for speech recognition
Original
Avner May, Alireza Bagheri Garakani, Zhiyun Lu, Dong Guo, Kuan Liu, Aurélien Bellet, Linxi Fan, Michael Collins, Daniel Hsu, Brian Kingsbury, et al · 2017
Later among the works it cites.
Recursive sampling for the Nystrom method
Cameron Musco and Christopher Musco · 2017
Later among the works it cites.
Generalization properties of learning with random features
Alessandro Rudi and Lorenzo Rosasco · 2017
Later among the works it cites.
Approximate kernel PCA using random features: Computational vs. statistical trade-off
Original
Bharath Sriperumbudur and Nicholas Sterge · 2017
Later among the works it cites.
Fixed-Rank Approximation of a Positive-Semidefinite Matrix from Streaming Data
Original
Joel A. Tropp, Alp Yurtsever, Madeleine Udell, and Volkan Cevher · 2017
Later among the works it cites.
Scalable kernel k-means clustering with Nystrom approximation: Relative-error bounds
Original
Shusen Wang, Alex Gittens, and Michael W. Mahoney · 2017
Later among the works it cites.
Streaming kernel PCA with O ~ ( n ) {\tilde{{O}}}(\sqrt{n}) random features
Md Enayat Ullah, Poorya Mianjy, Teodor Vanislavov Marinov, and Raman Arora · 2018
Later among the works it cites.

Beyond the bibliography

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

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…