On the Optimality of Misspecified Kernel Ridge Regression

Abstract

In the misspecified kernel ridge regression problem, researchers usually assume the underground true function $f_{\ddot{I}}{}^{\ast }\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 $\Vert f_{\ddot{I}}{}^{\ast }{\Vert }_{L^{\infty }}<\infty$ which implicitly requires $s>\hat{I}{\pm }_0$ where $\hat{I}{\pm }_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.

23 pages, 6 figures, The Fortieth International Conference on Machine Learning. arXiv admin note: substantial text overlap with arXiv:2303.14942