ISAAC Newton: Input-based Approximate Curvature for Newton's Method
Authors: Felix Petersen
Tobias Sutter
Christian Borgelt
Dongsung Huh
Hilde Kuehne
Yuekai Sun
Oliver Deussen
Venue: NeurIPS 2022 Submitted (2022)

Abstract: We present ISAAC (Input-baSed ApproximAte Curvature), a novel method that conditions the gradient using selected second-order information and has an asymptotically vanishing computational overhead, assuming a batch size smaller than the number of neurons. We show that it is possible to compute a good conditioner based on only the input to a respective layer without a substantial computational overhead. The proposed method allows effective training even in small-batch stochastic regimes, which makes it competitive to first-order as well as quasi-Newton methods.

11 methods large-scale machine learning (MI.) applications due to their memory requirements and prohibitive computational cost iteration, they have recently become more popular in MI. mainly 13 due to their fast convergence properties when compared to first-order methods (T]. The expensive computation of inverse Hessian (also known as pre-conditioning matrix) in the Newton step has 15 also been tackled via estimating the curvature from the change in gradients. Loosely speaking, these algorithms are known quasi-Newton methods and comprehensive treatment can be found in ISAAC Newton: Input-based Approximate Curvature for Newton's Method
Anonymous Author(s)
Affiliation
Address
email
Abstract
We present ISAAC (Input-baSed ApproximAte Curvature), novel method that conditions the gradient using selected second-order information and has asymp- totically vanishing computational overhead, assuming a batch size smaller than the number of neurons. We show that it is possible to compute good conditioner based on only the input to respective layer without a substantial computational overhead. The proposed method allows effective training stochastic regimes, which makes it competitive to first-order as well as quasi- Newton methods.
3
in small-batch
Introduction
10 While second- optimization methods are traditionally much less explored than first-order
17 the textbook [2). In addition, various new approximations to the pre-conditioning matrix have been proposed in the recent literature () From a theoretical perspective, second-order optimization methods are not nearly as well understood as first-order methods. an active research direction to fill this gap
19
21 Motivated by the task training neural networks, and the observation that invoking local curvature information associated with neural network objective functions can achieve much faster progress per iteration than standard first-order methods (9) [T]. several methods have been proposed. One of these methods, that received significant attention, is known Kronecker-factored Approximate Curvature (K-FAC) [12), whose main ingredient is a sophisticated approximation to the generalized Gauss-Newton matrix and the Fisher information matrix quantifying the curvature of the underlying neural network objective function, which then can be inverted efficiently.
23
25
27
28
Inspired by the K-FAC approximation and the Tikhonov regularization of the Newton method, we introduce novel two parameter regularized sounecker-fcctriiee Newton update step. The proposed scheme disentangles the classical Tikhonov regularization and allows us to condition the gradient
29
31 using selected second-order information and has an asymptotically vanishing computational overhead. While this property makes the presented method highly attractive from the computational complexity perspective, we show that achieved empirical performance on complicated high-dimensional Machine Learning problems remains comparable to existing state-of-the-a art methods.
33
35 The contributions of this paper can be summarized as follows: (i) we propose a novel two parameter regularized K-FAC approximated Causs-Newter update step; (ii) we show that asymptotically as
36
Submitted to 36th Conference on Neural Information Processing Systems (NeurIPS 2022). Do not distribute.

---

