Newton Losses: Efficiently Including Second-Order Information into Gradient Descent
Authors: Felix Petersen
Christian Borgelt
Tobias Sutter
Hilde Kuehne
Oliver Deussen
Venue: Submitted to ICLR 2023 (2023)
Keywords: differentiable algorithms
backpropagation
differentiable

Abstract: We present Newton losses, a method for incorporating second-order information of losses by approximating them with quadratic functions. The presented method is applied only to the loss function and allows training the neural network with gradient descent. As loss functions are usually substantially cheaper to compute than the neural network, Newton losses can be used at a relatively small additional cost. We find that they yield superior performance, especially when applied to non-convex and hard-to-optimize loss functions such as algorithmic losses, which have been popularized in recent research.

NEWTON LOSSES: EFFICIENTLY INCLUDING SECOND- ORDER INFORMATION INTO GRADIENT DESCENT
Anonymous authors Paper under double-bling review
ABSTRACT
We present Newton losses, method for incorporating second-order information losses by approximating them with quadratic functions. The presented method is applied only to the loss function and allows training the neural network with gradient descent. As loss functions are usually substantially cheaper to compute than the neural network, Newton losses can be used relatively small additional cost. We find that they yield superior performance, especially when applied to non-convex and hard-to-optimize loss functions such as algorithmic losses, which have been popularized in recent research.
INTRODUCTION
Neural network training has gained a tremendous amount of attention in machine learning in recent years. This is primarily due to the success of backpropagation and stochastic gradient descent for first- order optimization. However, there has also been a strong line of work on second-order optimization for neural network training; see (I) and references therein. While these second-order optimization methods (such as Newton's 's method and natural gradient descent) exhibit improved convergence rates and therefore require fewer training steps, they have two major limitations (2). namely (i) computing the curvature (or its inverse) for a 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 most cases; (ii) networks trained with second-order information exhibit reduced generalization capabilities 3
In this work, we propose novel method for incorporating second-order information of the loss func- tion into training, while training the actual neural network with gradient descent. As loss functions usually substantially cheaper to evaluate than neural network, the idea is to apply second-order optimization to the loss function while training the actual neural network with first-order optimiza- tion. For this, we decompose the original iterative optimization problem into two-stage iterative optimization problem, which leads to Newton losses. This is especially interesting for intrinsically hard-to-optimizz loss functions, i.e., where second-order optimization of the inputs to the loss is superior to first-order optimization. Such loss functions have recently become increasingly popular, as they allow for solving more specialized tasks such inverse rendering (4 (6). learning-to-rant (7)-
[33. self-supervised learning [14), differentiation of optimizers [15], [16]. and top-k supervision [9]
I1]. [7]. In this paper, we summarize these loss functions exceeding typical classification and
regression under the umbrella of algorithmic losses [18] as they introduce algorithmic knowledge
into the training objective.
We evaluate the proposed Newton losses for various algorithmic losses on two popular benchmarks: the four-digit MNIST sorting benchmark and the Warcraft shortest-path benchmark. We found that Newton losses improve the performance in case of hard-to-optimize losses and maintain the original performance in the case of casy-to-optimize losses.
Contributions. The contributions of this work are (i) introducing mathematical framework for splitting iterative optimization methods into two-stage schemes, which we show to be equal to the original optimization methods; (ii) introducing Newton losses combinations of first-order and second-order optimization methods; and (iii) an extensive empirical evaluation on two algorithmic supervision benchmarks using array of algorithmic losses.

---

1.1 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.c., losses which 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-rant works already appeared in the 2000s 77. (8. 19. but more recently (20) propose differentiable ranking metrics, and (12) propose PiRank, which relies on differen- tiable sorting. For differentiable sorting an array of methods has been proposed in recent years, which includes NeuralSort [21). SoftSort (22). Optimal Transport Sort (9). differentiable sorting networks (DSN) (T). and the relaxed Bubble Sort algorithm (18). Other works explore differentiable sorting- bosseng-based top-k for applications such as differentiable image patch selection [23). differentiable k-nearest- k-mearest-neighhorr [17). [2].. top-k attention for machine translation [17]. and differentiable beam
search methods [77]. [24. But algorithmic losses are not limited to sorting: other works have consid- ered learning shortest-paths [1].. 16), (18), learning 3D shapes from images and silhouettes [4-(6)) [8]. (25). , (26). learning with combinatoria solvers for NP-hard problems [16], learning classify handwritten characters based on editing distances between strings (18), learning with differentiable physics simulations (27). and learning protein structure with a differentiable simulator (28), among many others. The methods used to make algorithms differentiable can be broadly categorized into those, which estimate gradients via sampling (e.g.. (15) and those, which have analytical closed-form gradient estimates (e.g.. (18). In this work, we specifically focus on the tasks of ranking supervision and shortest-path supervision, and discuss the methods that we consider in detail in Section 4
Second-Order Optimization. Second-order methods have recently gained popularity in machine learning due to their fast convergence properties when compared first-order methods (T). One alternative to vanilla Newton are quasi-Newton methods, which, instead of computing inverse Hessian in the Newton step (which is expensive), approximate this curvature from the change in gradients 2). 22 (30]. In addition, number of new approximations the pre-conditioning matrix have been proposed in the recent literature, i.a., [3 [3]. While the vanilla Newton method relies on the Hessian, there variants which use the empirical Fisher information matrix, which can coincide in specific cases with the Hessian, but generally exhibits somewhat different behavior. For an overview and discussion of Fisher-based methods (sometimes referred as natural gradient descent), see 34] 35).
Decomposition Methods. When working with complex and non-standard loss functions, the opti- mization problem for neural network training is often challenging. In these cases, natural approach to look for a decomposition, i.c.. to break up the optimization problem into two (or more) sub- problems, which are then solved sequentially. The idea of decomposing an optimization problem is not new, see (36) for an overview of decomposition methods. A decomposition method, which has become particularly popular in machine learning. is the alternating direction method of multipliers (37). There are other decomposition methods known as operator splitting methods (38), which include the methods of multipliers with Gauss-Seidel passes [37] coordinate descent-type methods with
linear coupling constraints (2). or consensus based optimization schemes (39]. [40]. These methods typically derive optimization problems via Lagrangian duality that are then solved sequentially and
to the respective (global) optimality which requires loss functions that can be optimized at relatively
low cost. Moreover, convergence guarantees can be obtained if the underlying optimization problem is convex and the coupling constraints are linear. In this work, we consider problems where neither of these properties hold.
2 A TWO-STAGE OPTIMIZATION METHOD
We consider the training of a neural network f fax; f), where R is the vector of inputs, 0 E R is the vector of weights and y = f(x; 0) E I is the vector of outputs. We assume that we have access to data set of N samples drawn from the input distribution, which describes the empirical input x = [i...... xx I E R xx"_ As per vectorization, we denote = f(x; 8) E R Xm as the matrix describing the outputs of the neural network corresponding to the empirical inputs. Further, let N xm + R denote the loss function, and let the ground truth output be implicitly encoded
in (because for many algorithmic losses, it is not simply a label, but could be ordinal information).
2

---

In general setting, the training of neural network can be expressed as the optimization problem
arg min E(f(x: 6)), BEE
where θ C Rd is the domain of the parameters 6, and f and l are such that the minimum in [I exists. Note that the formulation ① is extremely general and includes, e.g., optimization of non- decomposable loss functions (i.e., not composed of individual losses per training sample), which is relevant for some algorithmic losses like ranking losses.
Typically, the optimization problem is solved by using some iterative algorithm like gradient descent (or Newton's method) updating the weights by repeatedly applying the following step:
0 One optimization step of {(f(x: 8)) wrt. A.
However, in this work, we consider decomposing the optimization problem (T) into two problems, which may be solved by applying the following two updates in an alternating fashion:
z + One optimization step of f(Z) wrt. z f(x; 0),
(3a)
0 + One optimization step of b|12²* - 0)12 wrt
(3b)
This split allows us later to use two different iterative optimization algorithms for (3a) and (3b). respectively. This is especially interesting for optimization problems where the loss function E is non-convex and its minimization a difficult optimization problem itself, and as such those problems, where a stronger optimization method exhibits superior rate of convergence.
We can express individual optimization steps (corresponding to (2 and 3ap) via
(4) where S2 is a regularizer such that one step of respective optimization method corresponds to the global optimum of the regularized optimization problems in (4). The regularizer Q has the standard property that (a, b) = 0 for any a = b. Note that the explicit form of the regularizer f2 does not need to be known. Nevertheless, in Supplementary Material C we discuss explicit choices of Ω.
< arg min {(f(x; 6')) + 2(6", 0) ('Ee
and z f arg min ((z) + 2(z, f(x; zEy
This allows us to express the set of points of convergence for the iterative optimization methods. Recall that an iterative optimization method has converged if has arrived at fixed point, i.e, the parameters do not change when applying an update. The set of points of convergence for ( is
A
0
arg min ((f(x; f)) + 220' .0)
(5)
6'
i.e., those points at which the update does not change 0. For the two-stage optimization method (3). the set of points of convergence is
{0 f(x: = E arg (imm(i()) ((z) Mzz f(x
(6)
as the method has converged if the update (3a) yields zt z because the subsequent update (3b) will not change 0 as zz z f(x; 0) already holds, and thus _ "|zz* fxx; 0) = O. Now, we show that the iterative method 2 and the alternating method (3) lead to the same sets of convergence points.
Lemma (Equality of the Sets of Convergence Points). The set A of points of convergence obtained by the iterative optimization method (2) is equal to the set B points of convergence obtained by the two-step iterative optimization method
Proof. (A C B) First, we show that any point in A also lies in B. By definition, for each point in A, the optimization step ( does not change 0, i.c., O' O. Thus, f(x: 0) fxx 0') arg min, {(z) + S(2 fx; 0)), and therefore 0 E B.
(B C A) Second, we show that any point in B also lies in A. For each B, we know that, by definition, fxx; 8) z arg min, f(z) + lZz. fxx; 0)), therefore f E arg ming ((f 8')) @(f(x: 8¹), fxx 8)) where ((f(x;)) f(x: 0)) 0 220, 8), and, therefore 0 A.
While Lemma states the equivalence of the original training 2 and its counterpart wrt. their possible points of convergence (i.e., solutions) for an arbitrary choice of the iterative method, the two approaches are also equal when applying standard first-order second-order optimization schemes. In other words, running a gradient descent step according to (2) coincides with two gradient steps of the alternating scheme Ba) and 33b) namely one step for (3a) and one step for (3b).
3

---

Theorem 2 (Gradient Descent Step Equality between 22) and Bal+ (bb). A gradient descent step according to 2 with arbirary step size ni coincides with two gradient descent steps, one according to (3a) and one according (3b). where the optimization over I has step size of 1n and the optimization over 2 has a unit step size. Proof deferred to SM
Theorem 3 (Newton Step Equality between 2 and 3a 3b for m = 1). In the case of m = 1, Newton step according to (2) with arbitrary step size lt coincides with two Newton steps, one according to (3a) and one according to (3b), where the optimization over 0 has a step size of 1 and the optimization over has a unit step size. Proof deferred to SMA
3 NEWTON LOSSES
In this section, we focus on the two-stage optimization method 33. and propose optimizing (3a) with Newton's 's method, while optimizing (3b) with stochastic gradient descent. Let us begin by considering the quadratic approximation of the loss function at the location y = f(x; 0), i.e.,
Ly(z) = { + (z - y) (yy + [ - y) y) (((())(2 y).
(7)
To find the location z' of the minimum of (z), we set its derivative to 0:
Valy(z") =0 + vyf(y) vZ yy) =0 Vyl(y) = -V - + - (V) Vyl(y) = -y
(8)
(9)
Thus, the minimum of (z(2)) is =rg
arg min, ( (z) y - (Vg)(((
When é is quadratic, it can be readily seen that xt is independent of the choice of y. For non- quadratic functions, we heuristically assume independence as z" is the projected optimum goal of the function f. In implementations, this independence sitop_gradient () Using z", we can derive the Newton loss l" as
be achieved using detach ()
(y) (z' y) Tz" y) 1 where
z'= arg min E (z)
(10)
and its derivative V y (y) y z' With this construction, we obtain the Newton loss tx new convex loss, which has gradient that corresponds the Newton step of the original loss.
Note that 10)) is an instance of (3) for regularization term describing the quadratic approximation error, i.e., (2 (x; 0)) = & (x.0)) - ((z). As Ω is already implicitly part of the Newton step, we do not need evaluate it.
In general, Cr exhibits more desirable behavior than E, as single gradient descent step can solve any quadratic problem, and it possesses the same convergence properties as the Newton method when optimizing y. In the case of non-convex f, as it is common for many algorithmic losses, the incorporation of second-order information also substantially improves empirical performance. Note that, in the case of non-convex ill-conditioned settings, using Tikhonov regularization [1 stabilizes ...
In the following, define Newton losses and use and 2² to denote samples / rows of x and z".
Definition 1 (Element-wiss. Hessian-based Newton losses). For loss function f, and a given current parameter vector 8, we define the element-wiss Hessian basee Newton loss as
E (v)
2 = vll.
where
2 = ÿ (V
and ÿ= f(;00)
However, instead using the dementt-wise Hessian-based Newton loss, it is typically more stable to the empirical Hessian-based Newton loss.
Definition 2 (Empirical Hessian-bart based Newton losses). For loss function e and given current parameter vector 0, we define the empirical Hessian-hased Newton loss as
C. (v) = 2 || - 2112. where 2 = E -
(EE (3((( Vg(()) and g = f(x;0)
4

---

Instead of using the Hessian, it also possible to use the Fisher information matrix for second-orde information. While this coincides with the Hessian in certain cases, in most cases it yields different results. The Fisher- based Newton loss can be seen using natural gradient descent for optimizing the loss, while using regular gradient descent for optimizing the neural network.
Definition 3 (Fisher-based Newton losses). For loss function E, and given current parameter vector 0, we define the Fisher-based Newton loss as
C. (v) 2 - u1l2, where 2 - ÿ (Ey V
ggll)) and ū - f(x;
Remark 1 (Computational Considerations). The Hessian of the loss function Vzely) may be approx- However as only the Hessian
imated using the empirical Fisher matrix F = Ey [Vy((y of the loss function (and not the Hessian of the neural network) needs be computed, computing the exact Hessian (ly) is usually also fast.
Remark 2 (Derivative of the Newton Loss). The derivative of the Newton loss is
8 ||=" 0y 2
v112 y z²
(11)
Note that the derivative of 2t wrt. y is zero because is the projected optimum of the original loss.
3.1 EXAMPLES
We have seen in (10) how a given loss function induces a corresponding Newton loss E* For specific loss functions, the Newton loss can explicitly computed. We begin with the trivial example the MSE loss. For notational simplicity we often drop the subscript x" in the definition of the Newton loss (TOp.
Example 1 (MSE loss). Consider the classical MSE loss, i.e., l(v) lly v" 11.. where y" denotes the ground truth. Then, =y and accordingly the Newton loss given as
(v) ([0)=11: 11 - u1
v12 f(y).
Therefore, the MSE loss and its induced Newton loss t are equivalent.
A popular loss function for classification is the softmax cross entropy (SMCE) loss, defined as
exp(y:
(SMCE(U) pi log q:
where
Ti Σ exp(v;)
(12)
Example 2 (Softmax cross-entropy loss). For the SMCE loss, the induced Newton loss is given as 1 where the element-wise Hessian variant is = (diag(a) (q) - 9q 1) (q p) + the empirical Hessian variant is 2²H Ey [diag(g) qq 1] -1 (g p) y, and the empirical Fisher variant is 27.- = Ey, [(g p) - p) 7| (q - p) +
SMCE (v) || y11
(13)
-1
In the experiments, we include a classification experiment with the SMCE loss. Additional examples of Newton losses can be found in the supplementary material.
ALGORITHMIC SUPERVISION LOSSES
In this section, we discuss how to derive the Newton losses for various types of algorithmic losses. Specifically, we consider SoftSort, DiffSort, Vigovn one-step Blackbox Differentiation, and stochastic smoothing. While all of these algorithmic losses can be used directly with Fisher-based Newton losses, the besssian-based Newton losses require an estimation the Hessian.
We consider the task of algorithmic supervision, i.e., problems where an algorithm is applied to the predictions of a model and only the outputs of the algorithm are supervised. Specifically, we focus on the tasks of ranking supervision and shortest-path supervision. As this requires backpropagating through conventionally din-dffferentialle algorithms, the respective approaches make the ranking or shortest-pal path algorithms differentiable such that they be used part of the loss function.
5

---

4.1 SOFTSORT AND NEURALSORT
SoftSort [22] and NeuralSort [21 are prominent yet simple examples of a differentiable algorithm. In the case of ranking supervision, they obtain array or vector of scalars and return row-stochastic matrix called the differentiable permutation matrix P. which is a relaxation of the argsort operator. Note that, in this case, a set of inputs yields a scalar for each image and thereby y E I As a 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 enforees the order of predictions to correspond to the true order, which is the training objective. SoftSort is defined as
P(y) = sofx (- y e sor /T) = softmax (- 1 e Syl/T) /T)
(14)
where is temperature parameter, "sort" sorts the entries of vector in non- non-ascenee -on-ascending order, @ is the element-wise broadcasting subtraction, | is the element-wise absolute value, and "softmax" is the row-wise softmax operator, as also used in (12) (right). NeuralSort is defined similarly and omitted for the sake of brevity. In the limit of T + 0, SoftSort and NeuralSort converge to the exact ranking permutation matrix [21). 22 A respective Newton loss can be implemented using automatic differentiation according to Definition 2 or via the Fisher information matrix using Definition B
4.2 DIFFSORT
Differentiable sorting networks (DSN) I. [13] offer strong alternative to SoftSort and NeuralSort. They are based sorting networks, classic family of sorting algorithms that operate by conditionally swapping elements (42). 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 differentially sort a set of values and obtain a differentiable doubly-stochasee
permutation matrix P, which can be used via the BCE loss as in Section 4. We can obtain the respective Newton loss either via the Hessian computed via automatic differentiation or via the Fisher information matrix.
4.3 ALGOVISION
Algo [T8) 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-pati
supervision, we use a relaxation of the Bellman-Ford algorithm [43), (44) 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.
4.4 STOCHASTIC SMOOTHING
This method regularizes a non- differentiable and discontinuous loss function E(y) by randomly perturbing its input with random noise (i.e., E(y c)). The loss function is then approximated as E = (v) = [. +)]. While é is not differentiable, its smoothed stochastic counterpart & is differentiable and the corresponding gradient and Hessian can be estimated via the following result.
Another differentiation method is stochastic smoothing 45
Lemma 4 (Exponential Family Smoothing, adapted from Lemma 1.5 in Abernethy et al. (45) ). Given distribution over T.T with probability density function i of the form p(c) exp(-v(e)) for any tvice-lifferemtiable v, then
vole() = R. [Cly + e)] = E. [[ly + E) Veu(E)).
(15)
Volc()= = E. [ely + e)] = E. [Lly + b) -Vvle)V.u(o)-vvuu
(16)
A variance-reduced form of [5 and (6) is
V, [K(y + {) = E. [[((y 6) - p(v)) V.u(c)].
(17)
V [2( + c)] E. [Cly + +c) - {())) (VeleVVavee"- -Va(ee)
(18)
6

---

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.
4.5 PERTURBED OPTIMIZERS WITH FENCHEL. YOUNG LOSSES
Blondel et al. (46) build on stochastic smoothing and Fenchel- Young losses 47 to propose perturbed optimizers with Fenchel- Fennhel-Young losses. For this, they use algorithms, like Dijkstra, to solve optimiza- tion problems of the type maxwec (y, w), where C' denotes the feasible set, e.g., the set of valid paths.
Blondel et al. (46) identify the argmax be the differential of max, which allows a simplification of stochastic smoothing. By identifying similarities to Fenchel- Young losses, they find that the gradient of their loss
V Vyl(w) = E. arg max (y + e, w) w wEC
(19)
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. Blondel et al. (46) find that the number of sumpless-suppisinglyy-oo on performance, such that 3 samples were sufficient in many experiments, and in some cases even a single sample was sufficient. In this work, we confirm this behavior and also compare it 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. If only few samples can be afforded (like 10 less), perturhed optimizers better as they more sample efficient; however, when more samples are available, stochastic smoothing is superior as it can utilize more samples better.
has a small impact
5 EXPERIMENTS
For the experiments, we evaluate Newton losses on two applications of algorithmic supervision, iee. problems where an algorithm is applied to the predictions of model and the outputs of the algorithm are supervised. The first algorithmic supervision task is ranking supervision, where only the relative order of a set of samples is known, while their absolute values remain unsupervised. The second algorithmic supervision task is the shortest path supervision, where only the shortest path is supervised, while the underlying cost matrix remains unsupervised. Finally, an ablation study, also apply Newton losses to the trivial case of classification,, where we do not expect a performance improvement, the loss is not hard-to-optimize, but rather validate that the method still works.
5.1 RANKING SUPERVISION
In this section, we explore the ranking supervision setting [13), 21 with an array of differentiable sorting-based losses. For this, we choose the recently popularized four-digit MNIST sorting bench- mark [9.
18] [2]. [22] In this setting, sets of 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 a CNN that maps each image this case,
scalar value in an order preserving fashion. Since these losses are harder to optimize achieve substantial improvements over the baselines. We train the CNN using the Adam optimizer (88 at learning rate 10-3 for 100 000 steps and with batch size of 100.
Table 1:
Differentiable sorting results. The metric is the percentage of rankings correctly identified (and individual element ranks correctly identified) averaged over 10 seeds.
5
10
Cauchy DSN Logistic DSN
NeuralSort
SoftSort
Cauchy DSN Logistic DSN
NeuralSort
SoftSort
Regular
85.00 .9 (93.31) 53. 56 (77.04) 71.33 (87.10)
70.70 75) 35.29 (87.06)
12.31 (58.81)
24.26 (74.47) 27. (76.02)
NL (Hessian)
85.11 (93.31)
75.02 (88.53)
83.31 (92.54)
83.87 (92.75 72)
56.49 (87.44)
42.14 (75.35)
48.76 (84.83)
55.07 (86.89)
NI. (Fisher)
84.93 95 (93.25)
63.11 (79.28) 83.93 (92.80) 84.03 (92.82)
12 (87.35) 25. (52. 18) 39.23 (81.14)
54.00 (86.56)

---

We explore NeuralSort, SoftSort, and differentiable sorting networks (DSNs) with logistic and Cauchy distributions in Table [ For NeuralSort and SoftSort, we find that using the Newton losses, based either on the Hessian on the Fisher matrix, improve performance substantially. In this case, using the Hessian performs better than using the Fisher matrix. For DSNs, we find that for logistic DSNs, the improvements are substantial. Monotonic differentiable sorting networks, i.e., the Cauchy DSNs, provide an improved variant of differentiable sorting networks, which also have the property of quasi-convexity, and have been shown to exhibit much better training behavior. Thus, in this case, for = 5 and Cauchy DSNs, there is no improvement over the default loss. However, for the somewhat harder setting of n 10, we can observe an improvement of more than 1% using the Hessian- based Newton loss, even in the Cauchy DSN case. In summary, we obtain strong improvements on losses that are difficult to optimize, while on well-behaving losses only small or no improvements can be achieved. This aligns with our goal of improving performance on losses that are hard-to-optimize.
5.2 SHORTEST-PATH SUPERVISION
In this section, we apply Newton losses to the shortest-pate supervision task of the 12 x 12 Warcraft shortest-path problem (15), [6] [8]. Here, 12 12 Warcraft terrain maps are given as 96 x 96 RGB images, and the supervision is the shortest path from the top left to the bottom right according to hidden cost embedding. The goal is to predict 12 x 12 cost embeddings of the terrain maps such that the shortest path according to the predicted embedding corresponds to the ground truth shortest path. For this task, we explore three approaches: the relaxed AlgoVisior Bellman-Ford algorithm, stochastic smoothing, and perturbed optimizers.
For the relaxed Algovision Bellman-Fort al- gorithm, we explore two variants of the algo- rithm (an outer For loop and an outer Wh i le loop) and two losses (I.1 and T.2), i.e., total of four settings. As computing the Hessian of the Algo Bellman- pensive with the Py PyTorch implementation, we restrict this case to the Fisher-based Newton loss. The variant with a For loop is easier to optimize than the Whi le loop variant, there is one condition less in the algorithm. This is beneficial in case of regular training: however, the For loop variant yields lower quality shortest paths due to an artifact arising from many unnecessary additional loop traversals when backtracking was actually already finished. This is avoided in the While e loop variant, which terminates the loop. As displayed in T the Newton loss improves performance in three out of four settings and the overall best performance is also provided by the Newton loss.
Table 2:
Shortest-path benchmark results for dif- ferent variants of the AlgoVision-relaxed Bellman- Ford algorithm. The displayed metric is the percent- age of perfect matches averaged over 10 seeds.
algorithm is too ex-
Algorithm Loop Loss
For
Whi le
L1
L1
L
Regular Fisher Newton
94.19
95.90
94.30
95.77
94.52
95.37
94.47
95.93
After discussing analytical relaxations, we continue with stochastic methods, the results of which are displayed in Ta- ble For stochastic smoothing of the loss function, (i.e., stochastic smoothing applied to the algo- rithm and loss as one unit), we find that Newton losses improve the performance for 10 and 30 samples, while the regular training performs best if only 3 samples can be drawn. This makes sense as the estimation of Hessian or Fisher with stochastic smoothing is not good enough with too few samples, but as soon as we have at least 10 samples, it is good enough to improve performance. For stochastic smoothing of the algorithm, (i.e.. stochastic smoothing applied only to the algorithm, and the gradient of the loss afterward computed using backpropagation), estimating the Hessian is intractable in this case, we can see improvements using the Fisher for 2 10 samples. For perturbed optimizers with Fenchel- Young loss (46), can confirm that the number
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 is the percentage of perfect matches averaged over 10 seeds.
Loss # Samples
SS of loss
SS of algorithm
PO w/ FY loss
3
10
30
10
30
3
10
30
Regular
62.83
77.01
85.48
57.55
78.70
87.26
80.64
80.39
80.71
Hessian Newton
62.40
78.82
85.94
83.09
81.13
83.45
Fisher Newton
58.80
78.74
86.10
53.82
79.24
87.41
80.70
80.37 80.45
observe very similar behavior. While
8

---

Table 4: MNIST classification learning results. The models 5-layer fully connected ReLU networks with 100 (MI), 400 (M2) and 600 (M3) neurons per layer, as well as the convolutional LeNet-5 with sigmoid activations (M4) and LeNet-5 with ReLU activations (M5). The results are averaged over 20 seeds, and significance tests between regular training and the Newton methods are conducted, better mean is indicated by a gray bold-face number, and significantly better result is indicated by a black bold-face number.
Optim.
SGD Optimizer
Adam Optimizer
Ep
Method / Model
M1
M2
M3
M4
M5
M1
M2
M3
M4
M5
1
Regular
93.06%
94.26%
94.77%
10.57%
96.25%
94.75%
96.36%
96.90%
90.60%
97.56%
1
Newton (e.w.
92.95%
94.23%
94.74%
10.57%
96.14%
94.63%
96.30%
96.06%
90.32%
77.63%
1
Newton L. (H)
93.06%
94.28%
94.77%
10.57%
96.23%
91.75%
96.36%
95.91%
90.63%
97. 63%
1
Newton (F)
94.56%
95.47%
95.36%
10.64%
97.77%
94.86%
96.28%
95.95%
90.57%
97. 97.49%
200
Regular
98. 13%
98.40%
98.46%
99.06%
90.07%
98.46%
98.62%%
98.05%
99.23%
200
Newton L. f. H)
98.11%
98. 39%
98. 44%
99.02%
99.09%
98.16%
98.44%%
98.54%
96. 96.95%
99.22%
200
Newton (H)
11%
98.42%
98.46%
99.041%
99.11%
12%
98.50%
08.633%
98.97%
99.20%%
200
Newton
98.22%
98.56%
98.68%
99.11%
99.23%
98..09%
98.53%
98.66%
98.98%
99.21%
of samples drawn barely affects performance. By extending the formulation also computing the Hessian of the Fenchel-Yone Young loss, we can compute the Newton loss, and find that we achieve improvements of more than 2% in this case. Interestingly, we find that perturbed optimizers are more sample efficient but do not improve with more samples. Also, we compare stochastic smoothing of the loss (which computes a gradient) and stochastic smoothing of the algorithm (which computes a Jacobian matrix). Smoothing of the loss is more sample efficient. On the other hand, smoothing of the algorithm performs better for 2 10 samples.
5.3 ABLATION STUDY: CLASSIFICATION
Finally, an ablation study, we explore the utility of Newton losses for the simple case of MNIST classification with a softmax cross-entropy loss. Note that, as softmax is already a well-behaved objective, we cannot expect improvements, and the experiment rather to demonstrate that no loss in performance is induced through the Newton losses.
To facilitate fair and extensive comparison, we benchmark training on 5 models and with 2 opti- mizers: We use 5-layer fully connected ReLU networks with 100 (MI), 400 (M2) and 1 600 (M3) neurons per layer, as well as the convolutional LeNet-5 with sigmoid activations (M4) and L with ReLU activations (M5). Further, we use SGD and Adam as optimizers. To evaluate both early performance and full training performance, we test after and 200 epochs. As computing the Hessian inverse is trivial for these settings, we also include the element-wise Hessian (e.w. H); however, as it performs (expectedly) poorly and as it would also be too expensive in the previous experiments, we did not include it for the algorithmic losses experiments in the previous sections.
We run each experiment with 20 seeds, which allows us to perform significance tests (significance level 0.05). As displayed in Table 4 we find that the element-wise Hessian (c.w. H) performs similar to regular training. Using the empirical Hessian (H) is indistinguishable from regular training, specifically in 12 out of 20 cases it is better and significantly better in one out of 20 cases, which is to be expected from equal methods (on average 1/20 tests will be significant at a significance level of 0.05). Finally, we find that the Fisher-based Newton losses perform better than regular training. Specifically, with the SGD optimizer, in 9 out of 10 settings, it is significantly better and on the remaining setting, has a higher mean. Using Adam (8), both methods perform similarly.
CONCLUSION
In this work, we proposed Newton losses, a method for combining second-order optimization of the loss function and first-order optimization of the model. We extensively benchmarked Newton losses on multiple tasks with an array of algorithmic losses. We found that Newton losses improve performance when training with non-trivial loss functions like algorithmic losses.

---

REFERENCES
[ N. Agarwal, B. Bullins, and E. Hazan, "Second- Stochastic Optimization for Machine Learning in Linear Time." Journal of Machine Learning Rexearch (JMLR), 2017.
[2] J. Nocedal and S. Wright, Numerical Optimization. Springer New York, 2006.
[3] N. Wadia, D. Duckworth, S. S. Schoenholz, Dyer, J. Sohl-Dickstein, "Whitening and second order optimization both make information in the dataset unusable during training, and can reduce or prevent generalization," in Proc. Machine Learning Research (PMLR), International Conference on Machine Learning (ICML), 2021.
[4] 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.
[5] W. Chen, J. Gao, H. Ling, et al., "Learnnng to prediet 3D objects with interpolation-busee differentiable
renderer," in Proc. Neural Information Processing Systems (NeurIPS), 2019.
[6] 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.
[7] C. Burges, T. Shaked, E. Renshaw, al., "Learning to rrank using gradient descent," in Proc. Machine Learning Research (PMLR), International Conference on Machine Learning (ICML), 2005.
[8] M. Taylor, J. Guiver, S. Robertson, and T. Minka, "Softrank: Optimizing non-smooth rank metrics," in
Proceedings of the 2008 International Conference on Web Search and Data Mining. 2008
[9] M. Cuturi, O. Tchoul, and J.-P. Vert, "Differcntiable ranking and sorting using optimal transport," in Proc. Neural Information Processing Systems (NeurIPS), 2019.
[10] Rolinek, V. Musil, Paulus, Vlastelica. C. Michaelis, and Martius, "Optimizing rank-batk based metrics with blackbox differentiation," in Proc. International Conference on Computer Vision and Puttern Recognition (CVPR), 2020.
[11] F. Petersen, C. Borgelt, H. Kuchne, and O. Deussen, "Differentiable sorting networks for scalable sorting and ranking supervision." in Proc. Machine Learning Research (PMLR), International Conference on Machine Learning (ICML). 2021.
[12] R. Swezey, A. Grover, B. Charron, and S. Ermon, "Pirank: Learning to rank via differentiable sorting," in Proc. Neural Information Processing Systems (NeurlPS), 2021.
[13] F. Petersen, C. Borgelt, H. Kuchne, and O. Deussen, "Monotonic differentiable sorting networks," in International Conference on Learning Representations (ICLR), 2022.
[14] M. Caron, I. Misra, J. Mairal, P. Goyal, P. Bojanowski, and A. Joulin, "Unsupervised learning of visual features by contrasting cluster assignments." Proc. Neural Information Processing Systems (NeurIPS). 2020.
[155] Q. Berthet, M. Blondel, O. Teboul, M. Cuturi, J.-P. Vert, and Bach, "L.eaming with Differentiable Perturbed Optimizers," " in Proc. Neural Information Processing Systems (NeurIPS), 2020.
[16] M. Vlastelica, A. Paulus, Musil, G. Martius, and M. Rolinek, "Differentiation of blackbox combinato- rial solvers." in International Conference on Learning Representations (ICLR), 2020.
[17] Y. Xic, H. Dai, M. Chen, et al., "Diffcrentiable top-k with optimal transport," in Proc. Neural Information
Processing Systems (NeurIPS), 2020.
[18] F. Petersen, C. Borgelt, H. Kuehne, and O. Deussen, "Learning with algorithmic supervision via continu- ous relaxations," in Proc. Neural Information P Processing Systems (NeurIPS). 2021.
[19] C. J. Burges, R. Ragno, and Q. V. Le, "Learming to rank with nonsmooth cost functions," in Proc. Neural Information Processing Systems (NeurIPS), 2007.
[20] H. Lee. S. Cho, Y. Jang, J. Kim, and H. Woo, "Differentiable ranking metric using relaxed sorting for top-k recommendation." IEEE Access, 2021.
[21] A. Grover, E. Wang, A. Zweig, and S. Ermon, "Stochastic Optimization of Sorting Networks via Continuous Relaxations." in International Conference on Learning Representations (ICLR), 2019.
[22] S. Prillo and Eisenschlos, "Softsort; A continuous relaxation for the argsort operator," in Proc. Machine Learning Research (PMLR), International Conference on Machine Learning (ICML), 2020.
[23] J.-B. Cordonnier, A. Mahendran, A. Dosovitskiy, D. Weissenborn, J. Uszkoreit. and T. Unterthiner, "Differentiable patch selection for image recognition," in Proc. International Conference Computer Vision and Pattern Recognition (CVPR), 2021.
[24] Goyal. Neubig, Dyer, and T. Kirkpatrk,, "A continuous relaxation of beam search for end-to-end training of neural sequence models," " in AAAI Conference on Artificial Intelligence, 2018.
[25] Kato, Y. Ushiku, and T. Harada, "Neural 3D mesh renderer," in Proc. International Conference on Computer Vision and Pattern Recognition (CVPR), 2018. 2018.
[26] F. Petersen, A. H. Bermano, O. Deussen, and D. Cohen Or, "Pix2Vex: Trage-to-Geomert Reconstruction using a Smooth Differentiable Renderer," Computing Research Repository (CoRR) in arXiv, 2019.
10

---

[27] Y. Hu, L. Anderson, T.-M. Li, al., "DiffTaichi: Differentiable Programming for Physical Simulation." 2020.
[28] J. Ingraham, A. Riesselman, C. Sander, and D. Marks, "Learning protein structure with differentiable
simulator," International Conference on Learning Representations (ICLR), 2018.
[29] R. H. Byrd, L. Hansen, J. Nocedal, and Singer, "A Stochastic Quasi-Newton Method for Large-Scale Optimization," " SIAM Journal on Oprimization, 2016.
[30]
Mokhtari and Ribeiro, "Global Convergence of Online Limited Memory BFGS." Journal of
Machine Learning Research (JMLR), 2015.
[31]
Martens and R. Grosse, "Optimizing neural networks Kromecker-factored approximate curvature," "
in Proc. Machine Learning Research (PMLR), International Conference on Machine Learning (ICML), 2015.
[32] M. Pilanci and M. J. Wainwright, "Newton Sketch: A Near Linear-Time Optimization Algorithm with Linear-Quadren Quadratic Convergence," SIAM Journal on Optimization, 2017.
[33] E. Frantar, E. Kurtic, and D. Alistarh, "M-FAC: Efficient matrix- freee approximations of second-order information," in Proc. Neural Information Processing Systems (NeurIPS), 2021.
[34] F. Kunstner, L. Balles, and P. Hennig. "Limitations of the empirical Fisher approximation for natural gradient descent," in Proc. Neural Information Processing Systems (NeurIPS), 2019.
[35] J. Martens, "New insights and perspectives the natural gradient method," Journal of Machine Learning
Research (JMLR), 2020.
[36] D. Bertsekas, Nonlinear Programming. Athena Scientific, 1999.
[37]
S. Boyd, N. Parikh, E. Chu. B. Peleato, and J. Eckstein, "Distributed optimization and statistical learning via the alternating direction method of multipliers," Foundations and Trends in Machine Learning. 201 I.
[38] G. Stathopoulos, H. Shukla, A. Szucs, Y. Pu, and C. N. Jones, "Operator Splitting Methods in Control," Foundations and Trends in Systems and Control, 2016.
[39] L. Carlone, V. Srivastava, Bullo, and G. C. Calafiore, "Distributed random convex programming via constraints consensus," " SIAM Journal on Control and Optimization, 2014.
[40] K. Margellos, A. Falsone, S. Garatti, and M. Prandini, "Distributed constrained optimization and con- sensus in uncertain networks via proximal minimization." " IEEE Trunsactions on Automatic Control, 2018,
[41]
N. Tikhonov and V. Y. Arsenin, Solutions of Ill-posed problems. W.H. Winston, 1977.
[42] E. Knuth, The of Computer Programming, Volume 3: Sorting and Searching (2nd Ed.) Addison Wesley, 1998.
[43]
R. Bellman, "On a routing problem," Quarterly of Applied Mathematics, vol. 16, no. 1, pp. 87-90, 1958. L. Ford Jr, "Network flow theory," Rand Corp, Santa Monica, CA, 1956.
[44]
[45]
J. Abernethy, C. Lee, and A. Tewari, "Perturbation techniques in online learning and optimization." Perturbations, Optimization, and Statistics. 2016.
[46]
M. Blondel, A. Mensch, and J.PP. Vert, "Differentiable divergences between time series," in International Conference on Artificial Intelligence and Statistics (AISTATS), 2021.
[47] M. Blondel, A. F. Martins, and V. Niculae, "Learning with Fenchel- Fenchel-Young losses," Journal of Machine Learning Research (JMLR), 2020.
[48] Kingma and "Adam: method for stochastic optimization," in International Conference on Learning Representations (ICLR), 2015.

---

A PROOFS
Theorem (Gradient Descent Step Equality between 2 and Bap+ 3b)).
gradient descent step according to ② with arbitrary step size ni coincides with two gradient descent steps according to Ga) and (3b) where the optimization over 0 has a step size of n and the optimization over z has
unit step size.
Proof. Let 0 E ④ be the current parameter vector and let z = f(x; 0). Then the gradient descent
steps according (3ah and
(3b) with step sizes and > 0 are expressed
2
2 = [(x; 0) - V {({(x)))
(20)
f(x; 00 n 0 0 0) (f(x;0)-0) -2)
0 - 7 Ve
(21)
00
Combining (20 and (1) eventually leads to
f(x: 0)
0 8-8 8 1j
(f(x; 0) f(x: 0) + V {(f(x; 0))) = 0 (x 0)),
(22)
09
which is exactly a gradient descent step of problem 1 starting at 0 E θ with step size
Theorem (Newton Step Equality between 2 and 3aa+ 3b for m = 1). the case of m 1,
Newton step according to (2) with arbitrary step size y coincides with two Newton steps according to
Ba) and (3b), where the optimization over 0 has a step size of n and the optimization over z has unit step size.
Proof. Let 0 E θ be the current parameter vector and let z = f(x: 0). Then applying Newton steps
according to (3a) and 35 leads
Z 2 z ( (z)) V (z) = f(x; 0) - (V)(((((s
(23)
V/ 2 1z f(x: 1xx0011 0011 Vogliz - 0)x:
- 0 "
(24)
0
[ [x: 0)
(f(x:0) -2) -f(x:()-2))
-05(x00) (f(x:0) z)
0x(x)))
0 n
(25)
00
08
08
0
fx: 0)
(f(x:0) - z)+ (2f(x:0) 2)
0 fxx:0)
= 0 n
(J(x;)) 2)
00
00
00
00
Inserting 23 we can rephrase the update above as
0
① fxx:)) 0)
(1)00)))) ))
0 (01(x:00) 2
0 -
(+(((1))))))))~>((((((())))) +
00
00
00
(26)
0 f 0)
(V)
00
By applying the chain rule twice, we further obtain
v(((((x)0)) =
á fa 0)
[((((x01)]
00
00
a
T f0 0)
V {)((f(x;0) 0f(x:)) 6)
v v)((f(x;()
00
00
00
00
a
a Tas(x; 0)
V [x((f(x 0)) 0x(x00) 2
()((x)))
00
00
00
00
0
T0 fx 8)
(2f(x0)
[)((f(x:)) 0)) +
v)((f(x(0).
00
00
00
which allows to rewrite
(26)
0' (173
- (,)))
(V(((((x))) 0)).
which is exactly single Newton step of problem 1 starting at O.
12

---

B FURTHER EXAMPLES FOR NEWTON LOSSES
less trivial example is the binary cross-entropy (BCE) loss with
m
(BC (v) BCE(y,P)
pt logy, + (1 -pp)) log(1 yi),
(27)
where p Am probability vector encoding of the ground truth.
Example 3 (Binary cross-entropy loss). For the BCE loss, the induced Newton loss is given as
1 1| -y112
(y) 2
(28)
where the element-wise Hessian variant is
z -diag (-pe + (1 (pe--(11)) (1 v) y,
(29)
the empirical Hessian variant is
z - diag
3)) +v, (30)
and the empirical Fisher variant is
zp [1oe (-
(31)
(pOp- 0 (1 - v)) +
and where @ and Ø are element-wise operations.
The BCE loss is often extended using the logistic sigmoid function to what is called the sigmoid binary cross-entropy loss (SBCE), defined as
ESBCE y = (C)(( p) where
x(x)
(32)
+ exp(
Example (Sigmoid Binary cross-entropy loss). For the SBCE loss, the induced Newton loss given
(VC 2 || 11=-~100 -y11
(33)
where the element-wise Hessian variant
z diag (a(y) ( au))²) -1 (o p) v,
(34)
the empirical Hessian variant is
E = diag (Ey (a(y) - (a(()) - -p) + +
(35)
and the empirical Fisher variant is
# Ey (((()) (a(y) p) + tØ,
(36)
and where @ and @ are element-wise operations.
13

---

C REGULARIZERS !2
In this section, we provide a more detailed discussion, how the regularization term Ω in induces different iterative optimization methods.
The simple setting, where 3ap represents a basic gradient descent, i.e..
z" -- ---z)(((z) z = f(x;0),
(37)
can be obtained by choosing regularization term
(z f(x: 0)) +V (z
f(x;0)) (x=x(x))) ((z)
(38)
+ ( f(x;0)).
(39)
Then, the first-order optimality conditions for min, ((z) 22 f(x:; 0)) are
Vx (f(z)) + P(zz (xx)))))))))))) 1/ /(f((x 0)) + f(x: 0) 0, which leads to the gradient step = f(x; 0) - 1/ ()) Alternatively, we can ask for the choice of the regularization term ! corresponding to a Newton step in (3a). i.e.,
(40)
x² - --== == f(x
(41)
In this case, by choosing
f(; = [(fx))x)))((( + 1/(2 ((xx)) [)((((x())
(42)
+ + - fxx=)(()))) (((([(x())) ())(0)))))2z))) f(x;0) -((z).
(43)
the first-order optimality conditions for min, ((2) Q(z f(x: 0)) are
V (f(z) + f(x; 0)) =V//(((x))) V>AU((x Ox) O.
(44)
which is equivalent to a Newton step z = -
14

---

D RUNTIMES
In this supplementary material, we provide and discuss runtimes for the experiments.
In the differentiable sorting and ranking experiment, shown in T observe that the runtime from regular training compared to the Newton Loss with the Fisher is only marginally increased. This because computing the Fisher and inverting it is very inexpensive. We observe that the Newton loss 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 computing the Hessian compared the Fisher.
Table 5:
Runtimes for the differentiable sorting results corresponding Table T training in seconds.
Times of full
10
DSN
NeuralSort SoftSort
DSN
NeuralSort
SoftSort
Regular
4214
3712
3683
6192
5236
5011
NL (Hessian)
8681
4057
4216
22617
6154
6010
NL (Fisher)
4232
3762
3730
6239
5153
5098
In Table we show the runtimes for the shortest-path experiment with AlgoVision. Here, we observe that the runtime overhead is very small.
Table 6: Runtimes for the shortest-path results corresponding Table 2 seconds.
Times of full training in
Algorithm Loop
For
Whi 1e
Loss
L1
L3
L1
L3
Regular
606
911
913
Fisher Newton
608
634
920
917
In Table 7 show the runtimes for the shortest- path experiment with stochastic methods. Here, observe that the runtime overhead is also very small. Here, the Hessian is also cheap to compute as not computed with automatic differentiation.
Table Runtimes for the shortest-path results corresponding Table seconds.
Times of full training in
Loss Samples
SS of loss
SS of algorithm
PO w/ FY loss
3
30
3
30
Regular
894 1419
3183
916
1401 3170
1157
2947
Hessian Newton
902
1398
3159
666
1161
2971
Fisher Newton
882
1394
3217
901 1382 3200
667
1168
2973
15

---

E CONVERGENCE PLOTS FOR THE CLASSIFICATION EXPERIMENT
In this Figure D. we provide convergence plots for the classification experiment. Here, we consider model M3, and the MNIST well the CIFAR-10 data sets. We show the convergence over the first 50 epochs.
MNIST:
M4 w/
Regula
Newrrnn Hessont
Newton (Hossaan)
Newson (Fshen)
28.2
96.2
97.6
97.6
27.4
Sepule
27.4
Newton (e.
Newton (hessla))
Newton (Fahert
20
10
40
Esech
Esech
CIFAR-10 10: M3 SGD
CIFAR-1D: M3 w/ Adam
65
Rogular
Nowton lo Hession)
60
Newton (timstan))
Newton (tster
50-
45
40
Regular
Newton In Hescan)
Newton [Hleobes)
15-
Nowton L (Fshen
Figure 1: Convergence plots the test accuracy for classification experiment on MNIST (top) and CIFAR-10 (bottom) for model M3. On the left, we use the SGD optimizer and on the right, we use the Adam optimizer. Results are averaged over 20 seeds and the standard deviations are marked in shaded color. We note that for CIFAR- 10 / SGD (bottom left) one of the seeds for "Newton L. (Hessian)" crashed numerically, which increased the standard deviation at this point.
16


Reviews:
[{"review_id": "evqJHhSdxp", "reviewer": "Reviewer_GdUr", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "The authors propose to use second order method only on the loss function -- not throughout the whole network in the training process.\nThey are also putting a L2 term in the formulation.", "summary_of_the_review": "Based on the limited novelty I vote for rejection.", "strength_and_weaknesses": "I don't see a strength in the formulation. Personally I have tried this method without introducing the L2 term and my finding is not quite satisfactory. Generally speaking when the Newton's method is only applied on the loss function it is a pretty weak method. Another way to think about it is if the loss function is a pure L2 loss, say for regression, then first order and second order methods are the same.\n\nAlso, if the authors are formulating the problem in a usable way, the L2 term should not be necessary. The second order information of the loss should be the only necessary thing to improve the training.\n\nLacking larger scale comparison is also a main problem with the paper. It is hard to say a piece of work is useful without scaling to imagenet-like datasets.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "Ptl5ae-oQH", "reviewer": "Reviewer_qAQi", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper introduces an approach to efficiently computing updates that incorporate second-order information. The idea is to decompose the update into two parts: a second-order update of the loss function, and a first-order update of the model. Notably, this avoids having to compute the hessian wrt the model parameters, which would be expensive for complex models like neural networks. It's shown that the two-step scheme can be equivalent to gradient descent and to the newton step algorithm for certain choices of the updates. The approach is tested empirically on algorithmic supervision tasks.", "summary_of_the_review": "The approach seems interesting and reasonably motivated, but I am not confident that the math actually checks out and would be hesitant to recommend acceptance.", "strength_and_weaknesses": "**Strengths** Breaking the update into an update wrt the loss function and an update wrt the model seems like an interesting and practical way to incorporate second-order information without computing the hessian wrt the model.\n\n**Weaknesses** The main weakness is that the math felt very imprecise to me throughout. For instance, throughout the paper argmin's are computed by arguing that the gradient is 0 at the argmin, but this isn't necessarily true since that point might have been outside of the domain. Similarly, there's often an implicit assumption that the model's range covers the entire domain, since this is how we get equivalence of $f(x;\\theta)=z^*\\in\\text{argmin}_z\\ell(z)+\\Omega(z,f(x;\\theta))$, which is used in the proof of Lemma 1 showing that the iterative and two-step method converge to the same points. This is not necessarily true without additional assumptions on the model class.\n\nSection 4 cataloguing various algorithmic supervision losses seemed mostly unnecessary and would potentially work better as an appendix", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "G1MgwaYj7BQ", "reviewer": "Reviewer_T2yc", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "The authors propose Newton losses, which breaks the loss optimization into two stages. The latent variable $z$ behaves as a target for the model output and is formed using a Newton step on the loss wrt the activations. The parameters are then optimized to match the target by minimizing a squared loss. The authors provide examples of different losses and validate the results experimentally.\n", "summary_of_the_review": "The authors need to distinguish their work from lifted networks and LocoProp. Currently, their proposed method is a special case of LocoProp on the final layer with a single local iteration. ", "strength_and_weaknesses": "### Strengths:  \n* The motivation for the approach is clear.\n\n### Weaknesses:  \n* The authors have missed important previous work that introduces such techniques. Namely, lifted networks [1] propose a two-stage optimization scheme by introducing latent variables and matching the output of each later with the latent variables. More importantly, LocoProp [2] introduced the idea of setting layerwise targets and iteratively minimizing layerwise losses to match the targets. The method proposed in this paper is a special case of LocoProp where 1) only a single target is formed for the last layer via a Newton step (this was already discussed in LocoProp in terms of a natural gradient descent (NGD) targets, and the authors show that the final update wrt to the parameters corresponds to NGD), 2) the loss is set to be the squared loss whereas LocoProp uses more advanced Bregman divergences, 3) the model parameters are updated using a single step whereas, in LocoProp, the authors try multiple steps on the fixed point problem and show that the final update on the parameters corresponds to a preconditioned update.\n\n[1] Miguel Carreira-Perpinan, and Weiran Wang. \"Distributed optimization of deeply nested systems.\" In Artificial Intelligence and Statistics, pp. 10-19. PMLR, 2014.  \n[2] Ehsan Amid, Rohan Anil, and Manfred Warmuth. \"Locoprop: Enhancing Backprop via local loss optimization.\" In International Conference on Artificial Intelligence and Statistics, pp. 9626-9642. PMLR, 2022.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "1NYdohHkbq", "reviewer": "Reviewer_fJV7", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper proposes to formulate some algorithmic losses (e.g. sorting) as bi-level optimization problems and solve the inner problem with second-order optimization. It reports performance gains over regular optimization", "summary_of_the_review": "The contribution of the paper is not clear to me, so I'm arguing for rejection.", "strength_and_weaknesses": "Strengths:\n* The performance improvements are consistent across the experiments.\n\nWeaknesses:\n* I find it extremely hard to understand what the contribution of the paper is supposed to be. Is it simply to use second order optimization on the the inner loss in bi-level optimization? Is it formulating some algorithmic losses as bi-level optimization problems? I also don't understand why the introduction opens up with a discussion of second-order optimization for neural networks, this does not seem relevant at all to what (I think) the paper is doing.\n* Related, I found it difficult to read the paper. The paper seems relatively practical to me, so I don't quite understand the choice to opt for a formal/mathematical style (Definition, Lemma, Theorem, Remark). Section 2 in particular seemed extremely verbose to me, while section 4 is lacking a lot of detail (without giving the reader a strong sense for what is going on in terms of the big picture).\n* The positioning is similarly opaque to me. While the related work cites a bunch of papers, I did not find a clear statement as to what gap in the literature the paper is trying to close and where it is improving over prior works.\n\nMinor comments:\n* Based on the title, I would have expected the paper to propose a method that includes second order information in the objective of general objective functions (similar to e.g. sharpness-aware minimization). I would suggest altering the title to make it more descriptive of the contents.\n* Inlining Tabs 2 & 3 makes reading the corresponding sections unnecessarily difficult.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject