An open question in the Deep Learning community is why neural networks trained with Gradient Descent generalize well on real datasets even though they are capable of fitting random data. We propose an approach to answering this question based on a hypothesis about the dynamics of gradient descent that we call Coherent Gradients: Gradients from similar examples are similar and so the overall gradient is stronger in certain directions where these reinforce each other. Thus changes to the network parameters during training are biased towards those that (locally) simultaneously benefit many examples when such similarity exists. We support this hypothesis with heuristic arguments and perturbative experiments and outline how this can explain several common empirical observations about Deep Learning. Furthermore, our analysis is not just descriptive, but prescriptive. It suggests a natural modification to gradient descent that can greatly reduce overfitting.
The paper studies the link between alignment of the gradients computed on different examples, and generalization of deep neural networks. The paper tackles an important research question, is very clearly written, and proposes an insightful metric. In particular, through the lenses of the metric it is possible to understand better the learning dynamics on random labels. However, the submission seems to have limited novelty, based on which I am leaning towards rejecting the paper.
Detailed comments
1. The prior and concurrent work is not discussed sufficiently:
a) The novelty of the "Coherent Gradients hypothesis" is not clear to me. First, the empirical fact that some examples are easier to learn than others in training of deep networks was the key focus of [5]. 
Hence, "Coherent Graident Hypothesis" should be mostly considered an explanation for why simple examples are/simple function are learned first. "Coherent Gradient Hypothesis" proposes that the key mechanism behind this phenomena is that simple examples/functions have co-aligned gradients and hence a larger "effective" learning rate. However, there are already quite convincing and closely related hypotheses. For example, the spectral bias interpretation of deep networks [2] and (2) suggests the same view actually. Just expressed in a different formalism, but can be also casted as having a higher effective learning rate for the strongest modes. Similarly, [3] proposes that SGD learns functions of increased complexity. A detailed comparison between these hypotheses is needed.
b) "Gradient coherence" metric is very closely related to Stiffness studied in [1] (01.2019 on arXiv). [1] studies the cosine (or sign) between gradients coming from different examples, and reach quite similar conclusions. It is also worth noting that [6, 7] propose and study a very similar metric as well. While arXiv submissions is not consider prior work, these three preprints should be discussed in detail in the submission.
c) It should be also remarked that "Coherent Gradient hypothesis" is to some extend folk knowledge. In particular, it is quite well known and also brought to the attention of the deep learning community that in linear regression strongest modes of the datasets as learned first when training using GD (see for instance [4]), which causally speaking stems directly from gradient coherence; these modes correspond to the largest eigenvalues of the (constant) Hessian. To make it more precise: consider that GD solving linear regression can be seen as having higher "effective" learning rates along the strongest modes in the dataset. 
2. Experiments on random labels and restricting gradient norms are interesting. However, [5] should be cited. They experimented with regularization impact on memorization, which due to the addition of noise, probably also supresses weak gradients. 
3. Experiments on MNIST do not feel adequate. While I do not doubt the validity of the experimental results, the paper should include results on another dataset; ideally from other domain than vision.
4. Plots in Figure 4 are too small to read. I would recommend moving half of them to the Supplement?
5. "Understanding why solutions of the optimization problem on the training sample carry over to the population at large" - Not sure what do you mean here. Could you please clarify?
6. "Furthermore, while SGD is critical for computational speed, from our experiments and others (Keskar et al., 2016; Wu et al., 2017; Zhang et al., 2017) it appears not to be necessary.". Please note there is very little work on training with GD large models. Also, citing in this context Keskar is misleading. Wasn't the whole point of Keskar to show why large batch size training overfits? Finally, there are many papers on studying the role of learning rate and batch size in generalization (not computational speed). I think this sentence should be rewritten to clarify what is the experimental data that GD is "sufficient", and SGD is just needed for "computational speed".
References
[1] Stanislav Fort et al, Stiffness: A New Perspective on Generalization in Neural Networks, https://arxiv.org/abs/1901.09491
[2] Rahaman et al, On the Spectral Bias of Neural Networks, https://arxiv.org/abs/1806.08734
[3] Nakkiran et al, SGD on Neural Networks Learns Functions of Increasing Complexity, https://arxiv.org/abs/1905.11604
[4] Goh, Why Momentum Really Works, https://distill.pub/2017/momentum/
[5] Arpit et al, A Closer Look at Memorization in Deep Networks, https://arxiv.org/abs/1706.05394
[6] He and Su, The Local Elasticity of Neural Networks, https://arxiv.org/abs/1910.06943
[7] Sankararaman, The Impact of Neural Network Overparameterization on Gradient Confusion and Stochastic Gradient Descent, https://arxiv.org/abs/1904.06963