Making Coherence Out of Nothing At All: Measuring Evolution of Gradient Alignment
Authors: Satrajit Chatterjee
Piotr Zielinski
Venue:  (2021)
Keywords: generalization
deep learning

Abstract: We propose a new metric ($m$-coherence) to experimentally study the alignment of per-example gradients during training. Intuitively, given a sample of size $m$, $m$-coherence is the number of examples in the sample that benefit from a small step along the gradient of any one example on average. We show that compared to other commonly used metrics, $m$-coherence is more interpretable, cheaper to compute ($O(m)$ instead of $O(m^2)$) and mathematically cleaner. (We note that $m$-coherence is closely connected to gradient diversity, a quantity previously used in some theoretical bounds.) Using $m$-coherence, we study the evolution of alignment of per-example gradients in ResNet and EfficientNet models on ImageNet and several variants with label noise, particularly from the perspective of the recently proposed Coherent Gradients (CG) theory that provides a simple, unified explanation for memorization and generalization [Chatterjee, ICLR 20]. Although we have several interesting takeaways, our most surprising result concerns memorization. Naively, one might expect that when training with completely random labels, each example is fitted independently, and so $m$-coherence should be close to 1. However, this is not the case: $m$-coherence reaches moderately high values during training (though still much smaller than real labels), indicating that over-parameterized neural networks find common patterns even in scenarios where generalization is not possible. A detailed analysis of this phenomenon provides both a deeper confirmation of CG, but at the same point puts into sharp relief what is missing from the theory in order to provide a complete explanation of generalization in neural networks.

