Kernel methods are a cornerstone of non-linear machine learning, enabling algorithms to find complex patterns by implicitly mapping data into high-dimensional feature spaces. However, this power comes at a significant computational cost: the kernel matrix grows quadratically with the number of data points, creating a bottleneck for large-scale applications. Sketching techniques offer a solution by compressing data into a lower-dimensional space while preserving essential geometric properties like distances and inner products.
Among these, oblivious sketches are particularly valuable. These are randomized mappings generated independently of the dataset, making them ideal for streaming, distributed computing, and privacy-preserving applications. This paper introduces a breakthrough in the efficiency of these sketches for high-degree polynomial and Gaussian kernels.
The Exponential Barrier
For a polynomial kernel of degree $p$, defined as $k(x, y) = \langle x, y \rangle^p$, the standard tool has been TensorSketch. While effective for low degrees, TensorSketch and its variants suffer from a target dimension that grows exponentially with $p$ (specifically $3^p$). This "exponential curse" renders high-degree polynomial kernels practically inaccessible for large datasets.
Furthermore, because the Gaussian kernel can be approximated via a Taylor expansion (effectively an infinite-degree polynomial), this exponential dependence has historically prevented efficient, oblivious sketching of Gaussian kernels without suffering from an exponential dependence on the original data dimension $d$. This limitation has forced researchers to rely on non-oblivious methods like Nyström approximations or data-dependent sketches for high-dimensional non-linear tasks.
Recursive Tensoring: A Hierarchical Approach
The core innovation of this work is Recursive Tensoring. The authors prove that simply tensoring standard Johnson-Lindenstrauss matrices inherently forces an exponential dependence on $p$. To break this, they propose a hierarchical, tree-based architecture for the sketching process.
Imagine the sketching process as a balanced binary tree:
- Leaves: The process begins at the bottom level, where standard, highly efficient linear sketches (such as CountSketch or OSNAP) are applied directly to the input vectors.
- Internal Nodes: Moving up the tree, the algorithm pairs up the sketched vectors from the previous level. It then applies specialized sketches designed for tensor products—such as TensorSketch or a newly introduced variant called TensorSRHT—to these pairs.
- Root: After $\log_2 p$ levels of recursive sketching and dimension reduction, the algorithm outputs a single sketched vector.
By compressing the data step-by-step at each level of the tree, the accumulation of mathematical error is tightly controlled. This structural innovation is what allows the target dimension to scale polynomially, rather than exponentially, with the degree $p$.
Key Theoretical Breakthroughs
The paper provides rigorous mathematical bounds for this new approach, yielding several landmark results:
- Polynomial Kernel Sketch: The authors developed an oblivious subspace embedding for degree-$p$ polynomial kernels with a target dimension of $m = \tilde{\Omega}(p^4 s_\lambda / \epsilon^2)$. This replaces the previous state-of-the-art's $3^p$ dependence with a highly efficient $p^4$ dependence.
- Unlocking the Gaussian Kernel: By applying recursive tensoring to a truncated Taylor series, the authors achieved the first oblivious sketch for the Gaussian kernel (on bounded datasets) with a target dimension that scales linearly with the statistical dimension ($s_\lambda$) and polynomially with the dataset radius.
- Input Sparsity Time: The proposed algorithms run in time proportional to the number of non-zero entries in the input data ($\tilde{O}(\text{nnz}(X))$), making them incredibly fast for sparse, high-dimensional datasets.
Impact and Future Directions
In regularized machine learning tasks like ridge regression, the complexity of a dataset is often measured by its statistical dimension $s_\lambda$, which is typically much smaller than the number of data points. By achieving a target dimension that scales linearly with $s_\lambda$, this method is theoretically optimal.
These sketches dramatically speed up downstream tasks like kernel ridge regression, kernel PCA, and canonical correlation analysis, moving their time complexities from exponential to polynomial with respect to $p$. While the paper is primarily theoretical, it sets the stage for significant practical improvements. Future work will likely focus on implementing these recursive sketches in optimized software libraries to benchmark their performance against heuristic methods like Random Fourier Features in real-world settings.
Summary updated