Newton Losses: Using Curvature Information for Learning with Differentiable Algorithms
Authors: Felix Petersen
Christian Borgelt
Tobias Sutter
Hilde Kuehne
Oliver Deussen
Stefano Ermon
Venue: NeurIPS 2024 poster (2024)
Keywords: differentiable
empirical fisher
hessian
continuous
relaxations
accelerated training
newton's method
stochastic smoothing
Primary area: optimization_for_deep_networks

Abstract: When training neural networks with custom objectives, such as ranking losses and shortest-path losses, a common problem is that they are, per se, non-differentiable. A popular approach is to continuously relax the objectives to provide gradients, enabling learning. However, such differentiable relaxations are often non-convex and can exhibit vanishing and exploding gradients, making them (already in isolation) hard to optimize. Here, the loss function poses the bottleneck when training a deep neural network. We present Newton Losses, a method for improving the performance of existing hard to optimize losses by exploiting their second-order information via their empirical Fisher and Hessian matrices. Instead of training the neural network with second-order techniques, we only utilize the loss function's second-order information to replace it by a Newton Loss, while training the network with gradient descent.  This makes our method computationally efficient. We apply Newton Losses to eight differentiable algorithms for sorting and shortest-paths, achieving significant improvements for less-optimized differentiable algorithms, and consistent improvements, even for well-optimized differentiable algorithms.

Newton Losses: Using Curvature Information for Learning with Differentiable Algorithms
Felix Petersen Stanford University mail0felix-pete -eeeeiixeeeersendde
Christian Borgelt University of Salzburg
Tobias Sutter University of Konstanz tobias. eutterrnut
christian@borgelt.c .et
Hilde Kuehne
Oliver Deussen University of Konstanz oliver deussen@uni. kn
Stefano Ermon Stanford University ermonêcs stanf ord. edu
Tuebingen AI Center
MIT-IBM Watson Al Lab
h. kuehneduni- taaeeetuun-ttueeennndde
Abstract
When training neural networks with custom objectives, such ranking losses and shortest-path losses, a common problem is that they are, per se, non-differentiable A popular approach is to continuously relax the objectives to provide gradients, abling learning. However, such differentiable relaxations are often non-convex and can exhibit vanishing and exploding gradients, making them (already in isolation) hard to optimize. Here, the loss function poses the bottleneck when training a deep neural network. We present Newton Losses, method for improving the performance of existing hard to optimize losses by exploiting their recond-orde information via their empirical Fisher and Hessian matrices. Instead of training the neural network with second-order techniques, we only utilize the loss function 's second-order information to replace by Newton Loss, while training the network with gradient descent. This makes our method computationally efficient. We apply Newton Losses eight differentiable algorithms for sorting and shortest- thottest-paths, achieving significant improvements for less-optimized differentiable algorithms, and consistent improvements, even for well-optimized differentiable algorithms.
Introduction
Traditionally, fully-supervised classification and regression learning relies on convex loss functions such as MSE or cross-entropy, which are tooo-miiee in isolation. However, the need for large amounts of ground truth annotations a limitation of fully-supervised learning; thus, weakly- supervised learning with non-trivial objectives [1]-7] has gained popularity. Rather than using fully annotated data, these approaches utilize problem-specific algorithmic knowledge incorporated into the loss function via a continuous relaxation. For example, instead supervising ground truth values, supervision can be given in the form of ordering information (ranks), e.g., based on human preferences [8], [9]. However, incorporating such knowledge into the loss can make it difficult to optimize, c.g., by making the loss non-convex in the model output, introducing bad local minima. and importantly leading to vanishing as well as exploding gradients, slowing down training [10], [11].
Loss functions that integrate -reeifi-ppecific knowledge can range from rather simple contrastive losses [12] to rather complex losses that require the integration of differentiable algorithms [2], [7], [8]. [11], [13]. In this work, primarily focus the (harder) latter category, which allows for solving
specialized tasks such as inverse rendering [14]-[16], learning-to-rant [2], [5], [8], [11], [17]-[20], self-supervised learning [3], differentiation of optimizers [21], [22], and top-k supervision [2]. [5].
[23]. In this paper, we summarize these loss functions under the umbrella of algorithmic losses [24] they introduce algorithmic knowledge via continuous relaxations into the training objective.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

While the success of neural network training is primarily due to the backpropagation algorithm and stochastic gradient descent (SGD), there also a promising line of work on second-order optimization for neural network training [25]-333]. Compared to first-order methods like SGD, second-order optimization methods exhibit improved convergence rates and therefore require fewer training steps; however, they have two major limitations [31], namely (i) computing the inverse of the curvature matrix for large and deep neural network is computationally substantially more expensive than simply computing the gradient with backpropagation, which makes second-order methods practically inapplicable in many cases [34]; (ii) networks trained with second-order information have been shown to exhibit reduced generalization capabilities [35]. Inspired by ideas from second ooder optimization, in this work, we propose novel method for incor- porating second-order information into training with non-conver and hard to optimize algorithmic losses. Loss functions are usually cheaper evaluate than a neural network. Further, loss functions operate on lower dimensional spaces than those spanned by the parameters of neural networks. If the loss function becomes the bottleneck in the optimization process because it is difficult to optimize, it suggests to use stronger optimization method that requires fewer steps like second- order optimization. However, as applying second-order methods to neural networks is expensive and limits generalization, we want to train the neural network with first-order SGD. Therefore, we propose Newton Losses, a method for locally approximating loss functions with a quadratic with second-orde Taylor expansion. Thereby, Newton Losses provides (locally) convex loss leading to better optimization behavior, while training the actual neural network with gradient descent.
For the quadratic approximation of the algorithmic losses, we propose two variants of Newton Losses: (i) Hessian-baser Newton Losses, which comprises a generally stronger method but requires an estimate of the Hessian [31]. Depending on the choice of differentiable algorithm, choice of relaxation, or its implementation, the Hessian may, however, not be available. Thus, we further relax the method to (ii) empirical Fisher matrix-based Newton Losses, which derive the curvature information from the empirical Fisher matrix [36], which depends only on the gradients. The empirical Fisher variant can be easily implemented on top of existing algorithmic losses because it does not require to compute their second derivatives, while the Hessian variant requires computation of second derivatives and leads to greater improvements when available.
We evaluate Newton Losses for an array of eight families of algorithmic losses on two popular algorithmic benchmarks: the four-digit MNIST sorting benchmark [37] and the Warcraft shortest- path benehmark [22]. We find that Newton Losses leads to consistent performance improvements for each of the algorithms-for for some of the algorithms (those which suffer the most from vanishing and exploding gradients) more than doubling the accuracy.
2 Background & Related Work
The related work comprises algorithmic supervision losses and second-order optimization methods. To the best of our knowledge, this is the first work combining second-order optimization of loss functions with first-order optimization of neural networks, especially for algorithmic losses.
Algorithmic Losses. Algorithmic losses, i.e., losses that contain some kind of algorithmic compo- nent, have become quite popular in recent machine learning research. In the domain of recommender systems, early learning-to-ran works already appeared in the 2000s [17]. [18], [38], but more recently Lee el al. [39] proposed differentiable ranking metrics, and Swezey al. [8] proposed PiRank, which relies on differentiable sorting. For differentiable sorting, an array of methods has been proposed in recent years, which includes NeuralSort [37]. SoftSort [40], Optimal Transport Sort [2], differentiable sorting networks (DSN) [5], and the relaxed Bubble Sort algorithm [24]. Other works explore differentiable sorting- based top-k for applications such differentiable image patch selection [41], differentiable hearest-neighhet [23], [37], top-k attention for machine translation [23], differen-
tiable beam search methods [23], [42], survival analysis [43], and self- supervied learning [7]. But
algorithmic losses are not limited to sorting: other works have considered learning shortest-paths [21],
[22]. [24], [44], learning 3D shapes from images and silhouettes [14]-[16], [24], [45]_[4]], learning with combinatorial solvers for NP-hard problems [22], learning to classify handwritten characters based on editing distances between strings [24], learning with differentiable physics simulations [48], and learning protein structure with differentiable simulator [49], among many others.

---

