Regularized linear vs. RKHS-regression

Question

I'm studying the difference between regularization in RKHS regression and linear regression, but I have a hard time grasping the crucial difference between the two.

Given input-output pairs $(x_i,y_i)$, I want to estimate a function $f(\cdot)$ as follows \begin{equation}f(x)\approx u(x)=\sum_{i=1}^m \alpha_i K(x,x_i),\end{equation} where $K(\cdot,\cdot)$ is a kernel function. The coefficients $\alpha_m$ can either be found by solving \begin{equation} {\displaystyle \min _{\alpha\in R^{n}}{\frac {1}{n}}\|Y-K\alpha\|_{R^{n}}^{2}+\lambda \alpha^{T}K\alpha},\end{equation} where, with some abuse of notation, the $i,j$'th entry of the kernel matrix $K$ is ${\displaystyle K(x_{i},x_{j})} $. This gives \begin{equation} \alpha^*=(K+\lambda nI)^{-1}Y. \end{equation} Alternatively, we could treat the problem as a normal ridge regression/linear regression problem: \begin{equation} {\displaystyle \min _{\alpha\in R^{n}}{\frac {1}{n}}\|Y-K\alpha\|_{R^{n}}^{2}+\lambda \alpha^{T}\alpha},\end{equation} with solution \begin{equation} {\alpha^*=(K^{T}K +\lambda nI)^{-1}K^{T}Y}. \end{equation}

What would be the crucial difference between these two approaches and their solutions?

Answer 1

As you probably have noticed when writing down the optimization problems, the only difference in the minimization is which Hilbert norm to use for penalization. That is, to quantify what 'large' values of $\alpha$ are for penalization purposes. In the RKHS setting, we use the RKHS inner product, $\alpha^tK\alpha$, whereas ridge regression penalizes with respect to the Euclidean norm.

An interesting theoretical consequence is how each method effects the spectrum of the reproducing kernel $K$. By RKHS theory, we have that $K$ is symmetric positive definite. By the spectral theorem, we can write $K = U^tDU$ where $D$ is the diagonal matrix of eigenvalues and $U$ is the orthonormal matrix of eigenvectors. Consequently, in the RKHS setting, \begin{align} (K+\lambda nI)^{-1}Y &= [U^t(D+\lambda nI)U]^{-1}Y\\ &= U^t[D+\lambda nI]^{-1}UY. \end{align} Meanwhile, in the Ridge regression setting, note that $K^tK=K^2$ by symmetry, \begin{align} (K^2+\lambda nI)^{-1}KY &= [U^t(D^2+\lambda nI)U]^{-1}KY\\ &= U^t[D^2+\lambda nI]^{-1}UKY\\ &= U^t[D^2+\lambda nI]^{-1}DUY\\ &= U^t[D+\lambda nD^{-1}]^{-1}UY. \end{align} Let the spectrum of $K$ be $\nu_1,\ldots,\nu_n$. In RKHS regression, the eigenvalues are stabilized by $\nu_i\rightarrow\nu_i+\lambda n$. In Ridge regression, we have $\nu_i\rightarrow \nu_i + \lambda n/\nu_i$. As a result, RKHS uniformly modifies the eigenvalues while Ridge adds a larger value if the corresponding $\nu_i$ is smaller.

Depending on the choice of kernel, the two estimates for $\alpha$ may be close or far from each other. The distance in the operator norm sense will be \begin{align} \|{\alpha_\text{RKHS}-\alpha_\text{Ridge}}\|_{\ell^2} &= \|{ A_\text{RKHS}Y-A_\text{Ridge}Y }\|_{\ell^2}\\ &\le \|[D+\lambda nI]^{-1}-[D+\lambda n D^{-1}]^{-1}\|_\infty\|Y\|_{\ell^2}\\ &\le \max_{i=1,\ldots,n}\left\{| (\nu_i+\lambda n)^{-1} - (\nu_i+\lambda n/\nu_i)^{-1} |\right\}\|Y\|_{\ell^2}\\ &\le \max_{i=1,\ldots,n}\left\{ \frac{\lambda n|1-\nu_i|}{(\nu_i+\lambda n)(\nu_i^2+\lambda n)} \right\}\|Y\|_{\ell^2}\\ \end{align} However, this is still bounded for a given $Y$, so your two estimators cannot be arbitrarily far apart. Hence, if your kernel is close to the identity, then there will mostly likely be little difference in the approaches. If your kernels are vastly different, the two approaches can still lead to similar results.

In practice, it is hard to say definitively if one is better than the other for a given situation. As we are minimizing with respect to the squared error when representing the data in terms of the kernel function, we are effectively choosing a best regression curve from the corresponding Hilbert space of functions. Hence, penalizing with respect to the RKHS inner product seems to be the natural way to proceed.