Data Dependent Kernel Approximations

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 128 papers42 conceptsfrozen 2026-10-04

Kernel methods are powerful because they allow linear algorithms to operate in high-dimensional feature spaces, capturing complex, non-linear patterns. However, they suffer from a fundamental scaling problem: the kernel matrix grows quadratically with the number of data points ($N^2$), making them prohibitively expensive for large datasets.

To solve this, researchers traditionally used Random Fourier Features (RFF), which approximate the kernel by projecting data onto random basis functions. While fast, RFF is "data-blind"—it samples frequencies from the kernel's spectral distribution without considering where the actual data points lie. A growing body of research suggests that data-dependent approximations, such as the Nyström method and learned sketches, offer a more efficient path by tailoring the approximation to the specific distribution of the dataset.

The Intuition of Landmarks

The core idea behind data-dependent methods like the Nyström approximation is to use a subset of the actual data points—often called landmarks—to define the feature space.

In Mean Nyström Embeddings for Adaptive Compressive Learning, Antoine Chatalic and Luigi Carratino argue that picking landmarks from the data ensures that the "sketch resolution" is concentrated in regions where data density is highest.

Think of it like drawing a map: RFF is like placing a grid over the entire world regardless of where people live. Nyström is like placing more detail on cities and less on the empty oceans. By anchoring the approximation to observed data, we capture the underlying manifold more effectively than purely randomized mappings. This allows for significant compression—squashing massive datasets into small "sketch" vectors—without sacrificing the accuracy of downstream tasks like clustering.

Why Data-Dependence Outperforms Randomness

The shift from data-independent to data-dependent methods is driven by the realization that most real-world data is structured and sparse, not uniformly distributed.

  1. Capturing the Manifold: Brian McWilliams and David Balduzzi demonstrate in Correlated random features for fast semi-supervised learning that Nyström-based features provide more accurate estimators for regression than RFF. This is because the landmarks inherently respect the geometry of the data.
  2. Efficiency in High Dimensions: In high-dimensional spaces, random projections often fail to capture the subtle differences between probability measures. Florian Kalinke and Zoltán Szabó show in Nyström Kernel Stein Discrepancy that data-dependent landmark selection provides more reliable statistical discrimination, even for the "unbounded" kernels required in Stein methods.
  3. Greedy Optimization: Rather than picking landmarks at random, we can optimize them. Fuxin Li and Guy Lebanon describe a process of greedily selecting parameters to eliminate error peaks in high-density regions, ensuring the approximation is most accurate where the data is most concentrated.

Learning the Sketch

If using data points as landmarks is good, "learning" the optimal projection matrix is even better. Piotr Indyk and colleagues in Learning-Based Low-Rank Approximations show that teaching an algorithm to recognize specific data structures can outperform traditional random methods by an order of magnitude.

These learned sketches achieve target accuracy with much smaller dimensions. Because the learned matrices can maintain the same sparsity patterns as random ones, they provide these efficiency gains without adding computational overhead during the sketching process.

Scaling to Massive Streams

Data-dependent approximations are particularly potent in online and large-scale settings. In Large Scale Online Kernel Classification, Steven C. H. Hoi and Jialei Wang use a small initial sample of a data stream to construct a representative basis. This allows kernel-based learning to scale linearly with data size.

Similarly, Nikolaas Steenbergen and Felix Bießmann introduced Doubly Stochastic Empirical Kernel Learning (DSEKL). By using the data itself to define the feature space (the empirical kernel map), they achieve performance comparable to traditional batch Support Vector Machines while maintaining the efficiency of neural networks.

Theoretical Robustness

A common concern with data-dependent methods is whether they maintain the theoretical guarantees of their data-blind counterparts. Recent work has solidified this foundation. Zenglin Xu and Rong Jin showed in Nystrom Approximation for Sparse Kernel Methods that by leveraging the restricted eigenvalue condition rather than simple low-rank assumptions, one can achieve massive computational speedups (up to 70,000x) without sacrificing the accuracy of sparse solutions.

By moving from "blind" random features to "aware" data-dependent landmarks, these methods ensure that every dimension of the approximated feature space is used to represent actual information, rather than empty space.

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_data_dependent_kernel_approximations_fcb7f8e6,
  title = {Data Dependent Kernel Approximations},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/data-dependent-kernel-approximations/rdr_fcb7f8e60c1545d79aa2e79fb58863f0},
  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_data_dependent_kernel_approximations_fcb7f8e6_v1,
  title = {Data Dependent Kernel Approximations},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/data-dependent-kernel-approximations/rdr_fcb7f8e60c1545d79aa2e79fb58863f0/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}