Coherent Gradients: An Approach to Understanding Generalization in Gradient Descent-based Optimization
Authors: Satrajit Chatterjee
Venue:  (2020)
Keywords: generalization
deep learning

Abstract: An open question in the Deep Learning community is why neural networks trained with Gradient Descent generalize well on real datasets even though they are capable of fitting random data. We propose an approach to answering this question based on a hypothesis about the dynamics of gradient descent that we call Coherent Gradients: Gradients from similar examples are similar and so the overall gradient is stronger in certain directions where these reinforce each other. Thus changes to the network parameters during training are biased towards those that (locally) simultaneously benefit many examples when such similarity exists. We support this hypothesis with heuristic arguments and perturbative experiments and outline how this can explain several common empirical observations about Deep Learning. Furthermore, our analysis is not just descriptive, but prescriptive. It suggests a natural modification to gradient descent that can greatly reduce overfitting.

Published as a conference paper at ICLR 2020
COHERENT GRADIENTS: AN APPROACH TO UNDERSTANDING GENERALIZATION IN GRADIENT DESCENT-BASED OPTIMIZATION
Satrajit Chatterjee
Google AI
Mountain View, CA 94043, USA
schatter@googl com
ABSTRACT
An open question in the Deep Learning community is why neural networks trained with Gradient Descent generalize well on real datasets even though they are capable of fitting random data. We propose an approach to answering this question based on a hypothesis about the dynamics of gradient descent that we call Coherent Gradients: Gradients from similar examples are similar and so the overall gradient is stronger in certain directions where these reinforce each other. Thus changes to the network parameters during training are biased towards those that (locally) simultaneously benefit many examples when such similarity exists. We support this hypothesis with heuristic arguments and perturbative experiments and outline how this can explain several common empirical observations about Deep Learning. Furthermore, our analysis is not just descriptive, but prescriptive. It suggests a natural modification to gradient descent that can greatly reduce overfitting.
INTRODUCTION AND OVERVIEW
Neural networks used in practice often have sufficient effective capacity to learn arbitrary maps from their inputs to their outputs. This is typically demonstrated by training a classification network that achieves good test accuracy on real dataset S, on a modified version of S (call S') where the labels are randomized and observing that the training accuracy course, the test accuracy is no better than chance (Zhang et al. (017). This leads to an important open question in the Deep Learning community (Zhang al. (201 7 Arpit et al. (2017); Bartlett et al. (2017); Kawaguchi et al. (2017); Neyshabur et (2018) Arora et al. (2088) Belkin et al. (2019); Rahaman al. (2019) ; Nagarajan & Kolter (2019), etc.): Among all maps that fit real dataset, how does Gradient Descent (GD) find one that generalizes well? This is the question we address in this paper.
S' is very high, though, of
We start by observing that this phenomenon is not limited to neural networks trained with GD but also applies to Random Forests and Decision Trees. However, there is no mystery with trees: 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 achieve good training accuracy (but, of course, at the cost of poor generalization). Thus, trees that achieve good accuracy on randomized dataset are much larger than those on a real dataset (e.g. Chatterjee & Mishchenko (2019 Expt. 5)).
possible that something similar happens with GD? We believe so. The type of randomized-labes experiments described above show that if there are common patterns to be found, then GD finds them. not, it fits each example on case-by-case basis. The question then is, what it about the dynamics of GD that makes it possible to extract common patterns from the data? And what does it mean for pattern to be common?
Since the only change the network parameters in GD comes from the gradients, the mechanism to detect commonality amongst examples must be through the gradients. We propose that this commonality detection can be explained follows:

---

Published as a conference paper at ICLR 2020
1. Gradients are coherent, i.e, similar examples (or parts of examples) have similar gradients (or similar components of gradients) and dissimilar examples have dissimilar gradients.
2. Since the overall gradient is the sum of the per-example gradients, it is stronger in directions 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.
3. Since network parameters are updated proportionally to gradients, they change faster in the direction of stronger gradients.
4. Thus the changes to the network during training are biased towards those that simultaneously benefit many examples instead of few (or one example).
For convenience, we refer to this as the Coherent Gradients hypothesis.
is instructive to work through the proposed mechanism in the context of simple thought experiment. Consider a training set with two examples a and At some point in training, suppose the gradient of a, Ia- can be decomposed into orthogonal components ga, and Jop of roughly equal magnitude, i.e,, there are two, equally good, independent ways which the network can better fit a (by using say two disjoint parts of the network). Likewise, for b. Now, further suppose that one of the two ways is common to both a and 6, i.e. say 9og 9b2 9ah, whereas, the other two are example specific, i.e., (9a1 9b. = O. Now, the overall gradient
9a gb 9a, + 2 Gab + 9b1-
Observe that the gradient is stronger in the direction that simultancously helps both examples and thus the corresponding parameter changes are bigger than those those that only benefit only one example
It is important to emphasize that the notion of similarity used above (i.e., which examples are consid- ered similar) is not a constant but changes in the course of training as network parameters change. starts from mostly task independent notion due random initialization and is bootstrapped in the course of training to be task dependent. We say "mostly" because even with random initialization, examples that are syntactically close treated similarly (e-g., two images differing in the intensities of some pixels as opposed to two images where one is translated version of the other).
The relationship between strong gradients and generalization can also be understood through the lens of algorithmic stability (Bousquet& & Elisseeff 2002): ; strong gradient directions are more stable since the presence or absence of a single example does not impact them as much, as opposed to weak gradient directions which may altogether disappear if a specific example is missing from the training set. 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 preserved. However, if some parameter updates are due to weak gradient directions, then stability Schale--hwarrd
is diminished. Since stability (suitably formalized) is equivalent to generalization how generalization may degrade as training progresses. Based
et al. 2010), this allows on this insight, we shall see later how a simple modification to GD to suppress the weak gradient directions can dramatically reduce overfitting.
In addition to providing insight into why GD generalizes in practice, we believe that the Coherent Gradients hypothesis can help explain several other empirical observations about deep learning in the literature:
(a) Learning slower with random labels than with real labels (Zhang al. 2017 2017)
Arpit et al.
(b) Robustness to large amounts of label noise (Rolnick et al.
2017
(c) Early stopping leads better generalization (Caruana et al.
2000)
(d) Increasing capacity improves generalization (Caruana et al. 2000
Neyshabur et al. 2018)
(c) The existence of adversarial initialization schemes (Liu et al
2019
(f) GD detects common patterns even when trained with random labels Chatterjee &
Mishchenko 2019)
While the mechanism is casiest to see with full or large minibatches, we believe it holds even for small minihatches (though there has to consider the bias in updates over time).
2

---

Published as a conference paper at ICLR 2020
A direct experimental verification of the Coherent Gradients hypothesis is challenging since the notion of similarity between examples depends on the parameters of the network and thus changes during training. Our approach, therefore, is to design intervention experiments where we establish a baseline and compare it against variants designed to test some aspect or prediction of the theory. As part of these experiments, replicate the observations (a)-(c) in the literature noted above, and analyze the corresponding explanations provided by Coherent Gradients (: and outline for future work how (d)-() may be accounted for (:5)
In this paper, we limit our study to simple baselines: vanilla Stochastic Gradient Descent (SGD) on MNIST using fully connected networks. We believe that this is good starting point, since even in this simple setting, with all frills eliminated (e.g., inductive bias from architecture or explicit regularization, or more sophisticated optimization procedure), we are challenged to find satisfactory explanation of why SGD generalizes well. Furthermore, our prior is that the difference between weak and strong directions is small at any one step of training, and therefore having a strong learning signal as in the case of MNIST makes direct analysis of gradients easier. It also has the benefit of having smaller carbon footprint and being easier to reproduce. Finally, based on preliminary experiments on other architectures and datasets we optimistic that the insights we get from studying this simple setup apply more broadly.
EFFECT OF REDUCING SIMILARITY BETWEEN EXAMPLES
Our first test of the Coherent Gradients hypothesis see what happens when we reduce similarity between examples. Although, at any point during training, we do not know which examples are similar, and which are different, we can (with high probability) reduce the similarity among training examples simply by injecting label noise. In other words, under any notion of similarity, adding label noise to a dataset that has clean labels likely to make similar examples less similar. Note that this perturbation does not reduce coherence since gradients still depend on the examples. (To break coherence, we would have to make the gradients independent of the training examples which would requiring perturbing SGD itself and not just the dataset).
2.1 SETUP
For our baseline, we use the standard MNIST dataset of 60,000 training examples and 10,000 test examples. Each example is a 28x28 pixel grayscale handwritten digit along with a label ("0'-"9'), We train a fully connected network on this dataset. The network has one hidden layer with 2048 ReLUs and output layer with a way softmax. We initialize it with Xavier and train using vanilla SGD (i.e., no momentum) using cross entropy loss with a constant learning rate of 0.1 and minibatch size of 100 for 10a steps (i.e., about 170 epochs). We do not use any explicit regularizers.
We perturb the baseline by modifying only the dataset and keeping all other aspects of the architecture and learning algorithm fixed. The dataset is modified by adding various amounts of noise (25%, 50% 75%, and 100%) to the labels of the training set (but not the test set). This noise is added by taking, say in the case of 25% label noise, 25% of the examples at random and randomly permuting their labels. Thus, when we add 25% label noise, we still expect about 75% + 0.1 25%, i.e., 77.5% of the examples to have unchanged (i.e. "correct") labels which we call the proper accuracy of the modified dataset. In what follows, we call examples with unchanged labels, pristine, and the remaining, corrupt. Also, from this perspective, it is convenient to refer to the original MNIST dataset as having 0% label noise.
We use a fully connected architecture instead of a convolutional one to mitigate concerns that some of the difference in generalization between the original MNIST and the noisy variants could stem from architectural inductive bias. We restrict ourselves to only hidden layer to have the gradients be as bel-ebehaved as possible. Finally, the network width, learning rate, and the number of training steps are chosen to ensure that exactly the same procedure is usually able to fit all variants to 100% training accuracy.
3

---

Published as a conference paper at ICLR 2020
2.2 QUALITATIVE PREDICTIONS
Before looking at the experimental results, it is useful to consider what Coherent Gradients can qualitatively say about this setup. In going from 0% label noise to 100% label noise, as per experiment design, we expect examples in the training set to become more dissimilar (no matter what the current notion of similarity is). Therefore, we expect the per-example gradients to be less aligned with each other. This in turn causes the overall gradient to become more diffuse, i.e., stronger directions become relatively weaker, and consequently, we expect it to take longer to reach a given level accuracy as label noise increases, i.e., to have a lower realized learning rate.
This can made more precise by considering the following heuristic argument. Let Og the vector of trainable parameters of the network at training step t. Let L denote the loss function of the network (over all training examples). Let gi be the gradient of at 8, and let a denote the learning rate. By Taylor expansion, first order, the change AL, in the loss function due small gradient descent step h4 = a 9t. is given by
AL. = L(O, + 14) - ((,,)= ~ (gt, ha) - (9t, = - ||
(1)
where || denotes the m2-nrmm. Now, let gte denote the gradient of training example at step t. Since the overall gradient is the sum of the per-example gradients, we have,
| ge) _ gte: Egie) gie) Σ (gte: Ihe')
Σ 19 +
(gtes (gtesgte))
e,e' esfie
Now, heuristically, let us assume that all the ||9tel are roughly the same and equal to | which is not entirely unreasonable (at least at the start of training. if the network has no a priori reason to treat different examples very differently). If all the per-example gradients are approximately orthogonal (i.e., (yte; Irer)
for A e'), then [| zs m |198 II2 where m is the number of examples. On the other hand, if they are approximately the same (i.e.. (gte, Ite') ze ||,];1]),, then [| z m² !| 2|2. Thus, we expect that greater the agreement in per-example gradients, the faster loss should decrease.
Finally, for datasets that have significant fractions of pristine and corrupt examples (i.e., the 25%, 50%, and 75% noise) we can make a more nuanced prediction. Since, those datasets, the pristine examples group still more similar than the corrupt ones, we expect the pristine gradients to continue to align well and sum up to a strong gradient. Therefore, we expect them to be learned faster than the corrupt examples, and rate closer to the realized learning rate in the 0% label noise case. Likewise, we expect the realized learning rate on the corrupt examples to be closer to the 100% label noise case. Finally, as the proportion of pristine examples falls with increasing noise, we expect the realized learning rate for pristine examples to degrade.
Note that this provides an explanation for the observation in the literature that that networks can learn even when the number of examples with noisy labels greatly outnumber the clean examples as long as the number of clean examples sufficiently large (Rolnick et al., (017)) since with too few clean examples the pristine gradients are not strong enough to dominate.
2.3 AGREEMENT WITH EXPERIMENT
Figure a and (b) show the training and test curves for the baseline and the 4 variants. We note that for all 5 variants, at the end of training, we achieve 100% training accuracy but different amounts of generalization. As expected, SGD is able to fit random labels, yet when trained on real data, generalizes well. Figure 1(c) shows the reduction in training loss over the course training, and Figure (d) shows the fraction of pristine and corrupt labels learned training processes.
The results are in agreement with the qualitative predictions made above:
1. In general, as noise increases, the time taken to reach given level of accuracy (i.e., realized learning rate) increases.
2. Pristine examples are learned faster than corrupt examples. They are learned at rate closer to the 0% label noise rate whereas the corrupt examples are learned at a rate closer to the 100% label noise rate.
4

---

Published as a conference paper at ICLR 2020
10
15
2013
12
0.2
3.0
0.0
207
10"
10'
10'
10'
trahing stpp
tntringg deep
(a) Training accuracy.
(b) Validation accuracy.
3.0
1.0
2.5
0.8
0.4
02
30
trairing
Training loss.
(d) First training step when example is learned.
Figure 1: Results of the experiment to reduce similarity by adding label noise ($)
3. With fewer pristine examples, their learning rate reduces. This most clearly seen in the first few steps of training by comparing say 0% noise with 25% noise.
Using Equation 1 note that the magnitude of the slope of the training loss curve is good measure of the square of the 12-norm of the overall gradient. Therefore, from the loss curves of Figure (c)), is clear that in early training, the more the noise, the weaker the 22- 12-norm of the gradient. If we assume that the per-example 12-norm is the same in all variants at start of training, then from Equation 2 it is clear that with greater noise, the gradients are more dissimilar.
Finally, we note that this experiment is an instance where early stopping (e.g.. Caruana et al. (2000) effective. Coherent gradients and the discussion in provide some insight into this: Strong gradients both generalize well (they are stable since they are supported by many examples) and they bring the training loss down quickly for those examples. Thus early stopping maximizes the use of strong gradients and limits the impact of weak gradients. (The experiment in the ( discusses different way to limit the impact of weak gradients and is an interesting point of comparison with early stopping.)
2.4 ANALYZING STRONG AND WEAK GRADIENTS
Within each noisy dataset, we expect the pristine examples to be more similar to each other and the comrupt ones to be less similar. In turn, based on the training curves (particularly, Figure (c)). during the initial part training, this should mean that the gradients from the pristine examples should be stronger than the gradients from the corrupt examples. We can study this effect via different decomposition of square of the 1o-morm the gradient (of equivalently upto a constant, the change in the loss function):
(ge, g.) = (gt, of + gt) = (gt, gf + (ge,gE)
where of and of are the sum of the gradients of the pristine examples and corrupt examples respec- tively. (We cannot decompose the overall norm into a sum of norms of pristine and corrupt due to the cross terms (ge gf). With this decomposition, we attribute the cross terms equally to both.) Now, set ff = <...9,> to pristine and corrupt each time step respectively (and we have fl + ff 1), and based on the foregoing, we expect the pristine fraction to be a larger fraction of the total when training starts and to diminish as training progresses and the pristine examples are fitted.
(gc=a") and ff (9.:9]] Thus, ff and fi represent the fraction of the loss reduction due
5

---

Published as a conference paper at ICLR 2020
0-0
1.2
1.0
0.8
0.
08
0.2
-5.2
-0.2
-1.2
-0.4
10'
10'
10
10
1.4
144
1-2
1.2
0.6
0.6
0.4
10'
10
10
1:3
1.0
0.
2.8
0.
0.2
0.2
-0.2
-22
-0.4
10'
12a
201
10'
10'
10
161
1.4
1.4
1.2
122
0.4
0.8
0.4
0.3
(1291 slop
Paniing Size
Figure 2: Relative contributions of pristine (similar) and corrupt (dissimilar) examples point-in- time loss reduction. To get a sense statistical significance, we show the actual statistic as well as simulations under the null assuming there is difference. See $2.4
The first row of Figure shows plot of estimates of ff and ff for 25%. 50% and 75% noise. These quantities were estimated by recording sample of 400 per-example gradients for 600 weights (300 from each layer) the network. We see that for 25% and 50% label noise, J initially starts off higher than fi and after a few steps they cross over. This happens because at that point all the pristine examples have been fitted and for most of the rest of training the corrupt examples need to be fitted and they largely contribute to the (2-norm of the gradient (or equivalently by Equation to loss reduction). Only at the end when the corrupt examples have also been fit, the two curves reach parity. In the case of 75% noise, slope downwards for the contribution from pristine examples. We believe this is because of the sheer number of corrupt examples, and their sum dominates.
that the cross over doesn't 't happen, but there is slight
though the individual corrupt example gradients weak,
To get sense of statistical significance in our hypothesis that there difference between the pristine and corrupt examples as group. in the remaining rows of Figure 2 we construct a null world where there is difference between pristine and corrupt. We do that by randomly permuting the "corrupt" and "pristine" designations among the examples (instead of using the actual designations) and reploting. Although the null pristine and corrupt curves are mirror images (as they must be even in the null world since each example is given one of the two designations), we note that for 25% and 50% they do not cross over as they with the real data. This increases our confidence that the null may be rejected. The 75% case weaker but only the real data shows the slight downward slope in pristine which none of the nulls typically show. However, all the nulls do show that corrupt is more than pristine which increases two sets. (Note that this happens in reverse in the 25% case: pristine is always above corrupt, but they never cross over in the null worlds.)
confidence that this is due to the significantly differing sizes of the
To get a stronger signal for the difference between pristine and corrupt in the 75% case, we can look different statistic that adjusts for the different sizes of the pristine and corrupt sets. Let [pl and [c]

---

Published as a conference paper at ICLR 2020
10-B 20% abeliardentariin
10-8 50% lis rnndomcaato
10-8 8 lnbl/radeeeaaddnnn
3.0
3.0
2.0
1.5
1.5
155
3.5
0.5
0.5
10
10
10-8
10
2.0
2.0
200
1.0
100
03
1e-8
3.0
1e-8
1e-8
25
25
23
1.0
10
0.0
0.0
1e-8
1e-8
3.0 1e-8
3.0
15
15
10
10
30
2r00ing stop
King 1000
trating stop
Figure 3: Contributions of mean pristine (similar) and corrupt (dissimilar) examples to loss reduction accumulated over first few steps of training. To get a sense statistical significance, we show the actual statistic well simulations under the null assuming there is difference. See 2.4
be the number of pristine and corrupt examples respectively. Define
(gr,gh>> o
and i
(gv: gEt
which represents first order and upto scale factor (a) the mean cumulative contribution of pristine or corrupt example up until that point in training (since the total change loss from the start of training to time is approximately the sum of first order changes in the loss at each time step).
The first row Figure ssows pristine and corrupt the most pronounced. As before, give sense of statistical significance, the remaining rows show the same plots in null worlds where we randomly permute the pristine or corrupt designations of the examples. The results appear somewhat significant but overwhelmingly so. It would be interesting to redo this on the entire population of examples and trainable parameters instead of small sample.
shows o and i for the first 10 steps of training where the difference between
3 EFFECT OF SUPPRESSING WEAK GRADIENT DIRECTIONS
In the second test of the Coherent Gradients hypothesis, we change GD itself in very specific (and to our knowledge, novel) manner suggested by the theory. Our inspiration comes from random forests. As noted in the introduction, by building sufficiently deep trees random forest algorithm can get perfect training accuracy with random labels, yet generalize well when trained on real data. However, if we limit the tree construction algorithm to have certain minimum number of examples in each leaf, then it no longer overfits. In the case of GD, we can do something similar by suppressing the weak gradient directions.
7

---

Published as a conference paper at ICLR 2020
3.1 SETUP
Our baseline setup is the same as before (22 but we add a new dimension by modifying SGD to update each parameter with a "winsorized" gradient where clip the most extreme values (outliers) among all the per-example gradients. Formally, let Jwe be the gradient for the trainable parameter w for example e. The usual gradient computation for
Iw Σ Jwe
Now let E [0,50) 50] be hyperparameter that controls the level of winsorization. Define bo be the c-th percentile of Swe taken over the examples. Similarly, let uw be the (100 - (100-c)-tt percentile. Now, compute the e-winsorized gradient for w (denoted by Fwr as follows:
9w Σ clip(gwer bw Uww
The change gradient descent is simply use Lh instead of Iw when updating each step.
Note that although this is conceptually a simple change, it is computationally very expensive due to the need for per-example gradients. To reduce the computational cost we only use the examples in the minibatch to compute la and thr- Furthermore, instead of using hidden layer of 2048 ReLUs, we use a smaller network with 3 hidden layers of 256 ReLUs each, and train for 60,000 steps (i.e.. 100 epochs) with fixed learning rate of 0.1. We train on the baseline dataset and the 4 noisy variants with c {0, 1,2, 4, 8). Since we have 100 examples each minibatch, the value of e immediately tells us how many outliers are clipped in each minibatch. For example, = 2 means the 2 largest and 2 lowest values of the per-example gradient are clipped (independently for each trainable parameter in the network), and 0 corresponds to unmodified SGD.
3.2 QUALITATIVE PREDICTIONS
the Coherent Gradient hypothesis is right, then the strong gradients are responsible for making changes to the network that generalize well since they improve many examples simultaneously. On the other hand, the weak gradients lead to overfitting since they only improve a few examples. By winsorizing each coordinate, suppress the most extreme values and thus ensure that parameter is only updated in a manner that benefits multiple examples. Therefore:
Since e controls which examples are considered extreme, the larger e is, the less we expect the network to overfit.
But this also makes it harder for the network to fit the training data, and so we expect the training accuracy to fall as well.
Winsorization will not completely eliminate the weak directions. For example, for small values of we should still expect overfitting happen over time though at a reduced rate since only the most egregious outliers are suppressed.
3.3 AGREEMENT WITH EXPERIMENT
The resulting training and test curves shown in Figure The columns correspond to different amounts of label noise and the rows different amounts of winsorization. In addition to the training and test accuracies (ta and va, respectively), we show the level of overfit which is defined as ta c 10 + (1 <) va] account for the fact that the test labels not randomized.
We see that the experimental results are in agreement with the predictions above. In particular,
For c 1, training accuracies do not exceed the proper accuracy of the dataset, though they may fall short, specially for large values of c.
The rate which the overfit curve grows goes down with increasing c.
Additionally, notice that with large amount of winsorization, the training and test accuracies reach a maximum and then go down. Part of the reason is that as a result winsorization, each step no longer in descent direction, i.e., this is no longer gradient descent.
8

---

Published as a conference paper at ICLR 2020
501
121
127
32
12
3F
Figure Effect of suppressing weak gradient directions by eliminating outlier per-example gradients. This is done independently for each trainable parameter. Overfit is measured after accounting for the fact that test labels are not randomized 33.3
DISCUSSION AND RELATED WORK
Although there has been lot of work in recent years in trying to understand generalization in Deep Learning, no entirely satisfactory explanation has emerged so far.
There is rich literature on aspects of the stochastic optimization problem such as the loss landscape 2015) Zhu al. (2018)) 8)), the curvature around stationary points
and minima (e.g., [horomanska (e.g., Hochrriter & Schmidhuber (1997) : Keskar et al. (2016) Dinh et al. (2017): Wu et al. (2018)). and the implications stochasticity due to sampling in SGD (e.g., Simsekli et al. (019)). However, we believe it should be possible to understand generalization without detailed understanding of the optimization landscape. For example, since stopping early typically leads to small generalization gap. the nature of the solutions of GD (e.g., stationary points, the limit cycles of SGD at equilibrium) cannot be solely responsible for generalization. In fact, from this observation, it would appear that an inductive argument for generalization would be more natural. Likewise, there is reason to believe that stochasticity is not fundamental to generalization (though it may help). For example, modifying the experiment [2.1 use full batch leads to similar qualitative generalization results. This consistent with other small scale studies (c.g., Figure of of et al. (2018) though we are not aware of any large scale studies on full batch.
Our view of optimization is simple, almost combinatorial, one: gradient descent is greedy search with some hill-climbing thrown in (due to sampling SGD and finite step size). Therefore, we worry less about the quality of solutions reached, 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 look at the transition dynamics to see if that preserves generalizability.
Another approach to understanding generalization, is to argue that gradient-based optimization induces a form of implicit regularization leading bias towards models of low complexity. This an extension of the classical approach where bounding a complexity measure leads to bounds on the generalization gap. As is well known, classical measures of complexity (also called capacity) do not work well. For example, sometimes adding more parameters to a net can help generalization (see for e.g. Lawrence al. (199)); Neyshabur al. (2018) and, have seen, VC-Dimension

---

Published as a conference paper at ICLR 2020
and Rademacher Complexity-bant based bounds must be vacuous since networks can memorize random labels and yet generalize on real data. This has led to a lot of recent work in identifying better measures of complexity such as peettaallynormmaizedd margin (Bartlett et al. 2017), path-based group norm (Neyshabur et al. 2018), a compression-based approach (Arora et al. 2018). etc. However, to our knowledge, none of these measures is entirely satisfactory for accounting for generalization in practice. Please see Nagarajan & Kolter (2019) for an excellent discussion of the challenges.
We rely on different classical notion to argue generalization: algorithmic stability (see [ouuquee & Elisseeff (202) for a historical overview). We have provided only an informal argument in Section 1, but there has been prior work by Hardt et al. (2016) in looking at GD and SGD through the lens of stability, but their formal results do not explain generalization in practical settings (e.g.. multiple epochs of training and non-convex objectives). In fact, such an attempt appears unlikely to work since our experimental results imply that any stability bounds for SGD that do not account for the actual training data must be vacuous! (This was also noted by Zhang et al. (2017).) That said, we believe stability is the right way to think about generalization in GD for few reasons. First, since by Shalev-Shwartz et al. (211)) stability, suitably formalized, is equivalent to generalization. Therefore, in principle, any explanation of generalizability for learning problem must to borrow a term from category theory- factor through stability. Second, a stability based analysis may be more amenable to taking the actual training data into account (perhaps by using a "stability accountant" similar to privacy accountant) which appears necessary to get non-vacuous bounds for practical networks and datasets, Finally, as we have seen with the modification in 3 a stability based approach is not just descriptive but prescriptive and can point the way to better learning algorithms.
Finally, we look at two relevant lines of work pointed out by a reviewer. First, Rahaman et al. (019)) compute the Fourier spectrum of ReLU networks and argue based on heuristics and experiments that these networks learn low frequency functions first. In contrast, we focus not on the function learnt, but on the mechanism in GD to detect commonality. This leads to perspective that is at once simpler and more general (for e.g.. it applies equally to networks with other activation functions, with attention, LSTMss and discrete (combinatorial) inputs). Furthermore, it opens up a path to analyzing generalization via stability. It is is not clear if Rahaman et al. (2019) claim a causal mechanism, but their analysis does not suggest an obvious intervention experiment such as ours of 3 to test causality. There are other experimental results that show biases towards linear functions (Nakkiran et al. 2019) and functions with low descriptive complexity (Valle- Perez et al. 2019) but these papers do not posit a causal mechanism. It is interesting to consider if Coherent Gradients can provide a unified explanation for these observed biases.
Second, Fort et a (019) propose a descriptive statistic stiffness based on pairwise per-example gradients and show experimentally that it can be used characterize generalization. [Sankararaman et al. (211)) propose a very similar statistic called gradient confusion but use it to study the speed of training. Unlike our work, these do not propose causal mechanisms for generalization, but these statistics (which are different from those in (2.4 could be useful for the further study of Coherent Gradients.
5 DIRECTIONS FOR FUTURE WORK
Does the Coherent Gradients hypothesis hold in other settings such as BERT, ResNet, etc.? For that we would need to develop more computationally efficient tests. Can we use the state of the network to explicitly characterize which examples are considered similar and study this evolution in the course of training? We expect non- non-paraettric methods for similarity such as those developed in Chatterjee & Mishchenko and their characterization of "casy" examples (i.e., examples learnt early as per Arpit et al. (007)) as those with many others like them, to be useful in this context.
Can Coherent Gradients explain adversarial initializations (Liu et al. 2019)? The adversarial initial state makes semantically similar examples purposefully look different. Therefore, during training. they continue to be treated differently (i.e., their gradients share less in common than they would if starting from a random initialization). Thus, fitting is more case-by-a by-case and while achieves good final training accuracy, does not generalize.
"See http://wwww.faaoomo.cco////////e for nice discussion of the difference.
10

---

Published as a conference paper at ICLR 2020
Can Coherent Gradients along with the Lottery Ticket Hypothesis (Frankle & Carbin 2018 explain the observation in Neyshabur et al. (2018) that wider networks generalize better? By Lottery Ticket, wider networks provide more chances to find initial gradient directions that improve many examples, and by Coherent Gradients, these popular hypotheses are learned preferentially (faster).
Can we use the ideas behind Winsorized SGD from } develop computationally efficient learning algorithm with generalization (and even privacy) guarantees? How does winsorized gradients compare in practice the algorithm proposed in Abadi et al. (2016) for privacy? Last, but not least, can we use the insights from this work to design learning algorithms that operate natively on discrete networks?
ACKNOWLEDGMENTS
I thank Alan Mishchenko, Shankar Krishnan, Piotr Zielinski, Chandramouli Kashyap. Sergey Ioffe, Michele Covell, and Jay Yagnik for helpful discussions.
REFERENCES
Martin Abadi, Andy Chu, Ian Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, CCS '1, pp. 308-318, New York, NY, USA, 2016. ACM. ISBN 41341 doi: 10. 10.1145/2976749 http:://on acm. 100 010....111122979411 2978818
URL
Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang. Stronger generalization bounds for deep nets via a compression approach. In Jennifer G. Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning. ICML 2018. Stockholmsmüssan, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Muchine Learning Reseurch, pp. 254 PMLR, 2018. URL. http:htttp/:poceeeeeeo
ngs m r. wwwps/ressspppe vt0 /t/0////rrrrrr. 1 html
Devansh Arpit, Stanislaw K. Jastrzebski, Nicolas Ballas, David Krueger, Emmanuel Bengio, Maxin- der S. Kanwal, Tegan Maharaj, Asja Fischer, Aaron C. Courville, Yoshua Bengio, and Simon Lacoste-Julien. A closer look memorization in deep networks. In Proceedings of the 34th Inter- national Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, htmll
pp. 233-242, 2017. URL
ml http:///ww.........ssrsss/////// wttpaas//1//aappp...p
Peter I. Bartlett, Dylan J Foster, and Matus J Telgarsky. Opectrally-normalizee margin bounds for Guyon, U. V. Luxburg, Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems 30, pp. 6240-6249. Curran Associates, Inc., 2017.
neural networks.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine-learning practice and the classical bias-variance trade-off. Proceedings of the National Academy of Sciences, 1 15839)):1189911588558 2019. ISSN 0027-8424. doi: 10.1073/pnas. h0073//ass.19007000 1903070116 16. URL.
https: wwww pnas org/ entoteen/// 116/1116/00 /0066//211888
Olivier Bousquet and André Elisseeff. Stability and generalization. Mach. Learn. Res., 2: 499-526, March 2002. ISSN 1532-4435, doi: 10. 10.112//532233072200007777
URL https
//doi.org// 0. (111111///2442222 0204444443277277700 662207044
Rich Caruana, Steve Lawrence, and Lee Giles. Overfitting in neural nets: Backpropagation, conjugate gradient, and early stopping. In Proceedings of the 13th International Conference on Neural Information Processing Systems, NIPS 00, pp. 381-3811 Cambridge, MA, USA, 2000. MIT Press. URL httphhttp//dlll acm. wwt.a//........iaaaa.ooc..ciiiia
Satrajit Chatterjee and Alan Mishchenko. based intrinsic methods to detect overfitting. CoRR, abs/1997.0199 2019. URL http:tttt//aaat www.//iwwwii.iaaaooooooa abs/ 10011.1997911111
Anna Choromanska, Mikael Henaff, Michaël Mathieu, Gérard Ben Arous, and Yann LeCun. The loss surfaces of multilayer networks. In Guy Lebanon and S. V. N. Vishwanathan (eds.), Proceed- ings of the Eighteenth International Conference on Artificial Intelligence and Statistics, AISTATS 2015, San Diego, California, USA, May 9-12, 2015, volume 38 of JMLR Workshop and Con- ference Proceedings. JMLR.org, 2015. URL cchrrmanskall 15.mml1
mlr. pr8ss/v38/

---

Published as a conference paper at ICLR 2020
Laurent Dinh, Razvan Pascanu, Samy Bengio, and Yoshua Bengio. Sharp minima can generalize for deep nets. CoRR, aws//1/0..04990000 2017. htRt://t://atttt org abs/1703... 04933
Stanislav Fort, Pawel Krzysztof Nowak, and Srini Narayanan. Stiffness: A new perspective on generalization in neural networks. CoRR, abs/1901.09491, 2019. URL http::/axx.v.or//
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Training pruned neural networks. CoRR, 0oss/8033006335 2018. htLL:tttp///aaxl...rrr/rbbbbb///
03635
Moritz Hardt, Benjamin Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In Proceedings of the 33rd International Conference on International Conference Machine Learning Volume 48, ICML pp. 1225-1234 JMI...rrg 2016. URL
http://dl. acm. org/ citatiin..n... c fm? d=330433000000 3045520
Sepp Hochreiter and Jürgen Schmidhuber. Flat minima. Neural Comput., 9(1): Januaary 1997.
ISSN 0899-7667. doi: htt.6///ncco.999..999 URL http: http://xxxdoii..oooooooo wtt.://ooo...o//011//1.111. neco 1997.9.1.1
K. Kawaguchi, L. Pack Kaelbling, and Y. Bengio. Generalization in Deep Learning. ArXiv e-prints, December 2017. URLhtttps: http///axvvvvoo wtt.aaaww...ggas///aa/aaaaaaaa/a /1710. 07471.0.5444888 45468v2
Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Peter Tang. On large-batch training for deep learning: Generalization gap and sharp minima. CoRR, abs/1609.04836 2016. htL:ttp: ptattp://arxiie ort. http//bs//11000 04836
Steve Lawrence, C. Lee Giles, and Ah Chung Tsoi. What size neural network gives optimal generalization? convergence properties of backpropagation. Technical report, 1996.
Shengchao Liu, Dimitris S. Papailiopoolos, and Dimitris Achlioptas. Bad global minima exist and SGD can reach them. CoRR, abs/1906. 1901//2666.1,,,,. 2019. URL http:p://aaxiv.org//ee
1906
02613
Vaishnavh Nagarajan and J. Zico Kolter. Uniform convergence may be unable to explain general- ization in deep learning. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' "'lchh-Bus -uc, Emily B. Fox. and Roman Gareett (eds.). Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, 8-14 December 2019, Vancouver, BC, Canada, pp. 1161 1-61-1110 1622, 2019.
Preetum Nakkiran, Gal Kaplun, Dimitris Kalimeris, Tristan Yang, Benjamin L. Edelman, Fred Zhang, and Boaz Barak. SGD on neural networks learns functions of increasing complexity. CoRR, abs/1905. 1600,, 2019. URL BRLp:ttp///aret
org/ hwtp://bs/11000 11604
Behnam Neyshabur, Zhiyuan Li, Srinadh Bhojanapalli, Yann LeCun, and Nathan Srebro. Towards understanding the role of over-parametriizatoo in generalization of neural networks. CORR, hbs/1805.12011 2018. http://///aaxx org/ tabb/1805.
Nasim Rahaman, Aristide Baratin, Devansh Arpit, Felix Draxler, Min Lin, Fred Hamprecht, Yoshua Bengio, and Aaron Courville. On the spectral bias of neural networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 5301-5310, Long Beach, California, USA, 09-15 15 Jun 2019. PMLR. URL.att::///rrceeeeee
ml wwwpseeesvvveeee v
Eahaman19a html
David Rolnick, Andreas Veit, Serge J. Belongie, and Nir Shavit. Deep learning is robust to massive label noise. CoRR,
2017. http:/tttt://i..../aaaaaaaa http:://wwwwwwx....aaaa http://wwwor//ab////oooa//
Karthik Abinav Sankararaman, Soham De. Zheng Xu. W. Ronny Huang, and Tom Goldstein. The impact of neural network overparameterization on gradient confusion and stochastic gradient descent. CoRR, abs//194.0063 2019. URL /tt///aaxx wtwpaaaivvvvv.o. wrg. abs///////// 1 904. 06963
Shai
Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Learnabllity, stability and uniform convergence. Mach. Learn. Res., 022633526700 December 2010. ISSN 1532-4435. URL U hhttp://d1: cm. orgg citaiiiiiiiiooo cfm? di 105600000100666666.1m11 993319
12

---

Published as a conference paper at ICLR 2020
Umut Simsekli, Levent Sagun, and Mert Gürbüzbalaban. A tail-index analysis of stochastic gradient noise deep neural networks. In Kamalika Chaudburi and Ruslan Salakhutdinov (eds.). Proceed- ings of the 36th International Conference on Machine Learning, ICML 2019. 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pp. 5827-5837. PMLR, 2019. utl.hhttp://prrceeedl ngs ml www..peessvvv. /v90ss/v9/// s msek 9a. html]
Guillermo Valle-Perez, Chico Q. Camargo, and Ard Louis. Deep learning generalizes because the varameter-functing map is biased towards simple functions. In International Conference on Learn- ing Representations, 2019. URL http::tttt//ttccctt //tttpeee//ppeeeeiieee net. forum wtw.::te...ouumm...rrra.........
Lei Wu, Chao Ma, and Weinan E. How sgd selects the global minima over-parameterizee learning: A dynamical stability perspective. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Dasa-Bianchi, and R. Gameett (eds.), Advances in Neural Information Processing Systems 31, pp. 8279-8288. Curran Associates, Inc., 2018.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In Proceedings of the International Conference on Learning Representations ICLR, 2017.
Zhihui Zhu, Daniel Soudry, Yonina C. Eldar, and Michael B. Wakin. The global optimization geometry of shallow linear neural networks. CoRR, abs/ 10///805.0000 009304938, 2018. URL http://
arxiv. org/ abs.aaab//.111./// 04938
13


Reviews:
[{"review_id": "r1egjUohYr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper posits that similar input examples will have similar gradients, leading to a gradient \"coherence\" phenomenon. A simple argument then suggests that the loss should decrease much more rapidly when gradients cohere than when they do not. This hypothesis and analysis is supported with clever experiments that confirm some of the predictions of this theory. Furthermore, since, as the authors emphasize, their hypothesis is prescriptive, they are able to suggest a novel regularization technique and show that it is effective in a simple setting.\n\nI find the coherent gradient hypothesis to be simple and reasonable. Furthermore, the paper is written very clearly, and as far as I know the main idea is original (although since it is a rather simple phenomenon, it's possible something similar could have appeared elsewhere in the literature). Perhaps more importantly, the associated experiments are very cleverly designed and are very supportive of the hypothesis. For instance, Figure 1 provides compelling evidence for the coherent gradient hypothesis and in particular motivates the way phenomenon of early stopping arises a natural consequence. Overall, the paper is of very high quality, and I recommend its acceptance.\n\nOne criticism perhaps is whether these results are sufficiently significant. On the one hand, most of the experiments were done on small network and dataset combinations -- and the proposed regularization scheme as is will not scale to practical problems of interest. On the other hand, I really feel like I learned something interesting about gradient descent from reading this paper and absorbing the experimental results -- which is often not something I can say given the large array of reported experimental results in this field. It's clear that the authors themselves are aware that it's of interest to extend their results to more realistic settings, and regardless I think that this paper stands alone as is and should be accepted to ICLR.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "SkeccRZqFr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\nThe paper studies the link between alignment of the gradients computed on different examples, and generalization of deep neural networks. The paper tackles an important research question, is very clearly written, and proposes an insightful metric. In particular, through the lenses of the metric it is possible to understand better the learning dynamics on random labels. However, the submission seems to have limited novelty, based on which I am leaning towards rejecting the paper.\n\nDetailed comments\n\n1. The prior and concurrent work is not discussed sufficiently:\n\na) The novelty of the \"Coherent Gradients hypothesis\" is not clear to me. First, the empirical fact that some examples are easier to learn than others in training of deep networks was the key focus of [5]. \n\nHence, \"Coherent Graident Hypothesis\" should be mostly considered an explanation for why simple examples are/simple function are learned first. \"Coherent Gradient Hypothesis\" proposes that the key mechanism behind this phenomena is that simple examples/functions have co-aligned gradients and hence a larger \"effective\" learning rate. However, there are already quite convincing and closely related hypotheses. For example, the spectral bias interpretation of deep networks [2] and (2) suggests the same view actually. Just expressed in a different formalism, but can be also casted as having a higher effective learning rate for the strongest modes. Similarly, [3] proposes that SGD learns functions of increased complexity. A detailed comparison between these hypotheses is needed.\n\nb) \"Gradient coherence\" metric is very closely related to Stiffness studied in [1] (01.2019 on arXiv). [1] studies the cosine (or sign) between gradients coming from different examples, and reach quite similar conclusions. It is also worth noting that [6, 7] propose and study a very similar metric as well. While arXiv submissions is not consider prior work, these three preprints should be discussed in detail in the submission.\n\nc) It should be also remarked that \"Coherent Gradient hypothesis\" is to some extend folk knowledge. In particular, it is quite well known and also brought to the attention of the deep learning community that in linear regression strongest modes of the datasets as learned first when training using GD (see for instance [4]), which causally speaking stems directly from gradient coherence; these modes correspond to the largest eigenvalues of the (constant) Hessian. To make it more precise: consider that GD solving linear regression can be seen as having higher \"effective\" learning rates along the strongest modes in the dataset. \n\n2. Experiments on random labels and restricting gradient norms are interesting. However, [5] should be cited. They experimented with regularization impact on memorization, which due to the addition of noise, probably also supresses weak gradients. \n\n3. Experiments on MNIST do not feel adequate. While I do not doubt the validity of the experimental results, the paper should include results on another dataset; ideally from other domain than vision.\n\n4. Plots in Figure 4 are too small to read. I would recommend moving half of them to the Supplement?\n\n5. \"Understanding why solutions of the optimization problem on the training sample carry over to the population at large\" - Not sure what do you mean here. Could you please clarify?\n\n6. \"Furthermore, while SGD is critical for computational speed, from our experiments and others (Keskar et al., 2016; Wu et al., 2017; Zhang et al., 2017) it appears not to be necessary.\". Please note there is very little work on training with GD large models. Also, citing in this context Keskar is misleading. Wasn't the whole point of Keskar to show why large batch size training overfits? Finally, there are many papers on studying the role of learning rate and batch size in generalization (not computational speed). I think this sentence should be rewritten to clarify what is the experimental data that GD is \"sufficient\", and SGD is just needed for \"computational speed\".\n\nReferences\n\n[1] Stanislav Fort et al, Stiffness: A New Perspective on Generalization in Neural Networks, https://arxiv.org/abs/1901.09491\n[2] Rahaman et al, On the Spectral Bias of Neural Networks, https://arxiv.org/abs/1806.08734\n[3] Nakkiran et al, SGD on Neural Networks Learns Functions of Increasing Complexity, https://arxiv.org/abs/1905.11604\n[4] Goh, Why Momentum Really Works, https://distill.pub/2017/momentum/\n[5] Arpit et al, A Closer Look at Memorization in Deep Networks, https://arxiv.org/abs/1706.05394\n[6] He and Su, The Local Elasticity of Neural Networks, https://arxiv.org/abs/1910.06943\n[7] Sankararaman, The Impact of Neural Network Overparameterization on Gradient Confusion and Stochastic Gradient Descent, https://arxiv.org/abs/1904.06963", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "Byg52vRAYr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary\nThe surprising generalization properties of neural networks trained with stochastic gradient descent are still poorly understood. The present work suggests that they can be explained at least partly by the fact that patterns shared across many data points will lead to gradients pointing in similar directions, thus reinforcing each other. Artefacts specific to small numbers of data points however will not have this property and thus have a substantially smaller impact on the learning. Numerical experiments on MNIST with label-noise indeed show that even though the neural network is able to perfectly fit even the flipped labels, the \"pristine\" labels are fittet much earlier during training. The authors also experiment with explicitly clipping \"outlier gradients\" and show that the resulting algorithm drastically reduces overfitting, thus further supporting the coherent gradient hypothesis.\n\nDecision\nThe present work proposes a plausible, simple mechanism that might be contributing to the generalization of Neural Networks trained with gradient descent. Parts of the discussion stay informal as the authors themselves admit, but I appreciate that rather than providing mathematical decoration the authors focus on well-designed experiments that support their claims. Overall, the paper is of high quality and provides an interesting perspective on an important topic, which is why I think it should be accepted.\n\nQuestions for the authors\nThe coherent gradient hypothesis seems equally valid in the absence of stochasticity. However, the latter is often seen as an explanation of the generalization performance of SGD. My understanding is that you are also using minibatched gradient descent. Would you expect your experiments to still be valid when using deterministic gradient descent (full batch)? Did you study the effects of large batch sizes on the experiments?", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes an intuitive causal explanation for the generalization properties of GD methods. The reviewers appreciated the insights, with one reviewer claiming that there was significant overlap with existing work.

I ultimately decided to accept this paper as I believe intuitive explanations are critical to the propagation of ideas. That being said, there is a tendency in this community to erase past, especially theoretical, work, for that very reason that theoretical work is less popular.

Hence, I want to make it clear that the acceptance of this paper is based on the premise that the authors will incorporate all of reviewer 3's comments and give enough credit to all relevant work (namely, all the papers cited by the reviewer) with a proper discussion on the link between these.
Decision: Accept (Poster)