Answers.Body: <p>In general, we won't know: it is an <em>undecidable</em> problem.</p>
  <p>For reference, <a href="https://arxiv.org/abs/2010.06076" rel="nofollow noreferrer">Bashir et al.</a> and <a href="https://arxiv.org/pdf/2102.02850.pdf" rel="nofollow noreferrer">Sehra et al.</a> proved that for a given dataset, (even if given unlimited training time) it is undecidable whether an encodable learning algorithm will always overfit or underfit respectively. So we can never know if we have got the 'right' model (in terms of generalization error).</p>
  <p>FYI, This problem is related to the halting problem and minimum description length (MDL).</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-06-19T04:36:25.163Z
Answers.LastActivityDate: 2023-06-19T04:36:25.163Z
Answers.UserDisplayName: lpounng
Body: <p>For given units of a measure of model complexity, how many examples do we need to train a network to get the model right and generalize?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-06-16T02:10:50.157Z
Comments.Text: Please name one such measure of model complexity, so we can elaborate from there.
Comments.UserDisplayName: lpounng
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-06-16T09:28:15.013Z
Comments.Text: Let us use VC complexity.
Comments.UserDisplayName: Justaperson
Tags: <deep-learning><training><models><sample-complexity>
Title: For given units of a measure of model complexity, how many examples do we need to train a network to get the model right and generalize?
UserDisplayName: Justaperson
ThreadText: # For given units of a measure of model complexity, how many examples do we need to train a network to get the model right and generalize?
  
  (Asked by: username_0 on 2023-06-15)
  
  For given units of a measure of model complexity, how many examples do we need to train a network to get the model right and generalize?
  
  **Tags:** deep-learning, training, models, sample-complexity
  
  > **Comments:**
  > **username_1**: Please name one such measure of model complexity, so we can elaborate from there.  
  > **username_0**: Let us use VC complexity.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2023-06-19. Score: 0
  
  In general, we won't know: it is an *undecidable* problem.
  
  For reference, [Bashir et al.](https://arxiv.org/abs/2010.06076) and [Sehra et al.](https://arxiv.org/pdf/2102.02850.pdf) proved that for a given dataset, (even if given unlimited training time) it is undecidable whether an encodable learning algorithm will always overfit or underfit respectively. So we can never know if we have got the 'right' model (in terms of generalization error).
  
  FYI, This problem is related to the halting problem and minimum description length (MDL).
  
  
  ---
  
  