Timezone: »

 
Spotlight
Gaussian Quadrature for Kernel Features
Tri Dao · Christopher M De Sa · Christopher Ré

Tue Dec 05 05:50 PM -- 05:55 PM (PST) @ Hall C
in Algorithms »
Kernel methods have recently attracted resurgent interest, matching the performance of 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$. In this paper, 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^{\gamma} + \epsilon^{-1/\gamma})$ samples as $\epsilon$ goes to 0. We validate our methods on datasets in different domains, such as MNIST and TIMIT, showing that deterministic features are faster to generate and achieve comparable accuracy to the state-of-the-art kernel methods based on random Fourier features.

Author Information

Tri Dao (Stanford University)
Christopher M De Sa (Stanford)
Christopher Ré (Stanford)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors