Gaussian Quadrature for Kernel Features
  Kernel methods have recently attracted resurgent interest, showing
performance competitive with deep neural networks in tasks such as speech
recognition. The random Fourier features map is a technique commonly used to
scale up kernel machines, but employing the randomized feature map means that
$O(\epsilon^{-2})$ samples are required to achieve an approximation error of at
most $\epsilon$. We investigate some alternative schemes for constructing
feature maps that are deterministic, rather than random, by approximating the
kernel in the frequency domain using Gaussian quadrature. We show that
deterministic feature maps can be constructed, for any $\gamma > 0$, to achieve
error $\epsilon$ with $O(e^{e^\gamma} + \epsilon^{-1/\gamma})$ samples as
$\epsilon$ goes to 0. Our method works particularly well with sparse ANOVA
kernels, which are inspired by the convolutional layer of CNNs. We validate our
methods on datasets in different domains, such as MNIST and TIMIT, showing that
deterministic features are faster to generate and achieve accuracy comparable
to the state-of-the-art kernel methods based on random Fourier features.
