Ridge Regression and Generalized Cross-Validation

Ridge regression is least squares with a $l_2$ penalty on the weights.

OLS solves:

\[\underset{W}{\min} \Vert XW - Y\Vert^2_F\]

with normal equation

\[X^\intercal X W = X^\intercal Y\]

where if $X^\intercal X$ is invertible,

\[W = (X^\intercal X)^{-1} X^\intercal Y\]

Ridge instead solves

\[\underset{W}{\min} \Vert XW - Y\Vert^2_F + \lambda \Vert W\Vert^2_F\]

Taking the derivative gives

\[(X^\intercal X + \lambda I)W = X^\intercal Y\]

so

\[W_\lambda = (X^\intercal X + \lambda I)^{-1} X^\intercal Y\]

The $\lambda I$ term makes system better conditioned and shrinks the learned weights. Not ethat $\lambda = 0$, ridge reduces to OLS.

NOTE In practice, we usualyl don't form inverse explicitly. Instead of computing \[W = A^{-1}B\]

we solve,

\[AW = B\]

Centering

If the model should include an intercept, we center both $X$ and $Y$.

\[X_c = X - \mu_X, \quad Y_c = Y - \mu_Y\]

Fitting ridge on the centered data:

\[\underset{W}{\min} \Vert X_c W - Y_c\Vert_F^2 + \lambda \Vert W \Vert^2_F\]

then predict

\[\hat{Y} = (X_\text{test} - \mu_X) W + \mu_Y\]

or equivalent to fitting:

\[\hat{Y} = X_\text{test}W + b \quad \text{with} \quad b = \mu_Y - \mu_X W\]

SVD View

Let

\[X = USV^\intercal\]

be the singular value decomposition of $X$ where the singular values are $s_i$.

singular value vs eigenvalue
An eigenvalue tells you how much a matrix stretches a vector whose direction stays the same: \[Av = \lambda v\]
  • represent magnitude of scaling along invariant eigenvector direction
  • Only square matrices, can be real or complex numbers.
  • Found via the characteristic polynomial \(\det(A - \lambda I) = 0\)

A singular value tells you how much a matrix stretches space along its main input directions, even if directions rotate or the matrix is not square:

\[Au_i = \sigma_i u_i\]
  • Always real, non-negative numbers
  • Found via the square roots of the eigenvalues of the Gram matrix $A^\intercal A$
  • Maps input directions v to output directions u
NOTE If a square matrix is symmetric, the singular values are simply the absolute values of the eigenvalues

Then the ridge can be written as

\[W_\lambda = V \text{diag}\Big(\frac{s_i}{s_i^2 + \lambda}\Big)U^\intercal Y\]

which essentially shrinks directions according to their singular values. Hence, directions with large $s_i$ are trusted more. [TODO: prove]

Our fitted predictions can thus be written as $\hat{Y_\lambda} = XW_\lambda = H_\lambda Y$ where

\[H_\lambda = X(X^\intercal X + \lambda I)^{-1} X^\intercal\]

Using SVD,

\[ \begin{align} H_\lambda &= X V \text{diag}\Big(\frac{s_i}{s_i^2 + \lambda}\Big)U^\intercal \nonumber \\ &= US\text{diag}\Big(\frac{s_i}{s_i^2 + \lambda}\Big)U^\intercal \nonumber \\ &=U\text{diag}\Big(\frac{s_i^2}{s_i^2 + \lambda}\Big)U^\intercal \nonumber \end{align} \]

meaning,

\[\frac{s_i^2}{s_i^2 + \lambda}\]

is the prediction shrinkage factor in singular direction $i$.

Effective Degrees of Freedom

For OLS, model complexity is roughly the number of fitted parameters or active dimensions. For ridge, dimensions are not simply kept or removed as they are partially shrunk.

The effective degrees of freedom (defined as trace of $\hat{H}$) are

\[\text{df}(\lambda) = \text{tr}(H_\lambda) = \sum_i \frac{s_i^2}{s_i^2 + \lambda}\]
  • Small $\lambda$ gives high df and behaves like least squareas. At $\lambda = 0$, $\text{df}(0) = \text{rank}(X)$.
  • At Large $\lambda$ gives low df and behaves like a smoothed model. $\lambda = \infty$ has $\text{df}(0) = 0$ or it just predicts mean target.

Generalized Cross-Validation

Generalized cross-validation, or GCV, is a way to choose $\lambda$ without using a separate validation split.

For each candidate $\lambda$, compute

\[\text{GCV}(\lambda) = \frac{\frac{1}{n} \Vert Y - \hat{Y_\lambda}\Vert_F^2}{\Big(1 - \frac{\text{df}(\lambda)}{n}\Big)^2}\]
  • The numerator is the training residual error
  • The denominator penalizes model complexity through the effective degrees of freedom

[TODO: why]

IMPORTANT: A small $\lambda$ may have low training error but high complexity. A large $\lambda$ may be too biased. GCV chooses the $\lambda$ with the best estimated out-of-sample behavior.

Why SVD Makes GCV Efficient

Trying many $\lambda$ values requires solving a new ridge system each time:

\[(X^\intercal X + \lambda I) W = X^\intercal Y\]

With SVD, the expensive decomposition $X = USV^\intercal$ is done only once. Each subsequent $\lambda$ only changes the diagonal shrinkage factors

\[\frac{s_i^2}{s_i^2 + \lambda} \text{ and } \frac{s_i}{s_i^2 + \lambda}\]

whcih becomes a cheap sweep over scalar shrinkage factors.

[TODO: Frisch–Waugh–Lovell,]