# On the Generalization Mystery in Deep Learning

Satrajit Chatterjee and Piotr Zielinski  Email<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

The generalization mystery in deep learning is the following: Why do over-
parameterized neural networks trained with gradient descent (GD) generalize
well on real datasets even though they are capable of fitting random datasets
of comparable size? Furthermore, from among all solutions that fit the
training data, how does GD find one that generalizes well (when such a well-
generalizing solution exists)?

We argue that the answer to both questions lies in the interaction of the
gradients of different examples during training. Intuitively, if the per-
example gradients are well-aligned, that is, if they are coherent, then one
may expect GD to be (algorithmically) stable, and hence generalize well. We
formalize this argument with an easy to compute and interpretable metric for
coherence, and show that the metric takes on very different values on real and
random datasets for several common vision networks. The theory also explains a
number of other phenomena in deep learning, such as why some examples are
reliably learned earlier than others, why early stopping works, and why it is
possible to learn from noisy labels. Moreover, since the theory provides a
causal explanation of how GD finds a well-generalizing solution when one
exists, it motivates a class of simple modifications to GD that attenuate
memorization and improve generalization.

Generalization in deep learning is an extremely broad phenomenon, and
therefore, it requires an equally general explanation. We conclude with a
survey of alternative lines of attack on this problem, and argue that the
proposed approach is the most viable one on this basis.

###### Contents

  1. 1 Introduction
  2. 2 The Theory, Informally
  3. 3 An Illustrative Example
  4. 4 Metrics to Quantify Coherence
  5. 5 Bounding the Generalization Gap with $\alpha$
  6. 6 Measuring $\alpha$ on Real and Random Datasets
  7. 7 From Measurement to Control: Suppressing Weak Descent Directions
  8. 8 Why are Some Examples (Reliably) Learned Earlier?
  9. 9 Learning With Noisy Labels
  10. 10 Depth, Feedback Loops, and Signal Amplification
  11. 11 What Should a Theory of Generalization Look Like?
  12. 12 Comparison with Other Theories and Explanations
  13. 13 Discussion and Directions for Future Work
  14. A Mathematical Properties of $\alpha$
  15. B Comparison of $\alpha$ with Other Metrics
  16. C Proof of The Generalization Theorem
  17. D Methods to Measure $\alpha$
  18. E Measuring $\alpha$ on Additional Datasets and Architectures
  19. F The Evolution of Coherence
  20. G Experimental Details of Easy and Hard Examples
  21. H The Under-Parameterized Case: A Preliminary Look
  22. I Additional Data

##  1\. Introduction

In spite of the tremendous practical success of deep learning, we do not yet
have a good understanding of why it works. Deep neural networks used in
practice are over-parameterized, that is, they have many more parameters than
the number of examples that are used to train them, and conventional wisdom
holds that such over-parameterized models should not generalize well, but yet
they do.111No less an authority than von Neumann is reported to have said,
“With four parameters I can fit an elephant, and with five I can make him
wiggle his trunk” (Mayer et al., 2010).

Although this gap in our understanding has been long known (see, for example,
Bartlett (1996) and Neyshabur et al. (2014)), the problem was sharpened in an
influential paper by Zhang et al. (2017) who showed that typical neural
networks trained with stochastic gradient descent, which is the usual training
method, can easily memorize a random dataset of the same size as the (real)
dataset that they were designed for. They argued that this simple experimental
observation poses a challenge to all known explanations of generalization in
deep learning, and called for a “rethinking” of our approach. This led to a
large effort in the community to better understand why neural networks
generalize. However, although our understanding of deep learning has greatly
improved as a result of this effort, to date, there does not appear to be an
satisfactory explanation (see Zhang et al. (2021) for a detailed review).

Our goal in this work is to answer the broad question raised by the
observations of Zhang et al., namely, M

Why do neural networks generalize well in practice when they have sufficient
capacity to memorize their training set?

M
Specifically, we want to answer the following questions:

  1. Q1.

Since by simply changing the dataset in an over-parameterized setting (for
example, from real labels to random labels), we can obtain very different
generalization performance, what property of the dataset controls the
generalization gap (assuming, of course, that architecture, learning rate,
size of training set, etc. are held fixed)? We stress that our interest is in
the gap, that is the difference between training and test loss (and not in the
test loss per se).

  2. Q2.

Why does gradient descent not simply memorize real training data as it does
random training data? That is, from among all the models that fit the training
set perfectly in an over-parameterized setting, how does gradient descent find
one that generalizes well to unseen data when such a model exists? This
property is often called the implicit bias of gradient descent.222 It is an
implicit bias because even in the absence of explicit regularizers (such as
weight decay or drop out), gradient descent still generalizes well (where
possible).

Most previous attempts to make progress on these questions have been based on
the notion of uniform convergence (Vapnik and Chervonenkis, 1971), the primary
theoretical tool in classical learning theory. However, a recent paper by
Nagarajan and Kolter (2019b) provides a strong argument for why any method
based on uniform convergence is unlikely to provide an explanation to the
mystery.

In this work, we study the generalization mystery from the less-explored, but
arguably more general, perspective of algorithmic stability (Devroye and
Wagner, 1979; Bousquet and Elisseeff, 2002). We propose that the answer to
both the questions lies in the interaction of the gradients of the examples
during training. (The interaction of per-example gradients has not received
much attention in the literature, with notable exceptions being Yin et al.
(2018); Fort et al. (2020); Sankararaman et al. (2020); Liu et al. (2020c);
Mehta et al. (2021) which we discuss later.)

Specifically, we argue,

  1. A1.

Gradient descent in an over-parameterized setting generalizes well when the
gradients of different examples (during training) are similar, that is, when
there is coherence.

  2. A2.

When there is coherence, the dynamics of gradient descent leads to models that
are stable, (that is, to models that do not depend too much on any one
training example), and stable models generalize well.

In this paper, we advance a theory along these lines, which we call the theory
of Coherent Gradients.333Some preliminary results appeared in Chatterjee
(2020); Zielinski et al. (2020); Chatterjee and Zielinski (2020).

##  2\. The Theory, Informally

The motivation for our theory comes from the observation that the ability to
memorize random datasets, and yet generalize well on real datasets is not
unique to deep neural networks, but also seen, for example, with decision
trees (and random forests). But there is no generalization mystery there: a
typical tree construction algorithm splits the training set recursively into
similar subsets based on input features. If no similarity is found,
eventually, each example is put into its own leaf to achieve good training
accuracy, but, of course, at the cost of poor generalization. Thus, trees that
achieve good training accuracy on a randomized dataset are larger than those
on a real dataset (for example, see Expt. 5 in (Chatterjee and Mishchenko,
2020)).

We propose that something similar happens with neural networks trained with
gradient descent (GD): M

Gradient descent exploits patterns common across training examples during the
fitting process, and if there are no common patterns to exploit, then the
examples are fitted on a “case-by-case” basis.

M
Intuitively, this provides a uniform explanation of memorization and
generalization: If a dataset is such that examples are fitted on a case-by-
case basis, then we expect poor generalization (it corresponds to
memorization), whereas, if there are common patterns that can be exploited to
fit the data, then we should expect good generalization.

So how does gradient descent exploit common patterns to fit the training data
(when such common patterns exist)? Since the only interaction between examples
in gradient descent is in the parameter update step, the mechanism for
commonality exploitation—if it exists—must be there. Let $\eta$ be the
learning rate and let $g_{i}(w_{t})$ be the gradient for the $i$th training
example at the point $w_{t}$ in parameter space. Furthermore, for now, assume
that the $g_{i}(w_{t})$ all have the same scale (we discuss the consequences
of relaxing this shortly). Now, consider the parameter update at step $t$ of
gradient descent:444For simplicity of exposition, here we only consider the
full-batch case and no batch normalization. For the stochastic case, we have
to consider the expected gradient, but the argument carries over, as we shall
see shortly in the formal development.

$w_{t+1}\equiv w_{t}-\eta\,\frac{1}{m}\sum_{i=1}^{m}g_{i}(w_{t})$

If $g(w_{t})$ denotes the average gradient, that is,
$g(w_{t})\equiv\frac{1}{m}\sum_{i=1}^{m}g_{i}(w_{t})$, we observe the
following:

  1. (1)

The average gradient $g(w_{t})$ is stronger in directions (components) where
the per-example gradients are “similar,” and reinforce each other; and weaker
in other directions where they are different, and do not add up (or perhaps
cancel each other).

  2. (2)

Since network parameters $w_{t+1}$ are updated proportionally to gradients,
those parameters that correspond to stronger gradient directions change more.

Therefore, the parameter changes of the network are biased towards those that
benefit multiple examples.

When per-example gradients reinforce each other, we say they are “coherent,”
and use the term coherence to informally refer to the similarity of per-
example gradients (either in aggregate across entire gradients or on a per-
component basis).

Note that it is possible that there are no directions or components where
different per-example gradients add up, that is, there is no coherence. That
case would correspond to fitting each example independently, that is, on a
case-by-case basis. In other words, reducing loss on one example fails to
reduce the loss on any other example. Intuitively, one might expect this to be
the case for random datasets, and only possible when the learning problem is
over-parameterized: the dimensionality of the tangent space (that is, the
dimension of the gradient vectors) is greater than the number of training
examples.

M

We can reason about the generalization of the above process through the notion
of algorithmic stability (Bousquet and Elisseeff, 2002; Devroye and Wagner,
1979). A learning process is stable if a replacing one example in the training
sample by another example (from the example distribution) does not change the
learned model too much. It can be shown that models obtained through stable
processes generalize well.

Strong directions in the average gradient are stable since in those directions
multiple examples support or reinforce each other. In particular, the absence
or presence of a single example in the training set does not impact descent
down a strong direction since other examples contribute to it anyway.
Therefore, by stability theory, the corresponding parameter updates should
generalize well, that is, they would lead to lower loss on unseen examples as
well.

On the other hand, weak directions in the average gradient are unstable, since
they are due to a few or even single examples. In the latter case, for
example, the absence of the corresponding example in the training set would
prevent descent down that direction, and therefore, the corresponding
parameter updates would not generalize well.

With this observation, we can reason inductively about the stability of GD:
since the initial values of the parameters do not depend on the training data,
the initial function mapping examples to their gradients is stable. Now, if
all parameter updates are due to strong gradient directions, then stability is
preserved. However, if some parameter updates are due to weak gradient
directions, then stability is diminished. Now, since stability (suitably
formalized) is equivalent to generalization (Shalev-Shwartz et al., 2010),
this allows us to see how generalization may degrade as training
progresses.555Based on this insight, we shall see later how a simple
modification to GD to suppress the weak gradient directions can dramatically
reduce overfitting. In summary: M

When there is coherence, the dynamics of gradient descent, particularly the
use of the average gradient, leads to models that are stable, that is, to
models that do not depend too much on any one training example.

M

Of course, in general, there can be no dataset-independent guarantee of
stability. We can understand the connection between coherence of the dataset
and stability intuitively, by considering two extreme cases. If, on the one
hand, the gradients of all the examples are pointing in the same direction
(that is, we have perfect coherence), then the replacing one training example
by another does not matter, and the loss on the replaced example should still
decrease, even though it was not used for training. On the other hand, if the
gradients of all the examples are all orthogonal to each other (we have low
coherence), then replacing an example with another eliminates the descent down
the gradient direction of the replaced example, and we should not expect loss
to reduce on that example. In other words, in the presence of high coherence,
training on the original training set, and a perturbed version should not
differ too much.

M

This insight suggests a new modification to gradient descent to improve
generalization, and also explains some existing regularization techniques:

  * •

We can make gradient descent more stable by eliminating or attenuating weak
directions by combining per-example gradients using robust mean estimation
techniques (such as median) instead of simple averages.

  * •

We can view $\ell^{2}$ regularization (weight decay) as an attempt to
eliminate movement in weak gradient directions by having a “background force”
that pushes each parameter to a data-independent default value (zero). It is
only in the case of strong directions that this background force is overcome,
and parameters updated in a data-dependent manner.

  * •

Earlier we assumed that all the $g_{i}(w_{t})$ all have the same scale. But
that is not always true. For example, during training, some examples get
fitted earlier than others, and so their gradients become negligible. Now,
fewer examples dominate the average gradient $g(w_{t})$, and this leads to
overfitting since stability is degraded. This may be viewed as a justification
for early stopping as a regularizer.

M

