Leverage Score Sampling for Scalable Kernel Methods

This direction is merged into another direction: leverage score sampling. Its last version stays readable and citable here.

Version 1 of 125 papers31 conceptsfrozen 2026-10-04

Kernel methods are among the most powerful tools in machine learning for capturing non-linear relationships, but they suffer from a fundamental scaling problem. To compute a Kernel Ridge Regression or a Gaussian Process, one typically needs to manipulate an $N \times N$ kernel matrix, leading to $O(N^2)$ memory and $O(N^3)$ computational costs. For a dataset of a million points, this is a death sentence for performance.

The research direction explored here focuses on overcoming this "quadratic bottleneck" through the Nyström method and, more crucially, the development of Leverage Score Sampling to make these approximations both efficient and theoretically sound.

The Nyström Approximation: Learning from Landmarks

The core intuition of the Nyström method is that we don't need the entire $N \times N$ kernel matrix to understand the geometry of our data. Instead, we can pick a small subset of $m$ "landmark" points (where $m \ll N$) and use their relationships to the rest of the data to reconstruct a low-rank approximation of the full matrix.

However, the success of this approximation hinges entirely on which points you pick. If you sample landmarks uniformly at random, you might miss the "rare but important" points—those that define the boundaries of a cluster or represent a sparse region of the feature space. As noted in Incremental Nyström-based Multiple Kernel Clustering by Weixuan Liang and colleagues, uniform sampling tends to over-index on dense regions, effectively ignoring the structural nuances of unbalanced datasets.

Defining Importance with Ridge Leverage Scores

To solve the selection problem, researchers have turned to Ridge Leverage Scores (RLS). Intuitively, the leverage score of a data point measures how "unique" or "influential" that point is relative to the kernel's range. A point in a dense cluster has low leverage because its neighbors can easily represent it; a point in a sparse region or near a decision boundary has high leverage because it provides information that no other point can.

The challenge is that calculating exact leverage scores requires the very $O(N^3)$ operations we are trying to avoid. A major breakthrough in this field was the development of Recursive Sampling, introduced in Recursive Sampling for the Nyström Method. This algorithm estimates leverage scores in linear time ($O(N)$), allowing for high-quality landmark selection without the prohibitive cost. By prioritizing points with high leverage, the approximation becomes "coherence-independent," meaning it works even if the data is highly irregular or poorly conditioned.

Subsampling as Computational Regularization

Perhaps the most profound insight in this research area is that subsampling isn't just a way to save time—it is a principled way to control model complexity. In Less is More: Nyström Computational Regularization, Alessandro Rudi, Raffaello Camoriano, and Lorenzo Rosasco prove that Nyström subsampling acts as a form of computational regularization.

They demonstrate that by choosing the number of landmarks $m$ in proportion to the dataset's intrinsic difficulty, one can achieve the same optimal statistical accuracy as the full $O(N^3)$ kernel method. This reframes the Nyström method: it is not a "lossy" approximation we settle for, but a strategic choice that balances statistical precision with computational budget.

Applications Across the Machine Learning Pipeline

The ability to efficiently select representative landmarks has transformed several sub-fields:

By moving from uniform random sampling to geometry-aware leverage score sampling, this research direction has turned kernel methods from elegant theoretical constructs into practical tools capable of handling the scale of modern data.

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_leverage_score_sampling_for_scalable_ker_61b16a76,
  title = {Leverage Score Sampling for Scalable Kernel Methods},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/leverage-score-sampling-for-scalable-kernel-methods/rdr_61b16a7615944755aa0e834b85ebb8c1},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_leverage_score_sampling_for_scalable_ker_61b16a76_v1,
  title = {Leverage Score Sampling for Scalable Kernel Methods},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/leverage-score-sampling-for-scalable-kernel-methods/rdr_61b16a7615944755aa0e834b85ebb8c1/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}