TL;DR
This paper provides a rigorous mathematical proof for a long-standing observation in deep learning: random, untrained neural networks are naturally biased toward "simple" functions. By analyzing wide ReLU networks in the infinite-width limit, the authors show that these models are remarkably robust to input noise, requiring significantly more perturbations to change their classification than a truly random classifier would.
The Mystery of Generalization
One of the biggest mysteries in deep learning is why over-parameterized models—networks with far more parameters than training data points—generalize so well instead of simply memorizing noise. Standard statistical learning theory often fails here because it suggests these models should overfit.
A popular hypothesis is that the "prior" distribution of functions—the functions a network is likely to represent at random initialization—is biased toward simplicity. If the network naturally prefers simple patterns, it will likely pick a simple explanation for the training data, which usually leads to better generalization on real-world data. While this "simplicity bias" had been observed numerically, a formal theoretical proof was missing. This paper sets out to provide that proof.
Methods: Infinite Width and Input Sensitivity
The authors bridge the gap between theory and practice using the Gaussian Process (GP) approximation. In the limit of infinite width, a deep neural network with randomly initialized weights and biases behaves like a Gaussian Process.
The researchers define "simplicity" through the lens of input sensitivity. They represent inputs as bit strings of length $n$ and analyze two specific metrics:
- Closest Boundary Distance: For a given input, how many bits (Hamming distance) must you flip to reach the closest point that the network classifies differently?
- Random Flip Robustness: If you start flipping bits at random, how many flips does it take on average to change the network's output?
They prove two main theorems showing that for random wide ReLU networks, these distances scale with the input size $n$ in a way that indicates extreme stability, whereas a "uniformly random" classifier would be highly unstable.
Key Insights
- DNNs are not "Random" Classifiers: If you picked a classification for every possible bit string at random, the nearest "wrong" classification would be just 1 bit flip away on average. In contrast, random DNNs require flipping roughly $\sqrt{n}$ bits to find the nearest boundary.
- The "Aha" Moment on Correlation: The reason DNNs are so robust is that their outputs for similar inputs are highly correlated. In the infinite-width limit, inputs that differ by only a few bits become "perfectly correlated," meaning the network almost certainly gives them the same label.
- Simplicity $\neq$ Low Kolmogorov Complexity: The authors clarify that while their "simple" functions have low Kolmogorov complexity (they are easy to describe), the reverse isn't always true. For example, the "parity function" is easy to describe but highly sensitive to single-bit flips; the paper proves that a random DNN is extremely unlikely to represent such a function.
- Confidence vs. Distance: There is a strong linear correlation between the absolute value of the network's output (its "confidence") and its distance to the nearest classification boundary.
Key Results
The paper validates its theoretical findings using synthetic random bit strings to test the scaling laws of Hamming distances, as well as the MNIST dataset to confirm these properties in a real-world context.
- Theorem 1 (The $\sqrt{n}$ Scaling): The average Hamming distance to the closest differently classified string is at least $\sqrt{n / (2\pi \ln n)}$. Numerical experiments confirmed this with high precision.
- Theorem 2 (Linear Scaling): The number of random flips required to change a classification grows linearly with $n$. Heuristic arguments suggested a bound of $n/4$, while simulations showed a scaling of approximately $n/3$.
- MNIST Consistency: Even after training on MNIST, the "simplicity" property survives. Correctly classified images were found to be much further from the classification boundary (average distance ~10.6) than incorrectly classified ones (average distance ~1.4 to 2.3).
Limitations and Future Work
- Infinite Width Limit: The core proofs rely on the Gaussian Process approximation, which assumes the hidden layers are infinitely wide. While the authors show the results hold for widths as small as $n=100$, the behavior of very narrow or bottlenecked networks remains a separate question.
- Activation Functions: While the scaling laws ($\sqrt{n}$ and $n$) hold for most activations, the "pre-factors" can become exponentially small as the network gets deeper for non-ReLU activations. This suggests that depth might "wash away" some of this simplicity bias in certain architectures.
- Adversarial Robustness: The authors note that their work is closely related to the study of adversarial examples. Future work could involve using these theoretical bounds to provide fundamental guarantees on how robust a network can be to malicious perturbations.
Summary updated