I think that it depends what you mean by "learning". Creating a mapping to a training set where you have a sufficiently expressive representation is trivial - s

I think that it depends what you mean by "learning". Creating a mapping to a training set where you have a sufficiently expressive representation is trivial - simply create a list, and then find the most efficient representation of the list; zip it for example. The point of learning is to generalize from the training set to unseen examples via the representation and figure 1 of the paper shows (part c) that this is not what is claimed for corrupted or randomized examples in this paper. How the non generalised claims then extend to the discussions in section 2 leaves me flailing, but that's not unusual! However, my thought is that the difficulty is measurement of the structural risk of a deep network where network weights very subtly encode information, or don't depending on the network. Perhaps sweeping the networks and then setting weights below a threshold to 0 and measuring the generalisation error impact would be a way to measure what in the network is useful encoding and what isn't? The rest of the network could be easily "measured" as bits to encode?