On the Optimality of Misspecified Kernel Ridge Regression
Haobo Zhang Yicheng Li Weihao Lu Qian Lin
In the misspecified kernel ridge regression problem, researchers usually
assume the underground true function $f_{\rho}^{*} \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_{\rho}^{*}\|_{L^{\infty}}<\infty$ which implicitly requires $s >
\alpha_{0}$ where $\alpha_{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.