Newton Losses: Using Curvature Information for Learning with Differentiable Algorithms

We thank the reviewer for evaluating our work. In the following, we address your comments.

"There are very few analytical examples studied in the paper. This could help readers realize the importance of Fisher information matrix.

A suitable theortical study is needed for the proposed paper. Some analytical examples can be presented to demonstrate the effectiveness of proposed method."

It would be helpful if the reviewer could point us to what is meant with "analytical examples". In particular, we would like kindly to point the reviewer to Supplementary Materials A, D, E and F, where we study the method from a theoretical perspective. For example, in SM D, we provide a variety of theoretical statements, and in SM F we illustrate analytically how the method would be applied to trivial losses.

"There are general natural gradient methods in the literature, in particular the Wasserstein natural gradient method. This could be discussed in the introduction.

Li, et.al. Natural gradient via optimal transport. Li et.al. Affine Natural Proximal Learning."

We thank the reviewer for pointing us to these two references. Natural gradients are not directly applicable to differentiable algorithms (because they require particular structures of the loss, not given in the case of differentiable algorithm based losses). It is still very interesting to see that natural gradients have also been considered in combination with optimal transport, and extending these ideas to be applicable for differentiable algorithms could be interesting for future investigations. We have included them as suggested in the introduction.

Please let us know whether we resolved your all of your concerns or whether there are any specific analytical examples you would like us to elaborate on. If we successfully addressed your concerns, we would appreciate if you would consider upgrading your score.

We thank the reviewer for evaluating our work. In the following, we address your comments.

Thank you for appreciating our "well written and good presentation" and our "solid theories support".

"Q1: Is there training curve of the real loss functions L during model training? Is there mismatch or conflicts between the MSE loss of the quadratic approximation and the real training loss for the real output y?"

The Newton Loss indeed has a different absolute loss value compared to the respective original loss, which as-per-construction of the Newton Loss does not pose a conflict. Further, we note that the original loss value is still available during training as the Newton Losses build upon the original loss. Figure 3 shows the test accuracy during training and we have included axis labels in the revised PDF.

"Q2: what is the training time for this new method, compared with original SGD method? Ex, the number of iterations and total training time. the validation test accuracy curve during training."

Kindly see Supplementary Material B where we show runtimes for the experiments. In particular, it shows that the proposal has comparable runtime in most cases and only where the computation of the Hessian is slow, it can slow down training. Therefore, we also proposed training with the Fisher variant, which always has comparable runtime compared to the original SGD method.

"There are some missing details and comparisons in the experiments part."

Please let us know whether we resolved your all of your concerns or whether there are any other details you would like us to elaborate on. If we successfully addressed your concerns, we would appreciate if you would consider upgrading your score.

We thank the reviewer for evaluating our work. In the following, we address your comments.

Weaknesses

"While the results show consistent improvements in the experiments, the improvement upon the best performing baselines seems relatively minor compared to the observed standard deviations. However, the method seems to especially improve performance on suboptimal baselines, which could transfer very well to potential new experimental setups."

Indeed, our method leads to the greatest improvements for the earlier differentiable algorithms. We selected these two categories (sorting and shortest path) of differentiable algorithms explicitly because they each have a number of algorithms that improved upon each other to paint a full picture of the approach. Our motivation is indeed to provide the approach for other researchers to use for future differentiable algorithm setups, which are typically not as well optimized as, e.g., the recent Cauchy DSNs.

"Regarding the presentation, I think the standard deviations should also be included in the main paper and not deferred to the appendix, as they seem very important for correctly interpreting the presented results. I also have some additional questions below. If the authors adequately address these final concerns I believe this paper will make a good contribution to the conference."

We would like to offer to include statistical significance tests for Tables 1, 2, and 3 for the camera-ready of the paper, considering the space restrictions. We believe that this would paint an even clearer picture than just including the raw standard deviations. Nevertheless, if you still believe that we should also include the standard deviations in exchange for a smaller table font size, we would accomodate that.

Questions

"In Tables 8-10 it looks like a wide range of the parameter $\lambda$ seems to be used in the experiments. Have the authors found these values purely empirically, or have they been chosen based on e.g. gradient norm? It would also be a useful addition to include an ablation study of how sensitive the performance is to this hyper-parameter for one of the experimental setups."

We found these values empirically by considering the grid $\lambda\in[0.001, 0.01, 0.1, 1, 10, 100, 1000]$ for 1 seed (different seed from the seeds used for the tables). We have started an ablation study to show the effects of $\lambda$ on the differentiable sorting experiment over the full grid. As these experiments will not finish within the rebuttal period, we offer to include the ablation study for the camera-ready.

