# How Uniform Random Weights Induce Non-uniform Bias: Typical Interpolating Neural Networks Generalize with Narrow Teachers

arXiv: https://arxiv.org/abs/2402.06323 · HTML: https://mlsanity.com/paper/2402.06323/

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 38 references that are in the map.
- First posted on arXiv 9 Feb 2024.

## Builds on (most cited first, 25 of 25)

- [Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift](https://mlsanity.com/paper/1502.03167/) (2015)
- [The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks](https://mlsanity.com/paper/1803.03635/) (2018)
- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [The Implicit Bias of Gradient Descent on Separable Data](https://mlsanity.com/paper/1710.10345/) (2017)
- [Weight Normalization: A Simple Reparameterization to Accelerate Training of Deep Neural Networks](https://mlsanity.com/paper/1602.07868/) (2016)
- [Quantized Neural Networks: Training Neural Networks with Low Precision Weights and Activations](https://mlsanity.com/paper/1609.07061/) (2016)
- [Implicit Regularization in Deep Matrix Factorization](https://mlsanity.com/paper/1905.13655/) (2019)
- [Implicit Regularization in Matrix Factorization](https://mlsanity.com/paper/1705.09280/) (2017)
- [Gradient Descent Maximizes the Margin of Homogeneous Neural Networks](https://mlsanity.com/paper/1906.05890/) (2019)
- [Kernel and Rich Regimes in Overparametrized Models](https://mlsanity.com/paper/2002.09277/) (2020)
- [Norm-Based Capacity Control in Neural Networks](https://mlsanity.com/paper/1503.00036/) (2015)
- [Size-Independent Sample Complexity of Neural Networks](https://mlsanity.com/paper/1712.06541/) (2017)
- [Implicit Bias of Gradient Descent for Wide Two-layer Neural Networks Trained with the Logistic Loss](https://mlsanity.com/paper/2002.04486/) (2020)
- [User-friendly introduction to PAC-Bayes bounds](https://mlsanity.com/paper/2110.11216/) (2021)
- [What's Hidden in a Randomly Weighted Neural Network?](https://mlsanity.com/paper/1911.13299/) (2019)
- [Proving the Lottery Ticket Hypothesis: Pruning is All You Need](https://mlsanity.com/paper/2002.00585/) (2020)
- [Universal Approximation with Deep Narrow Networks](https://mlsanity.com/paper/1905.08539/) (2019)
- [Deep learning generalizes because the parameter-function map is biased towards simple functions](https://mlsanity.com/paper/1805.08522/) (2018)
- [On the Implicit Bias in Deep-Learning Algorithms](https://mlsanity.com/paper/2208.12591/) (2022)
- [Nonuniform-to-Uniform Quantization: Towards Accurate Quantization via Generalized Straight-Through Estimation](https://mlsanity.com/paper/2111.14826/) (2021)
- [PAC-Bayes Compression Bounds So Tight That They Can Explain Generalization](https://mlsanity.com/paper/2211.13609/) (2022)
- [Implicit Bias in Deep Linear Classification: Initialization Scale vs Training Accuracy](https://mlsanity.com/paper/2007.06738/) (2020)
- [Is SGD a Bayesian sampler? Well, almost](https://mlsanity.com/paper/2006.15191/) (2020)
- [Exponentially vanishing sub-optimal local minima in multilayer neural networks](https://mlsanity.com/paper/1702.05777/) (2017)
- [How do Minimum-Norm Shallow Denoisers Look in Function Space?](https://mlsanity.com/paper/2311.06748/) (2023)

## Built on by (most cited first, 18 of 18)

- [Stable Minima Cannot Overfit in Univariate ReLU Networks: Generalization by Large Step Sizes](https://mlsanity.com/paper/2406.06838/) (2024)
- [From Kernels to Features: A Multi-Scale Adaptive Theory of Feature Learning](https://mlsanity.com/paper/2502.03210/) (2025)
- [Provable Tempered Overfitting of Minimal Nets and Typical Nets](https://mlsanity.com/paper/2410.19092/) (2024)
- [Mitigating the Curse of Detail: Scaling Arguments for Feature Learning and Sample Complexity](https://mlsanity.com/paper/2512.04165/) (2025)
- [The Implicit Bias of Structured State Space Models Can Be Poisoned With Clean Labels](https://mlsanity.com/paper/2410.10473/) (2024)
- [Unsupervised Translation of Emergent Communication](https://mlsanity.com/paper/2502.07552/) (2025)
- [Quantifying Overfitting along the Regularization Path for Two-Part-Code MDL in Supervised Classification](https://mlsanity.com/paper/2503.02110/) (2025)
- [Temperature is All You Need for Generalization in Langevin Dynamics and other Markov Processes](https://mlsanity.com/paper/2505.19087/) (2025)
- [Statistical Properties of Training & Generalization](https://mlsanity.com/paper/2606.20299/) (2026)
- [Favorability of Loss Landscape with Weight Decay Requires Both Large Overparametrization and Initialization](https://mlsanity.com/paper/2505.22578/) (2025)
- [On the Sample Efficiency of Inverse Dynamics Models for Semi-Supervised Imitation Learning](https://mlsanity.com/paper/2602.02762/) (2026)
- [Golden Handcuffs make safer AI agents](https://mlsanity.com/paper/2604.13609/) (2026)
- [Understanding the Parameter Space Geometry of Transformers Encoding Boolean Functions](https://mlsanity.com/paper/2606.08768/) (2026)
- [Revisiting the Volume Hypothesis](https://mlsanity.com/paper/2606.31282/) (2026)
- [Zero Generalization Error Theorem for Random Interpolators via Algebraic Geometry](https://mlsanity.com/paper/2512.06347/) (2025)
- [Width-Robust Learnability in Mean-Field Bayesian Neural Networks](https://mlsanity.com/paper/2607.05735/) (2026)
- [From Expressivity to Sample Complexity: Narrow Teachers for Transformers via C-RASP](https://mlsanity.com/paper/2607.11760/) (2026)
- [Understanding Generalization Requires Universal Induction](https://mlsanity.com/paper/2609.34458/) (2026)

## Abstract (arXiv)

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.