Kernel-based statistical methods provide a mathematically elegant framework for analyzing data without making restrictive parametric assumptions. By implicitly mapping data into infinite-dimensional Reproducing Kernel Hilbert Spaces (RKHS), metrics like the Maximum Mean Discrepancy (MMD), the Hilbert-Schmidt Independence Criterion (HSIC), and the Kernel Stein Discrepancy (KSD) can detect arbitrary, highly non-linear relationships. They allow us to determine if two datasets come from different distributions, if two variables are independent, or if a dataset matches a target probability model.
However, this expressive power comes with a steep computational price. Standard formulations of these tests rely on U-statistics or V-statistics, which require evaluating the kernel function across all pairs of data points. For a dataset of $n$ samples, this creates an $O(n^2)$ computational and memory bottleneck. When dealing with modern, large-scale datasets or streaming applications, this quadratic scaling quickly becomes an insurmountable wall.
To unlock the power of kernel methods for web-scale data, researchers have developed a suite of approximation strategies designed to bypass the pairwise comparison bottleneck, reducing the computational complexity from quadratic to linear ($O(n)$).
The Root of the Quadratic Bottleneck
To understand why kernel tests scale quadratically, consider the problem of testing for independence between two variables, $X$ and $Y$, using HSIC. To determine if $X$ and $Y$ are independent without assuming a linear relationship, we cannot simply compute a standard correlation coefficient. Instead, we must evaluate whether the joint distribution $P(X,Y)$ factorizes into the product of the marginals $P(X)P(Y)$.
In the kernel framework, this is achieved by computing the cross-covariance between the feature mappings of the variables in an RKHS. When estimating this from $n$ samples, the empirical test statistic requires computing an $n \times n$ Gram matrix for $X$ and another $n \times n$ Gram matrix for $Y$, followed by a matrix multiplication. As noted by Zhijian Zhou et al., hypothesis tests relying on these full U-statistics inherently scale quadratically with the sample size. In some complex scenarios, such as conditional independence testing, the scaling can even degrade to cubic ($O(n^3)$), as highlighted by Fateme Jamshidi.
This $O(n^2)$ scaling appears across a wide array of applications, creating severe performance bottlenecks in:
- Causal Inference: Where kernel-based conditional independence tests are used to discover causal graphs from large relational databases (Sanghack Lee et al.).
- Sequential Testing: Where data arrives continuously, and calculating a quadratic discrepancy at each step becomes prohibitively expensive over long testing periods (Diego Martinez-Taboada et al.; Jacopo Teneggi et al.).
- Generative Model Regularization: Where dependence measures are used as regularizers within training loops, penalizing the model at every batch (Naoya Takeishi et al.).
- Counterfactual Inference: Where debiasing historical datasets requires computing large-scale independence criteria (Romain Lopez et al.).
To resolve this, we must find ways to evaluate these global distributional properties without explicitly comparing every point to every other point.
Decoupling Pairs via Low-Rank Feature Approximations
The most prominent way to break the quadratic bottleneck is to decouple the pairwise interaction inside the kernel function. If a kernel $k(x, y)$ can be factored or approximated as an inner product of explicit, finite-dimensional feature vectors—such that $k(x, y) \approx \langle \phi(x), \phi(y) \rangle$ for some feature map $\phi: \mathbb{R}^d \to \mathbb{R}^D$ where $D \ll n$—the double summation over $n^2$ elements collapses into a single linear operation:
$$\sum_{i=1}^n \sum_{j=1}^n k(x_i, x_j) \approx \sum_{i=1}^n \sum_{j=1}^n \langle \phi(x_i), \phi(y_j) \rangle = \left\langle \sum_{i=1}^n \phi(x_i), \sum_{j=1}^n \phi(y_j) \right\rangle$$
By computing the sum of the feature maps first (which takes $O(n)$ time), we can evaluate the entire statistic with a single inner product. Two primary methods exist for constructing these low-rank approximations: Random Fourier Features (RFF) and the Nyström method.
Random Fourier Features (RFF)
RFF relies on Bochner’s Theorem, which states that any continuous, shift-invariant kernel is the Fourier transform of a positive regular measure (a probability distribution of frequencies). By drawing $D$ random frequencies from this distribution, we can construct an explicit randomized feature map $\phi(x)$ whose inner product approximates the kernel.
In Large-scale kernel methods for independence testing, Qinyi Zhang et al. demonstrate how RFF can be used to scale HSIC to millions of observations, transforming the test into a highly scalable linear-time operation. Similarly, Heishiro Kanagawa et al. leverage RFF to scale nonparametric goodness-of-fit tests for complex conditional density models.
The Nyström Method
Instead of sampling random mathematical frequencies, the Nyström method samples a small set of $m$ actual data points from the dataset, known as "landmarks." It then approximates the full $n \times n$ Gram matrix by evaluating how all $n$ points relate to these $m$ landmarks. This yields a low-rank factorization of the kernel matrix, reducing the computational cost to $O(n m^2)$.
Florian Kalinke et al. utilize this approach to create the Nyström M-HSIC, allowing researchers to test for non-linear independence across multiple groups of data simultaneously without hitting a computational wall. Billy Chang et al. also employ Nyström approximations to scale dependence-based Canonical Correlation Analysis (CCA), bridging the gap between interpretable linear projections and complex non-linear dependence tracking.
Subsampling and Incomplete U-Statistics
An alternative intuition for scaling kernel tests is to ask: Do we really need to look at all $n(n-1)/2$ pairs to make a statistically sound decision?
If a dataset is large enough, a randomly selected subset of pairs may contain more than enough signal to reject a null hypothesis. This insight leads to Block-based estimators and Incomplete U-statistics.
Full U-Statistic O(n²) Block-Based O(n) Incomplete U-Statistic O(n)
[X X X X X X X X] [X X] . . . . . . [X . . . X . . .]
[X X X X X X X X] [X X] . . . . . . [. . X . . . X .]
[X X X X X X X X] . . [X X] . . . . [. X . . . . . X]
[X X X X X X X X] ==> . . [X X] . . . . ==> [. . . X . X . .]
[X X X X X X X X] . . . . [X X] . . [X . . . . . . X]
[X X X X X X X X] . . . . [X X] . . [. . X . X . . .]
[X X X X X X X X] . . . . . . [X X] [. X . . . . X .]
[X X X X X X X X] . . . . . . [X X] [. . . X . . . X]
In a block-based approach, the dataset is partitioned into small, disjoint blocks of size $B$. The exact quadratic kernel statistic is calculated within each individual block, and the final test statistic is the average across all blocks. Because the block size $B$ is fixed, the total computation scales as $O(nB)$, which is strictly linear with respect to $n$.
Incomplete U-statistics generalize this idea by picking a linear number of random pairs from the full joint matrix rather than restricting them to blocks. As shown by Antonin Schrab et al. in the development of the Kernel Stein Discrepancy Aggregated test (KSDAGG), using incomplete U-statistics allows goodness-of-fit tests to scale linearly while maintaining minimax optimal detection rates, eliminating the need for wasteful data splitting or manual kernel tuning.
Bypassing Pairwise Comparisons via Analytic Embeddings
Perhaps the most radical departure from the quadratic bottleneck is to avoid comparing data points to each other entirely. Instead, we can represent an entire probability distribution as a single continuous function in the RKHS—a concept known as a kernel mean embedding.
To test if two distributions differ, or if two variables are dependent, we can evaluate their analytic kernel embeddings at a small, fixed number of strategically chosen "test locations" in the data space.
Pairwise Testing O(n²) Analytic Embedding O(n)
Point <---> Point Data Distribution
Point <---> Point │
Point <---> Point ▼
Point <---> Point Continuous Embedding
Point <---> Point │
Point <---> Point ┌────────────┼────────────┐
▼ ▼ ▼
Test Loc 1 Test Loc 2 Test Loc 3
This is the core mechanism behind the Normalized Finite Set Independence Criterion (NFSIC), introduced by Wittawat Jitkrittum et al.. Instead of computing an $n \times n$ matrix, the method maps the data to a finite set of optimized test locations. The complexity drops to $O(n)$, where the linear cost is determined solely by the number of locations. By optimizing these locations to maximize the test's statistical power, the authors create a linear-time test that matches the performance of state-of-the-art quadratic tests.
Alternative Non-Parametric Frameworks
While approximating the kernel matrix is highly effective, some researchers choose to bypass kernel formulations altogether, seeking alternative non-parametric representations that inherently scale better.
- Wavelet Transforms: The authors of the Wavelet Independence Test (WIT) introduce Multi-level Wavelet Mapping Correlation (MWMC). By projecting data into a wavelet domain rather than an RKHS, they capture multi-scale, non-linear dependencies in true linear time, avoiding the parameter-tuning complexities often associated with kernel methods.
- Nearest-Neighbor Estimators: Fernando Perez-Cruz demonstrates that information-theoretic measures like KL divergence and entropy can be accurately estimated using $k$-nearest-neighbor ($k$-nn) graphs. These non-convergent density estimators provide competitive detection power for independence and two-sample testing with a significantly lower computational footprint than exact kernel methods, though they can still exhibit quadratic-logarithmic complexity ($O(n \log n)$) depending on the tree structures used for neighbor lookups.
Through these diverse lenses—whether by projecting kernels into randomized feature spaces, subsampling pairs, or evaluating continuous embeddings at discrete test locations—the machine learning community has successfully mitigated the quadratic scaling bottleneck, transforming kernel methods into practical, high-throughput tools for large-scale statistical inference.
Key Foundational Work
Canonical Correlation Analysis based on Hilbert-Schmidt Independence Criterion and Centered Kernel Target Alignment (2013) — contributed 1 concept elements to this direction.
Estimation of Information Theoretic Measures for Continuous Random Variables (2008) — contributed 1 concept elements to this direction.