  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.
