On the Optimality of Misspecified Spectral Algorithms
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916377959333888 |
|---|---|
| author | Zhang, Haobo Li, Yicheng Lin, Qian |
| author_facet | Zhang, Haobo Li, Yicheng Lin, Qian |
| contents | In the misspecified spectral algorithms problem, researchers usually assume the underground true function $f_ρ^{*} \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_ρ^{*}\|_{L^{\infty}}<\infty$ which implicitly requires $s > α_{0}$ where $α_{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 $α_{0}-\frac{1}β < s < 1$, where $β$ is the eigenvalue decay rate of $\mathcal{H}$. We also give several classes of RKHSs whose embedding index satisfies $ α_0 = \frac{1}β $. Thus, the spectral algorithms are minimax optimal for all $s\in (0,1)$ on these RKHSs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2303_14942 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | On the Optimality of Misspecified Spectral Algorithms Zhang, Haobo Li, Yicheng Lin, Qian Statistics Theory Machine Learning In the misspecified spectral algorithms problem, researchers usually assume the underground true function $f_ρ^{*} \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_ρ^{*}\|_{L^{\infty}}<\infty$ which implicitly requires $s > α_{0}$ where $α_{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 $α_{0}-\frac{1}β < s < 1$, where $β$ is the eigenvalue decay rate of $\mathcal{H}$. We also give several classes of RKHSs whose embedding index satisfies $ α_0 = \frac{1}β $. Thus, the spectral algorithms are minimax optimal for all $s\in (0,1)$ on these RKHSs. |
| title | On the Optimality of Misspecified Spectral Algorithms |
| topic | Statistics Theory Machine Learning |
| url | https://arxiv.org/abs/2303.14942 |