The previous lecture introduced the RKHS norm as a measure of function complexity. A natural statistical question is how to combine this norm with a loss function to estimate an unknown regression function. We begin from familiar ridge regression and use an alternative primal-dual derivation adapted from Prof. Max Welling’s kernel ridge regression lecture note. This derivation shows that the solution depends on the observations only through inner products, which enables us to switch to a general kernel through the kernel trick. The same primal-dual idea will also reappear in support vector regression.
For clarity in this opening linear-ridge derivation, assume that the predictors and response have been centered, so we omit an intercept. Let \(\bX\in\RR^{n\times p}\) have \(\bx_i^\T\) as its \(i\)th row, let \(\by\in\RR^n\), and let \(\lambda>0\). Consider ridge regression
\[ \underset{\bbeta\in\RR^p}{\text{minimize}} \,\, \frac{1}{n} \lVert \by - \bX \bbeta \rVert^2 + \lambda \lVert \bbeta \rVert^2. \]
Introduce a new set of variables
\[ z_i = y_i - \bx_i^\T \bbeta, \]
for \(i = 1, \ldots, n\). Multiplying the objective by the positive constant \(1/(2\lambda)\) does not change its minimizer, so the original problem becomes
\[\begin{align} \underset{\bbeta, \bz}{\text{minimize}} \quad & \frac{1}{2n\lambda} \lVert \bz \rVert^2 + \frac{1}{2} \lVert \bbeta \rVert^2 \nonumber \\ \text{subject to} \quad & z_i = y_i - \bx_i^\T \bbeta, \,\, i = 1, \ldots, n. \end{align}\]
For this constrained optimization problem, we use the Lagrangian
\[ \cL(\balpha; \bz, \bbeta) = \frac{1}{2n\lambda} \lVert \bz \rVert^2 + \frac{1}{2} \lVert \bbeta \rVert^2 + \sum_{i=1}^n \alpha_i (y_i - \bx_i^\T \bbeta - z_i), \]
with \(\alpha_i \in \RR\). The primal problem can be written as
\[ \underset{\bz, \bbeta}{\min} \; \underset{\balpha}{\max} \; \cL(\balpha; \bz, \bbeta). \]
If a proposed \((\bz,\bbeta)\) violates an equality constraint, maximizing over the corresponding \(\alpha_i\) makes the Lagrangian equal to positive infinity. Therefore, the outer minimization excludes all infeasible values. By swapping the two optimizations, we obtain the dual problem
\[ \underset{\balpha}{\max} \; \underset{\bz, \bbeta}{\min} \; \cL(\balpha; \bz, \bbeta). \]
Here the objective is convex and the constraints are affine and feasible, so strong duality holds. To construct the dual objective, we first minimize with respect to \(\bbeta\) and \(\bz\) by taking derivatives and setting them to zero:
\[\begin{align} \frac{\partial \cL}{\partial z_i} &= \frac{1}{n\lambda}z_i - \alpha_i = 0, \quad i = 1, \ldots, n, \nonumber \\ \frac{\partial \cL}{\partial \bbeta} &= \bbeta - \sum_{i=1}^n \alpha_i \bx_i = \mathbf{0}. \end{align}\]
Hence,
\[ \bz=n\lambda\balpha, \qquad \bbeta=\sum_{i=1}^n\alpha_i\bx_i=\bX^\T\balpha. \]
This already shows that the ridge-regression coefficient vector lies in the span of the observed predictors. If we view the inner product as the linear kernel \(K(\bx,\bx_i)=\bx^\T\bx_i\), the predicted value at \(\bx\) is
\[\begin{align} f(\bx) &= \bx^\T \bbeta \nonumber \\ &= \sum_{i=1}^n \alpha_i \bx^\T \bx_i \nonumber \\ &= \sum_{i=1}^n \alpha_i K(\bx, \bx_i). \end{align}\]
Now, to complete the dual solution, define the linear-kernel matrix \(\bK=\bX\bX^\T\) and plug the stationary values into the Lagrangian:
\[\begin{align} g(\balpha) &= \frac{n\lambda}{2}\balpha^\T\balpha + \frac{1}{2}\balpha^\T\bK\balpha + \balpha^\T(\by-\bK\balpha-n\lambda\balpha) \nonumber \\ &= \balpha^\T\by - \frac{1}{2}\balpha^\T\bK\balpha - \frac{n\lambda}{2}\balpha^\T\balpha. \end{align}\]
Taking the derivative with respect to \(\balpha\) gives
\[ \by-\bK\balpha-n\lambda\balpha=\mathbf{0}, \]
and the dual solution is
\[ \widehat{\balpha}=(\bK+n\lambda\bI)^{-1}\by. \]
The dual objective depends on the predictors only through \(\bK\). This is the computational opening that lets us replace the linear kernel with another positive-definite kernel.
We continue with the KRR formulation without a separate intercept. For a nonlinear kernel, centering the raw predictors and response is not generally equivalent to fitting an unpenalized intercept.
For observed data \((x_i,y_i)\), \(i=1,\ldots,n\), and an RKHS \(\cH\) with reproducing kernel \(K\), kernel ridge regression solves
\[ \widehat f = \underset{f \in \cH}{\arg\min} \,\, \frac{1}{n} \sum_{i=1}^n \Big(y_i - f(x_i) \Big)^2 + \lambda \lVert f \rVert_\cH^2. \]
The general result is introduced in The Representer Theorem. For the squared-error problem here, view kernel ridge regression as another concrete example of the projection idea used for smoothing splines. We verify this special case directly using the reproducing property. Let
\[ \cS=\operatorname{span}\{K(\cdot,x_1),\ldots,K(\cdot,x_n)\}. \]
Because \(\cS\) is finite-dimensional, the Hilbert-space projection theorem gives the decomposition \(f=f_{\cS}+f_\perp\), where \(f_\perp\) is orthogonal to \(\cS\). For every observed input,
\[ f_\perp(x_i)=\langle f_\perp,K(\cdot,x_i)\rangle_\cH=0, \]
while \(\|f\|_\cH^2=\|f_\cS\|_\cH^2+\|f_\perp\|_\cH^2\). Therefore, \(f_\perp\) cannot improve the data-fitting term and can only increase the penalty. The minimizer must have the form
\[ \widehat f(\cdot)=\sum_{i=1}^n\widehat\alpha_iK(\cdot,x_i). \]
Let \(\bK\in\RR^{n\times n}\) have \(K(x_i,x_j)\) as its \((i,j)\)th element. For any coefficient vector \(\balpha\),
\[\begin{align} \left\|\sum_{i=1}^n\alpha_iK(\cdot,x_i)\right\|_\cH^2 &=\sum_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_j \langle K(\cdot,x_i),K(\cdot,x_j)\rangle_\cH \nonumber \\ &=\sum_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jK(x_i,x_j) \nonumber \\ &=\balpha^\T\bK\balpha. \end{align}\]
Hence, the finite-dimensional problem is
\[ \widehat{\balpha}\in\underset{\balpha\in\RR^n}{\arg\min} \,\, \frac{1}{n}\|\by-\bK\balpha\|^2+\lambda\balpha^\T\bK\balpha. \]
Notice that the penalty is \(\balpha^\T\bK\balpha\), not \(\balpha^\T\balpha\). It is the RKHS norm penalty, so this is not ordinary ridge regression on the kernel-section coefficients used in the first lecture.
Differentiating with respect to \(\balpha\) gives
\[ \nabla J(\balpha) =\frac{2}{n}\bK\big[(\bK+n\lambda\bI)\balpha-\by\big]. \]
The dual coefficient vector derived above,
\[ \widehat{\balpha}=(\bK+n\lambda\bI)^{-1}\by, \]
satisfies this first-order condition. Because \(\bK+n\lambda\bI\) is positive-definite when \(\lambda>0\), this dual coefficient vector is well-defined. If \(\bK\) is singular, the same fitted function may have other coefficient representations that differ by a vector in the null space of \(\bK\); the fitted function itself is unique.
For a new input \(x\), define
\[ \bk(x)=\big(K(x,x_1),\ldots,K(x,x_n)\big)^\T. \]
The KRR prediction is therefore
\[ \widehat f(x)=\bk(x)^\T(\bK+n\lambda\bI)^{-1}\by. \]
When \(K(\bx_i,\bx_j)=\bx_i^\T\bx_j\), we have \(\bK=\bX\bX^\T\). We should expect KRR to match the original ridge regression because this kernel produces a linear regression function. First, plug the linear kernel into the dual result:
\[ \widehat{\balpha}=(\bX\bX^\T+n\lambda\bI_n)^{-1}\by. \]
Using the matrix identity
\[ \bX^\T(\bX\bX^\T+c\bI_n)^{-1} =(\bX^\T\bX+c\bI_p)^{-1}\bX^\T, \]
with \(c=n\lambda\), the corresponding primal coefficient vector is
\[\begin{align} \widehat{\bbeta} &=\bX^\T\widehat{\balpha} \nonumber \\ &=(\bX^\T\bX+n\lambda\bI_p)^{-1}\bX^\T\by. \end{align}\]
Consequently, the fitted values are
\[ \widehat{\by} =\bX(\bX^\T\bX+n\lambda\bI_p)^{-1}\bX^\T\by, \]
which is exactly the ridge-regression solution under our \(1/n\) loss scaling. The penalty also maps back to the ridge form:
\[ \widehat{\balpha}^\T\bK\widehat{\balpha} =\widehat{\balpha}^\T\bX\bX^\T\widehat{\balpha} =\widehat{\bbeta}^\T\widehat{\bbeta}. \]
The fitted regression function can be written in either the primal or kernel representation:
\[\begin{align} \widehat f(\bx) &=\bx^\T\widehat{\bbeta} \nonumber \\ &=\sum_{i=1}^n\widehat\alpha_i\langle\bx,\bx_i\rangle \nonumber \\ &=\sum_{i=1}^n\widehat\alpha_iK(\bx,\bx_i). \end{align}\]
Hence, ordinary ridge regression is exactly KRR with the linear kernel.
Kernel ridge regression combines a familiar squared-error loss with the RKHS norm penalty. The kernel matrix makes the computation finite, while the choice of kernel determines the nonlinear function space. In the next application, kernel PCA will use the same kernel matrix to construct nonlinear principal components rather than a regression function.