Ridge Regression: Formulation and Solution

Hello! Welcome to our next lesson.

In our previous session, we explored the coefficient of determination ($R^2$) as a measure of model fit. We concluded by noting a significant drawback: $R^2$ tends to increase as we add more variables, regardless of their actual predictive power. This can encourage overly complex models that fit the training data's noise rather than its underlying signal—a phenomenon known as overfitting.

Today, we will directly address this problem by introducing regularization, a powerful technique for creating simpler, more robust models. Our learning outcome is to formulate L2 (Ridge) regularization for linear regression and derive its closed-form solution. This will be our first step in moving beyond OLS to build models that generalize better to unseen data.

1. The Need for Regularization: Overfitting and Multicollinearity

The OLS estimator finds the coefficients $\mathbf{\beta }$ that minimize the Residual Sum of Squares (RSS). While this is optimal under certain assumptions (as per the Gauss-Markov theorem), it can lead to problems in practice.

1. Overfitting: When a model has many parameters (i.e., many features), it can become too flexible. It may start fitting random fluctuations in the training data, leading to large estimated coefficient values. Such a model performs poorly on new data because it has learned the noise, not the true relationship.
2. Multicollinearity: As you know from your experience building regression models, features are often correlated. When features are highly correlated (high multicollinearity), the matrix ${\mathbf{X}}^T\mathbf{X}$ becomes "ill-conditioned" or nearly singular. As we saw in the derivation of the OLS solution ${\hat{\mathbf{\beta }}}_{\text{OLS}}=({\mathbf{X}}^T\mathbf{X}{)}^{-1}{\mathbf{X}}^T\mathbf{y}$, this means its inverse is unstable. Small changes in the input data can cause massive swings in the estimated coefficients, increasing their variance and making the model unreliable.

Regularization provides a way to constrain the learning algorithm to prevent these issues. Specifically, Ridge Regression tackles this by adding a penalty for large coefficient values.

2. Formulating the Ridge Regression Objective Function

As you just read, Ridge regression modifies the OLS cost function. Where OLS seeks only to minimize the sum of squared residuals, Ridge regression adds a second term: a penalty on the size of the coefficients.

The OLS cost function is:

$$J_{\text{OLS}}(\mathbf{\beta })=\text{RSS}=\sum _{i=1}^n(y_i-{\mathbf{x}}_i^T\mathbf{\beta }{)}^2=||\mathbf{y}-\mathbf{X}\mathbf{\beta }|{|}_2^2$$

Ridge regression adds an L2 penalty term, which is the squared L2-norm (Euclidean norm) of the coefficient vector, scaled by a hyperparameter $\lambda$ (lambda). The L2-norm of $\mathbf{\beta }$ is $||\mathbf{\beta }|{|}_2=\sqrt{{\sum }_{j=1}^p{\beta }_j^2}$, so the penalty is $\lambda ||\mathbf{\beta }|{|}_2^2=\lambda {\sum }_{j=1}^p{\beta }_j^2$.

The full Ridge Regression objective function is therefore:

$$J_{\text{Ridge}}(\mathbf{\beta })=||\mathbf{y}-\mathbf{X}\mathbf{\beta }|{|}_2^2+\lambda ||\mathbf{\beta }|{|}_2^2$$

• The term $||\mathbf{y}-\mathbf{X}\mathbf{\beta }|{|}_2^2$ pushes the model to fit the data well.
• The term $\lambda ||\mathbf{\beta }|{|}_2^2$ pushes the coefficients towards zero, penalizing complexity. This is often called shrinkage.
• The regularization parameter $\lambda \ge 0$ controls the trade-off.
  • If $\lambda =0$, we recover the OLS objective function.
  • As $\lambda \to \infty$, the penalty for non-zero coefficients becomes overwhelming, and the coefficients are shrunk to zero.

Note that the intercept term, ${\beta }_0$, is typically not included in the penalty. Penalizing the intercept would mean shrinking it towards zero, which is undesirable as it is simply a measure of the baseline prediction when all features are zero. In practice, data is often centered before fitting, which makes the intercept represent the mean of the target variable.

3. Deriving the Closed-Form Solution

