SGD on Neural Networks Learns Functions of Increasing Complexity

Preetum Nakkiran; Gal Kaplun; Dimitris Kalimeris; Tristan Yang; Benjamin L. Edelman; Fred Zhang; Boaz Barak

Source-linked AI summary

SGD on Neural Networks Learns Functions of Increasing Complexity

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

arXiv:1905.11604v1May 28, 2019cs.LGcs.NEstat.ML

TL;DR

The paper asks how SGD can produce generalizing classifiers in over-parameterized neural networks despite limited theoretical understanding of complexity and implicit regularization. It studies SGD dynamics using a conditional-mutual-information measure of classifier performance attribution and finds evidence that learning progresses from simpler, often linear functions to more complex ones while retaining earlier information.

Problem
The paper addresses the limited understanding of why over-parameterized neural networks trained by SGD generalize and what notion of implicit complexity SGD uses.
Method
The paper combines experiments across synthetic and real classification tasks with a mutual-information-based measure of how much a simple classifier explains a neural network’s prediction success, plus a simplified theoretical model.
Results
SGD initially learns functions whose performance is well explained by linear classifiers, then learns increasingly complex functions while retaining correlation with simpler classifiers through overfitting.
Takeaways & Limitations
The findings provide a framework for understanding SGD’s inductive bias as progressively increasing classifier complexity while preserving earlier generalizable information.
Takeaways & Limitations
The correct complexity measure remains unresolved, and phase separation is less clear in deeper CNNs because architecture depth may not perfectly represent simplicity.

Abstract

from arXiv · show

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.

1 Introduction

The paper investigates why SGD-trained over-parameterized neural networks can generalize, proposing that SGD initially learns simple, often linear functions and later adds complexity while retaining earlier information.

Motivation: SGD generalization remains poorly understood because classical bounds can fail for large neural networks trained on relatively few examples.The paper frames the gap around implicit regularization and the unclear notion of complexity produced by SGD.
Thesis: The authors hypothesize that SGD initially favors simple classifiers, then learns more complex functions while retaining information from the initial classifier.This thesis links early simplicity and later retention to the dynamics of SGD.
Main claims: In natural settings, early performance gains can be attributed almost entirely to a function correlated with a linear classifier, while later training can fit all training samples without losing that correlation.The claims apply to practical architectures, random initialization, and data distributions, including vanilla SGD without explicit simplicity-promoting methods.
Scope: The framework extends conceptually beyond linear classifiers, with complexity phases that may overlap and depend on the algorithm, initialization, and architecture.The paper also notes that its main empirical focus is binary classification, although the definitions can extend to multiclass settings.
Method: The paper introduces a mutual-information-based measure of how much one classifier explains another classifier’s prediction success.The measure is intrinsic to the classification function and data distribution rather than the classifier’s representation or behavior outside the data distribution.

2 Performance Correlation via Mutual Information

The paper defines performance correlation using mutual information to measure how much of a complex classifier’s predictive success can be attributed to a simpler classifier. It formalizes the claim that SGD first learns linear structure and retains it later.

Performance correlation via mutual information: The framework compares a simple classifier’s contribution to the performance of a more complex classifier using mutual information and conditional mutual information.Conditional mutual information measures the predictive information supplied by the complex classifier beyond the simple classifier.
Performance correlation via mutual information: Accuracy and mutual information are monotonically related for the binary setting, so mutual information provides an equivalent qualitative measure of prediction success.The paper also uses empirical mutual information between training predictions and labels as a proxy for training-set success.
Performance correlation via mutual information: Performance correlation is defined as µ_Y(F; L) = I(F; Y) − I(F; Y | L) = I(L; Y) − I(L; Y | F).It is upper bounded by the smaller of I(L; Y) and I(F; Y).
Performance correlation via mutual information: When µ_Y(F; L) = I(F; Y), the complex classifier adds no predictive information after observing the simpler classifier.The paper therefore interprets µ_Y(F; L) as the portion of F’s performance attributable to L when L is simpler.
Formalized SGD claims: Claim 1 states that, through an initial phase t ≤ T0, nearly all of SGD’s performance is explained by a linear classifier, until the network approximately matches its performance.Claim 2 states that this contribution later plateaus near I(L; Y) and remains substantial even when training fits the training set.
Formalized SGD claims: The mutual-information identity follows from applying the chain rule to I(F, L; Y) in two equivalent ways.The paper notes that the performance-correlation interpretation can be complicated because µ_Y(F; L) may sometimes be negative, although weak practical assumptions ensure non-negativity.

