Can a regularization harm more than help in the situation of a huge over-fit? I fit a regression model on a data set and get some in-sample RMSE. I wanted to know, how likely is that I get this good RMSE (or even better) under assumptions that there are no patterns in the data.
To answer this question, I take my real targets, resample from them, and replace the real targets by "fake" targets. By doing this I destroy any potential dependency on features.
To make it simple to understand, you can imagine that instead of a resampling I just randomly permute all the targets. So, obviously there is no dependency on features.
Now, I use my "fake" data set to fit the model again. I do it many times and what I see is that I never get results that are as good as on the real data set.
So, my interpretation is that the model fit some pattern (signal) on the real data set and therefore it is always better than on a fake (randomized) data set.
Now I do the same but with a gradual increase of the regularization parameter. What I see, is that difference between the performance in real and fake data sets gets smaller and smaller.
So, I assume that the regularization makes the model less sensitive to noise (which is good) but, at the same time, it makes the model less sensitive to signal (pattern).
So, now I come to my question: Can a regularization harm more than help in the situation of a huge over-fit?
What I mean by that, is that by a regularization model becomes less sensitive to noise but also it becomes much more insensitive to signal!

If you increase the regularisation parameter too much, the model will ignore the data completely and the norm of the weights will be forced arbitrarily close to zero". This ought to be the solution you would asymptotically get modelling fake targets, as there is no correlation between the attributes and the targets. Making generalisation worse by regularising too much (or by using a model that is too structurally simple, e.g. linear regression for a non-linear problem) is known as "under-fitting".
The key to regularisation lies in tuning the regularisation parameter to optimise out-of-sample performance without over- or under-fitting.  I tend to tune the regularisation to minimise the leave-one-out error (because it is cheap for many useful models) or use a Bayesian approach.
The regularisation parameter is equivalent to placing a bound on the magnitude of the weights (see my answer to this question).  This creates a nested set of models of increasing complexity as the bound is made looser (by reducing the regularisation parameter).  If you increase the bound slightly, the model can implement all of the functions it previously could, plus a few more.  Thus the value of the regularisation parameter is an indication of the complexity of the model class that you are fitting to the data.  In tuning the parameter, you are matching the complexity of the model to suit the complexity of the learning problem.  You don't want it to be too complex, but you don't want it to be too simple either.
