Introduction
A fundamental puzzle in deep learning is why overparameterized neural networks generalize so effectively. With millions of parameters, these models possess the capacity to memorize training data entirely, yet they consistently discover patterns that apply to unseen data. This paper from researchers at Harvard University investigates the "implicit regularization" of Stochastic Gradient Descent (SGD), proposing that the optimization process itself biases networks toward a specific "simplicity-to-complexity" trajectory.
The Simplicity Bias of SGD
The authors argue that SGD does not search for an arbitrary solution among the many that could fit the training data. Instead, it follows a structured path, learning simple functions before progressing to more complex ones. Crucially, the network "retains" these simple, generalizing patterns even as it continues to train and eventually fits noise in the later stages of optimization.
Methodology: Measuring Complexity
To quantify this phenomenon, the researchers introduced a novel information-theoretic metric called Performance Correlation ($\mu_Y(F; L)$). This metric, based on conditional mutual information, measures the extent to which a complex model's ($F$) predictive success on labels ($Y$) can be explained by a simpler reference model ($L$), such as a linear classifier.
If the performance of the complex model vanishes when conditioned on the simple model's predictions, it indicates that the complex model has not yet learned features beyond those captured by the simpler baseline. To ensure this bias is specifically toward simplicity (e.g., linearity) rather than just any model with similar accuracy, the authors compared their results against a "null model"—a random classifier with equivalent accuracy.
Key Insights and Results
The study's findings, illustrated in the figure below, reveal a consistent pattern across various tasks, including Binary MNIST, CIFAR-10, and synthetic high-dimensional sinusoids.
- The "Linear First" Phase: In the early stages of training, nearly all performance gains are attributable to the network learning a function highly correlated with a simple linear classifier. Quantitatively, $\mu_Y(F; L)$ was found to be nearly equal to the total mutual information $I(F; Y)$ during this phase.
- Information Retention: As training progresses, the network does not discard the simple patterns it initially learned. Even after reaching zero training error by fitting noisy data points, the underlying "simple" core remains stable and continues to drive generalization.
- The Complexity Hierarchy: Learning occurs in stages. The network first approximates a linear model, then a shallow convolutional neural network (CNN), and finally a deep architecture like a ResNet. Complexity is effectively layered upon a simple foundation.
Discussion and Future Work
The paper provides both experimental evidence and theoretical support for this simplicity bias. A mathematical proof for a simplified linear model demonstrates that starting near a "simple" solution allows SGD to fit data noise without destroying the original generalizing signal.
While these results offer a compelling explanation for generalization, several questions remain. Defining a universal measure of "complexity" for neural networks is still an open challenge. Furthermore, while the paper proves that this trajectory occurs, the precise mathematical mechanism of why SGD prefers this path—the "mechanism of simplicity"—requires further investigation. Future work will also look to extend these binary classification findings more extensively to multi-class problems.
Summary updated