Fast and scalable polynomial kernels via explicit feature maps

2013/08/11 by Ninh Pham, Rasmus Pagh · 5 citations
Computer Science · Mathematics · #Advanced Neural Network Applications #Tensor decomposition and applications #Stochastic Gradient Optimization Techniques

paper · doi:10.1145/2487575.2487591

openalex publication_date 2013/08/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29

Abstract

Approximation of non-linear kernels using random feature mapping has been successfully employed in large-scale data analysis applications, accelerating the training of kernel machines. While previous random feature mappings run in O(ndD) time for n training samples in d-dimensional space and D random feature maps, we propose a novel randomized tensor product technique, called Tensor Sketching, for approximating any polynomial kernel in O(n(d+D logD)) time. Also, we introduce both absolute and relative error bounds for our approximation to guarantee the reliability of our estimation algorithm. Empirically, Tensor Sketching achieves higher accuracy and often runs orders of magnitude faster than the state-of-the-art approach for large-scale real-world datasets.

Citations

• Finding frequent items in data streams
• Gradient-based learning applied to document recognition

Cited by

• Oblivious Subspace Injection Is Not Enough for Relative Error
• Second-order Democratic Aggregation
• Multi-Scale Thermal to Visible Face Verification via Attribute Guided Synthesis
• Convolution [wikipedia]
• Kronecker product [wikipedia]

Related

• Tensor Sketch: Fast and Scalable Polynomial Kernel Approximation
• Tensor machines for learning target-specific polynomial features
• Oblivious Sketching of High-Degree Polynomial Kernels
• Compact Random Feature Maps
• Near Input Sparsity Time Kernel Embeddings via Adaptive Sampling