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.
翻译:----
关于不正确谱算法的最优性
翻译摘要:
在不正确的谱算法问题中,研究人员通常假定地下真实函数 $f_{\rho}^{*} \in [\mathcal{H}]^{s}$,其中$\mathcal{H}$是再生核希尔伯特空间(RKHS)的一个较少平滑的插值空间,对于某些 $s\in (0,1)$。现有的极小值最优结果需要 $\|f_{\rho}^{*}\|_{L^{\infty}}<\infty$,这隐含着 $s > \alpha_{0}$,其中 $\alpha_{0}\in (0,1)$ 是嵌入指数,这是一个取决于$\mathcal{H}$的常数。谱算法是否对于所有 $s\in(0,1)$ 都是最优的是一个长期存在的问题。在本文中,我们展示了谱算法对于任何 $\alpha_{0}-\frac{1}{\beta} < s < 1$ 最小值最优,其中$\beta$是$\mathcal{H}$的特征值衰减率。我们还给出了几类嵌入指数满足 $ \alpha_0 = \frac{1}{\beta} $ 的RKHS。因此,在这些RKHS 上,谱算法在所有 $s\in (0,1)$ 上都是最小值最优的。