Ridge Regression

Definition

$w_{n,\lambda }={\mathrm{argmin}}_w\frac{1}{n}\Vert Y-Xw{\Vert }^2+\lambda \Vert w{\Vert }^2$ with $\lambda >0$.

Formula

$$w_{n,\lambda }=(X^{t}X+n\lambda I_d{)}^{-1}{X}^{t}Y=V\mathrm{diag}(\frac{{\sigma }_j}{{\sigma }_j^2+\lambda })U^{t}Y(\lambda \text{ rescaled})$$

• Always unique: the eigenvalues of $X^{t}X+n\lambda I$ are $\ge n\lambda >0$.
• Shrinks the small-singular-value directions (noise). Orthogonal design: $w_j={\hat{w}}_j/(1+\lambda )$, never exactly 0.
• Larger $\lambda$: more bias, less variance. Stability ${\Delta }_{\sup }\le 2L^2/(\lambda n)$.
• Rate (fixed design, $\hat{\Sigma }\approx I$, optimal $\lambda$): $\sigma \Vert {\theta }^{\ast }\Vert \sqrt{d}/\sqrt{n}$.
• Tikhonov 1943, Hoerl and Kennard 1970; a “ridge” added to the diagonal.

Appears in

• Lecture 5, idea
• Lecture 5, Theorem 4 (ridge solution)
• Lecture 5, shrinkage and Stein’s paradox
• Lecture 5, stability
• Lecture 5, Propositions 8 and 9 (excess risk of ridge, optimal λ)
• Lecture 5, exam-style task
• Lecture 4, regularization makes the squared loss strongly convex

Related concepts

• Lasso
• Strong Convexity
• Regularization