On the Optimality of Misspecified Kernel Ridge Regression

Haobo Zhang, Yicheng Li, Weihao Lu, Qian Lin
Proceedings of the 40th International Conference on Machine Learning, PMLR 202:41331-41353, 2023.

Abstract

In the misspecified kernel ridge regression problem, researchers usually assume the underground true function fρ[H]s, a less-smooth interpolation space of a reproducing kernel Hilbert space (RKHS) H for some s(0,1). The existing minimax optimal results require 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.

Cite this Paper


BibTeX
@InProceedings{pmlr-v202-zhang23x, title = {On the Optimality of Misspecified Kernel Ridge Regression}, author = {Zhang, Haobo and Li, Yicheng and Lu, Weihao and Lin, Qian}, booktitle = {Proceedings of the 40th International Conference on Machine Learning}, pages = {41331--41353}, year = {2023}, editor = {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan}, volume = {202}, series = {Proceedings of Machine Learning Research}, month = {23--29 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v202/zhang23x/zhang23x.pdf}, url = {https://proceedings.mlr.press/v202/zhang23x.html}, abstract = {In the misspecified kernel ridge regression problem, researchers usually assume the underground true function $f_{\rho}^{\star} \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 $\left\Vert f_{\rho}^{\star} \right \Vert_{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.} }
Endnote
%0 Conference Paper %T On the Optimality of Misspecified Kernel Ridge Regression %A Haobo Zhang %A Yicheng Li %A Weihao Lu %A Qian Lin %B Proceedings of the 40th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2023 %E Andreas Krause %E Emma Brunskill %E Kyunghyun Cho %E Barbara Engelhardt %E Sivan Sabato %E Jonathan Scarlett %F pmlr-v202-zhang23x %I PMLR %P 41331--41353 %U https://proceedings.mlr.press/v202/zhang23x.html %V 202 %X In the misspecified kernel ridge regression problem, researchers usually assume the underground true function $f_{\rho}^{\star} \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 $\left\Vert f_{\rho}^{\star} \right \Vert_{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.
APA
Zhang, H., Li, Y., Lu, W. & Lin, Q.. (2023). On the Optimality of Misspecified Kernel Ridge Regression. Proceedings of the 40th International Conference on Machine Learning, in Proceedings of Machine Learning Research 202:41331-41353 Available from https://proceedings.mlr.press/v202/zhang23x.html.

Related Material