3 SGD Learns a Linear Model First

Experiments on real and synthetic binary tasks test whether SGD learns linear structure first and retains it as training continues. Across tasks, early performance is closely explained by a linear classifier, while later learning proceeds beyond that regime without discarding the earlier contribution.

Experimental setup: The experiments evaluate SGD dynamics on binary MNIST, two CIFAR-10 tasks, and a high-dimensional sinusoid using CNNs or MLPs.Training uses vanilla SGD, binary cross-entropy, Xavier initialization, and no regularization.
Experimental setup: Each SGD-trained classifier is compared with a linear classifier selected as optimal when unique, or fitted to the network at the best linear-performance point when not unique.The authors emphasize that finding a linear classifier explaining most of the network’s performance is non-trivial.
Early linear learning: During the first phase t ≤ T0, µ_Y(F_t; L) is close to I(F_t; Y), indicating that most network performance is attributable to the linear classifier.T0 is the first step at which network performance reaches the linear model’s performance.
Early linear learning: The early-stage bias is specific to linear functions: for CIFAR (iii), the linear model ratio is 0.80 versus 0.31 for a matched-information random classifier.This comparison distinguishes linear learning from a general bias toward arbitrary accurate functions.
Retention and increasing complexity: After the linear phase, the contribution of the linear classifier plateaus near I(L; Y) rather than shrinking, supporting retention as SGD continues fitting data.The paper reports this qualitative behavior across datasets and architectures, under random or non-pathological initialization.
Retention and increasing complexity: The results support a separation of learning phases in which SGD initially learns simpler functions and later moves beyond linear learning toward more complex structure.The paper notes that larger CNNs show less clear phase separation, possibly because depth is not a perfect proxy for simplicity.

4 Beyond Linear: SGD Learns Functions of Increasing Complexity

The paper extends its analysis beyond linear classifiers, proposing that SGD learns successively more complex functions over time. Experiments on CIFAR support phase-separated learning and show that simpler functions remain retained during overfitting, though complexity is difficult to define precisely.

Beyond Linear: The authors conjecture that increasingly complex functions explain successive phases of SGD training.Each function is expected to explain the model up to a transition time, after which the model captures more complex behavior.
Beyond Linear: The correct complexity measure may depend on the data distribution, architecture, and initialization, so the paper uses convolutional-layer count as a proxy in image classification.The authors explicitly state that their conjecture is difficult to establish in full generality.
Experimental Setup: The experiment trains an 18-layer pre-activation ResNet on CIFAR First 5 vs. Last 5 and compares it with 2-, 4-, and 6-layer convolutional models.The task lacks a high-accuracy linear classifier, while the ResNet exceeds 90% accuracy.
Results and Discussion: All conditional-model curves initially track the full model, then successively plateau as training progresses, supporting phase-separated learning.The result extends the earlier linear-model analysis to more complex classifiers.
Results and Discussion: The simpler models’ mutual information remains flat during overfitting, indicating that SGD retains simpler functions rather than forgetting them.The 4- and 6-layer models show less clear phase separation than the 2-layer model and linear classifier.

5 Overfitting Does Not Hurt Generalization

The paper studies why continued SGD training can reach zero training error without destroying generalization. In a simplified overparameterized model, SGD fits the training set while preserving the performance of a simple initial classifier, and the theorem gives a precise version of this behavior.

Model: The authors construct an overparameterized linear setting where noisy sample components permit poor empirical risk minimizers despite a simple signal component.The data distribution separates a sparse signal from an orthogonal noisy component that can be memorized.
Model: The model uses n=o(d) samples and minimizes empirical square loss with SGD.This places the analysis in a heavily overparameterized regime.
Theoretical Result: Theorem 1 states that, under bounded initialization near the simple classifier, sample accuracy approaches 1 while population accuracy approaches 1−p.The guarantee holds with high probability as the number of gradient steps tends to infinity.
Theoretical Result: The proof argues that SGD’s displacement lies in the span of sparse sample vectors, which is nearly orthogonal to the population, while the signal coordinate approaches a constant.This explains how exact fitting can coexist with preserved population performance.
Theoretical Result: For a good bounded initialization, the conditional mutual information associated with the initial simple model barely decreases in the long term.This formalizes retention of the initial classifier in the simplified setting.

