Past exam of the mathematics course of the University of Cambridge / 2022 / iii / Paper 205 / 1 / Solution

With the normalization used in the question, kernel ridge regression minimizesThe representer theorem and the normal equations give the fitted-value vector

Let ${\mathcal{H}}_X=\mathrm{span}\{k(x_i,\cdot ):1\le i\le n\}$ and let $\bar{f}$ be the orthogonal projection of $f^0$ onto this space. The reproducing property makes $f^0(x_i)=\bar{f}(x_i)$ for every $i$. Writing $\bar{f}={\sum }_j{\alpha }_{j}k(x_j,\cdot )$ gives

Conditionally on $X$, the covariance matrix of the fitted vector isSince the eigenvalues of $K$ are $n{\hat{\mu }}_i$, the average conditional variance isFor $t\ge 0$,Taking $t=n{\hat{\mu }}_i/\lambda$ and adding the supplied squared-bias bound gives

Because $\hat{\lambda }$ minimizes this conditional upper bound, its expected value is at most the expected bound at any deterministic $\lambda =n\gamma$. Using the assumed eigenvalue comparison,