Under review as a conference paper at ICLR 2021
MAKING COHERENCE OUT OF NOTHING AT ALL: MEASURING EVOLUTION OF GRADIENT ALIGNMENT
Anonymous authors Paper under double-bling review
ABSTRACT
We propose a new metric (m-coherence) to experimentally study the alignment of per-example gradients during training. Intuitively, given a sample of size m, m-coherence is the number of examples in the sample that benefit from a small step along the gradient of any one example on average. We show that compared other commonly used metrics, m--oherence is more interpretable, cheaper to compute (0mm) instead of (m²)) and mathematically cleaner. (We note that m-coherence is closely connected to gradient diversity, a quantity previously used in some theoretical bounds.) Using m-coherence, we study the evolution of alignment of per-example gradients in ResNet and EfficientNet models on ImageNet and several variants with label noise, particularly from the perspective of the recently proposed Coherent Gradients (CG) theory that provides simple, unified explanation for memorization and generalization [Chatterjee, ICLR 20J. Although we have several interesting takeaways, most surprising result concerns memorization. Naïvely, one might expect that when training with completely random labels, each example is fitted independently, and so m-coherence should be close to 1. However, this is not the case: m--coherence reaches moderately high values during training (though still much smaller than real labels), indicating that weerpparameterized neural networks find common patterns even in scenarios where generalization is not possible. detailed analysis of this phenomenon provides both deeper confirmation of CG, but at the same point puts into sharp relief what is missing from the theory in order to provide a complete explanation of generalization neural networks.
INTRODUCTION
Generalization in neural networks trained with stochastic gradient descent (SGD) is not well- understood. For example, the generalization gap, i.e., the difference between training and test error depends critically on the dataset and we do not understand how. This is most clearly seen when fix all aspects of training (e.g., architecture, optimizer, learning schedule, etc.) and vary only the dataset. In typical experiment designed to test this, training leads a relatively small generalization gap. whereas training randomized data (c.g.. ImageNet with random labels) leads to much larger gap (Zhang et al. 2017 Arpit et al. 2017).
real data set (c.g., ImageNet)
The mystery is that in both cases (real labels and random) the training accuracy is close 100% which implies that the network and the learning algorithm have sufficient effective capacity (Arpil al. 2017) to memorize the training sets, i... to an arbitrary mapping from the imput images to labels. But, what then, is the mechanism that from among all the maps consistent with the training set, allows SGD to find one that generalizes well (when such a well-generalizing map exists)?
This question has motivated a lot of work (see e.g., Zhang et al. (2017): Arpit et al. (2017) Bartlett cet al. (2017); Kawaguchi et al. (0077): Neyshabur et al. (2018) Arora et al. (2018): Belkin et al. (2019); ; Rahaman al. (201)) but satisfactory answer has emerged. As Nagarajan & Kolter (019 point out, traditional approaches based on uniform convergence may not suffice, and new ideas needed. A promising line of attack is via algorithmic stability Bousquet & Elisseeff (2002). but traditional stability analysis of SGD (c.g., Hardt et al. (2016); Kuzborskij & Lampert] (2018)) does not account for the dataset, and without that, cannot hope get more than vacuous bound.

---

Under review as a conference paper at ICLR 2021
Recently, new approach called Coherent Gradients (CG) has been proposed that takes into account the training dataset in reasoning about stability (Chatterjee| 2020; Zielimski et (000). By analogy to Random Forests which also show dataset dependent generalization, CG posits that neural networks try to extract commonality from the dataset during the training process.
The key insight 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. Intuitively, at one extreme, if all the per-example gradients are aligned we get perfect stability (since dropping an example does not affect the overall gradient) and thus perfect generalization.
At the other extreme, if all the per-example gradients (since dropping an example eliminates any descent along its gradient), and thus pure memorization. This can be seen, for example, when trying to fit linear model y x to the following dataset under the usual mean squared error loss:
pairwise orthogonal, we get stability
Vi
1,
0,
0,
0.
1,
0,
0
-1
0,
0,
3
0,
0,
0,
1)
1
Thus CG provides a simple, unified explanation for both memorization and generalization. However, the same time, CG leads to some basic empirical questions:
1. What does the alignment of per-example gradients, i.e., coherence look like in practice?
As was noted in Chatterjee (2020), we expect a real dataset to have more coherence than a dataset with random labels, but how big is this difference quantitatively? Is coherence in the random label case like that in the pairwise orthogonal case described above? How does vary with layer architecture?
2. Is the coherence constant throughout training, or does it vary? If so, how?
The key insight of CG (as described above) a point-in-tie -n-tte observation, but in order get a full picture of generalization we need to analyse the entire training trajectory. For example, one might imagine that as more and more training examples are fitted, coherence decreases, but is it possible for it to increase in the course of training?
metric called m-coherence experimentally study gradient coher- ence. The metric admits a very natural intuitive interpretation that allows us to gain insight into the questions above. While we confirm our intuitions in many cases, we also find some surprises. These observations help us formulate more precisely what is missing from the CG explanation for generalization, and thus point the way future work in this direction.
In this paper, we propose
PRIOR WORK ON METRICS FOR EXPERIMENTALLY MEASURING COHERENCE
Pairwise Dot Product. An obvious starting point to quantify the alignment or coherence of a set of gradients is their average pairwise dot product. Since this has a nice connection to the loss function, we start by reviewing the connection, and also set up notation in the process.
Formally, let Dzz) denote the distributior of examples from a finite set Z, and assume without loss of generality that support(() for an example z ~ for a parameter vector w E RRd, For the learning problem, we are interested in minimizing the expected loss f(w) Ez<D[L_ (w)) Let 9= == [Ve (w) denote the gradient of the loss on example 2, and = [V][(w) denote the overall gradient. From linearity, we have,
Z. For network with d trainable parameters, let (w) be the loss
g
E z>D
gg
We would like to quantify gradient coherence for both populations and samples. Therefore, DD can either be a population distribution (typically unknown) or sample (i.c., empirical) distribution. We assume finiteness for simplicity since it does affect generality for practical applications.
2

---

Under review as a conference paper at ICLR 2021
Now, suppose take small descent step h -119 (where 77 0 is the learning rate). From the Taylor expansion of around w, we have,
f(w + h) f(w) = g -1
E 2DD
9=
E IND
9= = =
E
0== g2'
(1)
2 S.DDZI'D
where the last equality can be checked with direct computation. Thus, the following are approxi- mately equivalent:
reduction in loss (due to small step) divided by the learning rate,
squared e norm of the expected gradient, and,
expected pairwise dot product (where the expectation is over all pairs).
Example. (Chatterjee 2020) Consider a sample with m examples 2; where S i S m. Let gi be the gradient of z; and further that ||9:|| = |ul|| for some If all the yi the same, then 9 However, if they are pairwise orthogonal, i.e., fi = 0 for i & j. then g 1
| 2
As this illustrates, the average expected dot product can vary significantly depending the coherence. However, as metric for coherence it is rather fragile. For example, just re-scaling the loss can drastically alter the value of the metrie. Therefore, can only be used reason about coherence in very limited settings. For e.g.. Chatterjee (2020); Zielinski et al. (2020) use it to verify that adding dataset reduces coherence but in order to do so they keep increasing amounts of label noise everything else the same, and limit their considerations to the start of training. But, to study the evolution of coherence, even over single training run requires normalization since the magnitude of the gradients changes significantly in the course of training (e.g., see Appendix [B).
Stiffness. Fort et al. in their preprint (2020) study variants of the average pairwise dot product that they call sign stiffiess and cosine stiffness. In our notation these are
Saign =
E IND.E'
sign(g= - 92/)] and Scos
E
92' |1g./1
These are meant to capture how a small gradient step based on one input example affects the loss on a different input example. Although Fort et al.) do not describe why they choose to transform the gradients in these specific ways, we expect it is to normalize the dot product so that it can be tracked the course of training. In their experience, they found sign stiffiness to be more useful analyze stiffness between classes whereas cosine stiffness was more useful within class.
Gradient Confusion. Sankararaman et al. in their preprint (2019) introduce the notion of gradient confusion bound. The gradient confusion bound is Ç 2 0 for all 2, e Z and 2 स z/. we have, Os 9s' 2 -c They use this concept to study theoretically the convergence rate of gradient descent, but in their experimental results they measure the minimum cosine similarity between gradients, i.e.,
min 2E EZ
9=
9z'
19=
We note that the conelineasssies (and to a lesser extent the 2 * z' restriction) make it hard to tie stiffness or minimum cosine similarity to what happens during training; specifically, to the change in the loss function as a result of a gradient step which is the expectation over all per-example gradients.
A NEW METRIC FOR COHERENCE
The key insight behind our proposal that there natural scaling factor that can be used to normalize the expected dot product of per-example gradients (i.e., the quantity in (T) that preserves the connection to the loss. Consider the Taylor expansion each individual loss &g around w when we take small step ft2 down its gradient ge:
(w + h2) (2 9= h2 -1 9=
Taking expectations over 2 we get.
[l + h2) (z(ww) = -n E 19 9z] anD
(2)
z~D
3

---

Under review as a conference paper at ICLR 2021
The quantity in (2) has simple interpretation: is the reduction in the overall loss E if each example la could be optimized independently. As might be expected intuitively, is lower bound on the quantity in ① and is tight when all the per-example gradients are identical. We prove this formally in $ Thus, it serves as a natural scaling factor for the expected dot product, and we obtain a normalized metric for coherence (denoted by a)) from and
a(w + h) f(w) E 2ND
T
9
9=
E
19x)
E
9:
g]
20
20
3ND
(3)
[K-(w hn) la (w)]
E 2ND
10=
B 2ND
19:
B
ga.
Thus, is the change in the overall loss due to small gradient step a fraction of the maximum possible change in loss if each component of the loss could be optimized independently.
As noted before, 0 S
1, and the maximum is achieved when all the gradients identical, and the minimum is achieved when the expected gradient is 0, i.e., a stationary point is reached.
A natural scale for a. Once again, consider sample with m examples 2; where S i m. Let g: be the gradient of z,. Suppose further that the Ji are pairwise orthogonal i.e. 9i 9j = for + j. It is easy to check that a 1/m. For sample of size m, call this value of a the orthogonal limit.
Since in the orthogonal case, each example is optimized independently, going down the expected gradient is 1/m times as slow as optimizing each independently. If the gradients are better aligned, we expect them to help each other resulting in an a greater than the orthogonal limit.
S m, suppose each gi has common component e and an idiosyncratic component uy, i.c., 9: = + us with U, 0 for 1 S j S. m and j # i; = 0; and say, Uj u = ||u||² for some u. It is easy to see that a in this case is [1 + (m - 1) where f |c| 2 [[le]2 + ||
Example (Commonality). For 1
These examples along with the observation that 0 < a < 1 suggests more evocative (even if less accurate and less general) interpretation: In a given sample, the average fraction of examples that each example helps or supports. Thus, when analyzing experimental data, for a sample of size m, it is convenient to define new quantity m-coherence as follows:
T
1g= 94r
m-coherence == WL a 2n D. A
19==
gzl
2ND
Thus m-coherence in the orthogonal limit is and in the identical case is m. Intuitively, m-coherence of sample is the number of examples (including itself) that any one example helps on average.
A Advantages. a and m-coherence have several advantages over the metrics discussed in $2
Computational Efficiency. For a sample of size m, due to (3). a can be computed exactly in (m) time in contrast (m²) time required for stiffness and cosine dot products. Furthermoree, it can be computed in a streaming fashion by keeping two running sums, so the per-example gradients need not be stored. Thus, in our experiments we are able to use sample sizes couple of orders of magnitude higher than those in Fort et al. (2020) and (Sankararaman et al. (019))
Mathematical Simplicity. We believe our definition cleaner mathematically. This allows us to reason about the metric more easily. For example,
We can show that the coherence of minibatch gradients is greater than that of individual examples (Corollary 3.1). Therefore, care must be taken if minibatch gradients are used in lieu of example gradients in computing coherence (e.g., as in (Sankararaman al. (2019).
2. Explicitly ruling out * s' as in done in stiffness and cosine similarity to eliminate self-corre colf-corelation is unnatural and can get tricky in practice due to near pear-duplicate or multiple examples leading to same or very similar gradients. We obtain meaningful values without imposing those conditions, but if one insists on removing self-correlations, then subtracting 1/m from a or from m-coherence is more principled way to do it.
3. The non- con-linerittes in stiffness and cosine similarity amplify small per-example gradients potentially overstating their importance, and lead to a discontinuity (or undefined behavior) with zero gradients. However, we can cleanly account for the effect of negligible gradients in our observations (e.g., see Lemma
4

---

Under review as a conference paper at ICLR 2021
Interpretability. Finally, discussed in detail above, they are normalized and yet easily interpretable due to the natural connection with loss.
Prior Work on Gradient Diversity. While writing this paper we discovered that the reciprocal of a appears in the theory literature gradient diversity. This used by Yin et al. (2018) in theoretical bounds to understand the effect of miiiibatchinn on convergence of SGD. (A sumilar result appears for least squares regression in Jain et al. (2018).) They show that the greater is the gradient diversity, the more effective are large mini-batches in speeding up SGD. Although they support their theoretical analysis with experiments on CIFAR-10 10 (where they replicate 1/r of the dataset times and show that greater the value of r less the effectiveness of mini-batching to speed up) they never actually measure the gradient diversity in their experiments (or further study its properties). Also, note that for our purposes a is better choice than 1/a not just because coherence rather than incoherence is what leads to generalization but also since the latter can diverge: g can be 0 without all g2 being setting).
zero (e.g., at the end of training in
4 A MORE GENERAL SETTING FOR COHERENCE AND SOME BASIC FACTS
Our notion of coherence not specific to gradients (or optimization) but extends naturally to vectors in Euclidean spaces. Let V be a probability distribution on a collection of m vectors in an Euclidean space. In accordance with 3 we define the coherence of V (denoted by a(V)) to be
a(V)
E
10
Note that Elv v] 0 implies E/u vf] O. In what follows, we ignore the technicality of the denominator being 0 by always assuming that there is at least one non-zero vector in the support of (which also held in our experiments). We list some basic facts and the proofs are in Appendix
Theorem (Boundedness). We have O S a(V) < 1. In particular, avV) = 0 iff En-v[o] = 0 and
a(V) 1 iff all the vectors are equal.
Lemma 2 (Scale Invariance). For non-zero k E R. let kV denote the distribution of the random variable ku where v is drawn from V. We have o(kV) = (VV).
Theorem 3 (Stylized mini-batching). Let U1, U2, U/ be k i.id variables drawn from V. Let W
denote the distribution of the random variable w E U4. We have,
k- a(V)
a(W) 1+ (k: - 1) a(V)
(5)
Corollary 3.1 (Minibatch amplification). a(W) 2 a(V) with equality iff a(V) = 0 or (VV) = 1.
Remark. This formulation provides a nice perspective on the type results proved Yin et al.] (2018) Jain et al. (018). When < 1/k but non-zero (i.e., we have high gradient diversity), creating mani-batches of size l increases coherence almost & times. But, when a z 1 (i.c., low diversity) there is not much point in creating mini- bani-batches since there is little room for improvement.
Lemma 4 (Effect of zero gradients). W denotes the distribution where with probability >> 0 we pick a vector from V and with probability P we pick the zero vector then aW) p- a(V).
Example (Coherence Reduction). If we add zero gradients to the collection of gradients con- structed in the example of |3 (Commonality) using Lemma 4 we get.
m
1 |1+ (m 1) 1)- f] = n [1 (n-k-1)-5
m m
m
where n m is the size of this new sample. For a fixed n, as i increases, decreases going down to 1/n (the orthogonal limit) when all but one vector in the sample is zero, i.e., h = n 1.
5 EXPERIMENTAL RESULTS
As stated in the introduction, our objective in developing m-coherence is to better understand the recently proposed CG explanation for generalization (Chatterjee 2020 Zielinski et al. 2020). We
5

---

Under review as a conference paper at ICLR 2021
50% epoch)
50% (remaining)
100% epoch)
100% (remaining)
epoch)
(remeining)
23.0
Thaneg
Twinigg
Trihiing
25.3
32.5
13.3
12.5
300
201
8.0
01
80
323
42
140
Top-1 Accurayy (parcent)
Text
Text
Traniog
Teat
Tran-ng Text
Thanes Text
Trshing
100
20
cacherenne (entire model) -e
381
10'
10"
35'
10-
301
301
38
10P
309
00R
337
300
303
385
23
43
66
06
500
300
300
30
49
83
80
353
383
305
42
30
To coherencce (dlssiiccaton bayer)
10a
307
337
162
3.0
000
332
colfrencc (middl layen
38'
10'
301
001
231
101
20"
231
10"
000
381
380
200
303
20
40
66
06
500
200
306
20
49
53
86
300
380
300
25
46
66
colfrrence Frest layed
x %
102
12"
20
10P
122
101
12"
step
epoch
step
epoch
step
epoch
Figure 1: The evolution of alignment of per-example gradients of ResNet-18 during training as measured with m-coherence on samples of size m = 50,000 on 3 variants of ImageNet with different amounts of label noise. Our main finding is that coherence not only decreases in the course of training (as expected from Lemma when examples get fit), but it also increases. A high peak is reached rapidly with real labels (in the first 100 steps) and much lower peak reached slowly with random labels (over many epochs). Horizontal lines for m-coherence are shown at I (the orthogonal limit) and at m. Vertical lines indicate sharp reductions learning rate. Light dots show the results of other runs understand sensitivity w.r.t. randomness in initialization and mini-batch construction.
now measure m-coherence in setting very similar that used by Zielinski et al. 2020 for studying memorization and generalization.
Methodology. We train ResNet-18 (He et al. 2016) models on ImageNet with original labels (0% noise), and two derived datasets: one with half the training labels randomized (50% noise), and another with all the training labels randomized (100% noise) We use SGD with momentum (0.9), a batch size of 4096, and the learning rate schedule proposed in Goyal et al.) (2017). We turn off augmentation and weight decay to observe memorization in the noisy cases within reasonable number of steps. For each dataset, we track m-coherence on a random (but fixed) set of m 50,000 training examples.
Figure shows the data from our experiments. Each column corresponds to a different experiment and the rows show loss, accuracy, and m-coherence for the entire model and some specific layers.
We the original ImageNet validation our test set in all cases.

