On the Optimality of Misspecified Kernel Ridge Regression
This resolves a theoretical gap in nonparametric regression for statisticians and machine learning researchers, though it is incremental as it extends prior results to a broader range of conditions.
The paper addresses the long-standing problem of whether kernel ridge regression (KRR) is minimax optimal for all smoothness parameters in misspecified settings, and proves that KRR achieves minimax optimality for any smoothness parameter when using a Sobolev reproducing kernel Hilbert space.
In the misspecified kernel ridge regression problem, researchers usually assume the underground true function $f_ρ^{*} \in [\mathcal{H}]^{s}$, a less-smooth interpolation space of a reproducing kernel Hilbert space (RKHS) $\mathcal{H}$ for some $s\in (0,1)$. The existing minimax optimal results require $\|f_ρ^{*}\|_{L^{\infty}}<\infty$ which implicitly requires $s > α_{0}$ where $α_{0}\in (0,1)$ is the embedding index, a constant depending on $\mathcal{H}$. Whether the KRR is optimal for all $s\in (0,1)$ is an outstanding problem lasting for years. In this paper, we show that KRR is minimax optimal for any $s\in (0,1)$ when the $\mathcal{H}$ is a Sobolev RKHS.