Weak and Strong Gradient Directions: Explaining Memorization, Generalization, and Hardness of Examples at Scale
Authors: Piotr Zielinski
Shankar Krishnan
Satrajit Chatterjee
Venue:  (2021)
Keywords: generalization
deep learning
hardness of examples

Abstract: Coherent Gradients (CGH) [Chatterjee, ICLR 20] is a recently proposed hypothesis to explain why over-parameterized neural networks trained with gradient descent generalize well even though they have sufficient capacity to memorize the training set. The key insight of CGH is that, since the overall gradient for a single step of SGD is the sum of the per-example gradients, it is strongest in directions that reduce the loss on multiple examples if such directions exist. In this paper, we validate CGH on ResNet, Inception, and VGG models on ImageNet. Since the techniques presented in the original paper do not scale beyond toy models and datasets, we propose new methods. By posing the problem of suppressing weak gradient directions as a problem of robust mean estimation, we develop a coordinate-based median of means approach. We present two versions of this algorithm, M3, which partitions a mini-batch into 3 groups and computes the median, and a more efficient version RM3, which reuses gradients from previous two time steps to compute the median. Since they suppress weak gradient directions without requiring per-example gradients, they can be used to train models at scale. Experimentally, we find that they indeed greatly reduce overfitting (and memorization) and thus provide the first convincing evidence that CGH holds at scale. We also propose a new test of CGH that does not depend on adding noise to training labels or on suppressing weak gradient directions. Using the intuition behind CGH, we posit that the examples learned early in the training process (i.e., "easy" examples) are precisely those that have more in common with other training examples. Therefore, as per CGH, the easy examples should generalize better amongst themselves than the hard examples amongst themselves. We validate this hypothesis with detailed experiments, and believe that it provides further orthogonal evidence for CGH.

