"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{\theta }$ 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{\theta }$ 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{\theta }$, 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 $\theta$ 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 “deep lifting,” and then tie the achievable volume to stability properties of $\theta$. 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.