Are there any mathematical reasons that describe why "sparse models" are desirable? I am interested in better learning about why Model Sparsity (i.e. Regularization) "works"  - whether this is more due to mathematical principles or empirical results (on a case by case basis, i.e. individual datasets) .
As far as I know, here is the basic idea behind Model Sparsity:

*

*Because of the Bias-Variance Tradeoff, complex models (e.g. statistical models with many parameters) tend to overfit the training data and generalize poorly to unseen data.


*Regularization tries to fix this problem by reducing the (many) model parameters towards zero : some regularization techniques will try to push some of the model parameters more towards zero (e.g L1) , whereas other regularization techniques will try to push all the model parameters slightly towards zero (e.g. L2).


*When model parameters are pushed towards 0 - they reduce their impact and influence on the model prediction, thus effectively making a complex model into a simple model (i.e. a "sparse model").


*A "regularization penalty term" is added to the general parameter estimation equations belonging to a class of models. Thus, regularization "overrides" the initial parameter estimates from an optimization algorithm (e.g. stochastic gradient descent), and pushes the parameter estimates "away" from the initial estimates.

In statistical modelling, regularization techniques are almost considered as an integral part of the modelling process - but why do they work ?

*

*Based on some research I have done, the Bias-Variance Tradeoff does not seem to have an "exact proof" - the Bias-Variance Tradeoff is a more of a heuristic. There are some models that have many parameters and still don't overfit the data (e.g. GPT-3).


*Why does "model sparsity" (i.e. models where parameters are set to zero, the desired result and the end result of regularization) tend to benefit statistical models?


*If a non-regularized model can overfit, what exactly is "preventing" a regularized model from overfitting?
Can someone please comment or suggest some references on this? Are there any mathematical proofs that explain this - or are the beneficial effects of regularization more of an empirical result (and fundamentally only have "logical explanations" and "work" only on an "ad-hoc basis" depending on the dataset)?
Thanks!
 A: One interpretation is that regularization minimizes the "description length" of your model + data (the number of bits you'd need to encode your model + data). Sparsity is one way to do this -- obviously you need fewer bits if you have fewer parameters, but other types of regularization also accomplish this via the "bits back" argument.
But why prefer shorter descriptions? It turns out, following this idea, you can arrive at an inference procedure which is "optimal" in some very general senses. For example, if the world was deterministic, you'd only ever make a finite amount of errors in any prediction task. If the world was random, you'd only make about as many errors than if you knew its "true nature". You might find Shane Legg's primer on Solomonoff Induction helpful for a more rigorous description of this.
The fact that less regularization is sometimes better still agrees with the minimum description length principle: we're interested in minimizing the length of data and model, not just the model. Models like GPT-3 have very long descriptions, but they are powerful enough to reduce the length of the data by enough to compensate for this, and achieve an overall shorter description.
