In the misspecified spectral algorithms 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 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 $\alpha_{ 0}-\frac{ 1}{ \beta} < s < 1$, where $\beta$ is the eigenvalue decay rate of $\mathcal{ H}$. We also give several classes of RKHSs whose embedding index satisfies $ \alpha_0 = \frac{ 1}{ \beta} $. Thus, the spectral algorithms are minimax optimal for all $s\in (0,1)$ on these RKHSs.
Categories: math.ST cs.LG stat.TH