Research map / Learning theory and algorithms / Matrix and tensor methods
Memory Efficient Kernel Approximation
Si Si, Cho-Jui Hsieh, Inderjit S. Dhillon
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (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 k-means clustering in input space instead of random partition for blocks (ablation) | BKA / MEKA blocks · ijcnn1 subsample (4000 points, 5 blocks) | numerical rank of blocks: k-means block ranks 7-29 versus random partition ranks 43-139 | Improved |
| use k-means partition instead of random partition in BKA (ablation) | BKA · covtype and cadata (500 samples, five partitions) | Gaussian kernel approximation error | Improved |
| add off-diagonal link matrix (MEKA) instead of block-diagonal only BKA (ablation) | BKA · covtype sample, varying gamma | relative approximation error | Improved |
| increase number of clusters in BKA-SVM (ablation) | BKA-SVM · ijcnn1, census, covtype | training time and accuracy | Mixed |
| use BKA-SVM instead of LLSVM and FastFood low-rank solvers | kernel SVM · covtype | test accuracy (%): 84.21 -> 96.05 (LLSVM), 80.1 -> 96.05 (FastFood) | Improved |
| use MEKA instead of standard Nystrom at equal memory | Nystrom · ijcnn1 gamma=1 | relative kernel approximation error: 0.0423 -> 0.0082 | Improved |
| use MEKA instead of standard Nystrom at equal memory | Nystrom · covtype gamma=10 | relative kernel approximation error: 0.3700 -> 0.1192 | Improved |
| use Nystrom-based basis instead of random feature (RKS, Fastfood) methods | kernel approximation · pendigit, ijcnn1, covtype | relative kernel approximation error: 0.0811 vs 0.4404 (RKS), 0.4726 (fastfood) on pendigit | Improved |
| use MEKA instead of standard Nystrom for kernel ridge regression | Nystrom · covtype kernel ridge regression | test RMSE: 0.8197 -> 0.7106 | Improved |
| use MEKA instead of standard Nystrom for kernel ridge regression | Nystrom · cpusmall kernel ridge regression | test RMSE: 8.8747 -> 6.1130 | Improved |
| raise thresholding epsilon that zeros off-diagonal link blocks (ablation) | MEKA · ijcnn1 and cadata | time vs approximation error | Mixed |
| choose rank per cluster by size or by eigenvalues instead of the same k (ablation) | MEKA · ijcnn1 and cadata | approximation error | No clear effect |
Closest papers by meaning
- Giga-scale Kernel Matrix-Vector Multiplication on GPU (NeurIPS 2022 · similarity 0.88)
- Is Input Sparsity Time Possible for Kernel Low-Rank Approximation? (NeurIPS 2017 · similarity 0.88)
- Incremental Nyström-based Multiple Kernel Clustering (AAAI 2025 · similarity 0.87)
- Scalable Multiple Kernel Clustering: Learning Clustering Structure from Expectation (ICML 2024 · similarity 0.86)
- Random features for Grassmannian kernel approximation with bounded rank-one projections (NeurIPS 2026 · similarity 0.86)
- On the Target-kernel Alignment: a Unified Analysis with Kernel Complexity (NeurIPS 2024 · similarity 0.86)
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.
