Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The authors propose a regularizer for training DNNs - specifically adding the trace of the Hessian w.r.t. the parameters of the model.
They present two efficient stochastic estimators of the trace, based on the Hutchinson method and their own extension to it, specific to NNs. 
The authors also provide a motivation of the regularizer through a known generalization bound and through the perspective of dynamical systems stability. 
In three experiments - on CIFAR10, CIFAR100 and Wiki-Text they present results suggesting that the proposed method is performing better on average than other techniques. 

main_review: The paper starts well, with clear and simple goal - to introduce a new regualrizer. It motivates it through an existing generalization bound on linear models. Although, this bound does not translate to DNN models, I think this as a motivation is clearly presented and makes sense.
The stochastic estimators of the Hessian through Hutchinson method are well known and used in many places in ML. 

Equation 11 is somewhat redundant, since anyone familiar with how modern autodiff packages perform efficient Hessian-vector products  would know that they are just restating well known facts. For the least they should be citing Perlmutter's paper on fast Hessian-vector products, which basically define this. 
In this whole section on the Hessian estimator, I'm very unclear what is the benefit of the proposed extension SETH-D over SETH-H? Theoretically, due to dropping blocks of the whole network it should be more efficient. However, practically the way that modern autodiff packages work, it would be a significantly challenge to actually compute Hessian-vector products such that they benefit from this. E.g. if you just zero out those parts of `sigma` and perform still perform "dense" products on line 5 and 6 of Algorithm 2 it won't make any difference. Later in the results the authors do cite that based on the probability that they pick `p` they gain different run times. I think the authors should provide more details on how in practice they actually implement SEHT-D in order to take advantage of the structure of \sigma? These details although might look like not so important, are probably the only reason why one would even use SEHT-D over SETH-H. 

I have quite a bit of issue with the whole section 3.4. The authors attempt to motivate the trace trough stability analysis. First, that they expand the idealized ODE, for which there is now some literature which uses backward analysis to derive more accurate ODEs and in practice show case that the idealized version is not well capturing what happens with the dynamical system. Second, the main point at the end of this whole section, talking about stability of equilibrium points, is to argue that the goal of the method is to have a "more unstable dynamical system". Why would we want that - I don't know. The last paragraph presents an argument that since standard training is a function only of the training data, we would like it to be unstable in order to avoid overfitting. However, the authors do not present any evidence or even elude to why that last statement would be true and I'm quite doubtful if it will at all. We can make training unstable in many other ways (injecting significant amount of noise for instance) which do not lead to better generalization. As a result I would advice the authors to either significantly change, or just remove this whole section, as it currently serves no purpose. 

Finally, on the results section I have a few major issue with some of the numbers I'm seeing, which make me a bit doubtful of the overall results.

The WRN-28-10 has a baseline with 73% top 1 accuracy. The defualt pytorch open-source results from https://github.com/meliketoy/wide-resnet.pytorch indicate a 80% accuracy (ZCA - no-dropout 5e-4 weight decay). Perhaps the authors are suing different type of preprocessing scheme, or there are other differences, but this should be cleared out as to why they get so much worse results with the same model.

Another issue I have with the presented results, is that the authors do not mention to have done any search over the regualrizer penalty for any of the competing methods (and for theirs they do only two values - 0.01 0.05). They must mention why this is done - if they pick the values from one of the papers, they should make that more clear and also should make it clear that problems considered are equivalent to those in the reference. For many regualrizers their optimal weight changes between different problems. This might or might not explain some of the degradation results we see for some of the other techniques. 

