# How much does regularization prevent overfitting?

I've been curious why machine learning algorithms with high VC dimension, such as XGBoost and deep learning, do well in practice. The answer appears to be regularization significantly restricting the parameter space, but the only justifications I've seen are references to Occam's razor.

Is there quantitative/theoretical understanding of how much regularization can prevent overfitting in a model?

Background: I've taken a course in machine learning and covered the theory behind regularization and a couple techniques, such as lasso and ridge regression. I understand the principle that regularization can reduce the VC dimension by minimizing or zeroing weights in the model.

But, that principle does not clarify in my mind whether regularization is adequate to counteract the high VC dimension in models used by XGBoost and deep learning.

I am asking for some sort of quantitative theory that provides justification that even with high VC dimension regularization can reduce the dimensionality enough to provide a decent guarantee of generalization.

Alternatively, providing a method I can use to figure this out myself is also acceptable.

• What research and reading have you done? There's lots written on regularization and its purpose, including en.wikipedia.org/wiki/Regularization_%28mathematics%29 and stats.stackexchange.com/q/4961/2921 and many more. There seems to be little point in us repeating standard material. This site works best if you do a significant amount of research before asking, and show us in the question what you've found so far. Why are you unsatisfied the references to Occam's razor? – D.W. May 16 '17 at 22:38
• @D.W. Is it even clear that deep learning does regularisation in the sense described in the Wikipedia page you described? – Martin Berger May 17 '17 at 9:22
• @yters, as far as I can tell, it's an active area of research. There's a later paper responding to that one, openreview.net/pdf?id=rJv6ZgHYg, which seems to suggest that regularization might indeed be playing a role in explaining the small generalization error. – D.W. May 18 '17 at 19:59
• Here is another great post on this topic: inference.vc/everything-that-works-works-because-its-bayesian-2 – Nicholas Mancuso May 31 '17 at 23:20
• @NicholasMancuso, great article. If gradient descent is the magic that makes deep learning generalize, then deep learning itself is not special, since gradient descent is applied to many machine learning models. – yters Jun 2 '17 at 14:33

Formally, given observations $S = (z_1, \dotsc, z_n)$ and algorithm $A$, stability is defined as the expected difference between the risk and empirical risk $$\mathbb{E}[R - R_e] = \Delta,$$ where $R_e = \ell(z, S) = \frac{1}{n} \sum_i \ell(z_i, A(S))$ is the empirical risk and $R = \mathbb{E}_{z \sim D}[\ell(z, A(S))]$ is the risk.
The post details how to obtain bounds on $\Delta$ and its implications much better than I ever can. I highly recommend reading that post along with all of his other posts.
A much more practical argument is that regularization constrains the problem space to a very specific subset of models; namely, regularization methods can be recast as constrained optimization where $\|\beta\|_p \leq c$ for some value of $p$. This is equivalent to using prior knowledge about the problem and forcing the solution to be within some constrained space.