Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The authors present a modification of a method of Becker and Lecun (1989) using a diagonal Hessian approximation to improve the convergence of stochastic gradient descent schemes.  The scheme takes about the same amount of time as standard back-propagation, unlike some other approximation schemes.  Based on this modified Hessian approximation, they introduce the AdaHessian method, which compares favorably to other standard optimizers on a set of test problems.
strength_and_weaknesses: To the extent that I can read the figures, the approximation scheme does indeed seem to lead to better convergence results than competitors on the test problems.  The modification compared to B&L 89 is not large, but the authors point out that it makes a big difference in the convergence of the final method.

There is no new theory behind this, or at least none given in the paper.  The verification of the quality is purely empirical.  It would be interesting if there was a theoretical argument for why the modification makes as much difference as it does.
clarity,_quality,_novelty_and_reproducibility: The written presentation is quite clear.  There is not a lot of novelty here, but the improvement is clear; also (though the authors don't say much about it), the 1989 Becker-Lecun paper does not integrate with the Adam ideas, so there is a new combination of the Hessian approximation and modern SGD-style algorithms.

As a minor but key complaint: between the small fonts and the use of many colored lines, I found the plots very difficult to read.  This is surely made more difficult by my poor color vision, and I understand the constraints of a page limit -- but I would have been a much happier reader with something a little larger!
summary_of_the_review: With a small-but-critical change to a 1989 scaling technique, together with adopting modern SGD framework, the authors introduce a new SGD-style optimizer for NN training that includes second-order information "for cheap" and seems to lead to better training performance (in terms of test accuracy vs time) than natural competitors.  I am a fan of "not a big change, but the right change" work, and would like to see this published.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This study proposes HesScale, which can quickly compute the diagonal elements of loss Hessian in deep neural networks by back-propagating only the diagonal component of Hessian w.r.t. activation. For an MLP, it is shown that HesScale estimates a more accurate diagonal Hessian at a lower computational cost than existing methods such as AdaHessian. This study also proposes AdaHesScale, which incorporates the approximate diagonal Hessian calculated by HesScale into an Adam-style update rule. The experiment results show that AdaHesScale (and its variant) can achieve a certain test accuracy faster than SGD and Adam in training CNNs and MLPs for image classification tasks.

strength_and_weaknesses: Strengths
- The computational cost, training convergence, and sensitivity to hyperparameters of several diagonal second-order optimization and adaptive gradient methods are compared. (The validity of the comparison is questionable, though.)

Weaknesses
- The proposed HesScale appears to be a very crude approximation without justification.
    - HesScale ignores the off-diagonal elements of Hessian w.r.t. activation, but no theoretical or intuitive justification for this has been provided. Although the experimental results shown (Figure 1) indicate that HesScale has a relatively small error, it is unclear whether this is true in other tasks.
    - The recursive computation of the Hessian is already discussed by Botev et al. (2017) (https://arxiv.org/pdf/1706.03662.pdf) and Dangel et al. (2020) (https://openreview.net/forum?id=BJlrF24twB), where they “back-propagate” the Hessian w.r.t. activation including the off-diagonal elements.  
- The validity of the comparison is questionable.
    - It is unfair to compare only the diagonal elements of K-FAC in Figure 1. K-FAC approximates the layer-wise Fisher matrix, including off-diagonal elements, by sacrificing the accuracy of the diagonal elements. Therefore, the error of the layer-wise Fisher approximation should be compared. If only the diagonal elements matter, then a computational approach that only calculates the diagonal elements of the K-FAC matrix should be used to compare the computing time. 
    - Although diag(H) is used as the grand truth, H (Hessian) is not necessarily a valuable measure of information for second-order optimization in deep learning because the generalized Gauss-Newton and Fisher matrix is preferred in nonconvex optimization (e.g., https://www.cs.toronto.edu/~jmartens/docs/Deep_HessianFree.pdf).  
    - Similarly, the error with diag(H) is not a good indicator because what second-order optimization uses is the inverse of the (damped) second-order information: H_inv = (H + dI)^{-1}, where d > 0 is the damping value corresponding to \epsilon in Algorithm 2. Depending on the choice of d (it could be 1e-1 to 1e-4 in practice https://arxiv.org/pdf/1806.03884.pdf), the importance of the accuracy of estimating diag(H) will be limited.
    - Based on the above, I suggest reviewing the comparison approaches.
- The advantage of AdaHesScale over Adam is unclear.
    - AdaHesScale (Algorithm 2) uses the 'square root of' the inverse of the approximate diagonal Hessian as the preconditioner of the gradient, which does not correspond to the Newton-Raphson method. While the motivation for this study comes from improving approximation accuracy (and computational speed) of the Newton-Raphson method in large settings, it is unclear how much of the second-order information is utilized in AdaHesScale since it takes an update rule almost identical to that of Adam. 
    - According to the leaderboard for the CIFAR-100 classification task with All-CNN-C in DeepOBS (https://deepobs.github.io/leaderboardP6.html), Adam achieves a test accuracy of >61% at about 350 epochs, which is much better than Adam (47%) and AdaHesScale (53%) in Figure 4(b). Furthermore, training with momentum SGD achieves >66%. Even if it is difficult to reproduce the leaderboard results perfectly, I do not believe it is reasonable to use a result about 12% lower than the existing results as a baseline for Adam.
clarity,_quality,_novelty_and_reproducibility: The motivation for the study, the proposed algorithm, and the details of the experiments are clearly described. However, I believe the comparison method with existing methods (errors, computation time, training speed) is not appropriate. 

summary_of_the_review: While the computation of fast and accurate second-order information is indeed an important topic, questions remain about the validity of the approximations in the proposed HesScale and AdaHesScale, their superiority over existing methods, and the generality of the proposed method’s effectiveness. The quality of this study could be improved by more profound validation of the approximations used in HesScale (ignoring non-diagonal elements of the back-propagated Hessian w.r.t. activation) and more appropriate comparisons with existing second-order methods.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The authors present a method for approximating the diagonal of the Hessian of neural networks in order to use this approximate curvature information during training.
The approximation proposed by the authors is based on considering the exact symbolic derivative for the Hessian diagonal entries and then dropping terms as necessary during backprop in order to make the computation fast (constant factor of the function evaluation like standard backprop gradient).
The authors analyze the accuracy of their Hessian approximation compared to other baseline methods for approximating curvature information and are able to demonstrate that their approximation has much smaller approximation error in practice for some small toy networks (3 layeers with 16 unites, 1 layer with 512 both with tiny input size).
The authors also present some experimental results demonstrating the usefulness of their Hessian diagonal optimization in terms of reaching high test set accuracy faster.
strength_and_weaknesses: Strengths:
- Interesting approach because it utilizes an exact symbolic differentiation approach in a computationally efficient manner
- The authors present convergence results over wall-clock time demonstrating that their approximation is in principle computationally feasible in practice

Weaknesses:
- The background section is potentially a bit extensive on backgroud about block structure that is not necessary for the method proposed in the paper
- It would be interesting to know whether there can be theoretical bounds on the error made from dropping the terms in the symbolic derivative
- Tiny toy example network used for accuracy analysis (3 layers with 16 units, 1 layer with 512 units), not even something like MNIST but just random data examples so it is unclear how the accuracy statements hold in more realistic settings
- Increasing the number of outputs is not a practical application for increasing parameter size since the number of classes does not typically change, furthermore this seems biased as the last layer computation of the Hessian is exact and different from the others. So cost scaling should be done by increasing number of layers and layer width (and much larger input space should be used for the examples)
- The experimental section could be improved by presenting the results in a more structured way also presenting results numerically in tables, the scaling of the plot axes could be misleading
- Not sure if the hyperparam tuning for the different optimizers was sufficient to be convincing
- Need to better motivate the method compared to quasi-Newton type methods for estimating a Hessian diagonal (especially in a full-batch setting)
- Need to motivate the method in the context of nonconvex stochastic estimation or some other application of machine learning. In the end I am not sure sure what the relevance of curvature information is for machine learning. In theory curvature is useful for different contexts, it can be useful to escape saddle point quicker, but that's not how it seems to be used in this paper. The other purpose can be to converge to a an optimum faster when already in a convex region around the optimum. But getting close to an optimum of an empirical loss is not always beneficial for generalization. The authors show test set plots which is unconventional, but maybe they can be viewed like validation set plots. It would have been interesting as well to see how the training set loss behaves to see what the generalization gap is for these applications.

*Questions and remarks*:
- How does this related to edge pushing algorithm (see https://arxiv.org/pdf/2007.15040.pdf)?
- What is the quality of the Hessian approximation when computed on a mini-batch?
- Not sure about beta_1 search space of just two choices, that seems limited?
- Why is the standard error for the CIFAR-10 3C3D AdaHessian run so large?
- Color codes for different optimizers should be identical between plots (Figure 3 a) has AdaHessian in pink and b) has Adam in pink)
- Why does Figure 5 report test loss while Figure 3 and 4 report test accuracy?
- Typo: "sensitivty"

clarity,_quality,_novelty_and_reproducibility: Clarity: The paper is clearly written and understandable

Quality: The experiments do not reflect realistic use cases in machine learning which in combination with the insufficient motivation of the method for the machine learning setting makes it hard to believ
e that the method as such is useful in practice. The method is potentially an interesting idea theoretically but the paper does not attemt a theoretical analysis.

Novelty: I am not familiar enough with the literature but the idea seems so simple it would be surprising if it had not been explored elsewhere. Nonetheless, assuming it is novel to try this it is an orig
inal idea to pursue.

Reproducibility: The experiments should be easy enough to reproduce based on the described algorithm details in the paper.
summary_of_the_review: I do not recommend to accept the paper as the paper does not have either realistic experiments that are meaningful to the machine learning practitioner nor does it present a theoretical analysis of approximation bounds and resulting possible statements about optimizer convergence for the proposed Hessian approximation
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper proposes an efficient heuristic approximation to compute the diagonal of the Hessian matrix in neural nets, and empirically shows that it is significantly more accurate than other existing deterministic and stochastic approximations.  The paper then goes on to propose a second-order optimization method that uses these estimated hessian values, and shows on experimental results that the method is competitive and sometimes better than other standard optimizers (SGD, ADAM) in computer vision tasks. 
strength_and_weaknesses: Strength:  A principled and inexpensive approximate second-order optimization method for learning neural nets would be very impactful -- and the paper is taking a shot at this problem.  The method is a small modification of an existing proposal by Becker and Lecun, that observes that the diagonal of the Hessian of the last layer can be computed exactly (rather than approximately) for common loss functions,  but this seems to make a very significant difference in the approximation error (in experiments).  The paper then uses this Hessiagn-diagonal estimator for optimization. Experimental results with image classification show that the method is competitive with other optimizers, and shows the best performance on some if the instances. 

Weaknesses: 
1) The paper goes into a lot of depth describing the hessian-diagonal approximation, but the actual optimization method is just a paragraph + an algorithm.  Some additional explanation of steps / parameters would make it more readable. 

2) I was struck by the impressive results in for HessScale in Figure 1,  but I have some questions on them.  a) Do you have any intuition, insight or analysis on how can the method do so much better than other alternatives (order of 10-20x reduction in error w.r.t best other methods).   Are the discarded off-diagonal terms somehow conveniently cancelling for random problems, or what's going on?  Is the setting of random neural nets on random inputs somehow fortuitous for this evaluation, or does this improvement in Hessian approximation also hold for realistic neural nets in the middle of the training? 

3) What limitations are there on when the method can be used for more general neural nets? E.g. can it be applied with dropout, batch-norm layers, or for other architectures (ResNets, RNNs, LSTMs, transformer-style architectures)?  What common losses are not supported? 