---

Under review as a conference paper at ICLR 2021
Real Labels. Our first experiment (shown in the second column of Figure I for reasons that will become clear shortly) measures the m-coherence (row 3) for training with 0% noise, i.e, the real ImageNet labels at the end of each epoch. The coherence the end of the first few epochs is very high, between 10 and 10" and it decreases as more training examples get fit. We note that although there is some fluctuation in the coherence, it stays high (above 102 and often above 109) until well after the accuracy crosses the 50% mark. It settles at after all the examples are fit.
The high coherence in early epochs agrees well with the intuition from CG that real datasets have good per-example gradient alignment since that is what is necessary for good generalization as per the theory. The subsequent decrease in coherence in the course of training expected from Lemma under the assumption that the gradients of fitted examples become small.
Our second experiment (column 6) shows that with random labels, the coherence in the first few epochs is low (between I and 10). It increases steadily until it reaches peak in epochs 40 to 60 (above 102 but less than 10²) followed by a decrease.
Random Labels.
The low coherence (near the orthogonal limit) in the first few epochs agrees well with CG as discussed in the introduction but the subsequent increase is surprising (though not in contradiction with CG as discussed later). The increase is not small since at its peak each example is helping hundreds of other examples (though is well below the 10a peak seen with real labels). Once again, as examples get fitted, coherence decreases as expected from Lemma 4 though not back down to I, likely since training only goes on till about 80% accuracy is reached.
The increase in one case and not the other leads to natural question with implications about the dynamics of SGD: Is the evolution of coherence fundamentally different between the well-genent generalizing case (real labels) and the memorization case (random labels)?
Coherence in the First Epoch. To study this question, we took a closer look at the first epoch. We recorded m-coherence at initialization (i.e., before the first step) and, thereafter, for every other step in the epoch. Since this requires computing the per-example gradients for 50K examples every 2 steps, this was our most computationally expensive experiment taking a day per run using TPUs. The results are shown in columns (real labels) and 5 (random). We find that in both cases coherence starts from about the same low point and starts rising. The rise is much faster for real la-
noise [1st epoch)
0% noise [remainnng epochs]
bels than for random labels. We ran addi-
tional experiments with 50% noise (column
m-cchherence
10a
10
10
EffiientNee-B0
ResNet-18
3) and with 25% and 75% noise to con-
10a
10a
firm that the slope with which coherence increases depends inversely on the amount of label noise (see Appendix B)
101
10
10"
EfficientNet-B0
ResNet-18
10"
0
0
100
700
300
25 50
75
The Overall Evolution. If we combine the data from the steps of the first epuch with the rest of training (c.g., in row 3 we jointly view columns and 2), we find remarkably consistent pattern across all noise levels: m-coherence follows a broad parabolic trajectory (albeit with some local variation and noise) where it starts small, increases to a peak, and then goes back down. Thus, there is always an initial increase in coherence, just on different timescales.
step
epoch
Figure 2: model shows similar increase as ResNet. The overall trajectories are also similar, and it is interesting to note that we get similar values for coherence although the two architectures are very different.
The early trajectory of an EfficientNet-BB
From this point of view, the evolution of coherence in the memorization case does not look fundamen- tally different from that in the well-generall generalizingg case.
Impact of Layers. The bottom 3 rows of Figure D shows coherence by layer for 3 illustrative layers (the first convolution layer, convolution layer in the middle, and the final fully connected layer). Although the specific values are different across the layers we notice that the broad trajectory
'Since, the interpretability of meccoherence allows for meaningful comparisons between layers, we can get some additional insight into the dynamics of training by studying these values. We do in Appendix B
7