6 Discussion and Future Work

The findings suggest that SGD begins by learning an essentially linear classifier and increases classifier complexity as training progresses. The paper presents this as an initial framework for understanding generalization, while identifying the mechanism and correct complexity measure as open problems.

Discussion: The experiments suggest that SGD increases the complexity of the learned classifier over time, beginning with an essentially linear classifier.This is presented as insight into the inductive bias of SGD on deep neural networks.
Future Work: The authors identify explaining the early linear-learning phase and formalizing the correct complexity measure as major directions for future work.They seek a complexity measure that would imply generalization.

A Proof of Theorem 1

The proof characterizes the limit of SGD for a sparse, noisy linear classification model. Under the stated assumptions, the limiting classifier fits the sample while achieving population accuracy near the signal-limited level 1−p.

Assumptions: The proof assumes label noise in a fraction p of samples and distinct non-first nonzero coordinates across data points.These assumptions create a sparse structure that separates signal from sample-specific components.
Convergence: Because the objective is strongly convex, appropriately stepped SGD and gradient descent converge to a global minimum.The analysis therefore focuses on characterizing the limiting solution.
Convergence: Gradient descent remains in the affine space defined by initialization plus the row span of the data matrix and solves the constrained least-squares problem there.The candidate limit is shown to be the optimal solution in this space.
Limiting Solution: The matrix XXT is nonsingular under the orthogonality assumption, enabling the explicit limiting solution and its coordinate formulas.The proof uses the identity XXT=I+ssT and then applies the Sherman–Morrison formula.
Accuracy: With high probability, sample accuracy approaches 1 and population accuracy approaches 1−p as gradient steps tend to infinity.For sufficiently large dimension, the classifier is correct on a population fraction approaching 1−p.
Accuracy: Chebyshev’s inequality controls the contribution of non-signal coordinates, while the population argument considers an unseen nonzero coordinate.These steps establish the asymptotic classification behavior.

B Experimental Setup and Results for Sections 3 and 4

The experiments evaluate SGD on four binary classification tasks using MLPs and CNNs, comparing neural-network predictions with simple classifiers through performance correlation and conditional mutual information. The setup uses repeated random initializations and unregularized vanilla SGD.

Datasets: The study uses Binary MNIST, two CIFAR-10 binary tasks, and a high-dimensional sinusoid with differing linear-classifier accuracy.The CIFAR First 5 vs Last 5 task has best linear accuracy of ≈58%, while Binary MNIST, Animals vs Objects, and High-dimensional Sinusoid admit ≈87%, ≈75%, and ≈80% accuracy, respectively.
Models: Experiments use a 2-layer ReLU MLP for the sinusoid and a convolutional network for MNIST and CIFAR tasks.The CNN has four convolutional layers with 32 filters each, followed by pooling and dense layers.
Training: Neural networks are initialized with Uniform Xavier and trained with vanilla SGD without regularization to isolate optimization effects.Batch sizes and learning rates differ between MLP and CNN experiments.
Reported results: Tables 2 and 3 report performance correlations for linear or simple CNN models against accuracy-matched null models.The tables provide additional quantitative results for the experiments in Sections 3 and 4.
Explanatory models: Linear explanatory classifiers are trained with SGD on task labels, while task (iii) uses labels produced by the network’s initial outputs.For later-stage analysis, simple models are trained on the final network’s training-set predictions.
Evaluation: Performance correlation is assessed with mutual-information quantities estimated from the empirical joint distribution of predictions and true labels on the test set.Conditional mutual information measures the additional label-prediction information supplied by one classifier given another.

C Additional Plots

Additional plots illustrate how SGD-trained decision boundaries evolve on synthetic Gaussian classification tasks and how initialization affects subsequent training behavior.

Figure 6: On a one-dimensional Gaussian task with 10% label noise, the network’s early boundary becomes highly nonlinear outside the training set while agreeing strongly with a linear classifier.The plot distinguishes functional agreement on the data distribution from literal linearity everywhere.
Figure 7: On a two-dimensional Gaussian task with 10% label noise, the decision boundary becomes more linear initially before overfitting the noisy labels.The blue neural-network boundary is compared across training stages.
Figure 8: Two initializations with 88% training accuracy exhibit different subsequent behavior, contrasting a good initialization obtained after SGD with a bad initialization fitted to random labels.The comparison isolates initialization as a factor in training dynamics.