ON THE SATURATION EFFECT OF KERNEL RIDGE REGRESSION

ON THE SATURATION EFFECT OF KERNEL RIDGE REGRESSION

2023 | Yicheng Li & Haobo Zhang, Qian Lin
This paper investigates the saturation effect in kernel ridge regression (KRR), a phenomenon where KRR fails to achieve the information-theoretic lower bound on generalization error when the regression function is sufficiently smooth. The saturation effect has been conjectured for decades, and this paper provides a rigorous proof of this conjecture. The paper begins by introducing the problem of estimating the conditional mean function $ f_{\rho}^{*}(x) = \mathbb{E}[y \mid x] $ from i.i.d. samples. Kernel ridge regression is a non-parametric method that estimates this function by solving a regularized least squares problem in a reproducing kernel Hilbert space (RKHS). The paper shows that when the regression function is in a certain interpolation space of the RKHS, the generalization error of KRR cannot achieve the information-theoretic lower bound, leading to the saturation effect. The paper then introduces the concept of interpolation spaces of RKHS and shows that when the regression function belongs to a higher-order interpolation space, the generalization error of KRR is bounded below by $ n^{-\frac{2}{2+\beta}} $, where $ \beta $ is a parameter characterizing the RKHS. This result is proven using a bias-variance decomposition, where the bias term is shown to be $ \Omega_{\mathbb{P}}(\lambda^2) $ and the variance term is shown to be $ \Omega_{\mathbb{P}}(\frac{\lambda^{-\beta}}{n}) $. These bounds are consistent with the information-theoretic lower bound and show that the saturation effect is a fundamental limitation of KRR when the regression function is sufficiently smooth. The paper also provides numerical experiments that illustrate the saturation effect, showing that the generalization error of KRR decreases at a rate of $ n^{-r} $, where $ r $ is the convergence rate. When the regression function is sufficiently smooth, the convergence rate of KRR is limited by the saturation effect, and the best possible convergence rate is $ n^{-\frac{2}{2+\beta}} $. The paper concludes by discussing the implications of the saturation effect for kernel ridge regression and other spectral regularization algorithms. It shows that the saturation effect is a fundamental limitation of KRR when the regression function is sufficiently smooth and that the saturation lower bound is a key result in the theory of kernel ridge regression. The paper also highlights the importance of understanding the saturation effect for the development of more effective regularization algorithms.This paper investigates the saturation effect in kernel ridge regression (KRR), a phenomenon where KRR fails to achieve the information-theoretic lower bound on generalization error when the regression function is sufficiently smooth. The saturation effect has been conjectured for decades, and this paper provides a rigorous proof of this conjecture. The paper begins by introducing the problem of estimating the conditional mean function $ f_{\rho}^{*}(x) = \mathbb{E}[y \mid x] $ from i.i.d. samples. Kernel ridge regression is a non-parametric method that estimates this function by solving a regularized least squares problem in a reproducing kernel Hilbert space (RKHS). The paper shows that when the regression function is in a certain interpolation space of the RKHS, the generalization error of KRR cannot achieve the information-theoretic lower bound, leading to the saturation effect. The paper then introduces the concept of interpolation spaces of RKHS and shows that when the regression function belongs to a higher-order interpolation space, the generalization error of KRR is bounded below by $ n^{-\frac{2}{2+\beta}} $, where $ \beta $ is a parameter characterizing the RKHS. This result is proven using a bias-variance decomposition, where the bias term is shown to be $ \Omega_{\mathbb{P}}(\lambda^2) $ and the variance term is shown to be $ \Omega_{\mathbb{P}}(\frac{\lambda^{-\beta}}{n}) $. These bounds are consistent with the information-theoretic lower bound and show that the saturation effect is a fundamental limitation of KRR when the regression function is sufficiently smooth. The paper also provides numerical experiments that illustrate the saturation effect, showing that the generalization error of KRR decreases at a rate of $ n^{-r} $, where $ r $ is the convergence rate. When the regression function is sufficiently smooth, the convergence rate of KRR is limited by the saturation effect, and the best possible convergence rate is $ n^{-\frac{2}{2+\beta}} $. The paper concludes by discussing the implications of the saturation effect for kernel ridge regression and other spectral regularization algorithms. It shows that the saturation effect is a fundamental limitation of KRR when the regression function is sufficiently smooth and that the saturation lower bound is a key result in the theory of kernel ridge regression. The paper also highlights the importance of understanding the saturation effect for the development of more effective regularization algorithms.
Reach us at info@study.space
Understanding On the Saturation Effect of Kernel Ridge Regression