The properties of gradient descent as an optimizer do not play an important
role in our generalization theory. We model gradient descent as a simple,
“combinatorial” optimizer, a kind of greedy search with some hill-climbing
thrown in (due to sampling and finite step size). Therefore, we are concerned
less about the quality of solutions reached at the end of gradient descent,
but more about staying “feasible” at all times during the search. In our
context, feasibility means being able to generalize; and this naturally leads
us to look at the transition dynamics of gradient descent to see if that
preserves generalizability.

A notable feature of this approach is that it does not rely on any special
property of the final solution obtained by gradient descent. Therefore, (1) it
allows us to reason in an uniform manner about generalization with respect to
early stopping and generalization at convergence,666Since stopping early
typically leads to smaller generalization gap, the nature of the solutions of
GD (for example, stationary points, the limit cycles of SGD at equilibrium)
cannot be the ultimate explanation for generalization. In fact, think of the
extreme case where no GD step is taken, and we have zero generalization gap!
and (2) it applies uniformly to convex and non-convex problems (and uniformly
across architectures without requiring simplifying assumptions such as
homogeneous activations, infinite widths, etc.).

##  3\. An Illustrative Example

The main ideas of the theory described above can be illustrated with a simple
thought experiment where we fit an over-parameterized linear model to two toy
datasets, one of which is “real” and the other is “random.”

######  Example 1 (“Real” and “Random”).

Consider the task of fitting the linear model

$y=w\cdot x=\sum_{i=1}^{6}w^{(i)}x^{(i)}$

under the usual square loss $\ell(w)\equiv\frac{1}{2}(y-w\cdot x)^{2}$ to each
of the following datasets:

M

L (“real”)
---
$i$ | $x_{i}$ | $y_{i}$
$1$ | $\langle\,{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}1},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\phantom{-}1}\,\rangle$ | $\phantom{-}1$
$2$ | $\langle\,{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}-1},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}-1}\,\rangle$ | $-1$
$3$ | $\langle\,{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}-1},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}-1}\,\rangle$ | $-1$
$4$ | $\langle\,{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}1},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\phantom{-}1}\,\rangle$ | $\phantom{-}1$
$5$ | $\langle\,{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}-1},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}-1}\,\rangle$ | $-1$
M (“random”)
---
$i$ | $x_{i}$ | $y_{i}$
$1$ | $\langle\,{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}1},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},\phantom{-}0\,\rangle$ | $\phantom{-}1$
$2$ | $\langle\,{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}-1},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},\phantom{-}0\,\rangle$ | $-1$
$3$ | $\langle\,{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}-1},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},\phantom{-}0\,\rangle$ | $-1$
$4$ | $\langle\,{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}1},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},\phantom{-}0\,\rangle$ | $\phantom{-}1$
$5$ | $\langle\,{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}-1},\phantom{-}0\,\rangle$ | $-1$

M

In each dataset, the first four examples, that is, $(x_{i},y_{i})$ for
$i\in[4]$ are used for training whereas the fifth example $(x_{5},y_{5})$ is
held out for evaluating generalization. Observe that the first 5 input
features (shown in pink) are the same in both L and M, and furthermore, that
they are each only predictive for one example (they are “idiosyncratic”). The
last feature however is different in the two datasets. In L (shown in blue),
it is predictive across all examples (“common” feature), whereas in M (shown
in black), it is uninformative. We can think of L as a “real” dataset where
there is something that can be learned by a linear model, whereas M is a
“random” dataset that may at best be memorized.

Now, if we apply gradient descent (GD) to these problems (starting from
$w=0$), we see the following training and test curves:

L | M
---|---
|

In this simple setup, we see the same phenomena as in deep learning: (1) the
model has sufficient capacity to memorize random data (M), yet it generalizes
on real data (L), that is, the generalization is dataset dependent; and (2)
from among all the models that fit L (which includes the solution for M), GD
finds one that generalizes well (instead of just memorizing). However, in
contrast to deep models, it is much easier to understand intuitively what is
going on in this setup, particularly, from the point of view of the dynamics
of GD.

First, consider the per-example gradients $g_{i}(w)$ and the average training
gradient $g(w)$ at a point $w$ on the trajectory of gradient descent starting
from 0:

M

L
---
$i$ | $g_{i}(w)$
$1$ | $r(w)\,\langle\,{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}1},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\phantom{-}1}\,\rangle$
$2$ | $r(w)\,\langle\,{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}1},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\phantom{-}1}\,\rangle$
$3$ | $r(w)\,\langle\,{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}1},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\phantom{-}1}\,\rangle$
$4$ | $r(w)\,\langle\,{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}1},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\phantom{-}1}\,\rangle$
$g(w)$ | $r(w)\,\langle\,{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\frac{1}{4}},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\hskip 7.0pt\frac{1}{4}},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\hskip 7.0pt\frac{1}{4}},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\hskip 7.0pt\frac{1}{4}},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\phantom{-}1}\,\rangle$
M
---
$i$ | $g_{i}(w)$
$1$ | $r(w)\,\langle\,{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}1},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\phantom{-}0}\,\rangle$
$2$ | $r(w)\,\langle\,{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}1},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\phantom{-}0}\,\rangle$
$3$ | $r(w)\,\langle\,{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}1},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\phantom{-}0}\,\rangle$
$4$ | $r(w)\,\langle\,{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}1},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\phantom{-}0}\,\rangle$
$g(w)$ | $r(w)\,\langle\,{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\frac{1}{4}},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\hskip 7.0pt\frac{1}{4}},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\hskip 7.0pt\frac{1}{4}},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\hskip 7.0pt\frac{1}{4}},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\phantom{-}0}\,\rangle$

M

where $r(w)$ is a scalar.777$r(w)$ is equal to $|y_{i}-w\cdot x_{i}|$ for
$i\in[4]$, a quantity that is independent of $i$ for $w$ in the trajectory of
GD due to the symmetries in this problem. Observe that M lacks coherence: the
per-example gradients do not reinforce each other, that is, they do not add up
in any component. Therefore, there are no strong directions in the average
gradient. In contrast, in L, the per-example gradients are coherent: they
share a common component (shown in blue) which “adds up” in the average
gradient $g(w)$, which consequently, is 4 times stronger in that component
than in the other (idiosyncratic) components (shown in pink).

Finally, since parameter changes in GD are proportional to the average
gradient $g(w)$, the parameter $w^{(6)}$ corresponding to the common input
feature in L changes much more than any of the ones for the idiosyncratic
features (for example, $w^{(1)}$)888From symmetry, $w^{(2)},w^{(3)},$ and
$w^{(4)}$ are the same as $w^{(1)}$. during training. In contrast, in M, only
the weights for the idiosyncratic features are used to fit the data. This is
confirmed by looking at the trajectories of $w^{(1)}$ and $w^{(6)}$ during
training:

L | M
---|---
|

To summarize, in this simple example of “real” and “random” datasets that
replicates the generalization mystery of deep learning, we see that:

  1. (1)

The difference in the generalization gap between the two datasets can be
understood in terms of the difference in the similarity of the per-example
gradients, that is, in terms of the difference in coherence.

  2. (2)

In the case of the “random” dataset, the training data was fit on a case-by-
case basis (that is, memorized). Although the same would also have been an
optimal solution for the problem of fitting the “real” training data, gradient
descent produced a different solution by exploiting the commonality between
training examples, as expressed in their gradients.

M

Finally, let us consider a modification to gradient descent where instead of
simply averaging the per-example gradients, we take the component-wise median
gradient $\widetilde{g}(w)$:

M L $i$ $g_{i}(w)$ $1$
$r(w)\,\langle\,{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}1},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\phantom{-}1}\,\rangle$
$2$
$r(w)\,\langle\,{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}1},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\phantom{-}1}\,\rangle$
$3$
$r(w)\,\langle\,{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}1},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\phantom{-}1}\,\rangle$
$4$
$r(w)\,\langle\,{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}1},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\phantom{-}1}\,\rangle$
$\widetilde{g}(w)$
$r(w)\,\langle\,{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\phantom{-}1}\,\rangle$
M $i$ $g_{i}(w)$ $1$
$r(w)\,\langle\,{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}1},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\phantom{-}0}\,\rangle$
$2$
$r(w)\,\langle\,{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}1},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\phantom{-}0}\,\rangle$
$3$
$r(w)\,\langle\,{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}1},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\phantom{-}0}\,\rangle$
$4$
$r(w)\,\langle\,{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}1},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\phantom{-}0}\,\rangle$
$\widetilde{g}(w)$
$r(w)\,\langle\,{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\phantom{-}0}\,\rangle$
M M

It is easy to see that performing gradient descent with the median gradient
$\widetilde{g}(w)$ increases the stability of gradient descent on both
datasets by eliminating the weak gradient directions, and leads to zero
generalization gap for both “real” and “random”.999Note that in the case of
“random,” this reduction in the gap is achieved by preventing the training set
from being memorized.

∎

M

The conventional explanation of generalization in over-parameterized linear
models depends on the observation that GD from 0 finds the solution with
minimum $\ell^{2}$ norm (that is, the solution found by the pseudo-inverse
method). In comparison, the explanation above, based on the alignment of per-
example gradients and stability, is simpler and more direct. Crucially, it
generalizes in a straightforward manner to deep networks where GD does not
always find the minimum $\ell^{2}$ norm solution. Thus, at a fundamental
level, the Coherent Gradients approach allows us to decouple optimization and
generalization; so even if we cannot say anything about the result of the
optimization process after GD, we can say something about whether the solution
generalizes or not by analyzing the per-example gradients along the way.

##  4\. Metrics to Quantify Coherence

So far we have argued, informally, that if the gradients of different training
examples are similar and reinforce each other (that is, if they are coherent),
then the model produced by gradient descent is expected to generalize well;
and we have illustrated this argument with a simple thought experiment. But in
order to test this explanation in practical settings, such as the experiments
of Zhang et al. (2017), we need to quantify the notion of coherence.

An obvious metric to quantify the coherence of the per-example gradients is
their average pairwise dot product. Since this has a nice connection to the
loss function, we start by reviewing the connection, and also set up some
notation in the process. Formally, let $\mathcal{D}(z)$ denote the
distribution of examples $z$ from a finite set $Z$.101010We assume finiteness
for mathematical simplicity since it does not affect generality for practical
applications. For a network with $d$ trainable parameters, let $\ell_{z}(w)$
be the loss for an example $z\sim\mathcal{D}$ for a parameter vector
$w\in\mathbb{R}^{d}$. For the learning problem, we are interested in
minimizing the expected loss
$\ell(w)\equiv\operatorname*{\mathbb{E}}_{z\sim\mathcal{D}}[\ell_{z}(w)]$. Let
$g_{z}\equiv[\nabla\ell_{z}](w)$ denote the gradient of the loss on example
$z$, and $g\equiv[\nabla\ell](w)$ denote the average gradient. From linearity,
we have,

$g=\operatorname*{\mathbb{E}}_{z\sim\mathcal{D}}\ [\ g_{z}\ ]$

Now, suppose we take a small descent step $h=-\eta\,g$ (where $\eta>0$ is the
learning rate). From the Taylor expansion of $\ell$ around $w$, we have,

$\ell(w+h)-\ell(w)\approx g\cdot h=-\eta\ g\cdot
g=-\eta\operatorname*{\mathbb{E}}_{z\sim\mathcal{D}}\ [\ g_{z}\
]\cdot\operatorname*{\mathbb{E}}_{z\sim\mathcal{D}}\ [\ g_{z}\
]=-\eta\operatorname*{\mathbb{E}}_{z\sim\mathcal{D},z^{\prime}\sim\mathcal{D}}\
[g_{z}\cdot g_{z^{\prime}}]$ (1)

where the last equality can be checked with a direct computation. Thus, the
expected pairwise dot product is equal to the change in loss divided by the
learning rate, that is, the “instantaneous” change in loss.

######  Example 2 (Perfect similarity v/s pairwise orthogonal).

Consider a sample with $m$ examples $z_{i}$ where $1\leq i\leq m$. Let $g_{i}$
be the gradient of $z_{i}$ and further that $\|g_{i}\|=\|u\|$ for some $u$.
Let $1\leq j\leq m$. If all the $g_{i}$ are the same, that is, if coherence or
similarity is maximum, then $\operatorname*{\mathbb{E}}\,[g_{i}\cdot
g_{j}]=\|u\|^{2}$. However, if they are pairwise orthogonal, i.e., $g_{i}\cdot
g_{j}=0$ for $i\neq j$, then $\operatorname*{\mathbb{E}}\,[g_{i}\cdot
g_{j}]=(1/m)\|u\|^{2}$.

