Research map / Learning theory and algorithms / Kernels and regression theory
On the Target-kernel Alignment: a Unified Analysis with Kernel Complexity
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.
Analyzes truncated kernel-based methods (spectral truncation of the kernel matrix) under general Lipschitz convex losses via kernel complexity, showing truncation removes the saturation effect under target-kernel alignment and proving a minimax lower bound for squared loss.
Problem
Kernel-based methods (KRR and general loss variants) suffer a saturation effect when the target-kernel alignment is strong; it was unclear whether this can be removed for general losses beyond squared loss.
Approach
Estimate the target within a reduced RKHS built from the top-r eigen-components of the kernel matrix (truncated KM), and bound its error via a truncated kernel complexity function; the truncation level r trades estimation complexity against approximation bias, so strongly aligned targets obtain continuously improving rates instead of plateauing.
Key results
- Under polynomial alignment with gamma>1, the truncated estimator's rate improves continuously with gamma (approaching 1/n), whereas KM plateaus at n^{-2alpha/(2alpha+1)}.
- Minimax lower bound under squared loss shows KM is minimax optimal for 1/2<=gamma<=1 but only suboptimal for gamma>1, while TKM attains the minimax rate when r is chosen appropriately.
- On wine quality with check loss, TKM achieves lower averaged MSE than KM at all three quantile levels (e.g., 0.548 vs 0.590 at tau=0.3).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a spectrally truncated kernel space instead of the full kernel space | Kernel-based method with check loss · Wine quality test set, τ=0.3 | MSE: 0.590 ± 0.027 -> 0.548 ± 0.026 | Helped |
| Use a spectrally truncated kernel space instead of the full kernel space | Kernel-based method with check loss · Wine quality test set, τ=0.5 | MSE: 0.483 ± 0.035 -> 0.454 ± 0.045 | Helped |
| Use a spectrally truncated kernel space instead of the full kernel space | Kernel-based method with check loss · Wine quality test set, τ=0.7 | MSE: 0.638 ± 0.073 -> 0.530 ± 0.046 | Helped |
| Use spectral truncation with a carefully chosen truncation level | TKM · Over-aligned regime (γ > 1), polynomial decay | learning rate: n^{-2α/(2α+1)} -> n^{-2γα/(2γα+1)} | Helped |
| Use spectral truncation | TKM · Just-aligned and weakly-aligned regimes (1/2 ≤ γ ≤ 1) | learning rate | No clear effect |
Surprising findings
- Truncation gives no benefit when alignment is weak; the optimal truncation level is r=n in the just- and weakly-aligned regimes.
Limitations
- Analysis is restricted to the fixed design setting; random design is left as future work.
- Optimal truncation level r depends on unknown alignment and must be tuned, with no data-driven selection method provided.
- Misspecified case 0<gamma<1/2 is not covered.
Experimental setup
Datasets: synthetic nonparametric quantile regression data UCI wine quality dataset
Benchmarks: synthetic nonparametric quantile regression UCI wine quality
Metrics: MSE empirical excess risk
Baselines: standard kernel-based method (KM) KRR truncated KRR (Amini et al. 2022)
Builds on: kernel ridge regression Amini et al. 2022 truncated KRR Yang et al. 2017 fixed-design kernel analysis local Rademacher complexity
Closest papers by meaning
- Generalization Bound of Gradient Flow through Training Trajectory and Data-dependent Kernel (NeurIPS 2025 · similarity 0.86)
- Spectrally Transformed Kernel Regression (ICLR 2024 · similarity 0.86)
- Joker: Joint Optimization Framework for Lightweight Kernel Machines (ICML 2025 · similarity 0.86)
- Generalization in Kernel Regression Under Realistic Assumptions (ICML 2024 · similarity 0.86)
- Improving Adaptivity via Over-Parameterization in Sequence Models (NeurIPS 2024 · similarity 0.85)
- Neural Tangent Kernels Motivate Cross-Covariance Graphs in Neural Networks (ICML 2024 · 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.