Fast Evaluation of Additive Kernels: Feature Arrangement, Fourier Methods, and Kernel Derivatives

Theresa Wagner, Franziska Nestler, Martin Stoll

Abstract

Kernel-based learning methods, such as Support Vector Machines and Gaussian Processes, are powerful tools for non-linear modeling but are often hindered by the $O(N^2)$ computational complexity of kernel matrix operations. This paper introduces a high-performance framework for evaluating additive kernels—a structural approach that decomposes complex, high-dimensional data into sums of low-dimensional feature groups. By leveraging the Non-equispaced Fast Fourier Transform (NFFT), the authors reduce the complexity of kernel matrix-vector products to $O(N \log N)$. Additionally, the framework provides a novel method to accelerate kernel derivatives, facilitating faster hyperparameter tuning and improved model optimization.

Introduction

The primary bottleneck in kernel-based learning is the dense $N \times N$ kernel matrix. As datasets scale into the millions, standard matrix-vector products become computationally prohibitive. While various "fast summation" techniques have been proposed to approximate these products, most suffer from the curse of dimensionality, where efficiency degrades rapidly as the number of features increases.

This research addresses the bottleneck by focusing on additive kernels. These kernels model global similarity as a sum of similarities across smaller subsets of features. This structure is not only more interpretable but also allows for significant computational exploitation when combined with advanced Fourier analysis.

Methodology

Additive Gaussian Kernels and NFFT

Instead of employing a single massive kernel for all $d$ dimensions, the proposed framework utilizes a sum of kernels, where each sub-kernel operates on a small "window" of features (typically 1 to 3 dimensions). Because each sub-kernel functions in a low-dimensional space, the authors can apply the Non-equispaced Fast Fourier Transform (NFFT) to approximate the matrix-vector product. This approach shifts the computational burden into the Fourier domain, where the cost scales almost linearly with the number of data points, effectively bypassing the curse of dimensionality for high-dimensional problems.

Accelerated Kernel Derivatives

Optimizing hyperparameters, such as the length-scale $\ell$ in Gaussian Processes, requires calculating the derivative of the kernel matrix. Traditionally, this is a costly operation. The authors derive a "derivative kernel" that allows these gradients to be computed within the same fast NFFT framework. This advancement makes gradient-based hyperparameter optimization feasible on large-scale datasets that would otherwise require prohibitive amounts of compute time.

Feature Grouping Strategies

The arrangement of features into additive groups is critical for performance. The paper evaluates several strategies for feature grouping:

  • Mutual Information Score (MIS): Ranking and grouping features based on individual importance.
  • Lasso/Elastic Net: Utilizing regularization techniques to identify sparse feature interactions.
  • Global Sensitivity Indices (GSI): A Fourier-based ANOVA approach used to identify which feature combinations contribute most significantly to the model's variance.

Experimental Evaluation

The framework was evaluated on four standard regression benchmarks: Protein (tertiary structure, $N=45,730$), KEGGundir (metabolic pathways, $N=63,608$), Bike Sharing (rental counts, $N=17,379$), and Housing (California housing data, $N=20,640$).

Performance and Scalability

For datasets where $N > 10,000$, the NFFT-based approach demonstrated speeds orders of magnitude faster than standard matrix multiplication. On the Protein and KEGGundir datasets, standard methods eventually failed due to memory exhaustion, while the NFFT approach maintained stable performance.

Predictive Accuracy

Interestingly, the additive models often outperformed "full" kernels in terms of accuracy. On the Protein dataset, the additive model achieved a Root Mean Square Error (RMSE) of approximately 0.55, compared to ~0.65 for the state-of-the-art sklearn Kernel Ridge Regression (KRR) using a full kernel. These results suggest that real-world tabular data is often dominated by low-order feature interactions, making the additive assumption a beneficial structural prior rather than a limitation.

Conclusion and Future Work

This work demonstrates that combining additive kernel structures with NFFT acceleration provides a scalable and accurate alternative to traditional kernel methods. By providing rigorous analytical error estimates for Gaussian kernels and their derivatives, the authors offer a robust theoretical foundation for this fast evaluation framework.

Future research directions include extending the rigorous error analysis to other kernel families, such as Matérn kernels (3/2 or 5/2), and addressing potential periodization errors that occur at very small length-scales. Additionally, while the current NFFT implementation is optimized for feature groups of size $d_s \leq 3$, further work could explore efficient ways to handle higher-dimensional feature interactions within the additive framework.

Summary updated

BibTeX
@inproceedings{wagner2025fast,
  author = {Theresa Wagner and Franziska Nestler and Martin Stoll},
  title = {{Fast Evaluation of Additive Kernels: Feature Arrangement, Fourier Methods, and Kernel Derivatives}},
  booktitle = {ETNA},
  year = {2025},
  doi = {10.1553/etna\_vol63s496},
}

Loading related content...

Figure