37 both regularization parameters vanish our method recovers the classical K-FAC scheme and in
38 the opposite setting-as as both regularization parameters grow-our method asympiotically reduces
39 to classical gradient descent; (iii) we prove that for an arbitrary pair of regularization parameters,
40 the proposed update direction always a direction of decreasing loss; (iv) in the limit, as one
41 regularization parameter grows, we obtain an efficient and effective conditioning of the gradient with
42 an asymptotically vanishing overhead; (v) we empirically analyze the presented method and find that
43 our efficient conditioning method maintains the performance of its more expensive counterpart; (vi)
44 we demonstrate the effectiveness of the presented method in the setting of small-batch stochastic regimes and observe that it is competitive to first-order as well as quasi-Newton methods.
46
2
Preliminaries
47 In this section, we review aspects of second-order optimization, with a focus on generalized Gauss-
48 Newton methods. In combination with Kronecker factorization, this leads us to a new regularized update scheme. We consider the training of an L-layer neural network fax; 0) defined recursively as
49
(1) where ap = x is the vector of inputs and ar = fa: 8) is the vector of outputs. Unless noted otherwise, we assume these vectors to be row vectors (i.e., in Rixn) as this allows for direct extension to the (batch) vectorized case (i.e., in bxxn)) introduced later. For any layer i, ler W E x2 be a
2 - a (pre-activations),
+ ((2) (activations),
50
51
52
53
weight matrix and let á be an element-wise nonlinear function. We consider convex loss function
54
[yy y') that measures the discrepancy between y and y'. The training optimization problem is then arg min Ex, (I; 8)]
(2)
0
where 0 [o ((1)) with g(0) vec(W(()).
55
56
The classical Newton method for solving 2 is expressed as the update rule
0' = 0 - r H (o
(3)
57
where 7 > 0 denotes the learning rate and Hg is the Hessian corresponding to the objective function 58 in 2 The stability and efficiency of an estimation problem solved via the Newton method can be
59
improved by adding a Tikhonov regularization term [13 leading to a regularized Newton method
0' 0 - 77 (H, + AI) (f
60
where > is the so-called Tikhonov regularization parameter. well-known [1]] [15] that under the assumption of approximating the model of with its first-order Taylor expansion, the Hessian corresponds with the so-called generalized Gauss-Newton (GGN) matrix Go. and hence can be expressed as
61
62
(5) 64 A major practical limitation of 5 is the computation of the inverse term. A method that alleviates this difficulty is known as Kronecker-Factoo Factored Approximate Curvature (K-FAC) [12] which approximates the block-diagonal (i.e., layer-wise) empirical Hessian or GGN matrix. Inspired by K-FAC, there have been other works discussing approximations of Gø and its inverse (15). In the following, we
0' 17 (G, + VV 0),
65
66
67
68 discuss popular approach that allows for (moderately) efficient computation.
The generalized Gauss-Newton matrix Go is defined
Go [J 8)) T ()((((r;)) Jz.(
(6)
where J and H denote the Jacobian and Hessian matrices, respectively. Correspondingly, the diagonal block of Go corresponding to the weights of the ith layer W(()) is
71
G ( w f(x;0) V)C(((=; f(;
72 According to the backpropagation rule Jgio 0) = J,. a--)) a = a 2 b, and the mixed productt property, we can rewrite Gw as
73
G G =E|
8) a: "1
fz: (x; a+)1 (7)
= =o( a)-1) (g a- = (00 T (g0
(a 0 00 (8)
74 where
g = (J (V74af/(()00((((((1)1))))... (V))(((:))))))
(9)
2

---

75 Remark 1 (Monte-Cate Low-Rank Approximation for g g) As 9 is a matrix of shape m x d:
78 where m the dimension of the outuu of f. 9 is generally expensive to compute. Therefore. [I2] use
77 low-rank Monte-Care Canee-Carlo approximation to estimate (x;(f( 0), y) and thereby 9 9. For this, we need use the distribution underlying the probabilistic model of our loss L (e.g. Gaussian for MSE
78
79 loss, or categorical distribution for cross entropy). Specifically, by sampling from this distribution (x; 80 Pr Pf(x) defined by the network output f(x; 0), we can get an estimator of Hf 0), 2) via the
81 identity
H ((f(((x))), = Exppr(()) [ V 0))
(10)
82 An extensive reference for this (as well as alternatives) can be found in Appendix A.2 of Dangel et 83 al. 15%. The respective rank-1 approximation (denoted by 4 of Hf 0)) is
H, A vx[[f( 0), D) T ( 0), 9),
where 9 ~ (x)).. Respectively, we can estimate g 9 using this rank-1 approximation with 84
g - (J.. V ()) = V., ((f 0)
(11)
In analogy to 9. introduce the gradient of training objective with respect to pre-activations 2; as g == (J=, 0)) V vf((((;;0) 0). [(, (),
(12)
86 In other words, for given layer, let g E TR. xd; 1x:;; denote the gradient of the loss between an output and the ground truth and let g E Rmxd, denote the derivative of the network f times the square root of the Hessian of the loss function (which may be approximated according to Remark [. each of them with respect to the output 2; of the given layer i. Note that ğ is not equal to and that they require one backpropagation pass each (or potentially many for the case of g). This makes computing 9 costly,
87
86
89
90
81
Applying the K-FAC [12 approximation to (8) the expectation of Kronecker products can be approximated as the Kronecker product of expectations as
92
G == [E g) & (a a)) R= B(g g) & E(aTaa)
(13)
93 where, for clarity, we drop the index of a; in 8 and denote it with a; similarly we denote G Gw
94 as G. While the expectation of Kronecker products is generally not equal to the Kronecker product
85 of expectations, this K-FAC approximation (13) has been shown to be fairly accurate in practice
96 and preserve the "coarse structure" of the GGN matrix [12]. The K-FAC decomposition in (13
87 is convenient as the Kronecker product has the favorable property that for two matrices A, B the
98 identity (A c B) A & B which significantly simplifies the computation of an inverse.
99 In practice, E(g g) and E(a a) can be computed by averaging over a batch of size b as
E(g g) ~ g g/bb
E(a a) ~ aTa/b.
(14)
100 where we denote batches of g, 9 and a. as g E Rx . E rrxx and E Raxd; 1, where our layer has d inputs, d, outputs, b is the batch size, and r is either the number of outputs m or the rank of
101
102 an approximation according to Remark [ Correspondingly, the K-FAC approximation of the GGN
103
matrix and its inverse are concisely expressed as
G R
X (a
T a)/B²
G ~ (g
g)
(15)
104
Equipped with the standard terminology and setting, we now introduce the novel, regularized update step. First, inspired by the K-FAC approximation (3) the Tikhonov regularized Gauss-Newton method (5) can be approximated by
105
106
gtoy 009) n(g g/b AI) & (a aaTa/b -VV ())( (()
(16)
107
with regularization parameter À >> 0. A key observation, which is motivated by the structure of the above update, is to disentangle the two occurrences of X into two independent regularization parameters Ag. Aa > 0. By defining the Kromecker-factoriiees Gauss-Newton update step as
108
109
= A \a>a (g g/b + \²1)- & (a T a/b + AaI) ' (({(z))),
(17)
110 we obtain the concise update equation
g gL0) n'S.
(18)
3

---

This update (18) is equivalent to update (16) when in the case of 17" 7 and A= >= Xa. This
dg
equivalence does not restrict 17",, >g. Aa in any way, and changing >g Xa does not mean that
113 change our learning rate or step size 17". Parameterizing Ç in (17) with the multiplicative terms A²²a
114 makes the formulation more convenient for analysis.
115 In this paper, we investigate the theoretical and empirical properties of the iterative update rule (8) and in particular show how the regularization parameters Ag. a affect the croneckerffactrriig Gauss-Newton update step Ç. When analyzing the Kronecker-factorized Gauss-Newton update step particularly useful tool is the vector product identity,
117
0 g
(a (aTa)
vec(g aa) -vee (g a
(19)
where the gradient with respect to the weight matrix is g
Theoretical Guarantees
120
121
In this section, we investigate the theoretical properties of the Kronecker-factorizzed Gauss-Newton update direction Ç defined in (7].. We recall that Ç introduces a Tikonov regularization, as it is commonly done in implementations of second order-basee methods. Not surprisingly, we show that
122
123
by decreasing the regularization parameters Xg: Aa the update rule (18) collapses (in the limit) to the classical Gauss-Newton method, and hence the regime of small >g: An the variable Ç describes Gauss-Newton direction. Moreover, by increasing the regularization strength, we converge (in the limit) to the conventional gradient descent update step.
125
127
128
The key observation is that, as we disentangle the regularization of the two Kronecker factors ğ and a a, and consider the setting where only one regularizer is large (Ag + oo to be precise), we obtain an update direction that can be computed highly efficiently. We show that this setting describes an approximated Gauss-Newtor update scheme, whose superior numerical performance
129
130
131
132
then empirically demonstrated in Section 4
133
Theorem 1 (Properties of (). The K-FAC based update step Ç as defined in 17 can be expressed as
5
I
g bdg
Tb
99 b>g
9 .T.
Ib
1
aa
Ib
1
aa
bda
bla
(20)
Moreover, S admits the following asymptotic properties:
135
(i) In the limit of Xg, Xa + O, Teho is the K-FAC approximation of the Gauss-Newton step. i.e., G VVV (x)(())) where = denotes the K-FAC approximation 15)
136
limag +0 Agda
137
(ii In the limit of Xg. Xa + 3c. Ç is the gradient, i.e., lim = V ((f(z;))
138
The Proof is deferred to the Supplementary Material.
139
We want to show that Ç is well-defined and points in the correct direction, only for Ag and X numerically close to zero because we want to explore the full spectrum of settings for xg and Xa-
140
141
Thus, we prove that Ç is a direction of increasing loss, independent of the choices of Ag and da
Theorem 2 (Correctness of Ç is independent of Ag and Xa). Ç is direction of increasing loss, independent of the choices of Ag and Xa-
143
144
Proof. Recall that (AgIm. +ÿ " g/b) and (AaI, +a a/b) are positive semi-definite (PSD) matrices by definition. Their inverses (AgIm + g/b)- -1 and (NaI, + a a/b) are therefore also PSD. As the Kronecker product of PSD matrices is PSD, the conditioning matrix ((AgIm + g g/6) @ (AaIn +
145
148
a/b)-1 G G11 is PSD, and therefore the direction of the update step remains correct.
147
148
From our formulation of Ç. we can find that, in the limit for >g - oc, Equation 21 does not depend on g. This is computationally very beneficial as computing ğ is costly as it requires one or even many additional backpropagation passes. In addition, allows conditioning the gradient update by multiplying a b x b matrix between g and which can be done very fast.
150

---

152
Theorem 3 (Efficient Update Direction). In the limit of >g - oc, the update step Ç converges to limag- -00 5 = S", where
153
5==6" T.
aa
aa
T
a.
(21)
bdg
154
(i) Here, the update direction 5" is based only on the inputs and does not require computing (which would require a second backpropagation pass), making efficient.
155
(ii) The computational cost of computing the update Ç lies in O( + 62n + b²), where n the number of neurons in each layer. This comprises the conventional cost of computing the gradient
156
V g x lying in Obn²², and the overhead of computing 5 instead of V lying in O(b²n + b²). The overhead is vanishing, assuming n b. For b > n the complexity lies in Obm? n²)).
158
Proof. We first show the property (21 Note that according to (22) Ax= (AgIm. + g/6)) con-
180
161
verges in the limit of Ag + oo to Im and therefore (2T) holds.
162
(i) The statement follows from the fact that the term g does not appear in the equivalent characteriza-
163
tion (2T) of ç*
(ii) We first note that the matrix aa is of dimension b, and can be computed in ((22n) time.
184
185
Next, the matrix
Io
aaT
Ib
aa )
bdn
bia
is of shape b x b and can be multiplied with in O(Pn)) time.
Notably, 21 can be computed with vanishing computational overhead and with only minor modifications to the implementation. Specifically, only the g a expression has to be replaced by (2I) in the backpropagation step, As this can be done independently for each layer, this lends itself also to applying only to individual layers.
168
170
171
As we see in the experimental section, in many cases in the mini-batch regime (i.e., b < n), the optimal (or a good) choice for Ag actually lies in the limit to co. This is surprising result, leading to the efficient and effective 5 = -oe optimizer.
172
174
Remark2 2 (Relation between Update Direction Ç and ("). When comparing the update direction 175 C in (0) without regularization (i.e., Ag - 0, aa - 0) with C (i.e., Ag + 20) as given in (2I). can be directly seen that 5" corresponds to particular pre-conditioning of S. since Ç MC for
176
177
M bbg g g.
178
As the last theoretical property of our proposed update direction Ç", we show that in specific networks 5" coincides with the Gauss-Newtor Newton update direction.
179
180
Theorem 4 (C" is Exact for the Last Layer). For the case of linear regression more generally, the last layer of networks, with the mean squared error, 5² the Gauss-Newton update direction.
181
Proof. The Hessian matrix of the mean squared error loss is the identity matrix. Correspondingly, the expectation value of g is I. Thus, 5" =
182
194
Remark The direction 5" corresponds to the Gauss-Newton update direction with an approxima- tion of G that can be expressed as G ~ E [ (a a)].
185
186
Remark 4 (Extension to the Natural Gradient). In some cases, it might be more desirable to use the Fisher-based natural gradient instead of the
187
method. The difference to this setting is that in (5 the GGN matrix G is replaced by the empirical Fisher information matrix F.
189
We note that our theory also applies F. and that 5* also efficiently approximates the natural gradient update step F The i-th diagonal block of F (F gca
E (g. ga) & (a. & a;-1))
191 has the same form as a block of the GGN matrix G (go E. (g g.) 80 (aT_ 8 a; Thus, we can replace ğ with g in our theoretical results obtain their counterparts for F.
5

---

12122
4:516
3.64
1318
18%
1914
1912
Figure 1: Logarithmic training loss (top) and test accuracy (bottom) on the MNIST classification task. The axes the regularization parameters Ag and Åa in logarithmic scale with base 10. Training with 5 5-layer ReLU activated network with (left, a. e). (center, b, c. g).
(right, h) neurons per layer. momentum. The top-left sector
The optimizer is SGD except for (c, g) where optimizer SGD the top-right column is Ç" and the bottom-right corner is V (gradient descent). For each experiment and each of the three sectors, comparison between the methods; within each sector the learning rate is constant. We can observe that in the limit of Xg oo (i.e., the limit to right) the performance remains good. showing the utility (*
one learning rate, i.c., 5. V have their own learning rate to make fair
Experiments
198
In the previous section, discussed the theoretical properties of the proposed update directions Ç and (" with the aspect that Ç* would actually be "free" to compute in the mini-batch regime. In this section, provide empirical evidence that is good update direction, in deep learning. Specifically, we demonstrate that
195
196
197
198
(EI) 5" achieves similar performance K-FAC, while being substantially cheaper compute.
199
B2)
The performance of our proposed method can be empirically maintained in the mini-batch regime (n >> b).
201
E3 5* may be used for individual layers, while for other layers only the gradient is used, This still leads to improved performance.
B4) S* also improves the performance for training larger models such as BERT and ResNet. The runtime and memory requirements ς are comparable to those of gradient descent.
204
E5
E1:
Impact of Regularization Parameters
206
For (E1), we study the dependence of the model's performance on the regularization parameters Ag and An. Here, we train 5-layer deep neural network the MNIST classification task (16) with batch size of 60 for a total of 40 epochs or 40 000 steps.
208
The plots in Figure I demonstrate that the advantage of training by conditioning with curvature information can be achieved by considering both layer inputs a and gradients with respect to random samples but also using only layer inputs In the plot, show the performance of Ç for different choices of Ag and >a, each in the range from 10-6 to 10a. The right column shows Ç*, i.e., Ag = oc, for different Ày- The bottom-right corner is gradient descent, which corresponds to Zg oo and
210
212
214
X, 00.
Newton's 's method or the general K K-FAC approximation corresponds to the area with small >g and Xa. The interesting finding here is that the performance does not suffer by increasing Ag toward co, i.e. from left to right in the plot.
216

---

0.07
0.07
Gradient
descent
0.06
0a=0.:)
0.06
KPAC Ma
KMAC Mh 1011
Traiing 655
KFAC Iss
K-AC -003)
0.04
Pa 0.011
Training
0.04
Ua 0.01
0.03
0.03
0.01
0.01
0.00
0.00
2000 Steps
2500
3000
training (im
Figure 2: Training loss of the MNIST auto-encoder trained with gradient descent, K-FAC, Ç. and Ç", Comparing the performance per real-time (left) and per number of update steps (right). Runtimes are for CPU core.
In addition, in Figure MSE loss on MNIST [6] and Fashion-MND [17]. Here, we follow the same principle as above and also find that 5" performs well.
consider the case of regression with auto-encoder trained with the
219
-25
In Figure we compare the loss for dif- ferent methods. Here, we distinguish between loss per time (left) and loss per number of steps (right). We can ob- serve that, for À 0.1, K-FAC, Ç, and 5" are almost identical per update step (right), while 5" is by a large margin the fastest, followed by S. and the ventional K-FAC implementation is the slowest (left). On the other hand, for 0.01 we can achieve a faster con- vergence than with
223
225
-10
227
-50
229
Figure 3: Training an auto-encoder MNIST (left) and Fashion- MNIST (right). The model is the used Botev et al. (18). i.c., it is ReLU-activated 6-layer fully connected model with dimensions 784-1000-500- 30-500-1000-784 Displayed
231
0.1, but here only the K-FAC and ( methods are nu- merically stable, while (" is unstable in the logarithmic training loss.
239
234
235
this case. This means in the regime of very small X 5"
(a)
(b)
236
as robust K- FAC and Ç. however. it achieves good performance with small but moderate like À = 0.1. For À < 0.01, also K-FAC and Ç become numerically un- stable in this setting and, in general, we observed that the smallest valid À for
237
238
240
242
K-FAC is 0.01 or 0.001 depending on model and task. Under consideration of the runtime, ç" performs best as it is almost as fast as gradient descent while performing equivalent K-FAC and Ç. Specifically, a gradient descent step only about 10% faster than 5*
244
Figure 4: Training S-layer ReLU network with 400 neurons per layer the MNIST classification task (as in Figure but with the Adam optimizer
246
248
250
E2:
Minibatch Regime
Bo Brbgeres
For (E2), in Figure 1 we can see that training performs well for n {100, 400, 1 600) neu-
brlkeess
2.
252
rons per layer a batch size of only 60. Also, in all other experiments, we use small batch sizes of between 8 and 100.
log, training
-
254
-12
256
E3: in Individual Layers
257
In Figure 5 we train the 5-layer fully connected model with 400 neurons per layer. Here, we consider the setting that we use Ç" in some of layers while using the default gradient V in other layers. Specifically, consider the
-16
258
-18
250
500
750
1250 training time
1000
1500
1750
2000
280
Figure 5: Training on the MNIST classification task
using S" only in selected layers. Runtimes are for CPU.

---

Table I: BERT results for fine-tuning pre-trained BERT-Base (B-B) and BERT-Mini (B-M) models the COLA, MRPC, and STSB text classification tasks. Larger values better for all metrics. MCC the Matthews correlation. Results averaged over 10 runs.
Method Setting
CoLA (B-B)
CoLA (B-M)
MRPC (B-B)
STS-B (B-M)
Metric
MCC
MCC
Acc.
F1
Peurson
Spearman
Gradient buseline
54.20 +: 7.56
21.08 2.88
82.52 4: 1.22
87.88 + 0.74 76.98 +: 1.10 76.88 = 0.79
57.62 1: 1.59
24.67 2.62 83.28 1 0.89 88.28 1 0.70 81.09 1 1.58 80.82 1: 1.57
262
settings, where all, the first, the final, the first three, the final three, the odd numbered, and the
263
even numbered layers are updated by 5" We observe that all settings with 5" perform better than
264
plain gradient descent, except for "Ç" for layers 3,4,5" which performs approximately equivalent to gradient descent.
265
286
E4: Large-scale Models
BERT To demonstrate the utility of Ç" also in large-scale models, evaluate it for fine-tuning
268
BERT 20) on three natural language tasks. In Table we summarize the results for the BERT
269
fine-tuning task. For the "Corpus of Linguistic Acceptability" (CoLA) [21] data set, we fine-tune both the BERT-Base and the BERT-Mini models and find that we outperform the gradient descent
270
271
baseline in both cases, For the "Microsoft Research Paraphrase Corpus" (MRPC) [22] data set, we fine-tune the BERT-Base model and find that we outperform the baseline both in terms of accuracy and F1-scord Finally, on the "Semantic Textual Similarity Benchmark" (STS-B) (23) data set, we fine-tune the BERT-Mini model and achieve higher Pearson and Spearman corre correlations than the baseline. While for training with CoLA and MRPC, we were able to use the Adam optimizer [19] (which is recommended for this task and model) in conjunction with 5 in place of the gradient, for STS-B Adam did not work well. Therefore, for STS-B, we evaluated it using the SGD with momentum optimizer. For each method, we performed a grid search over the hyperparameters. We note that we use a batch size of 8 in all BERT experiments.
272
273
274
275
276
277
279
ResNet In addition, we conduct an experiment where we train the last layer of a ResNet with 5". while the remainder of the model is up- dated using the gradient V. Here, we train
0.78
281
283
ResNet-18 18 24 on CIFAR-10 (25) using SGD with batch size of 100 in a vanilla setting, i.e., without additional tricks employed in by He et
285
287 al [24] and others. Specifically, we use (i) a constant learning rate for each training (optimal from (1, 0.3, 0.1, 0.03, 0.01)) and (ii) vanilla SGD and not momentum-basee SGD. The rea-
Srudamm dasces p-t.
0.76
Srudinn doscert 2-1.0
289
fer firadteee 1-11
laztayer Lo
281
son behind this is that we want a vanilla experi- ment and with aspects such as extensively tuning multiple parameters of learning rate scheduler
250
500
750
1000
1250
1500
1750
2000
282
training time [s]
Figure 6: ResNNet-18 trained on CIFAR-10. Runtimes are for GPU. Results are averaged over 5 runs.
293
294
would make the evaluation less transparent; how- ever, therefore, all accuracies are naturally lower than SOTA. In Figure we plot the test accuracy against time. The results show that the proposed method outperforms vanilla SGD when applied
295
296
297
to the last layer of a ResNet-18, 18. To validate that the learning rate is not the cause for the better performance, we also plot the neighboring learning rates and find that even with a too small or too large learning rate 5* outperforms gradient descent with the optimal learning rate.
298
299
300
E5: Runtime and Memory
Finally, we also evaluate the runtime and memory requirements of each method. The runtime evaluation is displayed in Table We report both CPU and GPU runtime using PyTorch (26) and
302
303
(for K-FAC) the backpack library [5]. Note that the CPU runtime is more representative of the
304
pure computational cost, as for the first rows of the GPU runtime the overhead of calling the GPU
is dominant. When comparing runtimes between the gradient and Ç" on the GPU, we can observe that we have an overhead of around 2.5 s independent of the model size. The overhead for CPU time
306
is also very small at less than 1 1% for the largest model, and only 1.3 for the smallest model. In
8

---

308
contrast, the runtime of 5" is around 4 times the runtime of the gradient, and K-FAC has an even
309
substantially larger runtime. Regarding memory. Ç" (contrasting the other approaches) also requires only a small additional footprint.
310
Remark 5 (Implementation). The implementation of can be done by replacing the backpropagation
step of a respective layer by (21). As all "ingredients" are already available in popular deep learning frameworks, il requires only little modification fcontrasting K-FAC and S. which require at least one
312
313
additional backpropagation.)
314
Table 2: Runtimes and memory requirements for different models. Runtime is the training time per epoch on MNIST at a batch size of 60, i.c., for 1000 training steps. The K-FAC implementation is from the backpack library 15).
The GPU is an Nvidia A6000.
Grdisent
K-FAC
<'
Model
CPU time
GPU time
Memory
CPU time
GPU'
Memory
CPU
GPU
Memany
CPU
GPU
Memary
layers w/ 100 a.
2,00
1.79
1BMB
62.75 9
17.63
11.5 MB
8.65 s 11.76
1.6BB
9.34
4.07
1.0B
6 leyess wf 400 a.
23.74 x
1.84
4.8 MR
218 48
32.00
22.4 MB
38.67 x 12.62
MR
13.62 x 4.19
4.9
leyess w/1l G00
187.87
1,88
51.088
6980.45
156. 48
212.2 MB
660.880
12.53
80.8B
291.01
4.49
51.4 MB
layers 6 400m.
3430.59
8.22
601.0MB
1320.81
MB
9673x
$1.87
1197
107.8MB
3451.61
x 10.24 60
Auto- Frecder
78.61
2.20
16.2MB
1207 58 74.00
70.7
x x
33
87. x 4.83 16
315 We will publish the source code of our implementation. In the appendix, we give a PyTorch 226
implementation of the proposed method (C").
316
5
Related Work
318
K-FAC uses the approximation [3) to approximate the blocks of the Hessian of the empirical risk of neural networks. In most implementations of K-FAC, the off-diagonal blocks of the Hessian are also set to zero. One of the main claimed benefits of K-FAC is its speed (compared to stochastic gradient descent) for large-batch size training. That said, recent empirical work has shown that this advantage of K-FAC disappears once the additional computational costs of hyperparameter tuning for large batch training is accounted for. There is a line of work that extends the basic idea of K-FAC to convolutional layers [27]. Botev et al. (18) further extend these ideas to present KFLR, a Kronecker factored low-rank approximation, and KFRA, a Kronecker factored recursive approximation of the Gauss-Newton step. Singh and Alistarh (28) propose WoodFisher, a Woodbury matrix inversc-based estimate of the inverse Hessian, and apply it to neural network compression. Yao et al. [29] propose AdaHessian, a second-order optimizer that incorporates the curvature of the loss function via an adaptive estimation of the Hessian.
Our methods are related to K-FAC by Martens and Grosse [12]
319
320
321
322
324
326
328
329
330
Frantar et al. (6) propose M-FAC, a matrix-fii free approximation of the natural gradient through queue of the (e.g., 000) recent gradients. These works fundamentally differ from our approach in that their objective is to approximate the Fisher or Gauss-Newton matrix inverse vector products. In contrast, this work proposes to approximate the Gauss-Newtor matrix by only one of its Kronecker factors, which we find to achieve good performance at a substantial computational speedup and reduction of memory footprint. For overview of this area, we refer to Kunstner el al. (30 and Martens (3T).
332
333
334
335
338
For an overview of the technical aspects of backpropagation of second-order quantities, we refer to
337
Dangel et al. [5], 32)
338 Taking a step back, K-FAC is one of many Newton-type methods for training neural networks. Other prominent examples of such methods include subsampled Newton methods (33), 34 (which approximate the Hessian by subsampling the terms in the empirical risk function and evaluating the Hessian of the subsampled terms) and sketched Newton methods (5) (which approximate the
340
341
Hessian by sketching, e.g., by projecting the Hessian to a lower-dimensional space by multiplying it with random matrix). The main features that distinguish K-FAC from this group of methods
342
343
344
K- K-FAC's superior empirical performance and K-FAC's lack of theoretical justification.
Conclusion
345
346
In this work, we presented ISAAC Newton, a novel approximate curvature method based on layer- inputs. We demonstrated it to be a special case of the pnallariattinggeneraliiii Gauss-Newton
347
method and empirically demonstrate its utility. Specifically, our method features an asymptotically vanishing computational overhead in the mini-batch regime, while achieving competitive empirical performance on various benchmark problems.
349

---

References
351
352
[1] N. Agarwal, B. Bullins, and E. Hazan, "Second-order stochastic optimization for machine learning in linear time," Journal on Machine Learning Research, vol. 18, no. 1, pp. 41877 2017.
353
354
355
[2] J. Nocedal and S. J. Wright, Numerical Optimization, 2e. New York, NY, USA: Springer, 2006.
356
[3] A. Gonen and S. Shalev-Shwartz, "Faster SGD using sketched conditioning," arXiv preprins,
arXiv:/500 0tte:/506.02665 026.42064992 2015.
358
[4] M. Pilanci and M. J. Wainwright, "Newton sketch: A near linear-time optimization algorithm
with linear-quadratic convergence," SIAM Journal on Optimization, vol. 27, 2017.
359
380
[5] M. A. Erdogdu and A. Montanari, "Convergence rates of sub-sampled Newton methods," in
381
Proc. Neural Information Processing Systems (NeurIPS), 2015.
362
66] 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.
77]
N. Doikov and Y. Nesterov, "Convex Optimization based Global Lower Second-order Models," " in Proc. Neural Information Processing Systems (NeurIPS), Curran Associates, Inc., 2020.
365
367
88
Y. Nesterov and B. T. Polyak, "Cubic regularization of Newton method and its global perfor- mance," Mathematical Programming, vol. 108, 2006.
368
389
99
S. Becker and Y. Lecun, "Improving the convergence of back-propagation learning with second-order methods," " 1989.
370
371
[10]
T. Schaul, S. Zhang, and Y. LeCun, "No more pesky learning rates." in International Conference on Machine Learning (ICML), 2013.
372
[1]]
Y. Ollivier, "Riemannian metrics for neural networks i: Feedforward networks," Information and Inference, vol. 4, pp. 108-153, Jun. 2015.
374
375
[12] J. Martens and R. Grosse, "Optimizing neural networks with Kronecker-factored approximate curvature," in International Conference on Machine Learning (ICML), 2015.
[13]
A. N. Tikhonov and V. Y. Arsenin, Solutions of Ill-posed problems. W.H. Winston, 1977.
378
[14] P. Chen, "Hessian matrix vs. Coius--Newton Hessian matrix," SIAM Journal on Numerical
379
Analysis, 2011.
380
[15]
F. Dangel, F. Kunstner, and P. Hennig, "Backpack: Packing more into backprop," in Interna- tional Conference on Learning Representations, 2020.
381
382
[16]
Y. LeCun, C. Cortes, and C. Burges, "MNIST Handwritten Digit Database," " ATT Labs, 2010. [17] H. Xiao, K. Rasul, and R. Vollgraf, "Fashion-MNIST: A novel image dataset for benchmarking
383
machine learning algorithms." arXiv, 2017.
[18] A. Botev, H. Ritter, and D. Barber, "Practical
optimisation for deep learning," in International Conference on Machine Learning 2017
386
387
[19]
D. Kingma and J. Ba, "Adam: A method for stochastic optimization," in International Confer- ence on Learning Representations (ICLR), 2015.
388
389
[20]
J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova, "Bert: Pre-training of deep bidirectional transformers for language understanding." in North American Chapter of the Association for Computational Linguistics: Human Language Technologies (NAACL-HLT), 2018.
380
391
382
[21] A. Warstadt, A. Singh, and S. R. Bowman, "Neural network acceptability judgments," Trans- actions of the Association for Computational Linguistics, vol. 7, 2019.
383
[22]
W. B. Dolan and C. Brockett, " "Automatically constructing a corpus of sentential paraphrases." in Proceedings of the Third International Workshop on Puraphrasing (/WP2005), 2005.
395
396
[23]
D. Cer, M. Diab, E. Agirre, I. Lopez-Gazpio, and L.. Specia, "SemFval-2017 task 1: Semantic textual similarity multilingual and crosslingual focused evaluation," " in Proceedings of the 1th International Workshop on Semantic Evaluation (SemEival-2017), Vancouver, Canada: Association for Computational Linguistics, 2017.
398
400
[24]
K. He, X. Zhang, S. Ren, and J. Sun, "Deep residual learning for image recognition," in Proc. International Conference on Computer Vision and Pattern Recognition (CVPR), 2016.
401
402
[25]
A. Krizhevsky, V. Nair, and G. Hinton, 10 (Canadian Institute for Advanced Research)," 2009.
403
404
[26]
A. Paszke, S. Gross, F. Massa, el al., "Pytorch: An imperative style, perfoaace deep learning library," " in Proc. Neural Information Processing Systems (NeurIPS), 2019.
10

---

408
[27]
R. Grosse and J. Martens, "A crronecker-factored approximate Fisher matrix for convolution layers," " in International Conference on Machine Learning (ICML), 2016.
407
408
[88]
S. P. Singh and D. Alistarh, "Woodfisher: Efficient second-order approximation for neural network compression," in Proc. Neural Information Processing Systems (NeurIPS), 2020.
29
7. Yao, A. Gholami, S. Shen, M. Mustafa, K. Keutzer, and M. W. Mahoney, "Adahessian: An adaptive second order optimizer for machine learning," in AAAI Conference on Artificial Intelligence, 2021.
412
418
[30]
F. Kunstner, L. Balles, and P. Hennig. "Limitations the empirical Fisher approximation for natural gradient descent," in Proc. Neural Information Processing Systems (NeurIPS), 2019.
[31]
J. Martens, "New insights and perspectives the natural gradient method," Journal of Machine Learning Research, 2020.
416
417
[32]
F. Dangel, S. Harmeling, and P. Hennig, "Modular block-diagonal curvature approximations for feedforward architectures," " in International Conference on Artificial Intelligence and Statistics (AISTATS), 2020.
418
[33]
F. Goosta-Khorassan and M. W. Mahoney, "Sub-Sampled Newton Methods I: Globally Con- vergent Algorithms," " arXiv: 1601.04737, 2016.
421
422
[34]
P. Xu, J. Yang, F. Roosta, C. Ré, and M. W. Mahoney, "Sub-sampled Newton Methods with Non-uniform Sampling," in Proc. Neural Information Processing Systems (NeurIPS), 2016.
423

---

Checklist
424
1. For all authors...
426
(a) Do the main claims made the abstract and introduction accurately reflect the paper's
427
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
429
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
430
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them?
[Yes]
432
2. If you are including theoretical results...
433
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proof's of all theoretical results? [Yes]
435
3. If you ran experiments...
436
(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or URL)? [Yes] / [No] We include Python / PyTorch implementation of the method in the supplementary material. We will publicly release full source code for the experiments.
437
438
439
440
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
442
(c) Did you report error bars (e.g.. with respect the random seed after running experiments multiple times)? [Yes]
443
(d) Did you include the total amount of compute and the type of resources used (e.g.. type of GPUs, internal cluster, or cloud provider)? [Yes]
445
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
448
(b) Did you mention the license of the assets? [N/A]
449
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you't 're
451
using/curating? [N/A]
452
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
453
454
5. If you used crowdsoureing or conducted research with human subjects...
455
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
496
457
(b) Did you descrihe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
458
459
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
12

---

A PyTorch Implementation
462 We display PyTorch [26] implementation of ISAAC for fully-connected layer below. Here, we 483 mark the important part (i.e., the part beyond the boilerplate) with red rectangle.
import torch
class ISAACLinearFunction (torch. autograd.. Euttorrad.uuntton). Function): @staticmethod def forward input, weight, bias, la, inv_type):
ctx. save str__saeefo___e wor_baccwardddnppuc weight, bias)
ctx.la la
if inv_ ==
ctx. inverse torch. pholessk_iineerss
elif inv_typ == 'inverse':
ctx. inverse torch.
else:
raise Not.mpleeenteeBBrro (inveeddrrrrooi_yynpeeee
return input @ weight. T (bias if bias is not None else 0)
@staticmethod
def backward(ctx, grad_output):
input, weight, bias ctx saved if ctx ctx.needd_inge inputtggrad[[]
grad_0 grad_output @ weight
else:
grad_0 0 None
if ctx. needs baabss_inuttgr_lll_
aaT input input. grad_output. cetauuuuttt.ssppeeeee.e [0]
I_b torch. eye (aaT shape [0], device=aaT device, dtype= dtype) aaT_IaaT]
aaT ctx. inverse (aaT ctx.la I_b)
grad_1 grad_output. T @
I_b 1. ctx.
aaT aaT_IaaT_ _nn
@ input
else: grad_1 None
return (
grad_0, grad_1,
grad_output me,n(O, keepdim=True) if bias is not None else None, None, None, None,
class ISAACLinear
(torch. (torch
Linear):
def ___ini___eee (self, in in_features, out fet_ffeauure,
la, www_type='invere **kwargs): super (ISAACLinear, (elf)__inii___ in_ ott_ffestureerotttffetuueee **kwargs
self .a
self inv_type inv_type
def forward input: torch. Tensor) -> torch. Tensor:
return ISAACI.imearuunctinn apply input, self weight,
13

---

self. bias. unssuuezeeee) (0) if self. bias is not None else None, self. la,
self. inv__tttppp
464
B
Implementation Details
465
Unless noted differently, for all experiments, we tune the learning rate on a grid of (1, 0.3, 0.1, 0.03, 0.01, 0.003, 0.001). We verified this range cover the full reasonable range of
486
487
learning rates. Specifically, for every single experiment, we made sure that there is no learning rate
468
outside this range which performs better.
469
For all language model experiments, we used the respective Huggingface Py PyTorch implementation.
470
All other hyperparameter details are given in the main paper.
The code will be made publicly available.
C Additional Proofs
473 Proof of Theorem 7
We first show, that as defined (17) can expressed as in (20). Indeed by using (19). the Woodbury matrix identity and by regularizing the inverses, can that
5 >g>a g/b + X (aJa/aaa aaaabb- AaI)
g TTa
Agda
(AgIm
+g
g/b)
g (MaI,
a/b)
1
Agdaa
Im
29
I
99
9
Ax
bdg
bÂR
g
T
In
1
a
lb
+
1
Aa
bdaa
I
g
T
Io
99
9
g
bdg
bdg
a.
I
1
T
Ib
1
aa
bda
bλa
Im
g T
Ib
+
99
9
bd
bdg
a
aa
T
I6 +
aa
T
bA
I
g
Ib
+
99
g
bdg
bdg Ag
L
aa
T
Ib +
aa
b
bda
475 To show Assertion (i), we note that according to 17
lim Ag -0 Agda
5
lim
(g Tg/hbb + > 60 (a Ta/bbb-
1a1)
8 (a a) - a
G g a
14

---

478 where the first equality uses the definition of Ç in (77). The second equality is due to the continuity of the matrix inversion and the last approximate equality follows from the K-FAC approximation (15).
478 To show Assertion (ii), we consider lim -to and lim independently, that is
lim Ag (AgIm + g'b)
(22)
400
-1
lim
Im + b%g
g g'g g
Im
Ag 100
479 and
lim da (daIn + a alabb) -1
(23)
Au 100000
lim
In +
1 a
T a
L..
700000
bda
480
This then implies
Ag (>gTm + +ggg +g/g/b) -1
lim 700
g
(24)
a da (aann + a T a/b)
Im a In = aa a,
481
which concludes the proof.
15

---

D Additional Experiments
482
0.07
0.07
0.06
0.06
0.05
0.05
K-AC Ua 01110--931
C/AC (ha 600 Bowedt
0.01
0.01
0.00
0.00
candber: descee
Gratenttesreen
3.00
M A.11
0.00
G/AC M2-
0.05
K-AG 0.0
0.05
EAM Murhe 2612
0.04
5G0 Namentam
0.04
Vemarian
0.03
500 taweoor
0.03
360 (aa0000)
Adam
2000
4000
5000
8000
10000
5
10
15
20 Epechs
25
30
35
40
Lraniing time
Figure 7: Training loss of the MNIST auto-encoder trained with gradient descent, K-FAC, C.C" S""" as well SGD larger batch size (600), K-FAC with 10x larger batch size (600), and Adam.
w/ momentum, SGD with Comparing the performance per real-time (left) and per number of epochs (right). We display both the training loss (top) as well as the test loss (bottom) Runtimes are for a CPU core.
0.92
0.90
0.88
Test Acc.
0.86
0.84
Gradient descant,
weight decay
layer. SGD momentum weight decay
Gradient descent, SGD
0.82
for last layer,
momentum
Gradient descent, SGD
<" for layer. SGD
0.80
25
50
100
125
150
175
200
Epochs
Figure 8: ResNet-18 trained CIFAR-10 with image augmentation and cosine learning rate schedule. The first line (bluc) uses the hyperparameters public implementation. To ablate the optimizer, additional settings are added, specifically, without weight decay and without momentum. Results are averaged over 5 runs and the standard deviation is indicated with the colored areas.
16

---

0.990
0.985
0.980
Test accuracy
23822 wwwwaaks
0.975
Gradian: descent
for layers 2,
layors
for layers
layers
2" for layers 3.4,3
layers
for byeer 2.4
0.960
500
750
1000
1250
1500
1750
2000
training time [s]
Figure 9: Test accuracy for training on the MNIST classification task using Ç" only in selected layers. Runtimes are for CPU.
17


Reviews:
[{"review_id": "gocYINIa7js", "reviewer": "Reviewer_7xsL", "summary": "Inspired by the KFAC approximation and the Tikhonov regularization of the Newton method, this paper proposes a regularized K-FAC approximated Gauss-Newton type method called ISAAC. The proposed method is based on only the input to a respective layer, therefore does not suffer from a substantial computational overhead. Numerical experiments show the advantages of the proposed method compared to both first-order type and second-order type methods. \n", "questions": "line 60: change [14],[15] to [14.15]. It is better to put multiple references in the same brackets. Please check other places.\n\nIt is better to add the discussion between GGN matrix and Fisher matrix, which can refer to [1,2] and related literatures.\n\nIt is better to add a left brackets after $\\eta$ and a right bracket before the gradient in eq.(16). Please also add brackets in a suitable place in eq. (17).\n\nIn eq.(19), the gradient should be $\\mathrm{g}^\\top a /b$ where the $b$ is missed. In eq.(19), the authors use the same batch to approximate the GGN matrix and compute the gradient. Can the batches for approximation of the GGN and the computation of the gradient be different? In that case, what the related theoretical properties will be?\n\nWhen the objective function is convex, the GGN matrix is positive semi-definite matrix. Adding a regularization parameter in GGN, It is t easy to show that $\\zeta$ is an ascent direction, which means Theorem 2 is trivial.\n\nThe authors consider the fully-connected neural network in this paper. I believe this method can be extended to convolutional neural networks. And in numerical part, the authors have done some experiments. I wonder can we obtain some explanation from theory for this case? \n\nFor the kronecker approximation of the GGN matrix, $\\mathrm{a}\\mathrm{a}^\\top$ is more important than $\\overline{g}^\\top\\overline{g}$ part. I once validate it numerically. One reason is that each value of the matrix $\\overline{g}^\\top\\overline{g}$  is very small so that the $\\lambda_g$ domains. I have noticed one related work recently. The work is named NG+[3].\n\n[1] Botev, Aleksandar, Hippolyt Ritter, and David Barber. \"Practical gauss-newton optimisation for deep learning.\" International Conference on Machine Learning. PMLR, 2017.\n\n[2] Martens, James. \"New insights and perspectives on the natural gradient method.\" The Journal of Machine Learning Research 21.1 (2020): 5776-5851.\n\n[3] Yang, M., Xu, D., Cui, Q., Wen, Z., & Xu, P. (2021). NG+: A Multi-Step Matrix-Product Natural Gradient Method for Deep Learning. arXiv preprint arXiv:2106.07454.", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nRegularization parameters is crucial for second-order type methods.  The authors first approximate the GGN matrix as a kroncker product of two matrices, and then view two regulation parameters independently. By letting the two regularization parameters vanish or go to infinity, one can obtain new directions and therefore new methods. The proposed method is more efficient than KFAC since only one matrix should be inverted and no need extra propagation to compute $g$.  \n\nWeaknesses:\n\nThis paper should be polished to make it easier to read. \n\nSome related literatures on second-order methods should be mentioned, such as Shampoo[1], KBFGS[2], NG+[3] and SENG[4]. \n\nSome theoretical properties is natural and trivial. It is better to formalize an algorithm and give a convergence result.\n\nIt is better to add some large numerical examples, such as Resnet50 with Imagenet-1k and make a comparison with other second-order methods Shampoo[1], KBFGS[2], NG+[3] and SENG[4]. \n\n[1] Gupta,V.,Koren,T., Singer,Y.:, Shampoo: Preconditioned stochastic tensor optimization. In: International Conference on Machine Learning.\n\n[2] Goldfarb, D., Ren, Y., Bahamou, A.:, Practical quasi-Newton methods for training deep neural networks. In:Advances inNeural Information Processing Systems.\n\n[3] Yang, M., Xu, D., Cui, Q., Wen, Z., & Xu, P. (2021). NG+: A Multi-Step Matrix-Product Natural Gradient Method for Deep Learning. arXiv preprint arXiv:2106.07454.\n\n[4] Yang, M., Xu, D., Wen, Z., Chen, M., & Xu, P. (2020). Sketch-based empirical natural gradient methods for deep learning. Journal of Scientific Computing.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "QMvoL3al-12", "reviewer": "Reviewer_mLvU", "summary": "The paper addresses the problem of using second-order information in large-scale machine learning tasks (e.g. training neural networks). It proposes a Kronecker-factored Approximate Curvature (KFAC)-approximated, Tikhonov regularized Gauss-Newton (GN) update step. Instead of a single regularization parameter ($\\lambda$), the update step in the paper uses two independent regularization parameters ($\\lambda_g$ and $\\lambda_a$). The paper relates different settings of $\\lambda_a$ and $\\lambda_g$ to other algorithms (i.e. classical GN and gradient descent). It shows that allowing $\\lambda_g$ grows to infinity gives a computationally efficient update step. It provides empirical results on their proposed method.", "questions": "1. Line 70 refers to $H$ in Equation 6. Typo?\n2. Is there an intuitive interpretation of the preconditioner $M$ in Remark 2? Does this preconditioning help in terms of reducing the number of iterations needed to reach a solution?", "limitations": "This work does not appear to me to have negative social impact.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The update step $\\xi^*$ is interesting and practical. The paper provides experiments to show that using $\\xi^*$ can lead to lower computation time without sacrificing performance. Experiments are thorough and tested on some fairly large neural network architectures.\n2. The update step $\\xi$ is a nice, compact way to describe an algorithm for training neural networks. The analysis of $\\xi$ provides various ways of interpreting the algorithm in terms of different regularization parameter settings. The properties of $\\xi$ are interesting. The analysis is relatively thorough (e.g. showing that any combination of $\\lambda_g$ and $\\lambda_a$ will still result in a descent direction).\n3. Paper is well-written and clear. \n\nWeaknesses\n1. Some of the experiments are not benchmarked to SOTA (which is acknowledged by the paper). This might affect people's willingness to adopt the method in practice.  ", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "EhV4Wq2MV8", "reviewer": "Reviewer_uc7m", "summary": "This paper proposed a KFAC variant to improve the computation efficiency. It introduces two Tikhonov regularization terms into KFAC, and makes gradient conditioning more efficient by force $\\lambda_g$ go to infinity. The authors present a theoretical guarantee that the optimization still goes in the right direction even with such an adaptation. The authors also show ISAAC is more computation efficient in small-batch stochastic regimes.\n\nHowever, I feel contributions in this paper are rather limited, and some motivations might need further justification.\n", "questions": "See my comments above.", "limitations": "No", "rating": 5, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n\nThe paper is well written. Preliminaries and methods are clearly explained. \n\nWeaknesses:\n\n1, Contributions are limited. Reducing the compute costs of KFAC is a good problem. However, I am not convinced that separating the regularization term and using a large regularization is a novel and effective solution. It only makes the optimizer behave more and more like SGD. As the authors stated in Theorem 1, small $\\lambda_a, \\lambda_g$ leads to KFAC, while large $\\lambda_a, \\lambda_g$ leads to vanilla gradient descent. \n\n2, Empirical results need to be enhanced. The authors use several empirical results to support the claim that ISAAC still behaves like KFAC even though using a strong regularization factor. However, I do not think current results are strong enough to support the claim. The issues in the empirical evaluations also make me doubt the contributions in the paper. \n\n- 2.1, The author should provide more baselines (Adam, SGD with momentum) so that we can really have a fair evaluation. \n\n- 2.2, For Figure 1, my understanding is that the authors are trying to show ISAAC still obtains good results (loss and accuracy) even with large regularization. If so, I do not think it is necessary. As the authors stated in Theorem 1, larger regularization makes ISAAC behave more like SGD. Therefore, getting similar loss and accuracy is no surprise.\n    \n- 2.3, For Figure 2, there are several issues. First, hyper parameters are not fully revealed. For instance, what is the weight decay for each optimizer since weight decays large affects training convergence?  Second, only the training curve is reported. The author really should present both a training and validation curve. In many cases, we can have faster convergence on training dataset, but not for validation dataset. \n\n- 2.4, For Figure 6, the reported accuracy is obviously lower compared to results we usually have on CIFAR-10. The reason might be that the authors use SGD without momentum. However, I am not convinced under such a setting. SGD with momentum is a default setting in many training tasks. Without momentum, I do not think the results will provide meaningful comparisons and conclusions.\n\n3, Training with small batches should be further justified. I understand the authors stress the compute benefits of ISAAC in a small-batch regime (Theorem 3-ii). However, considering more general settings, the authors should well justify it: is it worth accelerating the training using small batches given the fact that large batches can also improve convergence performance even using SGD. Therefore, I think not only should the author provide results in small-batch regimes, training using large batches should also be evaluated and compared with other baselines.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "DM9Tzkb3BRv", "reviewer": "Reviewer_jPXR", "summary": "In unconstrained optimisation, Newton's method uses inverse Hessian to determine the step size of the update. When applied to deep learning, the sheer size of the Hessian matrix makes Newton's method intractable. Among existing attempts to address this challenge, K-FAC is a promising approach. In practice, Tikhonov regularization/damping is used to avoid divergence.\n\nIn this paper, the authors introduced an extension to the standard Tikhonov damping for K-FAC. The main idea is to use two independent damping parameters (hyper-parameters for regularisation) instead of one damping parameter, one for the gradient factor and one for the activity factor, as shown in Equation (17). The authors explored special cases where the two parameters are either 0 or infinity. They also discussed the special case of setting one parameter to infinity, effectively removing the gradient factor in K-FAC. One major claim was that this activity-only form has an advantage in reduced computational complexity, although I don't find a theoretical comparison with K-FAC in this aspect. \n\nThe claim for computational efficiency was mostly supported via empirical evaluation.", "questions": "What is the intuition behind Eq (21)? Compared with Eq (13), why is it a good approximation?", "limitations": "N/A", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The paper addresses an important problem: efficient approximation of Gaussian-Newton approximation\n2. The exposition is mostly clear, especially if you are already familiar with the existing literature.\n3. The experiments seem comprehensive.\n\nWeaknesses:\n\n1. It is not clear what is the main contribution of this paper. Is it the two-parameter damping mechanism (What advantage do we gain)? Or is it the special case mentioned in Remark 3 (Why this is a still good approximation without $g^{\\top}g$)? \n2. Many theoretical results presented look rather trivial.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Reject