Second-Order Optimization. Second-order methods have gained popularity in machine learning due to their fast convergence properties when compared to first-order methods [25]. One alternative to the vanilla Newton's s method are quasi-Newton methods, which, instead of computing an inverse Hessian in the Newton step (which is expensive), approximate this curvature from the change in gradients [31], [50], [51]. In addition, number of new approximations to the pre-conditioning matrix have been proposed the literature, i.a., [26], [28], [52]-[54]. While the vanilla Newton method relies on the Hessian, there are variants which use the empirical Fisher matrix, which can coincide in specific cases with the Hessian, but generally exhibits somewhat different behavior. For an overview and discussion of Fisher- methods (including natural gradient descent), see [36], [55].
3 Newton Losses
3.1 Preliminaries
We consider the training of a neural network f(;; (x; where E R" is the vector of inputs, 0 E R is the vector of trainable parameters and y = (x; E I is the vector of outputs. As per vectorization, Nx denotes set of N input data points, and f(x 0) E N denotes the neural network outputs corresponding to the inputs. Further, let é R xm - IR denote the loss function, and let the "label" information be implicitly encoded in L. The reason for this choice of implicit notation is that, for many algorithmic losses, it is not just a label, e.g., it can be ordinal information between multiple data points or a set of encoded constraints. We assume the loss function to be twice differentiable. but also present an extension for only once differentiable losses, as well as non con-iifferentiabee losses via stochastic smoothing in the remainder of the paper.
[2], .............. [.,.....
xNN] xN|
Conventionally, the parameters 0 are optimized using an iterative algorithm (e.g., SGD [56], Adam [57], or Newton's method [31]) that updates them repeatedly according to:
0g f One optim. step of {(f(x; 0)) wrt. O 0 0
However, in this work, we consider splitting this optimization update step into two alternating steps:
z One optim. step of f(z) wrt. z at z f(x: 0.-1),
(2a)
0g < One optim. step of || f(x; 0)12 wrt. 0 at A 0
(2b)
More formally, this can also be expressed via function øi :.:))) that describes one update step (its first argument is the objective to be minimized, its second argument is the variable to be optimized, and its third argument the starting value for the variable) as follows:
0, + a (x((((x; B)), 0, 0
(3)
And, for two update step funetions Φe and Φ2, we can formalize (2) to
z - Φn (E(Z), 2,
f(x: 0x;;)--)):
(4a)
0, - 22 E f(x; 0)1, 0, 1,-1).
(4b)
The purpose of the split is to enable us to use two different iterative optimization algorithms di and 62. This is particularly interesting for optimization problems where the optimization of the loss function f a difficult optimization problem. For standard convex losses like MSE or CE, gradient descent is perfectly sufficient choice for á (MSE will recover the goal, and CE leads to outputs xt that achieve a perfect argmax classification result). However, if there is the asymmetry of being harder to optimize (requiring more steps), while (4a) being much cheaper per step compared to (4b), then the optimization of the loss (4a) comprises a bottleneck compared to the optimization of the neural network (4b). Such conditions are prevalent in the space of algorithmic supervision losses.
similar split (for the case of splitting between the layers of neural network, and using gradient descent for both (2a) and (2b), i..., the requirement of Φ1 = Φz) is also utilized in the fields of biologically plausible backpropagation [58]-[61] and proximal backpropagation [62], leading to reparameterizations of backpropagation. For SGD, we show that (3) is exactly equivalent to (4) in Lemma 2, and for a special case of Newton's 's method, we show the equivalence in Lemma in the SM. Motivated by the equivalences under the split, in the following, we consider the case of Φ1 # d2.
3

---

3.2 Method
Equipped with the two-step optimization (2) (4), we can introduce the idea behind Newton Losses:
We propose 61 to be Newton's 's method, while Φ2 remains stochastic gradient descent.
In the following, we formulate how we can solve optimizing (2a) with Newton's 's method, or, whenever we do not have access to the Hessian of l, using a step pre-conditioned via the empirical Fisher matrix. This allows us to transform an original loss function È into Newton loss E", which allows optimizing & with gradient descent only while maintaining equivalence to the two-step idea, and thereby making it suitable for common machine learning frameworks.
Newton's method relies on quadratic approximation of the loss function at location y f(x; 0)
(z) E(y)+ + (z y) Vgl(y) + [ - y) Vzl(y) (
y),
(5)
and sets its derivative to 0 to find the location x' of the stationary point of &y (z):
V (z-d)(z")=0 =0 + Vgl(y) Vz((())(z y) =
zz z'= (V)
(6)
However, when is non-convex or the smallest eigenvalues of V (y) either become negative zero, this z" may not be a good proxy for a minimum of f, but may instead be any other stationary point or lie far away from y. leading exploding gradients downstream. To resolve this issue, we introduce Tikhonov regularization [63] with a strength of X, which leads to a well-conditioned curvature matrix:
z y y (V) + A 1) Vy((y).
(7)
Using z", we can plug the solution into (2b) to find the Newton loss E and compute its derivative as (yly) = =(== - y) (z" - y) = || - 212 and Vy (y) = y zz
(8)
Here, as in Section 3.1, y fx, 0). Via this construction, we obtain the Newton loss eg., new convex loss, which itself has a gradient that corresponds to one Newton step of the original loss. In particular, on y, one gradient descent step on the Newton loss (8) reduces to
y - 71- Vy (y) = - 7 -z) = y -1 (V + A- - vyl(y)
(9)
which is exactly one step of Newton's 's method on y. Thus, we can optimize the Newton loss t (x: 0)) with gradient descent, and obtain equivalence to the proposed concept.
In the following definition, we summarize the resulting equations that define the Newton loss E
Definition 1 (Newton Losses (Hessian)). For a loss function & and a given current parameter vector 0, we define the Hessian-based Newton loss via the empirical Hessian as
(y) = = 2/12²* -1112 where
2 = UJ - ( EN (()) Vg
(10)
for all i E {1....,N) N} and y f=x(x;)) ((x:0).
We remark that computing and inverting the Hessian of the loss function is usually computationally efficient. (We remind the reader that the Hessian of the loss function is the second derivative wrt. the inputs of the loss function and we further remind that the inputs to the loss are not the neural network parameters / weights.) Whenever the Hessian matrix of the loss function not available, whether it may be due to limitations of a differentiable algorithm, large computational cost, lack of a respective implementation of the second derivative, etc., we may resort to using the empirical Fisher matrix (i.e,, the second uncentered moments of the gradients) remark that the empirical Fisher matrix is not the same as the Fisher information matrix [36), and that the Fisher information matrix is generally not available for algorithmic losses. While the empirical Fisher matrix, as a source for curvature information, may be of lower quality than the Hessian matrix, it has the advantage that it can be computed from the gradients, i.c.,
source for curvature information. We
F E2 [V)c,,) ((f(x, 0)) (( e(((z, []
(11)
This means that, assuming moderate dimension of the prediction space m, computing the empirical Fisher comes at no significant overhead and may, conveniently, be performed in-place as we discuss later. Again, we regularize the matrix via Tikhonov regularization with strength À and can, accordingly, define the empirical Fisher-based Newton loss as follows.

---

Algorithm TTriniig with a Newton Loss
Algorithm 2 Training with InjectFisher
Python style pseudo-code
imp lements the Pisher-based Newton loss injected modification of the backward pass:
model
neural network original loss fn optim. of model hyperparameter
loss
optimizer
class def forxard(ctx, tik_1);
tik_1
assert (en (en(x.shape) shape) ctx. tik_iikl tik_1 return x
for data, label data_loader,
apply a neural network model model (data)
def backward(ctx, g):
compute gradient of orig. loss grad gradient (loas (y, label), y) compute Hessian (or alt. Fisher) hess hessian (1oss label), y)
fisher g.T g g shapee [0]
input_grad = 0 inverse(fishen + ctx. ctx.tikk1 eye eye (h]pe(1]))
return input_grad, None
compute the projected optimun z_star = (y grad 0 inverse (hess tik_l eye shape detach
for data, label in data_loader:
apply neural network model y = model (data)
inject the Fisher backward mod.
compute the Newton MSELoss() (y, z_star)
y InjectFisher. injeetPishhrraaplyyy
apply (y, tik_l) compute the original loss
1 = loss(y, label)
backpropagate and optim. step
# backpropagate and optim. step
1. backwardd)) optimizer . step()
1. backward
optimizer step()
Definition 2 (Newton Loss (Fisher)). For a loss function f, and a given current parameter vector 0, we define the empirical Fisher-based Newton loss
G- (y) = y112 where
= =
V ,,
for all E (1,..., N) and y f(;
Before continuing with the implementation, integration, and further computational considerations, we make interesting observation. In the of using the trivial MSE loss, i.e., E(y) 1/2 flyy y 1| where y denotes a ground truth, the Newton loss collapses to the original MSE loss. This illustrates that Newton Losses requires non-trivial original losses. Another interesting aspect is the arising fixpoint-the Newton loss of a Newton loss is equivalent to simple Newton loss.
3.3 Implementation
After introducing Newton Losses, in this section, discuss aspects of implementation and illustrate its implementations in Algorithms and 2. Whenever we have access to the Hessian matrix of the algorithmic loss function, it is generally favorable utilize the bessian-based approach (Algo. 1 Def. I), whereas we can utilize the empirical Fisher- based approach (Algo. 2/ Def. 2) in any case.
In Algorithm 1, the difference to regular training is that we use the original loss only for the computation of the gradient (grad) and the Hessian matrix (hess) of the original loss. Then we compute 2 (z_star). Here, depending the automatic differentiation framework, we need to ensure not to backpropagate through the target z_star, which may be achieved, c.g., via detach ()" or " sstop_gradeet ()", depending on the choice of library. Finally, the Newton loss 1 may be computed as the squared / MSE loss between the model output y and z_star and an optimization step on 1 may be performed. We note that, while we use label from our data_ [oader, this label may be empty or an abstract piece of information for the differentiable algorithm; in our experiments, use ordinal relationships between data points well as shortest- paths graphs.
In Algorithm 2, we show how to apply the empirical Fisher-based Newton Losses. In particular, due to the empirical Fisher matrix depending only on the gradient, we can compute it in-place during the backward pass backpropagation, which makes this variant particularly simple and efficient to apply. This can be achieved via an injection of custom gradient right before applying the original loss,
5

---

which replaces the gradient in-place by gradient that corresponds to Definition 2. performed by the injectFisher function, which corresponds to an identity during the forward pass but replaces the gradient by the gradient of the respective empirical Fisher-based Newton loss.
The injection is
In both cases, the only additional hyperparameter to specify is the Tikonov regularization strength (tik_1). À heavily depends on the algorithmic loss function, partieularly, on the magnitude of gradients provided by the algorithmic loss, which may vary drastically between different methods and implementations. Other factors may be the choice of Hessian / Fisher, the dimension of outputs m, the batch size N. Notably, for very large X, the direction of the gradient becomes more similar to regular gradient descent, and for smaller A, the effect of Newton Losses increases. We provide an ablation study for À in Section 4.3.
4 Experiments
For the experiments, we apply Newton Losses to eight methods for differentiable algorithms and evaluate them on two established benchmarks for algorithmic supervision, i.e., problems where an algorithm is applied to the predictions of model and only the outputs of the algorithm are supervised. Specifically, we focus on the tasks of ranking supervision and shortest-patt supervision because they each have range of established methods for evaluating our approach. In ranking supervision, only the relative order of set of samples is known, while their absolute values remain unsupervised. The established benchmark for differentiable sorting and ranking algorithms is the multi-digit MNIST sorting benchmark [2], [5], [11], [37], [40]. In shortest-pant -aatesttpathhhee supervision, only the shortest-path of graph is supervised, while the underlying cost matrix remains unsupervised. The established benchmark for differentiable shortest-path algorithms is the Warcraft shortest-path benchmark [21]. [22]. [24]. As these tasks require backpropagating through conventionally non- differentiable algorithms, the respective approaches make the ranking or shortest-path algorithms differentiable such that they can be used part of the loss.
4.1 Ranking Supervision
In this section, we explore ranking supervision [37] with an array of differentiable sorting-based losses. Here, we use the four-digit MNIST sorting benchmark [37]. where sets of n four-digit MNIST images are given, and the supervision is the relative order of these images corresponding to the displayed value, while the absolute values remain unsupervised. The goal is to learn CNN that maps each image scalar value in an order preserving fashion. As losses, we use sorting supervision losses based on the NeuralSort [37], the SoftSort [40], the logistic Differentiable Sorting Network [5], and the monotonic Cauchy DSN [11]. NeuralSort and SoftSort work by mapping an input list (or vector) of values to a differentiable permutation matrix that is row-stochastic and indicates the order ranking of the inputs. Differentiable Sorting Networks offer an alternative to NeuralSort and SoftSort. DSNs are based on sorting networks, a classic family of sorting algorithms that operate by conditionally swapping elements. By introducing perturbations, DSNs relax the conditional swap operator to a differentiable conditional swap and thereby continuously relax the sorting and ranking operators. We discuss the background of each of these diff. sorting and ranking algorithms in greater detail in Supplementary Material B.
Setups. The sorting supervision losses are cross-entropy losses defined between the differentiable permutation matrix
Ø
&
4
CNN
3 7 5 5
CNN CNN
Diff. Rank
40
40
0
D
produced by a respective differentiable sorting operator and the ground truth permutation matrix corresponding to ground truth ranking. The Cauchy DSN may be an exception to the hard to optimize classification as it is quasi- convex [11]. We evaluate the sorting benchmark for numbers of elements to be ranked n E (5, 10} and use the per- centage of rankings correctly identified
6 8 2
0
7
0
3 2
CNN
2
9 0 / 8
CNN
Figure 1: Overview over ranking supervision with a differentiable sorting / ranking algorithm. set of input images is (element- wise) processed by CNN, producing scalar for each image. The scalars are sorted / ranked by the differentiable ranking algorithm, which returns the differentiable permutation matrix, which is compared to the ground truth permutation matrix.
!Our implementation is openly available ggiiubb.com/iiiiittttteeeettawoo wwwerssenn/ewwwonn-ssseee

---

Table I: Ranking supervision with differentiable sorting. The metric is the percentage of rankings correctly
identified (and individual element ranks correctly identified, parentheses) avg. over 10 seeds. Statistically
significant improvements (sig. level 0.05) are indicated bold black; improved means are indicated in bold grey.
5
NouralSort [37]
SoftSort (400
Logistic DSN [5]
Cauchy DSN [11]
Baseline
71.33=2.05
70.70 (07.10
00
53.56:15.01 1.6.
(77.04
85. 35.09
(93.3110.8)
NL (Hessian)
83.31=1.70
83.87+0.81 (92.54.0773)
(92.72+0.39)
75.02=12.59
(88.63+00.00)
15.118
(9..31+0.34)
NL (Fisher)
83.93=0.62
(92.80=0.30)
84.03+0.59
63. 13.114330.3
279.28+22.10 16)
84.95=0.79
(93.25+00.7)
10
NeuralSort
SoftSort
Logistic DSN
Cauchy DSN
Baseline
24.26=01.52
(74.47:0083)
27.46+3.54 58
(76.02=1.g)
12.31=10.22
[58.81+16.7)
55. 55.29=2.46 46 (87 0.)
NL (Hessian)
48.76+06.88 88 (84.83+2.13
55.07=11088
(8..89+0.31)
42.14:22..00
(75.33+22.77)
56.49:1.02
(87.44++.40
NL (Fisher)
39.23=11.38
(81.14+4.91)
54.00+22.44
(86.5620.68)
25.72:27.42
(82.18136.51)
56. 16.12
(87.35:00655
as well as percentage of individual element ranks correctly identified as evaluation metrics. For each of the four original baseline methods, we compare to two variants of their Newton losses: the empirical Hessian and the empirical Fisher variant. For each setting, we train the CNN on 10 seeds using the Adam optimizer [57] at a learning rate of 10-3 for 10 steps and batch size of 100.
Results. As displayed in Table 1, we can see fhat-for each original loss-Newton Losses improve over their baselines. For NeuralSort, SoftSort, and Logistic DSNs, we find that using the Newton losses substantially improves performance. Here, the reason is that these methods suffer from vanishing and exploding gradients, especially for the more challenging case of n 10. As expected, we find that the Hessian Newton Loss leads to better results than the Fisher variant, except for NeuralSort and SoftSort in the easy setting of close. Monotonic differentiable sorting networks, i.... the Cauchy DSNs, provide an improved variant of DSNs, which have the property of quasi-convexity and have been shown to exhibit much better training behavior out-of-the-bol
5, where the results are nevertheless quite
which makes it very hard to improve upon the existing results. Nevertheless, Hessian Newton Losses are on-par for the easy case of n = 5 and, notably, improve the performance by more than 1% on the more challenging case of n = 10. To explore this further, we additionally evaluate the Cauchy DSN for n 15 (not displayed in the table): here, the baseline achieves 30.84 30.8442.74 (82.30=1.05) whereas, using NL (Fisher), we improve it to 32. 32.30+1.22 10.53,, showing that the trend of increasing improvements with more challenging settings (compared to smaller n) continues. Summarizing, we obtain strong improvements on losses that are hard to optimize, while in already well-behaving cases the improvements are smaller. This perfectly aligns with our goal of improving performance on losses that are hard to optimize.
4.2 Shortest-Path Supervision
In this section, we apply Newton Losses to the shortest-path supervision task of the 12 x 12 Warcraft shortest-path bench- mark [21]. [22], [24]. Here, 12 x 12 War- craft terrain maps are given 96 x 96 RGB images (e.g.. Figure 2 left) and the supervi- sion is the shortest path from the top left to the bottom right (Figure 2 right) according to hidden cost embedding (Figure 2 cen- ter). The hidden cost embedding is not available for training. The goal is to predict 12 x 12 cost embeddings of the terrain maps such that the shortest path according the predicted embedding corresponds to the ground truth shortest path. Vlastelica et al. [22] have shown that integrating an algorithm in the training pipeline substantially improves performance compared only using a neural network with an casy-to-optimize loss function, which has been confirmed by subsequent work [21], [24]. For this task, we explore set of families of algorithmic supervision approaches: Relaxed Bellman-Fort [24] is a shortest- -atottest-pahhhhtee algorithm relaxed via the Algo framework, which continuously relaxes algorithms by perturbing all accessed variables with logistic distributions and approximating the expectation value in closed form. Stochastic Smoothing [64] is a sampling- based differentiation method that can be used to relax, e.g., a shortest-pate algorithm by perturbing the input with probability distribution. Perturbed Optimizers with Fenchel- Young Losses [21] build on stochastic smoothing and Fenchel-Your losses [65] and identify the argmax to be the differential of max, which allows a simplification of stochastic smoothing, again applied, e.g., to shortest-path
Figure 2: 12 x 12 Warcraft shortest-pait problem. An input terrain map (left), unsupervised ground truth cost embedding (center) and ground truth supervised shortest path (right).
7

---

learning problems. We use the same hyperparameters as shared by previous works [21], [24]. In particular, it is notable that, throughout the literature, the benchmark assumes a training duration of 50 epochs and learning rate decay by factor of 10 after 30 and 40 epochs each. Thus, we do not deviate from these constraints.
Table 2: Shortest-path benchmark results for different variants of the
4.2.1 Relaxed Bellman-Ford
Algo Vision-relaxed Bellman-Ford algorithm [24]. The metric is the percentage of perfect matches averaged over 10 seeds. Significant improvements are bold black, and improved means are bold grey.
The relaxed Bellman-Ford algo- rithm [24] is continuous relaxation of the Bellman-Ford algorithm via the AigoVision library. To increase the number of settings considered, we ex- plore four sub-variants of the algo- rithm: For+I1, For+ While+L1, and While+T33 Here, For While refers to the distinction between using While and For loop in Bellman-Fone Ford, while L1 vs. L3 refer to the choice of metric between shortest paths. As computing the Hessian of the Algo Vision Bellman-FFrr algorithm is too expensive with the PyTorch implementation, for this evaluation, Fisher-based Newton loss. The results displayed Table While the differences are rather small, as the baseline here is already strong, case achieve significant improvement. This can be attributed to (i) the high performance of the baseline algorithm on this benchmark, and (ii) that only the empirical Fisher-based Newton loss is available, which is not as strong as the Hessian variant.
Variant
Fo
Fo L2
While+L1
While+
Baseline NL (Fisher)
94.19 19 94.5240.34
95.90=0.21 96.08+0.46
34:30:0:20
95. 35.7770041
94.4740.34
95.9440.27
restrict it to the empirical
observe improvements in all of the four settings and in one
4.2.2 Stochastic Smoothing
After discussing the analytical relaxation, we continue with stochastic smoothing approaches. First, we consider stochastic smoothing [64]. which allows perturbing the input of function with an exponential family distribution to estimate the gradient of the smoothed function. For reference on stochastic smoothing with focus on differentiable algorithms, we refer to the author's recent work [44]. For the baseline, we apply stochastic smoothing to a hard non-differentiable Dijkstra algorithm based loss function to relax it via Gaussian noise ("SS of loss"). We utilize variance reduction via the method of covariates. As we detail Supplementary Material B.4, stochastic smoothing can also be used estimate the Hessian of the smoothed function. Based on this result, we can construct the Hessian-varian Newton loss. As an extension to stochastic smoothing, we apply stochastic smoothing only the non-differentiable Dijstra algorithm (thereby computing its Jacobian matrix) but use a differentiable loss to compare the predicted relaxed shortest-path to the ground truth shortest-path ("SS of algorithm")). In this case, the Hessian Newton loss is not applicable because the output of the smoothed algorithm is high dimensional and the Hessian of the loss becomes intractable. An extended discussion of the "SS of algorithm" " fomulation can be found in SM B.4.1. Nevertheless. we can apply the Fisher-based Newton loss. We evaluate both approaches for 3, 10, and 30 samples.
In Table 3, we observe that Newton Losses improves the results for stochastic smoothing in each case with more than samples. The reason for the poor performance on 3 samples is that
80
NL (Hessian)
(Fisher)
75
Baseline
the Hessian or empirical Fisher, respectively, is estimated using only 3 samples, which makes the
Acc. [96]
70
estimate unstable. For 10 and 30 samples, the performance improves compared to the original method. In Figure 3. we display respective ac- curacy plot. When comparing "SS of loss" and "SS of algorithm", sion to smoothing only the algorithm improves performance for at least 10 samples. Here, the reason, again, is that smoothing the algorithm itself requires estimating the Jacobian instead of only the gradient; thus, larger number of sam- ples necessary; however starting at 10 samples, smoothing the algorithm performs better, which means that the approach is better at utilizing a given sample budget.
55
0
10
20
30
40
50
can observe that the exten-
Epochs
Figure 3: Test accuracy (perfect matches) plot for 'SS of loss" with 10 samples on the Warcraft shortest-path benchmark. Lines show the mean and shaded areas show the 95% conf. intervals.
8

---

Table 3: Shortest-path benchmark results for the stochastic smoothing of the loss (including the algorithm), stochastic smoothing of the algorithm (excluding the loss), and perturbed optimizers with the Fenchel- Young loss. The metric the percentage of perfect matches averaged over 10 seeds. Significant improvements are bold black, and improved means are bold grey.
Method
SS of loss
SS of algorithm
PO w/ FY loss
Samples
3
10
30
10
30
3
10
30
Baseline
62.8325.29 77.01=2.
85.481125 123 57.5524458
78. 7..70 87.26:1.50
64100.7 80.30=0.57
80.7111125
NL. (Hessian)
62.40+5548
78.8242.12
85.94+133
83.09=3.11 81.13#3.58 83.45+2.21
NL (Fisher)
58.80#5.10 78.74 86.10+0..0 53.8228.45 79.24 87.41+1.13
80.70=00.6
80.37 80.45
4.2.3 Perturbed Optimizers with Fenchel-Young Losses
Perturbed optimizers with Fenchel- Young loss [21] is formulation of solving the shortest path problem as an arg max problem, and differentiating this problem using stochastic smoothing- based perturbations and a Fenchel- Fenchel-Young Young loss. By extending their formulation to computing the Hessian of the Fenchel-Young loss, we can compute the Newton loss, and find that we can achieve improvements losses, which defined via their derivative, the
of more than 2%. However, for Fenchel- empirical Fisher is not particularly meaningful, leading to equivalent performance between the baseline and the Fisher Newton loss. Berthet er al. [21] mention that their approach works well for small numbers of samples, which we can confirm as seen in Table 3 where the accuracy is similar for each number of samples. An interesting observation is that perturbed optimizers with Fenchel-Youus losses perform better than stochastic smoothing in the few-sample regime, whereas stochastic smoothing performs better with larger numbers of samples.
4.3 Ablation Study
In this section, we present our ablation study for the (only) hyperparameter X. À is the strength of the Tikhonov regularization (see, e.g., Equation 7, or tik_ in the algorithms). This parameter important for controlling the degree to which second-order information is used as well as regularizing the curvature. For the ablation study, we use the experimental setting from Section 4.1 for NeuralSort consider 13 values for X, exploring the range from 0.001
and SoftSort and n 5. In particular, to 1000 and plot the element-wise ranking accuracy (individual element ranks correctly identified) in Figure 4. We display the average over 10 seeds as well each seed's result individually with low opacity. We can observe that Newton Losses are robust over many orders of magnitude for the hyperparameter A. Note the logarithmic axis for À in Figure 4. In general, observe that choices within few orders of magnitude around are generally favorable. Further, we observe that NeuralSort more sensitive to drastic changes in À compared to SoftSort.
4.4 Runtime Analysis
We provide tables with runtimes for the experiments in Supplementary Material D. We can observe that the runtimes between the baseline and empirical Fisher-based Newton Losses are indistinguish- able for all cases. For the analytical relaxations of differentiable sorting algorithms, where the
0.94
0.94
0.92
0.92
Acc. te.w (e.w.
0.90
0.90
0.88
0.88
NL (Hessian)
(Hessian)
0.86
NL (Fisher) Baseline
0.86
NL (Fisher)
Baseline
0.84
0.84
10-3
10-2
10
10a
10a
102
10a
10-3
10
-2
10
10
10a
10a
10a
A
Figure 4: Ablation study wrt. the Tikhonov regularization strength hyperparameter Displayed is element- wise ranking accuracy (individual element ranks correctly identified), averaged over 10 seeds, and additionally each seed with low opacity in the background. Left: NeuralSort. Right: SoftSort. Each for = 5. Newton Losses, and for both the Hessian and the Fisher variant, significantly improve over the bascline for up to (or beyond) orders of magnitude in variation of hyperparameter Note the logarithmic horizontal axis.

---

computation of the Hessian can become expensive with automatic differentiation (i.e., without a cus- tom derivation of the Hessian and without vectorized Hessian computation), we observed overheads between 10% and 2.6x. For all stochastic approaches, we observe indistinguishable runtimes for Hessian-based Newton Losses. In summary, applying the Fisher variant of Newton Losses has a minimal computational overhead, whereas, for the Hessian variant, any overhead depends merely on the computation of the Hessian of the algorithmic loss function. While, for differentiable algo- rithms, the neural network's output dimensionality algorithm's 's input dimensionality is typically moderately small to make the inversion of the Hessian or empirical Fisher cheap, when the output dimensionality becomes very large such that inversion of the empirical Fisher becomes expensive, we refer to the Woodbury matrix identity [66], which allows simplifying the computation via its low-rank decomposition. A corresponding deviation is included in SM F. Additionally, solver-based inversion implementations can be used to make the inversion more efficient.
5 Conclusion
In this work, we focused on weakly-supervin learning problems that require integration of differ- entiable algorithmic procedures in the loss function. This leads to non-convex loss functions that exhibit vanishing and exploding gradients, making them hard optimize. We proposed novel approach for improving performance of algorithmic losses building upon the curvature information of the loss. For this, we split the optimization procedure into two steps: optimizing on the loss itself using Newton's 's method to mitigate vanishing and exploding gradients, and then optimizing the neural network with gradient descent. We simplified this procedure via a transformation of an original loss function into Newton loss, which comes in two flavors: Hessian variant for cases where the Hessian available and an empirical Fisher variant as an alternative. We evaluated Newton Losses on set of algorithmic supervision settings, demonstrating that the method can drastically improve performance for merlly-perrorming differentiable algorithms. We hope that the community adapts Newton Losses for learning with differentiable algorithms and see great potential for combining it with future differentiable algorithms in unexplored territories of the space of differentiable relaxations, algorithms, operators, and simulators.
Acknowledgments and Disclosure of Funding
This work was in part supported by the IBM-MIT Watson Lab,, the DFG in the Cluster of Excellence EXC 2117 "Centre for the Advanced Study of Collective Behaviour" (Project-ID 390829875), the Land Salzburg within the WISS 2025 project IDA-Lab (20102-F1901 11119991666K22 KZP and 20204- WISS/225/197-0011 the U.S. DOE Contract No. DE-AC02-76SF0051: the ARO (N-11NF-- 0125), the ONR (N00014-23-1-2159), and the CZ Biohub.
References
[1] M. Dehghani, H. Zamani, A. Severyn, J. Kamps, and B. Croft, "Neural ranking models with weak supervision," in Proceedings of the 40th international ACM SIGIR conference research and development in information retrieval, 2017.
[2] M. Cuturi, O. Teboul, and J.-P. Vert, "Differentiable ranking and sorting using optimal trans- port," in Proc. Neural Information Processing Systems (NeurIPS), 2019.
[3] M. Caron, I. Misra, Mairal, Goyal, P. Bojanowski, and A. Joulin, "Unsupervised learning of visual features by contrasting cluster assignments," Proc. Neural Information Processing Systems (NeurIPS), 2020.
[4] G. Wang, G. Wang. X. Zhang, J. Lai, Z. Yu, and L. Lin, "Weakly supervised person re- id: Differentiable graphical learning and new benchmark." IEEE Transactions on Neural Networks and Learning Systems, vol. 32, no. 5. pp. 2142-2156, 2020.
[5] F. Petersen, C. Borgelt, H. Kuchne, and O. Deussen, "Differentiable sorting networks for scalable sorting and ranking supervision," Learning (ICML), 2021.
Proc. International Conference on Machine
[6] V. Shukla. Z. Zeng, K. Ahmed, and G. V. d. Broeck, "A unified approach to count-based weakly-supervised learning," Proc. Neural Information Processing Systems (NeurIPS), 2023.
10

---

[7] N. Shvetsova, F. Petersen, A. Kukleva, B. Schiele, and H. Kuehne, "Learning by sorting: Self-supervised learning with group ordering constraints," in Proc. International Conference Computer Vision (ICCV), 2023.
[8] R. Swezey, A. Grover, B. Charron, and S. Ermon, "Pirank: Learning to rank via differentiable sorting," in Proc. Neural Information Processing Systems (NeurIPS), 2021.
[9] T. Thonet, Y. G. Cinar, E. Gaussier, M. Li, and J.-M. Renders, "Listwise learning to rank based on approximate rank indicators," in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 36, 2022, pp. 8494-8502.
[10] P. Jain, P. Kar, el al., "Non-convex optimization for machine learning," Foundations and Trends in Machine Learning, vol. 10, no. 3-4, pp. 142-363, 2017.
[11] F. Petersen, C. Borgelt, H. Kuehne, and O. Deussen, "Monotonic differentiable sorting net- works," " in Proc. International Conference on Learning Representations (ICLR), 2022.
[12] P. Bachman, R. Hjelm, and W. Buchwalter. "Learning representations by maximizing mutual information across views," Proc. Neural Information Processing Systems (NeurIPS), 2019.
[13] F. Petersen, "Learning with differentiable algorithms, " Ph.D. dissertation, Universität Konstanz, 2022.
[14] S. Liu, T. Li, W. Chen, and H. Li, "Soft Rasterizer: A Differentiable Renderer for Image-based 3D Reasoning," in Proc. International Conference on Computer Vision (ICCV), 2019.
[15] W. Chen, J. Gao, H. Ling, et al., "Leearnigg to predict 3D objects with an interpolation-basel differentiable renderer," " in Proc. Neural Information Processing Systems (NeurIPS), 2019. [16] F. Petersen, B. Goldluecke, C. Borgelt, and O. Deussen, "GenDR: A Generalized Differentiable Renderer," in Proc. International Conference on Computer Vision and Pattern Recognition (CVPR), 2022.
[17] C. Burges, T. Shaked, E. Renshaw, et al., "Learning to rrank using gradient descent," in Proc. International Conference on Machine Learning (ICML), 2005.
[18] M. Taylor, J. Guiver, S. Robertson, and T. Minka, "Softrank: Optimizing non- non-smooth rank metrics," in Proceedings of the 2008 International Conference on Web Search and Data Mining, 2008.
[19] M. Rolinek, V. Musil, A. Paulus, M. Vlastelica, C. Michaelis, and G. Martius, "Optimizing rank-based metrics with blackbox differentiation." in Proc. International Conference on Computer Vision and Pattern Recognition ( (CVPR). 2020.
[20] A. Ustimenko and L. Prokhorenkova, "Stochasticrank: Global optimization of scale-free discrete functions," " in Proc. International Conference on Machine Learning (ICML), 2020,
[21] Q. Berthet, M. Blondel, O. Teboul, M. Cuturi, J.-P. Vert, and F. Bach, "Learning with Differ- entiable Perturbed Optimizers," in Proc. Neural Information Processing Systems (NeurIPS), 2020.
[22] M. Vlastelica, A. Paulus, V. Musil, G. Martius, and M. Rolinek, "Differentiation of blackbox combinatorial solvers," in Proc. International Conference on Learning Representations (ICLR), 2020.
[23] Y. Xie, H. Dai, M. Chen, et al., "Differentiable top-k with optimal transport," in Proc. Neural Information Processing Systems (NewrIPS), 2020.
[24] F. Petersen, C. Borgelt, H. Kuehne, and O. Deussen, "Learning with algorithmic supervision via continuous relaxations," in Proc. Neural Information Processing Systems (NeurIPS), 2021.
[25] N. Agarwal, B. Bullins, and E. Hazan, "Second-Order Stochastic Optimization for Machine Learning in Linear Time," Journal of Machine Learning Research (JMLR), 2017.
[26] J. Martens and R. Grosse, "Optimizing neural networks with Kronecker-factoned approximate curvature," in Proc. International Conference on Machine Learning (ICML), 2015.
[27] T. Schaul, S. Zhang, and Y. LeCun, "No more pesky learning rates," in Proc. International Conference on Machine Learning (ICML), 2013.
[28] E. Frantar, E. Kurtic, and D. Alistarh, "M-FAC: Efficient matrix-free approximations of second-order information." in Proc. Neural Information Processing Systems (NeurIPS), 2021.
[29] A. Botev, H. Ritter, and D. Barber, "Practical Bauss-Newton optimisation for deep learning." " in Proceedings of the 34th International Conference on Machine Learning, ser. Proceedings of Machine Learning Research, PMLR, 2017.

---

[30] N. Shazeer and M. Stern. "Adafactor: Adaptive learning rates with sublinear memory cost," in Proceedings of the 35th International Conference on Machine Learning, ser. Proceedings of Machine Learning Research, PMIR, 2018, pp- 4596-4604.
[31] J. Nocedal and S. Wright,, Numerical Optimization. Springer New York, 2006.
[32] W. Li and G. Montúfar, "Natural gradient via optimal transport," Information Geometry, vol. 1,
Pp. 181-214, 2018.
[33] W. Li, A. T. Lin, and G. Montúfar, "Affine natural proximal learning," in Geometric Science of Information: 4th International Conference, GSI 2019, Toulouse, France, August 27-29, 2019, Proceedings 4, Springer, 2019, pp. 705-714.
[34] F. Dangel, F. Kunstmer, and P. Hennig. "BackPACK: Packing more into backprop." in Proc. In- ternational Conference on Learning Representations (ICLR), 2020.
[35] N. Wadia, D. Duckworth, S. S. Schoenholz, E. Dyer, and J. Sohl- Sall-Dickttein, "Whitening and second order optimization both make information in the dataset unusable during training, and can reduce or prevent generalization," in Proc. International Conference on Machine Learning (ICML), 2021.
[36] F. Kunstner, L. Balles, and P. Hennig, "Limitations of the empirical Fisher approximation for natural gradient descent," in Proc. Neural Information Processing Systems (NeurlPS), 2019.
[37] A. Grover, E. Wang, A. Zweig, and Ermon, "Stochastic Optimization of Sorting Networks via Continuous Relaxations," in Proc. International Conference on Learning Representations (ICLR), 2019.
[38] C. J. Burges, R. Ragno, and Q V. Le, "Learning to rank with nonsmooth cost functions," in Proc. Neural Information Processing Systems (NeurIPS), 2007.
[39] H. Lee, S. Cho, Y. Jang, J. Kim, and H. Woo, "Differentiable ranking metric using relaxed sorting for top-k recommendation"" IEEE Access, 2021.
[40] S. Prillo and J. Eisenschlos, "Softsort: A continuous relaxation for the argsort operator," in Proc. International Conference on Machine Learning (ICML), 2020.
[41] J.-B. Cordonnier, A. Mahendran, A. Dosovitskiy, D. Weissenborn, J. Uszkoreit, and T. Un- terthiner, "Differentiable patch selection for image recognition," in Proc. International Confer- ence on Computer Vision and Pattern Recognition (CVPR), 2021.
[42] K. Goyal, G. Neubig, C. Dyer, and T. Berk-Kirkp,, "A continuous relaxation of beam search for end-to-end training of neural sequence models," " in AAAI Conference on Artificial Intelligence, 2018.
[43] A. Vauvelle, B. Wild, R. Eils, and S. Denaxas, "Differentiable sorting for censored time-to- event data," " in ICML 2023 Workshop on Differentiable Almost Everything: Differentiable Relaxations, Algorithms, Operators, and Simulators, 2023.
[44] F. Petersen, C. Borgelt, A. Mishra, and S. Ermon, "Generalizing stochastic smoothing for diffcrentiation and gradient estimation," " Computing Research Repository (CoRR) in arXiv, 2024.
[45] Kato, Y. Ushiku, and Harada, "Neural 3D mesh renderer," in Proc. International Confer- ence Computer Vision and Puttern Recognition (CVPR), 2018.
[46] F. Petersen, A. H. Bermano, O. Deussen, and D. Cohen-Or, "Pix2Vex: Geeemety Reconstruction using a Smooth Differentiable Renderer," Computing Research Repository (CoRR) in arXiv, 2019.
[47] F. Petersen, B. Goldluecke, O. Deussen, and H. Kuehne, "Style agnostic 3d reconstruction via adversarial style transfer," in IEEE Winter Conference on Applications of Computer Vision (WACV), 2022.
[48] Y. Hu, L. Anderson, T.-M. Li, et al., 'DiffTaich;: Differentiable Programming for Physical Simulation," in Proc. International Conference on Learning Representations (ICLR), 2020.
[49] J. Ingraham, A. Riesselman, C. Sander, and D. Marks, "Learning protein structure with differentiable simulator," in Proc. International Conference on Learning Representations (ICLR), 2018
[50] H. Byrd, L. Hansen, Nocedal, and Singer, "A Stochastic Quasi-Newton Method for Large-Scale Optimization," SIAM Journal on Optimization, 2016.
[51] A. Mokhtari and A. Ribeiro, "Global Convergence of Online Limited Memory BFGS." Journal of Machine Learning Research (JMLR), 2015.
12

---

[52] M. Pilanci and M. J. Wainwright, "Newton Sketch: A Near Linear-Tinee Optimization Algo-
rithm with Linear- Quadratic Convergence." " SIAM Journal on Optimization. 2017.
[53] F. Petersen, T. Sutter, C. Borgelt, et al., "Isaac newton: Input-based approximate curvature for newton's method," in Proc. International Conference Learning Representations (ICLR), 2023.
[54] N. Doikov, K. Mishchenko, and Y. Nesterov, "Super--uiversal regularized newton method,"
SIAM Journal on Optimization, vol. 34, no. I, pp. 27-56, 2024.
[55] J. Martens, "New insights and perspectives on the natural gradient method," Journal of Machine Learning Research (JMLR), 2020.
[56] J. Kiefer and J. Wolfowitz, "Stochastic estimation of the maximum of regression function,"
The Annals of Mathematical Statistics, pp. 462-466, 1952.
[57] D. Kingma and J. Ba. "Adam: A method for stochastic optimization," in Proc. International Conference on Learning Representations (ICLR), 2015.
[58] A. Meulemans, Carzaniga, J. Suykens, J. Sacramento, and B. F. Grewe, "A theoretical framework for target propagation," Proc. Neural Information Processing Systems (NeurIPS), vol. 33, 2020.
[59] Y. Bengio, D.-H. Lee, J. Bornschein, T. Mesnard, and Z. Lin, "Towards biologically plausible deep learning." Computing Research Repository (CoRR) in arXiv, 2015.
[60] Bengio, "How auto-encoders could provide credit assignment deep networks via target propagation," Computing Research Repository (CoRR) in arXiv, 2014.
[61] D.-H. Lee, S. Zhang, A. Fischer, and Y. Bengio, "Difference target propagation," in Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2015, 2015.
[62] T. Frerix, Möllenhoff, M. Moeller, and D. Cremers, "Proximal backpropagation." in Proc. In- ternational Conference on Learning Representations (ICLR), 2018.
[63] A. N. Tikhonov and V. Y. Arsenin, Solutions of Ill-posed problems. W.H. Winston, 1977.
[64] J. Abemethy, C. Lee, and A. Tewari, "Perturbation techniques in online learning and optimiza- tion," Perturbations, Optimization, and Statistics, 2016.
[65] M. Blondel, A. F. Martins, and V. Niculae, "Learning with Fenchel-Young losses," Journal of Muchine Learning Reseurch (JMLR), 2020.
[66] M. A. Woodbury, "Inverting modified matrices," Memorandum report, vol. 42, no. 106, p. 336,
1950.
[67] D. E. Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching (2nd Ed.) Addison Wesley, 1998.
[68] R. Bellman, "On routing problem." Quarterly of Applied Mathematics, vol. 16, no. 1, pp. 87-
90, 1958.
[69]
L. R. Ford Jr, "Network flow theory." 1956.
[70] Y. LeCun, C. Cortes, and C. Burges, "Mnist handwritten digit database," " 2010. [Online].
Available: http: /yannn /lc.unnnneennnnn......m lecun. com/ con/exdb/mmist.
[71] A. Paszke, S. Gross, F. Massa, et al., "Pytorch: An imperative style, high-performance deep learning library," " in Proc. Neural Information Processing Systems (NeurIPS), 2019.
[72] A. Agrawal, B. Amos, S. Barratt, S. Boyd, S. Diamond, and J. Z. Kolter, "Differentiable convex optimization layers," in Proc. Neural Information Processing Systems (NeurIPS), 2019.
13

---

Appendix
Table of Contents
A Characterization of Meaningful Settings for Newton Losses
14
B Algorithmic Supervision Losses
14
B.1 SoftSort and NeuralSort
14
DifiSort ...
B.3 AlgoVision
15
B.4 Stochastic Smoothing
15
B.5 Perturbed Optimizers with Fenchel- Young Losses
16
C Hyperparameters and Training Details
16
C.I Hyperparameter lambda
17
C.2 List Assets
D Runtimes
17
E Equivalences under the Split
18
F Woodbury Matrix Identity for High Dimensional Outputs
20
InjectFisher for CVXPY Layers
20
Gradient Visualizations
21
A
Characterization of Meaningful Settings for Newton Losses
For practical purposes, decide whether applying Newton Losses is expected improve results, recommend that loss l fulfills the following 3 minimal criteria:
non-convex.
(ii) smoothly differentiable,
(iii) cannot be solved by single GD step.
Regarding (ii), the stochastic smoothing formulation enables any non-differentiable function (such as Shortest-paths considered in this work) to become smoothly differentiable.
Regarding (iii), we note that, e.g., for the MSE loss, the optimum of the loss (when optimizing loss inputs) can be found using a single step of GD (see last paragraph of Section 3.2). For the cross-entropy classification loss, single GD step leads to the correct class.
B Algorithmic Supervision Losses
In this section, extend the discussion of SoftSort, DiftSort, AlgoVision, and stochastic smoothing.
B.1 SoftSort and NeuralSort
SoftSort [40] and NeuralSort [37] are prominent yet simple examples of differentiable algorithm. In the case of ranking supervision, they obtain array vector of scalars and return row-stochastic matrix called the differentiable permutation matrix P. which a relaxation of the argsort operator. Note that, in this case, set of inputs yields scalar for each image and thereby y E I As
14

---

ground truth label, ground truth permutation matrix Q is given and the loss between P and Q is the binary cross entropy loss (ss(y) BCE (P(y), Q). Minimizing the loss enforces the order of predictions to correspond to the true order, which is the training objective. SoftSort is defined as
P(y) softmax y e sort(v) /T) = softmax (- y + /T)
(12)
where is temperature parameter, "sort" sorts the entries of vector in non-ascending order, @ is the clement-wise broadcasting subtraction, is the element-wise absolute value, and "softmax" is the row-wise softmax operator. NeuralSort is defined similarly and omitted for the sake of brevity. In the limit of + 0, SoftSort and NeuralSort converge to the exact ranking permutation matrix [37]. [40]. A respective Newton loss can be implemented using automatic differentiation according to Definition or via the empirical Fisher matrix using Definition
B.2 DiffSort
Differentiable sorting networks (DSN) [5], [11] offer strong alternative to SoftSort and NeuralSort. They are based on sorting networks, classic family of sorting algorithms that operate by conditionally swapping elements [67]. As the locations of the conditional swaps are pre-defined, they are suitable for hardware implementations, which also makes them especially suited for continuous relaxation. By perturbing a conditional swap with a distribution and solving for the expectation under this perturbation in closed-form, we can differentiably sort a set of values and obtain a differentiable Houbly-stochastee permutation matrix P. which can be used via the BCE loss as in Section B. We can obtain the respective Newton loss either via the Hessian computed via automatic differentiation or via the Fisher matrix.
B.3 Algo Vision
Algo [24] is a framework for continuously relaxing arbitrary simple algorithms by perturbing all accessed variables with logistic distributions. The method approximates the expectation value of the output of the algorithm in closed-form and does not require sampling. For shortest-pate supervision, we use a relaxation of the Bellman-Ford algorithm [68]. [69] and compare the predicted shortest path with the ground truth shortest path via an MSE loss. The input to the shortest path algorithm is cost embedding matrix predicted by neural network.
B.4 Stochastic Smoothing
Another differentiation method is stochastic smoothing [64]. This method regularizes a non- differentiable and discontinuous loss function E(y) by randomly perturbing its input with random noise e (i.e., Ely + e)). The loss function is then approximated as E(y) (z E.[[(y e)]- While l may be non-differentiable, its smoothed stochastic counterpart L, is differentiable and the corresponding gradient and Hessian can be estimated via the following result.
Lemma (Exponential Family Smoothing, adapted from Lemma 1.5 Abernethy et al. [64]). Given distribution over I with probability density function y of the form put)) = exp(-v(e)) for any twice-lifferentiable v, then
for
Vylc(v) B, [e + e)] = ()
(13)
Vol(() V9E, [e(y + e)]
= -E,[elue +) (VarleVevle)-
(14)
variance-reduced form of (13) and (14) is
Eg [e(y +c] = E. + e) -(y))) v.vlc]]. VJE, [Cly +)] E.
(15)
( (ely - ((x)) (V. (VeuleV..lee)- (Vur))eee))-VVett) -(v(e))
(16)
In this work, we use this to estimate the gradient of the shortest path algorithm. By including the second derivative, we extend the perturbed optimizer losses to Newton losses. This also lends itself to full second-order optimization.
15

---

B.4.1 SS of Algorithm
SS of algorithm is extension of this formulation, where stochastic smoothing is used to compute the Jacobian of the smoothed algorithm, e.g., 14 + R144 and the loss is, e.g., {(y) MSE(f label). Here, we can backpropagate through MSE and can apply stochastic smoothing to onlly. (The idea being that for many samples, it is better to estimate the Jacobian rather than the gradient of smoothing the entire loss.) While computing the Jacobian of f is simple with stochastic smoothing, the Hessian here would be of size 144 x 144 x 144 x 144, making it infeasible to estimate this Hessian via sampling.
B.5 Perturbed Optimizers with Fenchel-Young Losses
Berthet et al. [21] build on stochastic smoothing and Senchel-Young losses [65] propose perturbed optimizers with Fenchel- Yeunhel-Young losses. For this, they use algorithms, like Dijkstra, to solve optimiza- tion problems of the type maxwec (y, w), where denotes the feasible set, e.g.. the of valid paths. Berthet et al. [21] identify the argmax to be the differential of max, which allows a simplification of stochastic smoothing. By identifying similarities Fenchel- Penchel-Young losses, they find that the gradient of their loss is
V Vyl(y) = E. arg max + w) w WEC
(17)
where w* is the ground truth solution of the optimization problem (e.g., shortest path). This formulation allows optimizing the model without the need for computing the actual value of the loss function. Berthet al. [21] find that the number of samples--surrrisinnns--oool has small impact on performance, such that 3 samples were sufficient in many experiments, and in some cases even single sample was sufficient.
this work, we confirm this behavior and also compare to plain stochastic smoothing. We find that for perturbed optimizers, the number of samples barely impacts performance, while for stochastic smoothing more samples always improve performance. only few samples can be afforded (like 10 or less), perturbed optimizers are better as they are more sample efficient; however, when more samples are available, stochastic smoothing is superior can utilize more samples better.
C Hyperparameters and Training Details
Sorting and ranking. 100,000 training steps with Adam and learning rate 0.001. Same convolu- tional network as in all prior works on the benchmark: Two convolutional layers with a kernel size of 5x5, 32 and 64 channels respectively, each followed by a ReLU and MaxPool layer; after flattening. this is followed by fully connected layer with size of 64, ReLU layer, and fully connected output layer mapping to a scalar.
NeuralSort
Temperature T 1.0 [Best for baseline from grid 0.001, 0.01, 0.1, 1, 10]
SoftSort
-Temperature 0.1 [Best for baseline from grid 0.001, 0.01, 0.1, 1, 10]
Logistic DSN
-Type: odd_even
Inverse temperature
*
For n 5: 3 = 10 [Best for baseline from grid 10, 15, 20]
* For n = 10: 8 = 10 [Best for baseline from grid 10, 20, 40)
Cauchy DSN
Type: odd_even
- Inverse temperature
For 5: B 10 [Best for baseline from grid 10, 100)
* For 10: B -100 [Best for bascline from grid 10, 100]
16

---

Model, Optimizer, LR schedule, and epochs same as in prior work: First block of ResNet18, Adam optimizer, training duration of 50 epochs, and learning rate decay by a factor of 10 after 30 and 40 epochs each.
Shortest-path.
AlgoVision:
3 = 10
n_ itte=118
(number iterations in for loop max num iteration algovision while loop)
t_conorm= ppobaailisticcc
Initial learning rate, for each (as it varies between for/while loop and L1/L2 loss), best among [1, 0.33, 0.1, 0.033, 0.01, 0.0033, 0.001].
SS of loss algorithm:
Distribution: Gaussian with 0.1
[best on factor 10 exponential grid for baseline]
Initial LR: 0.001
PO / FY loss:
Distribution: Gaussian with a = 0.1
[best on factor 10 exponential grid for baseline]
Initial LR: 0.01
C.1 Hyperparameter
For the experiments in the tables, select À based one seed from the grid À [0.001, 0.01, 0.1, 1, 10, 100, 100, 1000, 3000). For the experiments in Tables and 5, we present Tikhonov
the values in the Tables 4 and 5, respectively. For the experiments in Table 2, regularization strength of X = 1000 for the L1 variants and À = 3000 for the L3 variants.
Table 4: Tikhonov regularization strengths for the experiment in Table
n
10
NeuralSort SoftSort Logistic DSN Cauchy DSN NeuralSort SoftSort Logistic DSN Cauchy DSN
(Hessian)
0.01
10
0.1
0.01
(Fisher)
A 0.1
10
0.1
100
100
Table 5: Tikhonov regularization strengths for the experiment in Table 3.
Loss Samples
of loss
3 algorithm
w/ loss
30
3
NL (Hessian)
À = 1000 À 1000
A= = 1000
= 1000 X 1000 À 1000
NL (Fisher)
À = 0.1
À 0.1
À == 0.1
A= 1000 À == 1000 x = 1000 A = 1000 X 1000 À = 1000
C.2
List of Assets
Multi-digit MNIST [37], which builds MNIST [70] [MIT License / CC License]
Warcraft shortest-path data set [22] [MIT License]
PyTorch [71] [BSD 3-Clause License]
D Runtimes
In this supplementary material, provide and discuss runtimes for the experiments. All times are of full training on a single A6000 GPU.
In the differentiable sorting and ranking experiment, shown in Table 6, we observe that the runtime from regular training compared to the Newton loss with the Fisher only marginally increased. This is because computing the Fisher and inverting it is very inexpensive. We observe that the Newton loss
17

---

with the Hessian, however, is more expensive: due to the implementation of the differentiable sorting and ranking operators, we compute the Hessian by differentiating each element of the gradient, which makes this process fairly expensive. An improved implementation could make this process much faster. Nevertheless, there is always some overhead to computing the Hessian compared to the Fisher.
Table 6: Runtimes [h:mm] for the differentiable sorting results corresponding Table 1.
Yi
Y
DSN
NeuralSort SoftSort
DSN
NeuralSort SoftSort
Bascline
1:10
1:02
1:01
1:43
1:27
1:24
NL (Hessian)
2:24
1:07
1:10
6:17
1:42
1:40
NL (Fisher)
1:11
1:03
1:02
1:44
1:27
1:25
In Table 7, show the runtimes for the shortest-path experiment with AlgoVision. Here, we observe that the runtime overhead is very small.
Table 7: Runtimes [h:mm] for the shortest-pal path results corresponding to Table 2.
Algorithm Loop
For
While
Loss
L1
L3
L1
L3
Baseline
0:10
0:10
0:15
0:15
NL (Fisher)
0:10
0:11
0:15
0:15
In Table 8, we show the runtimes for the shortest-par -atth experiment with stochastic methods. Here, we observe that the runtime overhead is also very small. Here, the Hessian is also cheap compute is not computed with automatic differentiation.
Table 8: Runtimes [h:mm] for the shortest path results corresponding to Table 3.
Loss
SS of loss
SS of algorithm
PO w/ FY loss
# Samples
3
10
30
3
10
30
10
30
Baseline
0:15 0:23
0:53
0:15
0:23
0:53
0:11
0:19
0:49
NL (Hessian)
0:15
0:23
0:53
0:11
0:19
0:50
NL (Fisher)
0:15 0:23
0:54
0:15
0:23
0:53
0:19
0:50
80
NL (Hessian)
NL (Fisher)
75
Baseline
Acc. [%]
70
65
60
55
0
250
500
750 Time [s]
1000
1250
Figure 5: Training time plot corresponding to Figure 3: Test accuracy (perfect matches) plot for 'SS of loss' with 10 samples on the Warcraft shortest path benchmark.
E Equivalences under the Split
Using gradient descent step according to (1) is equivalent to using two gradient steps of the alternating scheme (2), namely one step for (2a) and one step for (2b). This has also been considered by [62] in a different context.
Lemma 2 (Gradient Descent Step Equality between (1) and (2a)+(2b)). A grudient descent step according to (1) with arbitrary step size n coincides with two grudient descent steps, one according to (2a) and one according (2b), where the optimization over has a step size of n and the optimization over has unit step size.
18

---

Proof. Let 9 E + be the current parameter vector and let z f(x: 8). Then the gradient descent
steps according (2a) and (2b) with step sizes and 17 > are expressed as
2 レ V, {(z) = [(x; V, {(((xx)))
(18)
-
1 Vo 1 [(x;
0 s [x; 0)
?
(f(x; 0) - 2)
(19)
00
Combining (18) and (19) leads to
1 f(x: 8)
0 - 0
((xx ((((x 0))
00
= - (x)(((x))),
(20)
which is exactly a gradient descent step starting at A E θ with step size y7-
Moreover, we show that a corresponding equality also holds for a special case of the Newton step. Lemma 3 (Newton Step Equality between (1) and (2a)+(2b) for m = 1). In the case of m = (i.e., a one- dimensional output), a Newton step according to (1) with arbitrary step size nj coincides with two Newton steps, one according to (2a) and one according to (2b), where the optimization over 0 has a step size of 1i and the optimization over 2 has a unit step size.
Proof. Let 0 E θ be the current parameter vector and let z = f(x; 0). Then applying Newton steps according to (2a) and (2b) leads
z + z - (V (z)) VV, ((z)
= f(x; 0) - (V)((((x(0))) (V
(21)
1
1
8
n
V 1z f(x: 0)]
vo2 Iz f(x((xx))
(22)
0
1 ss((x;) 0)
= -)(x
(f(x; -2) -2)
0 0x(xx0)
0 1
(f(x:0) z)
(23)
00
00
00
(x: 0]
()(x;0))))) (0 (Df(x:0) 0)2 20)
0 f((x 0)
= 0 - 7
(f(x;0)- -2)
00
00
00
00
Inserting (21), we can rephrase the update above as
a
[(x: 0)
(9((((x00)))) + (D1(x:0) 2
0 - 0
7
00
00
00
(24)
fxx #)
00
By applying the chain rule twice, we further obtain
v)e(((x00))
θ
O fx(x00 0)
[e([(x:0))
00
00
0
a
f(x:0) 8)
0x 0
))((f(x:0) 0))
v)((((x0)
00
00
00
00
a f(x: 0)
V v((((xx0)) 0f(x;0) 0)
V 11 ((((x())
00
00
00
a [x((x;0 0)
))((((x00) + (0](x:0)
( V)(({(x;0))
00
00
which allows us to rewrite (24) as
8' = - (17)((((::)) - 0
0)),
which is exactly single Newton step starting at 0 O
19

---

Woodbury Matrix Identity for High Dimensional Outputs For the empirical Fisher method, where Nx is computed via
- Us ( Σラ
(())
9. (())
for all e [I, and y fx: 0). simplify the computation via the Woodbury matrix identity [66]. In particular, we can simplify the computation of the inverse to
N - Vo, (()) V (()) +X-1)
(25)
1 N Vyl(y) Vy((F) +X.1)"
(26)
Im N. Vyl(y) (Nx V + IN) +N)= Vy((y).
(27)
This reduces the cost of matrix inversion from (mm)) down to O(N3). We remark that this variant only helpful for cases where the batch size is smaller than the output dimensionality m.
Further, we remark that in a case where the output dimensionality m and the batch size N are both very large, i.e., the cost of the inverse is typically still small comparison to the computational cost of the neural network. To illustrate this, the dimensionality of the last hidden space (i.e., before the last layer) hú is typically larger than the output dimensionality m. Accordingly, the cost of only the last layer itself is ONN m h4). which is typically larger than the cost of the inversion in Newton Losses. In particular, assuming h4 > m, O(N m ht) > O(min(m, S)
We remark that the Woodbury inverted variation can also be used in Inj InjectFisher.
G InjectFisher for CVXPY Layers
In this section, we provide an extension the presented method, from algorithmic losses to optimizing the parameters in differentiable convex optimization layers [72]. For this, we utilize the cvxpylayers framework, and, as proof of concept apply it to the training of a 3-layer network, where the first layers are modelled via cvxpylayers: https://githe: hwwp:///////g/p////////////eeee htt.a//rr///bbbbtm/////rr//////e
http////ttoorr//ee////aaaaarz iipybb.
Because there are no Hessians or second-order derivatives available in cvxpylayers. we ap- plied the empirical Fisher variant, via the InjectFisher function, cvxpylayers. We apply SejectFisher to (the vector of) all weights and biases of given layer, and choose À = 0.1.
We ran it for 5 seeds, and the loss improves in each case (see Table 9). Importantly, note that these are paired results (only networks with the same initialization are comparable).
Table 9: Loss of cvxpylayers model. Results comparable only within each seed.
Seed
cvxpy
cvxpy InjectFisherr
1
0.322
0.185
2
0.186
0.157
3
0.522
0.247
4
0.225
0.179
5
0.260
0.211
20

---

H Gradient Visualizations
9.5
34
9.4
A
8,80
0.0
-5.0
As- -5.0
3.4
4,..4.3
2x 210
Av: 8.0
12.12.
Aum 12.0
-05
NeuralSort gradients in dependence of
Logistic DSN gradients in dependence of 21
20300
5020
2020
-2050
-10000
10.0
-1000
-15.0
8.5
16.0
AL: 16.0
26.0
K:: 24.0
(c) NeuralSort gradients (larger spread)
(d) Logistic DSN gradients (larger spread)
0.04
0.02
0, 61
0.50
3:00
0.02
-3.05
10.0
10.0
-2.54
Xt. 16.0
16.0
24.0
26.0
(e) Newton gradients (empirical Fisher) for Neu- ralSort (larger spread)
(f) Newton loss gradients (empirical Fisher) for Logis- tic DSN (larger spread)
Figure 6: We illustrate the gradient of the NeuralSort and logistic DSN losses in dependence of one of the five input dimensions for the exploding gradients when inputs are too away from each other (which temperature r), 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 empirical Fisher Newton Loss recovers from the exploding gradients experienced in (c) / (d). The input examples simplification actual inputs, as here, 2n, I2, 23, 44 are already their correct order, and having multiple disagreements makes the loss more chaotic.
case. the illustrated example, one can observe that both algorithms experience
controllable steepness
21

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
We address all claims made in the abstract and introduction in the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Limitations are discussed throughout this work. See also Section for characterization of settings where Newton Losses meaningful.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: All assumptions are stated and the proofs are included alongside the lemmas. We do not repeat the proof the lemma from [64].
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Answer: [Yes]
Justification: We discuss all experimental details necessary for reproduction in Section C.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results?
Answer: [Yes]
Justification: All data openly accessible. Our implementation is openly available at gittublcco/Feiii..ccceeeeeeeeoon
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: See Section C.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Yes. for all results tables, include standard deviations, We further provide statistical significance tests. In particular, we utilize Welch's t-test, which is an adaptation of the Student's t-test for cases with unequal variances of populations (sets of results) and thus suitable for these experiments, also making it more reliable than vanilla Student's 's t-test. We utilize significance level of 0.05, which standard in machine learning.
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed reproduce the experiments?
22

---

Answer: [Yes]
Justification: Runtimes and hardware are discussed in Section D.
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: /tt::///euuure /wwrrps.....p//e cc/ c//ppblicc/thicccssilelllllleee
Answer: [Yes]
Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper comprises fundamental research.
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (c.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: All assets cited. See Section C.2.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
23


Reviews:
[{"review_id": "dMFzDesEyL", "reviewer": "Reviewer_qoSU", "summary": "The paper proposes a new method to optimize complex possibly non-smooth and algorithmic losses for neural networks. The approach is based on splitting the problem into two-step procedure, where in the first step we construct and optimize the so-called Newton loss and the second step is based on SGD-type procedure for MSE loss with the first step. The authors present a wide experimental comparison of the proposed Fisher and Newton approaches with existing methods.", "questions": "See Weaknesses", "limitations": "n/a", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "The paper has a strong literature review and motivation for solving different applications. The experimental section is well described, it contains 4 different non-trivial problems to solve. For the presented cases, the proposed methods outperform the baselines.", "weaknesses": "The paper does not contain any proofs or convergence guarantees. The mathematical formulation of the main problem is also quite confusing for me.  For example, is vector $x$ fixed for all steps or is it a batch of data?  Is it a sum-type problem or an expectation problem? What are the properties for $l(\\cdot)$? 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.  In Formulas 1 and 2, it is not clear what are the fixed parameters or data. Should $\\theta$ in 2a be $\\theta_{t-1}$? Also, I think the mention of Lemma 2 in the main text could be very helpful.\n\nFor 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. There are no convergence figures with the per-iteration or per-gradient performance. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n**Weaknesses**\n\n> The paper does not contain any proofs or convergence guarantees.\n\nIt 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.\nProviding 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.\n\n> For example, is vector $x$ fixed for all steps or is it a batch of data?\n\nWe 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.\n\n> Is it a sum-type problem or an expectation problem?\n\nWe 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.\n\n> 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.\n\nWe 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. \nFor 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. \nWe will clarify this in the revised version.\n\n> In Formulas 1 and 2, it is not clear what are the fixed parameters or data. Should $\\theta$ in 2a be $\\theta_{t-1}?\n\nThank you for spotting this typo. \nIndeed, in Equation (2a), $\\theta$ should be $\\theta_{t-1}$. We will fix it.\n\n> Also, I think the mention of Lemma 2 in the main text could be very helpful.\n\nThank you for the suggestion. We will provide a discussion of Lemma 2 in the main text in the revised version.\n\n> 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.\n\nThank you for this suggestion.\nAs 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.\n\n> There are no convergence figures with the per-iteration or per-gradient performance.\n\nCould you please clarify what precisely you would like us to plot, considering that we show a per-epoch convergence plot in Figure 3?\n\n> 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.\n\nThank you for this suggestion. \nOn these types of algorithmic loss benchmarks, to our knowledge, gradient clipping has not been previously considered in the literature.\nIf you do have a respective reference, we would greatly appreciate it.\nNevertheless, we have implemented gradient clipping for Table 1:\n\n| n    | NeuralSort | SoftSort | Logistic DSN | Cauchy DSN |\n|--|--|--|--|--|\n| n=5  | $73.79\\pm3.79 (88.23\\pm1.84)$ | $71.76\\pm1.39 (87.22\\pm0.64)$ | $61.28\\pm16.67 (81.54\\pm8.97)$ | $84.75\\pm0.54 (93.13\\pm0.30)$ |\n| n=10 | $25.02\\pm6.17 (74.56\\pm3.29)$ | $28.85\\pm6.20 (76.68\\pm3.05)$ |  $22.60\\pm1.54 (73.51\\pm0.87)$ | $54.30\\pm2.12 (86.65\\pm0.80)$ |\n\nThe results show consistent improvements for the first 3 algorithmic losses, but unfortunately it degrades Cauchy DSNs, even compared to the vanilla method.\nThese results are averaged over 5 seeds.\n**In each case, Newton Losses performs substantially better than gradient clipping.**\n\n\nPlease 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "RnJOOKw3Ip", "reviewer": "Reviewer_tok2", "summary": "The paper proposes second-order optimization with splitting for hard objectives that arise as smoothing of such hard problems as sorting and ranking to address the problem of vanishing/exploding gradients.", "questions": "1. 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\n2. 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.", "limitations": "Yes", "rating": 4, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "It is a well-written and very complete description of algorithms for reproducibility, which is a very good thing in itself.", "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", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n\n**Weaknesses**\n\n> 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\n\nThank you for this suggestion. We will include this paper in the related work.\nHowever, 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.\nWe will contact the authors regarding the source code, and if possible include these results in the camera-ready.\nNevertheless, 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).\n\n\n**Questions**\n\n> 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\n\nWe 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.\nWe also want to point out that we always include results with the empirical Fisher, which, by definition, is always positive semi-definite. \n\n> 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.\n\nAs 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).\nUsing the Adam optimizer is the established experimental setting on each of these benchmarks.\nIn Adam, the sign and relative magnitude of the gradient to the previous step are the important factors.\nThus, 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).\nAs 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.\n\n\n\n\n\n\nPlease 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "bPka2PtUyt", "reviewer": "Reviewer_nJzH", "summary": "The paper presents an alternative backpropagation scheme for deep learning with algorithmic losses that combines a preconditioned step on the loss with a gradient step on a least square objective. Two preconditioning methods are investigated: using the Hessian, or the empirical Fisher. Experiments demonstrate that the proposed plugin consistently improve performance of algorithms across architectures and losses on two benchmarks. An ablation study of the potential additional tikhonov regularization is give, as well as a discussion of runtime comparisons.", "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.\n- 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.\n- 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? \n- 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. Maybe one could correlate the number of steps taken by the underlying algorithm and the improved performance of the proposed approach.", "limitations": "Limitations (or rather scope) of the approach are discussed in Appendix A.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The main strength of the paper is its experimental evaluation. Two relevant benchmarks are analyzed. 4 losses are considered in the frist benchmark, 3 in the second benchmark. Ablation studies and runtime comparisons provide a rather full picture on the algorithm.\n- Overall the proposed method clearly provides gains across settings. Its theoretical motivation may be unclear but such experimental evidence invites for further research on the subject.", "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n\n**Weaknesses**\n\n> 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.\n\nIndeed 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). \n\nWe consider Section 3.2 to be rather a derivation of the method than a theory section with theoretical guarantees.\n\n\n**Questions**\n\n> 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.\n\nIn 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.\n\n> 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.\n\nThis 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.\n\nBeyond 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.\n\n> 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?\n\nFor 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. \n\nFor 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.\n\n> 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. \n\nTo illustrate the characteristics of the losses and their gradients, we provide 6 figures in the supplemental author response PDF page.\nWe illustrate the gradient of the NeuralSort and logistic DSN losses in dependence of one of the five input dimensions for the $n=5$ case.\nIn 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).\nFurther, we can observe that the gradients themselves can be quite chaotic, making the optimization of the loss rather challenging.\nIn Figures (e) / (f), we illustrate how using the Fisher Newton Loss recovers from the exploding gradients experienced in (c) / (d).\n\n> Maybe one could correlate the number of steps taken by the underlying algorithm and the improved performance of the proposed approach.\n\nWe 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.\n\n\nPlease 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
1 page rebuttal attachment: Illustrations of the gradient of the NeuralSort and logistic DSN losses.

Meta-review: Given my own evaluation of this work and taking into account the reviewer's expertise, I am recommending to accept this interesting submission.
Decision: Accept (poster)