"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 \hatθ 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 \hatθ 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 \hatθ, it adaptively generalizes at the rate \tilde O\left(\frac{wdWD}{n}\right), 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.