Observe that the loss reduces $m$ times faster in the case of maximum
coherence than when the gradients are pairwise orthogonal.

∎

As the above example illustrates, the average expected dot product can vary
significantly depending on the similarity of the gradients, and so could be
used as a measure of coherence. However, since it has no natural scale—just
rescaling the loss changes its value—it is difficult to interpret in an
experimental setting. For example, it is not immediately clear if say, a value
of 17.5 for the expected dot product indicates good or bad coherence.

Now, there is a natural scaling factor that can be used to normalize the
expected dot product of per-example gradients. Consider the Taylor expansion
of each individual loss $\ell_{z}$ around $w$ when we take a small step
$h_{z}$ down its gradient $g_{z}$:

$\ell_{z}(w+h_{z})-\ell_{z}(w)\approx g_{z}\cdot h_{z}=-\eta\ g_{z}\cdot
g_{z}$

Taking expectations over $z$ we get,

$\operatorname*{\mathbb{E}}_{z\sim\mathcal{D}}[\ell_{z}(w+h_{z})-\ell_{z}(w)]=-\eta\
\operatorname*{\mathbb{E}}_{z\sim\mathcal{D}}[g_{z}\cdot g_{z}]$ (2)

The quantity in (2) has a simple interpretation: It is the expected reduction
in the per-example loss $\ell_{z}$ if we could take different steps for
different examples. In that sense, it is an idealized reduction in loss that
real gradient descent cannot usually attain. As might be expected intuitively,
it is a bound on the quantity in (1) and is tight when all the per-example
gradients are identical. Thus, it serves as a natural scaling factor for the
expected dot product, and we obtain a normalized metric for coherence, called
$\alpha$, from (1) and (2):

$\boxed{\quad\
\alpha\equiv\frac{\ell(w+h)-\ell(w)}{\displaystyle\operatorname*{\mathbb{E}}_{z\sim\mathcal{D}}\
[\ell_{z}(w+h_{z})-\ell_{z}(w)]}=\frac{\displaystyle\operatorname*{\mathbb{E}}_{z\sim\mathcal{D},z^{\prime}\sim\mathcal{D}}\
[g_{z}\cdot
g_{z^{\prime}}]}{\displaystyle\operatorname*{\mathbb{E}}_{z\sim\mathcal{D}}\
[g_{z}\cdot
g_{z}]}=\frac{\displaystyle\operatorname*{\mathbb{E}}_{z\sim\mathcal{D}}\ [\
g_{z}\ ]\cdot\operatorname*{\mathbb{E}}_{z\sim\mathcal{D}}\ [\ g_{z}\
]}{\displaystyle\operatorname*{\mathbb{E}}_{z\sim\mathcal{D}}\ [g_{z}\cdot
g_{z}]}\quad\ }$ (3)

From the discussion above, it is easy to see that

$0\leq\alpha\leq 1.$

Coherence is 1 when all per-example gradients are identical, and 0 when the
expected gradient is 0, that is, when training converges.111111If all examples
are fit at the end of training, the denominator vanishes. However, in that
case, the numerator is also zero, and we define the coherence to be 0. This is
also consistent with adding a small positive epsilon to the denominator when
computing coherence to avoid division by zero. This choice can also be
justified with a continuity argument (see Appendix A). This is formalized as
Theorem 2 in Appendix A.

######  Example 3 (Orthogonal Sample and Orthogonal Limit).

If we have a sample of $m$ examples whose gradients $g_{i}$ ($1\leq i\leq m$)
are pairwise orthogonal (an “orthogonal” sample), then,

$\alpha=\frac{(1/m)\,{\displaystyle\operatorname*{\mathbb{E}}_{i}\,[g_{i}\cdot
g_{i}]}}{\operatorname*{\mathbb{E}}_{i}\,{\displaystyle[g_{i}\cdot
g_{i}]}}=\frac{1}{m}$

Thus, for an orthogonal sample, $\alpha$ is independent of the actual
gradients, and we call $1/m$ the orthogonal limit for a sample of size $m$,
and denote it by $\alpha^{\perp}_{m}$.

∎

In our experiments, we measure coherence on a sample, as we typically do not
have access to the underlying distribution $\mathcal{D}$. However, as one
might expect, $\alpha$ as measured from a sample is a biased estimator of the
true (that is, the distributional) $\alpha$. To distinguish between the two,
we use $\alpha_{S}$ to denote the estimate of $\alpha$ obtained from a sample
$S$. Since the sample $S$ is often clear from the context, we commonly also
use $\alpha_{m}$ instead of $\alpha_{S}$ where $m$ is the size of $S$ (to
preserve the distinction with $\alpha$ and to remind ourselves of the sample
size dependence).121212Typically, $\alpha_{S}$ overestimates $\alpha$. A
sample $S$ of size 1 provides an extreme example of this, since in that case,
$\alpha_{S}$ is $1$ regardless of $\alpha$. Another example is provided by a
distribution $\mathcal{D}$ where all the per-example gradients have the same
norm, and it is not too hard to see that
$\operatorname*{\mathbb{E}}_{S\sim\mathcal{D}^{m}}[\alpha_{S}]\geq\alpha$.
This is also confirmed by experiments (for example, see Figure 11 in Appendix
D).

In the case of $\alpha$ estimated from a sample, the coherence of a (possibly
fictitious131313If the dimension $d$ of the tangent space is less than $m$,
that is, we have more examples than parameters, then an orthogonal sample of
size $m$ cannot actually be constructed.) orthogonal sample provides a
convenient yardstick to judge the coherence of any other sample of the same
size. So given a sample of size $m$, rather than show $\alpha_{m}$, we show
the ratio $\alpha_{m}/\alpha^{\perp}_{m}=m\,\alpha$. This quantity has a
simple intuitive interpretation: M

The metric $\alpha_{m}/\alpha^{\perp}_{m}$ for coherence measures how many
examples on average (including itself) a given example helps at a given step
of gradient descent.

M
This intuition may be justified by considering different kinds of possible
training samples:

  * •

For an orthogonal sample, $\alpha_{m}=1/m$ and, therefore,
$\alpha_{m}/\alpha^{\perp}_{m}=1$. In this case, each example in the sample is
fitted independently of the others: a step in a direction of any given
example’s gradient does not affect the loss on any other example. Each example
“helps” only itself and does not positively or negatively affect the other
examples in the sample.

  * •

For a sample with perfect coherence (all the examples are identical),
$\alpha_{m}=1$, and we have, $\alpha/\alpha^{\perp}_{m}=m$. Here, each example
in the sample “helps” all the other examples in the sample during gradient
descent.

  * •

At the end of training, when the expected gradient of the sample is 0, either
the loss on a given example cannot be improved, or improving it comes at the
expense of worsening the loss on other examples in the sample. Thus, an
example “helps” no examples (including itself) on average, and
$\alpha_{m}=\alpha_{m}/\alpha^{\perp}_{m}=0$.

  * •

For the $d\ll m$ (under-parameterized) case, consider
$\alpha_{m}/\alpha_{m}^{\perp}$ for a sample that comprises $k\gg 1$ copies of
$d$ orthogonal gradients living in a $d$-dimensional tangent space (that is,
$m=kd\gg d$). Now, $\alpha_{m}$ of this replicated sample is also $1/d$ (since
replicating a sample does not change the empirical distribution) and thus, its
$\alpha_{m}/\alpha_{m}^{\perp}$ is $(1/d)/(1/kd)=k$, which agrees with the
intuition that each example in the replicated sample helps $k$ other examples.

######  Example 4 (“Real” and “Random”).

In Example 1, consider the training sample for L ($m=4$). It is easy to check
with a direct computation that $\alpha_{m}=5/8$ and
$\alpha_{m}/\alpha^{\perp}_{m}=2.5$, that is, each example helps 2.5 examples.
Intuitively, 2.5 may be understood as an example helping reduce the loss on
itself 100%, and reducing the loss on 3 other examples by 50% due to the
common component (the other half comes from their own idiosyncratic
components).

The training sample for M is pairwise orthogonal, and therefore,
$\alpha_{m}/\alpha^{\perp}_{m}=1$. ∎

M

One can imagine many different metrics for coherence. We have seen two so far:
the expected pairwise dot product and $\alpha$. As we will see in the next
section, another metric that arises naturally is

$\operatorname*{\mathbb{E}}_{z\sim\mathcal{D},\,z^{\prime}\sim\mathcal{D}}\,[\|g_{z}-g_{z^{\prime}}\|],$
(4)

and there are other metrics in the literature such as stiffness (Fort et al.,
2020) and GSNR (Liu et al., 2020c). Furthermore, coherence metrics may be
computed at the level of the network (that is, with entire per-example
gradient vectors), or at the level of layers or even individual parameters
(that is, with different projections of the per-example gradients).

Compared to the other metrics, $\alpha$ (and by extension,
$\alpha_{m}/\alpha^{\perp}_{m}$) has certain advantages: It is simultaneously
(1) easy to compute at scale, (2) more interpretable, and (3) has convenient
theoretical properties that, among other things, allows us to provide a
qualitative bound on the generalization gap. However, $\alpha$ is not a
perfect metric and has some significant limitations as we shall see.

##  5\. Bounding the Generalization Gap with $\alpha$

We can now formalize the argument in Section 2 by using $\alpha$ as a metric
of coherence. We build on the work of Hardt et al. (2016) and Kuzborskij and
Lampert (2018) who showed that (small-batch) stochastic gradient descent is
stable since each training example is looked at so rarely, that it cannot have
much influence on the final model if the training is not run for too long (or
the learning rate is decayed quickly enough). Obviously, such a dataset-
independent argument for stability is inapplicable to the generalization
mystery since it rules out memorization.141414In the light of this, the
experiments of Zhang et al. (2017) may be seen as demonstrating that in
practice we run SGD long enough that is it is no longer (unconditionally)
stable. In contrast, we provide a dataset-dependent argument for stability may
be summarized as follows:

coherence $\implies$ stability $\implies$ generalization

In the reverse direction, although it is known that generalization implies
stability, generalization or stability do not imply coherence. There may be
good generalization in spite of low coherence simply by virtue of having many
training examples (for example, under-parameterization) or by training for a
short time.

In this context, our main result is a bound on the expected generalization
gap, that is, the expected difference between training and test loss over all
samples of size $m$ from $\mathcal{D}$ (denoted by
$\operatorname*{gap}(\mathcal{D},m)$) in terms of $\alpha$. In its most
general form, where we make no assumption on the learning rate schedule, it is
as follows:

######  Theorem 1 (Generalization Theorem).

If (stochastic) gradient descent is run for $T$ steps on a training set
consisting of $m$ examples drawn from a distribution $\mathcal{D}$, we have,

$\displaystyle|\operatorname*{gap}(\mathcal{D},m)|\leq\frac{L^{2}}{m}\
\sum_{t=1}^{T}[\eta_{k}\,\beta]_{k=t+1}^{T}\cdot\eta_{t}\cdot\sqrt{2\
(1-\alpha(w_{t-1}))}$ (5)

where $\alpha(w)$ denotes the coherence at a point $w$ in the parameter space,
$w_{t}$ the parameter values seen during gradient descent, $\eta_{t}$ is the
step size at step $t$,

$[\eta_{k}\,\beta]_{k=t_{0}}^{t_{1}}\equiv\prod_{k=t_{0}}^{t_{1}}(1+\eta_{k}\,\beta),$

and $L$ and $\beta$ are certain Lipschitz constants.

###### Proof.

Please see Appendix C for the full formal statement and the proof. ∎

Like Hardt et al. (2016), our bound depends on the length of training (shorter
the training, better the generalization), and the size of the training set
(more the examples, better the generalization).151515In fact, when $m$ is
large, even with random data, we can have good generalization since we are
interested in the gap, and not just test loss—fitting the training set gets
harder with larger $m$. Although natural, this inverse dependence on $m$ does
not usually hold for bounds based on uniform convergence as was pointed out by
Nagarajan and Kolter (2019b). However, unlike Hardt et al. (2016), the bound
also depends on the coherence as measured by $\alpha$ during training (greater
the coherence, better the generalization). Due to the presence of the
“expansion” term $[\eta_{k}\,\beta]_{k=t+1}^{T}$, an interesting qualitative
aspect of this dependence is that high coherence early on in training is
better than high coherence later on. Also in contrast to Hardt et al. (2016),
our bound applies in an uniform manner to the stochastic and the full-batch
case in the general non-convex setting.161616In fact, since our analysis is in
expectation, the size of the minibatch drops out of the bound.

