Answers.Body: <p>To my knowledge, this is well understood in the setting with a true (sparse) linear model.</p>
  <p>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.</p>
  <p>See <a href="https://rads.stackoverflow.com/amzn/click/com/1498712169" rel="nofollow noreferrer" rel="nofollow noreferrer">https://www.amazon.com/Statistical-Learning-Sparsity-Generalizations-Probability/dp/1498712169</a> for more information.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-27T04:16:37.440Z
Answers.LastActivityDate: 2022-02-28T02:58:24.883Z
Answers.LastEditDate: 2022-02-28T02:58:24.883Z
Answers.UserDisplayName: sma
Answers.Body: <p>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 <span class="math-container">$p&gt;&gt;n$</span> as I'll mention below. In general it is a way to impose reasonable priors on the model though from a bayesian perspective.</p>
  <p>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 <a href="https://hastie.su.domains/ElemStatLearn/printings/ESLII_print12_toc.pdf" rel="nofollow noreferrer">Hastie (2001)</a>, especially section 16.2.2 titled <em>The &quot;Bet on Sparsity&quot; Principle</em>. You can think of sparsity in a bunch of different ways in addition to the number of zero weights in a linear model.</p>
  <blockquote>
  <p><span class="math-container">$L_1$</span> penalty is better suited to sparse situations, where there are few basis functions with nonzero coefficients (among all possible choices).</p>
  </blockquote>
  <p>I think the key here is that sparsity could exist in some basis, not necessarily your model weight basis.</p>
  <p>Another even more targeted mathematics heavy book would include <a href="https://hastie.su.domains/StatLearnSparsity_files/SLS.pdf" rel="nofollow noreferrer">Statistical Learning with Sparsity</a>.</p>
  <p><strong>Solution identifiability</strong>
  For example in the case where your parameter space is much larger than your number of samples (<span class="math-container">$p &gt;&gt; n$</span>), 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.</p>
  <p><strong>Domain specific knowledge</strong> 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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-23T04:57:32.417Z
Answers.LastActivityDate: 2022-02-23T04:57:32.417Z
Answers.UserDisplayName: John St. John
Body: <p>As I understand, this is the general summary of the Regularization-Overfitting Problem:</p>
  <ul>
  <li><p>The classical &quot;Bias-Variance Tradeoff&quot; 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).</p>
  </li>
  <li><p>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 &quot;complex models simpler&quot;, 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.</p>
  </li>
  <li><p>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 &quot;shrinkage&quot; effectively negates the influence of some of the parameters in complex models - and as a result, regularized models tend to have &quot;sparser&quot; solutions (i.e. contain more model parameters with values closer to 0).</p>
  </li>
  </ul>
  <p>Regarding this, I am still not sure if the mathematics behind why sparser models might result in less overfitting is clearly known.</p>
  <p>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 &quot;regularization penalty term&quot; 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.</p>
  <p><strong>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?</strong></p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-01-24T22:32:28.780Z
Comments.Text: Do not ask people to comment on something, but ask specific questions that can be answered with facts. For this reason, I removed your last part of the post.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-01-24T22:32:56.220Z
Comments.Text: What do you mean by "anecdotal evidence"? Maybe you mean "empirical evidence"? Regularisation really can help, it's not just an anecdote.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-01-24T22:32:56.677Z
Comments.Text: @ nbro: thank you for your helpful comments! I will remember this in the future!
Comments.UserDisplayName: stats_noob
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-01-25T01:28:40.513Z
Comments.Text: I guess you mean "why sparser models might *reduce* overfitting", not "*result in*"; please edit your post and, as a general remark, kindly *review* after posting.
Comments.UserDisplayName: desertnaut
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-01-25T06:09:32.363Z
Comments.Text: it basically restricts or biases your hypothesis (model) space.
Comments.UserDisplayName: SpiderRico
Tags: <neural-networks><overfitting><regularization>
Title: How does Regularization Reduce Overfitting?
UserDisplayName: stats_noob
ThreadText: # How does Regularization Reduce Overfitting?
  
  (Asked by: username_0 on 2022-01-24)
  
  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?**
  
  **Tags:** neural-networks, overfitting, regularization
  > **Comments:**
  > **username_1**: Do not ask people to comment on something, but ask specific questions that can be answered with facts. For this reason, I removed your last part of the post.  
  > **username_1**: What do you mean by "anecdotal evidence"? Maybe you mean "empirical evidence"? Regularisation really can help, it's not just an anecdote.  
  > **username_0**: @ nbro: thank you for your helpful comments! I will remember this in the future!  
  > **username_2**: I guess you mean "why sparser models might *reduce* overfitting", not "*result in*"; please edit your post and, as a general remark, kindly *review* after posting.  
  > **username_3**: it basically restricts or biases your hypothesis (model) space.  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_5 on 2022-02-23. Score: 2 | Accepted answer
  
  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)](https://hastie.su.domains/ElemStatLearn/printings/ESLII_print12_toc.pdf), 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](https://hastie.su.domains/StatLearnSparsity_files/SLS.pdf).
  
  **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 by username_4 on 2022-02-27. Score: 1
  
  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](https://rads.stackoverflow.com/amzn/click/com/1498712169) for more information.
  
  
  ---
  
  