On the Optimality of Misspecified Spectral Algorithms

Abstract

In the misspecified spectral algorithms 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 spectral algorithms are optimal for all $s\in (0,1)$ is an outstanding problem lasting for years. In this paper, we show that spectral algorithms are minimax optimal for any $\hat{I}{\pm }_0-{\frac{1}{\hat{I}}}^2<s<1$, where ${\hat{I}}^2$ is the eigenvalue decay rate of $\mathcal{H}$. We also give several classes of RKHSs whose embedding index satisfies $\hat{I}{\pm }_0={\frac{1}{\hat{I}}}^2$. Thus, the spectral algorithms are minimax optimal for all $s\in (0,1)$ on these RKHSs.

50 pages, 2 figures