Past exam of the mathematics course of the University of Cambridge / 2024 / iii / Paper 205 / 5

The kernel ridge regression estimator isBy the representer theorem, ${\hat{f}}_{\lambda }={\sum }_{j=1}^n{\alpha }_{j}k(x_j,\cdot )$. If $K_{ij}=k(x_i,x_j)$, substitution and differentiation giveThusThe matrix $H_{\lambda }$ is the kernel-ridge hat matrix.

The leave-one-out residual identity for a linear smoother, obtained from the block matrix inverse or the Sherman–Morrison formula, isHence

Compute once the spectral decomposition $K=U\mathrm{diag}(d_1,\dots ,d_n)U^T$ in $O(n^3)$ operations and the vector $U^{T}Y$ in $O(n^2)$. For each ${\lambda }_{\ell }$, setThen computeBoth calculations take $O(n^2)$ operations per tuning parameter, after which the displayed leave-one-out formula costs $O(n)$. All $L$ scores therefore require $O(n^3+L{n}^2)$ operations.