Probably, the final experiment is best execute, with significant hyper parameter search and good ablations, which makes it the only one that makes me trust its results, and unsurprisingly there the benefits are significantly more marginal then in the others. However, it is unclear what is Validation and Test Perplexy exactly? Do you train and cross-validate the hyper parameter to select them, and then retrain on train + validation and measure Test, or do you just measure the performance on the Test set of the best cross-validated model? Please clarify. 
summary_of_the_review: Good and simple idea. I have some issues with lacking implementation details of the method that the authors use in practice. One of the sections seems completely redundant to the narrative, unless the authors provide better explanation for their final statements there. Some of the experiments seem to have lower numbers than publicly known results and in general there is a lack of exploring hyper parameters for other regualrizers. The last experiment is probably the only one that is done really well.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: In this paper, the authors propose an efficient regularizer for the trace of the Hessian. To circumvent the extra computation needed to do the naive Hutchinson estimator (which pretty much amounts to taking *three* derivatives of the loss), the authors subsample the weights matrices, and then a second time internal to each weights matrix). Experimental results on CIFAR-10 and CIFAR-100 are presented: the proposed regularizer helps, but unfortunately not in a statistically significant way.
main_review: Strengths:

* The motivation of using jacobian and hessian trace norm regularizations is drawn from existing theoretical work, it's quite a nice way of tying it together with the extensive literature on generalization bounds. One comment worth adding though is that (I believe) all of those bounds are unfortunately vacuous. But even in that light, I think the idea is natural/worth writing a paper about.
* The initial downsampling (corresponding to p_1) is a clever way to make this work. Otherwise, instead of the 1.2-1.5x slowdowns, I would have expected to have seen at the very least a 2x slowdown (for two more derivatives), and practically speaking more like a 10-50x slowdown given how slow hessian vector products seem to be in practice.

Weaknesses:

* Unfortunately, the "better" results have heavily overlapping confidence intervals. In the top pane, the 2 std confidence interval is +/- 0.47/ Combined with say the seht-d + label smoothing, it's clear that none of these results are significant. I would suggest that the authors aggressively drive down the sizes of these confidence intervals. In the bottom pane, the comparison between mixup and seht-d + mixup suffers from the same problem. In fact, from these experiments, the only reasonable convlusion is that "mixup works really well".

* For comparison's sake, I think the authors really need to try the full version of the regularizer (with multiple iterations and prob=1.0). It's obviously going to be much slower, but if that doesn't work then the existing seht-d then I think something is probably wrong i.e., if the base claim is that "hessian regularization works", it is much less convincing if you don't directly test that hypothesis and go directly to approximations. I'd even be interested in seeing how much variance is introduced by the trace estimator, the two rounds of downsampling etc.

* I think there needs to be a careful study of hyperparameters of the regularizer i.e., prob and regularization coefficient etc.
summary_of_the_review: The idea is interesting, the approximation is nice, but the experimental results are too weak/incomplete to make this a convincing paper.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper develops a new regularization method for deep neural networks.  The proposed methods penalizes the trace of the Hessian.  The paper adapts Hutchinson method for estimating trace of a positive semi-definite matrix for the purposes of estimating trace of the Hessian.  This adaptation uses a dropout mechanism to efficiently compute trace of the Hessian.   The paper also studies the effects of minimizing the trace of the Hessian using linear dynamical systems theory, and shows that lowering the trace of Hessian diminishes the stability of the equilibrium points in the parameter (i.e., weight) space.  Thereby, reducing overfitting and improving generalizability of the network.  The paper concludes with a set of experiments on standard deep learning benchmarks---CIFAR-10, CIFAR-100, and WIKI-TEXT2---and in almost every case the proposed SEHT-D scheme achieves best results.

main_review: The paper makes a strong case for the proposed regularization scheme: penalizing the trace of the Hessian.  The empirical results included in the paper seem to indicate that the proposed regularization scheme improves network performance (and generalizability).  The technical details are accessible, and it is easy to follow the mathematical steps presented in the paper that lead to the final "efficient" algorithm for estimating the trace of the Hessian.  Section 3.4 that describes the linear stability analysis cogently argues why minimizing the trace of the Hessian is one way to improve the generalizability of the network. 

The paper also suffers from some shortcomings.  While reading the paper, I stumbled upon a number typos: misspellings, incorrect double quotes (very common in LaTeX users), etc.  These can be easily fixed.

