SGD on Neural Networks Learns Functions of Increasing Complexity.

Dimitris Kalimeris, Gal Kaplun, Preetum Nakkiran, Benjamin L. Edelman, Tristan Yang, Boaz Barak, Haofeng Zhang

TL;DR

This paper investigates why deep neural networks trained with Stochastic Gradient Descent (SGD) generalize well, even when over-parameterized. They propose and provide evidence for the hypothesis that SGD first learns simple, often linear, functions and then progressively learns more complex ones, retaining the simpler functions throughout.

What Problem Does This Paper Address?

Despite the remarkable success of deep neural networks in various domains, a fundamental theoretical understanding of why they generalize so well remains elusive. Classical generalization bounds often fail to provide meaningful guarantees for these models, and it's known that "bad" empirical risk minimizers exist that fit training data perfectly but perform poorly on unseen data. This suggests that the learning algorithm itself, particularly SGD, plays a crucial role in achieving good generalization. The paper aims to shed light on this "implicit regularization" by exploring the dynamics of SGD during training.

Methods

The core of the paper's methodology lies in a novel information-theoretic measure to quantify how much of a complex classifier's performance can be explained by a simpler one. They define "performance correlation" using conditional mutual information, denoted as $\mu_\gamma(F; L)$. This measure quantifies the overlap in predictive power between two classifiers, $F$ (the neural network) and $L$ (a simpler baseline, often linear).

The authors then use this measure to test two main claims:

  1. Claim 1 (Linear Learning): In the early stages of training, the performance of an SGD-trained neural network ($F_t$) is largely explained by a linear classifier ($L$).
  2. Claim 2 (Retention): Once SGD finds a good, simple classifier, it tends to retain its performance contribution even as training continues to fit the data more complexly.

They also introduce a theoretical result in a simplified linear model to provide provable evidence for Claim 2.

Datasets

The paper uses a combination of real-world and synthetic datasets for binary classification tasks:

  • Binary MNIST: Distinguishing between digits {0, 1, 2, 3, 4} and {5, 6, 7, 8, 9}.
  • CIFAR-10 Animals vs Objects: Distinguishing between animal and object classes.
  • CIFAR-10 First 5 vs Last 5: Distinguishing between classes {0, 1, 2, 3, 4} and {5, 6, 7, 8, 9}.
  • High-dimensional sinusoid: A synthetic task involving a sign function of a linear combination and a sine wave.

They also use convolutional neural networks (CNNs) and Multi-layer Perceptrons (MLPs) with standard architectures and uniform Xavier initialization.

Key Insights and Ideas

  • SGD's "Linear Bias": The most striking finding is that in the initial phases of training, the performance gains of SGD on neural networks are almost entirely attributable to a linear classifier. This suggests SGD has an inherent bias towards learning simple, linear representations first.
  • Progressive Complexity: As training progresses, SGD learns functions of increasing complexity. This is evidenced by the $\mu_\gamma(F_t; G_i)$ curves plateauing at different levels for increasingly complex baseline classifiers ($G_i$), indicating that the neural network's performance is explained by progressively more sophisticated functions.
  • Retention of Simpler Functions: Crucially, the paper shows that once a simple classifier (like a linear one) contributes significantly to performance, this contribution is retained even when training continues to achieve zero training error. This helps explain why overfitted models can still generalize.
  • Mutual Information as a Measure of Explanation: The use of conditional mutual information provides a principled way to quantify how much one classifier "explains" another's performance, going beyond simple correlation.

Key Results

  • Claim 1 Supported: Across multiple datasets and architectures, experiments show that $\mu_\gamma(F_t; L) \approx I(F_t; Y)$ in the early training phase, meaning the performance of the neural network $F_t$ is well-explained by a linear classifier $L$. This holds until the neural network's performance approaches that of the best linear classifier.
  • Claim 2 Supported: For $t > T_0$ (where $T_0$ is the step where linear performance is reached), $\mu_\gamma(F_t; L)$ plateaus near $I(L; Y)$, indicating that the contribution of the linear classifier is retained. This was also supported by a theoretical result in a simplified linear setting.
  • Progressive Complexity Demonstrated: In experiments with increasingly complex CNNs as baseline classifiers, the $\mu_\gamma(F_t; G_i)$ curves showed a separation in phases, with each successive plateau corresponding to the performance of a more complex baseline.
  • Qualitative Behavior: Table 1 summarizes that train and test accuracy, and $I(F; Y)$ generally increase in the first phase, while $\mu_\gamma(F_t; L)$ increases and then plateaus, and $I(F; Y|L)$ decreases. In the overfitting regime, train accuracy increases, test accuracy stabilizes, and $\mu_\gamma(F_t; L)$ remains constant, indicating no forgetting of simpler functions.

Limitations and Future Work

  • Measure of Complexity: The paper acknowledges that defining a universal "measure of complexity" for Conjecture 1 is challenging and may depend on the distribution, architecture, and initialization. The use of layer count for CNNs is an approximation.
  • "Why" of Linear Learning: The paper poses the question of why SGD exhibits this "linear learning" behavior as an important direction for future work.
  • Generalization of Complex Functions: While the paper supports the idea of increasing complexity, a formal understanding of how more complex functions learned by SGD generalize is still an open area.
  • Initialization Dependence: While the paper focuses on standard initializations, they note that adversarial initializations can break the observed inductive bias, suggesting initialization plays a critical role.
  • Theoretical Extension: The theoretical result is for a simplified linear setting. Extending this to non-linear models and more complex architectures is a natural next step.
  • Multi-class Classification: The current work focuses on binary classification, though preliminary results suggest the findings extend to multi-class settings.

Summary updated

Abstract

We perform an experimental study of the dynamics of Stochastic Gradient Descent (SGD) in learning deep neural networks for several real and synthetic classification tasks. We show that in the initial epochs, almost all of the performance improvement of the classifier obtained by SGD can be explained by a linear classifier. More generally, we give evidence for the hypothesis that, as iterations progress, SGD learns functions of increasing complexity. This hypothesis can be helpful in explaining why SGD-learned classifiers tend to generalize well even in the over-parameterized regime. We also show that the linear classifier learned in the initial stages is ``retained'' throughout the execution even if training is continued to the point of zero training error, and complement this with a theoretical result in a simplified model. Key to our work is a new measure of how well one classifier explains the performance of another, based on conditional mutual information.
BibTeX
@inproceedings{kalimeris2019sgd,
  author = {Dimitris Kalimeris and Gal Kaplun and Preetum Nakkiran and Benjamin L. Edelman and Tristan Yang and Boaz Barak and Haofeng Zhang},
  title = {{SGD on Neural Networks Learns Functions of Increasing Complexity.}},
  booktitle = {NeurIPS},
  year = {2019},
  url = {https://openreview.net/forum?id=HHzeNG_4bEL},
}
Figure