I haven't read the paper, but I think it only really makes sense in context: a) The traditional view of generalization would argue that neural nets are "too co

I haven't read the paper, but I think it only really makes sense in context: a) The traditional view of generalization would argue that neural nets are "too complicated"/have too many parameters/etc to generalize well. And that for generalization you need more limited models. b) To reconcile this with practical results of CNNs some people tried to argue that while neural nets had a lot of actual parameters, the structure of neural nets reduced the effective capacity of neural nets to not be as big as the parameter counts implied. Same argument for regularization. c) This paper shows that those arguments are not satisfactory since they really can fit random labels.