We emphasize that as with most theoretical generalization bounds in deep
learning, our bound is extremely loose, and is therefore only useful in a
qualitative sense. This is not only due to the Lipschitz constants. The
coherence term based on $\alpha$ only plays a strong role when it is close to
1, but as we shall see in the next section, $\alpha$ on real datasets is quite
far from 1. We believe that this is because $\alpha$, being an average over
the entire network, is a rather blunt instrument, and conjecture that a
tighter bound may be obtained in terms of layer-wise coherences, or perhaps
better yet, in terms of “minimum coherence cuts” of the network.

The proof of the theorem follows the iterative framework introduced in Hardt
et al. (2016). We analyze the evolution of two models under stochastic
gradient descent, one trained on the original training set, and another
trained on a perturbed training set where the $i$th training example ($z_{i}$)
is replaced with a different one from the data distribution (call it
$z_{i}^{\prime}$). When a minibatch with the $i$th example is encountered, the
two models diverge (further) due to the different gradients, and this
divergence (in expectation) is bounded by (4). This, in turn, is bounded by
$\alpha$ as follows (see Lemma 6):

$\operatorname*{\mathbb{E}}_{z\sim\mathcal{D},\,z^{\prime}\sim\mathcal{D}}\,[\|g_{z}-g_{z^{\prime}}\|]\leq\sqrt{2\
(1-\alpha)\operatorname*{\mathbb{E}}_{z\sim\mathcal{D}}\ [g_{z}\cdot g_{z}]}.$

##  6\. Measuring $\alpha$ on Real and Random Datasets

Figure 1. An experiment in the spirit of Zhang et al. (2017) illustrating the
generalization mystery in deep learning. We train two ResNet-50 models, one on
ImageNet with original labels (“real”, top row), and another on ImageNet with
images replaced by Gaussian noise (“random”, bottom row) using vanilla SGD and
no explicit regularization. As the loss and accuracy curves (first two
columns) show, the network has sufficient capacity to memorize the training
data, yet, it generalizes in one case and not the other. We believe that the
reason for this difference in behavior can be found by analyzing the
similarity between per-example gradients during training, that is, coherence.
Using the $\alpha/\alpha_{m}^{\perp}$ metric for coherence (last two columns),
we see that in the case of real data, the per-example gradients are much more
similar, and each example helps reduce the loss on many other examples, as
compared to the random case.  Figure 2. Unlike the situation with ResNet-50
(Figure 1), with AlexNet we find that the peak coherence for random data
(second row) as measured by
$\operatorname{\mathnormal{\alpha_{m}/\alpha^{\perp}_{m}}}$ can be
surprisingly high, even though it happens much later in training, and is lower
than that of real (first row). Although this appears to be a contradiction to
the theory, it is not; it is a limitation of the metric.
$\operatorname{\mathnormal{\alpha_{m}/\alpha^{\perp}_{m}}}$ in this plot is a
measure of coherence over the entire network (that is, over entire per-example
gradients), and is therefore an average quantity. A closer look at the layer-
by-layer values of $\operatorname{\mathnormal{\alpha_{m}/\alpha^{\perp}_{m}}}$
as shown in Figure 3 reveals, once again, a significant difference between
real and random data. Figure 3. A layer-by-layer breakdown of
$\operatorname{\mathnormal{\alpha_{m}/\alpha^{\perp}_{m}}}$ for AlexNet from
Figure 2 shows that on random data (second row),
$\operatorname{\mathnormal{\alpha_{m}/\alpha^{\perp}_{m}}}$ is indeed close to
1 and much lower than that of real data (first row) for the first few layers.
For the higher (dense) layers, coherence is comparable between real and
random, though note the difference in scale of
$\operatorname{\mathnormal{\alpha_{m}/\alpha^{\perp}_{m}}}$ between the
convolutional and dense layer plots.

In this section, we use the
$\operatorname{\mathnormal{\alpha_{m}/\alpha^{\perp}_{m}}}$ metric developed
in Section 4 to investigate the generalization mystery. We can measure
$\alpha_{m}$ at any point in training by computing it directly using (3) on a
given sample.171717Observe that $\alpha$ can be computed efficiently in an
online fashion by keeping a running sum for
$\operatorname*{\mathbb{E}}[g_{z}]$, and another for
$\operatorname*{\mathbb{E}}[g_{z}\cdot g_{z}]$. The sample could be either
from the training set (giving us “training” coherence), or the test set
(“test” coherence).

One complication is the use of batch normalization (Ioffe and Szegedy, 2015)
in most practical networks, since in that case, per-example gradients are no
longer well-defined. This is a problem not just with $\alpha$, but with any
metric that is based on per-example gradients. However, $\alpha$ has an
interesting mathematical property that allows us to impute it using the
coherence of mini-batch gradients. We discuss this in greater detail in
Appendix D. In what follows, we use this imputation method for networks with
batch normalization.

In our main experiment, along the lines of Zhang et al. (2017), we train a
ResNet-50 network on two datasets, one real (ImageNet) and the other random
(“ImageNet” with random input pixels). Both networks are trained with vanilla
SGD (that is, no momentum) with a constant learning rate of 0.5 and batch size
of 4096. We do not use any explicit regularizers such as weight decay or
dropout. We estimate test and train $\alpha$ during training using the test
set (which has 50K samples) and a training set (a random sample of 50K
training examples). We take snapshots of the network during training each time
the (minibatch) training loss falls by 1% from the previous low watermark, and
compute loss, accuracy, and
$\operatorname{\mathnormal{\alpha_{m}/\alpha^{\perp}_{m}}}$ on these
snapshots.

The resulting training curves are shown in the first two columns of Figure 1.
As expected, both networks achieve zero training loss and near perfect
training accuracy, but only the network trained on (real) ImageNet shows non-
trivial generalization to the test set.

Coherence as measured by
$\operatorname{\mathnormal{\alpha_{m}/\alpha^{\perp}_{m}}}$ ($m$ = 50,000) is
shown in the third and fourth columns of Figure 1. The third column shows
coherence as a function of the number of epochs trained, whereas the fourth
columns shows it in terms of the training loss. Since the realized rate of
learning is different for the two datasets (the real data is learned in fewer
epochs), plotting coherence against loss allows us to compare across the two
datasets more easily.

In the case of real data, we observe that
$\operatorname{\mathnormal{\alpha_{m}/\alpha^{\perp}_{m}}}$ starts off low
(around 1) in early training and then increases to a maximum (about 40) within
in the first few epochs and then returns to a low value again (around 1) at
the end of training.181818For now, we ignore the small differences in training
and test coherence. In the plot of
$\operatorname{\mathnormal{\alpha_{m}/\alpha^{\perp}_{m}}}$ against training
loss, we see that when actual learning happens, that is, when the loss comes
down, $\operatorname{\mathnormal{\alpha_{m}/\alpha^{\perp}_{m}}}$ stays around
20. In other words, when training with real labels, each training example in
our set of 50K examples used to measure coherence helps many other examples.

In contrast, for random data, although the evolution of
$\operatorname{\mathnormal{\alpha_{m}/\alpha^{\perp}_{m}}}$ is similar to that
of real data, the actual values, particularly, the peak is very different.
$\operatorname{\mathnormal{\alpha_{m}/\alpha^{\perp}_{m}}}$ starts off low
(around 1), increases slightly (staying usually below 5), and then returns
back to a low value (around 1). Therefore, each training example in the case
of random data, helps only one or two other examples during training, that is,
the 50K random examples used to estimate coherence are more or less orthogonal
to each other.191919We note here that very early in training, that is, the
first few steps (not shown in Figure 1, but presented in Figure 16 instead),
$\operatorname{\mathnormal{\alpha_{m}/\alpha^{\perp}_{m}}}$ can be very high
even for random data due to imperfect initialization. All the training
examples are coordinated in moving the network to a more reasonable point in
parameter space. As may be expected from our theory, this movement generalizes
well: the test loss decreases in concert with training loss in this period.
Rapid changes to the network early in training is well documented (see, for
example, the need for learning rate warmup in He et al. (2016) and Goyal et
al. (2017)).

In summary, M

With a ResNet-50 model on real ImageNet data, in a sample of 50K examples,
each example helps tens of other examples during training, whereas on random
data, each example only helps one or two others.

M
This provides evidence that the difference in generalization between real and
random stems from a difference in similarity between the per-example gradients
in the two cases, that is, from a difference in coherence.

While experiments with other architectures and datasets also show similar
differences between real and random datasets (see Appendix E), there are cases
when the coherence of random data as measured by
$\operatorname{\mathnormal{\alpha_{m}/\alpha^{\perp}_{m}}}$ over the entire
network can be surprisingly high for an extended period during
training.202020As we discussed earlier, coherence even for random can be high
for a short period early on in training due to imperfections in
initialization. But the difference here is sustained high coherence. In our
experiments, we found an extreme case of this when we replaced the ResNet-50
network in the previous experiment with an AlexNet network (learning rate of
0.01). The training curves and measurements of
$\operatorname{\mathnormal{\alpha_{m}/\alpha^{\perp}_{m}}}$ in this case are
shown in Figure 2. As we can see, unlike the ResNet-50 case,
$\operatorname{\mathnormal{\alpha_{m}/\alpha^{\perp}_{m}}}$ reaches a value of
40 for $m=50,000$. In other words, in a sample of 50K examples, at peak
coherence, each random example helps 40 other examples!212121 That said, note
that (1) even in this case, at its peak
$\operatorname{\mathnormal{\alpha_{m}/\alpha^{\perp}_{m}}}$ for real is more
than 2$\times$ the peak for random; and (2) the high coherence of random
occurs much later in training than that of real which possibly indicates the
importance of the “expansion term” ($[\eta_{k}\,\beta]_{k=t+1}^{T}$) in the
bound of Theorem 1 (see discussion in Section 5).

What is going on? An examination of the per-layer values of
$\operatorname{\mathnormal{\alpha_{m}/\alpha^{\perp}_{m}}}$ provides some
insight. These are shown in Figure 3. We see that for the first convolution
layer (conv1) in the case of random—and only in that
case—$\operatorname{\mathnormal{\alpha_{m}/\alpha^{\perp}_{m}}}$ is
approximately 1 indicating that the per-example gradients in that layer are
pairwise orthogonal (at least over the sample used to measure
coherence).222222The difference in
$\operatorname{\mathnormal{\alpha_{m}/\alpha^{\perp}_{m}}}$ in the first layer
between real and random is also seen when the entire training set is used to
measure $\operatorname{\mathnormal{\alpha_{m}/\alpha^{\perp}_{m}}}$ (Figure
19). This indicates that the first layer plays an important role in
“memorizing” the random data since each example is pushing the parameters of
the layer in a different direction (orthogonal to the rest). This is not
surprising since the images are comprised of random pixels.

Now, the overall (network) $\alpha$ is a convex combination of the per-layer
$\alpha$s (see Theorem 7 in Appendix A). Since the fully connected layers have
high coherence, overall $\alpha$ (as shown in Figure 2) can be high even
though there is a layer with very low $\alpha$ (at the orthogonal limit). In
other words, M

As a measure of coherence,
$\operatorname{\mathnormal{\alpha_{m}/\alpha^{\perp}_{m}}}$ over the whole
network, being an average, is a blunt instrument, and therefore, a finer-
grained analysis, for example, on a per-layer basis, is sometimes necessary.

M
An important open problem, therefore, is to devise a better metric for
coherence that accounts for the structure of the network, and to use that
metric to obtain a bound stronger than that in Theorem 1. Please also see the
discussion in Section 10, and particularly, Example 9 for a closer look at
this in the context of a simple, illustrative example.

M
Evolution of Coherence. Experiments across several architectures and datasets
show a common pattern in how coherence as measured by
$\operatorname{\mathnormal{\alpha_{m}/\alpha^{\perp}_{m}}}$ (or equivalently,
$\alpha$) changes during training. Ignoring the initial transient in the first
few steps of training, coherence follows a broad parabolic pattern: It starts
off at a low value, rises to a peak, and then comes back down to the
orthogonal limit.232323In rare cases, such as a fully connected network on
mnist where the signal is strong and easy to find, coherence starts off high.
This happens regardless of whether the dataset is random or real, indicating
that this is an optimization (as opposed to a generalization) effect. We
discuss the reasons behind this in Appendix F.

