Tensor Sketch: Fast and Scalable Polynomial Kernel Approximation

Ninh Pham [email protected], Rasmus Pagh [email protected] · 2025

Read Tensor Sketch: Fast and Scalable Polynomial Kernel Approximation by Ninh Pham [email protected], Rasmus Pagh [email protected] (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-08146.txt.

Introduction

Ninh Pham and Rasmus Pagh give a fast sketching method for polynomial kernels, in a 2025 paper. Kernel methods compare data through a chosen similarity score, but exact scores scale badly. Random maps can compress data while keeping the score near true.

Their Tensor Sketch builds such maps for polynomial scores with a clean run time on large sets. They prove bounds on how far the sketched score can stray. Sketches run well on high dimensional data that defeat exact methods. The pair also note extensions and uses where the sketch serves as the core step. The work helps machine learning on data too big for classic kernels.

Catalog record

CREATORNinh Pham [email protected], Rasmus Pagh [email protected]
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE56 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-08146

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Tensor Sketch: Fast and Scalable Polynomial Kernel Approximation Ninh Pham [email protected], Rasmus Pagh [email protected] Abstract Approximation of non-linear kernels using random feature maps has become a powerful technique for scaling kernel methods to large datasets. We propose Tensor Sketch , an efficient random feature map for approximating polynomial kernels. Given n n training samples in ℝ d \mathbb{R}^{d} Tensor Sketch computes low-dimensional embeddings in ℝ D \mathbb{R}^{D} in time 𝒪 ⁡ ( n ⁡ ( d + D ​ log ⁡ D ) ) \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. xxxx and xxxx † † heading: x 20xx x-xx x/xx xx/xx meila00a † † shortheadings: Tensor Sketch / Pham and Pagh † † firstpage: 1 † † editor: xxxx and xxxx keywords Polynomial kernel, SVM, Tensor Product, Count Sketches, FFT 1 Introduction Kernel machines such as Support Vector Machines (SVMs) ( Schölkopf and Smola, 2002 ) , are powerful tools for a wide range of machine learning and data mining tasks. A key strength of kernel methods lies in their ability to capture non-linear structure in data through the use of kernel functions. These functions implicitly map data from the original space to a high-dimensional feature space, where each coordinate corresponds to a feature of the input vectors. In this kernel space, many standard learning algorithms operate using only pairwise inner products, without explicitly computing the mapped coordinates. This implicit approach not only reduces computational overhead but also enables kernel methods to handle diverse data types, including both numeric and symbolic inputs, in a unified framework. While kernel methods have achieved considerable success across a wide range of data analysis tasks ( Shawe-Taylor and Cristianini, 2004 ) , their scalability remains a significant limitation. Kernel-based learning algorithms typically suffer from high computational and memory costs, with direct methods often requiring cubic time and quadratic space in the number of training samples ( Schölkopf and Smola, 2002 ) . This issue becomes increasingly problematic in modern machine learning applications that rely on large-scale datasets. In high-dimensional domains such as text, where data is often represented using sparse bag-of-words vectors, linear models – particularly linear SVMs – have demonstrated strong empirical performance ( Joachims, 1998 ; Lewis et al., 2004 ) . Consequently, there has been substantial research on designing training algorithms for linear SVMs that scale linearly with the number of training examples ( Joachims, 2006 ; Shalev-Shwartz et al., 2011 ; Fan et al., 2008 ; Bubeck, 2015 ; Allen-Zhu, 2017 ; d’Aspremont et al., 2021 ) . Since non-linear SVMs with kernel functions can be interpreted as linear SVMs operating in a high-dimensional feature space, Rahimi and Recht (2007) first proposed random feature maps for approximating shift-invariant kernels to combine the advantages of linear and non-linear SVM approaches. Their approach approximates kernels by a randomized feature map from data space into a relatively low-dimensional feature space. In this randomized feature space, the kernel function of any two vectors is well approximated by their inner product with high probability. In other words, the randomized feature map can be seen as a specific dimensionality reduction from the feature space, computed directly from vectors in data space. This enables the use of fast linear learning algorithms to approximate the performance of non-linear kernel methods, significantly reducing training time while maintaining competitive generalization performance. Given any two vectors \mathbf{x}=\left(x_{1},\ldots,x_{d}\right),\mathbf{y}=\left(y_{1},\ldots,y_{d}\right)\in\mathbb{R}^{d} , we denote their inner product by \left\langle\mathbf{x},\mathbf{y}\right\rangle=\sum_{i=1}^{d}x_{i}y_{i} . For an implicit feature space map \phi:\mathbb{R}^{d}\mapsto\mathcal{F} the inner product between vectors in the feature space \mathcal{F} can be quickly computed as \left\langle\phi(\mathbf{x}),\phi(\mathbf{y})\right\rangle=\kappa(\mathbf{x},\mathbf{y}) where \kappa(\cdot) is an easily computable kernel function. A random feature map f:\mathbb{R}^{d}\mapsto\mathbb{R}^{D} , where D is an integer parameter, can be used to approximate a kernel \kappa(\cdot) if it satisfies \mathbb{E}\left[\left\langle f(\mathbf{x}),f(\mathbf{y})\right\rangle\right]=\left\langle\phi(\mathbf{x}),\phi(\mathbf{y})\right\rangle=\kappa(\mathbf{x},\mathbf{y}), with good concentration around the expected value. Using such feature maps we can transform data from the original data space into a D -dimensional randomized feature space to efficiently approximate the solutions of learning algorithms on high-dimensional feature spaces. This line of work enables kernel methods to handle massive datasets on many standard statistical learning tasks, including kernel ridge regression ( Avron et al., 2017a ; Avron et al., 2017b ) , support vector machines ( Rahimi and Recht, 2007 ; Lu et al., 2016 ) , clustering ( Wu et al., 2018 ; Xu and Pham, 2024 ) and dimensionality reduction ( Lopez-Paz et al., 2014 ; Sriperumbudur and Sterge, 2022 ) . Randomized techniques for kernel approximation fall into two broad categories: data-dependent and data-independent methods. A prominent example of data-dependent approaches is Nyström method ( Williams and Seeger, 2000 ; Yang et al., 2012 ; Gittens and Mahoney, 2016 ) , which approximates the kernel matrix using a subset of training data. More recent variants leverage statistical properties such as leverage scores of the kernel matrix to select informative samples for improved approximation ( Avron et al., 2017b ; Li et al., 2019 ; Liu et al., 2020 ) . In contrast, data-independent random feature maps ( Rahimi and Recht, 2007 ) approximate the entire kernel function – not just the matrix – using features drawn from fixed distributions. This makes them particularly well-suited for online learning and streaming settings, where access to the full training set may be limited. Understanding the theoretical and practical properties of such random features has been the focus of extensive research over the past decade ( Sriperumbudur and Szabó, 2015 ; Bach, 2017 ; Rudi and Rosasco, 2017 ; Sun et al., 2018 ; Li et al., 2019 ) . These efforts have extended to downstream machine learning applications ( Muandet et al., 2017 ; Liu et al., 2022 ) , as well as to scaling deep learning architectures and analyzing over-parameterized neural networks ( Yehudai and Shamir, 2019 ; Zandieh et al., 2021 ; Choromanski et al., 2021 ; Fu et al., 2023 ) . Our contribution. This paper investigates algorithmic aspects of data-independent random features, with a focus on polynomial kernels. Although many modern learning algorithms can be trained in time linear in the number of samples ( Bubeck, 2015 ) , the cost of computing random features often becomes a bottleneck. Specifically, many existing kernel approximation methods require time and space proportional to the product of the data dimension d and the number of random features D . For instance, Rahimi and Recht (2007) maintained D random vectors \mathbf{w}_{1},\ldots,\mathbf{w}_{D}\in\mathbb{R}^{d} , requiring {\mathcal{O}}\left(dD\right) time and space to compute D features. When D={\mathcal{O}}\left(d\right) , this leads to quadratic costs, which may exceed the time spent in the actual learning or prediction phase. As a result, the cost of the random mapping itself can dominate the overall runtime of kernel-based methods. We study a near-linear time random feature mapping for approximating the standard polynomial kernel \kappa(\mathbf{x},\mathbf{y})=\left(c+\left\langle\mathbf{x},\mathbf{y}\right\rangle\right)^{p} for an integer p\geq 1 and a real c\geq 0 . The polynomial kernel is a widely used example of a non-stationary kernel, and it serves as a building block for a broader class of kernels that can

Read the complete text