Abstract
We prove that the binary classifiers of bit strings generated by random wide deep neural networks with ReLU activation function are biased towards simple functions. The simplicity is captured by the following two properties. For any given input bit string, the average Hamming distance of the closest input bit string with a different classification is at least $\sqrt{n / (2\pi \ln n)}$, where $n$ is the length of the string. Moreover, if the bits of the initial string are flipped randomly, the average number of flips required to change the classification grows linearly with $n$. These results are confirmed by numerical experiments on deep neural networks with two hidden layers, and settle the conjecture stating that random deep neural networks are biased towards simple functions. This conjecture was proposed to explain the unreasonably good generalization properties of deep learning algorithms. Our results constitute a fundamental step forward in the characterization of this distribution, therefore contributing to the understanding of the generalization properties of deep learning algorithms.
The Mystery of Generalization
One of the most significant puzzles in modern deep learning is why models with millions of parameters—far exceeding the number of training examples—do not simply memorize the training data and fail on new examples. Traditional statistical learning theory suggests that as a model's capacity increases, its ability to generalize should decrease. However, deep neural networks (DNNs) exhibit an "unreasonable effectiveness" in practice.
This paper addresses the conjecture that DNNs are inherently biased toward "simple" functions. While this bias has been observed numerically in previous studies, a formal mathematical proof was missing. The challenge lies in defining "simplicity" in a way that is both mathematically tractable and relevant to the operational mechanics of neural networks.
Defining Simplicity through Robustness
The authors define simplicity through the lens of robustness to input changes. They focus on binary classifiers of bit strings (sequences of 0s and 1s) and evaluate two specific metrics:
- Robustness to Targeted Change (Closest Hamming Distance): The minimum number of bit flips required to reach an input that receives a different classification.
- Robustness to Random Noise: The average number of random bit flips required before the network's classification changes.
Using the Gaussian Process (GP) approximation—a framework where infinitely wide neural networks with random weights behave like Gaussian processes—the authors analyzed the correlations between network outputs for different inputs. They found that in wide ReLU networks, these distances grow significantly with the input size $n$, indicating that the functions generated are highly stable and "simple."
Theoretical Results and Scaling Laws
Targeted Robustness
The authors proved that for random wide ReLU networks, the average Hamming distance to the nearest differently classified bit string scales as $\sqrt{n / \ln n}$. In a truly random classifier, this distance would typically be 1, regardless of $n$. This scaling law demonstrates that as the input dimension increases, the "islands" of constant classification become increasingly large and robust.
Random Noise Robustness
When considering random perturbations rather than targeted ones, the bias is even more pronounced. The research shows that the number of random flips required to change a classification grows linearly with the input size ($O(n)$). Heuristically, this requires flipping a substantial fraction of the bits (approximately 25%) to change the output, confirming that the network's classification regions are voluminous and stable.
Key Insights and Empirical Validation
Numerical simulations on networks with two hidden layers matched these theoretical predictions with high precision (within 1.5%). Several key insights emerged from this work:
- Simplicity is Stability: A "simple" function in the context of DNNs is one that is insensitive to small or moderate changes in the input. This stability forces the network to assign the same label to large "neighborhoods" of inputs.
- Correlation as a Driver: In wide networks, outputs for similar inputs are highly correlated. This correlation restricts the network to a tiny, highly structured corner of the possible function space that favors stability over chaos.
- Bias Survives Training: Experiments on the MNIST dataset showed that this bias is not merely a property of random initialization. Even after training, models remained biased toward simple, robust classification boundaries. Correctly classified images were found to be much "deeper" inside their classification regions (average distance ~10.5 bits) compared to incorrectly classified ones (average distance ~1.4 to 2.3 bits).
Limitations and Future Outlook
While these results provide a rigorous foundation for simplicity bias, some limitations remain. The core proof relies on the infinite-width limit of the Gaussian Process approximation; while results hold for widths as small as $n=100$, the behavior of extremely narrow networks is still an open question. Additionally, while the scaling laws hold across various activation functions, the constant multipliers (prefactors) for functions like tanh may become exponentially small in very deep networks, potentially weakening the effect.
Finally, this work provides a fundamental step toward understanding adversarial examples. The inherent simplicity bias suggests a natural trade-off between the generalization benefits of stability and the potential vulnerability to specifically crafted adversarial perturbations, a topic slated for future research.
Summary updated