Abstract
Kernel matrices, as well as weighted graphs represented by them, are ubiquitous objects in machine learning, statistics and other related fields. The main drawback of using kernel methods (learning and inference using kernel matrices) is efficiency -- given $n$ input points, most kernel-based algorithms need to materialize the full $n \times n$ kernel matrix before performing any subsequent computation, thus incurring $\Omega(n^2)$ runtime. Breaking this quadratic barrier for various problems has therefore, been a subject of extensive research efforts. We break the quadratic barrier and obtain subquadratic time algorithms for several fundamental linear-algebraic and graph processing primitives, including approximating the top eigenvalue and eigenvector, spectral sparsification, solving linear systems, local clustering, low-rank approximation, arboricity estimation and counting weighted triangles. We build on the recent Kernel Density Estimation framework, which (after preprocessing in time subquadratic in $n$) can return estimates of row/column sums of the kernel matrix. In particular, we develop efficient reductions from weighted vertex and weighted edge sampling on kernel graphs, simulating random walks on kernel graphs, and importance sampling on matrices to Kernel Density Estimation and show that we can generate samples from these distributions in sublinear (in the support of the distribution) time. Our reductions are the central ingredient in each of our applications and we believe they may be of independent interest. We empirically demonstrate the efficacy of our algorithms on low-rank approximation (LRA) and spectral sparsification, where we observe a 9x decrease in the number of kernel evaluations over baselines for LRA and a 41x reduction in the graph size for spectral sparsification.
The Scalability Challenge in Kernel Methods
Kernel methods are a cornerstone of machine learning, used for tasks ranging from dimensionality reduction to non-linear classification. However, they face a significant scalability wall: the "quadratic barrier." To work with $n$ data points, standard algorithms typically compute an $n \times n$ kernel matrix $K$, where $K_{i,j}$ represents the similarity between points $x_i$ and $x_j$. For a dataset of 1 million points, this matrix contains 1 trillion entries, making it computationally prohibitive to store or process. While sub-quadratic algorithms ($o(n^2)$ time) are highly desirable, many fundamental problems have remained stuck behind this barrier without restrictive assumptions on the data.
Methods: KDE as an Algorithmic Primitive
The core innovation of this work is treating Kernel Density Estimation (KDE) as a black-box algorithmic primitive. A KDE data structure can efficiently estimate the sum of kernel values between a query point and a dataset. The efficiency of this primitive varies by kernel type, as shown in Table 1.
Building on this, the authors developed several "algorithmic building blocks":
- Multi-level KDE: A recursive data structure partitioning the dataset for granular queries.
- Weighted Sampling Primitives: Sub-linear time sampling of vertices by "weighted degree" and edges by weight.
- Random Walk Simulation: Simulating random walks on implicit kernel graphs without materializing the full matrix.
- Importance Sampling: Efficiently sampling rows based on leverage scores.
Theoretical Breakthroughs
By combining these blocks, the authors achieved sub-quadratic runtimes for a wide array of tasks. Table 2 summarizes the query complexity and post-processing times for these primitives, demonstrating significant improvements over prior work.
Key Insights: Sampling and the $\tau$ Parameterization
- KDE as a Sampling Engine: KDE is not just for density estimation; it can build efficient "samplers." By estimating weight sums, tree-based searches can pick points proportional to their weight in logarithmic time.
- The $\tau$ Parameterization: The algorithms are parameterized by $\tau$, the smallest entry in the kernel matrix. In practice, $\tau$ is often a fixed constant (e.g., 0.01), allowing these algorithms to bypass theoretical lower bounds that assume $\tau$ can be arbitrarily small.
- Independence of $n$: For problems like approximating the top eigenvalue or the spectrum, runtimes are independent of the number of points $n$, depending only on accuracy $\epsilon$ and the kernel floor $\tau$.
Experimental Validation
The theoretical contributions are supported by empirical performance on several datasets:
- Low-Rank Approximation (LRA): On the MNIST dataset, the KDE-based method achieved a 2.9x decrease in runtime and a 9x decrease in kernel evaluations compared to state-of-the-art sketching baselines.
- Spectral Sparsification: For a synthetic "Nested" dataset, the algorithm reduced graph size by 41x compared to the full matrix.
- Clustering Efficiency: On a "Rings" dataset, computing eigenvectors for spectral clustering was 4.5x faster on the sparsified graph with no loss in accuracy.
Datasets
- MNIST: Handwritten digits (10k points, 784 dimensions).
- GloVe: Word embeddings (10k points, 200 dimensions).
- Nested Dataset: 5k points in a central cluster surrounded by a ring.
- Rings Dataset: 2.5k points forming two interlocking tori in 3D.
Conclusion and Future Work
The primary limitation is the dependence on the minimum kernel value $\tau$. If $\tau$ is polynomially small in $n$, the sub-quadratic advantage may diminish. Finding the optimal dependence on $\tau$ for kernels like Gaussian or Laplace remains an open challenge. However, this framework provides a powerful new toolkit for scaling kernel methods to massive datasets.
Summary updated