"Can be misleading" is an accurate characterization.
It is an uniform bound and will have problems with very large hypothesis classes but its statement isnt wrong (just that the tool is a little heavy handed). For simpler models they are adequately useful. So I would suggest new users to learn if they want to use simpler models rather than deep learning methods.
Real world isn't the adversarial/ worst-case that these models of generalization assume. So the generalization performance you experience is usually a better than what PAC indicates, but estimating that experience was not PAC's charter. It's charter was to quantify a adversarial/legal guarantee, the minimum (infimum) guaranteed program.
I too like PAC-Bayes a lot (see my other comments) but it does have a cop out in that by definition you do not know how good your prior is, yet the quantitative estimate of generalization error depends on how good it was.
Nevertheless, PAC-Bayesian and statistical physics based bounds are closer to what we experience, but you can't guarantee that the worst case will not bite you.
I agree that this is a good nuanced take. However, I find that students who have learned PAC (which usually takes quite some time) often have to unlearn certain principles to do PAC-Bayes, so my comments come from a fair amount of frustration with the topic. On the other hand, I find that teaching students PAC-Bayes from the get-go is easier, it still works for simpler models (you can derive the same PAC bounds, so you can't do any worse), and they get the full story. Obviously for those of us who learned both, it is good to know both. But I am skeptical for the next generation coming through whether it is worth teaching PAC at all.
You raise a good point.
I had not considered the pedagogical value of starting with PAC Bayesian bounds. It will be interesting to see ML courses that take that route.
Similar issues show up in traditional statics when considering multi-hypothesis testing. I wonder if betting/gambling over hypotheses might be a more accessible way to convey these ideas to new students.
Do you have a good textbook to reference to where the theory starts from PAC-Bayes?
You can try this one
https://books.google.co.in/books/about/User_friendly_Introdu...
Free download here
https://arxiv.org/abs/2110.11216
One of the ICMLs had a nice tutorial by Langford and Banerjee on the relationship between the different style of bounds. 2003, I think.
Just to add on top of the quality reference provided by srean, I like to first drill in Bayesian principles and then use this article to derive PAC-Bayes from that: https://arxiv.org/abs/1605.08636
Regular PAC falls out by taking a uniform prior over a finite hypothesis class (and then building up VC dimension if desired, but usually by this point you realise why the bounds are unlikely to be good).
Seems I was misremembering the dates. The Langford and Banerjee papers/turorials I had in mind were
On Bayesian Bounds https://dl.acm.org/doi/10.1145/1143844.1143855
Tutorial on Practical Prediction Theory for Classification https://jmlr.csail.mit.edu/papers/v6/langford05a.html
The first one is quite in the same spirit that you like.