---

Under review as a conference paper at ICLR 2021
observed for the coherence of the entire model holds for each individual layer. Thus, the trajectory (and in particular the increase) is not driven by one specific layer.
Impact of Architecture. We studied one other architecture, EfficientNet (Tan & Le 2019). and found a similar increase in coherence and indeed a similar broad trajectory (Figure and Appendix B
Coherence Test Set. For completeness, we also measured the coherence m examples not used for training (drawn from the ImageNet validation set). We defer the discussion to the Appendix.
Reconciliation with Other Studies. Although direct comparison with the results in Fort al. (2020) and (Sankararaman et al. (2019) is not possible due to differences in metrics, sample sizes, datasets (ImageNet v/s CIFAR), and effects studied; in much as they can be compared, did not find contradictions. Please see Appendix for more details.
6 DISCUSSION AND FUTURE WORK
In this paper, we have presented m-coherence, a mathematically clean and easily interpretable metric study the evolution of the alignment of per-example gradients in the course of training. As stated in the introduction, our motivation in developing this metric is to better understand the recently proposed CG explanation for generalization (Chatterjee 2020 Zielinski al. 2020).
As noted in Sections and in contrast to unnormalized metrics such as the expected pairwise dot products of per-example gradients (which are difficult to compare across different training steps or architectures), or previously proposed normalized metrics such as stiffiness or confusion (which are difficult to interpret due to ad hoc normalization that breaks the connection with the loss), the natural normalization employed in m-coherence allows as the number of examples (including itself) that any one example helps on average. In turn, this property permits us reason directly about the CG explanation.
directly interpret the value of m-coherence
Insights on Coherent Gradients (CG). Based on our measurement of coherence in the setting of Zielinski et al. )2020), for generalization: CG assumes that coherence exists, and from that, it shows how gradient descent can exploit it-this the causal mechanism that the CG papers verify through intervention experiments.
now pinpoint precisely what is missing in the original CG explanation
However, CG does not address where the coherence comes from and simply assumes that is a property of the dataset. For example, CG assumes that real data has high coherence, and that data with random labels has low coherence (e.g,, Section 2.2 in Chatterjee (2020)). Our measurements show that this assumption about coherence is not entirely true: For both real and random labels, at the start of training, coherence is low, and then increases.
That said, consistent with the intuition from CG, we find that the peak coherence with real labels is much higher (each example helps ss 10s other examples) than the peak with random labels (each example only helps As 10 other examples). Furthermore, the peak with real labels is reached very quickly (well within the first epoch) whereas with random labels it takes much longer (many epochs).
The failure of this assumption leads a very interesting open question:
What causes the alignment of per-example gradients, i.e., coherence to increase the course of training?
Since the increase happens both in the case of real labels and in the case of random labels, we conjecture that the increase is an optimization phenomenon and not directly related to generalization. Going back to the analogy with random forests in the introduction, the creation of coherence is similar to the finding of commonality (possibly spurious) between examples during decision tree construction (c.f. discussion on generalization in deep learning in Section 4 of Chatterjee & Mishchenko (2020).
In other words, while an explanation for why gradient descent generalizes is provided by the original CG hypothesis (if coherence exists, gradient descent exploits it by taking larger step in the direction that improves many examples). we now need an explanation for the optimization phenomenon of why coherence increases in gradient descent (since it does not start off high even in the case of real data).
8

---

Under review as a conference paper at ICLR 2021
It is important to note that in contrast with the increase in coherence which is mystery, the decrease in coherence as training progresses, and more examples get fit, is expected, as may be observed from Lemma and and the example on Coherence Reduction.
Practical Applications. Finally, it would be interesting to explore some practical applications of this metric. For example, we could consider using metric derived from m-coherence to predict the generalization gap as a result of training. While a simple heuristic might be to use the area under the curve of m-coherence over time as an (inverse) measure of the generalization gap, better heuristic would also incorporate for the distance travelled in parameter space since, as our experiments show, low coherence for relatively few steps (e.g.. early in training with real labels) or when gradients are small (e.g.. late in training) is not fatal for generalization.
Another possible use of m-coherence could be to freeze certain layers if they have low coherence to prevent overfitting in those layers to improve the speed of training (e.g. if all lower layers are frozen). These practical applications would require even faster methods estimate coherence. One way to do that might be to compute the coherence between mini-batches (with exponential moving averages) and then applying Corollary 3.1 reverse.
REFERENCES
Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang. Stronger generalization bounds for deep nets via a compression approach. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, ICMI. 2018, Stockholmsmüsssan, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pp. 254-263. PMLR, 2018. URL http:::pppocceeeiiiiiie
mlr press //////00///////// a/aarar0.8.... 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 at memorization in deep networks. In Proceedings of the 34th Inter- national Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, pp. 233-242, 2017. HRRLhttp:2/ http:/t::pppccccciiiiiis
ml wttp...ppe..////////aa/p////pp/
html
Peter L Bartlett, Dylan J Foster, and Matus J Telgarsky, Spectrally-normalizedd 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 6240-6249. Curran Associates, Inc., 2017.
normalized margin bounds for
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine-leariing practice and the classical virinvariance trade-off. Proceedings of the National Academy of Sciences, (16(32):15849-11 15844, 2019. ISSN 0027-8424. doi: 1t17733ppas.190337011.. URL
https: / www. pnas. org/ Cowtent/iieeee wttp:/nnnnnntnnnneeeeeeeeee wtw.eeettti111//1111333333
Olivier Bousquet and André Elisseeff. Stability and generalization. J. Mach. Learn. Res., 2:
499-526, March 2002. ISSN 1532-4435, doi: 10.1 10.116//1522443277600777 | https
//doi. 1ttp.//gg/..11e//332255566260000
Satrajit Chatterjee. Coherent gradients: An approach to understanding generalization in gradient descent-based optimization. In Proceedings of the International Conference on Learning Repre- sentations ICLR, 2020. URL
/ F http:///eerreeeioe.eeerrrrrrrrar
Satrajit Chatterjee and Alan Mishchenko. Circuit-based intrinsic methods to detect overfitting. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, Vienna, Austria, PMLR 119, 2020, 2020.
01991
Stanislav Fort, Pawel Krzysztof Nowak, Stanislaw Jastrzebski, and Srini Narayanan. Stiffness: A new perspective generalization in neural networks. CoRR, abs/1900..0949133 2020. URL httt:://axxiv.oor//bb.... /2tp/////b//0100099991133
Priya Goyal, Piotr Dollár, Ross B. Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch. Yangqing Jia, and Kaiming He. Accurate, large minibatch SGD: training imagenet in 1 hour. CoRR, abs/1 706.02677, 2017. URL htRl:http://ardt http:///arrii..orrr///////// wttp://o//aa///o/oo 71t1/71166660777777 02677

---

Under review as a conference paper at ICLR 2021
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 16, pp. 1225-1234. JMLR.org, 2016. URL https:// /ttp:///xxvvvv org/ abs/ 1509.00000 11.5599.124... 01240
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In 2016 IEEE Conference Computer Vision and Putter Recognition, CVPR 2016, Las Vegas, NV, USA, June 27-30, 2016, pp. 770-778, 2016. doi: 10.1 1099CVPR URL
https: /oi. www.oogggoooooo 10. 1109/100000 /w110//////.... CVPR. 2016. 90
Prateek Jain, Sham M. Kakade, Rahul Kidambi, Praneeth Netrapalli, and Aaron Sidford. Parallelizing stochastic gradient descent for least squares regression: Mini-batching, averaging, and model misspecificatioo. Journal of Machine Learning Research, 18(223): 2018. URL http
// http://ppppppppps.////se/ 5ttp:////11116555..111 59hmmml
K. Kawaguchi, L. Pack Kaelbling, and Y. Bengio. Generalization in Deep Learning, ArXiv e-prints, December 2017. (tttts::: /arxivv hbwpg/abb/1110.00 0546..
IÍa 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. 2224, Stockholmsmässan, Stockholm Sweden, 10-15 Jul 2018. PMLR.
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' Alché-Bue, 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. 11611-11622, 2019.
Behnam Neyshabur, Zhiyuan Li, Srinadh Bhojanapalli, Yann LeCun, and Nathan Srebro. Towards understanding the role of over-paramettrizaioo in generalization of neural networks. CoRR, abs/1805.12076, 2018. UtL/htts://arxxxvv...
abs 1800.180.000 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 Learning, volume 97 of Proceedings of Machine Learning Research, pp. 5301-5310, Long Beach, California, USA, 09-15 Jun 2019. PMLR. URL/ntt::/prrceediii . mlr press/v97/ rahaman 9a. html
Machine
Karthik Abinav Sankararaman, Soham De, Zheng Xu. W. Ronny Huang, and Tom Goldstein. The impact of neural network overparametterizatin on gradient confusion and stochastic gradient descent. CoRR, abss/1904.069e
2019. BRLLhtttp///xxiiii org/ a1s/ 06963v4
Mingxing Tan and Quae V. Le. Efficientnet: Rethinking model scaling for convolutional neural networks. Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.). Proceedings of the 36th Inter- national Conference on Machine Learning, ICMI. 20/9, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pp. 6105-6114 PMLR, 2019. html
URL http:http//prrccceediee ottppp/ceeeeaooooo...prere////aa
m.. www.pesssvv/taani
Dong Yin, Ashwin Pananjady, Max Lam, Dimitris Papailiopoulos, Kannan Ramchandran, and Peter Bartlett. Gradient diversity: a key ingredient for scalable distributed learning. Amos Storkey and Fernando Perez-Cruz (eds.), Proceedings of the Twenty-Firs International Conference Artificial Intelligence and Statistics, volume 84 Proceedings of Machine Learning Research, pp.
1998 2007, Playa Blanca, Lanzarote, Canary Islands, 09-11 Apr 2018. PMLR.
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.
Piotr Zielinski. Shankar Krishnan, and Satrajit Chatterjee. Weak and strong gradient directions: Ex- plaining memorization, generalization, and hardness of examples at scale. ArXiv, abs/2003.07422. 2020. URI.https. Phttps://arxivv wttp:///gaa.aooaa/ooo/
07422
10

---

Under review as a conference paper at ICLR 2021
A
OMITTED PROOFS
We present the proofs omitted from Section 4 Recall from (4)
that
a(V) --Var- [o.
E 10-
Theorem (Boundedness). We have 0 S a(V) I 1. In particular, a(V) = iff Eu-v(o] = 0 and a(V) iff all the vectors are equal.
Proof. Since 2 0 for any have Ey-y(U- v| 2 0. Furthermore, it is easy to verify by expanding the expectations (in terms of the vectors and their corresponding probabilities) that
E
IV v']
E w
[v]
[ 0. 2
E
(6)
Therefore, aVV) 0. Likewise, another direct computation shows that
0 E v'aV o (1 v') L [v] w')] = E
(
-~ [r.
E A~
[e]
E
[0]
Since from Equation 6 we have E[c] E[u] = Elu - w/I, it follows that a(V) < 1. Furthermore, since each term of the expectation the left is non-negative, equality is attained only when all the vectors are equal.
Lemma 2 (Scale Invariance). For non-zero k E R. let kV denote the distribution of the random variable ku where u drawn from V. We have o(kV) = aVV).
Proof.
[u-u]]
[ko 1oo')
E o V- V.r'
[0-0]]
p'
new V. w
a(kVV=
= a(V)
(8)
E
(0-
E
[Ko koo
0000
Theorem (Stylized mini-batching). Let U1, 12,,2,,-- 1%k be K i.i.d. variables drawn from V. Let W denote the distribution of the random variable w = Σi= Us. We have,
k aV)
a(W) a(kW)
(9)
1+ (k - 1) a(V)
Proof. The first equality follows from Lemma
For the second equality, we have,
[w . w']
E
v/)
k2 E
[u-
WwW
v V
(kW)
w/ kW
E WMW
w)
E
k E
+
x: (k:
1)
E
10.00
v'
Vn w'
By dividing the numerator and denominator the last expression by (e o] the required result follows.
wayy
Corollary 3.1 (Minibatch amplification). a(W) 2 a(V) with equality iff aVV) = 0 or (V)) = 1.
Proof. From the previous theorem, the transformation in coherence due to stylized mini-batching is given by the map I+(k-1)-a" Now, since < 1, we have & 2 1 (I: 1) a, and since 2 0. k-n
Finally, it is easy to check that the multiplying both sides by T= we have T+(K-1)-0 only fixed points of the map are 0 and

---

Under review as a conference paper at ICLR 2021
Lemma 4 (Effect of zero gradients). If denotes the distribution where with probability p 0 we pick a vector from V and with probability - p we pick the zero vector then a(W) = P a(V).
Proof.
E www.wwww a(W)=
[w w']
p²
o unVV [w-r0]
E
p. E 20 = =p.)(V)
(10)
w-W [20 - w|
vn
B ADDITIONAL EXPERIMENTAL RESULTS AND DISCUSSION
Experimental Setup. Our code for running experiments was heavily based on an open source Tensorflow example 5 with modifications to allow label randomization and coherence metric logging. We used SGD with momentum (0.9), a batch size of 4096, and the learning rate schedule proposed in Gnyaaa et al. (017). We did not use weight decay or random augmentation of the input.
When measuring per-example gradients compute m-cohherence, for normalizing activations in a batch norm (BN) layer, we use the moving averages collected by the layer, i.c., we measure per- example gradients in eval mode. However, in the first few steps of training, since the moving averages are initialized at O, the per-example gradients measured in this manner may not be accurate. We address this by priming the moving averages in the BN layers by running 40 steps without updating any trainable parameters (or momentum values) with no-op optimizer at the start of our experiments.
The importance of this correction depends upon the architecture. For example, for ResNet- 18 on ImageNet, without this correction, we ln(1000) 6.9) in the first few steps of training due to very large activations feeding the final softmax layer. This leads to artificially high gradient measurements and m-coherence. However, these measurement artifacts disappear in about 25 steps as the BN averages get primed.
artificially high loss (16 instead of the expected
Variation across Layers. One advantage of m-coherence is that it is natural use it to compare different projections of the per-example gradients and as such can be used to directly compare different layers with each other. Rows 4, 5 and 6 of Figure [ shows the m-coherence of the classification layer, a convolution layer in the middle and the first convolution layer respectively. We only show the m-coherence for the weights (since in spot check the m-coherence for weights and biases for given layer looked very similar). We make a few observations.
First, convolutional layers have higher coherence than the fully connected layer. Although this could be function of depth, we note that this may also be expected for a different reason. Since convolutional layers have filters that are instantiated at multiple sites, and the gradients from those sites for a single example add up in the overall gradient for single gradient. Therefore, by reasoning similar to that of Lemma 3.1 we expect the coherence of the gradient across sites to be greater than those for the sites individually. And with more sites, we expect greater coherence. This is another way to see that weight sharing prevents overfitting.
Second, the convolutional layers, particularly the first one shows high coherence for random labels (though still generally lower than those for real labels). However, the fully connected layer, there is much greater difference between real and random labels. For random, it is generally quite low reaching 10 at the peak, whereas for real, while the examples are being fit, it is usually above 10 and in early epochs, before overfitting sets in, it even exceeds 100.
Third, the only place where m-coherence sometimes falls below (the orthogonal limit) is in the first convolutional layer for real data after training accuracy has reached 100%. At that point, the layer may be over-constrained, i.e., improving the loss on one example may degrade it on another (though the discussion below test set coherence). Everywhere else, m--chheennce tends to be at or above the orthogonal limit in line with our expectation that this learning problem is over wer-parameterized.
Finally, we note that the different layers for EfficientNet in Figure show similar characteristics as those for ResNet.
12

---

Under review as a conference paper at ICLR 2021
50% epoch)
50% (remaining)
100% epoch)
epoch)
(remelning)
(remaining)
23.0
Thaneg
Twiiig
Trikiin
Thaming
32.5
12.5
13.3
54
3.0
300
201
8.0
01
323
8.0
140
Top-1 Accurayy (parcent)
Text
10
Teat
Trening
90
Taxt
Ten:
Triliing
82
Text
Thann-g
Teat
Tramngg
cocheeence (entire model)
381
10"
17"
35"
30-
301
38
10P
Se/er/
309
000
337
300
303
305
20
43
66
06
300
300
300
20
49
53
80
383
383
42
To coherencce (Slssincation bayer)
100
309
337
38
162
330
000
332
(middl So
38'
10'
30"
001
23'
colferencc
281
101
20"
18"
16"
600
300
300
303
20
40
66
64
530
200
306
20
49
53
86
300
380
300
46
66
cocherencce (Fest layed
201
10a
12a
10
102
12
101
12"
step
epoch
step
epoch
step
epoch
Figure 3: The evolution of alignment of per-example gradients of EfficienntNe-BB network during samples of size 50,000 on 3 variants of ImageNet
training measured with m-coherence with different amounts label noise. We note that the results are qualitatively in agreement with what we on ResNet, i.e., in both real and random cases we coherence increase. A high peak is reached rapidly with real labels (in the first 150 steps) and a much lower peak is reached slowly with shown 1 (the orthogonal
random labels (over many epochs). Horizontal lines for m-coherence limit) and at m. Vertical lines indicate sharp reductions in learning rate.
Coherence on Test Set. For completeness, we also measured the coherence on m examples not used for training (drawn from the ImageNet validation set). They are shown in columns and 2 of Figure as "test." the first epoch, we find that test and training coherence are roughly similar. However, when we look at the rest of training, we find that in the early part of the rest, test coherence is below that of training coherence, but the later part, the opposite is true. This may be further evidence that coherence creation is pure optimization phenomenon (as per the discussion in Section 6 of the main paper), i.c. the coherence creation (and subsequent consumption) is specific to the training examples.
It is interesting observe that particularly for the convolutional layers, the end of training, the test m-coherence is at 10 whereas training m-cohhrence is at or even lower. This suggests that those layers are adapted to the training examples beyond what is likely to generalize.
Reconciliation with Other Studies, Fort et al. (2020) use the cosine and sign stiffness measures to study how gradient alignment depends class membership, distance in input space between data
13

---

Under review as a conference paper at ICLR 2021
naise (remeining)
50% epoch)
50% (remaining)
100% epoch)
100% (remaining)
epoch)
23.0
Thaneg
Twiiig
Trihiing
32.5
13.3
12.5
300
201
8.0
01
10
43
80
323
203
42
140
Top-1 Accurayy (parcent)
Text
Teat
Traning
90
Taxt
Tramiing
Trannig Text
Thanes Text
Telt
20
Sccherenne (entire model) 9.
381
Traniing
10'
10"
33'
10-
301
301
Thaning
385
10P
309
00R
337
350
303
303
23
43
66
330
300
300
30
49
83
80
353
383
305
42
To coherencce (dlssincation bayer)
Teat
100
309
337
102
3.0
50R
332
Text
Colerence (middle layen
:el
38'
Irsakgg
10'
301
001
237
10"
231
Trasing
18"
102
000
381
380
300
303
20
40
66
06
530
200
306
20
49
53
86
300
380
300
25
4
66
colference Frest layed
x %
Teat
10a
10"
10
107
122
101
12"
Taxt
step
epoch
step
epoch
step
epoch
Figure 4: The evolution of alignment of per-example gradients of R during training as measured with m-coherence on samples of size m = 50,000 on 3 variants of ImageNet with different amounts of label noise. This figure is similar to Figure but also includes m-coherence plots for ImageNet test dataset (in column and 2).
points, training iteration and learning rate. They MNIST, Fashion MNIST, STFAR-10/100 and MNLI datasets. Typical sample sizes are around 500 (for the 10 label datasets) and 3000 (for the 100 label datasets). They do not study label noise or memorization explicitly. In their class-based analysis, they find that initially, an example of a class only helps other examples in its class and adversely impacts examples of other classes. However, in the course of training. this effect goes down, and stiffness between classes goes up (though only to end up at 0).
We do not explicitly perform blass- analysis, since with 1000 classes and about 1.2M training examples in ImageNet, we expect on average only 2 to 3 examples in each class pair. However, implicitly, our study an inter-class analysis (though not a class-pair analysis) since our sample, each example is expected to roughly 1000 times many examples of other classes it does its own class. Our results indicate that examples in one class do help examples in other classes at different points in training since m-coherence is often in 1000s, and in sample of approximately 50k, we expect only about 50 examples per class.
However, since metric is very different (as discussed in detail in Sections 2 and 3 of the paper), and the eтror bars in their study are large (as indicated in their Figure 5). we do not directly see any contradictions in the experimental data between their study and ours. Finally, do not study
14

---

Under review as a conference paper at ICLR 2021
coherence function of input distance between examples or of learning rate changes, though are interested in investigating the latter in future work.
Sankararaman al. (2019) show theoretically that high gradient confusion impedes the convergence of SGD, and also analyze how factors such as network depth and width and initialization impact gradient confusion. They validate their theoretical results with experiments MNIST, CIFAR- 10, and CIFAR- 00 (real labels only, since they do not study memorization) where they measure the minimum cosine similarity (MCS) between different training examples They mainly focus on the MCS value at the end of training as various architectural parameters are varied, but in Figures 7(c) and 8(c) in the appendix. they show the trajectory during training. There, we find that MCS starts low, increases to a peak and then comes back down again, in qualitative agreement with our findings.
They
Finally, in Figure we show the individual terms (the numerator Elg. 92'] and denominator E[g= 9=]. Although the numerator can be estimated from the slope of the loss curve (as per equation (1) in the main paper), without the denominator to give scale, it hard to understand what variations are meaningful. As extreme example, be seen in the loss plots from other studies such as Zhang et al. (2017) Zielinski et al. (2020)) in the 100% random case, for the first 20 epochs or so, the norm of the expected gradient is close to zero (Figure 5 last column, row 1). However, there is sigmificant activity in the denominator (row 2: and this is not typically recorded in experiments). By considering the quotient, and furthermore, by putting it into context with the orthogonal limit (as we do with m-coherence where that limit sets the that there is definite build up in coherence in that period (row 3).
see that, as expected from the loss curve (and this may
scale),
Effect of sample size m. Figure 6 shows the effect on m-coherence and a of doubling m from our baseline value of 50,000 to 100,000. We see that the numerical values generally the same, showing a slightly upward bias in m-coherence for the larger value of m as might be expected.
25 % and 75% label noise. The data for ResNet-18 18 training on 25% and 75% label noise is shown in Figure 7 This confirms the pattern noted in the main paper (Section 5) that with increasing noise, there is decrease in the rate which coherence increases.
'Since it is computed from mini-batch gradients rather than individual examples, it may over the gradient alignment (with the estimate being more inaccurate when alignment is low). Please see discussion in Section of the main paper and Corollary 3.1
15

---

Under review as a conference paper at ICLR 2021
0% nolse 11st oparh)
0% netso (remaining)
50% nolso
50% nolse (remaining)
100% noise (28t opoch)
1000% neise (remaining)
12st opach)
E. Euny io ad Tentire modell
107
L07
10-
131
29P
100
140
38F
By 60. 400 (eekite modee)
191
197
107
107
LE7
166
230
306
360
230
260
302
206
306
20
Sacoheoee [onti mosel
107
107
20*
5 Buu la "k (clessifiatio layert 14
139
1.2
101
10"
30"
100
300
20
303
45
380
200
300
26
By elg-- 92 Iclassficaaion layer) 2 %
10"
1.7
23
20"
10-
38'
231
23
10"
38*
230
200
purcoherence trussification layee)
% 12 33
107
1.7
1.7
38
liest layer
10"
1."
5.
106
104
43
8.6
139
10"
1.7
31a
(fret (ayed)
1.-
107
1.7
101
1."
m--chherence Birst layer)
te.
38
266
266
243
200 200
300
26
336p
epoch
step
epoch
st6p
opoth
Figure The expected gradients in the numerator and denominator for (not m-coherence) corresponding to Figure Note that even when the expected gradient flat (as may be inferred even from the slope of the loss function), there is activity the denominator which gets picked up with or m-coherence particularly, if the scale is set appropriately w.r.t. to the orthogonal limit.
16

