mlsanityData to 14 Oct 2026

Tensor Sketch: Fast and Scalable Polynomial Kernel Approximation

arXiv 2505.08146 ↗First posted 13 May 2025cs.DS cs.LGcited by 4

Not on the map. Why?

Abstract (arXiv)

Approximation of non-linear kernels using random feature maps has become a powerful technique for scaling kernel methods to large datasets. We propose textitTensor Sketch, an efficient random feature map for approximating polynomial kernels. Given n training samples in ℝd Tensor Sketch computes low-dimensional embeddings in ℝD in time Oleft( n(d+D logD) 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.

Key facts. Cited by 4 papers in the map (data through 14 Oct 2026). Builds on 33 of its 85 references that are in the map. First posted on arXiv 13 May 2025.

Builds on

33 of 85 references.

References · 33

  1. 2020Rethinking Attention with Performerscited by 1,601
  2. 2014Convex Optimization: Algorithms and Complexitycited by 575
  3. 2016Kernel Mean Embedding of Distributions: A Review and Beyondcited by 364
  4. 2014Sketching as a Tool for Numerical Linear Algebracited by 288
  5. 2016Multimodal Compact Bilinear Pooling for Visual Question Answering and Visual Groundingcited by 243
  6. 2016Generalization Properties of Learning with Random Featurescited by 164
  7. 2015On the Equivalence between Kernel Quadrature Rules and Random Feature Expansionscited by 138
  8. 2016Katyusha: The First Direct Acceleration of Stochastic Gradient Methodscited by 135
  9. 2020Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and Beyondcited by 109
  10. 2019On the Power and Limitations of Random Features for Understanding Neural Networkscited by 103
  11. 2015Compact Bilinear Poolingcited by 97
  12. 2013Revisiting the Nystrom Method for Improved Large-Scale Machine Learningcited by 77
21 more
  1. 2018Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guaranteescited by 71
  2. 2018Learning to Evaluate Image Captioningcited by 53
  3. 2021Acceleration Methodscited by 48
  4. 2017Relative Error Tensor Low Rank Approximationcited by 45
  5. 2016Faster Kernel Ridge Regression Using Sketching and Preconditioningcited by 44
  6. 2023What can a Single Attention Layer Learn? A Study Through the Random Features Lenscited by 40
  7. 2015Optimal Rates for Random Fourier Featurescited by 38
  8. 2018Hashing-Based-Estimators for Kernel Density in High Dimensionscited by 33
  9. 2021Scaling Neural Tangent Kernels via Sketching and Random Featurescited by 32
  10. 2017Sketching for Kronecker Product Regression and P-splinescited by 29
  11. 2018But How Does It Work in Theory? Linear SVM with Random Featurescited by 28
  12. 2017High-Order Attention Models for Visual Question Answeringcited by 22
  13. 2015Fast and Guaranteed Tensor Decomposition via Sketchingcited by 19
  14. 2014Randomized Nonlinear Component Analysiscited by 18
  15. 2023Tanimoto Random Features for Scalable Molecular Machine Learningcited by 15
  16. 2013Compact Random Feature Mapscited by 12
  17. 2019Random Fourier Features via Fast Surrogate Leverage Weighted Samplingcited by 8
  18. 2018Scalable Spectral Clustering Using Random Binning Featurescited by 7
  19. 2019Polynomial Tensor Sketch for Element-wise Function of Low-Rank Matrixcited by 7
  20. 2019Higher-order Count Sketch: Dimensionality Reduction That Retains Efficient Tensor Operationscited by 5
  21. 2018KONG: Kernels for ordered-neighborhood graphscited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 4.

4 papers.

  1. 2026Step-resolved data attribution for looped transformerscited by 5
  2. 2026Manifold Random Featurescited by 1
  3. 2026Improving TensorSketch Using Complex Random Variablescited by 0
  4. 2026Accurate Trace Estimation with Fewer Random Bits via Recursive TensorSketchcited by 0