Introduction
Traditional statistical learning theory suggests that models with far more parameters than data points should "memorize" noise and fail to generalize. Yet, deep neural networks—which are notoriously overparameterized—achieve state-of-the-art performance without explicit regularization. This paper argues that generalization is driven by an inherent simplicity bias rooted in how models are constructed: even before training begins, the probability space of overparameterized models is naturally tilted toward simple functions rather than complex ones.
Methodology
The paper employs a mix of discrete mathematics and dynamical systems theory to analyze three distinct scenarios where simplicity emerges naturally from architectural constraints.
Architectural Mechanisms
The study distinguishes between the simplicity mechanisms in wide versus deep networks. Wide networks achieve simplicity through the Central Limit Theorem, behaving as Gaussian Processes (Neural Tangent Kernels). In contrast, deep networks act as dynamical systems where layers serve as operators that naturally converge toward simple "fixed point" functions.
Theoretical Frameworks
- Boolean Functions: Analysis of binary AND/OR trees shows that "constructing a tree at random" leads to simplicity, whereas "choosing a function at random" leads to overfitting.
- Wide Neural Networks: These are viewed as Gaussian Processes where simplicity arises from averaging many random variables.
- Deep Neural Networks: Stability analysis using Lyapunov exponents shows that increasing depth causes networks to converge toward simple constant functions.
Key Insights and Ideas
- Construction vs. Sampling: Building a function by randomly connecting components is exponentially more likely to create something "simple" than picking a random function from a list of all possibilities. Simplicity is the "default" state of random construction.
- The "No Shannon Effect": While Claude Shannon proved that most Boolean functions are complex, this paper highlights that in randomly constructed models, these complex functions are so rare they are practically non-existent.
- Optimizer Independence: Simplicity bias exists at initialization. Training via Stochastic Gradient Descent (SGD) simply "nudges" this pre-existing simple prior to fit the specific data points, rather than being the primary source of generalization.
Key Results
The paper formalizes these observations through several theorems. Notably, Theorem 3 shows that under certain conditions, such as orthonormal samples (Condition S2), a randomly initialized deep network forced to fit training data will naturally behave like a kernel machine or a nearest-neighbor classifier.
- Theorem 1 (Random Trees): Proves that random construction interpolates data without overfitting if the target function's complexity is below a certain threshold relative to sample size.
- Theorem 2 (Asymptotic Stability): Demonstrates that in deep networks with standard activations like ReLU, the zero-state is an attractor, favoring simple constant outputs.
Limitations and Future Work
While the paper proves that a "naive" random search for a fitting model would generalize, it acknowledges that such a search is computationally impossible, making SGD necessary for efficiency. Some proofs also rely on idealized "orthonormal samples" (perfectly perpendicular data points), which are rare in real-world correlated data. Future research may explore the complex interaction between the loss landscape and data distribution during the middle stages of training.
Summary updated