Tensor Sketch: Fast and Scalable Polynomial Kernel Approximation
This provides a fast and scalable solution for machine learning practitioners dealing with high-dimensional and large-scale data, though it is incremental as it builds on existing random feature map techniques.
The paper tackles the problem of scaling kernel methods to large datasets by proposing Tensor Sketch, an efficient random feature map for approximating polynomial kernels, achieving embeddings in time O(n(d + D log D)) with theoretical guarantees on approximation error.
Approximation of non-linear kernels using random feature maps has become a powerful technique for scaling kernel methods to large datasets. We propose $\textit{Tensor Sketch}$, an efficient random feature map for approximating polynomial kernels. Given $n$ training samples in $\mathbb{R}^d$ Tensor Sketch computes low-dimensional embeddings in $\mathbb{R}^D$ in time $\mathcal{O}\left( n(d+D \log{D}) \right)$ making it well-suited for high-dimensional and large-scale settings. We provide theoretical guarantees on the approximation error, ensuring the fidelity of the resulting kernel function estimates. We also discuss extensions and highlight applications where Tensor Sketch serves as a central computational tool.