"In figure 3, does the plot show the number of training epochs on the x-Axis? It seems like this information is missing. This plot could also benefit from averaging over all seeds and including the standard deviations."

Yes, it is the number of epochs. We added labels and extended the figure to include 95% confidence intervals.

"In the proof of Lemma 3, does getting from equation 22 to the final expression require some assumptions on commutativity of the involved matrices? It would be great if the authors could present this final step in a bit more detail."

In Lemma 3, we particularly consider the case of $m=1$ (i.e., a one-dimensional output) (see first line of Lemma 3). With $f(x;\theta)$ a scalar (and hence $\nabla_f$ and $\nabla_f^2$ also scalars), commutativity is not an issue, because scalars commute with matrices.

Please let us know whether we resolved your all of your concerns or whether you have any other questions, concerns, or comments. If we successfully addressed your concerns, we would appreciate if you would consider updating your score.

We thank the reviewer for evaluating our work. In the following, we address your comments.

Weaknesses:

"The main weakness of the presented approach is that the authors consider explicit construction of Hessian or Fischer matrices and directly inverse it. Matrix inversion is the numerically unstable operation in the ill-conditioned case, see (Higham, 1993 - https://eprints.maths.manchester.ac.uk/346/1/covered/MIMS_ep2006_167.pdf). This issue may be crucial in the single-precision format which is typically used in deep learning."

We use Tikhonov regularization on the Hessian and Fisher matrices, which is a standard approach to improve their conditioning by "shifting the eigenvalues" (as the condition number of a matrix is the ratio of the largest to the smallest eigenvalue) (this is addressed in the paper from Equations (5) to (6)). Numerical problems are thus avoided. Note that the Fisher matrix, as an outer product, is necessarily positive semi-definite, and with Tikhonov regularization guaranteed to be positive definite.

"In addition, storage of the full square matrix with a dimension equal to the number of model parameters can be prohibited for large models. Thus, this step in the proposed method lacks detailed analysis and requires more in-depth investigation in terms of scalability and robustness to round-off errors. For example, the iterative methods for solving large symmetrix linear systems can exploit hessian-by-vector product operation without explicitly composing the hessian matrix due to automatic differentiation tools. [...]"

Indeed a "full square matrix with a dimension equal to the number of model parameters" could be prohibitively expensive. However, in our work, we never consider such a matrix. Instead the Hessian or Fisher matrices are always of size $m\times m$ where $m$ is the dimensionality of the output of the neural network (see Section 3.1, all Hessian / Fisher matrices are wrt. $\mathbf{z}$, i.e., the output of the neural network). To illustrate this, for a regular classification neural network, $m$ would correspond to the number of classes (often, 10--1000), which is always drastically smaller than the number of parameters (often millions to billions). In our paper, we consider sizes of $m$ in the range of 5 to 144.

We believe that many of the questions build on this misunderstanding.

Questions:

1. The approach is scalable regardless of the number of model parameters and the size of the dataset. Scalability only depends on the number of outputs of the neural networks / number of inputs of the differentiable algorithm / loss. Another component can be the cost of computing the Hessian of a differentiable algorithm; however, for this reason, we also include the Fisher approach.

2. In this work, we deal with non-convexity and exploding/vanishing gradients specifically in the loss function (and not the neural network). In classical image classification, the loss is typically convex and does not have exploding/vanishing gradients (e.g., CrossEntropyLoss). Conceptually, we are dealing with problems where optimization of the loss function is the bottleneck of the learning problem and optimizing the neural network is easier than optimizing the loss. In image classification with convex losses, this is not the case.

3. Regarding the runtime analysis, the largest matrix that we need to invert is a well-conditioned 144x144 matrix, which is computationally very cheap (< 0.1 millisecond). Accordingly, in most experiments the runtime is only insignificantly increased, and as many factors affect the runtime (like GPU temperature, GPU die quality, CPU scheduling, PCIe interferences, etc.) the differences between runtimes are often smaller than the possible measurement precision of the runtimes. The only case where the runtime actually gets noticably more expensive was in the case of differentiable sorting with the Hessian because computing the Hessian of the differentiable sorting algorithms did not have closed-form solutions (using the Fisher resolves this concern.)

4. The standard deviations are reported in the Supplementary Material C. The sizes of the standard deviations are actually common in the field, which is why we followed the gold standard of using 10 seeds. We found that most improvements are actually statistically significant and we offer to indicate statistical significances in the camera-ready of the paper.

5. Thanks for the suggestion, we added the axis labels to Fig. 3

6. Thanks, we moved the captions on top of the tables.

Please let us know whether we resolved your all of your concerns or whether you have any other questions, concerns, or comments. If we successfully addressed your concerns, we would appreciate if you would consider updating your score.