Past exam of the mathematics course of the University of Cambridge / 2024 / iii / Paper 218 / 2

Because the columns of the design matrix are centred, ridge regression with an unpenalized intercept solvesThe normal equations give, for $\lambda >0$,The fitted values are consequentlyIf the objective is normalized by $n$, the same formulas hold after replacing $\lambda$ by $n\lambda$.

Choose $\lambda$ to minimize an estimate of out-of-sample mean squared prediction error, commonly K-fold cross-validation or a separate validation set. As $\lambda$ increases, the coefficient vector is shrunk toward zero. This generally increases bias of an estimator but decreases variance of an estimator; the minimizing value balances the two contributions in the bias-variance tradeoff. The independent test set in the question can assess the final choice, but repeatedly selecting $\lambda$ on that same set would cause data leakage.

Coordinate descent cycles through the intercept and coefficient coordinates, minimizing the convex ridge objective in one coordinate while holding the others fixed. Given current coefficients, updateFor coordinate $j$, form the partial residualand update it by the exact one-dimensional minimizerRepeated sweeps converge to the unique fitted value because the objective is a convex function; with $\lambda >0$ it is strictly convex in $\beta$.

The solid curve is the test errorand the dashed curve is the training error $n^{-1}\Vert Y-{\hat{Y}}_{\lambda }{\Vert }_2^2$. As the horizontal coordinate tends to $+\infty$, $\lambda \to \infty$, so every penalized slope tends to zero and ${\hat{Y}}_{\lambda }\to \overline{Y}1$. The two limits are thereforerespectively.

As the horizontal coordinate tends to $-\infty$, $\lambda \downarrow 0$ and the fit approaches the ordinary least squares fit $H_{0}Y$. Hence the solid curve tends to $n^{-1}\Vert Y^{\ast }-H_{0}Y{\Vert }_2^2$, which the plot shows is approximately $0.4$.

Put $f=(f(x_1),\dots ,f(x_n){)}^T$, so $Y=f+\epsilon$ and $Y^{\ast }=f+{\epsilon }^{\ast }$ with independent noise vectors having covariance matrix $I_n$. For any deterministic linear smoother $H$,whereas independence givesExpanding the first trace shows that the second expression exceeds the first by $2\mathrm{tr}(H)$, proving the identity.

For ridge regression,Its effective degrees of freedom are $\mathrm{tr}(H_{\lambda })$. Thus training error is optimistically biased for independent-copy prediction error by $2\mathrm{tr}(H_{\lambda })/n$. The graph exhibits exactly this effect: the dashed training curve keeps falling as $\lambda$ decreases, while the solid test curve eventually rises through overfitting.