Introduction
Kernel methods have long been a cornerstone of machine learning, providing a robust framework for handling non-linear data by projecting it into high-dimensional feature spaces. Despite their theoretical elegance, these methods face a significant "scalability wall." Traditional approximation techniques, such as the Nyström method, scale cubically ($O(N^3)$) with the number of data points, rendering them impractical for the massive datasets characteristic of modern deep learning.
NeuralEF introduces a novel framework that bypasses these limitations by "deconstructing" kernels into their principal eigenfunctions using neural networks. By reformulating kernel eigendecomposition as a series of asymmetric optimization problems—generalizing the "EigenGame" concept to function space—NeuralEF enables the efficient approximation of complex, modern kernels like Neural Tangent Kernels (NTKs) on a scale previously thought unattainable.
The Scalability Challenge
Beyond the cubic scaling of traditional methods, modern kernels that leverage the inductive biases of deep learning—such as Neural Network Gaussian Process (NN-GP) kernels and NTKs—are notoriously expensive to evaluate. While previous attempts have been made to use neural networks for this task (e.g., Spectral Inference Networks or SpIN), they were often hindered by expensive orthogonalization steps and complex implementation requirements. NeuralEF aims to provide a scalable, easy-to-implement, and efficient alternative that treats kernel approximation as a parametric learning problem.
The NeuralEF Framework
The core innovation of NeuralEF is the treatment of kernel eigendecomposition as a functional optimization problem. The framework is built upon several key technical pillars:
- Function-Space EigenGame: The authors demonstrate that the top-$k$ eigenpairs of a kernel can be recovered by solving a sequence of asymmetric maximization problems. This generalizes the "EigenGame" (originally designed for finite matrices) to the infinite-dimensional space of functions.
- Neural Eigenfunctions: Rather than approximating a single large matrix, NeuralEF employs $k$ separate neural networks. Each network is specifically trained to approximate one individual eigenfunction of the kernel.
- Asymmetric Loss Function: To prevent all $k$ networks from converging to the dominant (first) eigenfunction, the framework utilizes an asymmetric objective. The loss function for the $j$-th network includes a penalty term that enforces orthogonality relative to the previous $j-1$ networks. This avoids the need for explicit, computationally expensive orthogonalization steps like Cholesky decomposition.
- L2 Batch Normalization (L2BN): To satisfy the mathematical requirement that eigenfunctions maintain a unit norm, the authors introduced a specialized L2BN layer. This ensures the output of each neural eigenfunction has a unit L2 norm across the mini-batch during training.
- Matrix-Valued Extension: The method is versatile enough to handle matrix-valued kernels, which are essential for multi-output neural networks, by modifying the output layers and loss calculations accordingly.
Experimental Evaluation
The authors evaluated NeuralEF across a variety of benchmarks, ranging from synthetic visualizations to large-scale image classification and uncertainty estimation.
Efficiency and Accuracy
On classic kernels like Polynomial and RBF, NeuralEF matched the accuracy of the Nyström method while demonstrating superior speed. Because NeuralEF is trained via Stochastic Gradient Descent (SGD) on mini-batches, its training time remains nearly constant regardless of the total dataset size, whereas Nyström's complexity grows cubically.
Modern Kernels on MNIST
Using a CNN-GP kernel approximated via NeuralEF, the researchers achieved 84.98% accuracy on MNIST using a simple logistic regression classifier. This significantly outperformed classic kernels approximated by Nyström, which plateaued around 78%.
Scalable Laplace Approximation
NeuralEF enables advanced Bayesian techniques on large architectures. For instance, it allowed for the use of Linearized Laplace Approximation on a ResNet-110 model. NeuralEF achieved an Expected Calibration Error (ECE) of 0.010, a marked improvement over the MAP baseline (0.046) and other approximations like KFAC (0.749).
Feature Extraction and Clustering
On CIFAR-10, the learned neural eigenfunctions served as effective "plug-and-play" feature extractors. K-means clustering using NeuralEF features reached 97.5% accuracy in distinguishing airplanes from automobiles, far exceeding the 67.8% accuracy achieved by clustering raw pixels.
Insights and Future Directions
NeuralEF represents a shift in how we approach kernel methods, moving from matrix-based approximations to parametric function learning. By breaking the cubic barrier, it allows researchers to apply the inductive biases of modern deep kernels to large-scale problems. Furthermore, it can approximate kernels that lack closed-form analytical solutions, such as CNN-GP kernels with max-pooling.
However, some limitations remain. Currently, each eigenfunction requires a dedicated neural network; if a kernel has a "long tail" of many significant eigenvalues, training dozens of networks becomes computationally taxing. Future work may explore weight sharing across eigenfunctions to mitigate this. Additionally, the stochastic nature of SGD makes it challenging to capture eigenfunctions associated with very small eigenvalues (e.g., those less than 1% of the maximum eigenvalue). Despite these challenges, NeuralEF provides a powerful new toolkit for scaling kernel methods to the era of big data.
Summary updated