##  7\. From Measurement to Control: Suppressing Weak Descent Directions

Weak directions in the average gradient are supported by few examples or
perhaps even one, and therefore, are less stable than strong directions which
are supported by many examples. Therefore, as discussed in Section 2,
suppressing weak directions in the average gradient should lead to less
overfitting and better generalization. Now, although existing regularization
techniques such as weight decay, dropout, and early stopping may be viewed
through this lens, the theory also suggests a new, more direct, regularization
technique we call winsorized gradient descent (WGD).

In WGD, instead of updating each parameter with the average gradient as in
gradient descent, we update it with a “winsorized” average where the most
extreme values (outliers) are clipped. Formally, let $w_{t}^{(j)}$ represent
the $j$th trainable parameter (that is, the $j$th component of the parameter
vector $w_{t}$) at step $t$, and $g^{(j)}_{i}(w_{t})$ the $j$th component of
the gradient of the $i$th example at $w_{t}$. In normal gradient descent, we
update $w_{t}^{(j)}$ as follows:

$w_{t+1}^{(j)}=w_{t}^{(j)}-\eta\frac{1}{m}\sum_{i=1}^{m}g_{i}^{(j)}(w_{t}).$

Now, let $c\in[0,50]$ be a hyperparameter that controls the level of
winsorization. Define $l^{(j)}$ to be the $c\,$th percentile of
$g_{i}^{(j)}(w_{t})$ (over the examples $i$). Likewise, let $u^{(j)}$ be the
$(100-c)\,$th percentile of $g_{i}^{(j)}(w_{t})$. The update rule with
winsorized gradient descent is as follows:

$\boxed{\quad w_{t+1}^{(j)}=w_{t}^{(j)}-\eta\frac{1}{m}\sum_{i=1}^{m}{\rm
clip}(g_{i}^{(j)}(w_{t}),\,l^{(j)},\,u^{(j)})\quad}$

where ${\rm clip}(x,l,u)\equiv{\rm min}({\rm max}(x,l),u)$.

The modified update rule minimizes the effect of outliers in the per-example
gradients on a per-coordinate basis. The value of $c$ dictates what is an
outlier. When $c=0$, nothing is an outlier, and this corresponds to normal
gradient descent, whereas when $c=50$, all values other than the median are
considered outliers. Thus, increasing $c$ reduces variance and increases bias.

######  Example 5 (WGD applied to Example 1).

Recall that using the component-wise median gradient in Example 1 instead of
the average gradient reduced the generalization gap to zero for both “real”
and “random.” We note that this corresponds to running WGD with $c=50$.

∎

Although the modification for WGD is a conceptually simple change, it greatly
increases the computational expense due to the need to compute and store per-
example gradients for all the examples. The computational expense can be
reduced by performing winsorized stochastic gradient descent (WSGD). This is a
straight forward modification of SGD where the winsorization is only performed
over the examples in the mini-batch rather than all examples in the training
set.

Figure 4.  Generalization improves when weak directions in the average
gradient are suppressed during gradient descent. Weak directions are
suppressed by winsorization, that is, by clipping extreme per-examples
gradients (independently for each coordinate of the gradient). The parameter
$c$ controls the level of winsorization and $c=0$ corresponds to using the
(usual) average gradient. We train a fully connected network on mnist with
varying amounts of label noise (see Figure 26 for a similar experiment with
random pixels).

M
WSGD on MNIST. We train a small fully-connected ReLU network with 3 hidden
layers of 256 neurons each for 60,000 steps (100 epochs) with a fixed learning
rate of 0.1 on mnist and 4 variants with different amounts of label noise
$\epsilon$ ranging from 25% to 100%.242424A label noise of 25% means that the
dataset is constructed by randomly assigning labels to 25% of the training
examples in mnist that are chosen uniformly at random. The remaining 75% have
the correct labels as do the test examples. Since mnist has 10 possible
labels, this means that 75% + (1/10) 25% = 77.5% of training examples have
pristine (that is, correct) labels and 22.5% have corrupted labels. We use
WSGD with a batch size of 100 and vary $c$ in $\\{0,1,2,4,8\\}$. Since we have
100 examples in each minibatch, the value of $c$ immediately tells us how many
outliers are clipped in each minibatch. For example, $c=2$ means the 2 largest
and 2 lowest values of the per-example gradient in a batch are clipped
(independently for each trainable parameter in the network), and as always,
$c=0$ corresponds to unmodified SGD.

The resulting training and test curves shown in Figure 4. The columns
correspond to different amounts of label noise and the rows to different
amounts of winsorization. In addition to the training and test accuracies
(${\sf ta}$ and ${\sf va}$, respectively), we show the level of overfit which
is defined as ${\sf ta}-{\sf va}$.

As expected, as $c$ increases, and the weaker directions are suppressed more,
the extent of overfitting decreases. Furthermore, for larger values of $c$
(for example, $c=8$) the ability to fit the corrupted labels is severely
impacted. The training accuracy stays below the accuracy that would be
obtained if only the uncorrupted labels were learned (shown by dashed gray
lines in the plot). The ability to memorize, that is, fit random labels (100%
noise) is impacted more than the ability to fit real labels (0% noise): the
effective learning rate (the rate at which training accuracy increases) is
much lower for random than for real.

In summary, M

If we suppress weak gradient directions by modifying SGD to use a robust
average of per-example gradients that excludes outliers, generalization
improves. This provides further direct evidence that weak directions are
responsible for overfitting and memorization.

M

Finally, we notice that with a large amount of winsorization, there can be
optimization instability (not to be confused with algorithmic stability which
as we have seen is improved): training accuracy can fall after a certain
point. We are not sure what causes it but conjecture that this is because of a
strengthening of positive feedback loops in strong directions (see Section
10).

Figure 5. Taking the coordinate-wise median of 3 micro-batches (M3) suppresses
weak gradient directions more than taking their coordinate-wise average (A3)
(the same as ordinary SGD), leading to better generalization. Here, we train a
ResNet-50 on 3 datasets derived from ImageNet by replacing some fraction of
the training images with Gaussian noise. In the case of random data (100%
noise), M3 prevents memorization, so the training and test curves both lie on
the x-axis. In contrast, as expected, A3 (SGD) memorizes the training set.
When only half the training images are replaced by noise (50% noise), M3
reaches a training accuracy near 50% suggesting that only the real images are
learned. This is confirmed in Figure 6. Figure 6. In the experiment of Figure
5, on the dataset where half the training images are replaced by noise (50%
noise), M3 only learns the real (pristine) training images but does not learn
the random (corrupt) images. In contrast, A3 (that is, SGD) learns both,
though the corrupt examples are learned later in training. This is further
evidence that the gradients of real data are well-aligned, and add up to
strong directions in the average gradient; whereas those of random data are
not well-aligned, and may be suppressed if weak directions are attenuated
through robust averaging. This difference in the strength of the gradients in
the two cases explains the observed difference in generalization between them.

M
Scaling up. Winsorization requires computing and storing many per-example
gradients.252525For exact computation, the storage would depend on $c$ and may
be tractable for small $c$. This could be reduced further by employing
approximations to compute streaming quantiles. This makes it impractical for
large datasets such as ImageNet, as well as inapplicable to popular networks
such as ResNet-50 which employ batch normalization as per-example gradients
are not defined in that case.

An alternative to winsorization that addresses both these problems is the well
known technique of taking median of means (see, for example, Minsker
(2013)).262626 Median of means has the theoretical property that its deviation
from the true mean is bounded above by $O(1/\sqrt{m})$ with high probability
(where $m$ is the number of samples). The sample mean satisfies this property
only if the observations are Gaussian.  The main idea of the _median of means_
algorithm is to divide the samples into $k$ groups, computing the sample mean
of each group, and then returning the median of these $k$ means. The most
obvious way to apply this idea to SGD is to divide a mini-batch into $k$
groups of equal size. We compute the mean gradients of each group as usual,
and then take their coordinate-wise median. The median is then used to update
the weights of the network.272727Since we are simply replacing the mini-batch
gradient with a more robust alternative, this technique may be used in
conjunction with other optimizers.

Even though the algorithm is straightforward, its most efficient
implementation (that is, where the $k$ groups are large and processed in
parallel) on modern hardware accelerators requires low-level changes to the
stack to allow for a median-based aggregation instead of the mean. Therefore,
in this work, we simply compute the mean gradient of each group as a separate
micro-batch and only update the network weights with the median every $k$
micro-batches, i.e., we process the groups serially.

In the serial implementation, $k=3$ is a sweet spot. We have to remember only
2 previous micro-batches, and since ${\rm
median}(x_{1},x_{2},x_{3})=\sum_{i}x_{i}-\min_{i}x_{i}-\max_{i}x_{i}$ (where
$i\in\\{1,2,3\\}$), we can compute the median with simple operations. We call
this M3 (median of 3 micro-batches).

######  Example 6 (M3 applied to Example 1).

In this case, applying M3 with a micro-batch size of 1 (batch size of 3)
completely suppresses the weak gradient directions (corresponding to the
idiosyncratic signals) in both the “real” and “random” datasets, and leads to
perfect generalization.

∎

Figure 5 shows the effect of M3 on 3 datasets: real ImageNet, ImageNet with
half the images replaced by Gaussian noise (50% noise), and “ImageNet” with
all the images replaced by Gaussian noise (100% noise). The 100% noise dataset
is the same as the “random” dataset in Section 6. We run M3 with a micro-batch
of 256 (that is, batch size of $3\times 256$) for 90 epochs and a learning
rate of 0.20. For comparison we also run SGD with an identical setup. Instead
of the median of 3 micro-batches, in SGD we compute their average, and hence,
in this context, we refer to SGD as A3 to highlight that the only difference
in the two cases is replacing the median operation with average.282828In
practice, SGD with a batch size of $3\times 256$ is subtly different from A3
with a micro-batch of $256$ in how the low-level computation is distributed
among the accelerators and in the resulting statistics for batch
normalization. Although that difference is immaterial, we use A3 here to
eliminate all differences other than the method of aggregation.

We observe the following:

  1. (1)

On real data, M3 only slightly slows down training after about 50% of the
dataset has been learned, and almost reaches the 100% training accuracy
achieved by A3. Also, M3 has a lower generalization gap (43.34%) compared to
A3 (47.15%).

  2. (2)

With 50% noise, M3 reaches a training accuracy less than 50% which is much
lower than the 100% training accuracy of A3. Thus M3 has a much lower
generalization gap (25.90%) compared to A3 (77.13%). Further investigation
shows that M3 learns the real 50% of the training dataset (the “pristine”
examples) well, but does not learn the remaining 50% of the training set that
is Gaussian noise (the “corrupt” examples). This is, of course, in contrast to
A3 which learns both almost equally well. See Figure 6.

  3. (3)

Finally, in the case of 100% noise, M3 fails to learn any of the training data
at all in sharp contrast to A3.

This provides further evidence that (a) weak directions are responsible for
memorization, and (b) suppressing weak directions improves generalization (via
improving stability).

The choice of hyper-parameters of M3 requires care. Larger the size of the
micro-batch, less effective is the median operation in suppressing weak
directions (consider the extreme case when the micro-batch is the entire
training set and taking the median serves no purpose). However, smaller the
micro-batch, less reliable are the batch statistics (for batch normalization),
and higher the effective level of winsorization (consider a micro-batch size
of 1 where the effective winsorization level now is $c=50$). The learning rate
has to be set in conjunction with the micro-batch size, and for some learning
rates we found the training to be unstable (see Figure 27). This is similar to
the optimization stability seen with winsorization previously.

##  8\. Why are Some Examples (Reliably) Learned Earlier?

Figure 7. Coherence as measured by
$\operatorname{\mathnormal{\alpha_{m}/\alpha^{\perp}_{m}}}$ is higher for
examples that are learned early in ImageNet training (Easy ImageNet) than for
those that are learned later (Hard Imagenet). As expected, the higher
coherence translates into better generalization. The network used is a
ResNet-50.

In a study on memorization in shallow fully-connected networks and small
convolutional networks on mnist and cifar-10, Arpit et al. (2017) discovered
that for real datasets, starting from different random initializations, many
examples are consistently classified correctly or incorrectly after one epoch
of training. They call these easy and hard examples respectively. They
conjecture that this variability of difficulty in real data “is because the
easier examples are explained by some simple patterns, which are reliably
learned within the first epoch of training.”

