3
$\begingroup$

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.

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ 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? $\endgroup$
    – D.W. ♦
    Commented May 16, 2017 at 22:38
  • 1
    $\begingroup$ @D.W. Is it even clear that deep learning does regularisation in the sense described in the Wikipedia page you described? $\endgroup$
    – Martin Berger
    Commented May 17, 2017 at 9:22
  • 1
    $\begingroup$ @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. $\endgroup$
    – D.W. ♦
    Commented May 18, 2017 at 19:59
  • 1
    $\begingroup$ Here is another great post on this topic: inference.vc/everything-that-works-works-because-its-bayesian-2 $\endgroup$
    – Nicholas Mancuso
    Commented May 31, 2017 at 23:20
  • 1
    $\begingroup$ @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. $\endgroup$
    – yters
    Commented Jun 2, 2017 at 14:33

1 Answer 1

Reset to default
4
$\begingroup$

Moritz Hardt's excellent blog outlines extensive research into the idea that stability in machine learning methods is related to the idea of generalization. Interestingly, we find that regularization implies stability.

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ This is interesting, in particular he states: "Our algorithm’s output shouldn’t change much if perturb one of the data points." Yet, in the case of deep learning we know that it only takes slight perturbations to change the output dramatically. Taking this post at its word, this implies deep learning does not generalize. Is that a fair assessment? If so, then this answer gives me the insight I need and I'll accept it. $\endgroup$
    – yters
    Commented May 18, 2017 at 2:06
  • 1
    $\begingroup$ @yters I don't think that is a fair assessment. In the deep learning sense, this would be equivalent to altering a single picture out of the entire data set and retraining. With that said, that post, along with its links describe enough of the mathematical frameworks to begin your own formal analysis of deep learning. $\endgroup$
    – Nicholas Mancuso
    Commented May 18, 2017 at 17:15
  • $\begingroup$ True, but wouldn't this robustness to perturbation apply not only to the training process, but the final model itself? It seems any significant discontinuity in output from slight perturbations to input fed to the final model also mean that slight changes in the training data will significantly change the final model. But, as you say, I'll need to conduct formal analysis myself. $\endgroup$
    – yters
    Commented May 18, 2017 at 17:35
  • $\begingroup$ This comment seems to be saying something similar: disq.us/p/18hvn9n $\endgroup$
    – yters
    Commented May 18, 2017 at 19:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.