Introduction
Kernel methods are a staple of machine learning, allowing models to learn complex, non-linear patterns by implicitly mapping data into a high-dimensional "feature space." However, this expressive power comes at a steep computational cost. Traditionally, utilizing a kernel requires computing the Gram matrix—an $n \times n$ matrix of all pairwise similarities—which takes $O(n^2 d)$ time. For large datasets, this quadratic scaling becomes a massive bottleneck.
"Sketching" is a popular dimensionality reduction technique used to accelerate statistical learning by compressing data into a lower-dimensional "sketch" while preserving its geometric properties. While sketching works exceptionally well for linear models, applying it to kernels is notoriously difficult because the implicit feature space is often too large to represent explicitly (e.g., for a degree-$q$ polynomial kernel, the dimension scales as $d^q$). The central challenge addressed in this work is: Can we create a sketch of a high-dimensional kernel space without ever actually computing or visiting that space?
This paper introduces the first fast Oblivious Subspace Embedding (OSE) for the polynomial kernel. By proving that the existing TensorSketch algorithm provides a subspace-wide guarantee, the authors enable nearly linear-time algorithms for approximate Kernel Principal Component Analysis (PCA) and Principal Component Regression (PCR) without explicitly mapping data into high-dimensional feature spaces.
Methodology: TensorSketch as an Oblivious Subspace Embedding
The authors focus their analysis on the Polynomial Kernel: $k(x, y) = (\langle x, y \rangle + c)^q$.
The key technical contribution is a rigorous theoretical analysis of TensorSketch. Originally designed to accelerate matrix multiplication, TensorSketch uses a combination of CountSketch (a hashing-based dimensionality reduction technique) and the Fast Fourier Transform (FFT) to efficiently compute the sketch of a tensor product.
Crucially, the authors prove that TensorSketch functions as an Oblivious Subspace Embedding. This is a significantly stronger property than what was previously established. While earlier work demonstrated that TensorSketch preserves the length of a single vector (a pointwise guarantee), this paper proves it preserves the geometry of an entire $k$-dimensional subspace. Furthermore, they show that the hash functions used in TensorSketch only need to be 3-wise independent to satisfy the OSE property, simplifying the randomness requirements.
Building on this, they introduce the $k$-Space algorithm, which uses two independent TensorSketches to:
- Find an approximate basis for the top $k$ principal components of the data in the kernel space.
- Project the data onto this basis to perform low-rank approximation or regression.
Because the method operates implicitly, it runs in time roughly proportional to the number of non-zero entries in the input matrix ($nnz(A)$), making it drastically faster than methods requiring the full Gram matrix.
Key Results and Performance
The authors evaluated their approach on several standard classification and regression benchmarks, including MNIST ($n=60,000$), CPU ($n=6,554$), ADULT ($n=32,561$), CENSUS ($n=18,186$), and USPS ($n=7,291$).
The empirical results highlight massive improvements in both efficiency and scalability. For instance, on the MNIST dataset, standard Kernel PCA Regression often runs out of memory because the $60,000 \times 60,000$ Gram matrix is simply too large to store and process. The proposed $k$-Space algorithm (Sampled PCA Regression) handled this dataset easily, achieving a 7.9% error rate, compared to a 14% error rate for standard linear regression.
In almost all evaluated cases, performing regression on the sketched "principal components" led to better generalization (lower test error) than using the original features. This suggests that the sketching process inherently acts as a form of regularization.
Theoretically, for the polynomial kernel, the total time to compute a low-rank approximation is reduced to $O(nnz(A) \cdot q + (n+d) \cdot poly(k/\epsilon))$. This is a massive algorithmic speedup over the traditional $O(n^2 d)$ or $O(d^q)$ alternatives.
Limitations and Future Directions
While groundbreaking for polynomial kernels, the current proofs and methods are specifically tailored to this kernel type. The authors note that while many kernels have finite expansions, they do not yet provide OSEs for non-finite kernel expansions, such as the popular Gaussian (RBF) kernel.
Additionally, the "fast" component of the algorithm still depends on a polynomial of $k$ (the target rank) and $1/\epsilon$ (the error tolerance). If $k$ is very large or if extremely high precision is required, this overhead could become significant.
Future work will likely focus on designing OSEs for non-finite kernel expansions. Successfully extending these sketching techniques to the Gaussian kernel would open the door for highly scalable, sketching-based RBF methods across a wider array of machine learning applications.
Summary updated