Answers.Body: <blockquote>
    <p>But, the literature (i.e. Learning from Data) states that VC gives a loose bound and that in real applications, learning models with lower VC dimension tend to generalize better than those with higher VC dimension.</p>
  </blockquote>
  
  <p>It's true that people often use techniques such as <em>regularisation</em> to avoid over-parametrized models. However, I think it's dangerous to say that, in real applications, those models are really generalizing better, given that you're typically assessing their generalization ability by using a finite validation dataset (possibly selected in a biased way). Moreover, note that the validation dataset is often ignored in certain bounds and the only thing that is taken into account is the expected risk and the empirical risk (on the training data).</p>
  
  <p>In any case, the <span class="math-container">$\mathcal{VC}$</span> bounds may be "loose" because</p>
  
  <ul>
  <li>the <span class="math-container">$\mathcal{VC}$</span> dimension is often expressed with the big-<span class="math-container">$\mathcal{O}$</span> notation (e.g. see <a href="https://ai.stackexchange.com/a/17881/2444">this answer</a>)</li>
  <li>the bounds often involve probabilities and uncertainties (e.g. see <a href="https://ai.stackexchange.com/a/20341/2444">this other answer</a>)</li>
  <li>there aren't stricter bounds (i.e. no one found better bounds yet)</li>
  </ul>
  
  <blockquote>
    <p>Is the VC generalization bound loose due to its universality? Meaning, its results apply to all hypothesis sets, learning algorithms, input spaces, probability distributions, and binary target functions.</p>
  </blockquote>
  
  <p>I think the answer is yes. In fact, often, the specific tasks or learning algorithms are ignored in the analyses, but, in general, you may exploit your knowledge of the problem to improve e.g. the number of useful examples that the learning algorithm could use.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-19T17:21:24.930Z
Answers.Text: Great. A comment about "(i.e. no one found better bounds yet)": "_There exist lower bounds on the rate of uniform convergence where the order of magnitude is close to the order of magnitude obtained for the upper bounds (Vapnik and Chervonenkis, 1974)_"
Answers.UserDisplayName: OmG
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-19T13:03:35.853Z
Answers.LastActivityDate: 2020-04-19T13:15:08.237Z
Answers.LastEditDate: 2020-04-19T13:15:08.237Z
Answers.UserDisplayName: nbro
Body: <p>From what I understand VC dimension is what establishes the feasibility of learning for infinite hypothesis sets, the only kind we would use in practice. </p>
  
  <p>But, the literature (i.e. <a href="https://work.caltech.edu/textbook.html" rel="nofollow noreferrer">Learning from Data</a>) states that VC gives a <strong>loose</strong> bound, and that in real applications, learning models with lower VC dimension tend to generalize better than those with higher VC dimension. So, a good rule of thumb would be to require at least <code>10xVC</code> dimension examples in order to get decent generalization.</p>
  
  <p>I am having trouble interpreting what loose bound means. Is the VC generalization bound loose due to its universality? Meaning, its results apply to all hypothesis sets, learning algorithms, input spaces, probability distributions, and binary target functions.</p>
  
Tags: <machine-learning><computational-learning-theory><vc-dimension><vc-theory>
Title: What do we mean by saying "VC dimension gives a LOOSE, not TIGHT bound"?
UserDisplayName: Stefan Radonjic
ThreadText: # What do we mean by saying "VC dimension gives a LOOSE, not TIGHT bound"?
  
  (Asked by: username_0 on 2020-04-19)
  
  From what I understand VC dimension is what establishes the feasibility of learning for infinite hypothesis sets, the only kind we would use in practice.
  
  But, the literature (i.e. [Learning from Data](https://work.caltech.edu/textbook.html)) states that VC gives a **loose** bound, and that in real applications, learning models with lower VC dimension tend to generalize better than those with higher VC dimension. So, a good rule of thumb would be to require at least `10xVC` dimension examples in order to get decent generalization.
  
  I am having trouble interpreting what loose bound means. Is the VC generalization bound loose due to its universality? Meaning, its results apply to all hypothesis sets, learning algorithms, input spaces, probability distributions, and binary target functions.
  
  **Tags:** machine-learning, computational-learning-theory, vc-dimension, vc-theory
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-04-19. Score: 1 | Accepted answer
  
  > But, the literature (i.e. Learning from Data) states that VC gives a loose bound and that in real applications, learning models with lower VC dimension tend to generalize better than those with higher VC dimension.
  
  It's true that people often use techniques such as *regularisation* to avoid over-parametrized models. However, I think it's dangerous to say that, in real applications, those models are really generalizing better, given that you're typically assessing their generalization ability by using a finite validation dataset (possibly selected in a biased way). Moreover, note that the validation dataset is often ignored in certain bounds and the only thing that is taken into account is the expected risk and the empirical risk (on the training data).
  
  In any case, the $\mathcal{VC}$ bounds may be "loose" because
  
  * the $\mathcal{VC}$ dimension is often expressed with the big-$\mathcal{O}$ notation (e.g. see [this answer](https://ai.stackexchange.com/a/17881/2444))
  * the bounds often involve probabilities and uncertainties (e.g. see [this other answer](https://ai.stackexchange.com/a/20341/2444))
  * there aren't stricter bounds (i.e. no one found better bounds yet)
  
  > Is the VC generalization bound loose due to its universality? Meaning, its results apply to all hypothesis sets, learning algorithms, input spaces, probability distributions, and binary target functions.
  
  I think the answer is yes. In fact, often, the specific tasks or learning algorithms are ignored in the analyses, but, in general, you may exploit your knowledge of the problem to improve e.g. the number of useful examples that the learning algorithm could use.
  
  > **Comments:**
  > **username_2**: Great. A comment about "(i.e. no one found better bounds yet)": "_There exist lower bounds on the rate of uniform convergence where the order of magnitude is close to the order of magnitude obtained for the upper bounds (Vapnik and Chervonenkis, 1974)_"  
  
  ---
  
  