Subquadratic Algorithms for Kernel Matrices via Kernel Density Estimation

Ainesh Bakshi, Piotr Indyk, Praneeth Kacham, Sandeep Silwal, Samson Zhou

TL;DR

This paper breaks the "quadratic barrier" for kernel methods by providing subquadratic-time ($o(n^2)$) algorithms for fundamental tasks like spectral sparsification, low-rank approximation, and clustering. By leveraging recent advances in Kernel Density Estimation (KDE), the authors show how to perform complex linear algebra and graph processing without ever materializing the full $n \times n$ kernel matrix.

The Quadratic Barrier in Kernel Methods

In machine learning and statistics, kernel methods are powerful tools for capturing non-linear relationships. However, they face a massive scalability hurdle: the Quadratic Barrier.

Given $n$ input points, a kernel matrix $K$ contains $n^2$ entries, where each entry $K_{i,j}$ is the similarity between point $i$ and point $j$. Most standard algorithms require "materializing" this entire matrix before any computation begins. For a dataset of 1 million points, the matrix would require 4 terabytes of memory—a non-starter for most systems. While approximation techniques exist, many still require $O(n^2)$ time or have high error. The authors aim to find algorithms that run in subquadratic time while maintaining strong theoretical guarantees for a wide range of applications.

Methods: Bridging KDE and Graph Algorithms

The core innovation of this paper is a "two-pronged" approach that bridges the gap between Kernel Density Estimation (KDE) and traditional graph/matrix algorithms.

  1. KDE as a Black Box: The authors utilize recent data structures that can estimate the sum of kernel values (row/column sums of the matrix) in sublinear time.
KDE Data Structures
  1. Algorithmic Building Blocks: They develop efficient reductions to transform these KDE queries into fundamental sampling primitives:
  2. Weighted Vertex Sampling: Sampling a vertex with probability proportional to its "degree" (the sum of its similarities to all other points).
  3. Weighted Neighbor/Edge Sampling: Efficiently picking a random neighbor of a vertex based on edge weights without looking at all neighbors.
  4. Simulated Random Walks: Performing random walks on the "kernel graph" in sublinear time.
  5. Multi-level KDE: They use a recursive tree-based structure to partition the dataset, allowing them to descend the tree and sample points or edges efficiently.

By treating the KDE structure as a black box, the authors ensure that any future improvements in KDE efficiency will automatically speed up their entire suite of algorithms.

Datasets

The authors evaluated their algorithms on both real-world and synthetic datasets:

  • Real-world (for Low-Rank Approximation):
    • MNIST: 10,000 images of handwritten digits (784 dimensions).
  • GloVe: 10,000 word embeddings (200 dimensions).
  • Synthetic (for Clustering and Sparsification):
    • Nested Dataset: Points at the origin surrounded by a circle of points.
  • Rings Dataset: Two interlocking tori in 3D space. These are classic "non-linearly separable" challenges where spectral clustering is required because simple methods like k-means fail.

Key Insights and Ideas

  • The $\tau$ Parameterization: The authors observe that in practice, kernel values are rarely "polynomially small." They parameterize their runtimes by $\tau$, the smallest entry in the kernel matrix. This allows them to skirt known lower bounds that only apply when entries are infinitesimally small.
  • Sampling without Materializing: The "aha moment" is realizing you don't need to see an edge to sample it. By using the KDE tree structure, they can estimate the "weight" of entire branches of the dataset and only zoom in on the specific points needed for a sample.
  • Independence from $n$: For certain problems, like approximating the top eigenvalue or the entire eigenvalue spectrum (in Earth Mover Distance), they achieve runtimes that are entirely independent of the number of points $n$, depending only on the precision $\epsilon$ and the kernel bound $\tau$.

Key Results

The paper demonstrates significant speedups and efficiency gains across various tasks:

Summary of Subquadratic Algorithms
  • Low-Rank Approximation (LRA): Observed a 9x decrease in the number of kernel evaluations compared to standard baselines on the MNIST dataset.
  • Spectral Sparsification: Achieved a 41x reduction in graph size (number of edges) while maintaining enough structural information to cluster the "Nested" and "Rings" datasets with near-perfect accuracy.
  • Computational Efficiency: On the "Rings" dataset, computing eigenvectors on the sparsified graph took 0.08 seconds, compared to 0.27 seconds for the full dense matrix (a ~3.4x speedup).
  • Theoretical Breadth: The paper provides the first subquadratic algorithms for a massive list of problems, including arboricity estimation, triangle counting, and Laplacian system solvers for kernel matrices, significantly improving upon prior work.

Limitations and Future Work

  • Dependence on $\tau$: The algorithms scale inversely with $\tau$ (e.g., $1/\tau^3$). If the kernel function decays very rapidly and $\tau$ becomes extremely small, the subquadratic advantage may diminish.
  • Additive vs. Relative Error: For low-rank approximation, the current algorithm provides additive error guarantees. While easier to implement and evaluate, some applications strictly require relative error, which remains a more computationally expensive target.
  • Optimal $\tau$ Scaling: The authors note that the optimal dependence on $\tau$ for spectral sparsification is still an open theoretical question, suggesting there may be even faster algorithms yet to be discovered.

Summary updated

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 \emph{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 recently developed 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 \emph{weighted vertex} and \emph{weighted edge sampling} on kernel graphs, \emph{simulating random walks} on kernel graphs, and \emph{importance sampling} on matrices to Kernel Density Estimation and show that we can generate samples from these distributions in \emph{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 $\textbf{9x}$ decrease in the number of kernel evaluations over baselines for LRA and a $\textbf{41x}$ reduction in the graph size for spectral sparsification.
BibTeX
@inproceedings{bakshi2023subquadratic,
  author = {Ainesh Bakshi and Piotr Indyk and Praneeth Kacham and Sandeep Silwal and Samson Zhou},
  title = {{Subquadratic Algorithms for Kernel Matrices via Kernel Density Estimation}},
  booktitle = {International Conference on Learning Representations},
  year = {2023},
  url = {https://openreview.net/forum?id=74A-FDAyiL},
}
Figure