Your goal is to derive the solution with high mathematical rigor. Fortunately, like OLS, the Ridge objective function is convex and has a unique, closed-form solution. The derivation process is very similar to what we did for OLS: expand the objective function, take its gradient with respect to $\mathbf{\beta }$, set it to zero, and solve.

Let's write the objective function in matrix form:

$$J(\mathbf{\beta })=(\mathbf{y}-\mathbf{X}\mathbf{\beta }{)}^T(\mathbf{y}-\mathbf{X}\mathbf{\beta })+\lambda {\mathbf{\beta }}^T\mathbf{\beta }$$

Now, let's watch a video that walks through the derivation step-by-step.

Let's summarize and formalize the steps from the video.

Step 1: Expand the objective function.
As we did for OLS, we expand the RSS term:

$$(\mathbf{y}-\mathbf{X}\mathbf{\beta }{)}^T(\mathbf{y}-\mathbf{X}\mathbf{\beta })={\mathbf{y}}^T\mathbf{y}-2{\mathbf{\beta }}^T{\mathbf{X}}^T\mathbf{y}+{\mathbf{\beta }}^T{\mathbf{X}}^T\mathbf{X}\mathbf{\beta }$$

So the full objective function is:

$$J(\mathbf{\beta })={\mathbf{y}}^T\mathbf{y}-2{\mathbf{\beta }}^T{\mathbf{X}}^T\mathbf{y}+{\mathbf{\beta }}^T{\mathbf{X}}^T\mathbf{X}\mathbf{\beta }+\lambda {\mathbf{\beta }}^T\mathbf{\beta }$$

Step 2: Take the gradient with respect to $\mathbf{\beta }$.
We apply the rules of matrix calculus to each term:

• ${\nabla }_{\mathbf{\beta }}({\mathbf{y}}^T\mathbf{y})=0$
• ${\nabla }_{\mathbf{\beta }}(-2{\mathbf{\beta }}^T{\mathbf{X}}^T\mathbf{y})=-2{\mathbf{X}}^T\mathbf{y}$
• ${\nabla }_{\mathbf{\beta }}({\mathbf{\beta }}^T{\mathbf{X}}^T\mathbf{X}\mathbf{\beta })=2{\mathbf{X}}^T\mathbf{X}\mathbf{\beta }$
• ${\nabla }_{\mathbf{\beta }}(\lambda {\mathbf{\beta }}^T\mathbf{\beta })={\nabla }_{\mathbf{\beta }}(\lambda {\mathbf{\beta }}^T\mathbf{I}\mathbf{\beta })=2\lambda \mathbf{I}\mathbf{\beta }=2\lambda \mathbf{\beta }$

Combining these gives the gradient:

$${\nabla }_{\mathbf{\beta }}J(\mathbf{\beta })=-2{\mathbf{X}}^T\mathbf{y}+2{\mathbf{X}}^T\mathbf{X}\mathbf{\beta }+2\lambda \mathbf{\beta }$$

Step 3: Set the gradient to zero and solve for $\mathbf{\beta }$.

$$-2{\mathbf{X}}^T\mathbf{y}+2{\mathbf{X}}^T\mathbf{X}\mathbf{\beta }+2\lambda \mathbf{\beta }=0$$

Divide by 2 and move the ${\mathbf{X}}^T\mathbf{y}$ term to the other side:

$${\mathbf{X}}^T\mathbf{X}\mathbf{\beta }+\lambda \mathbf{\beta }={\mathbf{X}}^T\mathbf{y}$$

Now, we factor out $\mathbf{\beta }$. Crucially, as shown in the video, we cannot simply add the matrix ${\mathbf{X}}^T\mathbf{X}$ and the scalar $\lambda$. We must multiply $\lambda$ by the identity matrix $\mathbf{I}$ of the same dimension ($p\times p$) to ensure the matrix addition is conformable.

$$({\mathbf{X}}^T\mathbf{X}+\lambda \mathbf{I})\mathbf{\beta }={\mathbf{X}}^T\mathbf{y}$$

