Gaussian Quadrature for Kernel Features.

Area of Science:

• Machine Learning
• Kernel Methods
• Signal Processing

Background:

• Kernel methods show performance competitive with deep neural networks.
• Random Fourier features map is a common technique to scale kernel machines.
• Randomized feature maps require O(ε^-2) samples for approximation error ε.

Purpose of the Study:

• Investigate deterministic feature map construction schemes.
• Approximate kernels in the frequency domain using Gaussian quadrature.
• Develop a more efficient alternative to random Fourier features.

Main Methods:

• Constructing deterministic feature maps.
• Approximating kernels in the frequency domain.
• Utilizing Gaussian quadrature for approximation.

Main Results:

• Deterministic feature maps achieve error ε with O(e^γ + ε^-1/γ) samples.
• The method performs well with sparse ANOVA kernels.
• Deterministic features are faster to generate than random features.
• Accuracy comparable to state-of-the-art random Fourier features methods.

Conclusions:

• Deterministic feature maps provide an efficient and accurate alternative to random Fourier features.
• This method is particularly effective for sparse ANOVA kernels.
• The approach demonstrates strong performance on benchmark datasets like MNIST and TIMIT.