Under review as a conference paper at ICLR 2021
WEAK AND STRONG GRADIENT DIRECTIONS: EXPLAINING MEMORIZATION, GENERALIZATION, AND HARDNESS OF EXAMPLES AT SCALE
Anonymous authors Paper under double-blind review
ABSTRACT
Coherent Gradients (CGH) is a recently proposed hypothesis to explain why wer-parameterized neural networks trained with gradient descent generalize well even though they have sufficient capacity to memorize the training set. The key insight CGH is that, since the overall gradient for single step of SGD is the sum of the per-example gradients, it is strongest in directions that reduce the loss on multiple examples if such directions exist. In this paper, we validate CGH ResNet, Inception, and VGG models ImageNet. Since the techniques presented in the original paper do not scale beyond toy models and datasets, we propose new methods. By posing the problem of suppressing weak gradient directions as problem of robust mean estimation, we develop coordinate- median of means approach. We present two versions this algorithm, M3, which partitions mini-bat baini-batch into 3 groups and computes the median, and a more efficient version RM3, which reuses gradients from previous two time steps to compute the median. Since they suppress weak gradient directions without requiring per- example gradients, they can be used to train models at scale. Experimentally, we find that they indeed greatly reduce overfitting (and memorization) and thus provide the first convincing evidence that CGH holds at scale. We also propose new test of CGH that does not depend on adding noise training labels on suppressing weak gradient directions. Using the intuition behind CGH, we posit that the examples learned early in the training process (i.e., "easy" examples) are precisely those that have more in common with other training examples. Therefore, as per CGH, the easy examples should generalize better amongst themselves than the hard examples amongst themselves. We validate this hypothesis with detailed experiments, and believe that provides further orthogonal evidence for CGH.
INTRODUCTION
Generalization in over- vor-parameterized neural networks trained using Stochastic Gradient Descent (SGD) is not well understood. Such networks typically have sufficient capacity memorize their training set (Zhang et af.] 2017) which naturally leads to the question: Among all the maps that are consistent with the training set, why does SGD learn one that generalizes well to the test set?
This question has spawned lot of research in the past few years (Arora et al.
2018
Arpit et al. 2017)
Neyshabur et al. 2018 Sankaaaakaa et al. 2019 Rahaman et al. 2219 Zhang el al. 2017). There have been many attempts to extend classical algorithm-indeee independent techniques for reasoning about generalization (e.g.. VC-dimension) to incorporate the "implicit bias" of SGD to get tighter bounds (by limiting the size of the hypothesis space to that reachable through SGD). Although this line of work is too large to review here, the recent paper of Nagarajan & Kolter (019) provides a nice overview. However, they also point out some fundamental problems with this approach (particularly, poor asymptotics), and come to the conclusion that the underlying proof technique itself (uniform convergence) may be inadequate. They argue instead for looking at algorithmic stability (Bousquet & Elisseeff 2002). While there has been work analysing the algorithmic stability of SGD (Hardt et al. 2016 Kuzborskij & Lampert 2018), it does not take into account the training data. Since SGD can memorize training data with random labels, and yet generalize real data (i.e., its generalization behavior is data-dependent (Arpit)
Bartlett al. 2017 Belkin et al. 2019 Fort al., 2020 Kawaguchi et al.
2017

---

Under review as a conference paper at ICLR 2021
al. 2017) ), any such analysis must lead to vacuous bounds in practical settings (Zhang et al. 2017). Thus, in order for an algorithmic stability based argument to work, what is needed is an approach that takes into account both the algorithmic details of SGD well the training data.
Recently, a new approach, for understanding generalization along these lines has been proposed in Chatterrjee (220)) Called the Coherent Gradients Hypothesis (CGH), the key observation is that descent directions that are common to multiple examples (i.e., similar) add up in the overall gradient (i.e., reinforce each other) whereas directions that are idiosyncratic to particular examples fail to add up. Thus, the biggest changes to the network parameters are those that benefit multiple examples. In other words, certain directions in the tangent space of the loss function are "strong" gradient directions supported by multiple examples whereas other directions are "weak" directions supported by only a few examples. Intuitively-and CGH only a qualitative theory at this point-strong directions are (al (algorithmically) stable (in the sense of [Bousquet & Hlisseeff (2002). i.e., altered marginally by the removal of a single example) whereas weak directions are (algorithiically unstable (could disappear entirely if the example supporting it is removed). Therefore, change to the parameters along a strong direction should generalize better than one along a weak direction. Since the overall gradient is the mean of per-example gradients, if strong directions exist, the overall gradient has large components along it, and thus the parameter updates are biased towards algorithmic stability.
Since CGH is causal explanation for generalization, Chatterjee (2020) tested the theory by perform- ing two causal interventions. Although they found good agreement between the qualitative predictions of the theory and experiments, important limitation of their work is that their experiments were on shallow (1-3 hidden layers) fully connected networks trained on MNIST using SGD with a fixed learning rate. In this work, test CGH on large convolutional networks such as ResNet, Inception and VGG on ImageNet. While one of the tests of Chatterjee (2020) (reducing similarity) scales to this setting, the more compelling test (suppressing weak gradients by winsorization) does not. We propose new class of scalable techniques for suppressing weak gradients, and also propose an entirely new test of CGH which is not based on causal intervention but on analyzing why some examples are learned earlier in training than others.
PRELIMINARY: REDUCING SIMILARITY ON IMAGENET
One test of CGH proposed in Chatterjee (200)) is to study how dataset similarity impacts training. Since directly studying similarity is difficult because which examples are considered similar may change during training (in CGH examples are similar if their gradients are similar), Chatterjee (2020) proposed adding label noise to a dataset based on the intuition that no matter what the notion of similarity, adding label noise is likely to decrease it. Therefore, if CGH is true, we should expect that:
As the label noise increases, the rate at which examples are learned decreases,
Examples whose labels have not been corrupted (pristine examples) should be learned faster than the rest (corrupt examples), and,
With increasing noise, since there are fewer pristine examples, the rate at which they are learned should decrease.
As preliminary experiment, we ran this test on ImageNet and the results for ResNet- 18 are shown in
Figure [ The results for Inception-V3. V3 and VGG-13 are very similar (please see Appendix AA). We note the good agreement with the predictions from CGH thus providing initial evidence that CGH holds at scale.
ABLATING SGD TO TEST THE COHERENT GRADIENT HYPOTHESIS: SCALABLE TECHNIQUES TO SUPPRESS WEAK GRADIENT DIRECTIONS
Since weak directions are supported by few examples, CGH holds that overfitting and memorization in SGD is caused by descending down weak directions. The original CGH paper proposed to test CGH by modifying SGD to suppressing weak directions in order to verify that it significantly reduces overfitting (Chatterjee) 2020), i.c., improves generalization through greater algorithmic stability (Bousquet& & Elisseeff 2002
2

---

Under review as a conference paper at ICLR 2021
380
25 rass baai
53% mose freind
25%
100%) Dian
56% role
L205 Irant
23
(a) Accuracy on train and test data
(b) Training loss
319
wontented
22% rolae
min
75% betiine
19%
100% se Inomant
opoc
4pach
(c) Acc. on pristine and corrupt split training data (d) Loss on pristine and corrupt split of training data
Figure 1: Training curves of ResNet-18 18 without augmentation or weight decay on ImageNet dataset with various levels noise training labels. We randomize 0%, 25%, 50%, 75%, and 100% of the training labels to get variants of ImageNet. The training examples whose labels are unaffected by randomization are called pristine and the rest are corrupt. We keep fixed sample of 50k examples from the pristine and corrupt sets to measure there are fewer than 50k pristine). Figures (a) shows the training and test accuracy with various levels of noise, while (b) shows the corresponding training loss. Figures (c) and (d) show the accuracy and loss plots on the pristine and corrupt samples. The plots confirm the predictions from CGH in Section (We train with a mini-bate batch size of 256 and momentum 0.9. The jumps 30 and 60 epochs are due to the usual lowering of the learning rate by 1/10 from an initial value of 0.1.)
accuracy and loss (except for 100% noise where
3.1 REVIEW OF THE WINSORIZATION TECHNIQUE
The test modified SGD by using the (coordinate-wise winsorized mean of the per-example gradients in a mini-batch (instead of the usual mean) to update the weights in each step. Everything else, including learning rate was kept the same. The winsorized mean limits the influence of outliers by clipping them to a specified percentile of the data (called the winsorization level). As expected from CGH, they found that as the winsorization level increased, the rate of overfitting decreased.
We replicated this study with a ResNet-32 on CIFAR-10 10 and confirmed the results of the original study on this new dataset and architecture (please see Appendix B). We note that since the original study was only on MNIST which has low generalization gap, the effect of suppressing weak directions only manifested with label noise. On CIFAR- 10 even the real label case (i.e., 0% noise) has significant overfitting which is reduced by winsorization. This provides stronger evidence in support of CGH.
However, a big challenge with winsorization is the need to compute and store per-example gradients which makes training much slower. For example, in our CIFAR- 10 experiment we had to reduce the mini-batch size to 32 make training feasible. This is exacerbated with larger models and more complex datasets such ImageNet, and new techniques are needed to scale up the test.
3.2 TECHNIQUES BASED ON MEDIAN OF MEANS
We start by observing that the problem of suppressing weak gradient directions can be posed as robust mean estimation problem from the robust statistics literature (Huber 1981). Although winsorization is one way of obtaining robust mean estimates, there are others. In particular, the median of means algorithm (Minsker 2013) is an optimal estimation technique in the sense that
3

---

Under review as a conference paper at ICLR 2021
(a) RM3 v/s SGD (0% noise)
(b) RM3 v/s SGD (50% noise)
(c) RM3 v/s SGD (100% noisc)
(d) RM3 v/s RA3 (0% noise)
(e) RM3 v/s RA3 (50% noise)
(i) RM3 v/s RA3 (100% noise)
RM3 v/s M3 (0% noise)
(h) RM3 v/s M3 (50% noise)
(i) RM3 v/s M3 (100% noise)
Figure 2: First row: Using the rolling median of 3 mini-batch gradients (RM3) to train a ResNet- 18 on ImageNet leads to a smaller generalization gap than using SGD. Since this reduction in overfitting is obtained by suppressing weak gradient directions, this provides strong evidence for CGH in this setting. Second row: The use of median in RM3 is critical; using average instead (RA3) does not suppress (and resembles SGD). Last row: A comparison with M3, another method for suppressing weak gradient directions based on splitting mini-batch into groups and computing the median. We do not show error bars since the curves are top of each other.
deviation from the true mean is bounded above by O / with high probability (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 groups, computing the sample mean of each group, and then returning the geometric median of these & means. The geometric median of & vectors I1, T2. .. Rd is the vector y" such that y* arg min Σ y - 24 Il2- When high dimensions the al algorithm compute the geometric median (Weiszfeld, 1937) is iterative and is expensive to integrate in a traditional training loop. A simpler technique is to apply the median of means algorithm to each coordinate that gives dimension dependent bound the performance of the estimator.
1, the geometric median is just the ordinary median of scalars. However, in
The M3 Technique. The most obvious way to apply this idea to SGD 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-ve wise median. The median is then used update the weights of the network
Even though the algorithm is straightforward, its most efficient implementation (i.c., where the groups are large and processed in parallel) on modern hardware accelerators requires low-level changes to the stack to allow for median based aggregation instead of the mean. Therefore, in this work, we simply compute the mean gradient of each group as separate micro-batch and only update the network weights with the median every A micro-batches, i.e., we process the groups serially.
'iine we are simply replacing the mini-batch gradient with more robust alternative, this technique may be used to study optimizers other than vanilla SGD (such as SGD with momentum, ADAM, etc.). A systematic exploration of that outside the scope of this study.
4

---

Under review as a conference paper at ICLR 2021
(a) RM3 v/s SGD (50% noise)
(b) RM3 v/s RA3 (50% noise)
(c) RM3 v/s M3 (50% noise)
Figure 3: The suppression of weak gradients by RM3 greatly inhibits learning of corrupt examples as compared to pristine. This shows that weak gradient directions are responsible for memorization and provides compelling evidence for CGH. We note again that median is what is critical, and not the rolling aspect since RA3 (Figure (b)) behaves like SGD (Figure (a)), but M3 (Figure (c)) like RM3. We do not show error bars since the curves are on top of each other.
In the serial implementation, k 3 is sweet spot. We have remember only 2 previous micro- batches, and since median [#1, z2, za) = E; Di min; I; - max; 24 (where E {1, 2, 3)), we can compute the median with simple operations. We call this median-of-3 micro-batches (M3).
Example (Effectiveness of M3). Fix d and consider a set of m < training examples. At some point in training, let 9: E d (1 S i S m) be their gradients. Suppose further that each gradient 9; has an idiosyneratic component u, and a common component c, i.e., 9: = + c with uy My = 0 (for j F i) and u, O. Since M3 involves coordinate operations, let assume that working in a basis where the non-zero coordinates of uy do not overlap with each other or with c.
Now, consider mini-batch of size 3b S m constructed by picking 3b examples (i.c., their gradients) uniformly at random without replacement. The expected value of this update if we take an SGD step (i.e., simply take the mean of the mini-batch), JSGD + m expected value of the update with M3 is 9M3 = since any non-zero coordinate of any u, cannot be the median value for that coordinate across the 3 groups since can appear at most once.
1 E, Ug. On the other hand, the
In this extreme case, we see that M3 suppresses the weak gradient directions (the u.) while preserving the strong gradient direction c.
The RM3 Technique. Now, rather than update the weights every i mhicro-batches, we do in M3, we can update the weights every micro-bated using the median from that micro-batch and the previous two. In this rolling setup, there is longer difference between mini-batche and micro-batches, i.e. this essentially the same as computing the median over the current mini maich gradient and the mini-batch gradients from the previous 2 steps. We call this rolling median of 3 mini-batches (RM3).
Two remarks concerning RM3 are in order. First, RM3 may be seen as an approximation to M3 chosen for implementation efficiency. The assumption is that the loss function does not change very much in gradient step, i.e., is locally stationary. Second, since RM3 uses recent gradient history, one may be tempted to think of RM3 as form of momentum, but that would be wrong. We can understand this better by replacing the median operation RM3 with the mean. We call this RA3 for rolling average of 3 mini-batches. As we shall see, it is the median v/s mean that makes significant difference in suppressing weak gradient directions, not the rolling v/s non-rolling. Schematically, in their ability suppress weak directions, we find that
SGD RA3 < RM3 M3.
3.3 EXPERIMENTAL RESULTS
Suppressing Weak Directions. Our setup is similar to that of Figure | architecture and train on ImageNet with 0%, 50%, and 100% label noise with the same learning rate schedule, and no augmentation weight decay. Unless otherwise specified, we use mini-batch size of 256 and no momentum.
We use the ResNet- 18
Figure 2 (a-c) shows the training and test accuracies of RM3 and SGD for the 3 noise levels. In all cases (including 0% noise, i.e, the real labels), we find that the suppression of weak gradients in RM3 leads to lower generalization gap than SGD. The impact of suppressing weak gradients is even more clear when we look at the relative training accuracies pristine and corrupt examples in the 50% label noise case. This is shown in Figure (a). We that unlike SGD which achieves high training
5

---

Under review as a conference paper at ICLR 2021
(a) Accuracy
(b) Loss
Figure 4: Using the original ImageNet training dataset, we create two datasets easy and hard. These are subsets of the original dataset and have training set (e-train and ht-rriin) and test set (e-fest and h-tesf). We train on both with a ResNet-18 architecture. Figure (a) shows the accuracy curves full, easy and hard training sets evaluated the original, e-test and h-test test sets. Figure (b) shows the corresponding training and test loss curves. The generalization of casy examples to other easy examples is better than that of hard examples other hard examples, in accordance with CGH, and provides additional confirmation (Section
DIFFICULTY
RM3 ACCURACY
COUNT
19%1
328400
1
97.82%
100599
2
96.73%
72814
3
95.69%
63783
4
94.46%
60389
5
92.85%
62617
6
90.56%
71495
7
86.61% %
99056
8
61.01%.
422014
(a) Top-1 Training Accuracy of RM3 and Difficulty
(b) Decision Boundary and Hardness.
Figure 5: (a) Training accuracy of RM3 on examples of varying difficulty. The suppression of weak gradients by RM3 disproportionately impacts the learning of more difficult examples which as expected from CGH (Section 4.3) (b) If SGD enumerates hypotheses of increasing complexity then the examples learned early (i.e., easy examples) should be the ones far away from the decision boundary since they can be separated by simpler hypotheses. However, the hard examples then, should generalize well the easy examples, but that is not what we find (Section
accuracy both pristine and corrupt examples, RM3 achieves good accuracy only the pristine examples and does not learn the corrupt examples. Since suppressing weak gradient directions leads significant reduction in overfitting (and memorization), this confirms the prediction from CGH that weak gradient directions are responsible for overfitting and memorization, and increases our confidence in the theory.
Ablation of RM3. To ensure that this effect is due to suppressing weak gradient directions, and not due to the rolling nature of RM3, we compared RM3 with RA3 (Figures (d-f) 3nd and with M3 (Figures (g-i) and 3 (c) On the one hand, we see that there is a big difference between RM3 and RA3 and that the behavior RA3 almost identically to SGD, On the other, we find that M3 shows an even smaller generalization gap than RM3. (See schematic equation (I).
Remark: Algorithmic stability may come with optimization instability! One unintended effect of using median to eliminate weak directions (and increase algorithmic stability) is that strong directions get amplified (c.f. median (0, 0, 1) < average(0, 0, 1) with median 1) average(O, 1, 1)). This may lead to larger steps in the strong directions which could increase loss (optimization instability). We see this for MB with 0% label noise (Figure 2 (g)) where directions are expected to be stronger than in the 50% and 100% cases where this does not happen.
Note that mini-batch size for RM3 is important. The larger the mini-batch, the more it behaves like SGD (as may also be by considering the extreme case of full-batch training). Finally, RM3 increases the run-time of SGD by less than 1% whereas M3 adds about 30% overhead.
We ran M3 with a batch size of 264 (i.c., micro-batch size of 88) instead of 256 since use 8 GPUs and 264 is closest multiple of 8.

---

Under review as a conference paper at ICLR 2021
4 EASY AND HARD EXAMPLES
In this section, we study easy and hard examples through the lens of CGH. This is interesting for two reasons. First, we believe that this perspective leads to a better understanding of what determines the hardness of examples. Second, easy and hard examples provide a fundamentally different test of CGH than the label noise techniques used so far to test CGH since they do not force memorization.
4.1 BACKGROUND AND THE CGH PERSPECTIVE
Arpit et al. (017)) conducted a detailed study of memorization in shallow fully connected networks and small AeexStt-ttyle convolutional networks on MNIST and CIFAR-10. One of their main findings is that for real data sets, starting from different random initializations, many examples are consistently classified correctly or incorrectly after one epoch of training which is in contrast to what happens with noisy data. They call these easy or 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."
We believe that CGH provides an explanation of this phenomenon. But rather than say easy examples are explained by "simple" patterns (which begs the question of what makes a pattern simple), CGH would posit that easy examples are those that have a lot common with other examples where commonality is measured by the alignment of the gradients of the examples. With this postulate it is easy to see why an easy example is learned sooner reliably: most gradient steps benefit it.
Note that this is a more nuanced phenomenon than claimed in Arpit et al. (2017) The dynamics of training (including initialization) can determine the difficulty of examples. ls. In particular, it may explain the results adversarial initialization (Liao et al. 2018 Liu al., 2019) (where examples that are easy to learn with random initialization become significantly harder) and our own experience with anti-adversarial initialization (Section ? since in both these cases the dataset remains the same (and thus the patterns remain the same).
4.2 TEST 1: EASY EXAMPLES SHOULD GENERALIZE BETTER THAN HARD EXAMPLES
If our hypothesis is true, the easy examples as group have more in common with each other than the hard examples. Therefore, we would expect the gradients for the easy examples be stronger than those for hard examples, and thus be more algorithmically stable (Bousquet & Elisseefi] 2002). In other words, they would be less impacted by the presence or absence of a single example. Therefore, we should expect that the easy examples should generalize better than hard examples.
To test this prediction, first we trained R8sNet-18 on ImageNet to 50% training accuracy using the normal training protocol. As per the discussion above, call the examples that have been learned easy and the rest hard. Next, from the easy examples, we pick 500K cxamples and 100K examples at random (without replacement) to create training set (e-train) and test set (e-test). We train ResNet- 18 model from scratch (using the normal training protocol) on the e-train data and evaluate it on the e-test data to measure the generalization gap for the easy examples. Finally, we then repeat the process with the hard examples to get the generalization gap for the hard examples.
The results are shown in Figure 4 First, verify that even in this setup of separate training, the easy examples (e-train) is learned faster than the hard examples (h-train). The slope of the corresponding losses carly in training suggest that the gradients of the easy examples are more coherent than those of the hard examples (as per the argument in (Chatterjec) [0200] $2.2)). Finally, note that the measured generalization gap for easy is significantly smaller than that for hard, in accordance with the prediction above.
4.3 TEST SUPPRESSING WEAK DIRECTIONS SHOULD IMPAIR LEARNING HARD EXAMPLES MORE
Based on the discussion above, we expect that the learning of hard examples is more reliant on weak gradient directions than the learning of easy examples. Therefore, if we technique to suppresses weak gradient directions during training with SGD, then we should expect that the training accuracy on hard examples should be relatively worse than its training accuracy on easy examples.
7

---

Since the performance of the model learned from hard examples on easy test examples is much lower than that of easy-on-easy, one may be justified in saying that hard examples do not generalize well to easy examples. In other words, the examples learned late by SGD (i.e., the hard examples) by themselves are insufficient to define the decision boundary to the extent that the early examples are. Under review as a conference paper at ICLR 2021
To test this, we extended the notion of easy and hard to (slightly more) continuous notion of difficulty. To each example in the ImageNet training set, we associate a difficulty as follows. We run the easy/hard classification procedure (from Section 4.2) times with different initializations. Since there is some variation from run to run in whether particular example is classified as easy or hard, for each example, we count how many times it is classified as hard. We call this its difficulty. Thus, difficulty of 8 means that in all 8 cases it was classified hard ("super hard"), whereas 0 means that in all 8 cases classified easy ("super easy").
We then train a model for 90 epochs using RM3 on the ImageNet training set (as described in Section B. and analyze how many examples at each difficulty level are correctly learned. Recall that all examples are correctly learned by SGD after 90 epochs. The results are shown in Figure As expected, the suppression of weak gradients makes harder to learn the more difficult examples. For example, the super hard examples have a top-1 training accuracy of only 61% % in comparison to 99% for the super easy ones.
4.4 DOES SGD EXPLORE FUNCTIONS OF INCREASING COMPLEXITY? A POSSIBLE TEST.
One intuitive explanation of generalization is that SGD somehow explores candidate hypotheses of increasing "complexity" during training, thus finding the simplest hypothesis that explains the data. While there is some evidence backing this view (Arpit al. 2017; Nakkiran al. 2019 Rahaman itt al. 2019), and this is not incompatible with CGH, we believe an aspect of our experiment suggests that this view not entirely satisfactory.
In one interpretation of this view, as Figure (bb) illustrates, one might think of the examples far away from the decision boundary as easy (since they can be separated by simpler hypotheses explored early on) and ones closer to the decision boundary as hard (since they need more complex hypotheses to be separated). One imagines that SGD in the course of training considers increasingly complex functions starting with perhaps linear classifiers (which fit many easy examples) and then refining it to increasingly complicated decision boundaries (to fit the remaining hard examples). From this, one might expect that the decision boundary learned from the easy examples, generalizes poorly to the hard examples, but that learned from the hard examples generalizes well to the easy examples.
We measure these quantities in the experiment of Section 4.2, and find them to be shown below.
model trained on
model evaluated on
accuracy
easy (e-train)
easy (e-test)
85%
shown as a baseline for good generalization
easy (e-train)
hard (h-test)
17%
low (as expected)
hard (h-train)
easy (e-test)
44%
low (unexpected)
hard (h-train)
hard (h-test)
21%
shown for completeness
This puts into question least one interpretation of the viewpoint that SGD explores functions of increasing complexity during training.
5 CONCLUSION
Coherent Gradients provides an approach to understanding the data- data-dependent generalization ob- served in neural networks trained with SGD. In this paper, we have presented new evidence for CGH both through reproducing and scaling up previous work, and through new methods and experiments.
If CGH is true, our experiments with naturally occurring easy and hard examples suggest a subtle yet important shift in perspective: Generalization happens not because "simple" patterns are prioritized by SGD, but because common patterns are found first. (Of course, since common patterns are usually also simple, prevailing intuitions are not incorrect.)
For future work, it would be interesting to test CGH on other types of networks such as transformers as well as develop practical optimizers and regularizers based on techniques such as M3 and RM3.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
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 Machine Learning, ICML 2018, Stockholmsmmässan, Stockholm, Sweden, July 10-15 2018, volume 80 of Proceedings of Machine Learning Research, pp. 254 263. PMLR, 2018. URL htt:::tttp::ccee/eeeeee/
m press http:///////raaaa..a.a hhtml
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 at memorization in deep networks. In Proceedings of the 34th Inter- national Conference on Machine Learning, ICMI, 20/7, Sydney, NSW, Australia, 6-11 August 2017, pp. 233-242, 2017. URL HtRt: htttt::pppppceee///////o ngs m htt.gg.........../.....pt www.ppesssvvi. arpit tt1 html
Peter I. Bartlett, Dylan Foster, and Matus J Telgarsky. Spectrally-norralizeed margin bounds for neural networks. In I. Guyon, U. V. Luxburg, S. 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.
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, (16(32):15843 158499115444-44444 2019. ISSN 0027-8424, doi: 10.1073/pnas. 1903070116 URL
https: www. pnas. org. wwtpaa/.o.g//ooeeetnttieeooe wtt.://ttttttttttccccoooooo //6/ 32////2/110 15849 911899
Olivier Bousquet and André Elisseeff.
Stability and generalization. Mach. Learn. Res.,
499-526, March 2002. ISSN 1532-4435, doi: 10.1 10.116//13243327722007777 URL https
Satrajit Chatterjee. Coherent gradients: An approach to understanding generalization in gradient descent-basee optimization. Proceedings of the International Conference on Learning Repre- sentations ICLR, 2020. URL
Stanislav Fort, Pawel Krzysztof Nowak, Stanislaw Jastrzebski, and Srini Narayanan. Stiffness: A new perspective on generalization in neural networks. CoRR, (ooouummid=zyyFF0Err http::/arxiv..o 0ttp:////ab/11100999999999
2020. URL
Moritz Hardt, Benjamin Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In Proceedings of the 33rd International Conference International Conference on Machine Learning Volume 48, ICML'16, pp. 1225-1234. JMLR.org, 2016. URL http://d]. acm. org/ cetttiiaiiooo inttaiion.. wwo.ocff.... cf..:fm??... (etr:dd=333539900 3045520
P.J. Huber. Robust statistics. Wiley New York, 1981.
K. Kawaguchi, L, Pack Kaelbling, and Y. Bengio. Generalization Deep Learning. ArXiv e-prints, December 2017. URL/https: //tp:///aiii..//.i httpg//ab//11..0555
Ilja Kuzborskij and Christoph Lampert. Data-dependent stability of stochastic gradient descent. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 2815-2822 2824, Stockholmsmässaan Stockholm Sweden, 10-15 Jul 2018. PMLR.
Qianli Liao, Brando Miranda, Andrzej Banburski, Jack Hidary, and Tomaso A. Poggio. A surprising linear relationship predicts test performance in deep networks. CoRR, abs/1807. bbs/1897.00659, 2018. URL
Shengchao Liu, Dimitris S. Papailiopoulos, and Dimitris Achlioptas. Bad global minima exist and SGD can reach them. CoRR, abs/1906. 026113, 2019. URL htll:t/tp///axx>> wwwpswiiiorrrroooooooooooo wwt./a////////eoo////..///aaaeee 02613
Stanislav Minsker. Geometric median and robust estimation in banach spaces. Bernoulli, 21, 08 2013. doi: 1..1150/14-BBJe.

---

Under review as a conference paper at ICLR 2021
Vaishnavh Nagarajan and J. Zico Kolter. Uniform convergence may be unable explain general- ization in deep learning. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' A'ché-BBus Buc, Emily B. Fox. and Roman Gamett (eds.). Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, 8-14 December 2019, Vancouver, BC, Canada, pp. 1161 1-11622, 2019.
Preetum Nakkiran, Gal Kaplun, Dimitris Kalimeris, Tristan Yang. Benjamin Edelman, Fred Zhang, and Boaz Barak. SGD on neural networks learns functions of increasing complexity. CoRR, abs/1905.1 1604, 2019.
abs 905. 11604
Behnam Neyshabur, Zhiyuan Li, Srinadh Bhojanapalli, Yann LeCun, and Nathan Srebro. Towards understanding the role of wverpaarametrizzaiionn in generalization of neural networks. CoRR, abs/1805. 2018. URL [tttp:////xxxx org/ abs /1055.1185.... 12076
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 on Machine Learning. volume 97 of Proceedings of Machine Learning Research, pp. 5301 5301-5310, Long Beach. California, USA, 09-15 Jun 2019. PMLR. URL ppr.ceee/prccceedeeeeee ings ml r. www.r.preaaee. wrw.srrssssee.... //sss//v9 press/v977 9 rahhmann 9a. html
Karthik Abinav Sankararaman, Soham De, Zheng Xu, W. Ronny Huang, and Tom Goldstein. The impact of neural network overparameterriztton gradient confusion and stochastic gradient descent. CoRR, abs/1904,06963, 2019. URL http:/
1904. 06963
Endre Weiszfeld. Sur le point pour lequel la somme des distances de n points donnés est minimum. Tohoku Mathematical Journal. First Series, 43:355-386, 1937.
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.
A IMAGENET TRAINING DETAILS AND RESULTS ON INCEPTION AND VGG
We used PyTorch v1.3.1 and the implementations of the 3 models (ResNet-18, V3,-13, Inception- V3) used for ImageNet training are from Torch Vision v0.4.2 The initial learning rate for models was 0.1. For ResNet- 18 we decreased by factor of 10 every 30 epochs (which is default behavior of the example ImageNet trainer in Py Torchh examples package) while for VGG-13 and Inception-V3 we used the cosine annealing schedule") The Inception model did not use auxiliary logits. All experiments presented in Section 2 were run with momentum of 0.9 and a mini-batch size of 256. No random augmentation of the inputs weight decay was used. To save compute we stopped VGG training early (when training accuracy reached 100%).
Figures 6 and 7 show the results of the label noise experiments on Inception-V VV3 and VGG-13 respectively. The results are essentially the same as that for ResNet-18 which has been presented in Section 2.
B WINSORIZATION ON CIFAR-10
We train ResNet-32 on CIFAR-10 10 using SGD with a batch size of 32. We use a normal learning rate schedule where the initial rate is 0.1 and is lowered by 1/10th first at 40K steps, and then every 20K steps thereafter. We train for a total of 100K steps (i.e., 64 epochs).
The amount of winsorization is controlled by a parameter 8. First, we compute individual gradients for each example in minibatch (this procedure memory intensive for a large network like ResNet-32, which is why use smaller batchsize than usual). We perform winsorization by manipulating the per-example gradients a coordinate-wise fashion. For the 7th component, we collect the
10

---

Under review as a conference paper at ICLR 2021
380
26 ra3s Iaai
25%
55% roee
Farm racie (icee
145
(a) Accuracy train/test data
(b) Training loss
389
140 2003000
wartented
25% mote
55% roter
130% comm
75% relee coberied
10Em 11-10 100% tormant
Lic
40od
10:1
(c) Accuracy on pristine/corrupt split of training data
(d) Loss on pristinefcorrupt split of training data
Figure 6: Training curves of Inception-V. V3 without augmentation or weight decay on ImageNet dataset with various levels of noise in training labels. We randomize 0%, 25%, 50%, 75%, and 100% of the training labels to get variants of ImageNet. The training examples whose labels are unaffected by randomization are called pristine and the rest are corrupt. We keep a fixed sample of 50k examples from the pristine and corrupt sets to measure accuracy and loss (except for 100% noise where there are fewer than 50k pristine). Figures (a) shows the training and test accuracy with various levels of noise, while (b) shows the corresponding training loss. Figures (c) and (d) show the accuracy and loss plots on the pristine and corrupt samples. The plots confirm the predictions from CG in Section 2.
per-example gradients to get 32 scalars. Instead of simply summing them to get the ith component of the overall gradient, we first reduce the impact of outliers by clipping each per-example scalar to be no less than the (s 1)-smallest and no larger than the (s + 1) J-largest of the 32 values, and then sum. Thus s = 0 corresponds to no clipping and thus regular SGD.
Figure shows the performance of winsorization. The top of the grid shows our results the original dataset with winsorization parameter = 0, 2, and 4. We can see that as s increases, the gap between train and test accuracy decreases. Also worth noting is that for small levels of winsorization, the model performance on test data does not change significantly. The bottom row in Figure & shows similar results when we add 100% label noise. At s O, we can see that the model completely memorizes the training data while generalizing very poorly. By increasing to 2 in order to suppress weak gradient directions, we find that the model completely fails learn the training set. We view this as strong validation for CGH.

---

Under review as a conference paper at ICLR 2021
194
rass lead
3ren) jrct
note frain
(a) Accuracy train/test data
(b) Training loss
25% soaelpraine
Dereneteeee 123% wis aurrel
(c) Accuracy on pristine/corrupt split of training data
(d) Loss on pristine/corrupt split of training data
Figure 7: Training curves of VGG-13 without augmentation or weight decay on ImageNet dataset with various levels of noise in training labels. We randomize 0%, 25%, 50%, 75%, and 100% of the training labels to get variants ImageNet. The training examples whose labels are unaffected by randomization are called pristine and the rest are corrupt. We keep fixed sample of 50k examples from the pristine and corrupt sets to measure our accuracy and loss (except for 100% noise where there are fewer than 50k pristine). Figures (a) shows the training and test accuracy with various levels of noise, while (b) shows the corresponding training loss. Figures (c) and (d) show the accuracy and loss plots the pristine and corrupt samples. The plots confirm the predictions from CG in Section
S=0
2
5-4
100
100
100
accuracy (0% neise)
train
test
25
100
100
100
accuracy 1100% noise)
25
epoch
epoch
epoch
Figure 8: Performance of winsorization the training of CIFAR-10 10 dataset on ResNet-32 architecture.
The number of extreme samples in the mini-batch (of size 32) that are clipped are shown on the top of each column of the grid. The rows represent training with 0% and 100% label noise respectively. As the number of samples clipped by winsorization increases (i.e., more weak directions are suppressed), we can see that the generalization gap decreases. With 100% label noise and clipping extreme samples, SGD does not memorize the training set.
12


Reviews:
[{"review_id": "skIHYzhYMGi", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "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 of paper:**  Builds on and tests the \"coherent gradients hypothesis\" (CGH), which proposes that SGD is able to generalize well because of 'coherence' (similar direction) of gradients. The methodology of CGH involved comparing gradient directions on individual examples, infeasible for large datasets, so this work proposes and compares 2 mean- and median- based methods for testing CGH at scale. It also investigates easy/hard examples and thereby proposes a test of coherence of gradients based on the number of times an example of a certain difficulty is correctly classified. \n\n\n**Pros/strong points:**\n - interesting experiments, solid relationships made to related work\n - locally clear explanations of techniques\n\n**Cons/weak points:**\n - global flow/organization need a lot of work\n - builds heavily on previous work and is not sufficiently standalone\n - the main unique contributions of this work (separate from just validating CGH) are not sufficiently investigated to my understanding / satisfaction (see specific comments in \"Quality\" below)\n\n**Summary of review + recommendation:** This has some nice experiments and I like to see papers building on and pushing further on previous insight (novelty is somewhat a weak point, but it is enough for me given the value of this kind of \"building\"). The presentation/organization needs a lot of work, and the main novelty proposed in this work (the methodologies that scale well) are missing an important baseline IMO. I also find some of the conclusions claimed (specifically sec.4.4) somewhat shaky. If these are addressed I am optimistic about increasing my score.\n\n\n**DETAILED REVIEW:**\n\n**Quality:**\n - The experiments are interesting and investigation of easy/hard examples is a nice addition\n - One of the main contributions of this work is methodology for computing similarity of gradients at scale (when it is infeasible to do so on a per-example basis as is possible e.g. for MNIST). A somewhat gaping hole in the testing of these methods then, to my mind, is to compare them to single-example computations: i.e.do experiments with RA3, RM3 and MA on minibatches of MNIST and CIFAR and make sure the conclusions are the same/agree with what is found via the single-example version.\n\n**Clarity:**\n - A lot of sentences, especially in the intro, read very \"conversationally\" (lots of parentheses, asides, and relatively long sentences). This isn't bad, exactly, but it can be unclear especially for non-native english speakers, and is hard to parse quickly. I recommend reading over the whole text and trying to make the sentences shorter/punchier/each making only one clear point. Similarly for paragraphs, each should have a clear purpose/thesis in order to provide good flow and structure\n - Overall flow of the main part of the paper is very unclear; an \"overview\" or something at the end of the introduction could help a lot. Also confusing that methods are reviewed / terms defined in the experimental sections; maybe worth splitting these (but maybe having an overview would make it clear enough), and CGH isn't reviewed until after half of the experiments.\n\n**Originality:**\n - The choices of experiments are logical for investigating CGH at scale, and the methods for doing so are novel to my knowledge\n - Relies heavily on previous ideas (CGH)\n\n**Significance:** \n - Interesting experimental results, pushing forward our understanding/intuition of deep net generalization behaviour, but current presentation limits their significance \n\n**Specific questions/recommendations:**\n\n - first sentence of abstract is a bit clunky, suggest rephrase as: The coherent grad hyp (CGH) was recently proposed to explain why....\n - Unclear flow in 2 sentences in abstract: In this paper ... Since ... | suggest rephrasing these sentences as \"Since the techni ... new methods in order to validate CGH on ...\" \n - suppressing weak gradient dirs: unclear link with generalization/memorization etc. or reason we would want to do this (can figure it out, but it's not clear in the abstract where it's important to be clear).\n - why is CGH causal? What were the interventions? They're referenced mid-paragraph without explanation.\n - seems like pristine examples should only be learned faster if the noise is sufficient to confuse the gradients (at low levels of noise, the noise can act as a regularizer and actually boost learning of mildly-noised samples)\n - winsorization experiments seem out of nowhere / don't flow or add insight (could cut most of this except for a line about the results in order to make space for the validation to single-example version suggested in the \"Quality\" section)\n - unclear what \"increasing noise\" means when introduced (needs 1-line explanation of how the label noise is generated).\n - Fig 5a) is not well explained/related to the text in the caption (doesn't mention what the count means, or that this is being proposed as a measure of coherence of gradients)\n - Fig 5b) how is this generated, is this just an illustration of what a decision boundary is or is this actual data? What data?\n - I get the intuition for the Remark on p6 but I find the explanation unclear (why do larger steps mean increased loss; I think an argument about variance might be more appropriate). I also had trouble parsing/don't understand the last sentence of the remark\n - background and CGH perspective should come before experiments on it\n - Why 50% acc for easy examples? Were other things tried? Arpit et. al used just one epoch.\n - What about the plots for generalization of h-train to e-test and e-train to h-test? I'd like to see these in appendix\n - Seems incorrect to conclude that \"hard examples do not generalize well to easy examples\" when the results show they generalize twice as well to easy examples (which are out of distribution) as to hard examples! These are still interesting results but the experiments would have to be more in depth (e.g. including visualizations, and small examples or something) to actually support this conclusion.\n - the paper overall reads like a sequel to CGH where you need to have read CGH to understand key plot points. Have someone who has not read CGH read it and point out places it does not stand well alone.\n\n**Nits:**\n - \"whereas directions that are idiosyncratic to particular examples fail to addup.\" wordy/unclear\n - \" descending down weak directions.\" -> descending in OR toward (descending down is redundant and therefore confusing)\n - Figures need larger legends and maybe bolder lines- easy examples, generalizes poorly -> remove comma", "extra_scores": {}, "extra_text": {}}, {"review_id": "lVKsJlRbDuk", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "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": "The paper gives algorithms to test the Coherent Gradients Hypothesis (CHG) for larger models and larger datasets. CGH is a recently proposed hypothesis to explain generalization of neural networks using algorithmic stability and other empirical observations for deep learning. It claims that there are strong gradient directions which are shared by many examples and those directions lead to better generalization where there is overfitting in weak gradient directions where only a few examples contribute. This paper extends the experiments to larger datasets like Imagenet and CIFAR and bigger models like ResNet, Inception, and VGG whereas the original paper looked at small fully connected networks for MNIST dataset. To test this hypothesis on larger datasets, they pose suppressing weak gradients as a robust mean estimation algorithm and propose two algorithms. This paper also gives another empirical test that can be used to confirm CGH.\n\n1) The new algorithm which used the median of means technique to suppress weak gradients is interesting but I do not think that it is a significant enough contribution. \n \n2) I find this paper’s perspective on easy and hard examples interesting that easy examples are those that have a lot in common with other examples and thus, are learned during the beginning of the training due to gradient alignment. They also give supporting experiments for this observation. \n\nI would recommend rejecting this paper. I believe that the contribution of this paper is incremental in comparison to the paper which introduced CGH. This paper extends those experiments to larger datasets and models but I do not think that it is adding any significant new insight for the community. \n\nDetailed Comments/Questions:\n\n1) Using the earlier technique of coordinate wise winsorization, what is the largest batch size possible for Imagenet and does using a larger batch size significantly change the conclusions of this paper?\n2) I am not entirely convinced by the arguments of section 4.4. This paper argues that learning only hard examples (which are learned later in the training period) does not generalize well to the easy examples and vice versa. Hence, if we think of hard examples as the ones close to the decision boundary, they should generalize well to the easy examples which is not true empirically. Hence, we can not fully think of SGD as learning functions of increasing complexity. I think more experiments are needed to fully understand this perhaps on smaller datasets to understand what is happening. Hard examples might not be sufficient to fully learn the training boundary but SGD still might be learning functions of increasing complexity. \n3) I did not completely follow the comment on adversarial initialization in section 4.1 of the paper.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "izgCF_V64LO", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "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": "The paper aims at providing experimental evidence to support the Coherent Gradients Hypothesis (CGH), that was published previously. The hypothesis suggests that the ability of large neural networks to generalise comes from the aligned gradients of the examples in the dataset. Once SGD follows common gradients, ignoring the rare directions, the model will generalise better. For the experimental evidence the authors present two algorithms for approximate smoothing insignificant gradient directions for large scale networks and datasets, as opposed to the original CGH paper, where experiments were performed for MNIST and one hidden layer network. The proposed techniques allow for large-scale experiments and show a decreased generalisation gap compared to vanilla SGD. The authors also propose to analyse “easy” (ones that are learned first) and “hard” (require lots of training) examples. The claim is that the easy examples are the ones having coherent gradients, while hard ones push the network to rare directions.\n\nThe paper is clearly written, but contains some informal claims and formulations (more details in minor comments), that makes it difficult to follow the idea. The main goal of the paper is formulated as finding scalable evidences for CGH to be true, and the central part is the algorithms and experiments using them. The authors also proposed an “orthogonal” set of experiments, as compared to the original CGH paper, based on comparing generalisation on easy and hard examples. The authors provide the code and detailed descriptions of all the experiments.\n\nThe idea of CGH was already published, while the further step from my point of view should be trying to find more rigorous formal justification of similar gradients and their connection to the generalisation, rather than providing additional experiments, that are still just an indication that CGH might be true. If the proposed algorithms are considered to be a practical contribution for better generalising training, then the results should be compared to related techniques (for example, batch normalisation). Also, I would be highly interested in comparing the original winsorization approach to get rid of the insignificant gradient directions to the median robustness approach used here. Are they equivalent in the effect? Also, for easiness of computation, the algorithm calculates medians coordinate-wise - I wonder if from formal perspective this leads to something completely different than what was intended (since the original theory is introduced for the whole vectors up to my understanding). The discussion on the benefits of median compared to average reads too vague. Finally, the discussion on the complexity of learned network (section 4.4) is extremely informal and confuses more than it provides insights. \n\nI would recommend the paper for rejection, because from my point of view it does not contain sufficient novel contributions for a conference publication.\n\nMinor comments:\n\n1 - sloppiness in SGD definition (as compared to mini batch GD): stochastic gradient descent is commonly used when the training is done without mini batches, i.e., updates are happening after each example seen\n\n2 - sloppiness in gradient update definition (sum (in abstract) or average (later)?)\n\n3 - algorithmic stability citation, Kuzborskij&Lampert - it is told they do not take training data into account, what does it mean? Their work is exactly about data dependent stability of SGD. I guess the problem is in wording - data dependency considers distributions, while dataset dependency considers properties of a particular dataset at hand. \n\n4 - The claim that “any generalisation analysis that does not take into account dataset has to be vacuous” is somehow too strong. There are indications for it, but it cannot be claimed certainly.\n\n5 - The gradients of examples are named to be a similarity measure between examples that does not change with training - but it does. Also, claim that label noise will always reduce any similarity measure between examples - what if only input part is taken into account for measuring similarity?\n\n6 - the first experiment claims that hardship in learning label noise affected examples supports CGH - I cannot really agree with that. The added noise will make the network learn worse, that does not provide any evidence for aligned gradients being the reason for good generalisation. Moreover, in further experiments, one can see that vanilla SGD constantly outperforms the proposed methods on pristine examples (figure 3a) - does it mean that removing insignificatant directions hurts performance in some sense?\n\n7 - figure1, c and d - are there any pristine examples when the level of noise is 100%?\n\n8 - the first sentence in paragraph3.1 is poorly formulated\n\n9 - it feels like the main point of the plots to all the experiments is to show the difference in final achieved accuracy/loss. If it is the case - why overload the reader with the full training development of the values? I would suggest to report it in more concise form.\n\n10 - figure2 and 4 is extremely hard to read, too small\n\n11 - easy and hard examples experiments: does the originally trained network, with vanilla SGD, generalise better on easy examples than on hard examples?", "extra_scores": {}, "extra_text": {}}, {"review_id": "YmK787NCNf", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "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": "### Pros\n\nI appreciate an experimental study to delve deeper into the dynamics of CGH. The RM3 algorithm is very interesting and scalable and can perhaps be adapted to be used more regularly for optimization in the presence of noise.\n\n### Cons\n\nIn short my main issue is as follows - The entire idea of the paper is to present empirical evidence to support CGH as the explaining factor behind generalization. However, if there are a lot of confounding variables in the experimental setup, in my opinion, it becomes very hard to draw reasonable conclusions from the experiments. There are also multiple other papers (which is too large to list here) that propose different explanations for generalization and mitigation techniques to improve generalization. So, I believe that if one were to posit one of the theories over the other theories it is important to show specific situations where the other explanations fail and this succeeds. I do not see any such experiments in this paper.\n\nIn addition, it is not a theoretical paper (which is absolutely alright in my opinion) but being an empirical paper its experiments need to be thorough and convincing enough so that some conclusion can be drawn out of it and I think it would be wrong to draw reasonable conclusions out of the experiments in this paper in its current form.\n\nPerhaps, most importantly, the paper seems to suggest that the only way to generalization, and which is supported  by CGH to a certain extent, is to not memorize label noise in noisy datasets. This seems to be at odds with the behaviour where neural networks can generalize even in the presence of label noise while memorizing it (*benign overfitting*). The authors do not discuss theoretical and practical works that discuss this phenomenon of benign overfitting or the importance of memorization for learning in neural networks.\n\n#### Detailed points \n\nIf the key idea is that it is CGH that is causing generalization and not something else, the paper must compare itself with other regularizers and training techniques that claim to improve generalization and either explain why CGH is not at odds with them or show experimental or theoretical scenarios where CGH succeeds and others fail. For something, which is as purely experimental and intuitive as CGH, I think the experiments need to be more through than what it is. The benefits of generalization could have easily been brought about by something else other than the robust mean estimation in RM3, which would completely negate the hypothesis.\n\nThe three points proposed in  Section 2 (which is a preliminary argument as admitted by the authors) are not something typical of CGH. While CGH could be a possible explanation, they are too generic to be very specific about CGH. It could easily be about learning progressively complex hypotheses.\n\n\nIn Fig 1c, the accuracy of  _pristine_ examples increases faster for datasets with more label noise, which agrees with  Point 1 in Section 2. However, I am not sure how the fact that _corrupt_ examples also see a similar trend i.e. noisy examples in datasets with more noise take longer to learn support this argument. As all noisy examples are uniformly randomly labelled, shouldn't they all see equally _randomly_ _oriented_ gradients and thus learn at the same rate ?\n\nSome experiments show _underfitting_, which might explain why it is showing better generalization in the presence of label noise. For example, experiments with 50% label noise in Fig 2, show a train accuracy of around 40% which is quite low. One possible explanation is that the hyper-parameters used here are preventing further optimization and thus memorization of the noisy labels (and the authors do state that they use the original hyper-parameters and do not tinker with them).  Thus, it cannot be said with certainity that the cause of generalization in those experiments is due to RM3 and not due to the particular choice of hyper-parameters.\n\nFurther, as I mentioned before, neural networks can exhibit generelization even when memorization is exhibited. \n\nI also find the experiments in Sec 4.4 to be very unsatisfactory.  One of the hypothesis that this section is based on is that - hard examples are the ones closer to the boundary. That would mean that harder examples are ones that are confusing and it can belong to either of the two classes. However, that is not necesasarily true. Hard examples can just be rare examples  not necessarily close to the boundary. This would also support both the stats in the table in 4.4. corresponding to a) h-train, e-test b) h-train, h-test without being at odds with \"SGD learns functions of increasing complexity\".\n\n\nThe authors have not prepared a rebuttal. ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviews are concerned about the novelty/incremental nature of the paper and partially also about the 
conclusions drawn from the experiments. The authors did not take the chance to write a response.
Decision: Reject