Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper proposed a supposed novel way of using the Hessian-vector product as a momentum vector instead of the traditional momentum vector. The gradient is computed as a linear combination of the past gradient, which is also supposedly clipped, and the current gradient.
strengths_and_weaknesses: Strengths:
1. Used the Hessian vector product is computed efficiently.
Weaknesses:
1. There is no convergence guarantee for the current method
2. The computation expense is higher for the proposed approach, but the improvement in accuracy is limited. Especially in the case of Imagenet.
3. The authors mention that the level of noise is limited in the conclusion section. However, no evidence of this is provided.
4. Upon closer inspection in the appendix material, the results do no show improvement to 

Editorial:
1. The paper is very hard to read. A lot of the derivations and lemmas can be moved to the supplementary section.
2. The presentation needs improvement. Give more importance to the convergence proofs and the results. All of the derivations seem to reduce the credibility of the paper.

questions: 1. Why is $z_t$ appearing everywhere ? If the gradients are not computed with respect to $z_t$, it is recommended to remove it.
2. What is G-Lipschitz ? The formulation in equation (6) is very different from the one the reviewer has seen. Can the authors share a reference ?
3. What is L ? Is this the constant term of the Lipschitz continuity equation ? If so, how is it determined ?
Editorial:
4. Why are only equations 1-6 numbered ?
limitations: 1. The paper does not identify any convergence criterias.
2. It is not performing better than state-of-the-art. It might seem in Figure 1(a) and (b) that they might reach maximum accuracy, but the sharp increase is also indicative of overtraining 
3. Equation with the gradient update (please use number for the main equations) can literally be boiled down to a linear combination of the past gradient and the current gradient.  $\hat{g}_t = (1-\alpha)\hat{g}_{t-1} + \alpha g_t$
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper introduces a Hessian-based correction term in SGD with momentum to reach $\epsilon$ critical point in $\mathcal{O}(\epsilon^{-3})$ stochastic gradient and Hessian-vector product computations. The authors extend the benefit of the correction term to normalized SGD and adaptive algorithms. Finally, they showcase the benefits of their proposed algorithm with an experimental study on CIFAR-10, ImageNet, and neural machine translation.
strengths_and_weaknesses: The major strength of the work is in the simplicity of the correction term introduced in momentum, which achieves the same complexity to reach an $\epsilon$-critical point, compared to Arjevani et al. [2021], which requires a larger batch size (and a more complicated Hessian vector product calls). Moreover, the authors can show better performance of SGDHess compared to SGD in various vision and NLP settings. The theorem statements are clearly written and easy to understand.


The major issue with this is that the global smoothness and second-order smoothness constants may be very large for the theoretical bounds to turn vacuous for the deep neural networks. Moreover, there is a mismatch between the theoretical claims and the experimental results as pointed out later.
questions: Here are my major questions:
1. It would be great to have a discussion on why Arjevani et al. [2021] require large batch sizes and how the authors can tackle the necessity with momentum. The algorithm of Arjevani et al. [2021] (algorithm 1) uses K Hessian vector products (similar to the one being used in the current paper) per gradient step to reduce the variance. However, the algorithm of Arjevani et al. uses different samples for the K Hessian vector products, while the authors can get away with a single Hessian vector product update in the momentum. Why?
 

2. There seems to be a mismatch between the theoretical claims and the experimental results. The theoretical claims show that SGDHess can reach a stationary point with $\mathcal{O}(\epsilon^{-3})$  stochastic gradient and Hessian calls, compared to $\mathcal{O}(\epsilon^{-4})$ stochastic calls for SGD. However, the experiments talk about achieving better generalization with SGDHess. 

a) How is the result connected to generalization? 

b) Isn't it better to compare the loss behavior for the two algorithms, and show faster convergence for SGDHess? 

3. ResNet models use the ReLU activation function and maximum pooling layers. Hence, the global smoothness and the second-order smoothness are undefined, which are necessary for the theoretical claims. One suggestion to modify the experiments will be to use smooth activation functions like GeLU and tanh, and average pooling layers.


limitations: The authors have jotted down one of the main limitations of their work, which is assuming that the function is Lipschitz. However, it would be great to also include a discussion on the viability of the other assumptions, which are L-smoothness (Eq. 2), second-order smoothness (Eq. 6), and the upper bound on the variance of the gradient and the Hessian (Eqs. 3 and 4). Since one of the major ambitions of the paper is to show the benefits of the proposed algorithm in neural networks, it would be great to see some ablations for these assumptions in the deep learning architectures.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper derives an improved momentum SGD method based on Hessian-vector products. It achieves optimal theorical rates on non-convex problems, and high-accuracy performance on deep learning tasks. 
strengths_and_weaknesses: The strength of this paper is to introduce a correction to reduce the bias in the classical momentum SGD method (section 2). An algorithm SGDHess is proposed for this purpose, with theorical convergence analysis. Although there is a gap between the theorical version of the algorithm, and its practical version (i.e. return hat x in theory, and x_T in practice), numerical results are convincing about its improved accuracy compared to momentum SGD. One weakness is that I do not fully understand why it works better in practice, could this be explained better (see questions below)?
questions: The introduction says that the optimal rate of convergence is T=O(eps^-3), however, the rate of Theorem 1 seems to be faster than that (eps = logT/T^(2/3)), could you explain more on this optimality?

A discussion on the related work by Cutkosky,Mehta 2022 (Momentum Improves Normalized SGD) is needed I think in Section 3, which seems to be too short. 

What is the practical performance of Algorithm 3? Some discussions are welcome. What is tilde O on line 196?

What is the batchsize used in the experiment (section 5.1 setup)? It is not clear. A numerical comparison or at least some more discussions with the method Cutkosky et al. 2020  (Momentum-based variance reduction in non-convex sgd) is needed in Section 5 to support the claim in the introduction that recursive variance reduction requires large batches, as numerical results in that paper seem to work well on CIFAR.

Why the top 1 test accuracy, bleu score are higher with SGDHess compared to SGD in Table 1 and 2? Is that due to a higher training accuracy or some form of implicit regulization?


limitations: NA
review_title: null

Meta-review: metareview: This papers develops a new efficient second order method for non-convex optimization. Reviewers seemed to agree that the paper offers a significant over the prior work of Arjevani, Yossi, et al "Second-order information in non-convex stochastic optimization: Power and limitations" by requiring a single Hessian vector product update in the momentum update, and therefore would be of interest to the NeurIPS audience. 
confidence: Certain
Decision: Accept