Sampling Techniques for Kernel Methods
Abstract
We propose randomized techniques for speeding up Kernel Principal Component Analysis on three levels: sampling and quantization of the Gram matrix in training, randomized rounding in evaluating the kernel expansions, and random projections in evaluating the kernel itself. In all three cases, we give sharp bounds on the accuracy of the obtained ap- proximations. Rather intriguingly, all three techniques can be viewed as instantiations of the following idea: replace the kernel function by a “randomized kernel” which behaves like
Cite
Text
Achlioptas et al. "Sampling Techniques for Kernel Methods." Neural Information Processing Systems, 2001.Markdown
[Achlioptas et al. "Sampling Techniques for Kernel Methods." Neural Information Processing Systems, 2001.](https://mlanthology.org/neurips/2001/achlioptas2001neurips-sampling/)BibTeX
@inproceedings{achlioptas2001neurips-sampling,
title = {{Sampling Techniques for Kernel Methods}},
author = {Achlioptas, Dimitris and Mcsherry, Frank and Schölkopf, Bernhard},
booktitle = {Neural Information Processing Systems},
year = {2001},
pages = {335-342},
url = {https://mlanthology.org/neurips/2001/achlioptas2001neurips-sampling/}
}