Given a labeled dataset {(xi,yi)}i=1n, 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~(nwdWD), 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.
Figures & tables
Figure 1: A small interpolating network “witnesses” many large interpolating networks. Blue volume dwarfs the intersection of the gray and red volumes once n≫wWD .
Figure 2: A visualization of the structure of a deep lift ,ϕ∈CM(W,D) , of θ∈CM(u,D) . Most of ϕ ’s weights (in blue), may be chosen arbitrarily from [−M,M] . Those in green are chosen from an interval of size 2ρ′ . Those in red are chosen from an interval of size ρ (built around θ ’s weights). The result is a high-volume set of nearly equivalent lifts of θ .