A more serious issue with the paper is its use of the word "efficient," as in, "to efficiently implements [sic] the Hutchinson method."  I did not see any experiments that showcase how efficient the proposed method is.  I would have liked to see some runtime figures that drive home the point about the efficiency of the proposed approach.  Is there a way to remedy this?

The paper actually presents two methods for estimating the trace of the Hessian.  The first method does not use dropout,  whereas the second, more efficient, method uses dropout.  The paper contains no results using the first method.  It would be nice to know the performance gap between the first and the second method.  In many situations performance and efficiency are inversely related.  Does that hold here too?  Alternately, may be deep neural networks upend this trend and the second method posts both better performance and better runtimes.
summary_of_the_review: Overall the paper is well-written.  It proposes a new regularization scheme that seems to improve deep neural networks performance on CIFAR-10, CIFAR-100, and WIKI-TEXT2 datasets.  The proposed scheme improves performance for both convolutional and recurrent neural networks.  The paper uses linear dynamical systems theory to argue that minimizing the trace of the Hessian improves the generalizability of the network.  Lastly, the mathematical description for "efficiently" computing the trace of the Hessian is easy to follow.

My only issue with the paper is that it doesn't include any results to support the assertion that the algorithm for estimating trace of the Hessian is efficient.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The authors propose a method for estimating the trace of the Hessian of the cross-entropy loss with respect to the weights of a neural network classifier. They suggest adding the trace estimator as a regularizing penalty term for training neural networks with improved generalization.

The authors give two theoretical motivations for regularizing the Hessian trace:
- For linear models the trace of the Hessian of the cross-entropy loss with respect to the logits appears as a factor in a term for bounding generalization error. The authors draw a connection between the Hessian with respect to the weights and the Hessian with respect to the logits and argue that penalizing the trace of the Hessian with respect to the weights also leads to a tighter bound on the generalization error.
- For the continuous gradient dynamics around the optimum the Hessian eigenspectrum is the negative eigenspectrum of the Jacobian of the gradient dynamics which determine the stability of the dynamic system. The authors argue that decreasing Hessian trace increases Jacobian trace and hence reduces data dependend stability which will avoid overfitting.

The authors' suggested method for estimating the trace uses the stochastic Hutchinson trace estimator which samples a random vector sigma with E(sigma sigma^T) = I to get E(sigma^T H sigma) = tr(H). The authors appear to use back-propagation through a back-propagation gradient approach to compute sigma^T H sigma by first computing the gradient g = dl/domega of the loss l with respect to the weights omega, and then computing the gradient of the inner product g^T sigma which is a scalar, with respect to the weights again. This gradient-over-gradient can be inner product multiplied again with sigma.

In order to save cost the authors suggest a drop out method setting a fraction of the terms of sigma to 0 which saves a fraction of the derivative computation and correspondingly drops terms of the trace sum.

The authors then present experimental results evaluating their suggested regularization method in combination with and compared to other regularization methods on
- CIFAR10 / Resnet18
- CIFAR100 / Wide Residual Network
- WikiText-2 / 2-layer LSTM
main_review: Strengths:
- The connection of Hessian spectrum and trace to generalization is an interesting and promising area of research and it is great to see results for a method regularizing the Hessian that seems to outperform other regularization methods
- The structure of the paper is clear and the paper is understandable

Weaknesses:
- The connection between theoretical justification and practical method is not always clear and the relevant details could be expanded:

My feeling is that the connection between using the Hessian / Jacobian with respect to the logits vs with respect to the parameters is not as straight forward as it is made out to be in the paper and could be explained better. For example the paper states: "Naturally, at the minimum the gradient is zero and the norm of the Jacobian matrix is small near minimum."

But if we have for e.g. a nonlinear classifier f(x) = W y(x) where W are the weights of the last layer then dl/df is what is meant as Jacobian in the bound but the gradient in optimization is with respect to parameters, e.g. dl(f(x))/dW = dl/df * df/dW = dl/df * y(x). Could there perhaps be a way for the gradient to be small if y(x) is small without dl/df being small? This question could be expanded upon.

