Research map / Learning theory and algorithms / Kernels and regression theory

Optimal Rates for Vector-Valued Spectral Regularization Learning Algorithms

NeurIPS 2024 · Learning theory and algorithms › Kernels and regression theory · approach: Kernel ridge regression analysis · 1 citations (OpenAlex)

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.

Proves a saturation lower bound for vector-valued kernel ridge regression and upper learning rates for general vector-valued spectral algorithms (ridge, gradient descent, principal component regression) in well- and misspecified settings.

Problem

Learning rates of kernel regression with vector-valued (possibly infinite-dimensional) outputs are poorly understood: the saturation effect of ridge regression lacks matching lower bounds, and general spectral algorithms have no upper rates for vector-valued outputs, especially in the misspecified c

Approach

Derives a bias-variance lower bound showing KRR with vector-valued output saturates at rate n^{-2/(2+p)} for beta>2, and proves upper rates for general spectral filters in interpolation norms using vector-valued interpolation spaces, covering misspecified targets and bypassing saturation for gradient descent and principal component regression.

Key results

• Proves KRR with vector-valued output has lower bound c n^{-2/(2+p)} on the L2 risk for beta>=2 under noise lower bound and Hölder kernel, establishing saturation.
• Upper rates for general spectral algorithms with qualification rho: optimal for smoothness beta in (alpha-p, 2rho], with rates ||[F_lambda]-F*||_gamma^2 <= J n^{-(beta-gamma)/(beta+p)} in the regime beta+p>alpha.
• Gradient descent and principal component regression (infinite qualification) attain optimal rates without saturation; Tikhonov (rho=1) recovers state-of-the-art rates.

Surprising findings

• The authors note a previous real-valued saturation proof has issues in the treatment of bias and variance, and that p=1 is incompatible with a bounded kernel.

Limitations

• Obtaining minimax optimal rates for beta < alpha - p remains open even in the real-valued case.
• Saturation lower bound requires compact X in R^d, Hölder continuous kernel and noise bounded below.
• Purely theoretical; no empirical experiments reported.

Experimental setup

Metrics: expected squared L2 risk convergence rate in n

Baselines: kernel ridge regression vector-valued KRR minimax rates (Tikhonov) real-valued saturation lower bound (Li et al.)

Builds on: spectral algorithms (Gerfo et al. / Blanchard and Mücke) vector-valued interpolation spaces kernel ridge regression Tikhonov regularization saturation

Closest papers by meaning

• On the Saturation Effects of Spectral Algorithms in Large Dimensions (NeurIPS 2024 · similarity 0.91)
• Regularized least squares learning with heavy-tailed noise is minimax optimal (NeurIPS 2025 · similarity 0.89)
• Generalization error of spectral algorithms (ICLR 2024 · similarity 0.88)
• Spectral Preconditioning for Gradient Methods on Graded Non-convex Functions (ICML 2024 · similarity 0.87)
• A Comprehensive Analysis on the Learning Curve in Kernel Ridge Regression (NeurIPS 2024 · similarity 0.86)
• Characterizing Overfitting in Kernel Ridgeless Regression Through the Eigenspectrum (ICML 2024 · similarity 0.86)