Comment by srean

PAC isn't asymptotic in general. It gives finite estimates for finite sizes of training data.

If you say, and I think you are indeed saying so, that PAC is ridiculously pessimistic, I would be in violently agreement with you. That's one reason why for practical training data sizes and practical (infinite version space) hypothesis classes PAC gives bound such as -- probability of error is less than 41K. This isn't exactly incorrect but not very useful or informative.

A far more useful formulation is PAC-Bayesian where you get error bounds less than 1 guaranteed and usually less than 0.5 on reasonable sized training data sets.