Tensor Sketch: Fast and Scalable Polynomial Kernel Approximation

• URL: http://arxiv.org/abs/2505.08146v2
• Date: Sun, 18 May 2025 05:01:24 GMT
• Title: Tensor Sketch: Fast and Scalable Polynomial Kernel Approximation
• Authors: Ninh Pham, Rasmus Pagh,
• Abstract summary: Approximation of non-linear kernels using random feature maps has become a powerful technique for scaling kernel methods to large datasets.<n>We provide theoretical guarantees on the approximation error, ensuring the fidelity of the resulting kernel function estimates.
• Score: 19.363672064425504
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Dimensionality Reduction for General KDE Mode Finding [12.779486428760373]
  Finding the mode of a high dimensional probability distribution $D$ is a fundamental problem in statistics and data analysis. We show that there is no time algorithm for finding the mode of a kernel density estimate, unless $mathitP = mathitNP$.
  arXiv  Detail & Related papers  (2023-05-30T05:39:59Z)
• Sub-quadratic Algorithms for Kernel Matrices via Kernel Density Estimation [24.166833799353476]
  We develop efficient reductions from $textitweighted edge sampling$ on kernel graphs, $textitsimulating random walks$ on kernel graphs, and $textitweighted sampling$ on matrices to Kernel Density Estimation. Our reductions are the central ingredient in each of our applications and we believe they may be of independent interest.
  arXiv  Detail & Related papers  (2022-12-01T16:42:56Z)
• Efficient Dataset Distillation Using Random Feature Approximation [109.07737733329019]
  We propose a novel algorithm that uses a random feature approximation (RFA) of the Neural Network Gaussian Process (NNGP) kernel. Our algorithm provides at least a 100-fold speedup over KIP and can run on a single GPU. Our new method, termed an RFA Distillation (RFAD), performs competitively with KIP and other dataset condensation algorithms in accuracy over a range of large-scale datasets.
  arXiv  Detail & Related papers  (2022-10-21T15:56:13Z)
• On The Relative Error of Random Fourier Features for Preserving Kernel Distance [7.383448514243228]
  We show that for a significant range of kernels, including the well-known Laplacian kernels, RFF cannot approximate the kernel distance with small relative error using low dimensions. We make the first step towards data-oblivious dimension-reduction for general shift-invariant kernels, and we obtain a similar $mathrmpoly(epsilon-1 log n)$ dimension bound for Laplacian kernels.
  arXiv  Detail & Related papers  (2022-10-01T10:35:12Z)
• Scalable First-Order Bayesian Optimization via Structured Automatic Differentiation [4.061135251278187]
  We show that a wide range of kernels gives rise to structured matrices, enabling an exact $mathcalO(n2d)$ matrix-vector multiply for gradient observations and $mathcalO(n2d2)$ for Hessian observations. Our methods apply to virtually all canonical kernels and automatically extend to complex kernels, like the neural network, radial basis function network, and spectral mixture kernels.
  arXiv  Detail & Related papers  (2022-06-16T17:59:48Z)
• Complex-to-Real Sketches for Tensor Products with Applications to the Polynomial Kernel [15.535749953841274]
  Randomized sketches of a product of $p$ vectors follow a tradeoff between statistical efficiency and computational acceleration. We propose a simple Complex-to-Real (CtR) modification of well-known sketches that replaces real random projections by complex ones. We show that our method achieves state-of-the-art performance in terms of accuracy and speed compared to other randomized approximations from the literature.
  arXiv  Detail & Related papers  (2022-02-04T09:15:43Z)
• Random matrices in service of ML footprint: ternary random features with no performance loss [55.30329197651178]
  We show that the eigenspectrum of $bf K$ is independent of the distribution of the i.i.d. entries of $bf w$. We propose a novel random technique, called Ternary Random Feature (TRF) The computation of the proposed random features requires no multiplication and a factor of $b$ less bits for storage compared to classical random features.
  arXiv  Detail & Related papers  (2021-10-05T09:33:49Z)
• Fast Sketching of Polynomial Kernels of Polynomial Degree [61.83993156683605]
  kernel is especially important as other kernels can often be approximated by the kernel via a Taylor series expansion. Recent techniques in sketching reduce the dependence in the running time on the degree oblivious $q$ of the kernel. We give a new sketch which greatly improves upon this running time, by removing the dependence on $q$ in the leading order term.
  arXiv  Detail & Related papers  (2021-08-21T02:14:55Z)
• Scaling Neural Tangent Kernels via Sketching and Random Features [53.57615759435126]
  Recent works report that NTK regression can outperform finitely-wide neural networks trained on small-scale datasets. We design a near input-sparsity time approximation algorithm for NTK, by sketching the expansions of arc-cosine kernels. We show that a linear regressor trained on our CNTK features matches the accuracy of exact CNTK on CIFAR-10 dataset while achieving 150x speedup.
  arXiv  Detail & Related papers  (2021-06-15T04:44:52Z)
• Random Features for the Neural Tangent Kernel [57.132634274795066]
  We propose an efficient feature map construction of the Neural Tangent Kernel (NTK) of fully-connected ReLU network. We show that dimension of the resulting features is much smaller than other baseline feature map constructions to achieve comparable error bounds both in theory and practice.
  arXiv  Detail & Related papers  (2021-04-03T09:08:12Z)
• Finding Global Minima via Kernel Approximations [90.42048080064849]
  We consider the global minimization of smooth functions based solely on function evaluations. In this paper, we consider an approach that jointly models the function to approximate and finds a global minimum.
  arXiv  Detail & Related papers  (2020-12-22T12:59:30Z)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  We show that there exists an $epsilon$-cover for $S$ of cardinality $M = (k/epsilon)O_d(k1/d)$. Building on our structural result, we obtain significantly improved learning algorithms for several fundamental high-dimensional probabilistic models hidden variables.
  arXiv  Detail & Related papers  (2020-12-14T18:14:08Z)
• Fourier Sparse Leverage Scores and Approximate Kernel Learning [29.104055676527913]
  We prove new explicit upper bounds on the leverage scores of Fourier functions under both the Gaussian and Laplace measures. Our bounds are motivated by two important applications in machine learning.
  arXiv  Detail & Related papers  (2020-06-12T17:25:39Z)
• Linear Time Sinkhorn Divergences using Positive Features [51.50788603386766]
  Solving optimal transport with an entropic regularization requires computing a $ntimes n$ kernel matrix that is repeatedly applied to a vector. We propose to use instead ground costs of the form $c(x,y)=-logdotpvarphi(x)varphi(y)$ where $varphi$ is a map from the ground space onto the positive orthant $RRr_+$, with $rll n$.
  arXiv  Detail & Related papers  (2020-06-12T10:21:40Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.