4) Evaluation.  It would be great to include some examples from other (non-vision) domains and with different achitectures -- e.g. natural language, tabular data, recommendation, maybe speech.  It seems that there are differences in what's the default optimizer in each community, and it could be motivated by artifacts of the structure of the problem / architectures commonly used. 

5) For second order methods ideally it would be better to compute the diagonal of the inverse Hessian -- rather than inverting the diagonal of the Hessian? Is that something that can be computed efficiently?  Having access to Hessian-vector products it is possible to estimate the diagonal of the inverse -- using Hutchinson's like methods,  or alternatives, like (this is in context of Gaussian graphical models, but it's essentially an estimator for the diagonal of the inverse of the matrix): 
Wilsky, Malioutov, Johnson, "GMRF Variance Approximation using Spliced Wavelet Bases." 2007 IEEE ICASSP, 2007. 

6) For AdaHessScaleGCN -- it seems that well into convergence the optimizer occasionally has some large instabilities with large oscillations (e.g. top-left and in Figure 1, and some runs in Fig 6).  Why does this happen, and can it be improved somehow? 


clarity,_quality,_novelty_and_reproducibility: The paper is clearly written, experimental results are well done (but it'd be great to add examples from other domains).  There is limited  insight or analysis into why the proposed approximation works as well as it does and discussion of where it may work less well.  
summary_of_the_review: The paper proposed an improved approximate estimator of the diagonal of the Hessian for neural networks, and uses it to propose a second-order method. Experimental results are done well,  but could be more comprehensive.  It'd be very helpful if the authors made an attempt at gaining insight into why the method works as well as it does (and whether there are settings where it works less well) .
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper proposes a method to approximate the diagonal of Hessians, based on a simple modification of the method of Becker and Lecun (1989).

Strengths:
- The method is simple
- It seems to work well on MNIST and CIFAR

Weaknesses:
- The paper is overselling its contribution: It is not mentioned until Section 3 that the proposed method is a simple modification of Becker and Lecun (1989)
- No theoretical guarantees
- Experiments only on MNIST and CIFAR, on feedforward and CNN networks: for a strictly empirical paper, this is too limited
- Does not perform better than ADAM
- Figure 1 is misleading, as there is no evidence that approximating the Hessian diagonal well is useful for optimization

Overall, we agree with the 2 reviewers who recommended rejection. The paper does not meet the bar for publication at ICLR, in its current state.
justification_for_why_not_higher_score: Limited evaluation, does not perform better than ADAM, contribution is oversold
Decision: Reject