Should gradient descent with regularization trained on training set generalize better on test set than without regularization?

Question

This is for a homework assignment, and I want to make sure that this is a result of a bug in my code and not in my understanding.

I have a sample of x vectors from a training data set $X_{train}$ with 100 points and 100 dimensions, and a set of 100 y values $Y_{train}$ that I am trying to do linear regression for. The $X_{train}$ values were generated randomly, and the $Y_{train}$ values are produced by X times $A_{true}$ plus some random noise, where $A_{true}$ is the actual solution matrix.

I use gradient descent to find the solution matrix A with some sum squared error score. Then I calculate the sum squared error using the solution A on a test data set $X_{test}$ and $Y_{test}$ (both test and training were generated from the same "true" solution matrix), and as expected, the sum squared error is worse, because of overfitting.

However, now I use gradient descent to find a solution A' but use L2 regularization, which as I understand, prevents overfitting by penalizing too many parameters. This solution A' minimizes the objective function which contains the sum squared error + lambda * ||A'||^2. However, what I am finding is that the sum squared score on A' using the test data is much worse than solution A (unless lambda < 1, in which case the results are basically the same).

So I want to make sure I understand - the point of doing the regularization is that the solution obtained on the training data should generalize better for the unseen test data and result in a lower sum squared error score than a solution obtained on training data without regularization. Is this correct?

Answer 1

How did you choose $\lambda$?

I will not go into much detail but $\lambda$ reduces what is known as effective degrees of freedom $df$.

In a simple regression $df = p = rank(X)$ and the same holds when you set $\lambda = 0$ in L2. Also for $\lambda \to \infty $ we have $df \to 0$.

To find optimal result with L2 you should test it for a number of different $df$s (usually best model has $df$ close to the original $p$) and find one with best test set score.

This may help you to play with different $df$s in R how to calculate effective degrees of freedom in ridge regression in R

Also, I think you should not expect a major improvement in overall test score with L2, so when you say "basically the same", you may want to inspect this difference closer.