Research map / Learning theory and algorithms / Kernels and regression theory
Supervised Kernel Thinning
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.
Combines kernel thinning (KT-Compress++) with Nadaraya-Watson and kernel ridge regression by designing meta-kernels over input-output pairs, giving KT-NW and KT-KRR estimators with quadratic speed-ups and improved statistical rates over i.i.d. subsampling.
Problem
Non-parametric regression with kernel methods (Nadaraya-Watson and kernel ridge regression) is computationally expensive at training and inference time for large n, while coreset methods have been designed for unsupervised integration rather than supervised learning.
Approach
Treat NW and KRR as averages of functions over the empirical measure and choose meta-kernels over (x,y) pairs (k + k·y1y2 for NW; k² + k·y1y2 for KRR) so that kernel thinning with KT-Compress++ yields a coreset of size sqrt(n) whose regression estimates retain near-minimax rates.
Key results
- KT-NW achieves O(n log^3 n) training and O(sqrt n) inference with MSE rate n^{-β/(β+d)} log^2 n, strictly better than ST-NW's n^{-β/(2β+d)}.
- On California Housing, KT-KRR gets test MSE 0.5580% in 0.0153s training versus 0.3237s for RPCholesky-KRR and 0.5736% for ST-KRR.
- On SUSY, KT-KRR gets 22.00% test error in 1.79s training, between ST-KRR (22.71%) and RPCholesky (19.99%) while being faster than RPCholesky (3.46s).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the KT-NW supervised meta-kernel instead of standard i.i.d. thinning | NW regression · Simulated data | MSE | Helped |
| Use the KT-NW supervised meta-kernel instead of RPCholesky point selection | NW regression · Simulated data | MSE | Helped |
| Use the KT-NW supervised meta-kernel instead of full-data NW | NW regression · Simulated data | MSE | Hurt |
| Use the KT-KRR supervised meta-kernel instead of standard i.i.d. thinning | KRR · Simulated data | MSE | Helped |
| Use the KT-KRR supervised meta-kernel instead of RPCholesky landmark selection | KRR · Simulated data | MSE | Hurt |
| Use KT-KRR instead of full-data KRR | KRR · Simulated data | MSE | Hurt |
| Use KT-KRR instead of ST-KRR | KRR · California Housing | MSE (%): 0.5736 ± 0.0018 -> 0.5580 ± 0.0015 | Helped |
| Use KT-KRR instead of RPCholesky-KRR | KRR · California Housing | MSE (%): 0.3503 ± 0.0001 -> 0.5580 ± 0.0015 | Hurt |
| Use KT-KRR instead of ST-KRR | KRR · SUSY | test error (%): 22.71 ± 0.30 -> 22.00 ± 0.21 | Helped |
| Use KT-KRR instead of RPCholesky preconditioning | KRR · SUSY | test error (%): 19.99 ± 0.00 -> 22.00 ± 0.21 | Hurt |
| Use the NW supervised meta-kernel k(x1,x2) + k(x1,x2)y1y2 instead of the base input kernel (ablation) | KT-NW · Simulated data | MSE | Helped |
| Use the NW supervised meta-kernel instead of the concatenated (x,y) kernel (ablation) | KT-NW · Simulated data | MSE | Helped |
Surprising findings
- KT-KRR does not achieve a strictly better excess risk rate than ST-KRR for infinite-dimensional kernels, though it shows empirical gains.
- RPCholesky-KRR attains lower MSE than KT-KRR on the California Housing and SUSY datasets despite being slower.
Limitations
- Guarantees hold only when f* lies in the RKHS of a base kernel; misspecification is not covered.
- Theory for NW requires a reproducing shift-invariant kernel, and infinite-dimensional KT-KRR gives no strict rate improvement over ST-KRR.
Experimental setup
Datasets: California Housing SUSY
Benchmarks: California Housing SUSY simulated regression
Metrics: test MSE test classification error training time prediction time
Baselines: Full-NW ST-NW RPCholesky-NW Full-KRR ST-KRR RPCholesky-KRR FALKON Conjugate Gradient
Builds on: kernel thinning KT-Compress++ Nystrom subsampling RPCholesky
Closest papers by meaning
- Generalized Kernel Thinning (ICLR 2022 · similarity 0.92)
- Debiased Distribution Compression (ICML 2024 · similarity 0.89)
- Low-Rank Thinning (ICML 2025 · similarity 0.89)
- Kernel Regression in Structured Non-IID Settings: Theory and Implications for Denoising Score Learning (NeurIPS 2025 · similarity 0.88)
- A Comprehensive Analysis on the Learning Curve in Kernel Ridge Regression (NeurIPS 2024 · similarity 0.87)
- Conditional Distribution Compression via the Kernel Conditional Mean Embedding (NeurIPS 2025 · 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.