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

With the normalization used in the question, ridge regression solvesDifferentiating with respect to $\mu$ and using the centered columns $X^{T}1=0$ gives $\hat{\mu }=\overline{Y}$. The normal equation for $\beta$ issoThe push-through identity then gives the equivalent dual form

Fix $j\in A$ and writeThe matrix $R$ is positive definite. Applying the Sherman–Morrison formula to $R+X_j{X}_j^T$ yields

For the active set $A_k$, maintainThe initial $n\times n$ matrix inverse costs $O(n^3)$. At step $k$, compute $v_k=M_k^{-1}Y$ in $O(n^2)$ operations and all active ridge coefficients $X_{A_k}^T{v}_k$ in $O(|A_k|n)$ operations; their smallest absolute value determines $j_k$.

After deleting $j_k$,Part b ensures that the denominator in the Sherman–Morrison formula is positive, and the rank-one downdatecosts $O(n^2)$. Summing over the $p$ steps givesSince $p\ge n$, both earlier terms are bounded by $O(p^{2}n)$, proving the claimed computational complexity within computational complexity theory.