But that begs the question what makes a pattern “simple” and why are such
patterns reliably learned early? The theory of Coherent Gradients provides a
refinement: M

Easy examples are those examples that have a lot in common with other examples
where commonality is measured by the alignment of the gradients of the
examples.

M
Under this assumption, it is easy to see why an easy example is learned sooner
reliably: most gradient steps benefit it.

Note that this hypothesis is more nuanced than the conjecture in Arpit et al.
(2017). First, the difficulty of an example is not simply a property of that
example (whether it has simple patterns or not), but depends on the
relationship of that example to others in the training set (what it shares
with other examples).

Second, the dynamics of training, including initialization, can determine the
difficulty of examples. Consequently, it can accommodate the observed
phenomenon of adversarial initialization (Liao et al., 2018; Liu et al., 2019)
where examples that are easy to learn with random initialization become
significantly harder to learn with a different, specially constructed
initialization, and the generalization performance of the network suffers. Any
notion of simplicity of patterns intrinsic to an example alone cannot explain
adversarial initialization since the dataset remains the same, and therefore,
so do the patterns in the data.

In order to test the above hypothesis, we create two datasets with 500K
training and 50K test examples from the standard ImageNet training set. These
datasets consists of examples that a ResNet-50 reliably learns early (“Easy
ImageNet”) or late (“Hard ImageNet”). See Appendix G for more details on this
construction. Next, as in Section 6, we measure loss, accuracy, and coherence
during training on both datasets.

Figure 8. If gradient descent enumerates hypotheses of increasing complexity
then the examples learned early, that is, the easy examples, should be the
ones far away from the decision boundary since they can be separated by
simpler hypotheses. However, a model learned from the hard examples then,
should generalize well to easy examples, but that is not what we find on
ImageNet. A model trained on hard ImageNet examples has only a 17% accuracy on
easy ImageNet examples (in contrast to a 71% accuracy obtained by a model
trained on other easy examples).

The results are shown in Figure 7. We observe that the coherence for Easy
ImageNet is significantly higher than that of Hard ImageNet, and as might be
expected from the theory, the generalization gap of Easy ImageNet is smaller
since the average gradient in that case is more stable.292929This is also seen
in an in situ measurement of coherence of easy and hard examples during
regular ImageNet training, but due to a technicality involving batch
normalization statistics, that measurement is less reliable. See Appendix G
for details.

In other words, since easy examples, as a group have more in common with each
other (than with the hard examples, or the hard examples have amongst
themselves), (1) a model is less impacted by the presence or absence of a
single easy example in the training set, leading to good generalization on
easy examples; and (2) easy examples have a stronger (focused) effect on the
average gradient direction than the hard examples (which are diffuse) leading
to easy examples being learned faster. Thus there is a correlation between how
quickly examples are learned and their generalization.303030This may be seen
as an additional justification for early stopping to the one in Section 2.

Although the above experiment shows that easy examples have more in common
with each other, it does not rule out that there is something intrinsic to
each easy example that accelerates learning. For instance, easy examples could
have larger gradients than hard examples. To check this, we train a network on
a single example from Easy ImageNet or Hard ImageNet at a time and measure the
number of steps it takes to fit the example. We find that there is no
statistically significant difference between the two datasets in this regard.
It is only when sufficiently many easy examples come together (as in the
earlier experiment), that they train faster than hard examples. This may be
seen as further evidence that it is the relationship between examples rather
than something intrinsic to an example that controls difficulty. Please see
Appendix G for more details.

M
Does gradient descent explore functions of increasing complexity? One
intuitive explanation of generalization is that GD somehow explores candidate
hypotheses of increasing “complexity” during training. Although this is backed
by some observational studies (for example, Arpit et al. (2017); Nakkiran et
al. (2019); Rahaman et al. (2019)), we are not aware of any causal mechanism
that has been proposed to explain this sequential exploration.313131For
example, there is no causal intervention similar to suppressing weak gradient
directions.

Our theory suggests one. As described above, as training progresses, more and
more examples get fit, starting with examples whose gradients are well-aligned
with those of others, and ending with those examples whose gradients are more
idiosyncratic. Thus, one may observe the function implemented by the network
to get more and more complicated in the course of training simply because it
fits (interpolates through) more and more training examples (points). An
interesting question for future work is if this argument can be formalized to
explain some of the specific empirical observations in the literature (such as
ReLU networks learning low frequency functions first (Rahaman et al., 2019) or
learning low descriptive-complexity functions first (Valle-Perez et al.,
2019)).

However, one may wonder if there is some other causal mechanism that causes
SGD to explore functions in increasing order of complexity? A simple extension
of the previous experiment with Easy and Hard ImageNet suggests not. To
motivate the extension, consider a thought experiment motivated by the 2D
classification problem shown in Figure 8. If SGD were to somehow “try” simpler
hypothesis early on, then the easy examples would be the ones far from the
decision boundary (which could be easily separated by say, linear
classifiers), and the hard ones would be ones close to the boundary (which
would need more complex curves to separate). Therefore, based on the intuition
provided by Figure 8, one might expect that the decision boundary learned from
the hard examples, would generalize well to the easy examples.

But this is not what we see with real data in high dimensions: The model
trained on Hard ImageNet has an accuracy of only 17% on the Easy ImageNet test
set. This is much lower than the 71% test accuracy of the model trained on
Easy ImageNet (as seen in Figure 7). In other words, M

Examples learned late by gradient descent (that is, the hard examples), by
themselves, are insufficient to define the decision boundary to the same
extent that early (or easy) examples are.

M
This observation leads us to a view of deep models that is closer in spirit to
kernel regressors (Nadaraya, 1964; Watson, 1964), but, of course, with a
“learned kernel,” and is consistent with the intuition that in high
dimensions, learning (almost) always amounts to extrapolation (Balestriero et
al., 2021).

Figure 9. Pristine examples, that is examples with correct labels, show higher
coherence than the corrupt examples, and consequently are learned much faster.
Here, we train a Resnet-50 on ImageNet where half the images in the training
set have randomly assigned labels (that is, ImageNet with 50% label noise).

##  9\. Learning With Noisy Labels

The theory of Coherent Gradients provides insight on why it is possible to
learn in the presence of label noise (Rolnick et al., 2017). As Figure 9
shows, similar to real and random data, coherence as measured by
$\operatorname{\mathnormal{\alpha_{m}/\alpha^{\perp}_{m}}}$ is greater for
examples with correct labels (the pristine examples) than it is for examples
with incorrect labels (corrupt examples). Consequently, the strong directions
in the average gradient correspond to the pristine examples, and they get
learned before the corrupt examples (mirroring the situation with easy and
hard examples discussed in the previous section).

We can thus explain the empirical success of early stopping when learning with
noisy labels and the empirical observation that the loss of pristine examples
falls faster than that of corrupt examples (see, for example, “small-loss”
trick in Song et al. (2020, Section III E)). Furthermore, even if early
stopping is not used, and training is continued until convergence, the
gradients of corrupt examples are not strong enough to “interfere” with those
of the pristine examples which reinforce each other.323232However, there may
still be some coherence amongst incorrectly labeled examples which may cause
unintended generalization to the test set. This is manifested as a degradation
in test performance as the corrupt examples are learned, and can be seen in
experiments (see, for example, Chatterjee (2020, Figure 1 (b)), Zielinski et
al. (2020, Figure 1 (a)), and in Arpit et al. (2017, Figures 7 and 8 (b))).

##  10\. Depth, Feedback Loops, and Signal Amplification

Gradient descent through the lens of Coherent Gradients is a mechanism for
soft feature selection, or equivalently, for signal amplification. The over-
parameterized linear regression model in Example 1 provides a good
illustration of this. When training the model on dataset L (“real”), we see
that the weight of the common signal grows more rapidly since increasing it
simultaneously reduces the loss on all training examples.

In this section, we shall see how the signal amplification effect becomes
stronger when the model has multiple layers, due to the interaction between
the parameters belonging to the different layers. We illustrate this with two
simple examples that build on Example 1 to add depth.

######  Example 7 (Adding Depth to Linear Regression).

Instead of fitting the a model of the form $y=w\cdot x$ as is the case in
linear regression, consider fitting the following “deep” model:

$y=(w\odot u)\cdot
x=\sum_{j=1}^{6}w^{(j)}h^{(j)}=\sum_{j=1}^{6}w^{(j)}u^{(j)}x^{(j)}$

$x^{(1)}$$x^{(2)}$$x^{(3)}$$x^{(4)}$$x^{(5)}$$x^{(6)}$$h^{(1)}$$h^{(2)}$$h^{(3)}$$h^{(4)}$$h^{(5)}$$h^{(6)}$$y$$\displaystyle
h^{(j)}=u^{(j)}\,x^{(j)}$$w^{(1)}$$u^{(1)}$$w^{(2)}$$u^{(2)}$$w^{(3)}$$u^{(3)}$$w^{(4)}$$u^{(4)}$$w^{(5)}$$u^{(5)}$$w^{(6)}$$u^{(6)}$

under the square loss $\ell(w)\equiv\frac{1}{2}(y-(w\odot u)\cdot x)^{2}$ to
the dataset L (“real”) from Example 1:

$i$ | $x_{i}$ | $y_{i}$
---|---|---
$1$ | $\langle\,{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}1},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\phantom{-}1}\,\rangle$ | $\phantom{-}1$
$2$ | $\langle\,{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}-1},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}-1}\,\rangle$ | $-1$
$3$ | $\langle\,{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}-1},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}-1}\,\rangle$ | $-1$
$4$ | $\langle\,{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}1},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\phantom{-}1}\,\rangle$ | $\phantom{-}1$
$5$ | $\langle\,{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}-1},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}-1}\,\rangle$ | $-1$

Now start gradient descent (GD) with a constant learning rate of 0.1 at
$w^{(j)}=u^{(j)}=0.01$ for $j\in[6]$.333333Unlike linear regression, we use a
near-zero initialization for the deep model rather than a zero initialization
since the latter is a stationary point. As in the case of linear regression,
the parameters corresponding to the common feature $x^{(6)}$, that is,
$u^{(6)}$ and $w^{(6)}$ grow more quickly than those corresponding to the
idiosyncratic features $x^{(1)},\dots,x^{(4)}$. But what is striking is the
extent of the relative difference. This can be seen by comparing the plots of
their values in the two cases:343434We only show $w^{(1)}$ and $w^{(6)}$
since, along the trajectory of GD, from symmetry, $u^{(j)}=w^{(j)}$ for all
$j\in[6]$ in the deep model and $w^{(2)},w^{(3)},$ and $w^{(4)}$ are equal to
$w^{(1)}$ in both models.

deep model | linear regression
---|---
|

In fact, for the deep model, the difference between $w^{(1)}$ and $w^{(6)}$
understates the importance of the corresponding features since the weight of
feature $i$ in the model is given by $u^{(j)}w^{(j)}$ (which, in this case, is
$(w^{(j)})^{2}$ due to symmetry).

The improvement in amplification efficiency is also reflected in the
generalization gap (using the 5th example in L as the test example) which is
negligible for the deep model in comparison to that of linear regression:

deep model | linear regression
---|---
|

This naturally leads to the following question: M

Why is the signal amplification so much greater in the case of the deep model
compared to linear regression?

M
The answer lies in the interaction of the weights across the two layers.
Consider the components of the gradient corresponding to $u^{(j)}$ and
$w^{(j)}$ for the $i$th example. These are, respectively,

$\frac{\partial\ell_{i}}{\partial{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}u^{(j)}}}=r_{i}(u,w)\,x^{(j)}\,{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}w^{(j)}}\quad\quad\quad\textrm{and}\quad\quad\quad\frac{\partial\ell_{i}}{\partial{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}w^{(j)}}}=r_{i}(u,w)\,x^{(j)}\,{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}u^{(j)}}$

where $r_{i}(u,w)=y_{i}-(w\odot u)\cdot x_{i}$ is the residual. Observe that
the component of the gradient corresponding to $u^{(j)}$ is directly
proportional to $w^{(j)}$ and vice-versa. By slight abuse of terminology we
call this a positive feedback loop between $u^{(j)}$ and $w^{(j)}$.353535It is
an abuse of terminology since the positive feedback is not absolute. There is
a second “dampening” dependency through the residual which becomes more
important closer to convergence.

Now consider the gradient $g_{i}(u,w)$ for the $i$th example, and the average
gradient $g(u,w)$:363636$r(u,w)$ is equal to $|r_{i}(u,w)|$, a quantity that
is independent of $i$ for $(u,w)$ in the trajectory of GD due to the
symmetries in the problem.

