Quasi-Monte Carlo Feature Maps for Shift-Invariant Kernels
| Title | Quasi-Monte Carlo Feature Maps for Shift-Invariant Kernels |
| Publication Type | Conference Paper |
| Year of Publication | 2014 |
| Authors | Yang, J., Sindhwani V., Avron H., & Mahoney M. |
| Other Numbers | 3679 |
| Abstract | 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. |
| Acknowledgment | 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. |
| URL | https://www.icsi.berkeley.edu/pubs/initiatives/quasimonte14.pdf |
| 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 |