Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: This paper studies two objects that quantify the optimization trajectory: the Hessian of the training loss (H) that describes the curvature of the loss surface, and the covariance of gradients that quantifies noise induced by noisy estimate of the full-batch gradient. 

The authors predict and demonstrate that learning rate and batch size determine H and K and demonstrate that both large learning rate and small batch size results in two effects on K and H along the trajectory: (1) variance reduction and (2) pre-conditioning. These effects are observed after the break-even point. The further verified these predictions on BN networks.

Comments:

Understanding the optimization trajectory is an important topic and this work is one step towards better understanding. There are many questions I hope the authors could clarify: 

- the concept of break even point, which justify whether the minima is stable or not, is also presented in Wu et al, 2018, including the proof. In the introduction of equation 1, the break even point concept seems to be novel in the context of learning trajectory. What is the difference with Wu et al, 2018? Does this break even point appear only once during training?

- What is the practical usage for identifying the break-even point or stable/unstable of the optimizer? Does reaching the unstable phase of SGD earlier by large learning rate/small batch size mean better performance?

- It seems the author does not apply learning rate decay for all experiments. What is the connection with learning rate decay? As we often see the training loss and validation error decreases significantly during training in step based learning rate schedule, what is their corresponding change of \lambda_H^1 and \lambda_K^1?

- The authors did not mention whether momentum is used or not during training, which is commonly used in training neural nets. How would momentum affect the conjectures?

- Regarding to conjecture 1 which states that “larger” learning rate yields lower \lamda_H^1 and \lamda_K^1, is there a limit for the range of learning rate? If we use learning rate 10, the training may not even converge. The experiments only verifies three learning rate with a maximum value 0.1, which does not cover “large” learning rate.

- Also as small batch size naturally results in more iterations than large batch given the same number of epochs. Comparing small batch and large batch may need to take this into account. By reaching the break-even-point “early”, does it mean less number of epochs? I would like to see the comparison in terms of iterations rather than epochs. 

- In section 4.1, the definition of \alpha* is not clear. It was noted in Figure 2 as the width of the loss surface and is defined to be the minimum step size along the adjacent iterate direction to have 20% loss increase. What is the unit of t here, is it a batch or epoch?
How exactly is \alpha calculated? Due to the scale invariance [1,2], this \alpha is not necessarily the true `width` of the loss surface as it could be influenced by the weight norm.
Why do different learning rates reach a similar \alpha? It would be better to mark the starting point of the trajectory and the ending point of trajectory.

- The illustration of Figure 1a is very unclearer. What is the x-axis and y-axis? Where is exactly the break-even point? It would be helpful to mark the starting and ending point of the trajectory. Also it would be helpful to have the values marked in the contours or make a separate value bar.


- The authors studied whether the conjectures hold for BN networks in section 4.3. They only verified learning rate but not batch size. Does the batch size part still hold? It is known that BN requires larger batch size to work well, which may contradict with the conjecture that smaller batch size works better.


Minor:
- I was confused by the Figure 3 where different hyperparameters has different values at epoch 0. Does epoch 0 means the first epoch? It would be clear to have the same starting point and make epoch 0 as the initialization point.  

- The experiments of DenseNet on ImageNet seems incomplete as it is only trained for 10 epochs. What is the top-1 error on the validation set?

[1] https://arxiv.org/abs/1703.04933 
[2] https://arxiv.org/abs/1712.09913


-----update after rebuttal----------

After reading the response, I think most of my questions are properly answered and corresponding changes are made in the revision. I  changed my score to weak accept. I would hope the authors could further improve the paper by well organizing the additional experiments and findings. Too much experiment variation settings make the paper not easy to follow. I hope the authors could make it clear about the practical benefits of identifying the existence of break even point with common experiments settings, e.g., nonzero momentum, weight decay and step based learning rate decay. In the new provided experiments about learning rate decay, I did not see the normal abrupt change of validation accuracy. More analysis about whether learning rate decay helps reaching break-even point would be great. 
review_title: Official Blind Review #3

final_score: rating: 8: Accept
review_content: The authors demonstrate that, during training, there is a point during the early phase of training that leads stochastic gradient descent (SGD) to a point where the covariance of the gradients (K) has a lower spectral norm (smaller first eigenvalue) and improved conditioning in K and the Hessian of the training loss (H).

The authors experiments seem to verify that learning rate and batch size do play a part in the spectral norm of K and the conditioning of K. My one issue is that, while effects on K produced by higher learning rates are supposed to be "good", the authors do not directly relate this back to model performance. From my years of experience training neural networks, I have seen many scenarios in which higher learning rates result in worse performance, even after reducing the learning rate. Can this be related back to the author's claims? Under what conditions does a higher learning rate lead to these effects on K and H and will it always lead to better model performance?


Other comments:
In definitions, it says that the eigenvalue of matrix A is \lambda_A^i, however, later in the 4th part of the assumptions, the spectral norm of H is referred to as \lambda_1^H. Is there a difference here? Typo?

The last part of the definitions where \Phi(\tau) is introduced should have a formal definition for \Phi(\tau) as \Phi is initially does not take any parameter \tau.

In section 4.1, "further growth of \lambda_K^1 K does not translate into an increase of \lambda_K^1" \lambda_K^1 is repeated. Typo?

** After author response **
Changing from weak accept to accept.

The authors have addressed my concerns about the paper.
review_title: Official Blind Review #2

final_score: rating: 6: Weak Accept
review_content: 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
review_title: Official Blind Review #1

Meta-review: This is an interesting study analyzing learning trajectories and their dependence on hyperparameters, important for better understanding of learning in deep neural networks.  All reviewers agree that the paper has a useful message to the ICLR community, and appreciate changes made by the authors in response to the initial reviews.
Decision: Accept (Spotlight)