NeuralEF: Deconstructing Kernels by Deep Neural Networks

Zhijie Deng, Jiaxin Shi, Jun Zhu

Kernel methods are foundational in machine learning, allowing us to process non-linear data by projecting it into high-dimensional spaces. However, they hit a massive scalability wall: standard techniques like the Nyström method demand $O(N^2)$ memory and $O(N^3)$ computation. This makes them impractical for large datasets.

Furthermore, modern kernels like Neural Network Gaussian Processes (NN-GP) and Neural Tangent Kernels (NTKs) are computationally prohibitive to evaluate analytically. Previous attempts to approximate these kernels using neural networks (e.g., Spectral Inference Networks or SpIN) relied on expensive, difficult-to-train orthogonalization steps like Cholesky decomposition.

Enter NeuralEF, a novel framework that uses an ensemble of deep neural networks to learn the principal eigenfunctions of a kernel. By reformulating eigendecomposition as a series of asymmetric optimization problems, NeuralEF scales to massive datasets and complex modern kernels, outperforming previous neural-based approximations in both efficiency and accuracy.

Core Methodology

The central innovation of NeuralEF is treating kernel eigendecomposition as a hierarchy of asymmetric maximization problems.

  1. Neural Eigenfunctions: Instead of a single monolithic model, NeuralEF employs $k$ separate neural networks to approximate the top-$k$ eigenfunctions of a kernel.
  2. Function-Space EigenGame: Inspired by "EigenGame" (which frames PCA as a competitive game), the authors extend this concept to function space. The first network learns the primary eigenfunction. The second network learns the next one but is penalized if it isn't orthogonal to the first, and so on. This asymmetric setup bypasses the global, expensive orthogonalization steps required by prior methods.
  3. L2 Batch Normalization (L2BN): To guarantee the learned eigenfunctions are properly normalized (a strict requirement for Mercer’s theorem), the authors introduce a specialized L2BN layer. This ensures the outputs of each network maintain a unit norm over the data distribution during mini-batch training.
  4. Monte Carlo Estimation: For kernels lacking easy analytical forms (like NTKs), NeuralEF provides strategies to estimate the kernel matrix using finite-width neural networks, broadening its applicability to diverse architectures.
NeuralEF deconstructs a kernel into an ensemble of DNNs under the principle of eigendecomposition.

Experimental Setup and Key Insights

The authors evaluated NeuralEF across several benchmarks, ranging from synthetic 2D data (for visualizing eigenfunction recovery) to large-scale image datasets like MNIST, CIFAR-10, and SVHN.

A major takeaway is NeuralEF's ability to break the $O(N^3)$ barrier. While traditional Nyström methods slow down exponentially as data is added, NeuralEF’s training time remains nearly constant regardless of sample size once the network architecture is fixed.

Furthermore, the learned neural eigenfunctions define a new "axis system" for the data. These can act as plug-and-play, unsupervised feature extractors for downstream tasks like clustering or classification, effectively capturing the intrinsic similarities defined by the kernel. Finally, by removing the need for Cholesky decomposition and Jacobian tracking, NeuralEF is significantly easier to integrate into standard deep learning pipelines.

Key Results

  • Scalability and Accuracy: NeuralEF matches the accuracy of the Nyström method on classic kernels but scales gracefully. As shown in the training time comparisons, while Nyström's computational cost explodes with more samples, NeuralEF remains highly efficient.
NeuralEF delivers solutions as accurate as Nyström but with much more sustainable resource consumption as data size grows.
  • Superior Clustering: On CIFAR-10, K-means clustering using NTK eigenfunctions learned by NeuralEF achieved an impressive 97.5% accuracy, vastly outperforming raw pixels (67.8%) and standard random feature approaches (81.3%).
  • Large-Scale Laplace Approximation: The authors successfully applied NeuralEF to a linearized Laplace approximation involving a massive $500,000 \times 500,000$ kernel matrix. NeuralEF provided better-calibrated uncertainty estimates (lower Expected Calibration Error) than standard baselines like KFAC or Diagonal LLA.

Limitations and Future Directions

Despite its advantages, NeuralEF currently requires $k$ separate neural networks to find $k$ eigenfunctions. For kernels with a "long tail" of important eigenfunctions, maintaining many separate networks could become a memory and computation bottleneck. Additionally, the method struggles to accurately capture eigenfunctions associated with very small eigenvalues (e.g., less than 1% of the largest eigenvalue), likely due to numerical errors inherent in stochastic optimization.

Future work may explore weight-sharing among the $k$ networks to improve parameter efficiency and further investigate NeuralEF's potential as a general-purpose unsupervised representation learner.

Summary updated

Abstract

Learning the principal eigenfunctions of an integral operator defined by a kernel and a data distribution is at the core of many machine learning problems. Traditional nonparametric solutions based...
BibTeX
@inproceedings{deng2022neuralef,
  author = {Zhijie Deng and Jiaxin Shi and Jun Zhu},
  title = {{NeuralEF: Deconstructing Kernels by Deep Neural Networks}},
  booktitle = {International Conference on Machine Learning},
  year = {2022},
  url = {https://openreview.net/forum?id=V4cXe1jUht},
}
Figure