$i$ |  $g_{i}(u,w)=\,\langle$ $\frac{\partial\ell_{i}}{\partial{u^{(1)}}}$, $\frac{\partial\ell_{i}}{\partial{u^{(2)}}}$, $\frac{\partial\ell_{i}}{\partial{u^{(3)}}}$, $\frac{\partial\ell_{i}}{\partial{u^{(4)}}}$, $\frac{\partial\ell_{i}}{\partial{u^{(5)}}}$, $\frac{\partial\ell_{i}}{\partial{u^{(6)}}}$, $\frac{\partial\ell_{i}}{\partial{w^{(1)}}}$, $\frac{\partial\ell_{i}}{\partial{w^{(2)}}}$, $\frac{\partial\ell_{i}}{\partial{w^{(3)}}}$, $\frac{\partial\ell_{i}}{\partial{w^{(4)}}}$, $\frac{\partial\ell_{i}}{\partial{w^{(5)}}}$, $\frac{\partial\ell_{i}}{\partial{w^{(6)}}}$ $\rangle$
---|---
$1$ |  $aa,$ $r(u,w)\,\langle$ $w^{(1)}$, $0$, $0$, $0$, $0$, $w^{(6)}$, $u^{(1)}$, $0$, $0$, $0$, $0$, $u^{(6)}$ $\rangle$
$2$ |  $aa,$ $r(u,w)\,\langle$ $0$, $w^{(2)}$, $0$, $0$, $0$, $w^{(6)}$, $0$, $u^{(2)}$, $0$, $0$, $0$, $u^{(6)}$ $\rangle$
$3$ |  $aa,$ $r(u,w)\,\langle$ $0$, $0$, $w^{(3)}$, $0$, $0$, $w^{(6)}$, $0$, $0$, $u^{(3)}$, $0$, $0$, $u^{(6)}$ $\rangle$
$4$ |  $aa,$ $r(u,w)\,\langle$ $0$, $0$, $0$, $w^{(4)}$, $0$, $w^{(6)}$, $0$, $0$, $0$, $u^{(4)}$, $0$, $u^{(6)}$ $\rangle$
$g(u,w)$ |  $aa,$ $r(u,w)\,\langle$ $\frac{1}{4}w^{(1)}$, $\frac{1}{4}w^{(2)}$, $\frac{1}{4}w^{(3)}$, $\frac{1}{4}w^{(4)}$, $0$, $w^{(6)}$, $\frac{1}{4}u^{(1)}$, $\frac{1}{4}u^{(2)}$, $\frac{1}{4}u^{(3)}$, $\frac{1}{4}u^{(4)}$, $0$, $u^{(6)}$ $\rangle$

M

M

We see that, just as in linear regression with dataset L (Example 1), the per-
example gradients in the common component (shown in blue) reinforce each
other, and add up in the average gradient $g(u,w)$, but the idiosyncratic
components (shown in pink) do not.373737This is also reflected in the higher
coherence of the $u^{(6)}$ and $w^{(6)}$ components compared to the rest as
measured by (component-wise) $\alpha$.

However, in contrast to linear regression where the relative difference in the
gradient directions was constant during training (1 v/s $\frac{1}{4}$), in the
deep model, the relative difference depends on $u$ and $w$ (for example,
$w^{(6)}$ v/s $\frac{1}{4}w^{(1)}$ and $u^{(6)}$ v/s $\frac{1}{4}u^{(1)}$).
This combined with the positive feedback loop between the $u^{(i)}$ and the
corresponding $w^{(i)}$ leads to the relative difference between the gradient
directions exponentially increasing as training progress.

As a result, the relative importance of the common signal increases much
faster in the deep model than in the linear regression case leading to a
winner-take-all situation. In summary, M

In the deep model, in contrast to linear regression, the relative difference
between the common and idiosyncratic gradient directions gets exponentially
amplified during training due to positive feedback between layers.

M

This rapid growth in the strong component of the gradient is reflected in the
plot of training coherence as measured by
$\operatorname{\mathnormal{\alpha_{m}/\alpha^{\perp}_{m}}}$ ($m=4$) over time
since the $u^{(6)}$ and $w^{(6)}$ components (the strong, or the high
coherence components) come to dominate the gradient for the deep model, and
they have perfect coherence:

deep model | linear regression
---|---
|

Thus although $\operatorname{\mathnormal{\alpha_{m}/\alpha^{\perp}_{m}}}$ for
the deep model starts off at 2.5 (exactly the same as for linear regression),
it rises to near maximum of 4 (while in the linear regression case it stays
constant).

∎

The previous example showed how feedback loops due to depth can amplify input
signals or features that generalize better relative to noise signals. Feedback
loops can also play a critical role in differentially amplifying internal
signals in the network that generalize better than their peers. To see this,
consider the following thought experiment that builds on Example 1 by adding a
second layer to select between a “memorization” neuron and a “learning”
neuron.

######  Example 8 (A Tale of Two Neurons).

Consider the following linear neural network with one hidden layer with two
neurons:

$x^{(1)}$$x^{(2)}$$x^{(3)}$$x^{(4)}$$x^{(5)}$$x^{(6)}$$h^{(1)}$$h^{(2)}$$y$$\displaystyle
h^{(1)}=\sum_{j=1}^{5}u^{(j)}\,x^{(j)}$$\displaystyle
h^{(2)}=\sum_{j=1}^{6}v^{(j)}\,x^{(j)}$$\displaystyle
y=\sum_{j=1}^{2}w^{(j)}\,h^{(j)}$$w^{(1)}$$w^{(2)}$$u^{(1)}$$v^{(1)}$$u^{(2)}$$v^{(2)}$$u^{(3)}$$v^{(3)}$$u^{(4)}$$v^{(4)}$$u^{(5)}$$v^{(5)}$✗$v^{(6)}$

Now consider the task of fitting it to the following dataset (dataset L
(“real”) from Example 1 that we have been using as a running example):

$i$ | $x_{i}$ | $y_{i}$
---|---|---
$1$ | $\langle\,{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}1},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\phantom{-}1}\,\rangle$ | $\phantom{-}1$
$2$ | $\langle\,{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}-1},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}-1}\,\rangle$ | $-1$
$3$ | $\langle\,{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}-1},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}-1}\,\rangle$ | $-1$
$4$ | $\langle\,{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}1},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\phantom{-}1}\,\rangle$ | $\phantom{-}1$
$5$ | $\langle\,{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}\phantom{-}0},{\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}-1},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}-1}\,\rangle$ | $-1$

Of the two neurons in the hidden layer, one, the “good” neuron, $h^{(2)}$, is
connected to the common input feature $x^{(6)}$, whereas, the other, the “bad”
neuron, $h^{(1)}$, is not. Therefore, the bad neuron can only help in
memorizing the training data.383838In terms of Example 1, the bad neuron only
“sees” the random dataset M.

When we perform gradient descent starting, as before, from 0.01 for all
parameters, we find that the weight for the good neuron ($w^{(2)}$) grows much
more rapidly than that for the bad neuron ($w^{(1)}$) and we have good
generalization (as measured on $(x_{5},y_{5})$):

|  |
---|---|---

As in the previous example, the reason behind the rapid increase in $w^{(2)}$
relative to $w^{(1)}$ is due to the interaction between the layers. In brief,
there is a positive feedback loop393939As in the previous example, there is a
second dampening dependence through the residual that becomes important near
convergence. between $w^{(1)}$ and each of $u^{(1)},\dots,u^{(5)}$ and between
$w^{(2)}$ and each of
${\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}v^{(1)},\dots,v^{(5)}}$.
However, in addition, $w^{(2)}$ also has a feedback loop with
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}v^{(6)}}$,
a component with high coherence since it is the weight for the common input
feature $x^{(6)}$. Consequently, $w^{(2)}$ grows exponentially faster than
$w^{(1)}$.404040Indeed, due to the feedback loop, and the faster growth of
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}w^{(2)}}$,
even $v^{(1)},\dots,v^{(4)}$ grow faster relative to $u^{(1)},\dots,u^{(4)}$.

M
Adversarial initialization. The relative amplification effect is so strong
that even if $w^{(1)}$ is very favorably initialized at 0.1 or 0.2 while
keeping $w^{(2)}$ initialized at 0.01, in the course of training, $w^{(2)}$
eventually surpasses $w^{(1)}$ (we also show the test and train curves and
$\operatorname{\mathnormal{\alpha_{m}/\alpha^{\perp}_{m}}}$ on the training
set ($m$ = 4) measured over the whole network for subsequent discussion):

|  |
---|---|---
|  |

Of course, for a large enough adversarial initialization, $w^{(2)}$ can no
longer overcome $w^{(1)}$ and we have poor generalization:

|  |
---|---|---

We can study this systematically by plotting a heatmap of the test loss at the
end of training as a function of the initial values of $w^{(1)}$ and $w^{(2)}$
(all other parameters are initialized at 0.01):

The additional positive feedback loop between $w^{(2)}$ and
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}v^{(6)}}$
ensures that from almost all initializations, the common feature has greater
importance in the final output than any idiosyncratic feature. In summary, M

Due to the interaction between layers, the hidden neuron with access to the
common feature, gets a much higher weight compared to its peer that does not.

M
In this manner, gradient descent amplifies intermediate features that
generalize better.414141Informally, a feature that generalizes better is one
that is stable, that is, one that shows a smaller perturbation if the training
set we slightly changed. A feature such as $h^{(1)}$ may be thought of as a
“memorization” feature since it takes on very different values on a particular
example depending on whether that example was in the training set or not. In
this context, the method of counterfactual simulation presented in Chatterjee
and Mishchenko (2020), a method to analyze the stability, and hence
generalization of intermediate signals of a trained model, may be of interest.

∎

M
Memorization and Layer-wise Coherence. In the previous example, it may be
tempting to think that the difference in generalization capability between the
good neuron and the bad neuron is reflected in the training coherence of their
respective weights. That is not so. Both $w^{(1)}$ and $w^{(2)}$ have the same
coherence over the training set during gradient descent for any of the above
trajectories, that is, both have a component-wise $\alpha$ of 1. Thus, M

Coherence alone at a hidden layer cannot distinguish between a feature from
the previous layer that does not generalize well and one that does.

M
This has two consequences for coherence measured on random data:

  1. (1)

The coherence of a given layer may be high if memorization happens in other
layers. We believe that this is a likely reason for why high coherence is
observed in AlexNet for the higher layers when it is trained on random data
(Figure 3).

  2. (2)

Coherence as measured over the whole network, that is, $\alpha$ computed using
the entire gradient vector, can skew high since it is a weighted sum of the
per-layer coherences, since many of the layers can have high coherence if
memorization happens in only a few layers. This was seen in the case of
AlexNet (Figure 2).

######  Example 9 (Tale of Two Neurons with Memorization).

Both these consequences for random data can be illustrated by training the
model used in Example 8 on the “random” dataset M of Example 1 (instead of
dataset L as we have been doing so far):

|  |
---|---|---

It is easy to check, on the training set of M ($m=4$), that
$\operatorname{\mathnormal{\alpha_{m}/\alpha^{\perp}_{m}}}=1$ for the first
layer (where we may say memorization, or the case-by-case fitting, occurs) and
$\operatorname{\mathnormal{\alpha_{m}/\alpha^{\perp}_{m}}}=4$ for the second
layer (where all the examples are treated uniformly). Thus, the overall
$\operatorname{\mathnormal{\alpha_{m}/\alpha^{\perp}_{m}}}$ is greater than 1
(the orthogonal limit), as seen above, even with memorization.

∎

The observation above, that is, coherence of the entire network can be high on
random data, is not specific to the $\alpha$ metric. It is indeed the case
that the per-example gradients of different examples are similar in the
components of the gradient corresponding to the higher (non-memorization)
layers. Therefore, even other metrics for coherence such as dot product and
stiffness that depend on the entire gradient vector would be skewed upwards.

M

In summary, the examples in this section show how depth can help with feature
selection through positive feedback loops between layers. Due to these
feedback loops, features whose weights have high coherence get amplified
beyond what coherence alone can accomplish.

##  11\. What Should a Theory of Generalization Look Like?

The ultimate goal of a theory of generalization for deep learning would be to
provide a tight guarantee on the generalization gap in problem setups of
practical interest, but that appears out of reach at present. Even so, there
are a number of different qualitative properties that such a theory should
satisfy. For example, in the introduction, we already noted that the work of
Zhang et al. (2017) puts a very strong constraint on the form of any theory of
generalization:

  1. [C1]

