How does Regularization Reduce Overfitting?

Question

As I understand, this is the general summary of the Regularization-Overfitting Problem:

• The classical "Bias-Variance Tradeoff" suggests that complicated models (i.e. models with more parameters, e.g. neural networks with many layers/weights) are able to well capture complicated patterns in data (i.e. low bias) but are unable to generalize well to unseen data (i.e. high variance). On the other hand, simpler models are able to generalize better to unseen data (i.e. low variance), but unable to capture complex patterns in data (i.e. high bias).

• Regularization tries to navigate this compromise by attempting to improve the ability of complicated models to generalize to unseen data. Regularization does this by making "complex models simpler", by strategically reducing the number of parameters in complex models such that they maintain their ability to capture complexity in the data but also generalize to unseen data.

• Regularization does this by bringing some of the model parameters towards 0 (L1 Regularization) or by bringing many of the model parameters somewhat towards 0 (L2 Regularization). This "shrinkage" effectively negates the influence of some of the parameters in complex models - and as a result, regularized models tend to have "sparser" solutions (i.e. contain more model parameters with values closer to 0).

Regarding this, I am still not sure if the mathematics behind why sparser models might result in less overfitting is clearly known.

The way I currently see things, Regularization seems to be more of a general heuristic : Countless evidence shows that models overfit less when you add a "regularization penalty term" to the model's Loss Function - and thus deliberately choose model parameters corresponding to a region of the Loss Function that is situated away from the true minimum point. Mathematically, I can understand how this happens.

But are there any mathematical justifications that suggest a sparser model based on a regularized solution is less likely to overfit data compared to a non-regularized solution - or is this still based on heuristics and anecdotal evidence? Do we have any insights as to how the Mathematics of Regularization acts to prevent Overfitting?

Answer 1

I think different mathematical explanations exist for different situations where regularization is useful. The importance of regularization varies by problem as well. It is absolutely necessary when $p>>n$ as I'll mention below. In general it is a way to impose reasonable priors on the model though from a bayesian perspective.

I'm going to put together a quick answer that I hope is somewhat satisfactory. I don't think it is exactly what you are going after though. At a high level I would recommend skimming Hastie (2001), especially section 16.2.2 titled The "Bet on Sparsity" Principle. You can think of sparsity in a bunch of different ways in addition to the number of zero weights in a linear model.

$L_1$ penalty is better suited to sparse situations, where there are few basis functions with nonzero coefficients (among all possible choices).

I think the key here is that sparsity could exist in some basis, not necessarily your model weight basis.

Another even more targeted mathematics heavy book would include Statistical Learning with Sparsity.

Solution identifiability For example in the case where your parameter space is much larger than your number of samples ($p >> n$), you have an identifiability problem. Infinite numbers of solutions exist, so picking one with small total weight of parameters is just as justified as any other, but perhaps more plausible in most situations from aesthetics. Without regularization in this setting, you would have instability issues where different equally good solutions could be chosen, perhaps based on random initial conditions.

Domain specific knowledge In many cases, you wouldn't expect all of your parameters to be meaningful. Enforcing sparsity will mathematically limit the solution space to one with more zeros, as you point out, or in general a solution space with a fewer number of underlying basis functions being involved in the data generation. In many domains there are a smallish number of factors that are causing a large number of observed variables to be changed, so regularization is imposing that kind of a constraint onto your model. Since the remainder of the variables are not real, or would otherwise make use of too many basis functions to represent your task, you are helping the model out by providing this useful piece of information. There are many extensions on this. For example if you know that your features are spatially correlated you could add in a fused lasso penalty, etc. The rationale here mathematically is probably something along the lines of including more noise terms in your solution results in a lower likelihood of generalizing.

Answer 2

To my knowledge, this is well understood in the setting with a true (sparse) linear model.

In high dimensional regimes and when the true model is sparse, a regularized solution is less likely to overfit the data because with high probability, we will obtain the true support of our model. This follows from the equivalence of L1 solution to solving L0 solution, when the Restricted nullspace property (RNSP) holds. A sufficient condition for RNSP is the restricted isometry property (RIP). Under a subgaussian analysis, one can see RIP is satisfied with high probability meaning solving lasso obtains our true support. Analysis gets more complex in a noisy setting, but intuition can be built from the noiseless case. Low l2 error of coefficients follows with high probability as well.

See https://www.amazon.com/Statistical-Learning-Sparsity-Generalizations-Probability/dp/1498712169 for more information.