Ridge & Lasso Regression

Table of Contents

1. Learning Objectives
2. Notation
3. Core Intuition
4. Ridge Regression: Derivation
5. Spectral Analysis of Ridge
6. Ridge Bias-Variance Tradeoff
7. Lasso Regression: Formulation
8. Subgradient Optimality and Sparsity
9. Coordinate Descent for Lasso
10. The Regularization Path
11. Geometric Interpretation
12. Model Selection: Choosing Lambda
13. Common Pitfalls
14. Summary
15. Exercises

Learning Objectives

1. Derive the ridge regression estimator and its relationship to SVD.
2. Quantify how ridge shrinks eigencomponents differentially.
3. Derive the subgradient optimality condition for Lasso.
4. Implement coordinate descent conceptually.
5. Explain why L1 produces exactly zero coefficients but L2 does not.
6. Describe the full regularization path as $\lambda$ varies.

Notation

• $\mathbf{X} \in \mathbb{R}^{n \times d}$ — design matrix (rows = samples)
• $\mathbf{y} \in \mathbb{R}^n$ — response vector
• $\hat{\mathbf{w}}_\lambda$ — regularized coefficient estimate
• $\sigma_1 \geq \cdots \geq \sigma_d$ — singular values of $\mathbf{X}$
• $\partial\lVert\mathbf{w}\rVert_1$ — subdifferential of L1 norm

Core Intuition

When features are collinear or $d > n$, ordinary least squares is ill-conditioned or non-unique. Ridge regression adds a quadratic penalty that "rounds" the eigenvalues of $\mathbf{X}^T\mathbf{X}$, stabilizing inversion. Lasso adds an absolute-value penalty that drives some coefficients to exactly zero, performing automatic feature selection.

Ridge Regression: Derivation

The ridge objective:

Taking the gradient and setting to zero:

The matrix $\mathbf{X}^T\mathbf{X} + \lambda\mathbf{I}$ is always invertible for $\lambda > 0$, even when $\mathbf{X}^T\mathbf{X}$ is singular.

Spectral Analysis of Ridge

Let $\mathbf{X} = \mathbf{U}\boldsymbol\Sigma\mathbf{V}^T$ with singular values $\sigma_1, \ldots, \sigma_{\min(n,d)}$. Then:

Shrinkage factor: $s_j = \frac{\sigma_j^2}{\sigma_j^2 + \lambda} \in (0, 1)$.

• Directions with large $\sigma_j$ (strong signal): $s_j \approx 1$ → barely shrunk.
• Directions with small $\sigma_j$ (noise): $s_j \approx 0$ → heavily shrunk.
• Ridge acts as a soft spectral filter.

Ridge Bias-Variance Tradeoff

Bias. $\text{Bias}(\hat{\mathbf{w}}_{\text{ridge}}) = -\lambda(\mathbf{X}^T\mathbf{X} + \lambda\mathbf{I})^{-1}\mathbf{w}^*$ where $\mathbf{w}^*$ is the true parameter.

Variance. $\text{Var}(\hat{\mathbf{w}}_{\text{ridge}}) = \sigma^2(\mathbf{X}^T\mathbf{X} + \lambda\mathbf{I})^{-1}\mathbf{X}^T\mathbf{X}(\mathbf{X}^T\mathbf{X} + \lambda\mathbf{I})^{-1}$.

The MSE is minimized at $\lambda^* > 0$ whenever $\mathbf{w}^* \neq \mathbf{0}$ — ridge always improves over OLS in terms of MSE (a consequence of the Gauss–Markov theorem not applying to MSE under bias).

Lasso Regression: Formulation

The L1 penalty is convex but not differentiable at $w_j = 0$.

Subgradient Optimality and Sparsity

The optimality condition uses the subdifferential:

where $\partial|w_j| = \begin{cases}\{+1\} & w_j > 0 \\ \{-1\} & w_j < 0 \\ [-1, +1] & w_j = 0\end{cases}$.

For coordinate $j$, let $r_j = \mathbf{x}_j^T(\mathbf{y} - \mathbf{X}_{-j}\hat{\mathbf{w}}_{-j})$ (partial residual correlation):

Sparsity mechanism: If the correlation $r_j$ between feature $j$ and the residual is smaller than $\lambda$ in magnitude, the coefficient is set to exactly zero.

