Selecting Regularization Strength

We've established that Ridge regression, for some $\lambda > 0$, provides better MSE than OLS. But the theoretical optimal λ depends on unknown quantities—the true coefficients and noise variance. This creates a practical challenge: how do we select λ using only the observed data?

This is a fundamental problem in machine learning: selecting hyperparameters that control model complexity. The regularization parameter λ is not learned from data like the coefficients β; it must be set through a separate procedure.

A naive approach (don't do this):

One might think: "Minimize training RSS over λ." But this fails catastrophically:

$$\text{RSS}(\lambda) = |\mathbf{y} - \mathbf{X}\hat{\boldsymbol{\beta}}_\lambda|_2^2$$

The training RSS is minimized at $\lambda = 0$ (OLS), because regularization only adds constraints. The OLS solution fits training data best, but (as we've seen) may generalize poorly.

The fundamental problem:

Training error is a biased estimate of test error. Models that fit training data well may have:

• Captured noise patterns specific to the training set
• Exploited coincidental correlations that don't generalize
• Overfit to idiosyncrasies of the sample

What we really want to minimize:

We want to choose λ to minimize expected test error—the error on future, unseen data:

$$\text{Test Error}(\lambda) = \mathbb{E}{(\mathbf{x}{\text{new}}, y_{\text{new}})} \left[ (y_{\text{new}} - \mathbf{x}{\text{new}}^T\hat{\boldsymbol{\beta}}\lambda)^2 \right]$$

Since we don't have access to the test distribution, we must estimate this quantity from training data. The methods below provide various approaches to this estimation.

The idea:

Cross-validation estimates test error by systematically holding out portions of the training data and measuring prediction error on the held-out portions.

K-Fold Cross-Validation procedure:

1. Randomly partition the training data into K roughly equal-sized folds: $\mathcal{F}_1, \ldots, \mathcal{F}_K$
2. For each fold $k = 1, \ldots, K$:
   • Train Ridge regression on all data except fold $k$ (using regularization λ)
   • Compute prediction error on fold $k$
3. Average the K fold errors to get the CV estimate:

$$\text{CV}K(\lambda) = \frac{1}{K} \sum{k=1}^{K} \frac{1}{|\mathcal{F}k|} \sum{i \in \mathcal{F}k} (y_i - \hat{y}{i}^{(-k)}(\lambda))^2$$

where $\hat{y}_{i}^{(-k)}(\lambda)$ is the prediction for observation $i$ using the model trained without fold $k$.

Choosing K:

• K = 5 or K = 10: Most common choices. Good balance between bias and variance of the CV estimate.
• Small K (e.g., K = 2): High bias (training sets are small), low variance, fast computation.
• Large K (e.g., K = n): Low bias, high variance, expensive computation (this is Leave-One-Out CV).

The one-standard-error rule:

Instead of selecting the λ that minimizes CV error, a more robust approach:

1. Compute CV error and its standard error for each λ
2. Find λ* that minimizes CV error
3. Select the largest λ whose CV error is within one SE of the minimum

This provides additional regularization, hedging against overfitting in hyperparameter selection.

The extreme case: K = n

Leave-One-Out Cross-Validation (LOOCV) uses each observation as its own validation fold:

$$\text{LOOCV}(\lambda) = \frac{1}{n} \sum_{i=1}^{n} (y_i - \hat{y}_{i}^{(-i)}(\lambda))^2$$

where $\hat{y}_{i}^{(-i)}$ is the prediction for observation $i$ from a model trained on all other observations.

Properties of LOOCV:

• Nearly unbiased: Training sets have size n-1, very close to full data
• High variance: Single-observation validation sets are noisy
• Deterministic: No randomness from fold assignment
• Naively expensive: Requires n model fits

The shortcut formula:

Remarkably, for linear models like Ridge regression, LOOCV can be computed without refitting n models. Using the hat matrix $\mathbf{H}_\lambda = \mathbf{X}(\mathbf{X}^T\mathbf{X} + \lambda\mathbf{I})^{-1}\mathbf{X}^T$:

$$\text{LOOCV}(\lambda) = \frac{1}{n} \sum_{i=1}^{n} \left( \frac{y_i - \hat{y}i(\lambda)}{1 - h{ii}(\lambda)} \right)^2$$

where:

• $\hat{y}i(\lambda) = [\mathbf{H}\lambda \mathbf{y}]_i$ is the fitted value from the full model
• $h_{ii}(\lambda) = [\mathbf{H}\lambda]{ii}$ is the $i$-th diagonal element of the hat matrix (leverage)

This is the PRESS statistic (Predicted Residual Error Sum of Squares), normalized.

Motivation:

Generalized Cross-Validation (GCV), introduced by Craven and Wahba (1979), is a rotation-invariant approximation to LOOCV that replaces individual leverages with their average.

The GCV formula:

$$\text{GCV}(\lambda) = \frac{\frac{1}{n} |\mathbf{y} - \hat{\mathbf{y}}_\lambda|_2^2}{\left(1 - \frac{\text{df}(\lambda)}{n}\right)^2}$$

where $\text{df}(\lambda) = \text{tr}(\mathbf{H}\lambda) = \sum{j=1}^{p} \frac{d_j}{d_j + \lambda}$ is the effective degrees of freedom.

Comparison to LOOCV:

In LOOCV, each observation has its own leverage $h_{ii}$. GCV replaces all leverages with the average leverage $\bar{h} = \text{df}(\lambda)/n$:

$$\text{GCV} \approx \frac{1}{n} \sum_{i=1}^{n} \left( \frac{y_i - \hat{y}_i}{1 - \bar{h}} \right)^2$$

This simplification makes GCV computationally trivial and often works well in practice.

Properties of GCV:

1. Rotation invariance: GCV is unchanged by orthogonal transformations of the data. This is desirable since the "best" λ shouldn't depend on coordinate choices.

2. Computational efficiency: Only requires computing RSS and trace of hat matrix—both easy for Ridge.

3. Asymptotic optimality: Under certain conditions, GCV-selected λ achieves optimal prediction risk asymptotically.

4. No tuning parameters: Unlike K-fold CV, no choice of K is needed.

The effective degrees of freedom:

The denominator involves $\text{df}(\lambda) = \text{tr}(\mathbf{H}_\lambda)$, which measures the "effective number of parameters" used by the model. As λ increases:

• $\text{df}(\lambda) \to 0$ (highly constrained model)
• The denominator $(1 - \text{df}/n)^2 \to 1$ (minimal penalty)

As λ decreases:

• $\text{df}(\lambda) \to p$ (approaching OLS)
• If $p \approx n$, the denominator becomes very small, heavily penalizing complex models.

Information criteria provide an alternative to cross-validation by explicitly penalizing model complexity.

The general form:

$$\text{IC}(\lambda) = n \log(\text{RSS}(\lambda)/n) + \text{Penalty}(\text{df}(\lambda))$$

The penalty increases with the effective degrees of freedom, discouraging overly complex models.

Akaike Information Criterion (AIC):

$$\text{AIC}(\lambda) = n \log(\text{RSS}(\lambda)/n) + 2 \cdot \text{df}(\lambda)$$

AIC aims to select the model that minimizes expected prediction error. It tends to select more complex models.

Bayesian Information Criterion (BIC):

$$\text{BIC}(\lambda) = n \log(\text{RSS}(\lambda)/n) + \log(n) \cdot \text{df}(\lambda)$$

BIC has a stronger penalty for complexity ($\log(n)$ vs 2 when $n > 7$). It aims to select the "true" model if it exists, preferring simpler models.

Corrected AIC (AICc):

When sample size is small relative to parameters, AIC tends to overfit. The corrected version:

$$\text{AICc}(\lambda) = \text{AIC}(\lambda) + \frac{2 \cdot \text{df}(\lambda)(\text{df}(\lambda) + 1)}{n - \text{df}(\lambda) - 1}$$

AICc adds an extra penalty that becomes significant when df is comparable to n.

When to use which:

• AIC: When prediction is the goal, you're willing to accept slightly more complex models
• BIC: When you believe a "true" sparse model exists and want to find it
• AICc: When n is small relative to p, as a more conservative alternative to AIC
• CV/GCV: When you want a data-driven approach without assuming a particular penalty form

The Bayesian perspective revisited:

Recall that Ridge regression corresponds to MAP estimation with a Gaussian prior: $\boldsymbol{\beta} \sim \mathcal{N}(\mathbf{0}, \tau^2 \mathbf{I})$, where $\lambda = \sigma^2/\tau^2$.

Instead of choosing λ by cross-validation, we can estimate it by maximizing the marginal likelihood—the probability of the observed data after integrating out the unknown coefficients.

The marginal likelihood:

Integrating over the prior on $\boldsymbol{\beta}$:

$$p(\mathbf{y} | \mathbf{X}, \sigma^2, \tau^2) = \int p(\mathbf{y} | \mathbf{X}, \boldsymbol{\beta}, \sigma^2) p(\boldsymbol{\beta} | \tau^2) d\boldsymbol{\beta}$$

For the Gaussian model, this integral is tractable:

$$\mathbf{y} | \mathbf{X}, \sigma^2, \tau^2 \sim \mathcal{N}(\mathbf{0}, \sigma^2 \mathbf{I}_n + \tau^2 \mathbf{X}\mathbf{X}^T)$$

Log marginal likelihood:

$$\log p(\mathbf{y} | \mathbf{X}, \sigma^2, \tau^2) = -\frac{n}{2}\log(2\pi) - \frac{1}{2}\log|\mathbf{C}| - \frac{1}{2}\mathbf{y}^T\mathbf{C}^{-1}\mathbf{y}$$

where $\mathbf{C} = \sigma^2 \mathbf{I} + \tau^2 \mathbf{X}\mathbf{X}^T$.

Empirical Bayes estimation:

Maximize the (log) marginal likelihood over $\sigma^2$ and $\tau^2$ (or equivalently, over $\sigma^2$ and $\lambda = \sigma^2/\tau^2$):

$$(\hat{\sigma}^2, \hat{\tau}^2) = \arg\max_{\sigma^2, \tau^2} \log p(\mathbf{y} | \mathbf{X}, \sigma^2, \tau^2)$$

Then use $\hat{\lambda} = \hat{\sigma}^2/\hat{\tau}^2$ as the regularization parameter.

Connection to Restricted Maximum Likelihood (REML):

The marginal likelihood approach is related to REML estimation used in mixed-effects models. Both aim to estimate variance components (here, $\sigma^2$ and $\tau^2$) in a principled way.

Advantages of Empirical Bayes:

• Provides a principled estimate of the noise variance $\sigma^2$ alongside λ
• Coherent probabilistic interpretation
• Can be extended to more complex prior structures

Disadvantages:

• More complex to compute than CV/GCV
• Assumes Gaussian errors (less robust to outliers)
• May overfit hyperparameters in small samples ("double dipping")

Having covered multiple λ selection methods, here's a practical workflow for applying Ridge regression: