Understanding the optimization trajectory is critical for understanding training of deep neural networks. We show how the hyperparameters of stochastic gradient descent influence the covariance of the gradients (K) and the Hessian of the training loss (H) along the trajectory. Based on a theoretical model, we conjecture that using a high learning rate or a small batch size leads SGD to regions of loss landscape, typically early during training, characterized by (1) reduced spectral norm of K, and (2) improved conditioning of K and H. We refer to the point on the training trajectory after which these effects hold as the break-even point. We demonstrate these effects empirically for a range of deep neural networks applied to different tasks. Finally, we apply our analysis to networks with batch normalization (BN) layers and find that it is necessary to use a higher learning rate to improve loss surface conditioning compared to a network without BN layers.
This work analyzes the optimization of deep neural networks from the point of view of the different learning trajectories obtained during different learning settings as brought about by different hyperparameters in optimization. Specifically, the authors consider how the batch size (S) and the step-size (eta) hyper-parameters modify the learning trajectory. The authors conduct their analysis for networks with and without BatchNorm. 
To get a quantitative understanding of the different trajectories of the optimization landscape the authors monitor and analyze the 
A.  Hessian of the network with respect to the parameters 
B. The covariance matrix of the per-sample gradients 
The majority of the work focuses on monitoring A and B for various hyper-parameter regimes. 
The authors discover a nice and clear trend, the leading eigenvalues of H (the Hessian) and K (per sample gradient covariance) are 
1. Heavily correlated to each other (Figure.2 left) 
2. Positively correlated with batch size (S) (Figures 3-5)
3. Negatively correlated with step-size (eta) (Figures 3-5)
The 3 trends presented empirically all originate and qualitatively agree very well with equation (1) of the paper that describes stability regions in training.  Equation (1) directly prescribes the maximum allowed eigenvalue for the Hessian matrix H for a given a learning rate, and batch-size to ensure stability. For equation (1) to hold, the authors make  the assumption that H and K share a leading eigenvector direction (this assumption is partially corroborated on the CIFAR10 dataset). The empirical analysis presented in the paper analyzes training on the CIFAR10, ImageNet, IMDB, and the MNLI datasets and uses a variety of common network architectures to evaluate the empirical claims. In general, I am quite happy with the breadth and depth of the experimental results presented in the paper! 
The paper makes a few observations in addition to trends 1-3, It argues that BatchNorm networks need a large learning rate to exhibit smaller dependence on the subspace of the leading eigenvectors of K,  and that the networks reach a breaking point early in training where the leading eigenvalues of H and K are chosen by the trajectory.
Overall the paper is well written and the numerous experimental results are quite impressive. Nonetheless I have a few problems that are discouraging me from fully accepting this paper, so I am currently borderline accepting this paper.
The following problems should be addressed:
i. The theoretical results in the paper are very similar to the results given in Wu et al. (as mentioned in the main body and Appendix A). Moreover, the modified proofs presented in the appendix are not fully explained and are difficult to follow so I do not find them rigorous. It also seems like some of the empirical analysis is also presented in Wu et al.
ii. As stated, Conjecture 2 is not empirically supported in the paper. Currently, Conjecture 2 proposes that for  training with smaller batches or larger learning rates, the reciprocal of the ''conditioning number'' ( least POSITIVE eigenvalue / leading eigenvalue)  reaches a larger maximum value during training. Instead the authors "estimate" the least positive eigenvalue by the trace of the matrix which is very much a different notion than the least positive eigenvalue and also displays a different behavior.
It seems maybe measuring the trace as an un-normalized quantity for the average eigenvalue is more suitable but that is different from the least positive eigenvalue. Perhaps of the same flavor would be a statement on the stable rank of the matrices in question.
iii. Figure 1 (left) is quite confusing. I hope the authors can help clarify the heatmap shown along with the trajectories. The caption mentions that the colors signify the value of the leading eigenvalue of K.  First, since this is an explicit quantity can the authors provide a value range for the heatmap? Second, and more importantly, how is this quantity, which depends on K, can be computed for all the points in the 2D grid of UMAP to form this heat map? Recall K is a quantity that is computed for a given parameterization value and fixed number of mini-batch examples. 
iv. Lack of clarity and rigor for the eigenvalue approximation: In appendix B the authors discuss approximating the eigenvalues of K and H, I think it is okay to develop numerically efficient approximations to the quantities in question but the presentation is not very intuitive nor rigorous. In the first paragraph the authors mention that since H is ill conditioned, a small subset of the training examples gives a good approximation to the Hessian, can the authors elaborate on this statement? 
Other more minor comments:
Even though the default step size and batches are mentioned in appendix D it could be nice to mention them in the figures that they are presented in.
Page 7 Fig 5b | The labels of the figures should be adjusted so that they do not overlap with the adjacent figures.
Minor typos/grammar:
page 1 caption of figure 1 | vertical line marks -> the vertical line marks 
page 3 in definitions paragraph | let us denote loss -> let us denote the loss
page 3 3rd assumption | training trajectory -> the training trajectory
page 3, 3rd assumption | escape region-> escape a region
page 7, other experiments paragraph | depend -> depends,  possibly?
page 7, Figure 5 (b) Middle |  lambda_k to lambda_k^1