Reproduce “Optimal Rates for Vector-Valued Spectral Regularization Learning Algorithms” on OpenResearch

About this paper

Dimitri Meunier, Zikai Shen, Mattes Mollenhauer, Arthur Gretton, Zhu Li

The paper analyzes regression for Hilbert-space-valued outputs, comparing kernel ridge regression with spectral filters such as gradient descent and principal component regression. It links target smoothness to filter qualification. For smoothness β>2, KRR’s upper rate saturates at n^-2/(2+p), versus the lower rate n^-β/(β+p). Under domain, kernel, noise, and eigenvalue assumptions, higher-qualification methods can avoid the ceiling in upper bounds, not measured speed.

Key insights

• Vector-valued kernel ridge regression (KRR) definitively suffers from a saturation effect, with its learning rate plateauing at n^(-2 / (2+p)) when the target function's smoothness (β) exceeds 2.
• General vector-valued spectral algorithms with high or infinite qualification (ρ) can bypass KRR's saturation, effectively exploiting greater function smoothness to achieve faster, often minimax optimal, learning rates.
• The derived optimal learning rates hold for both well-specified and misspecified learning problems, providing robust theoretical guarantees for algorithms operating in infinite-dimensional output spaces.

Summary by alphaXiv.