Hacker News Reader

Comment by 5555watch | Hacker News Reader

Another useful link [0], page 91. Effectively, the more complex the solution, the heavier is the upper bound on true risk. It doesn't mean a simpler model is necessarily better. But the complexity brings its own larger support for mistakes to live in. The _likelihood_ of being _more correct_ is probably related to larger sample required to learn a more complex model.

[0]: https://www.cs.huji.ac.il/~shais/UnderstandingMachineLearnin...

View on HN

Absolutely not. This link is a reference on PAC learning, which is thoroughly misleading in the land of deep learning and inevitably leads to vacuous bounds. This is common knowledge in deep learning. I would not recommend that any student learn any part of this theory at this point, since we have far better alternatives in terms of simplicity, accuracy, and generality.

PAC-Bayes is genuinely superior, for example. Instead of a uniform weighting over all hypotheses (effectively encoded in the supremum), you get to weight the hypothesis class in virtually any way that you want. This is critical to ensure that you exclude absurd hypotheses that you have almost nil chance of reaching. If you do consider a uniform weighting, then you can just easily reduce to PAC anyway, but you do so in a cleaner package.

"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.

Reply on news.ycombinator.com