Coordinate Descent for Lasso

Algorithm. Repeat until convergence:

For $j = 1, \ldots, d$:

1. Compute partial residual: $\mathbf{r}^{(j)} = \mathbf{y} - \sum_{k \neq j}\mathbf{x}_k\hat{w}_k$
2. Update: $\hat{w}_j \leftarrow S_\lambda(\mathbf{x}_j^T\mathbf{r}^{(j)}) / \lVert\mathbf{x}_j\rVert^2$

where $S_\lambda(z) = \text{sign}(z)\max(|z| - \lambda, 0)$ is the soft-thresholding operator.

Convergence. Coordinate descent converges to the global minimum because the Lasso objective is convex (but not strictly convex when $d > n$, so the solution may not be unique).

The Regularization Path

As $\lambda$ decreases from $\lambda_{\max} = \lVert\mathbf{X}^T\mathbf{y}\rVert_\infty$ (all coefficients zero) to 0:

• Coefficients enter the model one by one at breakpoints.
• The path is piecewise linear (LARS algorithm exploits this).
• Ridge path: coefficients shrink continuously, never reach zero.
• Lasso path: coefficients shrink and hit zero at finite $\lambda$.

Geometric Interpretation

Constrained form (equivalent by Lagrangian duality):

• Ridge: minimize $\lVert\mathbf{X}\mathbf{w} - \mathbf{y}\rVert^2$ subject to $\lVert\mathbf{w}\rVert_2^2 \leq t$
• Lasso: minimize $\lVert\mathbf{X}\mathbf{w} - \mathbf{y}\rVert^2$ subject to $\lVert\mathbf{w}\rVert_1 \leq t$

The L2 constraint is a sphere — the ellipsoidal loss contours touch it smoothly, rarely at coordinate axes. The L1 constraint is a diamond — contact occurs at vertices (coordinate axes), producing zeros.

Model Selection: Choosing Lambda

The optimal $\lambda$ is selected via cross-validation:

1. For a grid of $\lambda$ values $\lambda_1 > \lambda_2 > \cdots > \lambda_K$
2. For each $\lambda$, compute $K$-fold CV error
3. Select $\lambda$ minimizing CV error (or "one-SE rule": largest $\lambda$ within one standard error of minimum)

Information criteria (AIC, BIC) can also be used:

Common Pitfalls

Pitfall 1. Applying Lasso without standardizing features. L1 penalizes $|w_j|$ equally for all $j$; features on larger scales get penalized more in absolute terms.

Pitfall 2. Expecting Lasso to handle groups of correlated features. It tends to select one and zero out the rest. Use Elastic Net for grouped selection.

Pitfall 3. Comparing ridge and Lasso MSE without context. Ridge is better when all features contribute; Lasso wins when true model is sparse.

Summary

• Ridge adds $\lambda\lVert\mathbf{w}\rVert_2^2$: always has closed-form, shrinks all coefficients, stabilizes ill-conditioning.
• Lasso adds $\lambda\lVert\mathbf{w}\rVert_1$: produces sparse solutions, solved by coordinate descent.
• Sparsity comes from the geometry of the L1 ball (corners at coordinate axes).
• Both can be seen as constrained optimization with different constraint sets.
• Choose $\lambda$ via cross-validation.

Exercises

Exercise 1. Starting from the SVD $\mathbf{X} = \mathbf{U}\boldsymbol\Sigma\mathbf{V}^T$, derive equation (3) for the ridge solution.

Exercise 2. Show that ridge always reduces variance relative to OLS: $\text{tr}(\text{Var}(\hat{\mathbf{w}}_{\text{ridge}})) \leq \text{tr}(\text{Var}(\hat{\mathbf{w}}_{\text{OLS}}))$.

Exercise 3. For orthonormal $\mathbf{X}$ ($\mathbf{X}^T\mathbf{X} = \mathbf{I}$), derive the closed-form Lasso solution and compare with ridge.

Exercise 4. Prove that $\lambda_{\max} = \lVert\mathbf{X}^T\mathbf{y}\rVert_\infty$ is the smallest $\lambda$ for which $\hat{\mathbf{w}}_{\text{lasso}} = \mathbf{0}$.

Exercise 5. Show that Elastic Net can be reformulated as a Lasso on an augmented dataset.