Uniform explanation of memorization and generalization. It must simultaneously
be able to explain why on some datasets, there is good generalization, when
the exact same setup (architecture, learning rate, number of steps) is capable
of memorizing a random dataset. Thus any non-trivial generalization bound must
depend on the dataset in some non-trivial way (that is, beyond just the number
of training examples). And ideally, in the case of label noise experiments,
the bound should increase with increasing amount of label noise.

In addition to this constraint, practical experience with deep learning
suggests several other constraints on a theory of generalization. Nagarajan
and Kolter (2019b) propose the following criteria:

  1. [C2]

Incorporate architecture dependence. It should provide an explanation of why
the generalization error reduces with increasing width (or depth), as has been
surprisingly observed in practice.

  2. [C3]

Apply to real networks (not post-processed networks, noisy variants, or
infinite limits). The theory should apply to the network learned by gradient
descent without any modification or explicit regularization, or to
idealizations.

  3. [C4]

Generalization should improve with more training data. The generalization gap
predicted by the theory should decrease with increase in the size of the
training set (and not increase as is the case for many bounds, particularly
those based on weight-norms!).

To these four criteria from the literature, we would like to add the
following:

  1. [C5]

Uniform explanation of early stopping and training to convergence. The theory
should provide an explanation of why early stopping works in practice, and
furthermore, such an explanation should ideally be uniform with respect to the
two extremes of early stopping: perfect generalization at initialization
(before any data is seen) and good generalization at end of training (that is,
at a local minimum or a stationary point of the loss function), particularly
since early stopping is not essential to good generalization (for example, see
Figure 1).

  2. [C6]

Uniform handling of stochasticity of batch construction. Although for many
datasets and architectures of practical interest it is computationally
prohibitive to do full-batch gradient descent, where such experiments have
been performed (for example, Wu et al. (2018) and Chatterjee (2020)424242See
data here: https://openreview.net/forum?id=ryeFY0EFwS&noteId=rJglFKTBoB), or
equivalent optimization outcome achieved in practice (for example, over-
parameterized linear regression using full-batch gradient descent starting
from the origin converges to the solution obtained by computing the pseudo-
inverse using the singular value decomposition), we find that full-batch also
leads to good generalization. Furthermore, careful experiments show that there
is no clear connection between batch-size and generalization gap though it was
suggested previously that there may be (see Shallue et al. (2019) for a
comprehensive study). (Now, this is not to say that stochasticity does not
help: for example, sampling noise from mini-batch construction could help get
out of local minima, or perhaps even serve as a regularizer; but it appears
that stochasticity is not essential for a non-trivial generalization gap.)

  3. [C7]

Right level of generality for the phenomenon. Generalization in deep learning
is an extremely broad phenomenon and has been observed in many situations that
differ in specifics along dimensions such as type of activation function (for
example, ReLU, sigmoid, sinusoidal, etc.); type of loss function; whether the
task is a regression, classification (few classes or very many classes) or a
generative task; discreteness of the problem (both in inputs, such as language
models, and in weights and activations, such as extremely quantized models
such as binarized neural networks (Hubara et al., 2016)); training schedules
such as SGD with warm restarts (Loshchilov and Hutter, 2017); etc.

Therefore, a satisfactory explanation of generalization in deep learning
cannot be too closely tied to the specific properties of a system such as
scale invariance of ReLU activations (the explanation would not work for other
activation functions), or the learning problem being a classification problem
with a few output classes such as a margin-based explanation (the explanation
would not be natural for regression or generative models, or even
classification with 100K output classes), or even the training steps
monotonically reducing in size (would not work for warm restarts).

M

To this list, one might be tempted to add: uniformity of the explanation with
respect to the degree of over-parameterization, that is, an uniform
explanation for both under-parameterized models and over-parameterized models.
However, given the observations of Belkin et al. (2019) around double descent,
such a criterion may be difficult to satisfy. We believe that this dimension
is an interesting one to explore in the future, but for now we focus only on
the over-parameterized case.

M

We believe our approach satisfies all the criteria outlined in this section
(even though some such as [C2] require further work). In the next section, we
contrast our approach with the leading alternatives using these criteria as
the framework for comparison.

##  12\. Comparison with Other Theories and Explanations

There has been a lot of work to understand the nature of deep learning. At the
highest level, we can categorize the efforts into two buckets: understanding
optimization, and understanding generalization. This follows from decomposing
the test loss as follows:

${\rm test\ loss}={\rm training\ loss}+{\rm generalization\ gap}$

where the generalization gap is defined as the difference between the test and
training losses.

The work on optimization focuses on trying to understand why given the non-
convexity of the fitting problem in general, gradient descent can reach good
global minima (and often zero training loss). On the other hand, the work on
generalization tries to understand why the generalization gap is small.
Although the work on optimization is fascinating in its own right, and there
may be reasons to believe that there is an interesting interplay between
optimization and generalization in deep learning (for example, our work
suggests that when one can optimize quickly, that is also when one is most
likely to generalize well), our focus here is on generalization. We refer the
reader to Liu et al. (2020a) as a recent entry point into the optimization
literature.

M
Approaches based on Uniform Convergence. Uniform convergence (Vapnik and
Chervonenkis, 1971) is the earliest and most popular mathematical tool for
proving generalization. This theory was initially developed to understand
under what circumstances is it possible to identify a model or a hypothesis
(from a possibly infinite family) based on only a finite training sample, and
it provided a framework to bound the generalization gap based on the
complexity of the family of hypotheses (quantified, for example, by notions
such as Vapnik-Chervonenkis (VC) dimension) from which the model was selected
relative to the size of the training set.

Early generalization bounds for neural networks were obtained by bounding
their VC dimension by the parameter count (Baum and Haussler, 1989), but even
then it was realized that far fewer training samples are needed for good
generalization in practice than is implied by these bounds. Bartlett (1996,
1998) showed in the case of sigmoid networks, that as long as the learning
algorithm finds a network with small weights, what matters for a small
generalization gap is not the number of weights (i.e., the parameter count),
but the size of weights (i.e., their norm).

The growing popularity of deep learning along with the surprising experimental
results of Zhang et al. (2017) (showing that deep networks used in practice
can easily fit random data) brought renewed attention to the generalization
problem in deep learning. The results of Zhang et al. (2017) imply that the
complexity of hypothesis class in the case of practical neural networks is
already too large in comparison with the size of the training set to make
these bounds non-vacuous (that is, they fail [C1]). This motivated a large
number of new investigations that try to capture the implicit bias or
regularization of gradient descent (for example, Bartlett et al. (2017);
Golowich et al. (2018); Arora et al. (2018); Neyshabur et al. (2018a);
Dziugaite and Roy (2017); Zhou et al. (2019); Li and Liang (2018); Allen-Zhu
et al. (2019a); Nagarajan and Kolter (2019a); Neyshabur et al. (2019)). While
these bounds aim to satisfy [C1], and often provide valuable insights into the
nature of deep learning, Nagarajan and Kolter (2019b) observe that they
generally fail to either have the correct architecture dependence ([C2]) or
are not applicable to the network obtained from gradient descent, but to some
modification thereof ([C3]). Furthermore, they point out that many of these
approaches (particularly, the non-PAC-Bayesian ones), fail in a more
fundamental way by failing to satisfy [C4]: the bounds on the generalization
gap obtained from these approaches increases with more training examples. This
happens because the bound depends on some norm of the weights (that is,
distance from initialization) that typically increases with larger training
sets.434343The PAC-Bayesian ones typically fail [C3] since they apply only to
stochastic ensembles. We discuss them in greater detail in a little later.

Finally, Nagarajan and Kolter (2019b) construct examples of overparameterized
problems involving linear models and neural networks where uniform convergence
provably fails to explain generalization. They show that the set of models
with low test error and actually explored by GD (that is, every model in the
set corresponds to a GD solution for some training set) is too large to get
anything other than an almost vacuous uniform convergence bound for its
members.

For the expert in uniform convergence, we note that the fact that uniform
convergence is necessary for learnability (in the setting of classification or
regression) does not preclude the fact that uniform convergence may be unable
to explain generalization in a particular algorithm for a particular
distribution (which is the situation we are faced with in explaining the
generalization mystery in deep learning). For a detailed discussion of this,
please see Appendix I of Nagarajan and Kolter (2019b). In fact, to their
argument, we may add that what we are interested in is not just a particular
algorithm for a particular distribution, but even a specific sample size. In
other words, a result that is asymptotic in sample size may not be
illuminating at all. For example, consider that there are only finitely many
ResNet-50 networks when the parameters are quantized to 32 bits. Thus, for a
large enough sample size, even the humble combination of Hoeffding’s
inequality and the union bound would provide a non-trivial bound on the
generalization gap, but that argument does not provide much insight on why
ResNet-50 trained with gradient descent generalizes well on ImageNet given the
tiny size of the actual ImageNet training set in comparison.

M

In comparison, our approach is not based on uniform convergence, but on a
different tool from learning theory, namely algorithmic stability, and so does
not suffer from the problems pointed out by Nagarajan and Kolter (2019b). In
particular, note that the bound in Theorem 1 has an explicit inverse
dependence on the size of the training set, as expected.

M
Previous approaches based on Algorithmic Stability. In short order after the
development of uniform convergence, an alternative framework was developed to
explain generalization in models based on “local rules” (for example, nearest
neighbors) where the complexity of the hypothesis class is not fixed but
scales with the size of the training dataset (Rogers and Wagner, 1978; Devroye
and Wagner, 1979). Unlike uniform convergence where the focus is on the size
of the space to be searched, the focus here is on how the algorithm searches
the space. This approach is now known as Algorithmic Stability (Bousquet and
Elisseeff, 2002; Shalev-Shwartz et al., 2010; Kearns and Ron, 1999), and the
key idea, as we saw, is as follows: If the model learnt from the training set
does not depend too much on any one training example (that is the presence or
absence of any one example does not change the model very much) then we expect
the model to generalize well.

Hardt et al. (2016) analyzed the stability of stochastic gradient descent in
the setting of deep learning under the assumption that each batch consists of
one example and the learning rate decays over time. Under these assumptions,
they are able to bound the generalization gap by the number of training steps,
a result they summarize by the slogan “train faster, generalize better.”
Kuzborskij and Lampert (2018) tighten the Hardt et al. (2016) bound by taking
into account the curvature of the loss function at initialization but at the
cost of a more onerous assumption: no training example is looked at more than
once.

This line of argument critically relies on the assumption that each training
sample is seen rarely (or not at all) and so the presence or absence of a
training sample cannot matter too much. But one should feel uneasy about such
an explanation since it may throw the baby out with the bath water. For
example, if we don’t see any example at all (that is, take 0 steps of training
and stay at the randomly chosen initial point), then the generalization gap
should be zero in expectation, that is, we should expect the training loss to
be an unbiased estimate of the test loss. The previous slogan taken to its
logical conclusion is: Train in no time, generalize perfectly!

So what has gone wrong? The problem is that the generalization mystery
requires us to keep in mind simultaneously the real data case and the random
data case, and what we need is a “differential” analysis of the two cases. In
other words, in the random case, if you see each example rarely (or not at
all), you will not be able to memorize it, but the fact that in practice
neural networks memorize random labels means that they are run for long enough
to see each example several times, and it is in that setting that we need to
explain generalization on real data. In other words, the existing stability
approaches fail to satisfy [C1] above. Finally, as noted in Section 7 of the
extended version444444https://arxiv.org/abs/1509.01240 of Hardt et al. (2016),
this approach does not extend to full-batch case, that is, it fails [C6].

M

Our result may be seen as a natural extension of this approach that takes into
account the dataset (more precisely, the interaction of the dataset and the
architecture) which is necessary to explain the generalization mystery.

M

We note here a line of work that combines stability and PAC-Bayesian analysis
to study noisy gradient descent (stochastic gradient Langevin dynamics) where
isotropic Gaussian noise is added at every SGD update step (thus failing to
meet [C3] and [C6]). Although a more detailed discussion is out of scope,
please see Li et al. (2020) for a starting point into this literature.

M
Sharpness and Flatness of Minima. A popular explanation of why SGD generalizes
well in large networks in practice is based on the empirical observation that
the minima found by SGD are “flat,” that is, they are in regions where the
overall loss (on the training set) does not change very much around the