---

Under review as a conference paper at ICLR 2021
10a
- 55,021
in U00 (00)
Cocherence
m 032
10
10a
10
10t-
10a
10a
epach
epoch
Figure 6: To understand the effect of m for the values of a and m-coherence, we plot these values for m = 50,000 and m 100,000 for the ResNet-18 18 training on 0% noise. In both plots we show horizontal lines for the orthogonal limit (which is different for the two samples in the a plot since it is 1/m, but the same in the m-coherence plot since is both cases) and the perfect alignment case (which is the same in the plot since it is I, and is different in the m-coherence plot since it is mn.)
25% noise
25% nobe (nemaining)
75% noise epoch)
75% noise (remaining)
[1st apach)
Tarki
1084ngg
33.0
28.0
10.0
10.0
5.0
258
266
300
109
Top-3 Arcuracy (percent)
Text Ovatt
Ovaft
Overt:
Taxing
Ni-coheeens (entrre (idda))
10"
107
122
122
coherence Intuzaiication layer)
30"
365
307
309
18
381
318
280
253
390
23
30
cocherencc (miidall (r))
167
367
1.i0 2/5
colference
(ffi2t byyan
30'
30'
181
361
155
107
122
18
30
380
358 step
269
350
330
33
66
66
60
20
200
150
330
300
20
epoch
step
Figure 7: Evolution of m--chhernnce for 25% and 75% label noise (under the same settings as Figure D This confirms the pattern discussed the main text that with increasing noise, the rate at which coherence is created in early training slows down.
17


Reviews:
[{"review_id": "yWYUqgknY9t", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "######################################################################\n\n1.  Paper Summary \n\n\nThis work introduces m-coherence, a new method for understanding gradient coherence when training deep neural networks.  The authors then present theoretical properties of m-coherence (importantly scale invariance) and demonstrate that m-coherence can be computed in a computationally efficient manner.  The authors then compute m-coherence across steps/epochs when training ResNet-18 and EfficientNet on ImageNet without label noise, with 50% label noise, and 100% label noise.  The experiments demonstrate that (1) m-coherence matches intuition after an initial phase  (i.e. m-coherence is large and decreases over time for real data) (2) m-coherences increases for all datasets to a peak in the first 100 epochs before decreasing.  \n\n######################################################################\n\n2. Strengths\n\n2.1. m-coherence is a very natural metric for understanding gradient coherence in that it is scale invariant, easy to compute, and is easy to analyze mathematically.  \n\n2.2. The description of m-coherence and its properties is presented well in comparison to recent work.   Additionally, the proofs follow almost immediately from the definitions and highlight how m-coherence is a simple, intuitive framework for understanding gradient coherence.  \n\n2.3. As m-coherence can be computed in a computationally efficient manner (both in algorithm complexity and memory usage), the authors are able to analyze gradient coherence on modern convolutional networks trained on 50,000 examples from ImageNet.  Importantly, the authors present both step-wise m-coherence and epoch-wise m-coherence, which highlights the phenomenon of m-coherences increasing for the first few steps of SGD.  This empirical finding could be an important stepping stone for theoreticians in understanding optimization and generalization for over-parameterized models.  \n\n2.4. The authors also highlight that the initial increase in m-coherence is robust across a variety of architectures, label noise settings, and initializations/minibatch constructions.  This finding is rather surprising in that it occurs even on datasets with 100% label noise.  \n\n######################################################################\n\n\n3. Limitations/Questions\n\n3.1. I would have liked to see an explicit comparison of m-coherence with the other recent methods on a subset of CIFAR10.  In particular, does a similar trend arise of gradient coherence first increasing before decreasing under these other methods?  I read through the discussion in the appendix about this result being consistent across these papers, but there appear to be caveats with what samples were considered in other works.  It would be interesting to compare gradient coherence under these methods using a fixed random subset of CIFAR10 across methods (please let me know if I missed anything though in case this is already done).  \n\n3.2. (Minor) Just for some clarity, it would be interesting to understand the makeup of the 50,000 samples considered in the experiment.  How far away is the sample set from having 50 examples per class?  ImageNet also has a large number of classes of similar objects (e.g. ~100+ dog classes).  Is there indeed a higher m-coherence for such subsets of ImageNet during training or does m-coherence actually increase on these subsets as well?\n\n\n######################################################################\n\n4. Score and Rationale\n\nOverall, I vote for accepting this paper.  I find the contribution of m-coherence to be novel, practical step towards understanding gradient coherence for modern machine learning settings.  In particular, I feel that these findings will be of interest to theoreticians interested in the intersection of optimization and generalization.  My only criticism of the work would be that the authors should try to provide a more concrete comparison with other works on a random subset of CIFAR10 to determine whether gradient coherence phenomena are robust across all these methods.     \n\n\n######################################################################\n\n\n5. Minor Comments\n\n5.1. I think the \"overfit\" label in Figure 1 is a bit confusing in the second row of Figure 1- is this just the gap between and test error? If so, I feel that just re-labelling this as the \"Gen. Gap\" or even just removing it would be fine.  \n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "iFr_YRfRtqK", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "In this paper, the authors provide a new metric named m-coherence to measure the gradient coherences, i.e., the alignment of per-sample gradients. The proposed metric is to normalize the expected pairwise dot  product by an expected gradient norm. The authors show that the proposed metric is computationally efficient, mathematically simple, and may help researchers to investigate the gradient coherence behaviors during the entire training process. The authors provide some simple mathematical explanations and characterizations of the properties of m-coherence, e.g., boundedness, relativeness to sample minibatch, the impacts of zero gradients. The empirical results based on m-coherence are mostly intuitive. For example, as more training samples are fitted, the gradient coherence will decrease because more per-sample gradients are close to zero. There is also some surprising results. For example, the experiments on random labels show that the gradient coherence does not go to the expected 1.  \n\nStrength:\n\n(1) The proposed metric is computationally efficient, and can be of interest to researchers who aim to explore the generalization behaviors of SGD or other algorithms in training neural networks.\n\n(2) The paper is well written and easy to follow. The empirical results seem reasonable.\n\nWeakness:\n\n(1) Some of these empirical results are not surprising (and such results can be also easily made based on some other metrics, of course with additional cost). For me, it is more interesting to provide a completely theoretical demonstration via recent advances on theory of over-parameterized neural network rather than explain these results via merely looking at an empirical metric.  \n\n(2) Although the paper provides some surprising findings, e.g., experiments on random labels, this paper fails to provide an explanation on such findings, which, in my opinion, is more interesting. However, it seems to me that the current metric or tool cannot achieve this goal.\n\n(3) One motivation of the new metric is the computational cost. Therefore, it would be better to demonstrate such an advantage over other metrices in the experiments. In addition, I am wondering whether the proposed metric is looser than other metrics (of course with higher computational cost), e.g., those in Fort et al., 2020 and Sankararamen et al., 2019. If so, it would be better to check whether such tightness will affect the empirical observations?    \n\nOverall, I am not excited about this paper, especially about its empirical results. For such reasons, I tend to weakly reject this paper. Since I am not an expert in this area, I am open to change my mind after reading other reviewers’ comments.", "extra_scores": {}, "extra_text": {}}, {"review_id": "efbPr-HdTES", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "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 studies a new notion of coherence to explain generalizability of neural networks. Coherence is defined as the degree to which the gradients w.r.t the data points are aligned with each other. The proposed metric to measure coherence improves upon existing definitions in the literature by ensuring a natural normalization such that the metric is always between 1 and the number of data points, thus having a direct interpretation of the number of data points whose gradients are aligned. \n\n## Pros: \n1. The experiments presented are pretty interesting and the paper does a good job of interpreting the results of the experiments. Studying the evolution of the coherence can be seen to be insightful in understanding generalizability.  \n2. The proposed definition of the metric enjoys a better computational complexity, making it possible to experiment on larger datasets. \n3. The paper also provides some general theory on coherence w.r.t to general sets, which is appreciated and manages to provide a better intuition to the readers. \n\n## Cons\n1. The general discussion in section 6. seems hand-wavy. Examples: 1)  \"One may imagine an uneasy equilibrium between these opposing tendencies leading to expansion\nand contraction in coherence. As soon as significant coherence builds up, it leads to an increase in the\neffective learning rate (higher relative gradient norm) leading to faster consumption\" - It's hard to say which one is the cause and which is the effect.  2) \"Since this creation happens even with random labels where there is nothing to learn (i.e.,\nno generalization), there is reason to believe that this creation is purely an optimization phenomenon.\" \n\n2. In general, although section 6 adds value to the paper, it does not seem to be the result of a principled analysis and seems more like a commentary on the plots. \n\n\n##  Overall score:\nI am giving this paper an overall score of 6. The paper is interesting and the ideas presented are sound. My reasons for not providing a stronger recommendation for acceptance are \n1. I am not convinced that there is one particular message that the paper finally arrives at. There is a new metric defined, and some general theory provided w.r.t this metric and experiments that study the evolution of the proposed metric. It would have been good to have a discussion how this particular set of experiments can better inform practice or theory of deep learning. \n2. The analysis is vague and hand-wavy. \n\nSome potential directions for improvement:\n1. Studying how the coherence changes w.r.t the complexity of the model. This can maybe performed using toy datasets and small architectures. What happens when layers are added, removed, made wider, and so on. \n2. Studying the evolution of coherence across different cross-validation folds to see if coherence can be used a way to tune hyper-parameters.\n3. Study of what happens when there are adverserial examples.", "extra_scores": {}, "extra_text": {}}, {"review_id": "cbAE_9lrkIR", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "In this work, the authors propose m-coherence as an replacement of sign stiffness / cosine stiffness / gradient confusion to measure the coherence of gradients in SGD training. Compared to existing measurements, m-coherence is more scalable and well-normalized. Using the m-coherence, the authors perform empirical studies on SGD optimizing a ResNet on ImageNet with natural or random label. The experiments show that for both real label and random label datasets,  the initial coherence is low, then increases as the training goes on, finally decreases as more and more data gets fitted.\n\n# Interesting empirical results.\n- I think the empirically similarity of gradient coherence for SGD learning real label and random label datasets is interesting. It suggests (1) the optimization of real label dataset and random label dataset is not totally different ---- they only differ in terms of fitting time; (2) we should look closer at the initial optimization of real label dataset though, since the \"coherence increasing\" phase in this case is super fast.\n\n- On the other hand, the observation is not too surprising since even real label dataset contains noise, and random label dataset is only an extreme case where the noise in the dataset is super large.\n\n- In sum, I personally do not think this pure finding, without an insightful analysis, is significant enough for an acceptance. \n\n# Misleading interpretation.\n\n- I think the writing of this paper is quite misleading. For example, in page 6 Real Labels paragraph, it claims for real labels, the initial coherence is very high? But then in page 7 Early Training paragraph, it instead claims the initial coherence is not very high if you look closer. Personally I find it misleading to make a claim first but then correct the claim with another one which is totally contradictory to the formal. I think it is better to explicitly point out the claims are for different scenarios, i.e., in large timescale/small timescale.\n\n- Moreover, in page 8, the last part, Separation of Generalization and Optimization. The statements are super vague and not supported by experiments/theory. I do not understand why these arguments can make sense. I strongly encourage the authors to backup their statements with evidences.\n\n\n# Experiments\n- The authors claim several benefits of the proposed m-coherence compared with existing measurements like sign stiffness / cosine stiffness / gradient confusion. Indeed in terms of computation, m-coherence can be cheaper. But it is not clear whether or not sign stiffness / cosine stiffness / gradient confusion agrees with m-coherence empirically. In my opinion there should be some ablation studies to check the trend of gradient coherence with other measurements.\n\n- Looking at Fig. 1, I find the plots are not consistent in format. For example, in the third row, the first two plots have test m-coherence, while the others do not have this; in the second row, the last plots misses a training accuracy curve; and so on. Please explain why.\n\n# Minors\n\n- Page 3, below Eq. (2). I guess it should be a \"lower bound\" instead of \"upper bound\"? Since in Eq. (2) there is a negative sign.\n\n- Page 2, second paragraph last sentence. I am not sure about this claim. If the loss functions are not linear and gradient directions change every iterates (even for the same data point), the claim can be wrong. Because even at every iteration the gradients are orthogonal, abandoning one data point does not imply GD/SGD cannot optimize the direction along the gradient on this data, since other data points can contribute this direction afterwords.\n\n\n\n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The average score of the reviewers is 6. There are various pros and cons pointed out by the reviewers. Unfortunately, the AC and SAC found that the merit could be outweighed by the limitations of the work, and would like to recommend rejection. For example, a central concern raised by the reviewers is the lack of theoretical justification---the measurement that the paper proposes does seem to show an interesting empirical phenomenon, but as a few reviewers pointed out, it's unclear how the interesting phenomenon directly links to the generalization mechanism, and it's unclear whether the new interesting phenomenon is caused by the change of measurement of the gradient coherence or it is something fundamental. The arguments related to these are found to be generally vague and hand-wavey by the reviewers.  The AC would like to encourage the authors to address the reviewers' concerns thoroughly, especially those regarding the difference and similarity with prior works, the interpretation, and limitations of the results, etc., and consider adding more rigorous analysis to justify the proposed measurement of gradient alignment.  
Decision: Reject