"Deep lifts": Neural networks can generalize even with the dumbest optimizer

Given a labeled dataset (x i, y i) i = 1 n, consider drawing a parameter vector θ uniformly at random from those that interpolate the data within a width- W depth- D ReLU architecture with continuous weights bounded within [-M, M]. We study the generalization properties of θ in the case where the dataset can, in fact, be explained by a smaller w-by- d ReLU network. Despite the obliviousness of the selection rule for θ, it adaptively generalizes at the rate O (wdWD over n), rather than being governed by the VC dimension of the full W-by- D hypothesis class. The reason is due to a particular inductive bias in ReLU networks: the w-by- d parameter *witnesses* an exponential volume of W-by- D interpolating parameters, which dwarfs the volume of poorly generalizing parameters (conditioned on interpolation). We explicitly construct this set of near-equivalent W-by- D parameters by a proof technique called *deep lifting*, and then tie the achievable volume to stability properties of the w-by- d witness. Examples show that these techniques allow us to convert approximation-theoretic results into generalization guarantees for nonparametric classes. We further show that generalization of uniform-random interpolators can survive label corruptions.