The Regularizing Effect of Kernel Matrix Approximation

This direction is merged into another direction: kernel method scalability (computational complexity of kernel methods). Its last version stays readable and citable here.

Version 1 of 120 papers27 conceptsfrozen 2026-10-04

Kernel methods are mathematically elegant but computationally brutal. To compute a standard kernel machine, one typically faces an $O(N^2)$ memory bottleneck and an $O(N^3)$ time complexity, where $N$ is the number of data points. To bypass this, researchers use approximation techniques like the Nyström method or Random Features (RF).

The traditional intuition is straightforward: the more accurately we approximate the kernel matrix, the better our model should perform. However, a growing body of evidence suggests this is not the case. In many scenarios, a "worse" approximation—one that is coarser or noisier—actually yields better generalization on unseen data. This phenomenon suggests that approximation is not just a computational shortcut, but a form of computational regularization.

The Fidelity Paradox

In classical numerical analysis, the goal of an approximation is to minimize a metric like the Frobenius norm error between the true kernel matrix and its low-rank surrogate. Yet, as Fanghui Liu, Johan Suykens, and others point out in Random Features for Kernel Approximation: A Survey in Algorithms, Theory, and Beyond, there is a persistent disconnect between approximation fidelity and task performance.

Improving the precision of a kernel function approximation does not consistently result in superior predictive performance. In fact, Mohamad Amin Mohamadi and Danica J. Sutherland found that simplified "pseudo-NTK" approximations can actually achieve higher test accuracy than the full empirical Neural Tangent Kernels they are meant to mimic. This suggests that the "noise" or "error" introduced by the approximation may be filtering out redundant degrees of freedom or preventing the model from over-fitting to the training data.

Nyström Subsampling as Regularization

The Nyström method approximates a large matrix by sampling a subset of its columns. While this was long viewed as a necessary evil for scaling, Alessandro Rudi and Lorenzo Rosasco proved in Less is More: Nyström Computational Regularization that this subsampling is a legitimate regularization strategy.

They demonstrated that by choosing a specific number of subsampled points, one can achieve the same minimax optimal learning accuracy as full kernel methods. The subsampling acts as a low-pass filter, focusing the model on the most significant "ridge leverage scores"—a concept further refined by Recursive Sampling for the Nyström Method to achieve linear-time approximations without sacrificing predictive power.

Why More Isn't Always Better

If approximation error were the only thing that mattered, then methods like Simplex Random Features (which use obtuse angles to minimize estimation error) or Quadrature-based features (which replace Monte Carlo sampling with structured quadrature) would always be the superior choice.

While these methods by Isaac Reid and Marina Munkhoeva do provide tighter matrix approximations, the downstream benefits are often non-linear. Oriol Vinyals and Trevor Darrell explored this in Why Size Matters: Feature Coding as Nystrom Sampling, showing that while increasing dictionary size (or the number of random features) improves performance initially, it eventually hits a point of saturation.

Beyond this point, the extra "fidelity" provides no additional information for the classification task. In some cases, as noted by Fanghui Liu in his work on hyper-RKHS, a high-fidelity fit to a training similarity matrix can even be detrimental, as it lacks a direct theoretical link to out-of-sample generalization.

The Future of "Good Enough" Approximations

This research direction shifts the focus from approximation accuracy to task-relevant fidelity. If the goal is generalization, we may not need to evaluate kernels exactly—even when we can. For instance, Ryan Sweke recently showed in Kernel-based dequantization of variational QML that certain quantum-inspired kernels can be evaluated exactly using tensor networks, bypassing randomized approximations entirely.

However, the open question remains: does this exactness actually help? If the "noise" in Random Fourier Features or Nyström sampling serves as a regularizer, then moving toward exact evaluation might require us to re-introduce explicit regularization elsewhere. The core insight of this field is that in the regime of large-scale machine learning, the "errors" we make for the sake of speed are often the very things that help our models learn better.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_the_regularizing_effect_of_kernel_matrix_3c86c8f0,
  title = {The Regularizing Effect of Kernel Matrix Approximation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/the-regularizing-effect-of-kernel-matrix-approximation/rdr_3c86c8f048a04cd19d14c48af19f576b},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_the_regularizing_effect_of_kernel_matrix_3c86c8f0_v1,
  title = {The Regularizing Effect of Kernel Matrix Approximation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/the-regularizing-effect-of-kernel-matrix-approximation/rdr_3c86c8f048a04cd19d14c48af19f576b/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}