Step 4: Isolate $\mathbf{\beta }$.
To isolate $\mathbf{\beta }$, we pre-multiply both sides by the inverse of $({\mathbf{X}}^T\mathbf{X}+\lambda \mathbf{I})$.
This gives us the final closed-form solution for the Ridge regression estimator:

$${\hat{\mathbf{\beta }}}_{\text{Ridge}}=({\mathbf{X}}^T\mathbf{X}+\lambda \mathbf{I}{)}^{-1}{\mathbf{X}}^T\mathbf{y}$$

The following image provides a concise visual summary of this derivation.

A key mathematical point for you: the Hessian of the Ridge objective function is $2({\mathbf{X}}^T\mathbf{X}+\lambda \mathbf{I})$. For $\lambda >0$, this matrix is guaranteed to be positive definite, which proves that our objective function is strictly convex. This ensures that the solution we found is a unique global minimum. This is also why the inverse $({\mathbf{X}}^T\mathbf{X}+\lambda \mathbf{I}{)}^{-1}$ always exists, even if ${\mathbf{X}}^T\mathbf{X}$ itself is singular.

Test your understanding!

Suppose a design matrix $\mathbf{X}$ has two columns that are perfectly collinear (e.g., one is twice the other).

1. What is the problem with computing the OLS solution ${\hat{\mathbf{\beta }}}_{\text{OLS}}=({\mathbf{X}}^T\mathbf{X}{)}^{-1}{\mathbf{X}}^T\mathbf{y}$ in this case?
2. How does the Ridge formulation with $\lambda >0$ resolve this problem mathematically?

Show answer

1. With perfect collinearity, the matrix $\mathbf{X}$ does not have full column rank. Consequently, the matrix ${\mathbf{X}}^T\mathbf{X}$ is singular (its determinant is zero) and is not invertible. Therefore, the OLS solution is not unique and cannot be computed using the standard inverse formula.
2. The Ridge formulation adds the term $\lambda \mathbf{I}$ to ${\mathbf{X}}^T\mathbf{X}$. The resulting matrix $({\mathbf{X}}^T\mathbf{X}+\lambda \mathbf{I})$ is guaranteed to be invertible for any $\lambda >0$. Mathematically, ${\mathbf{X}}^T\mathbf{X}$ is a positive semi-definite matrix, meaning its eigenvalues are $\ge 0$. With collinearity, at least one eigenvalue is exactly 0, making it singular. Adding $\lambda \mathbf{I}$ adds $\lambda$ to every eigenvalue of ${\mathbf{X}}^T\mathbf{X}$. If $\lambda >0$, all eigenvalues of the new matrix become strictly positive, making the matrix positive definite and thus invertible. This provides a stable, unique solution even in the presence of severe multicollinearity.

Conclusion

In this lesson, we have formally introduced L2 regularization as a method to address the shortcomings of OLS, particularly overfitting and instability due to multicollinearity.

Key Takeaways:

• Ridge regression adds an L2 penalty term, $\lambda ||\mathbf{\beta }|{|}_2^2$, to the OLS cost function. This penalizes large coefficient values, effectively "shrinking" them towards zero.
• The objective is to minimize $J_{\text{Ridge}}(\mathbf{\beta })=||\mathbf{y}-\mathbf{X}\mathbf{\beta }|{|}_2^2+\lambda ||\mathbf{\beta }|{|}_2^2$.
• This optimization problem has a closed-form solution, the Ridge estimator: ${\hat{\mathbf{\beta }}}_{\text{Ridge}}=({\mathbf{X}}^T\mathbf{X}+\lambda \mathbf{I}{)}^{-1}{\mathbf{X}}^T\mathbf{y}$.
• The addition of the $\lambda \mathbf{I}$ term ensures that the matrix is always invertible for $\lambda >0$, providing a stable solution even when ${\mathbf{X}}^T\mathbf{X}$ is singular.

Preview of the Next Lesson:
We have derived the Ridge estimator, but what are its properties? We've traded the OLS objective for a penalized one, which must have consequences. In the next lesson, we will explore the effect of L2 regularization on model parameters and the bias-variance trade-off. We will see that by introducing a small amount of bias into our estimates, Ridge regression can achieve a significant reduction in variance, often leading to a model with better overall predictive performance.