Newton Losses: Using Curvature Information for Learning with Differentiable Algorithms

We sincerely appreciate the reviewer for dedicating their time to evaluate our work and helping us improve it further. Below, we have addressed your insightful comments.

Weaknesses

The soundness of the approach from a theoretical viewpoint is lacking. However, it is probably better to have clear experimental evaluations than wobbly theoretical explanations. And theoretical explanations can be given later.

Indeed the focus of our paper is rather on the experimental part rather on a detailed theoretical analysis (4 pages of experiments compared to 2 pages of the derivation of the method).

We consider Section 3.2 to be rather a derivation of the method than a theory section with theoretical guarantees.

Questions

Why do the authors multiply an inverse of the Hessian with the gradients? Such operation amounts to solve a linear system and is always best handled with matrix-free linear algebra solvers that can make use of Hessian vector products.

In all our experiments, the cost of inverting the Hessian and the multiplication is negligable due to the sizes of the involved spaces. We will add a remark mentioning the solver-based alternative option.

Can the approach be cast as appropriate block-coordinate minimization of the Lagrangian associated to the composition of the loss and the network? As the authors acknowledge if both steps in 2.a, 2.b are gradient steps, we retrieve the classical gradient back-propagation as demonstrated in [57]. Such a setting may help uncover the principles underlying the improved performance.

This is an interesting question. As the reviewer correctly points out, if both steps (2a) and (2b) are gradient steps, this is equivalent to using a gradient descent step for (1), as shown in Lemma 2.

Beyond that special case, we are not aware if the combination of steps (2a) and (2b) can recover any other classical approaches, such as block-coordinate minimization. Our notation with the $\phi$-function may suggest a similarity to the (block)-coordinate descent method. However, unlike coordinate descent methods, we do not split our variables $x$ or $\theta$ into sub-coordinates.

I don't see how the learning rates were tuned in the experiments. Since it is generally a crucial hyperparameter for optimization methods, can the authors comment on this?

For the sorting and ranking experiments, we use a learning rate of 0.001, which is an established value for 100 000 step long training on the benchmark. We want to point out that, as we use Adam, the optimizer is (apart from numerical precision) agnostic to factors of the gradient magnitude.

For the shortest path experiments, we determine the optimal initial learning rate for the baseline and then apply the same learning rate for Newton Losses; the values for SS / PO methods and the grid from AlgoVision is provided on page 15. The learning rate decay schedule is predefined by the benchmark.

The authors keep on mentioning vanishing/exploding gradient phenomena. Could the authors actually demonstrate this issue numerically? I suppose the vanishing/exploding gradient phenomena depends on the number of steps taken by the algorithm defining the loss.

To illustrate the characteristics of the losses and their gradients, we provide 6 figures in the supplemental author response PDF page. We illustrate the gradient of the NeuralSort and logistic DSN losses in dependence of one of the five input dimensions for the $n=5$ case. In the illustrated example one can observe that both algorithms experience exploding gradients when the inputs are too far away from each other (which is also controllable via steepness / tau), see Figures (c) / (d). Further, we can observe that the gradients themselves can be quite chaotic, making the optimization of the loss rather challenging. In Figures (e) / (f), we illustrate how using the Fisher Newton Loss recovers from the exploding gradients experienced in (c) / (d).

Maybe one could correlate the number of steps taken by the underlying algorithm and the improved performance of the proposed approach.

We agree; from Table 1, we can derive such a comparison: using a DSN with 10 inputs has twice the number of steps of a DSN with 5 inputs. Here, we can see that the performance improvements with 10 inputs are greater than the performance improvements in the 5 input case.

Please let us know whether you have any other questions or concerns regarding our paper and response, or whether we have successfully answered and resolved all of your questions and concerns.

We sincerely appreciate the reviewer for dedicating their time to evaluate our work and helping us improve it further. Below, we have addressed your insightful comments.

Weaknesses

1. Insufficient experiments. I'd appreciate adding a comparison here with the SFA technique from there, as it will rely only on first-order information: https://arxiv.org/pdf/2003.02122

Thank you for this suggestion. We will include this paper in the related work. However, we were not able to find any source codes for this work, and reimplementing it from scratch within the author response period is not feasible. We will contact the authors regarding the source code, and if possible include these results in the camera-ready. Nevertheless, we would like to point out the extensiveness of our experimental results, as we apply Newton losses to 11 algorithms, which comprises direct comparisons to the methods of 6 published articles (and on the benchmarks that these works utilize).

Questions

Considering Newton's method in the case of non-convex objectives is a mistake. No matter how much it is regularized, as long as regularization is L2, had authors considered cubic regularization? E.g., https://link.springer.com/article/10.1007/s10107-006-0706-8

We thank the reviewer for highlighting Nesterov's work on cubic regularization. As noted in the mentioned paper, various regularization techniques can be applied when using the Newton method for non-convex or ill-conditioned problems. The most classical technique is Tikhonov regularization (or Levenberg-Marquardt regularization). Given that our Tikhonov-regularized version already demonstrates good empirical performance, we did not explore more sophisticated regularization techniques such as cubic regularization. However, this is indeed an interesting direction for future research. We also want to point out that we always include results with the empirical Fisher, which, by definition, is always positive semi-definite.

