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:
- Sequential and Active Learning: Paul Edmund Chang and Mohammad Emtiyaz Khan applied these concepts to Gaussian Processes in Memory-Based Dual Gaussian Processes for Sequential Learning. They use "Bayesian leverage scores" to decide which past data points to keep in a fixed-size memory, preventing the "forgetting" problem in continual learning.
- Numerical Integration: In Efficient Numerical Integration in Reproducing Kernel Hilbert Spaces via Leverage Scores Sampling, Antoine Chatalic and Nicolas Schreuder show that leverage scores can identify the best nodes for quadrature, outperforming traditional greedy methods for integrating complex functions.
- Diverse Subset Selection: Raja Hafiz Affandi and Emily B. Fox extended these approximations to Determinantal Point Processes (DPPs) in Nystrom Approximation for Large-Scale Determinantal Processes, enabling the selection of diverse items from massive datasets in sub-second time.
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.