Research map / Learning theory and algorithms / Kernels and regression theory
Spectrally Transformed Kernel Regression
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Revisits spectrally transformed kernel regression (STKR), proving its generality via a target-smoothness characterization and giving scalable inductive implementations with statistical guarantees for known polynomial transforms and kernel PCA.
Problem
How to use unlabeled data for regression via a base similarity kernel, given that kernel ridge regression ignores unlabeled samples; prior spectral transformation methods were mostly transductive and lacked scalable inductive implementations and guarantees.
Approach
Defines target smoothness via a multiscale diffusion-induced metric and shows any sufficiently smooth target is captured by an STK; proposes inductive STKR estimators (Monte-Carlo polynomial STK approximation, inverse Laplacian, and kernel PCA with ridge probe) with closed-form predictors and L2 error bounds.
Key results
- On Computers, SP-topd (transductive) reaches 80.80% accuracy vs 77.30% for Label-Prop.
- On Cora, SP-Lap (transductive) reaches 77.04% vs 73.33% for Label-Prop.
- STKR with s(λ)=λ^p for p>1 substantially outperforms KRR (p=1), which gets 26.35% on Computers inductively.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use inverse Laplacian instead of Label-Prop | Computers node classification · Computers | accuracy (%): 77.30_{3.05} -> 77.81_{3.94} | No clear effect |
| Use inverse Laplacian instead of Label-Prop | Cora node classification · Cora | accuracy (%): 73.33_{6.00} -> 77.04_{5.74} | Helped |
| Use inverse Laplacian instead of Label-Prop | DBLP node classification · DBLP | accuracy (%): 66.44_{3.78} -> 65.42_{5.02} | Hurt |
| Use kernel PCA instead of inverse Laplacian | Computers node classification · Computers | accuracy (%): 77.15_{2.64} -> 80.80_{3.28} | Helped |
| Use kernel PCA instead of inverse Laplacian | Cora node classification · Cora | accuracy (%): 67.78_{7.62} -> 63.70_{6.00} | Hurt |
| Use kernel PCA instead of inverse Laplacian | DBLP node classification · DBLP | accuracy (%): 65.20_{4.92} -> 63.16_{3.41} | Hurt |
| Use STKR with s(λ)=λ^8 instead of base-kernel KRR | Computers node classification · Computers | accuracy (%): 26.35_{4.34} -> 71.91_{4.13} | Helped |
| Use STKR with s(λ)=λ^8 instead of base-kernel KRR | Cora node classification · Cora | accuracy (%): 28.52_{8.56} -> {65.19}_{9.11} | Helped |
| Use STKR with s(λ)=λ^8 instead of base-kernel KRR | DBLP node classification · DBLP | accuracy (%): 44.80_{3.86} -> {64.51}_{4.05} | Helped |
| Use inductive rather than transductive STKR | STKR node classification · Computers | accuracy (%): 77.81_{3.94} -> 77.15_{2.64}; 76.72_{4.12} -> {71.91}_{4.13}; 80.80_{3.06} -> 80.80_{3.28} | Mixed |
| Use inductive rather than transductive STKR | STKR node classification · Cora | accuracy (%): 77.04_{5.74} -> 67.78_{7.62}; 71.48_{5.80} -> {65.19}_{9.11}; 69.26_{7.82} -> 63.70_{6.00} | Hurt |
| Use inductive rather than transductive STKR | STKR node classification · DBLP | accuracy (%): 65.42_{5.02} -> 65.20_{4.92}; 64.52_{4.20} -> {64.51}_{4.05}; 64.86_{4.60} -> 63.16_{3.41} | Mixed |
Surprising findings
- KRR with the base kernel performs very poorly in the inductive setting (e.g., 28.52% on Cora), showing the base kernel alone is nearly useless without spectral transformation.
Limitations
- Assumes full access to the base kernel K(x,x'), which fails for e.g. positive-pair contrastive kernels.
- Does not address how to choose the base kernel.
- Ignores node features in graph tasks; experiments are limited relative to theory.
Experimental setup
Datasets: Computers Cora DBLP
Benchmarks: Computers Cora DBLP
Metrics: accuracy
Baselines: Label-Prop KRR with base kernel
Builds on: Label propagation Kernel ridge regression Kernel PCA Interpolation Sobolev spaces minimax rates
Closest papers by meaning
- On the Target-kernel Alignment: a Unified Analysis with Kernel Complexity (NeurIPS 2024 · similarity 0.86)
- Generalization error of spectral algorithms (ICLR 2024 · similarity 0.86)
- Learning with Exact Invariances in Polynomial Time (ICML 2025 · similarity 0.85)
- Generalization in Kernel Regression Under Realistic Assumptions (ICML 2024 · similarity 0.85)
- Out of the Ordinary: Spectrally Adapting Regression for Covariate Shift (ICML 2024 · similarity 0.84)
- Inverse M-Kernels for Linear Universal Approximators of Non-Negative Functions (NeurIPS 2024 · similarity 0.84)
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.