Similarly, an explanation of the difference between the trace of the loss Hessian w.r.t. to logits vs w.r.t to the weights would benefit the paper. For example it is well-known that the Hessian w.r.t. to weights for a deep neural network can have negative eigenvalues but the Hessian w.r.t. to logits for a convex loss has only positive eigenvalues. Does this matter to the trace and associated bound somehow?

Regarding the linear stability argument the paper could be improved by empirically demonstrating that regularizing the Hessian trace leads to an optimum with a Hessian that has "less stability", perhaps by analyzing the eigenvalues at the optimum. Furthermore, is there a connection between the idea that increasing instability helps generalization to the literature that says that flat optima help generalization?

- There is no discussion of using the reverse-over-reverse autodiff method for computing the Hessian vector product instead of a forward-over-reverse autodiff method which can save memory and hence could also be faster on a GPU:

In principle you can get the directional derivative of the scalar g^T(omega) * sigma with respect to omega in the direction of sigma by evaluating

dg/domega * sigma = (g(omega + eps * sigma) - g(omega)) / eps

or similarly

d(g*sigma)/domega * sigma = (g(omega + eps * sigma) * sigma - g(omega) * sigma) / eps

at a factor two of the cost of evaluating only the gradient (gradient evaluated at omega). Alternatively, forward-mode autodiff can be used to the same effect and the dropout idea can still be applied by setting some of the sigma to zero and hence eliminating the cost further due to dropped nodes in the computational graph.

- The experimental section does not analyse the regularizer itself or the connection to theory of the Hessian trace regularization and is instead focused on just demonstrating beating baselines:

There is currently no analysis of the trade-off of the bias of the trace estimator by using more dropout vs additional compute cost, just the statement "Although increasing the probability to select parameters can improve test accuracy, the time consumption will increase a lot". The paper could be improved by adding an empiricial analysis of the accuracy of the trace estimator.

There is also no analysis of how trace accuracy impacts generalization performance and trace itself, e.g. you could add plots showing how the true Hessian trace changes throughout training.

It would be good to see the training and cross validation curves for different hyperparams of overlayed penalty terms (like Hessian trace term, L2 norm term etc.) to see how they impact training and how stable training is to the corresponding hyperparameters. It would be good to have an analysis of how much does Hessian trace term add on top of hyper-param tuned other regularization, e.g. for Jacobian regularization the paper says just "we set number of projections nproj = 1 and weight values λJR = 0.01" which does not necessarily suggest that there was a sufficient hyperparameter tuning effort.

Another interesting question to analyze would be: How does the added regularizer impact the training dynamics, e.g. faster or slower convergence in the beginning vs end of training and why?


Some more general recommendations to improve the paper:
- Checking grammar and spelling typos will improve readability and quality of the paper
- State the generalization bound as a theorem as in the original paper (Theorem 4.1)
- In related work perhaps also connect to other works analyzing Hessian and Fisher matrix spectrum and related norms for generalization (e.g. "Fisher-Rao Metric, Geometry, and Complexity of Neural Networks")

summary_of_the_review: I do not recommend to accept the paper in its current form since the connection between the theoretical justification and the empirical evidence is weak and the experiments in the paper are not sufficient for an empirical understanding of how the suggested regularizer really works.
review_title: null

Meta-review: This paper regularizes deep neural networks via the Hessian trace.  The algorithm is based on Hutchison’s method, further accelerated via dropout.  Connection to the linear stability of dynamical system is discussed.  The proposed regularization shows favorably in the experimental results.

The idea of the method is clear.  The paper’s writing needs a lot of improvement because there are a number of grammatical errors.  The major technical concerns include: a) the experimental results are still not convincing; b) the explanation of favoring instability in the dynamical system that resorts to overfitting prevention (reviewer GDik).  I’ve read the rebuttal, but remain unconvinced.
Decision: Reject