Quasi-Monte Carlo Feature Maps for Shift-Invariant Kernels

TitleQuasi-Monte Carlo Feature Maps for Shift-Invariant Kernels
Publication TypeConference Paper
Year of Publication2014
AuthorsYang, J., Sindhwani V., Avron H., & Mahoney M. W.
Other Numbers3679

We consider the problem of improving the efficiency of randomized Fourier feature mapsto 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 insteadwhere the relevant integrands are evaluated on alow-discrepancy sequence of points as opposedto random point sets as in the Monte Carlo approach. We derive a new discrepancy measurecalledbox discrepancybased on theoretical characterizations of the integration error with respectto a given sequence. We then propose to learnQMC sequences adapted to our setting based onexplicit box discrepancy minimization. Our theoretical analyses are complemented with empirical results that demonstrate the effectiveness ofclassical and adaptive QMC techniques for thisproblem.


This work was partially supported by the XDATA program of the Defense Advanced Re-search Projects Agency (DARPA), administered through Air Force Research Laboratory contract FA8750-12-C-0323. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors or originators and do not necessarily reflect the views of DARPA or of the U.S. Government.

Bibliographic Notes

Proceedings of the 31st International Conference in Machine Learning (ICML), Beijing, China

Abbreviated Authors

J. Yang, V. Sindhwani, H. Avron, and M. W. Mahoney

ICSI Research Group

Big Data

ICSI Publication Type

Article in conference proceedings