On Kernel Derivative Approximation with Random Fourier Features

Zoltán Szabó, Bharath K. Sriperumbudur

TL;DR

This paper tackles the theoretical understanding of Random Fourier Features (RFFs), a popular technique for scaling kernel methods. The authors extend existing RFF approximation guarantees to kernel derivatives, showing that RFFs can approximate derivatives as efficiently as function values, with improvements in theoretical bounds related to the domain size.

What Problem Does This Paper Address?

Kernel methods, while powerful for modeling complex relationships, are often computationally expensive. Random Fourier Features (RFFs) offer a way to approximate kernel functions, making these methods more scalable. While RFFs have seen practical success, their theoretical optimality and limitations, especially for tasks involving derivatives of kernel functions, remain less understood. Many machine learning problems, such as gradient-based learning or density estimation, can benefit from incorporating derivative information. This paper aims to bridge this gap by providing theoretical guarantees for RFF-based approximations of kernel derivatives, specifically addressing how well RFFs can approximate these derivatives and under what conditions.

Methods

The core of the paper lies in analyzing the approximation error of kernel derivatives using RFFs. The authors leverage the fact that shift-invariant kernels can be represented as Fourier transforms. They then use Random Fourier Features to approximate this Fourier transform. The key technical contribution is the application of recent tools from unbounded empirical process theory to bound the approximation error of kernel derivatives. This allows them to derive finite-sample guarantees that improve exponentially with the size of the domain, matching the best known guarantees for approximating kernel values themselves. Specifically, they analyze the supremum of the difference between the true kernel derivative and its RFF approximation, framing it as an empirical process problem. They then bound the bracketing entropies of the relevant function classes, which is crucial for dealing with unbounded functions.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • RFFs are as good for derivatives as for values: The most significant insight is that RFFs can approximate kernel derivatives with the same theoretical efficiency (in terms of sample size and domain size dependence) as they approximate kernel values. This is a crucial theoretical result for applications that rely on kernel derivatives.
  • Unboundedness is manageable: A key challenge addressed is that the functions involved in kernel derivative approximation are not uniformly bounded, unlike those for kernel value approximation. The paper shows that recent techniques for unbounded empirical processes can overcome this limitation.
  • Exponential improvement with domain size: The theoretical bounds derived show an exponential improvement with respect to the domain size, which is a significant theoretical advancement and matches the state-of-the-art for kernel value approximation.
  • Bernstein condition is key: The paper highlights the importance of a Bernstein-type condition on the kernel's spectral density for guaranteeing efficient RFF approximation of derivatives. Kernels with faster decaying spectral densities (like Gaussian kernels, up to a certain order of derivative) satisfy this condition more readily.

Key Results

The paper proves a main theorem providing uniform finite-sample bounds on the approximation quality of kernel derivatives using RFFs. The key result is that the approximation error, measured in $L_\infty$ norm, can be bounded by $O_{a.s.} \sqrt{\frac{\log m}{m}}$, where $m$ is the number of RFFs and the bound holds for compact sets $S$ with diameter $|S|$. This matches the optimal rate for kernel value approximation. They also show that this result extends to $L_r$ norms and discuss the implications of the Bernstein condition for specific kernels like the Gaussian kernel, demonstrating that it holds for derivatives up to a certain order related to the kernel's spectral decay.

Limitations and Future Work

  • Bernstein condition: The paper notes that the Bernstein condition (15) is not satisfied for all orders of derivatives, particularly for higher orders of kernels with slower spectral decay. An open question is whether this condition can be relaxed while maintaining similar approximation rates.
  • Practical implications of higher-order derivatives: While the theory extends to higher-order derivatives, the paper hints that kernels with faster spectral decay are more amenable to efficient RFF approximation of these derivatives. Further investigation into the practical trade-offs for different kernel types and derivative orders would be valuable.
  • Empirical validation: The paper is primarily theoretical. Future work could involve empirical studies to validate these theoretical findings and explore their impact on real-world machine learning tasks that utilize kernel derivatives.

Summary updated

Abstract

Random Fourier features (RFF) represent one of the most popular and wide-spread techniques in machine learning to scale up kernel algorithms. Despite the numerous successful applications of RFFs, unfortunately, quite little is understood theoretically on their optimality and limitations of their performance. Only recently, precise statistical-computational trade-offs have been established for RFFs in the approximation of kernel values, kernel ridge regression, kernel PCA and SVM classification. Our goal is to spark the investigation of optimality of RFF-based approximations in tasks involving not only function values but derivatives, which naturally lead to optimization problems with kernel derivatives. Particularly, in this paper, we focus on the approximation quality of RFFs for kernel derivatives and prove that the existing finite-sample guarantees can be improved exponentially in terms of the domain where they hold, using recent tools from unbounded empirical process theory. Our result implies that the same approximation guarantee is attainable for kernel derivatives using RFF as achieved for kernel values.
BibTeX
@inproceedings{szabo2019kernel,
  author = {Zoltán Szabó and Bharath K. Sriperumbudur},
  title = {{On Kernel Derivative Approximation with Random Fourier Features}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2019},
  url = {https://openreview.net/forum?id=IhqaaQNeRYS},
}
Figure