Near Input Sparsity Time Kernel Embeddings via Adaptive Sampling

David Woodruff, Amir Zandieh
Proceedings of the 37th International Conference on Machine Learning, PMLR 119:10324-10333, 2020.

Abstract

To accelerate kernel methods, we propose a near input sparsity time method for sampling the high-dimensional space implicitly defined by a kernel transformation. Our main contribution is an importance sampling method for subsampling the feature space of a degree $q$ tensoring of data points in almost input sparsity time, improving the recent oblivious sketching of (Ahle et al., 2020) by a factor of $q^{5/2}/\epsilon^2$. This leads to a subspace embedding for the polynomial kernel as well as the Gaussian kernel with a target dimension that is only linearly dependent on the statistical dimension of the kernel and in time which is only linearly dependent on the sparsity of the input dataset. We show how our subspace embedding bounds imply new statistical guarantees for kernel ridge regression. Furthermore, we empirically show that in large-scale regression tasks, our algorithm outperforms state-of-the-art kernel approximation methods.

Cite this Paper

BibTeX
@InProceedings{pmlr-v119-woodruff20a, title = {Near Input Sparsity Time Kernel Embeddings via Adaptive Sampling}, author = {Woodruff, David and Zandieh, Amir}, booktitle = {Proceedings of the 37th International Conference on Machine Learning}, pages = {10324--10333}, year = {2020}, editor = {III, Hal Daumé and Singh, Aarti}, volume = {119}, series = {Proceedings of Machine Learning Research}, month = {13--18 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v119/woodruff20a/woodruff20a.pdf}, url = {https://proceedings.mlr.press/v119/woodruff20a.html}, abstract = {To accelerate kernel methods, we propose a near input sparsity time method for sampling the high-dimensional space implicitly defined by a kernel transformation. Our main contribution is an importance sampling method for subsampling the feature space of a degree $q$ tensoring of data points in almost input sparsity time, improving the recent oblivious sketching of (Ahle et al., 2020) by a factor of $q^{5/2}/\epsilon^2$. This leads to a subspace embedding for the polynomial kernel as well as the Gaussian kernel with a target dimension that is only linearly dependent on the statistical dimension of the kernel and in time which is only linearly dependent on the sparsity of the input dataset. We show how our subspace embedding bounds imply new statistical guarantees for kernel ridge regression. Furthermore, we empirically show that in large-scale regression tasks, our algorithm outperforms state-of-the-art kernel approximation methods.} }
Endnote
%0 Conference Paper %T Near Input Sparsity Time Kernel Embeddings via Adaptive Sampling %A David Woodruff %A Amir Zandieh %B Proceedings of the 37th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2020 %E Hal Daumé III %E Aarti Singh %F pmlr-v119-woodruff20a %I PMLR %P 10324--10333 %U https://proceedings.mlr.press/v119/woodruff20a.html %V 119 %X To accelerate kernel methods, we propose a near input sparsity time method for sampling the high-dimensional space implicitly defined by a kernel transformation. Our main contribution is an importance sampling method for subsampling the feature space of a degree $q$ tensoring of data points in almost input sparsity time, improving the recent oblivious sketching of (Ahle et al., 2020) by a factor of $q^{5/2}/\epsilon^2$. This leads to a subspace embedding for the polynomial kernel as well as the Gaussian kernel with a target dimension that is only linearly dependent on the statistical dimension of the kernel and in time which is only linearly dependent on the sparsity of the input dataset. We show how our subspace embedding bounds imply new statistical guarantees for kernel ridge regression. Furthermore, we empirically show that in large-scale regression tasks, our algorithm outperforms state-of-the-art kernel approximation methods.
APA
Woodruff, D. & Zandieh, A.. (2020). Near Input Sparsity Time Kernel Embeddings via Adaptive Sampling. Proceedings of the 37th International Conference on Machine Learning, in Proceedings of Machine Learning Research 119:10324-10333 Available from https://proceedings.mlr.press/v119/woodruff20a.html.

Related Material