Research map / Learning theory and algorithms / Kernels and regression theory
Recycling Randomness with Structure for Sublinear time Kernel Expansions
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 |
|---|---|---|---|
| Use Toeplitz-like semi-Gaussian features with displacement rank 20 instead of Gaussian random features | Kernel random feature maps · USPS (k=256), kernel approximation error | kernel approximation error (%): 5.06 -> 6.68 | Hurt |
| Use Toeplitz-like semi-Gaussian features with displacement rank 20 instead of Gaussian random features | Kernel random feature maps · USPS (k=256), classification | classification error (%): 7.12 -> 7.29 | Hurt |
| Use Toeplitz-like semi-Gaussian features with displacement rank 20 instead of Gaussian random features | Kernel random feature maps · DNA (k=80), classification | classification error (%): 31.04 -> 30.70 | Helped |
| Increase Toeplitz-like displacement rank from 1 to 20 (ablation) | Toeplitz-like kernel features · USPS (k=256) | kernel approximation error (%): 9.66 -> 6.68 | Helped |
| Increase Toeplitz-like displacement rank from 1 to 20 (ablation) | Toeplitz-like kernel features · USPS (k=1280) | kernel approximation error (%): 4.41 -> 3.00 | Helped |
| Increase Toeplitz-like displacement rank from 1 to 20 (ablation) | Toeplitz-like kernel features · DNA (k=80) | kernel approximation error (%): 6.26 -> 4.10 | Helped |
| Increase Toeplitz-like displacement rank from 1 to 20 (ablation) | Toeplitz-like kernel features · DNA (k=900) | kernel approximation error (%): 2.88 -> 1.83 | Helped |
| Increase Toeplitz-like displacement rank from 1 to 20 (ablation) | Toeplitz-like kernel features · COIL (k=1024) | kernel approximation error (%): 5.60 -> 3.79 | Helped |
| Increase Toeplitz-like displacement rank from 1 to 20 (ablation) | Toeplitz-like kernel features · COIL (k=2048) | kernel approximation error (%): 4.18 -> 2.76 | Helped |
| Increase Toeplitz-like displacement rank from 1 to 20 (ablation) | Toeplitz-like kernel features · USPS (k=1280) | classification error (%): 4.62 -> 4.65 | No clear effect |
| Increase Toeplitz-like displacement rank from 1 to 20 (ablation) | Toeplitz-like kernel features · DNA (k=80) | classification error (%): 31.35 -> 30.70 | Helped |
| Increase Toeplitz-like displacement rank from 1 to 20 (ablation) | Toeplitz-like kernel features · COIL (k=1024) | classification error (%): 0.62 -> 0.52 | Hurt |
Closest papers by meaning
- Random features for Grassmannian kernel approximation with bounded rank-one projections (NeurIPS 2026 · similarity 0.88)
- The Unreasonable Effectiveness of Structured Random Orthogonal Embeddings (NeurIPS 2017 · similarity 0.88)
- Scalable Learning in Reproducing Kernel Krein Spaces (ICML 2019 · similarity 0.87)
- Structure-Aware Random Fourier Kernel for Graphs (NeurIPS 2021 · similarity 0.87)
- Manifold Random Features (NeurIPS 2026 · similarity 0.86)
- The Price of Linear Time: Error Analysis of Structured Kernel Interpolation (ICML 2025 · 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.