Answers.Body: <p>Indeed PAC learning theory's uniform convergence provides a worst case lower bound on the number of samples needed for the training error to be close to the generalization error for all hypotheses in a given hypothesis class. The bound depends on the size of the hypothesis class (or its complexity, like VC dimension or Rademacher complexity), the desired error tolerance <span class="math-container">$ϵ$</span>, and the confidence level <span class="math-container">$(1−δ)$</span>.</p>
  <p>However, for many practical ML models such as overparameterized neural networks, the number of possible hypotheses is extremely large due to the huge number of parameters. As a result the sample complexity worst case lower bound predicted by above PAC theory is often too high. On the other hand, in practice we rarely have a number of training samples that meets this high theoretical lower bound. Therefore these models can perform well on the training set but poorly on unseen data which is overfitting since uniform convergence doesn't apply.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-09-10T01:53:46.843Z
Answers.Text: I understand that but only needing ~130*d examples per parameter for 0.02 error bounds on difference between test error and generalization error seems kind of light no? Maybe I am underestimating the number of parameters in NN's?
  
  ResNet50 has ~26 million parameters so would 3.4B images would be needed to have  very good guarantees on not overfitting...? That doesn't seem like a ENORMOUS massive number of images
Answers.UserDisplayName: Joe Jameson
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-09-10T01:54:49.040Z
Answers.Text: NVM i did the math wrong it would be 50x more but still?
Answers.UserDisplayName: Joe Jameson
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-09-10T02:28:27.073Z
Answers.Text: Remember PAC bounds here are worst case bounds, and it may be more for different models with different details and architectures. If you don't buy this main idea, certainly you can wait for other responses or ideas
Answers.UserDisplayName: cinch
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-09-13T00:56:29.880Z
Answers.Text: I mean I understand what your trying to say but I feel like there are so many cases where there is a big gap between training error and test error which seems to contradict the theory?
Answers.UserDisplayName: Joe Jameson
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-09-13T02:10:16.357Z
Answers.Text: @JoeJameson PAC learning theory is known to be of little practical use as you correctly pointed out there're so many cases it cannot apply as I've explained the main reason above. I don't see logical contradiction either in PAC theory or our claims.
Answers.UserDisplayName: cinch
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-09-09T04:56:39.873Z
Answers.LastActivityDate: 2024-09-09T04:56:39.873Z
Answers.UserDisplayName: cinch
Body: <p>I have been learning about agnostic PAC and uniform convergence with finite hypothesis classes. If we use a NN with <span class="math-container">$d$</span> parameters with <span class="math-container">$64$</span>-bit precision</p>
  <p><span class="math-container">$$ \frac{r^2(128d+2\ln(\frac{2}{\delta}))}{\epsilon^2} $$</span></p>
  <p>should be an upper bound on the number of examples needed for the sample error to be within epsilon of the generalization error for any hypothesis, where <span class="math-container">$r$</span> is the &quot;range&quot; of the loss function.</p>
  <p>The theory suggests overfitting shouldn't occur, but it obviously does, so what am I missing?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-09-11T11:11:41.627Z
Comments.Text: You say "finite hypothesis classes" and PAC learning? Are neural networks finite? I don't see how the theory suggests that over-fitting shouldn't occur. Can you be more specific? Aren't they talking about bounds and number of examples _needed_?
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-09-13T00:54:10.030Z
Comments.Text: They are not finite but in practice computers are limited to finite bit-representations so there are roughly $2^{64*d}$ parameters for a neural network with d parameters
Comments.UserDisplayName: Joe Jameson
Tags: <machine-learning><overfitting><computational-learning-theory><pac-learning>
Title: Why do learning paradigms overfit? (Machine Learning Theory) uniform convergence
UserDisplayName: Joe Jameson
ThreadText: # Why do learning paradigms overfit? (Machine Learning Theory) uniform convergence
  
  (Asked by: username_0 on 2024-09-09)
  
  I have been learning about agnostic PAC and uniform convergence with finite hypothesis classes. If we use a NN with $d$ parameters with $64$-bit precision
  
  $$ \frac{r^2(128d+2\ln(\frac{2}{\delta}))}{\epsilon^2} $$
  
  should be an upper bound on the number of examples needed for the sample error to be within epsilon of the generalization error for any hypothesis, where $r$ is the "range" of the loss function.
  
  The theory suggests overfitting shouldn't occur, but it obviously does, so what am I missing?
  
  **Tags:** machine-learning, overfitting, computational-learning-theory, pac-learning
  > **Comments:**
  > **username_1**: You say "finite hypothesis classes" and PAC learning? Are neural networks finite? I don't see how the theory suggests that over-fitting shouldn't occur. Can you be more specific? Aren't they talking about bounds and number of examples _needed_?  
  > **username_0**: They are not finite but in practice computers are limited to finite bit-representations so there are roughly $2^{64*d}$ parameters for a neural network with d parameters  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2024-09-09. Score: 0 | Accepted answer
  
  Indeed PAC learning theory's uniform convergence provides a worst case lower bound on the number of samples needed for the training error to be close to the generalization error for all hypotheses in a given hypothesis class. The bound depends on the size of the hypothesis class (or its complexity, like VC dimension or Rademacher complexity), the desired error tolerance $ϵ$, and the confidence level $(1−δ)$.
  
  However, for many practical ML models such as overparameterized neural networks, the number of possible hypotheses is extremely large due to the huge number of parameters. As a result the sample complexity worst case lower bound predicted by above PAC theory is often too high. On the other hand, in practice we rarely have a number of training samples that meets this high theoretical lower bound. Therefore these models can perform well on the training set but poorly on unseen data which is overfitting since uniform convergence doesn't apply.
  
  > **Comments:**
  > **username_0**: I understand that but only needing ~130*d examples per parameter for 0.02 error bounds on difference between test error and generalization error seems kind of light no? Maybe I am underestimating the number of parameters in NN's?  ResNet50 has ~26 million parameters so would 3.4B images would be needed to have  very good guarantees on not overfitting...? That doesn't seem like a ENORMOUS massive number of images  
  > **username_0**: NVM i did the math wrong it would be 50x more but still?  
  > **username_2**: Remember PAC bounds here are worst case bounds, and it may be more for different models with different details and architectures. If you don't buy this main idea, certainly you can wait for other responses or ideas  
  > **username_0**: I mean I understand what your trying to say but I feel like there are so many cases where there is a big gap between training error and test error which seems to contradict the theory?  
  > **username_2**: @JoeJameson PAC learning theory is known to be of little practical use as you correctly pointed out there're so many cases it cannot apply as I've explained the main reason above. I don't see logical contradiction either in PAC theory or our claims.  
  
  ---
  
  