Adding to the first question, for ranking objectives, Hessians are expected to converge to zero. Have you considered an increasing learning rate schedule? I am somewhat sure that this hessian/fisher type of method, due to vanishing gradients, also vanishes, resulting in effectively increasing the learning rate up to $\propto \lambda^{-1}$. I will appreciate experiments against the first-order method with the learning rate scheduler growing up to that value.

As the optimizer for all experiments in this paper is the Adam optimizer, such effects can be rather excluded, as multiplying the loss by a factor does not affect updates (apart from numerical precision effects). Using the Adam optimizer is the established experimental setting on each of these benchmarks. In Adam, the sign and relative magnitude of the gradient to the previous step are the important factors. Thus, if the gradient magnitudes increase or decease over time by a certain factor, it should not significantly affect training, as Adam normalized for gradient magnitudes over time (via the square-root of the uncentered variance component). As an ablation study prior to writing the paper, and not included in the paper, we did actually multiply the loss value (and thus also gradient) by factors, and observed that this had no effect on optimization.

Please let us know whether you have any other questions or concerns regarding our paper and response, or whether we have successfully answered and resolved all of your questions and concerns.

We sincerely appreciate the reviewer for dedicating their time to evaluate our work and helping us improve it further. Below, we have addressed your insightful comments.

Weaknesses

The paper does not contain any proofs or convergence guarantees.

It is important to keep in mind that the methods to which we apply Newton Losses do not come with any theoretical convergence guarantees by themselves, even for only SGD optimization, which stems from the non-convexity and complexity of such algorithmic loss functions. Providing convergence guarantees for a simplification that lies outside the space of our considered losses, e.g., a convex original loss function, while trivial, would be rather misleading in our opinion.

For example, is vector $x$ fixed for all steps or is it a batch of data?

We apologize for any confusion. The input vector $x$ throughout our paper refers to a batch of data. We will clarify this in the revised version.

Is it a sum-type problem or an expectation problem?

We generally consider non-separable loss functions. For example, for the ranking supervision experiments, the relation between individual samples and the sorted population is considered. Thus, these ranking losses can not be expressed as a sum over individual samples. Between independent sets, however, the loss can be expressed as an expectation.

What are the properties for $l(.)$? Is it differentiable, smooth? Because some parts of the text said that the loss is non-smooth and later we calculate the Hessian of such a function.

We apologize for the confusion. We assume that the loss function is twice differentiable, ensuring the existence of a Hessian, or at least differentiable for ensuring the existence of the gradient and empirical Fisher matrix. For settings with non-smooth objectives (e.g., shortest-path problem), we apply smoothing techniques to approximate the loss with a smooth counterpart, such as stochastic smoothing (see Section 4.2.2), such that the loss function $\ell(\cdot)$ to which we apply Newton Losses is smooth. We will clarify this in the revised version.

In Formulas 1 and 2, it is not clear what are the fixed parameters or data. Should $\theta$ in 2a be $\theta_{t-1}?

Thank you for spotting this typo. Indeed, in Equation (2a), $\theta$ should be $\theta_{t-1}$. We will fix it.

Also, I think the mention of Lemma 2 in the main text could be very helpful.

Thank you for the suggestion. We will provide a discussion of Lemma 2 in the main text in the revised version.

For the experimental section, personally, it feels that the most of space is taken by the description of the problems and the setup and not the actual comparison. As the paper is mostly experimental and empirical, one would expect a better comparison of the proposed methods with the multiple benchmarks.

Thank you for this suggestion. As we have an additional page for the camera-ready, we will extend the discussion of the results and actual comparisons in the camera-ready; however, we feel that it remains important to maintain the detailed discussions of the benchmarks as well as continuous relaxations that we apply Newton Losses to.

There are no convergence figures with the per-iteration or per-gradient performance.

Could you please clarify what precisely you would like us to plot, considering that we show a per-epoch convergence plot in Figure 3?

As the authors claim, the main issues in the existing approaches are vanishing and exploding gradients. However, I didn’t find any clipping method for the comparison, which are the possible solutions for exploding gradients.

Thank you for this suggestion. On these types of algorithmic loss benchmarks, to our knowledge, gradient clipping has not been previously considered in the literature. If you do have a respective reference, we would greatly appreciate it. Nevertheless, we have implemented gradient clipping for Table 1:

The results show consistent improvements for the first 3 algorithmic losses, but unfortunately it degrades Cauchy DSNs, even compared to the vanilla method. These results are averaged over 5 seeds. In each case, Newton Losses performs substantially better than gradient clipping.

Please let us know whether you have any other questions or concerns regarding our paper and response, or whether we have successfully answered and resolved all of your questions and concerns.

Dear Reviewer qoSU,

Thank you very much for the clarification! Accordingly, we will include both per-epoch and per-time plots in the appendix of the camera-ready version.

Please let us know in case any further questions or concerns come up.