How Uniform Random Weights Induce Non-uniform Bias: Typical Interpolating Neural Networks Generalize with Narrow Teachers
This addresses a fundamental theoretical problem in machine learning about generalization in over-parameterized models, but it is incremental as it builds on prior empirical work to provide a proof under specific conditions.
The paper tackles the puzzle of why over-parameterized neural networks generalize well when interpolating data by proving that random neural networks sampled from a uniform prior over parameters, conditioned on perfect training classification, typically generalize well if an underlying narrow teacher neural network exists. The result shows that this approach enables learning with sample complexity roughly proportional to the teacher's complexity, not the student's.
Background. A main theoretical puzzle is why over-parameterized Neural Networks (NNs) generalize well when trained to zero loss (i.e., so they interpolate the data). Usually, the NN is trained with Stochastic Gradient Descent (SGD) or one of its variants. However, recent empirical work examined the generalization of a random NN that interpolates the data: the NN was sampled from a seemingly uniform prior over the parameters, conditioned on that the NN perfectly classifies the training set. Interestingly, such a NN sample typically generalized as well as SGD-trained NNs. Contributions. We prove that such a random NN interpolator typically generalizes well if there exists an underlying narrow ``teacher NN'' that agrees with the labels. Specifically, we show that such a `flat' prior over the NN parameterization induces a rich prior over the NN functions, due to the redundancy in the NN structure. In particular, this creates a bias towards simpler functions, which require less relevant parameters to represent -- enabling learning with a sample complexity approximately proportional to the complexity of the teacher (roughly, the number of non-redundant parameters), rather than the student's.