Quasi-Monte Carlo Feature Maps for Shift-Invariant Kernels

Jiyan Yang, Vikas Sindhwani, Haim Avron, Michael Mahoney
Proceedings of the 31st International Conference on Machine Learning, PMLR 32(1):485-493, 2014.

Abstract

We consider the problem of improving the efficiency of randomized Fourier feature maps to accelerate training and testing speed of kernel methods on large datasets. These approximate feature maps arise as Monte Carlo approximations to integral representations of shift-invariant kernel functions (e.g., Gaussian kernel). In this paper, we propose to use Quasi-Monte Carlo (QMC) approximations instead where the relevant integrands are evaluated on a low-discrepancy sequence of points as opposed to random point sets as in the Monte Carlo approach. We derive a new discrepancy measure called box discrepancy based on theoretical characterizations of the integration error with respect to a given sequence. We then propose to learn QMC sequences adapted to our setting based on explicit box discrepancy minimization. Our theoretical analyses are complemented with empirical results that demonstrate the effectiveness of classical and adaptive QMC techniques for this problem.

Cite this Paper

BibTeX
@InProceedings{pmlr-v32-yangb14, title = {Quasi-Monte Carlo Feature Maps for Shift-Invariant Kernels}, author = {Yang, Jiyan and Sindhwani, Vikas and Avron, Haim and Mahoney, Michael}, booktitle = {Proceedings of the 31st International Conference on Machine Learning}, pages = {485--493}, year = {2014}, editor = {Xing, Eric P. and Jebara, Tony}, volume = {32}, number = {1}, series = {Proceedings of Machine Learning Research}, address = {Bejing, China}, month = {22--24 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v32/yangb14.pdf}, url = {https://proceedings.mlr.press/v32/yangb14.html}, abstract = {We consider the problem of improving the efficiency of randomized Fourier feature maps to accelerate training and testing speed of kernel methods on large datasets. These approximate feature maps arise as Monte Carlo approximations to integral representations of shift-invariant kernel functions (e.g., Gaussian kernel). In this paper, we propose to use Quasi-Monte Carlo (QMC) approximations instead where the relevant integrands are evaluated on a low-discrepancy sequence of points as opposed to random point sets as in the Monte Carlo approach. We derive a new discrepancy measure called box discrepancy based on theoretical characterizations of the integration error with respect to a given sequence. We then propose to learn QMC sequences adapted to our setting based on explicit box discrepancy minimization. Our theoretical analyses are complemented with empirical results that demonstrate the effectiveness of classical and adaptive QMC techniques for this problem.} }
Endnote
%0 Conference Paper %T Quasi-Monte Carlo Feature Maps for Shift-Invariant Kernels %A Jiyan Yang %A Vikas Sindhwani %A Haim Avron %A Michael Mahoney %B Proceedings of the 31st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2014 %E Eric P. Xing %E Tony Jebara %F pmlr-v32-yangb14 %I PMLR %P 485--493 %U https://proceedings.mlr.press/v32/yangb14.html %V 32 %N 1 %X We consider the problem of improving the efficiency of randomized Fourier feature maps to accelerate training and testing speed of kernel methods on large datasets. These approximate feature maps arise as Monte Carlo approximations to integral representations of shift-invariant kernel functions (e.g., Gaussian kernel). In this paper, we propose to use Quasi-Monte Carlo (QMC) approximations instead where the relevant integrands are evaluated on a low-discrepancy sequence of points as opposed to random point sets as in the Monte Carlo approach. We derive a new discrepancy measure called box discrepancy based on theoretical characterizations of the integration error with respect to a given sequence. We then propose to learn QMC sequences adapted to our setting based on explicit box discrepancy minimization. Our theoretical analyses are complemented with empirical results that demonstrate the effectiveness of classical and adaptive QMC techniques for this problem.
RIS
TY - CPAPER TI - Quasi-Monte Carlo Feature Maps for Shift-Invariant Kernels AU - Jiyan Yang AU - Vikas Sindhwani AU - Haim Avron AU - Michael Mahoney BT - Proceedings of the 31st International Conference on Machine Learning DA - 2014/01/27 ED - Eric P. Xing ED - Tony Jebara ID - pmlr-v32-yangb14 PB - PMLR DP - Proceedings of Machine Learning Research VL - 32 IS - 1 SP - 485 EP - 493 L1 - http://proceedings.mlr.press/v32/yangb14.pdf UR - https://proceedings.mlr.press/v32/yangb14.html AB - We consider the problem of improving the efficiency of randomized Fourier feature maps to accelerate training and testing speed of kernel methods on large datasets. These approximate feature maps arise as Monte Carlo approximations to integral representations of shift-invariant kernel functions (e.g., Gaussian kernel). In this paper, we propose to use Quasi-Monte Carlo (QMC) approximations instead where the relevant integrands are evaluated on a low-discrepancy sequence of points as opposed to random point sets as in the Monte Carlo approach. We derive a new discrepancy measure called box discrepancy based on theoretical characterizations of the integration error with respect to a given sequence. We then propose to learn QMC sequences adapted to our setting based on explicit box discrepancy minimization. Our theoretical analyses are complemented with empirical results that demonstrate the effectiveness of classical and adaptive QMC techniques for this problem. ER -
APA
Yang, J., Sindhwani, V., Avron, H. & Mahoney, M.. (2014). Quasi-Monte Carlo Feature Maps for Shift-Invariant Kernels. Proceedings of the 31st International Conference on Machine Learning, in Proceedings of Machine Learning Research 32(1):485-493 Available from https://proceedings.mlr.press/v32/yangb14.html.

Related Material