Quasi-Monte Carlo Feature Maps for Shift-Invariant Kernels
  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.
