[redytedy]

>> Indeed, this is precisely why deep neural nets need to be trained with so much data. Because they are simply trying to memorise enough instances of a concept to minimise their error.

Uh, the degree to which this is true is hotly -contested and an active area of research. Some architectures appear to generalize within domains. You can't conclude this from the assumptions made in the PAC-Learnability proof..

[YeGoblynQueenne]

Sorry, my fault: I don't mean that PAC-Learnability means that neural nets memorise their training instances. That's more my interpretation of their observed behaviour, if you like. What I meant was that PAC-Learnability doesn't assume any ability like reasoning, and really no other ability than er, PAC-Learnability.

There's a debate, of course. I like to point to Domingos' paper:

Every Model Learned by Gradient Descent Is Approximately a Kernel Machine

https://arxiv.org/abs/2012.00152

With the full understanding that it's just one paper.