In Statistical Learning Theory, Uniform convergence means for a hypothesis class H, given m(\delta, \epsilon), for arbitrary distribution over domain (X, Y), with probability $1- \delta$, the generalization error is within $\epsilon$ range.
Now The no free lunch theorem state that one can construct a distribution over (X,Y) such that an algorithm will fail with large probability while another algorithm will work. The sample size is m smaller than half of cardinality of X.
My question is: are the two statements contradictory? If the uniform convergence hold, algorithm A working on hypothesis class H will always work as long as the sample complexity is reached, so there would not be cases of failure?
There is a version of the No Free Lunch theorem, namely "With Vanishing Risk"; this one might be more in sync with the uniform convergence requirement.
It seems that the sample size m is fixed in no free lunch theorem and this sample size has not reached the sample complexity of a hypothesis class with size |H|=2^{2m}. So in the settings of no free lunch theorem, as long the hypothesis class size of the learner is |H|=2^{2m}, the learner associated H is not PAC learnable.
There is a version of the No Free Lunch theorem, namely "With Vanishing Risk"; this one might be more in sync with the uniform convergence requirement.
- Badges
- Science topic
- Similar topics
- Medicine
- Physiology
- Biosignals
- Biomedical Signal Processing
- Statistical Learning