Research map / Learning theory and algorithms / Kernels and regression theory
Fast Sketching of Polynomial Kernels of Polynomial Degree
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace independent sketches at each tensor-tree node with a shared SRHT and TensorSRHT | Polynomial-kernel sketch · Degree-p polynomial kernel | running time: \widetilde O(pnd+\epsilon^{-2}n^3p^2) -> \widetilde O(nd+\epsilon^{-2}n^2p^2) | Helped |
| Use the limited-randomness sketch rather than the compared prior algorithm | Polynomial-kernel sketch · Degree-p polynomial kernel | running time: \widetilde O(p^{2.5}nd+\poly(\epsilon^{-1},p)n^3) -> \widetilde O(nd+\epsilon^{-2}n^2p^2) | Helped |
| Exactly compute the first s Taylor terms and sample later terms proportional to their coefficients | p-convergent kernel approximation · p-convergent kernels, 2<p<3 | expected running time: O ( (n/\epsilon)^{2+6/(1+2p)} \cdot \poly(\log(nd/\epsilon\delta)) + nd\log(nd/\epsilon\delta)) | Helped |
| Use the general truncation-based algorithm without the sampling scheme | p-convergent kernel approximation · p-convergent kernels with 1<p<3 | running time: The general theorem gives a running time of \widetilde O(n^3/\epsilon^2+nd) for p\geq 3; ... if p\in (1,3), Theorem [ref | Hurt |
| Apply polynomial-kernel sketching to truncated Gaussian Taylor terms | Gaussian kernel approximation · Gaussian kernel | running time: \widetilde O(\epsilon^{-2}n^2q^3+nd) | Helped |
| Use the sampling scheme with the NTK's 1.5-convergent coefficients | Neural Tangent Kernel · Neural Tangent Kernel | running time: \epsilon^{-3} n^{11/3} \cdot \poly( \log(nd/\epsilon\delta) )+nd\log(nd/\epsilon\delta) | Helped |
Closest papers by meaning
- Tight Dimensionality Reduction for Sketching Low Degree Polynomial Kernels (NeurIPS 2019 · similarity 0.90)
- Polynomial Tensor Sketch for Element-wise Function of Low-Rank Matrix (ICML 2020 · similarity 0.86)
- FlashSketch: Sketch-Kernel Co-Design for Fast Sparse Sketching on GPUs (ICML 2026 · similarity 0.85)
- Is Input Sparsity Time Possible for Kernel Low-Rank Approximation? (NeurIPS 2017 · similarity 0.85)
- Adaptive Sketching for Fast and Convergent Canonical Polyadic Decomposition (ICML 2020 · similarity 0.85)
- Incremental Randomized Sketching for Online Kernel Learning (ICML 2019 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.