But ultimately they look for a convenient 'nearby' solution: that's the nature of stochastic gradient descent. If you have two solutions and one of them is the hash function, it would be helpful to /know/ that the hash function is harder to get to than the 'correct' solution.

For my pet problem, there's quite different performance across classes. It would be tougher to do the comparison for a subset of classes, but could still probably design some kind of experiment.

What is a generalization of a random labeling? Does the network become psychic? Is this saying "garbage works fine by these measures"?

I'm still honestly confused here. Yes, the success of neural networks generally shows they more than memorize. Some of the experiments here show they can just memorize too. I guess some describe something in-between.

But all this seems obvious. Is there something that's being quantified here?

Classical statistical learning theory (from Vapnik and Chervonenkis, among others), predicts that low capacity models will generalize (have small generalization gaps). It makes no promises for large capacity models, i.e. those which can fit random labels. Yet here we are.