An Improved Empirical Fisher Approximation for Natural Gradient Descent
Authors: Xiaodong Wu
Wenyi Yu
Chao Zhang
Phil Woodland
Venue: NeurIPS 2024 poster (2024)
Keywords: Empirical Fisher
Natural Gradient Descent
Second-order Optimisation
Deep Learning
Primary area: optimization
TL;DR: An improved Empirical Fisher is proposed to resolve the limitations of Empirical Fisher.

Abstract: Approximate Natural Gradient Descent (NGD) methods are an important family of optimisers for deep learning models, which use approximate Fisher information matrices to pre-condition gradients during training. The empirical Fisher (EF) method approximates the Fisher information matrix empirically by reusing the per-sample gradients collected during back-propagation. Despite its ease of implementation, the EF approximation has its theoretical and practical limitations. This paper investigates the *inversely-scaled projection* issue of EF, which is shown to be a major cause of its poor empirical approximation quality. An improved empirical Fisher (iEF) method is proposed to address this issue, which is motivated as a generalised NGD method from a loss reduction perspective, meanwhile retaining the practical convenience of EF. The exact iEF and EF methods are experimentally evaluated using practical deep learning setups, including widely-used setups for parameter-efficient fine-tuning of pre-trained models (T5-base with LoRA and Prompt-Tuning on GLUE tasks, and ViT with LoRA for CIFAR100). Optimisation experiments show that applying exact iEF directly as an optimiser provides strong convergence and generalisation. It achieves the best test performance and the lowest training loss for the majority of the tasks, even when compared to well-tuned AdamW/Adafactor baselines. Additionally, under a novel empirical evaluation framework, the proposed iEF method shows consistently better approximation quality to exact Natural Gradient updates than both the EF and the more expensive sampled Fisher methods, meanwhile demonstrating the superior property of being robust to the choice of damping across tasks and training stages. Improving existing approximate NGD optimisers with iEF is expected to lead to better convergence and robustness. Furthermore, the iEF method also serves as a better approximation method to the Fisher information matrix itself, which enables the improvement of a variety of Fisher-based methods, not limited to the scope of optimisation.

An Improved Empirical Fisher Approximation for Natural Gradient Descent
Xiaodong Wu'+
Wenyi Y
Chao Zhang²
Philip Woodland'
Dept. of Engineering. University of Cambridge
Dept. of Electronic Engineering, Tsinghua University (xw338, Stw338,pw11e pw117)@cam ac. uk {ysy220mails, c2277@maill tsinghua. edu. cn
Abstract
Approximate Natural Gradient Descent (NGD) methods important family of optimisers for deep learning models, which use approximate Fisher information matrices pre-condition gradients during training. The empirical Fisher (EF) method approximates the Fisher information matrix empirically by reusing the per-sample gradients collected during propappopag Despite its ease of imple- mentation, the EF approximation has its theoretical and practical limitations. This paper investigates the inversely-scaled projection issue of EF, which is shown to be major cause of its poor empirical approximation quality. An improved empirical Fisher (iEF) method is proposed to address this issue, which motivated as a generalised NGD method from loss reduction perspective, meanwhile retaining the practical convenience of EF, The exact iEF and EF methods are experimentally evaluated using practical deep learning setups, including widely-used setups for parameter-effiin eeffntte-eeffcientt fine- min-ttning of pre-trained models (T5-base with LoRA and Prompt-Tumine
GLUE tasks, and VIT with LoRA for CIFAR Optimisation experiments show that applying exact iEF directly as an optimiser provides strong convergence and generalisation. It achieves the best test performance and the low- est training loss for the majority of the tasks, even when compared to well-tuned AdamW/Ate A/dfffccor baselines. Additionally, under a novel empirical evaluation framework, the proposed iEF method shows consistently better approximation quality to exact Natural Gradient updates than both the EF and the more expensive sampled Fisher methods, meanwhile demonstrating the superior property of being robust to the choice of damping across tasks and training stages. Improving existing approximate NGD optimisers with iEF is expected to lead to better convergence and robustness, Furthermore, the iEF method also serves as a better approximation method to the Fisher information matrix itself, which enables the improvement of a variety of Fisher-based methods, not limited the scope of optimisation.
Introduction
Parameter optimisation crucial research area in the field of deep learning, where stochastic optimisers are commonly used which update the model parameters iteratively to minimise target loss function. Approximate Natural Gradient Descent (NGD) [T] methods are an important family of approximate second-order optimisers, which pre-condition the gradient with the (approximate) Fisher information matrix (also called the Fisher matrix) accelerate training or improve generalisation.
Although there are many successful optimisers based on approximate NGD, many of them in fact the empirical Fisher (EF) as pre-conditioner. These methods are referred as approximate empirical NGD methods [52]. The EF method constructs an approximation to the exact Fisher matrix directly from the gradients of training samples, which are usually readily computed during the
These authors contributed equally to this work
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

training process 220 In contrast, the exact Fisher matrix needs to be either sampled from the model output distribution 26], or requires repeated evaluation of the matrix-vector product with the Fisher matrix [25] which are both expensive operations. As a result, due to the ease of implementation brought by EF, empirical NGD used in many approximate NGD optimisers as the default choice
33
54
10 11 52 51].
Despite the prevalence of empirical NGD optimisers. it known that EF is in general a questionable approximation to the exact Fisher matrix [26
20
47 The poor approximation quality of EF-based
updates has been experimentally verified for small scale experimental setups by (20 47 However,
traditional evaluation methods are used in 220
47 where the exact NG update and Fisher matrix
need to be explicitly computed, making their findings impossible to verify for large deep learning
setups for practical tasks. Hence, a more generally applicable evaluation framework is needed. There also a need for an improved approximation to the exact Fisher matrix (as a pre-conditioner) than EF, while being as efficient to implement. This paper aims to fill these gaps.
Our Contributions: In this paper, an improved EF (iEF) approximation for NGD is proposed, which provides a better approximation to the exact Natural Gradient (NG) updates, while maintaining the practical convenience of EF. This method allows for straightforward upgrade for all existing approximate empirical NGD optimisers. To achieve this, a theoretical investigation into the behaviour EF update is first carried out, where the impact of the EF update on each involved sample is analysed (the "involved samples" refers to training samples whose gradient is used to construct the EF update). This leads to finding the inversely- scaaled projection issue of EF (see Sec. 4 Accordingly, the iEF method is proposed to overcome this issue by introducing diagonal scaling matrix to the standard formulation of the EF pre-conditioner. is motivated as an approximate Gauss-Newton algorithm from a loss reduction perspective, with global convergence guarantees under mild assumptions (see Sec. 5 A novel empirical evaluation framework for approximate NGD methods is then proposed to enable accurate comparison of approximate Fisher pre-conditioners (e.g. EF and iEF) in large-scale optimisation setups (see Sec. (). We conducted experiments that compare the exact EF and iEF methods in a range of practical deep learning setups including computer vision and fine-tuning large language models. Under our evaluation framework, iEF demonstrates better approximation quality to exact NG updates than both EF and the more expensive Monte- Carlo sampled Fisher method (SF, Appendix[E] meanwhile being significantly more robust to the choice of damping across tasks and training stages. Direct application of iEF optimiser also shows consistently strong generalisation and convergence, even when compared to well-tuned Adam W/Adafactor baselines (see Sec.
2 Related Work
Approximate (Empirical) NGD: There are many existing approximate (empirical) NGD methods, most of which use EF despite its theoretical limitations. Some prior work, e.g. [43 40
uses the
Woodbury identities (36) to exactly compute EF updates. Recent block-diagonal methods (based on K-FAC (27) have gained popularity due to their efficiency, which includes work that modify
3 or distributively apply K-FAC optimisers [34] 49 Sometimes Adagrad-based methods [9] 13 17 are also regarded as empirical NGD methods.
the K-FAC approximation [54] 10.
52,
However, the connection is questionable (20) these methods use the square-root of the EF matrix, instead of the EF matrix itself, as pre-conditioner.
Limitations of EF Approximation: The limitations of EF as approximate Fisher matrix have been discussed and demonstrated in several papers (26] 20 47), among which (20 provided a thorough review and analysis. However, as far as we are aware, there has been no prior work that analysed the exact EF method in larger deep-Icarning setups, and most of the observations are limited to small-scale problems for theoretical machine-lcariing studies. It is known, however, that practical EF-based optimisers usually require a sophisticated damping scheme to work well [33] 3T). It has even been suggested that an infinitely large damping should be used with the gradient covariance term 33). These observations can be tied to the theoretical limitations of EF.
Empirical Evaluation of Approximate NGD Quality: An accurate evaluation of the approximation quality to exact NG updates is of great importance for approximate NGD methods. Usually, the performance of the method of interest is evaluated which provide crucial information from the optimisation perspective. However, limited information about the approximation quality to exact NGD can be drawn from these experiments. Therefore,
machine learning benchmarks [54] 27

---

additional ssale experiments are usually performed to compare against the exact Fisher matrices 27 ITI or the exact NG updates [20) 31 which are extremely difficult do for commonplace large-scale models. This limits our understanding of these methods in the context of large-scale tasks.
3 Preliminaries
Supervised Learning for Classification Model with Softmax Activation: This paper considers supervised learning of categorical classification, where a probabilistic model is trained to predict outputs y {c/c 1, 2. ... C} of C categories from inputs E X. The target model E IR. as the model parameters, which outputs the logits 2 E RRC Assume a softmax activation is used on the logits, the model can be expressed as a conditional probability of po (y)zz). Given N i.i.d. training samples (I 8n) yn) (assuming N < P), the following accumulated loss is minimised
So (a=) has
[(0) = Σ, log po (y ynlz,) = Σ,,, In: T
(I)
where 1,, = poly yn (x))) is the categorical cross-entropy loss for the n-th training sample. For brevity, we denote (y) = cl ) = (c).
A vectorised representation of loss L E RN is used where ( 12,,2, .Nx] The accumulated loss then becomes (()) En
I where 1 is an all column vector of matching dimension, and the accumulated gradient can be re-written as Vo((0) Vel where Vøl RNN is the Jacobian of per-sample losses w.r.t model parameters.
NGD and Empirical NGD In first-order optimisation method, say SGD 42 the update direction on the model parameter is the estimate the accumulated gradient (o) In the NGD method (26). the gradient is pre-condin rrecconditooeed by the Fisher matrix F (i.e. F F- Vo((() accelerate convergence. The exact Fisher matrix can be computed from the model output distribution using available training samples as follows
F: F= E.= pa(c) Vo log (c) log Px)
The Fisher matrix can be estimated with Monte-Card (MC) sampling 27 This approximation method is usually used with one MC sample per training sample, which is termed SF in this paper (see Appendix Ep. Alternatively, when the model is well trained and pr, (3x) + for all N samples, is possible approximate the exact Fisher with EF using the empirical gradient as follows
F F: E; Volog (y.) Vo log Pn (v.)) Vol Vol.
Pre-conditioning the gradient with the EF matrix (i.e. F ()(()) yields the empirical NGD method. Although empirical NGD is prevalent due to the convenience of computing the EF matrix in practice, the approximation quality of EF to the exact Fisher matrix is worth questioning 20 47
Anversely-Scaleee Projection Issue of Empirical Fisher
Despite the practical prevalence of the EF method, it is generally believed to be a poor approximation of the exact NGD method (20). To better understand the cause of the limited approximation quality of the EF method, an analysis of the impact of the EF update on each of the involved samples is presented below. This leads to finding the "inversely-sculed projection issue" of the EF method, which provides focus for the improvement of the EF method.
4.1 Formal Definition
Recall the definition of EF in Eqn. defined as follows
3 The empirical NG update (or just the EF update) can be
A = - 'v -7 (Vel Vol AI) - (Vol'
(4)
where x E R is a small damping factor to facilitate inversion (gradient covariance matrix Vol Vol PxP cannot directly inverted for werrpparameterised models). Using the Woodbury identity 36). the EF update can be re-expressed as follows:
A - Vol (V + +AI) '1.
(5)
3

---

The loss change induced on each sample (denoted AlFF) when applying the EF update to the model can be estimated using the Jacobian Vol as follows:
A Vol = 7 VolV at (VolVol" + XI) -111
This result means that EF updates have the property of inducing equal loss reduction on every involved sample. For the n-th sample, the projection of the EF update onto gradient direction Valn (denoted as (KF) can be computed as follows
Voln
(Km EF A0FF
(6)
V Vellll
where | denotes the 12 norm of the n-th per-sample gradient. This means that the projection of EF update onto every sample gradient is inversely proportional to the gradient norm of each sample. Note that smaller ||Vol, ll2 generally indicates the sample better trained (or more converged, or closer to its minimum). The EF update is therefore easily biased towards well-trained samples, and tends to have a larger norm as training progresses Valn 2l2 decreases) 220). We term this the snversely-scaled projection issue of the EF update, which is further illustrated in the following section.
4.2 Visual Illustration
The detrimental impact of the inversely-scaled projection issue of EF updates is illustrated in 2- 2-parameter 2-datum linear least-square regression problem in Fig. (third plot). It is shown that EF updates are "attracted" to the minimum of each training sample (the dashed lines), leading to distorted update vector field and inefficient training trajectories. Also, EF updates have a much larger norm when either training sample is nearly converged, suggesting the necessity of complicated step-size scheduler. Please refer to Appendix B for detailed description and discussion, which also includes an additional visualisation for a logistic regression setup in Fig. 4 which leads to similar observations. These effects of the inversely-scale projection issue are further validated in experiments (E1) and (F:2) large-scale deep learning setups Sec.
SGD
NGD/EF
EF
Figure I: A visual comparison of Fisher, iEF and EF as pre-conditioners for a 2-parameter 2-datum linear least-squares regression problem inspired by (20) (see Appendix B for details). All three plots are loss landscapes with the æ-axis and y-axis representing 0n and 01 respectively. The first plot shows the gradient vector field of the loss function and sampled training trajectories for SGD updates. Similarly, the second plot is for NGD/EFF updates and the third plot is for EF updates (with zoomed view). The global minimum (0, is marked with a star where visible. The two dashed lines on all plots represent the optimal parameter sets for each training sample. It can be seen that the EF method has highly distorted update vector field while the iEF and NGD methods adapt the curvature of the problem successfully.
Improved Empirical Fisher
The EF method is a widely used approximate NGD method, mainly because it can be implemented conveniently by constructing the EF matrix with the per-sample gradients that are readily computed during backpropagation. In this section, we propose the improved EF (iEF) method which preserves implementational convenience of projection issue. The iEF method can be justified as approximate (generalised) NGD method from a loss reduction perspective. Continuous-tinn convergence analyses also show that the iEF method guarantees uubllinarr/liner convergence to the global minimum under mild assumptions.
method, meanwhile alleviating the inversely-scaled

---

5.1 Update Formulation
The nature of the inversely-scalet projection issue that the EF update enforces constant loss reduction regardless of the convergence level of each sample (see Sec. 4.1. To address this issue, the iEF update is designed induce per-sample loss reduction that takes into account the convergence level. The loss reduction induced by the iEF update for the n-th sample is designed to be
(lE)) Vol,, A -1 Vv, 12.
where >V,, 4nll2 is the gradient norm at the model output logits-level. Note that =,, 4ull2 in general decreases as the r-th sample gets better trained because of the positive convexity of the objective of interest (cross-ent) enssopy with softmax activation). Therefore, this update formulation allows the induced per-sample loss reduction by the iEF update to be closely related to how well sample has converged, which then greatly alleviates the tnverselysscalee projection issue of the EF method.
A viable formulation of the iEF update AFE that both satisfies Eqn. 7 per-sample gradients is proposed as follows
and relies only on the
Arr = - Vol (VolVol" + AT) SHE,
(8)
where SEr E TR- is a scaling vector defined as
S 21, 2V
V VN 12]
which can be obtained along with back-propagation (e.g. in Pytorch (32) with negligible overhead. This improved formulation for EF is shown to be effective. In the toy examples in Fig. [ and 4 switching from EF to iEF completely removes the distortion in the EF update vector fields. Results in Sec. also alss validate that iEF achieves consistently better approximation quality NG updates than both EF and SF methods in practical deep learning setups (experiment (EI)), meanwhile being robust the choice of damping À across tasks and training stages (experiment (E3)).
5.2 Theoretical Connection to Generalised NGD
The choice of scaling vector &FFF is motivated by the Gauss-Newton (GN) algorithm, which is type of generalised NGD method (30. The update for the GN algorithm is defined as
A = -7 G-
where G-E, VOz, Voz, the GN matrix. The GN algorithm can be effectively viewed gradient descent method on the model output logits space -space) and the loss reduction induced for the n-th sample by the GN update approximately
(10) which takes exactly the same form as the per-sample loss reduction induced by the iEF update (see Eqn. (7). Therefore, the iEF method can be regarded as an efficient approximation to the GN algorithm in terms of its loss-reduction behaviour. particular, can be shown that the iEF method is equivalent to the GN algorithm for all supervised learning problems with regression model and the exact NGD method for the least-squares regression problem (see Appendix A)..
Alln)N -1 V/. 1..12.
5.3 Convergence Analysis
In this section, two continuous time convergence analyses are provided for the stoshatccc version of the iEF method, which shows its sub-linear linear global convergence guarantee for different types of objective functions (see Appendix for proofs). The analysis can be considered as extensions of proofs provided in (53) to setups using non-regression models and cross-entropy objectives. The two base assumptions used by the two convergence analysis are as follows:
Assumption 5.1. At time the full-batch, un-damped iEF update model parameters ((1) is
d0(() Vecc ( [[ ((mr(t)))
(11)
dt
Assumption 5.2. Vt 0, the gradient covariance matrix (or Gram matrix) [ooo]())[[ is always full rank.
The two main conclusions of the analysis are described below.
5

---

Sub-linear Global Convergence for Softmax + Cross-Entropy Objective When the target model
uses softmax output and cross-entropy loss (as described in Sec. D. the Theorem |. 5.3 can be proved.
Theorem 5.3. Suppose Assumption 5.2 holds, vn E fI,...,N ,N, the target probability (n) :=
Poct) (y- - yn un for the n-th training sample is bounded as follows
2
(t( > 1 t Co +1
(12)
where Co = [-) + log (0)
Pa( and max { (-1 03.
Linear Global Convergence for Strongly Convex Objective When the target model uses an m-strongly convex objective function [2] (see Assumption C.2 note that cross-entropy loss does not
satisfy this assumption), the Theorem 5, can be proved.
Theorem 5.4. Suppose Assumption 5.2 and C.2 holds, Vn E {l,...,N, N) the per-sample loss b, (t)
for the n-th training sample is bounded follows
(n(t) 1 S e 2mL (L) - -M))
(13)
where 1n is the minimum loss for the n-th sample.
Remark: Theorem 5.4 only assumes a strongly-convex target objective w.r. model output (As- sumption C.2) The target loss landscape w.zr model parameters can still be arbitrarily non-convex depending on the target model structure.
5.4 Applications of IEF
As an approximate NGD method, the exact iEF method can be used directly an optimiser (see Algorithm| [ for models with a small parameter size. Its performance is evaluated in experiment (E2) in Sec. 7 which demonstrates competitive convergence and generalisation when compared to well-tuned baselines. Refer to Appendix. D.T for discussions on the implementation and complexity.
More importantly, the iEF method provides an improved approximation method to the exact Fisher matrix. The iEF approximated Fisher matrix (iEF matrix) F* E PR"x takes the following form
F Vol diag $
Vol.
(14)
which can be derived from Eqn. 8 (sec Appendix D.2.1 F by design takes a highly similar form
to the EF matrix (see Eqn 3 making them equally convenient to compute. Also, results in Sec. 7
show that updates preconditioned with the iEF matrix achieve consistently better approximation quality to NG updates than both EF and SF updates, meanwhile obviating the need for damping tuning. Consequently, the iEF matrix can be considered as cheap yet better approximation method for the Fisher matrix than both the EF and SF methods, which opens up the possibility of improving wide range of Fisher-based methods (not limited to optimisation methods). An example is provided in Appendix [.2.2] to demonstrate that iEF can be easily integrated into the popular empirical K- FAC optimiser [37]. Preliminary experimental results show that the integration leads to consistent improvements of the approximation quality to exact NG updates. Another example is provided in Appendix D.2.3 to demonstrate that iEF can be directly applied to improve the EF approximated Hessian used in the WoodFisher algorithms for model compression [6).
6 Empirical Evaluation Framework for Approximate NGD Methods
Traditional evaluation methods for quality of approximate NGD methods have high memory and time complexity, which is infeasible for large setups (see discussion in Sec. (). In order to accurately evaluate the quality of approximate NGD methods (EF, iEF, SF etc.) in practical deep-learning setups, we introduce an efficient empirical evaluation framework which enables a quantitative comparison of different approximate NGD methods under large- scale setups. For given approximate NGD method that generates an update A6, our proposed evaluation framework satisfies the following requirements: 1) provides a quantitative evaluator 7( (AO) that measures the (direction-wise) approximation quality to the exact NG update; 2) the evaluation process is efficient in modern auto-grad frameworks, and it poses no constraints on the size or structure of the target model. The implementation and theoretical motivations of this empirical evaluation framework are discussed in the following sections.

---

6.1 Efficient Indicator of Approximation Quality
The proposed evaluation framework revolves around the indicator 7(0) which is designed to accurately reflect the quality of an approximate NG update. while being efficient to compute. For an update A of interest, the proposed indicator (50) RR defined as
(AO FAO)
7 (20) = AO Vo[(o))
(15)
and the smaller the value of (A0)), the better the approximation quality of A to the exact NG update. This indicator mainly requires computing a matrix-vector product with the exact Fisher matrix (i.e. FA0), which can be efficiently done in modern auto-grad frameworks (32) This allows for the application of this framework to large-scale models in practical setups. Refer to Appendix F.T F.T for implementationn details, algorithm complexity and comparison with traditional methods.
6.2 Theoretical Motivation
In this section, the proposed indicator 7-) is justified theoretically appropriate evaluator of the quality of an approximate NG update. An alternative definition for the NGD is first proposed, which formulates the NG update direction with an unconstrained optimisation problem
F VoL(O) = arg min 7 (A0))²
(16)
where ç' E IR is an arbitrary non-zero scalar. It is shown that this alternative definition for NGD is implicitly used in the Hessian-free method [25] and the linear conjugate gradient (CG) algorithm used in Hessian-free Appendix F.2 for proof). Under this definition, any approximate NG update with smaller 7( (A))² is a "strictly better approximation"
solve for the exact NG update is locally optimal minimiser for )A)) (see
the exact NG update (which is the minimiser for (AA))
Furthermore, (A0) can also be justified from a second-order optimisation perspective. 2y())) is shown to quantify the maximum achievable loss reduction for given update direction under a local quadratic approximation of the loss function (see Appendix. |F for proof). Consequently, the proposed indicator can be used to accurately predict the convergence ability of a target update generation method (see experiment (F2) in Sec.
7 Experiments
Experimental results are presented this section. The main goal of the experiments is to verify that the behaviour of exact EF and iEF methods align with our theories in practical deep learning setups. Mainly three approximation methods are compared: EF, iEF and SF (an unbiased yet more expensive Fisher approximation method, see Appendix P.. The exact updates of each method generated based on Eqn. (5) (8). (49) respectively. Fifteen different setups are used to evaluate the optimisation performance and the approximation quality of these methods, including widely used parameter-efficient fine-tuning (PEFT) for pre-trained models. These include T5-base with LoRA and Prompt-Tuning on GLUE tasks 7 and ViT with LoRA for CIFAR [3). PEFT of pre-trained models is investigated because it involves large-scale practical models, while having small trainable parameter size (the implementation of exact EF, iEF and SF methods are memory intensive, see Appendix D. Please refer to Appendix H.I for detailed experimental setups. The following three findings are demonstrated with our experiments.
(F1) The approximation quality (to exact NG updates) of EF, iEF, SF and SGD was evaluated and compared using the proposed evaluation framework Sec. 6 on all setups. It is shown that iEF consistently improves on SGD updates and is superior to both EF and SF methods for the majority of the training stages for all setups.
(E2) The optimisation performance of EF, iEF, SF and SGD was evaluated on all setups. For each task, additional well-tuned baseline optimiser (Adafactor/AdamW) that iEF consistently achieves comparable or better performance than the corresponding baseline, while EF and SF suffer from unstable training different extents.
also compared. It is shown
(E3) The impact of damping on the approximation quality EF, iEF and SF was analysed under the proposed evaluation framework. It is shown that the quality of traditional EF and SF methods relies
7

---

heavily on careful damping tuning, unlike iEF which works well with any near-zero damping across tasks and training stages.
Finally, results for an additional experiment considering a 10M parameter Multi-layer Perceptron (MLP) on the CIFARIO (19) dataset are provided in Appendix H..7 This additional experiment further validates the aforementioned findings for a train-from-scratch setup with a much larger (10x) trainable parameter size.
EI: Approximation Quality to NG Updates The behaviour of updates generated with EF, iEF, SF and SGD methods were compared using the proposed empirical evaluation framework in terms of their approximation quality to exact NG updates. The updates for EF, iEF and SF were generated according to Eqns. (5) { and (49) respectively, and the evaluation framework follows Algorithm 4 The "un-damped" behaviour of these methods is analysed and a near- zero damping factor is used for update generation. The checkpoints at the end of each epoch generated by the baseline optimisation methods (Adam W/Adafactor) for each task were used for evaluation. In each evaluation. For each checkpoint f(t), indicators were computed from 100 batches of randomly picked training samples of the target task of batch size M- = 160. The averaged indicator for each update were then evaluated (7(A0sca(!)) 5 (A)FF()), (A0 ((). (A0ss(()) which are denoted as 7SGD; TiFF, YEF, 7SF for simplicity). The relationship among these indicators across epochs and tasks is shown in Fig. 2 Note that results are presented for only 3 representative setups due to space limit (indicator plots for all tasks are shown in Appendix I. Three findings can be concluded from these figures: 1) EF achieves poorer approximation quality even than SGD updates for most training stages and tasks. This is aligned with the finding in prior work that EF is a questionable approximation to NGD. 2) The fourth plot shows that the gradient norm imbalance gets larger as training progresses. This correlates well with both the EF and SF curves, while impacting iEF less. This means that the inversely-sen scaleed projection issue indeed plays a significant role in reducing the approximation quality of the EF (and SF) approximation. 3) Comparing the first three plots, it can be seen that, for the majority of the training stages, the approximation quality follows iEF > SF > EF. IEF gives a consistently better approximation, and EF and SF are only able to beat iEF at the start of training (where a good approximation to the NG update has less impact).
YerlYsco
Vier/Yoc
YerlYson
Gradient Norm Imbslance
10
10P
10t
10P
10
102
107
10
13
10
10
Epcor
Ecoch
1/
QGPTT5-PT) + (NU(TS-LORA)
+ CIFARIOOWWT-LORA
Figure 2: Four (log-scaled) ratios computed for checkpoints at various stages of training (sampled at the interval of one epoch) for of the all 15 tasks. The r-axes represent the training stages of the model. 0% means the initialised model and 100% means model at the end of the last epoch. Each data point is averaged across 100 evaluations, and the error bars represent the standard deviation (1-sigma). The first plot shows "/FF PEF//SGD. which denotes the relative approximation quality improvement of EF updates w.e.t SGD updates (the lower the better). The second plot shows "HEr//sCn and the third plot shows "/sp/ "/SP//EP- The last plot depicts the imbalance of gradient norms, which is the average ratio between the maximum and minimum gradient norm for each evaluated batch (a larger value indicates more imbalanced per-sample gradient norms, which should lead to more significant inversely-scales projection issue). Overall, the approximation quality follows iEF > SF EF.
E2: Optimisation Performance The exact iEF, EF and SF methods were implemented as stochastic optimisers (following Algorithms respectieely. The same near-zero damping factor was used as in (E1). The averaged test metrics for GLUE and CIFAR 100 for each optimiser are shown in Table (see full test results in T validation result in Table final training loss in Table and training curves in Fig. 12 and 13p. The following three observations can be made:
1) From the final training loss reported in Table 5 the ranking of final training loss generally follows
iEF < Adamm/Adafactor < SGG < SF EF (the lower the better). This ranking of training
8

---

convergence follows the ranking of indicators in (EI) closely, demonstrating the effectiveness of the empirical evaluation framework in predicting the training behaviour of optimisers. 2) For most of the tasks, EF always suffer from unstable training (see training curves in Fig. an] T3p, while iEF consistently reaches the lowest training loss at the end of training (even when compared with well-tuned Caafactor/Adam W baselines). This further confirms the inversely-scale projection issue of EF, and demonstrates the strong convergence ability of the proposed iEF method. 3) From test results in Table I it can be seen that iEF achieves the best generalisation for Prompt Tuning tasks (outperformed Adafactor in 6 out of tasks). For LoRA tasks, iEF remains competitive to AdamW W with each of them outperformed the other in 4 out of tasks. This is likely because LoRA setups (which on average have 50 times more trainable parameters than Prompt Tuning) have a stronger reliance regularisation and momentum, which have not been properly extended to use together with the exact iEF optimiser yet. Overall, iEF achieves the best generalisation for the majority of tasks (10 out of 15), indicating its potential as a strong optimiser for PEFT for pre-trained models.
Table 1: Average test performance of different optimisers for GLUE and CIFAR1O0. For GLUE tasks, the average metric results for the 7 tasks are used as the final test score. For tasks with two metrics, these metries are averaged first (50). For all tasks, the test result is computed for the best validation accuracy checkpoint. Refer to Table 7 for more complete test performance report and detailed explanations on metrics.
A Adafactor SGD
EF
SF
iEF
GLUE + T5 + Prompt Tuning
77.1
67.4
48.1
69.7
79.3
GLUE + T5 + LoRA
80.1
77.3
63.1
76.5
79.3
CIFAR100 + VIT + LoRA
93.9
91.3 31.0 92.8 94.3
E3: Impact of Damping As is discussed Sec. 2 practical approximate NGD optimisers rely heavily on good damping schedule, which is typically chosen based on empirical experience (27). Using the proposed evaluation framework, it is straightforward to analyse the impact of damping on the approximation quality of EF, SF and iEF. For a target task, the indicator y w.E.t. damping À curve is computed at the start, mid-way and end of the training. Graph for an example task is shown in
Fig. 3 (graphs for other tasks provided in Appendix H.5.2). Two observations can be made:
I) A well-chosen damping factor significantly improves the approximation quality of EF and SF,
which aligns well with observations in prior work approximate NGD optimisers [27] 33 34),
However, the optimal damping factor changes greatly for different tasks and training stages, which makes the damping schedule for SF EF based optimisers necessary yet hard-to-design in practice. 2) Across all tasks and training stages, iEF robustly achieves great approxin inprroimmatinn quality with a near-zero damping factor. More importantly, its approximation quality is consistently better than EF method, and is comparable to the optmally-damppd SF method (which is much more expensive, particularly when the cost of damping tuning considered). Overall, iEF can be considered a cheaper, higher-quality and more robust alternative to both the EF and SF approximation methods.
Epoch 1%
Epoch 50%
Epoch 100%
EF
SF
10'
100
Figure 3: Approximation quality (relative to SGD) of EF, SF and iEF methods w.r.f. damping factor A at different training stages of task CoLA+T5+LORA, z-axes show the value of the damping factor, y-axes depict the relative approximation quality improvement of the target update method w.r.t. SGD (the lower the better). Each data point is averaged across 100 evaluations, and the error-bars represent the standard deviation (I-sigma). The first plot is for checkpoint saved at the end of the first training epoch, the second plot for the mid-way epoch and the third plot for the final epoch. It can be observed that iEF achieves the best approximation quality robustly for any near-zero A. In contrast, À has non-linear impact on both SF and EF, When optimally tuned, an EF update can achieve better approximation quality than SGD, and an SF update can achieve comparable quality to iEF. However, the optimal damping factor for EF and SF changes greatly with training stages (and tasks).

---

Conclusions and Future Work
This paper presents the iEF method, which addresses the inversely-scaled projection issue of the EF approximation for NGD, meanwhile maintaining the implementational convenience. A novel empirical evaluation framework for the quality of general approximate NGD update also proposed which enables quantified comparison of approximate NGD methods in large deep learning setups" Based on the experiments with practical PEFT pre-trained models for NLP and CV classification tasks, the exact iEF optimiser shows superior convergence and generalisation for majority of the tasks, supporting the applicability of iEF directly as an optimiser. Further evaluation on approximation quality concludes that iEF achieves consistently better approximation quality than both EF and SF. The iEF method also demonstrates the superior property being robust to the choice of damping factor across different tasks and training stages.
As is discussed in Sec. 5.4 the iEF method can be viewed not only as an improved approximate NGD optimiser, but also as an improved approximation method for the exact Fisher matrix in general. This opens up many opportunities of future work to improve a wide range of Fisher-based methods (not limited to optimisation methods). Some example applications include improving the empirical K-FAC optimiser (37, 33) (which has shown promising results in preliminary experiments) and improving the WoodFisher algorithm for model compression 46
Acknowledgements
Xiaodong Wu in part funded by the Cambridge Trust, a donation from Meta Systems and Christ's College, Cambridge. This work has in part been performed using resources provided by the Cambridge Tier-2 system operated by the University Cambridge Research Computing Service (www.hpc.cam.ag funded by EPSRC Tier 2 capital grant 1P/T0221.9/11
'Codebase will be publicly released.
10

---

References
[1] Shun-ichi Amari. "Natural Gradient Works Efficiintly in Learning". In: Neural Computation 10.2 (Feb. 1998), pp. 251-276. URL: https://doi org. 10. 0016////8897666630077777799
[2] Andersen Ang. Convergence of gradient flow. Dec. 2022. URL: hnttp:://anga. science/ doc/CVX/Gradient
pdf
[3] Achraf Bahamou, Donald Goldfarb, and Yi Ren. "A Mini-Block Fisher Method for Deep Neural Networks", In: International Conference on Artificial Intelligence and Statistics. 2022.
URL: httpss//api..
prrg/Copuus..o ID: 253158046)
[4] Frederik Benzing. "Gradient Descent on Neurons and its Link to Approximate Second-order Optimization". In: Proceedings of the 39th International Conference on Machine Learning. Ed. by Kamalika Chaudhuri et al. Vol. 162. Proceedings of Machine Learning Research. PMLR, July 2022, pp. 1817-1853. html
URL: https::/ppoceeeiinnn
mlr. pptsss/v662/beezingg222
[5] Ulf Brefeld al., eds. Machine Learning and Knowledge Discovery in Databases European Conference, ECML PKDD 2019, Würzzurg, Germany, September 16-20, 2019, Proceedings, Part III. Vol. 11908. Lecture Notes in Computer Science. Springer, 2020. URL: http://bblp
ami-trier www.eedddddbb/eeeeeeeeeeeeeeeeee htt/////oofff/t/ pppkd//pkdd20199 3.html
[6] Tom B Brown et al. "Language models are few-shot learners". In: arXiv preprint arXiv:2005. 14165 (2020).
[7] Ning Ding et al. "Parameter-efficiem fine-tuning of large-scale pre-trained language models". In: Nature Machine Intelligence 5 (Mar. 2023), pp. 1-16.
[8] Alexey Dosovitskiy et al. "An Image Worth 16x16 Words: Transformers for Image Recogni- tion at Scale". In: International Conference on Learning Representations. 2021. URL: https //ppenreview.
[9] John Duchi, Elad Hazan, and Yoram Singer. "Adaptive Subgradient Methods for Online Learning and Stochastic Optimization". In: Journal of Machine Learning Research 12.61 (2011), pp. 2121-2159. URL: http:: // //jrr .ww. wtg.papers/v122 http:///cchhhllaaa html
[10] Kaixin Gao et al. Siseenallue-Coreccte Natural Gradient Based on New Approximation".
In: Asia-Pacific Journal of Operational Research (APJOR) 40.01 (Feb. 2023), pp. 1-18. URL:
:stps://idees repec org/ a wsi /aapappooorr//// / html
[11] Thomas George et al. "Fast Approximate Natural Gradient Descent in Kronecker-factoree Eigenbasis". In: Neural Information Processing Systems. 2018. URL: https / api
Bemanticscholar org/ hhg/CorppusID. :7018147
[12] Donald Goldfarb, Yi Ren, and Achraf Bahamou. "Practical Quasi-Newton Methods for Train- ing Deep Neural Networks". In: Proceedings of the 34th International Conference on Neural Information Processing Systems. NIPS'20, Vancouver, BC, Canada: Curran Associates Inc., 2020.
[13] Vineet Gupta, Tomer Koren, and Yoram Singer. "Shampoo: Preconditioned Stochastic Tensor Optimization". In: 2018. URL: http / proceedings mlr press / v80 gupta18a/
gupta18a. pdf
[14] Kaiming He et al. "Deep residual learning for image recognition". In: Proceedings of the IEEE conference on computer vision and pattern recognition. 2016, pp. 770-778.
[15] Xuehai He et "Parameter-efficient model adaptation for vision transformers". In: Pro- ceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence and Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence and Thirteenth Symposium on Educational Advances in Artificial Intelligence. AAAT23)AAAF23/AANN
AAAI Press,
2023, URL: httph::t///t :tstps://dor //doi. orgo 10. 1609/ 16099/aai. wtw.aa......aa... vv7i1. 25160
[16] Edward Hu et al. "LoRA: 1 Low-Rank Adaptation of Large I Language Models". In: Interna- tional Conference on Learning Representations. 2022. URT.: httph::t//// //opnrevieerrr..e..e net/
f forum forum?ide Nimmmid=nZeeeeeeee
[17] Diederik P. Kingma and Jimmy Ba. "Adam: A Method for Stochastic Optimization". In: 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA. May 7-9, 2015, Conference Track Proceedings. Ed. by Yoshua Bengio and Yann LeCun. 2015. URL: http://arxiie org/ wttggabs//412..o 6980

---

[18] Andrew V. Knyazev. "Toward the Optimal Preconditioned Eigensolver: Locally Optimal Block Preconditioned Conjugate Gradient Method". In: SIAM Journal on Scientific Computing 23.2
(2001), pp. 517-541. URI.: https: //doi: org/10 10..0000000 1137
[19] A. Krizhevsky and G. Hinton. "Learning multiple layers of features from tiny images". In: Master's 's thesis, Department of Computer Science University of Toronto (2009).
[20] Frederik Kunstner, Lukas Balles, and Philipp Hennig. "Limitations of the Empirical Fisher Approximation for Natural Gradient Descent". In: Proceedings of the 33rd International Con- ference on Neural Information Processing Systems. Red Hook, NY, USA: Curran Associates Inc., 2019.
[21] Yann LeCun and Corinna Cortes, "MNIST handwritten digit database". In: (2010). URL:
http: /ttp://yann lecun. cww hxdbb mexdb/mmisst mnist//
[22] Brian Lester, Rami Al-Rfou, and Noah Constant. "The Power of Scale for Parameter-Efficiee Prompt Tuning". In: Proceedings of the 202/ Conference on Empirical Methods in Natural Language Processing. Online and Punta Cana, Dominican Republic: Association for Compu- tational Linguistics, Nov. 2021, pp. 3045-3059. URL: https::/aclaathhooooggg. orgg/02)
emnlp-mante 243)
[23] Brian Lester, Rami Al-Rfou, and Noah Constant. "The Power Scale for Crrameter-Efficiee Prompt Tuning". In: Proceedings of the 2021 Conference Empirical Methods in Natural Language Processing. Online and Punta Cana, Dominican Republic: Association for Compu- tational Linguistics, Nov. 2021, pp. 3045-3044000 3059. URL:
orggorg///0 2021
emnlp 1alppmmmin.... 243
[24] Ilya Loshchilov and Frank Hutter. "Decoupled Weight Decay Regularization", In: 7th Interna- tional Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019. URL: htttp::// http://pppemeeeeeeeeeee.eorromm nwt/terumm BiddmiiddiBigggppp
[25] James Martens. "Deep learning via Hessian-free optimization." In: ICMI.. Ed. by Johannes Fürnkranz and Thorsten Joachims. Omnipress, 2010, pp. 735-742. URL: http:/ttpp//ppppppp uni- trier. trier.de/due dtde/d//cott/ htmmmmmmmmmmmmmmmmmmmmmmmmmmmm html #ttml#Mattenn0
[26] James Martens. "New Insights and Perspectives on the Natural Gradient Method", In: Journal of Machine Learning Research 21. 146 (2020), pp. 1-76. URL: http::tpp:mmmm org/ http://pmlrrrrrpppprsss////
v21/17-678. htm html
[27] James Martens and Roger Grosse. "Optimizing Neural Networks with Kronecker- Factorrd Approximate Curvature". In: Proceedings of the 32nd International Conference on Interna- tional Conference on Machine Learning Volume 37. ICML' 15. Lille, France: JMLR.org, 2015, pp. 2408-2417.
(28) Mahesh Chandra Mukkamala and Matthias Hein. "Variants of RMSProp and Adagrad with Logarithmic Regret Bounds". In: Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, Ed. by Doina Precup and Yee Whye Teh. Vol. 70. Proceedings of Machine Learning Research. PMLR, 2017, pp. 2545- htm]
2553. URL: http::/proccediing/ mml.. preas//70/mukkamaa
[29] Behnam Neyshabur et "The role of over-parametriization in generalization of neural net- works". In: 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019. URL: https : / /peprevierrevvrre net/forum?idd-yygfea
[30] Levon Nurbekyan, Wanzhou Lei, and Yunan Yang. "Efficient Natural Gradient Descent Meth- ods for Large-Scale PDE--Based Optimization Problems". In: SIAM Journal on Scientific Computing 45.4 (2023), A1621-A1655. URL: U bhttps:/p/oott org/ 10. 1 22M1477805
[31] Kazuki Osawa et al. "Large-Scar Scale Distributed Second-Orden Optimization Using Kronecker- Factored Approximate Curvature for Deep Convolutional Neural Networks" In: 2019 IEEE//CV Conference on Computer Vision and Pattern Recognition (CVPR) (2018), pp. 12351-12359. URL: httt:::tts::/papp httttp:://ap..semmnticchhooooo semanticscholarr org/ Ctsp/Crrpuss.D... :TD.6667886111
[32] Adam Paszke et al. "PyTorch: An Imperative Style, High-PPeformance Deep Learning Library". In: Advances in Neural Information Processing Systems 32. Curran Associates, Inc., 2019,
pp. 8024-8033 8035.
[33] J. Gregory Pauloski et al. "Convolutional neural network training with distributed K-FAC", In: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis. SC '20. Atlanta, Georgia: IEEE Press, 2020.
12

---

[34] J. Gregory Pauloski et al. "Deep Neural Network Training With Distributed K-FAC". In: IEEE Transactions on Parallel and Distributed Systems 33.12 (2022), pp. 3616-3627.
[35] Felix Petersen et al. "ISAAC Newton: Input-based Approximate Curvature for Newton's Method". In: The Eleventh International Conference on Learning Representations. 2023. URL:
net wtw/teeuunnniiiie wtt.//oommmddpppp (owpum/ddd-paccssrT]
[36] K. B. Petersen and M. S. Pedersen, The Matrix Cookbook. Version 20081110. Oct. 2008. URL:
http://www2: imm. dtu dk/ wwwpppppppppp.o.p php73274
[37] Daniel Povey, Xiaohui Zhang, and Sanjeev Khudanpur. "Parallel training of DNNs with Natural Gradient and Parameter Averaging". In: (Oct. 2014).
[38] Alec Radford al. "Robust Speech Recognition via Large-Scale Weak Supervision". In: Proceedings of the 40th International Conference on Machine Learning. Ed. by Andreas Krause al. Vol. 202. Proceedings of Machine Learning Research. PMLR, July 2023, pp. 28492- 28518. URL: httph:ttp//// ttttps://proceedin:
mlr wtt.s/m...rress/2222222 ctress/2202/raffrddo/
html
[39] Colin Raffel et al. "Exploring the Limits of Transfer Learning with Unified Text-to-Tex. Text Transformer". In: Journal of Machine Learning Research 21.140 (2020), pp. 1-67. URL.:
http://jmlr... .ww.oorggpaaa.. pwwp/sppprss///ppp 201222220002222 html
[40] Yi Ren and Donald Goldfarb. "Efficient Subsampled Methods for Training Neural Networks". In: CoRR abs/1 1966.02333 (2019). URL.: http
and Natural Gradient
// 7/axxiv.org algg/666/990....... 02353
[41]
Yi Ren and Donald Goldfarb. "Tensor Normal Training for Deep Learning Models". In: Advances in Neural Information Processing Systems. Ed. by M. Ranzato et al. Vol. 34. Curran Associates, Inc., 2021, pp. 26052. URL: https : p/wcce/dingg.......peeee.p neurips cc paper_files.
pdf [42] Herbert Robbins and Sutton Monro. "A Stochastic Approximation Method". In: The Annals of Mathematical Statistics 22.3 (1951), pp. 400-407. URL: https: org 10. 1214/
aoms foms/1177729586
[43] Nicolas Roux, Pierre-antoine Manzagol, and Yoshua Bengio. "Trgiio..TTore "Topmoumoute Online Natural Gradient Algorithm". In: Advances in Neural Information Processing Systems. Ed. by J. Platt al. Vol. 20. Curran Associates, Inc., 2007. URL: paper_ files- wwtpss/pppp///eeeeee / 2007 http:/iie//99// 2tw.:44440080aaaa3eeeeeeeeeeeee 1ttp://000000100220066666666666-
wnw.eeedddnnnne.euipiepeeee wwwrips....... cc/
pdf [44] John Schulman al. "Trust Region Policy Optimization", In: Proceedings of the 32nd In- ternational Conference on Machine Learning. Ed. by Francis Bach and David Blei. Vol. 37. Proceedings of Machine Learning Research. Lille, France: PMLR, July 2015, pp. 1889-1897. pressppree//vv/// htt.//ccccaama....cmmm. html
URL.: htt.:tttts:/pproceddinge
[45]
Jonathan Richard Shewchuk. "An Introduction to the Conjugate Gradient Method Without the Agonizing Pain". In: (Aug. 1994). URL: http::/tt::tt //wp///wwww////////// cs. cmu, edu/ quaaee-paerse
painless-con cosess-ooonngatttt www.eeerrradieen..g..m pdf
[46] Sidak Pal Singh and Dan Alistarh. "WoodFisher: Efficient Second-Order Approximation for Neural Network Compression". In: Advances in Neural Information Processing Sys- tems. Ed. by H. Larochelle et al. Vol. 33. Curran Associates, Inc., 2020, pp. 18098-18109 URL: https: : / proceedings neurips cc /paerr files / /pappr/ppppp/ap / 2020 / file/ / pdf
[47] Valentin Thomas et al. "On the interplay between noise and curvature and its effect on optimization and generalization". In: International Conference on Artificial Intelligence and Statistics. 2019.
[48] Hugo Touvron et al. I.MMMA Open and Efficient Foundation Language Models. 2023.
[49] Yuichiro Ueno et al. "Rich Information is Affordable: A Systematic Performance Analysis of Second-order Optimization Using K-FAC". In: Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. KDD '20. Virtual Event, CA, USA: Association for Computing Machinery, 2020, pp. 2145-2153. URL: httpss///osi
111100.111/339444 3403265
[50] Alex Wang et al. "GLUE: A Multi-Task Benchmark and Analysis Platform for Natural Language Understanding". In: Proceedings of the 2018 EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP. Brussels, Belgium: Association for
Computational Linguisties, Nov. 2018 pp. 353-355, URL: https://aaclatthooggy.. org/
W18-5446
13

---

[51] Minghan Yang et al. "An Efficient Fisher Matrix Approximation Method for Large-Scale Neural Network Optimization", In: IEEE Transactions on Pattern Analysis and Machine Intelligence 45.5 (2023), pp. 5391-5403.
[52] Minghan Yang et al. "Sketch-Baae -asedd Empirical Natural Gradient Methods for Deep Learning" In: J. Sci. Comput. 92.3 (Sept. 2022). URL: /stpp://doo.orr/111 1000 022
01911-x
[53]
Guodong Zhang, James Martens, and Roger Grosse. "Fast Convergence of Natural Gra- dient Descent for aver-Paramtterized Neural Networks". In: Advances in Neural Informa- Processing Systems. Ed. by H. Wallach al. Vol. 32. Curran Associates, Inc., 2019. URL: https : / proceedings neurips cc / paper files / paper 2019 file/ / Icaf/f/522201e711fffffffTfCC.C. Paper, Paapr.ppd... pdf
[54] Lin Zhang, Shaohuai Shi, and Bo Li. "Eva: Practical Sccond-order Optimization with Kronecker-vecctrrized Approximation" In: The Eleventh International Conference Learning Representations. 2023. URL: htt:::ttp:::. http///peeeeiiieeeeeeeeee www./eetfoornn _ Mi
[55] Yingqiu Zhu et al. "Automatic, dynamic, and nearly optimal learning rate specification via local quadratic approximation" In: Neural Nenworks 141 (2021), pp. 11-29. URL: https
//www.sciinneeeet www.ssciencedirect. http:/dddreetttccccccicccceeeeee http://cc.....c..co.oo/ooooo///t
14

---

A Relation between iEF, GN and NGD in Different Machine Learning Setups
The connection between iEF, GN and NGD methods is discussed for different common machine- learning scenarios. It is explained that for scalar output (regression) model, the iEF method and the GN algorithm is equivalent. Furthermore, for a least-squares problem, the iEF, GN and NGD methods are all equivalent.
A.1 Regression Model Problem
In this section, a supervised learning problem for a target model with only a scalar output (i.e. regression model) is discussed. The definition of the setup is follows.
Consider a target regression model fo(-) R + R. where E IR. the trainable parameters of size P. Given N ii.d. training samples (In,, ( Bn) (where æn is the input feature vector and Yn E R is the scalar label), the output of the model for the n-th sample is 2n [o where on E IR is a scalar. For the n-th sample, the per-sample loss L, is defined as
Joh (Zn, Un),
(17)
where F.b)( E R is the per-sample objective function, and the accumulated loss Σ In is to be minimised. Some examples of this problem setup include least-squares regression problems where mean-square error used the loss function, and binary classification problems where the Sigmoid-activation plus binary cross-entropy is used as the loss function.
Recall the definition of the iEF matrix in Eqn. 14 In this problem setup, the iEF matrix can be computed as follows
dln 112 F' E,
dln
dl, de
Vozn) Voza) = Σ, Voen Vo2, G dz,
(18)
dzn
which takes the same form as the GN matrix. Therefore, the iEF and GN methods are equivalent to supervised learning problems of regression models.
A.2 Least-Squares Problem
The least-squares problem is representative example supervised learning problems of regression models, which includes the toy example shown in Fig. [ The definition of this type of problem follows most of the definitions in Appendix [A.]] apart from the per-sample objective function, which is elaborated as follows. For the least-squares problem, the objective function is defined as follows
1 2 2(2n -yn)²
Foob (Zns Un) =
(19)
The Fisher matrix for the least-squares problem defined as follows 47
F
Σ 12 Voz V
G
(20)
which coincides with the iEF and GN matrix in this problem setup. Consequently, the iEF, GN and NGD methods are equivalent for eqast-squares problems. This is verified the second plot of Fig. where NGD and iEF share the same update vector field.
B Visualisation for Linear Least-Squares Problem with Two Training Samples
Setup Description In this section, the Fig. Treferenced in Sec. 4.2 is explained in detail. The vector field graph is based simple linear least-squares regression problem, with 2 training samples and 2 trainable parameters.
The linear least-squares problem is chosen for visualisation because it is not only highly representa- tive machine learning setup 47 20), but also there has been precedent of using this problem to
visualise the distortion in EF (see Figure 1 in (20). The trainable parameter size of P = 2 is chosen
15

---

to facilitate the 2D visualisation, and the training sample size of N 2 (i.e. N & P) is chosen to better match the practical deep learning scenarios where the model is over-parameterrsee..
The target linear model is formulated as fo( = A Fas 1] = 0o + 01 with In E and 0 TR? The two training samples (Ins Un ) {(0,0) ()) (with N 2) and the target loss be minimised is ( -==1 Elyn (z,)) It is obvious that the optimal parameter (at global minimum) is 0 [0, 0j
2
The update vector fields are generated using the following definition:
AOSGD
Ve((O)
AONGD
(F + )NGDD) -oonD))-Veo(()
(21)
AOEF (F + >EEI) VV)
AQEF
(F"' +
The EF matrix F follows the definition in Eqn. The iEF matrix F* and Fisher matrix F shares
the same definition as shown in Eqn. (20) (see Appendix (.2)). For this toy problem, the damping factors λuE and ANGD set to zero. The damping factor AEr is set to zero everywhere, apart from when one of the per-sample gradient gives norm of O, a damping factor of 1 10 max (diag (F)) is used to facilitate inversion. Finally, in the third plot of Fig. | the EF update vectors are normalised for better visualisation, because EF updates have hugely different scales across the contour plots. In the zoomed view next to the third plot, the EF update vectors are not normalised, which should give a better demonstration of the inverse scaling issue of EF updates.
The same set initial parameters (shown as black solid octagons) are used to generate training trajectories (coloured curves) on each plot in Fig. [ Each follows the corresponding update vector fields (each step follows the direction of the update vector field, and is normalised to 10-2). To demonstrate how each sample affects the EF updates, the optimal parameter set for each training sample (i.e. when [y/- fo(x))) 0) is added on all plots in Fig. as dashed lines. For training sample I: (0, 0), the optimal parameter set is 0, O, which is shown as horizontal dashed lines. For training sample 2: (1, 0), the optimal parameter set 9g + 01 0, which is shown as diagonal dashed lines.
Observations By observing the behaviour of the vector fields for different updates on the loss landscape, along with the 5 sampled trajectories in Fig. it can be seen that all methods successfully reached the global minimum, with the NGD/jEF updates having the most efficient training trajectory. However, the EF method has highly distorted update vector field and training trajectories due to the inversely-seabee projection issue discussed Sec. 4.1 The following conclusions can be drawn for EF updates:
Directional bias towards converged samples: The EF update vector field is easily "attracted" to the dashed lines because the EF update is strongly affected by the better- converged sample (due to inverse scaling). This leads to a distorted update vector field and ineffective training trajectories. In particular, when per-sample gradients have highly imbalanced norm near the dashed lines, the EF update vector field becomes almost parallel to the loss contour. This causes them to deviate significantly from both the gradient descent direction and the optimal direction (NG update direction), and oscillations can be observed along the dashed line in the zoomed view.
2. Inversely-scaled update norm: samples is nearly converged (see the zoomed plot). fact, the EF training trajectories managed to converge because we normalised every update to small norm of x 10-2, which is not needed for SGD, NGD and iEF methods. Consequently, it is likely that a sophisticated learning rate scheduler is necessary when training with the EF method in practical deep learning setups (as is mentioned in (20).
EF updates have larger norms when either of the training
Motivation As is stated in Sec. 3, the paper mainly focuses on classification setups, but visual- isation of regression setup in Fig. is used in the main paper for the following reasons: 1) The least-squares regression problem is commonly used when analysing NGD and EF in the literature 22 47]. Particularly, our visualisation follows a similar setup to [20), which an important related work regarding the limitations of EF, Overall, the toy regression example allows for consistency with
16

---

the literature. 2) The 2-datum least-squares regression problem have several nice properties. There exists unique global minimum; the NG update can find the global minimum in one step, and the advantage over all other updates is self-evident; the iEF update and NG update has the same form; the distortion of the EF update extreme. All of these properties make the visualisation in Fig. much more straightforward to understand than a visualisation for classification setup.
Additional Visualisation for Logistic Regression Problem Given that the paper focuses on classification setups, it is important to also include visualisation for a toy classification setup. Consequently, an additional visualisation, in a similar fashion, that compares Fisher, iEF and EF as pre-conditioners in toy classification setup is provided in Fig- 4 This figure considers 2- datum logistic regression setup and more detailed description provided in the caption. This new visualisation demonstrates consistent results to that of Fig. Particularly, it can be observed that EF updates deviate from the optimal decision boundary because it is biased toward further optimising the better classified datum (i.e. the datum with lower CE loss). Also, EF updates become larger when either of the datum achieves a small loss. Meanwhile, SGD, NGD and iEF update approaches the optimal decision boundary consistently, and arguably NGD and iEF reach the optimal decision boundary more effectively than SGD.
SGD
NGD
IFF
EF
Figure 4: A visual comparison of Fisher, iEF and EF as pre-conditioners for logistic regression problem (classifying two ID datum Zo = 0, x1 = into two classes). The target model is pe(xn) = (00 + 014x), where (-)) (-) is the Sigmoid function and CE loss is used, which follows the problem setup description Sec. This figure is different from Fig. ii aspects: 1) iEF and NG updates no longer identical, and presented in separate plots; 2) There is no global minima, but the model achieves lower loss when moving further down the bottom-right corner, 3) The dashed line now represents the optimal parameter set for decision boundary of 1. The training trajectory of EF is still ill-behaved, meanwhile both NG and iEF updates move towards the optimal decision boundary smoothly.
C Convergence Analysis
The proofs for Theorem. 5.3 and Theorem, 5.3 are provided this section. The proofs follow and extend the continuous-tine analysis framework in [53 and (2)
Justification of Full-rank Gram Matrix Assumption Recall Assumption 5.2 which assumes Vec to be full-rank throughout the training process. This is equivalent to assuming ((t) NxP always have full row rank. This is considered mild assumption for practical deep learning because:
1. It is generally true that for each individual per-sample gradient Veco (1), the norm of the gradient will be zero if and only if V to) (t) 0 (i.e. at the minimum of that sample). Therefore, it is unlikely that there exists zero norm per-sample gradients in (o during training.
2. The target model is usually highly parameeteteri with P > N and the model is highly complex. is general unlikely that Vo(o,((t) is rank-deficient, as long as there are no duplicate training samples.
Ideal Per-sample Loss Change for IEF Lemma can be derived
Given Assumption 5.1 and Assumption 5.2 the following
17

---

Lemma C.1. Suppose Assumption 5.2 holds. Vn fl....,N? NN, the loss reduction induced on the n-th training sample by the iEF update follows
dl (t) - 2V,
(22)
dt
Proof of Lemma.
C.I
di(t)
be computed as follows
dt
dl(l)
d0(()
(() dt
Ve(i) (())) (V (Nonn sur(!) -8pr(() (1).
V
dt
(23)
Therefore, dl.,()
.n (t))
Global Sub-linear Convergence for Softmax CE Objective Function The proof for Theo- rem 5.3 is provided here. In this analysis, the supervised learning setup with softmax + CE objective function considered (as described in Sec. 3) This is a setup commonly used in practical deep learning, making this convergence analysis practically relevant.
As stated in Sec. 3 the target model is assumed to softmax activation function. For the n-th sample at time step i, 2n (t) = Se(e) (a:n), where z,, (1) E RC is the output logits. The output probability for class can be computed from the logits using the softmax activation: (c))())(t))= =
[ors (Zn (t))le where (-) RRC - I is the softmax activation function.
The per-sample loss in this setup therefore defined as
(t) == - log[p,, (yn, )tt) == log p.. (t) = log Jos (zn (t))
(24)
yn.
where (2.)] represents the output probability for the target class yn- It can be seen that the lowest loss for sample n tends to O, which is achieved when (t) - 1.
The gradient of (t) w.r.. Zn (1) can be computed as
(P,(e)))))) # yn. Pt)
V (o.00))4o00)
(25)
yn.
The norm of the gradient satisfies the following inequality
= (e) (t) 2 [1 - (t)
(26)
Combining Lemma.
C.I
with the definition in Equ. (24). the following equation can be obtained
dl, (t) d log (t)
dp.
- VV (
(27)
dt
dt
(r,(1) (1) de
Combining Eqn. 26 27
the following inequality can be obtained
1
(t.(t) dt.
(28)
PA(1I[1 Pn (1)]2
Integrating on both sides gives
pt((t - Co 2 t. 1 1- (t(()
(t) + log
(29)
where Co = I-p log (0) can be further relaxed to
known that x > log x for x. > 0, therefore the inequality
I-p (0)
(t)
+ 1 - pn((t)
> t + Co.
(30)
1- (x)
which is equivalent to
> > C +
(31)
1 (t)
Now consider large s.t. t Co + 1 > 0, bound can be provided for (t) as follows
2
(t)
(32)
Co +1
This shows that iEF guarantees global sub-lineal convergence for target probability Pn - for every
training sample. It equivalently implies that iEF guarantees sub-linear convergence to the global minimum of the accumulated cross-entropy loss (achieved when Yn = (1....N] N). P. 1), given the per-sample objective function is the softmax + cross-entropy combination.
18

---

C.1 Global Linear Convergence for Strongly Convex Objective Functions
The proof for Theorem 5.4 is provided here. Unlike for Theorem 5.3 where the model is assumed to
use softmax + tross-entropy loss function, this theorem is applicable to group of common loss functions: m-strongly convex objective functions.
The details of the setup used here mostly follow that in Sec. 3 The differences are described as follows. Given N i.i.d. training samples (æ:; ) (where d. is the input feature vector and Yr is label of arbitrary form), the output of the model for the n-th sample is 2n. fe(xn) where Zn _º is general model output vector (no longer logits vector). m-strongly convex objective loss function (-) (.) is used to compute the per-sample loss for the n-th sample l, E R as follows
L = Fab En. yn) = (zn),
(33)
where the label y, is omitted for simplicity, Finally, the following accumulated loss be minimised
[()) 1,00,,, la-
(34)
In addition to Assumption 5.1 and 5.2 an additional assumption is made for the objective loss function follows
Assumption C.2. For the n-th sample, the objective loss function Fas (zn) is assumed to be m- strongly convex on the model output space 2n. which then satisfies the following inequality (5]
Fats(z)) Fods S
2m V
(35)
where Faty(z,) is the global minimum of the loss for the n-th sample. For simplicity, the notation 1 used in place (2 The inequality is therefore rewritten as follows
1 2m
I
1
V 1.13
(36)
Assumption. C.2 is quoted from
(2). which covers a wide range of loss functions including mean- square-error. Note that under this assumption, both per-sample losses and accumulated loss can still have an arbitrarily non-convex landscape on the parameter space.
Based on Lemma C.I when training with iEF updates, for the n-th sample, the loss change is
dl (t)
-IV.... (1))
(37)
dt
Using the Polyak-Lojasiewiin inequality in Assumption. the following inequality can be obtained
dlnn (1) (1)
d( (1) (7,) < -2mm
-2m(La (7)) (L,(t) (7)
(38)
dt
dt
Integrating on both sides gives the following
(t) 1" Se 2mL (L, - -,,),
(39)
which shows that iEF pre-conditioned gradient flow linearly converges to the global minimum for every sample. This then implies that iEF has global linear convergence guarantee for accumulated loss (()).
D Discussion on Practical Applications of IEF
D.I Stochastic IEF/EF Optimiser
As is mentioned in Sec. 5.4 the stochastic version of the exact iEF method can be directly used as an optimiser. is described Algorithm I this section, the implementation of this exact iEF optimiser is discussed, along with its computation and memory complexity. Note that the stochastic exact EF optimiser can constructed in a similar form Algorithm The following discussions should also apply to the exact EF optimiser.
19

---

Algorithm Stochastic Optimisation with Exact IEF
Require: All N training samples, initial model parameters ((0)
for t 0 to T - 1 do
Sample
Mt))) with size M
Perform forward pass on batch ((t) to obtain the per-sample loss vector [(t)
Perform back-pre propagation obtain Jacobian Voce)((t) and logits gradient norm vector (
Compute iEF update (t) = Vow (V)
+ XI) (t) Eqn.
Update model O( + 1) = (()) - 7)0FF((!)
end for
Algorithm Stochastic Optimisation with Exact EF
Require: All N training samples, initial model parameters ((0)
fort= 0 to T - 1 do
MMt)) with size M Sample Mini-batee
Perform forward pass on batch M(t) to obtain the par-sample loss vector ((t)
Perform back propagaopnt to obtain Jacobian (t)
Compute EF update (t) (t) T (Vor)((t)Voon) + +AI =1I--11: Eqn. 5
Update model O( + 1) (() ()0rr(())
end for
Implementation Details There are two main aspects of the implementation of this optimiser that are non-trivial. These are discussed respectively as follows:
1. Jacobian matrix Vol:
The computation of Vel is effectively collecting the per-sample gradients for batch during the back-propagation process. In Pytorch (32), the per-sample gradients are readily computed during back-propagation, but are usually accumulated along the batch dimension to compute the total gradient, and are not available for collection directly. Therefore, additional backward hooks need be attached trainable modules to store these per- sample gradients during the back propagation process. This is a standard procedure used most approximate NGD optimisers [27] 4 43). Our implementation is partially based on this K-FAC implementation, Note that this additional procedure of computing per- sample gradients is negligible w.r.f. forward and backward of large pre-trained models in PEFT setups, making iEF/EF have comparable speed as standard Adam W/Adafactor/SGGD optimisers.
2. Logits gradient norm vector Sier:
During back- propagation in Pytorch [32]. the gradient of logits Vz,, In is already computed, but is not stored because logits vector xn, is not leaf-node. This be easily changed by calling the "'.retain grad(") method on the logits vector. Although this operation is non-standard to common approximate NGD optimisers, it adds negligible cost standard brok-propagatton (in general deep learning setup, not limited to PEFT) and its effect on speed can be ignored.
Time and Memory Complexity Given a batch size of M, and trainable parameters of size P. assume the per-sample gradients have already been computed through backpropagation, the time complexity of computing each update is O(M² + M)2), and the memory complexity is O(M² + .M. Due model over- aeer-paramtterisatioon we have P > M. Then, the time complexity becomes 2(M2P) P) and memory complexity becomes OMMP). In practical deep learning frameworks such as Pytorch (32). the limiting factor for the applicability of such an exact EF-like method is the memory complexity O(MP). which is essentially the storage of the M per-sample gradients involved in the computation of exact iEF updates.
therefore only possible to apply exact EF- like methods to models with small trainable parameter sizes (either full tuning of small models or parameter-efficient fine-tuning of large models) or small batch size M. This the reason why exact EF is never directly used to optimise modern deep learning models, and additional approximation is or SVD-based pruning (43)). Nevertheless, given the rise of large parameter-efficient fine-tuning has gained traction
always necessary (e.g. K-FAC 27
pre-trained models [8
6
39
38
[5 16 7 and
20

---

direct application of exact iEF may still be beneficial (as the trainable parameter size is usually < 1% of the pre-trained model size).
D.2 Improving Existing Fisher-based Methods with IEF
is mentioned in Appendix [.1 that exact iEF as an optimiser is limited by its memory complexity. Given the descent training performance of exact iEF optimiser, it would be interesting to observe the performance of iEF on more general setups. As is mentioned in Sec. 4] it can achieved by incorporating iEF into existing EF-based optimisers such as empirical K-FAC (27]. In this section,
an improvement to the EF-based K-FAC optimiser with iEF is proposed, which can act as a starting point for future work in improving other approximate empirical NGD methods.
D.2.1 Expression of IEF Matrix
The iEF matrix can be computed according to Eqn. F Vel" diag( ( This can be derived from Eqn. (8) using the identity (UV + Al) derivation, we denote
- U(VU X1) For simplicity of Vol and assume J is a square matrix and is full-rank. Also, we denote = diag( (iEF) and assume the diagonal matrix to be full-rank. Therefore, the proposed iEF matrix can be expressed F S JJ The following derivation can be made
(F*)- (Vol 1) (J'S~"J)----
( -
(40)
= - = J
1
This shows that the update pre-conditioned by F* indeed is the same as the iEF update described in Eqn. (8)
The expression for the iEF matrix in Eqn. 14 can be alternatively rewritten as follows
F
Vol diag(srr)- Vol
(IV La l ' =v,
(41)
which differs from the EF matrix Eqn. 3 in that each per-sample gradient re-scaled with | s, ln 11 Such simple scaling is easy implement in most approximate empirical NGD optimis- ers.
D.2.2 Improving Empirical K-FAC with IEF
The empirical K-FAC 37 is widely used version 33
34
49
31 of the original K-FAC method
27 Its formulation can be described as follows.
Assume there are n samples in the target batch. For one fully connected layer in a target model, the weight matrix is denoted by matrix W E R= the (batched) input is denoted by a E R and the (batched) output is denoted by row vector e E Ro*k They satisfy e == aW. The gradient Vel E Ba is denoted by g- The block-diagonal portion of the EF matrix corresponding this layer (denoted as F Fw) can be estimated using K-FAC approximation
follows (2
Fw Eigg X
a)] (aTa))
(a
E[g g] & BB(a a).
(42)
This is based on the gradient expression for weight matrix W: Vwl = g a. By rescaling this gradient with vector SIEF, the expression for Fw becomes:
Fw Efgg diag(8ur) g] X E[a T a].
(43)
where the SIFF vector is easy to compute in Pytorch (32 with negligible extra cost (as shown in Appendix D.I. and such diagonal rescaling is straightforward to implement. In conclusion, the idea of iEF can be easily integrated into existing approximate empirical NGD optimisers, and is interesting to observe the improvements due such integration.
Preliminary evaluation of the approximation quality to the exact NG update of the block-diagonal version of the iEF method is conducted using the evaluation framework proposed in Sec. (following
the style of experiment (E1)). The approximation quality to exact NG updates (relative to SGD updates) are reported for iEF, KFAC (block-diagonal version of SF method [12 ). eKFAC (block-
diagonal version of HF method (37)) and ieKFAC (block-diagonal version of iEF method), for different training stages of selected tasks in Fig. damping.
All updates are generated using a near-zero
21

---

Vise/Ysco
Yint
Yssac/Ysco
Yeszac/VaGo
10
107
10F
100
102
10"
10
10"1
10"1
ONLITS LORA)
+ 3TE/TTLLRRN
+ MRPCITS LORN)
Figure 5: Approximation quality (relative to SGD) of "un "un-damped" iEF, ieKFAC, KFAC and eKFAC for 3 selected PEFT tasks (QNLI+LORA, RTE+LORA, MRPC+LoRA) across training stages. The style of the visualisation follows that for the first 3 plots of Fig. 2 This evaluation shows that, ieKFAC update has similar approximation quality to the exact iEF method, and much better approximation quality than both KFAC and eKFAC in most training stages. This demonstrates the effectiveness of using ieKFAC to approximate iEF and its potential of further improving the approximation quality of existing KFAC-based methods.
D.2.3 Improving Empirical WoodFisher Model Compression
The EF matrix is used in the WoodFisher model compression algorithm [46] as an approximation to the Hessian matrix. It is therefore natural to consider using the iEF matrix in place of the EF matrix to improve the approximation quality. The WoodFisher algorithm relies on a recursion-bac formulation of the EF matrix follows
Voln Vol. F Fat1 = F.,
(44)
N
This can easily switched to the iEF matrix using Eqn. 41 as follows
1 F F = F + N 2 Vol voll'
(45)
E Monte-Carlo Sampled Fisher Matrix
The SF method used in the experimental setups (see Sec. is introduced and analysed in details in this section. commonly used method to estimate the exact Fisher matrix without bias is through Monte-Carlo sampling. which is used in the original K-FAC method as sampled Fisher in this paper. Particularly, when only one Monte-Carla sample is generated for each training sample, the corresponding method is termed SF for brevity. Recall the definition of the Fisher matrix Eqn. ( it can be rewritten using expectations as follows
(27). This method is referred to
Be<po(ylz,)) Ve log P.. (c) Po F Σ,,
(46)
This means, by generating enough labels (with Monte-Carla sampling) from the output distribution po(y),,) and computing the gradient w.r.t these labels Vo log estimated without bias.
Pa (c), the Fisher matrix can be
Assume K labels are generated for each training sample, the exact expression for sampled Fisher with samples (denoted as F(K)) is as follows
F(K)
Σ
Vo Pn ( log (1 K ((K)
(47)
where (k)
po(y) is the k-th generated label for the n-th RNK))P denotes the stacked sampled gradients [V log (1) ).... Vo logop. (1(1) )..., Vo log (N (K))
In
ple,
Jacobian
J(K)
(1)) i.c. sampled Fisher with sampling for each training sample, is used as a baseline approximate
NGD method Sec. (termed as SF this paper) and is compared against EF and iEF, This has
two reasons:
22

---

1. For F(K), K = 1 is more commonly chosen in practice 13 27 than K > 1. This is mainly because F(K) requires K additional back-propagations through the target batch, which becomes very expensive for a large K.
2. F(1) has a maximum rank of N, which is the same rank as the EF matrix (F) and the iEF matrix (F*).
Note that even for F(1), as compared to EF and iEF methods, requires an additional back pack-propagation through target batches. This makes F(1) hard to implement in practice, and becomes nearly twice as
expensive as EF/EF. It is the leading reason that EF is commonly used in favour of F(1) in practice
33 34 49 31
Exact Pre-conditioning with F(1) To properly evaluate the pre-conditioner F(1 either through optimisation or our evaluation framework (see Sec. (). is necessary to exactly compute the pre- conditioned gradient. The Aneeman--Morrioo-Woonn this, which states that (U T U + A = I U (ÜUT + AU)-
(SMW) identity (40] can be used to achieve
The update pre-conditioned by ((1) (denoted as A0sF) takes the following form sf (F + A
(48)
By plugging in F(1) = (() and using the SMW identity, the update can then be computed as follows
20sr - = 11 - (() + -
(49)
which is easy to compute once the Jacobian (1(1) for sampled gradients is collected (using the per-sample gradient collection method described in Appendix Similar EF and iEF, an exact stochastic optimiser can also be constructed for SF; as is described in Algorithm 3 Note that as
compared to Algorithm SF requires an additional back pack-propagation.
Algorithm 3 Stochastic Optimisation with Exact SF
Require: All N training samples, initial model parameters O(0)
for f. = 0 to 7 do
Sample Mini-bated MM(t) with size .M
Perform forward pass on batch M(t) to obtain output distribution p(t)
Perform back pockppropagation obtain accumulated loss Co(e)((((t)
Sample output labels ((() p(l)
Compute cross-entropy loss between p(() and sampled label (()) to obtain the pseudo per-
sample loss vector i(t)
Perform additional back-propagation to obtain Jacobian At) Vony((t) Compute SF update A (t) (t) (())))) +AI) Att Eqn.
Update model 6(t + 1) (tt n)0sr(t)) end for
Impact of Inversely-Sealed Projection on SF Update Although the same analysis in Sec. ccnnoot be applied SF due to the different formulation of the update, the inversely-scaled projection issue is still expected to impact SF. As the model gets better trained, becomes likely for the sampled Fisher matrix F(1) of SF to sample empirical per-sample gradients. Pre-conditioning with the inverse of this matrix would then cause the inverse-scaling issue just like EF, Consequently, poorer approximation quality of SF to the exact NG update is still probable.
Empirical Evaluation Framework for Approximate NGD Methods
F1 Implementation Details
As introduced in Sec. 6 the proposed empirical evaluation framework is built around the proposed indicator 7(-). Consider given model checkpoint (()), M pairs of training samples (In, yn M
23

---

from a target dataset and K approximate NGD methods (.) of interest. Each update generation method can generate an update ()()) for the provided samples and given model checkpoint fol- lowing ()())()) - g (0(()) (Inn (n))1n) The framework is implemented such that K indicators 7 (A)(t)())) are computed, which allows for the quantitative comparison of these update generation methods w.E. their approximation quality the exact NGD method. The detailed evaluation process is described in Algorithm [ In practice, for the k-th update generation method, multiple batches are used to compute a series of (A0(k)) ), and their average is used to provide a more accurate indicator value. Note that this evaluation process can be repeated for model checkpoints different training stages Og to provide more thorough comparison.
is worth mentioning that the ratio Y (/() (()()))) is an important quantity. This ratio describes the relative approximation quality of the target update generation method w.e.t standard SGD method, and should be smaller than I for a good approximate NGD method. If this ratio is consistently larger than I, then the target approximate NGD method (.) has a worse approximation quality than the SGD method and is likely to perform poorly in practice.
The four update methods investigated in the main paper (see Sec. 7 are SGD, HF, iEF and SF (sampled Fisher with Monte-Carlo sample for each training sample). The SGD update is simply the
gradient Verry (()(t)); the iEF update is computed according to Eqn.
(8; the EF update is computed
according to Eqn. (5) the SF update is computed according to Eqn.
Finally, the computationally most expensive operation when computing indicators is finding the matrix-vector product between the exact Fisher and a given update direction, i.e. F PO.. A detailed discussion is provided on its implementation and algorithm complexity in the following section.
Algorithm 4 Empirical evaluation framework for approximate NGD Methods
Input: batch of M training data pairs (ar,: In )M model checkpoint (t), loss function C(O(t)). K update generation methods g (*))(((t))
(In, (In, M) & E {1.... ,K).
Execute:
Compute accumulated gradient VoC(O(t)) on M training samples for k = 1 to K do
Compute update ( = (^)) (0(tt, (In: Yn M
Compute indicator (())())()) = () (Fa (1) end for
(A0())A)) Voce
Output: Return K indicators ())))))))))
Updates with smaller indicator values are
k=1
considered better approximate NG updates.
F11.1 Matrix-Vector Product and Algorithm Complexity
The most important operation in Algorithm 4 when computing the proposed indicator the com- putation of the matrix- product F(-). It is the most expensive operation that dominates both the time and space complexity of this algorithm. Fortunately, this can be efficiently computed in a modern auto-grad framework using the double differentiation trick [44). The key to computing the matrix-vector product with the exact Fisher matrix is identifying the equivalence of the Fisher matrix and the Generalised target model which uses softmax activation and cross-entropy loss function, the following equality holds
matrix (GGN matrix, denoted as G). It can be shown that for the
F F= Σ,
(.) = G.
(50)
Therefore, the matrix-vector product can be broken down into the computation of three separate matrix-vector products. The double differentiation trick is useful when computing the first two matrix- vector products: (.),..)) V2 (-). The final vectox product Voz,, (.) can be computed using the standard back pack-propagttion pipeline. Please refer to for implementation details.
Overall, with the double differentiation trick, the time and memory complexity of the matrix- vector product with the Fisher matrix is comparable to standard training with batch size M. In our implementation in Pytorch, the matrix- vector product requires 2 forward passes and 2 backward passes
24

---

through the model on the M samples. This makes our proposed empirical evaluation framework efficient in practice.
Finally, for the reader's information, we adopt the method used in 25 is possible to further reduce the cost of the matrix-vector product down only additional forward pass and backward pass. However, this may not be preferable choice because it requires customised forward-propagiee propaaationnn code, making our evaluation framework less generally applicable.
E.1.2 Comparison to Traditional Evaluation Methods
As is summarised in Sec. traditional evaluation of the approximation quality to the NGD method requires the explicit storage and inversion of the exact Fisher matrix. This is usually done using the definition in Eqn. 2 For general model, computing the Fisher matrix in Eqn. 2 requires C
separate backwards and forward passes through the model (C' being the output category number). This can range from 10 (e.g. 2)]) to >10,000 (for our LLM finetune setup 77.. From a time complexity perspective, the traditional method can be arbitrarily more expensive than our evaluation framework depending on the output category size C. From a memory complexity perspective, the storage of the Fisher matrix of R is infeasible for a large-scale model. Both of these concerns limit the traditional evaluation of approximate NGD methods in large practical setups. On the contrary, our proposed evaluation framework resolves these limitations of the traditional evaluation method, meanwhile having a strong theoretical motivation. This greatly facilitates the evaluation of approximate NGD methods in large-scale deep-learning setups for methods not limited to EF, iEF and SF.
F.2 Hessian-free Implicitly Minimises r(-) Indicator
In Sec. 6.2 stated that the indicator r(-) is implicitly minimised in the linear CG algorithm
to iteratively approximate the exact NG update in Hessian-free method [25] In this section, this statement formally introduced and justified.
The Hessian-free method is an important approximate NGD method. Unlike most other approximate NGD methods, which approximate the Fisher matrix F directly, the Hessian-free method does not explicitly express the Fisher matrix. Instead, it uses an iterative method to directly solve for AOFF in the following equation
FAO VoL(O)-
(51)
The iterative method used in Hessian-free is the linear CG algorithm 45
which is classical method that iteratively solves for AOHF in Eqn. (5I) with only the access to the matrix-vector product function F(-) (introduced in Sec. (6). Since the Fisher is not required be explicitly stored, the method enjoys a memory complexity of O(P) where P is the number of trainable parameters in a target model.
The linear CG algorithm (without pre-conditioning) used in HF is shown in Algorithm 5
known that the CG algorithm is an efficient solver for Eqn. (5I) and usually regarded locally optimal minimiser (each step uses an exact line search) for the equivalent pseudo loss function
25 45
(cG() VoL(0) - } 1 A0
(52)
However, it is also possible to interpret this method as locally optimal minimiser [8] for the generalised Rayleigh Quotient of positive semi-defnite matrices F and (oC()))oC(
(AO
(53)
AP
Ve
A
HP
where 7(A0FF) happens to be the proposed indicator of this paper. The proof of this statement is provided in the following section.
F.2.1 Proof that Linear CG is Locally Optimal Minimiser for Indicator 7(-)
Note that in every iteration in Algorithm 5 an update (mm tn is accumulated to the final solution This update On Um can be shown achieve the local maximum reduction in 7xx)² in every
2 Mes-
25

---

Algorithm 5 The Linear CG Algorithm in Hessian-free Method
Input: The maximum CG execution iterations McG The gradient vector (e
The matrix-vector product function for the Fisher F Execute:
Set ro b
Set th f to
Set m 4-0 0
while m < McG do
Compute ||rm|| r Tm
Set a.m < || ( Fum)
Update Tm+1 5 xm + am Um
Update pm+11 f- p' am Fum
Compute ||rm+1 12= m Pm+1
Set 3m+1 + ||rm+11| /1/////lmmmmmmmm/m// 1?
Update Um++1 < Tm+11 + 8m+ Um
Update m + m7 +
end while
Output: Return Mcc an approximate solution for A
iteration. Formally, to shown that, for current partial solution am and the given search direction Um. the scaling factor am achieves the maximum reduction in y( ):
Om arg min (3 Mca)
(54)
Now, assume the actual minimiser am is different from the Om in the CG iterations. The true minimiser O'm can be acquired through a Ritz-Rayleigh analysis [18 By setting B VoL(O)VoL(()) and plugging in the true minimiser am Eqn. (54) becomes:
[(mm + amm v) F(W (m + ain v)]
O'm arg min
(55)
[mmm + a'm v) B' (3m u b)
The Ritz-Rayleigh analysis then gives the optimal scaling:
b Vmn
a m
v m
T Fum
(56)
in order to prove Omm ame the following need be proved bT Um T Tmn This can be done through recursion.
Recall that Omn o Frm
For 0, it is obvious that b" bT ro ro.
For m 1, it is known that Un = r -mm-1 - is true, then:
b Um = T (rm + brrm
Bm-mm1)
r
bb rm r m Pm
b Vm
Trr
(57)
=To
T T' + mm--
r 1m
rhrm I'
(. 0)
r Tm
In conclusion, Om is indeed the true minimiser for [m to w) P(r ta to, w]] in every CG iterations,
t to 2) (mm (mm +. v)
making CG locally optimal optimiser for )
26

---

It is known that Hessian-free iteratively approaches the exact NG update [25]. and a larger iteration number Mcg leads better approximation. Now that has been shown that the indicator 7 (xx) decreases (optimally) for every iteration of Hessian-free, it verifies that indicator (ax) directly describes the approximation level of the intermediate solution Zm to the exact NG update.
F.3
7()) Quantifies Loss Reduction Effectiveness under the Local Quadratic Approximation
The indicator (A00) can also describe the loss-reduction effectiveness of a target update direction under the Local Quadratic Approximation. The loss change induced by target update can be estimated using a Taylor expansion up to the second order as follows:
1 A0(1) ((0(t+ 1)) = L()()) A0 Vo)()) 2 BBA00() B,,)))BB,0000
(58)
where B PRPPP is the choice of curvature matrix. Such an approximation the loss function is regarded as a Local Quadratic Approximation (55).
Consider fixed-direction target update AO with an unknown step size n) the maximum achievable loss reduction based on Local Quadratic Approximation can be obtained as follows
v 2y)2 min n00 T VoC(O)+ AO AOTFAO
(59)
where F is used in place of the curvature matrix B. This implies that the maximum loss reduction along update direction AO is -A/2) which is inversely proportional to the square of the proposed indicator. For update with smaller r(A0), it is expected to induce larger loss reduction, with the exact NG update achieving the maximum loss reduction. Consequently, the proposed indicator has strong correlation practical convergence ability of the target update generation method.
G Limitations
Focus on Theoretical Approximation for NGD Method The focus of the paper is on the theoreti- cal approximation methods for NGD, including the exact EF method, the proposed iEF method, and also the SF method. Practical approximate (empirical) NGD optimisers are not the main focus of this paper (e.g. K-FAC (27). EK- EK-FAC (IT) TNT [41] etc.), and no experiments Despite the importance of these practical optimisers in the scene NGD-based optimisation, they seteeturewwwrre approximation
conducted for them.
can all be considered further is an important future work to apply iEF to improve existing approximate NGD optimisers (an example of using iEF to improve empirical K-FAC is provided in Appendix DD2.22.
the EF or SF methods. However,
Limitations of Exact Update Generation The updates generated by EF, iEF and SF methods (defined in Eqn. 5 449 respectively) investigated in this paper "exact", in order provide a more theoretically rigorous comparison and analysis. In our experiments, they are generated based only the current provided batch M(() is described in Algorithms 2 respectively. The implementation of exact EF, iEF and SF updates requires storage of the per-sample gradients, which memory- -emandddd in practice. This limits the scope application of the exact iEF (and EF/SF) optimisers to setups where trainable parameter size is small, such as PEFT for pre- trained models. However, given the rise of PEFT setups, and consider the competitive optimisation performance of the exact iEF optimiser, such limitations may be out- weighted by the gain in practice. Additionally, the exact update formulation of iEF means momentum and weight decay cannot be directly applied with the resultant optimiser. This affects the optimisation performance on certain setups, and further work required to integrate these key techniques with exact iEF optimiser. However, none of these limitations would affect the future work where iEF is incorporated into practical approximate NGD optimisers, where memory constraints and momentum/weight decay integration is already resolved in these practical NGD optimisers.
27

---

H Detailed Experiment Information
H.1 Overall Experimental Setup
Textual Classification of GLUE We have investigated 7 selected GLUE benchmark tasks (50] including CoLA, SST-2, MRPC, QQP, MNLI, QNLI, and RTE, which together cover a range of NLP classification tasks such as sentiment classification, semantic equivalence checking, grammar checking, entailment prediction etc. The same selection of GLUE tasks is used in (7]. One key aspect of GLUE tasks is that they do not have test labels, and for test evaluations, they have to be submitted to their official website (with a maximum allowed frequency of submits per day). The textual label tokens are to be directly predicted by the target model. Also, an instruction is prepended to the input of each training sample. See details in Table. 2 For each task, a pre- trainedddd T5-base model [39] is trained with two -efffiiter-fffcieent finetuning methods: Prompt Tuning [22] and LoRA [16]
Table 2: Training details for the 7 GLUE tasks. The input format column describes how the inputs
are structured before being sent to the model. (S1), ). (S2) represents the default input sentence(s) of the corresponding tasks, some tasks have only one input sentence and some have two. Labels are the tokens to be predicted by the model for each task.
Task
Input Format
Labels
Classify if the following sentence's grammar is
acceptable, unacceptable
CoLA
acceptable or unacceptable: (S1)
Classify if the following sentence's 's sentiment is
SST-2
positive, negative
positive negative: (S1)
Classify if the following Q1 and Q2 are semantically
QQP
equivalent, answer yes or no: Q1: [S1] Q2: (S2)
yes, no
Classify if the following S1 and S2 are semantically
MRPC
equivalent, answer yes no: S1: (S1) S2: (S2)
yes, no
Predict whether the premise entails the hypothesis, contradicts the hypothesis,or or neither, answer yes. no maybe: premise: (S1) hypothesis: [S2) Determine whether the context sentence S contains
MNLI
yes, no, maybe
QNLI
the answer to the question Q. answer yes or no:
yes, no
Q: (S1) S: (S2)
Classify if entailment S2 or not, answer yes no:
RTE
S1: (S1) S2: [S2]
yes, no
Computer Vision Classification with CIFAR100 The well-known CIFARIO0 dataset 19 is used
to finetune the pretrained ViT model g). The model is finetuned with LoRA 16 following the setup
in [15].
H.2
Optimisation Experimental Setup
For Prompt Tuning, the Adafactor [23 optimiser is used as baseline (as is done in (23 7
For all
other training setups, the AdamW 24 optimiser was used as the baseline.
Different tasks were trained with a different number of epochs. The validation accuracy (on the dev set of each task) of the best checkpoint is reported and sent for test evaluation (for GLUE, the checkpoints are submitted to GLUE website (50). Details are shown in Table 3
For all the GLUE tasks and for each finetuning method (Prompt Tuning or LoRA), a single set of hyper- pper-pprameters were searched for each optimiser and is used across runs on all 7 GLUE tasks. Three runs with different seeds were conducted to generate the eтror bar. For each run, the checkpoint with the highest validation accuracy was saved for later evaluation (to get test performance or to be evaluated in the proposed evaluation framework). All optimisers were trained
batch size of 32.
Prompt Tuning + T5-base on GLUE: 20 prompts are used for Prompt Tuning. The trainable parameter size is 15, 360, taking up 0. 0.0069% of the total parameter size (222,918,91 of the basbase model. Constant scheduling was used for Adafactor, SGD and iEF runs. For iEF, EF and SF, a damping of A ==1 1 x 10-12 was used. For the Adafactor baseline optimiser, the hyper-parameter provided in [ was used (which comes from (23)): weight-decay 1 x 10-5, .2 = 0.8, learning rate 77 0.3 and no parameter scaling. For the SGD method, the learning rate is 17 100, which was
28

---

Table 3: Optimisation details all involved tasks. Train epochs represent the number of epochs for which the model trained. Evaluation frequency describes the number of update steps between each validation evaluation on the development set.
Task
Train Epochs
Evaluation Frequency
CoLA
20
100
SST-2
20
1000
QQP
5
1000
MRPC
30
50
MNLI
5
1000
QNLI
15
1000
RTE
40
30
CIFARI00
5
1000
searched from (0.1, 1, 10, 20, 50, 100}. For the iEF method, the learning rate was 1) = 50, which was searched from {1, 10, 50, 100}. For the EF method, different scheduling of learning rate was used to guarantee convergence, due to the inverse scaling of EF updates. The chosen strategy was linearly decaying normalised update, with the first update being normalised to ((1 10 x 10-3 1 x 10 2, 1 10-1 1, 10)) and linearly decaying O. The SF method was trained using the same method as EF with the same set of hyperparameters.
LoRA T5-base on GLUE: The LoRA was set to have rank 8 with dropout 0.1 (15). The trainable parameter size is 884, 736, taking up 0.40% of the total parameter size (222,18,9122) of the T5-base model. Constant scheduling was used for the AdamW, SGD and iEF runs. For iEF, EF and SF, damping of = X 10 was used (it is orders of magnitude larger than that used in Prompt Tuning because the diagonal of the gradient covariance matrix has 5 order of magnitude larger norm LoRA than Prompt Tuning). For the Adam baseline optimiser, the hyper-parameters are: weight-decay
x 10-2, and the learning rate of 1 x 10-3 was searched from (1 x 10-3 10-41 11. For the SGD method, the learning rate was = 0.1, which was searched from {0.1, 1, 10, 20, 50, 100). For the iEF method, the learning rate 77 100, which from {1, 10, 50, 100}. For the EF method, normalised update with linear scheduling was used similar to Prompt Tuning, and starting learning rate of 0.01 was searched from {1 10 5 10 1 10-2,1211 x 10-1,1) The SF method was trained with the same strategy and hyperparameters.
x 10 1 1.
searched
LoRA VIT on CIFAR100 The setup of using LoRA to finetune CIFAR100 in [15 was used. The trainable parameter size is 313,344, taking up 0.36% the total parameter size (86.862,568) ViT model -vit-base-patch166 1-2244 The same hyperparameters for LoRA + T5 was used for these experiments.
H.3 Experiments Compute Resources
All the optimisation experiments and evaluation experiments A100 GPUs with 80GB GRAM. For all the optimisation experiments, optimisation time with different optimisers leads to an additional 60% runtime. For standard SGD/Adam W/Adafactoo//E///BB optimisers, on takes 10 hours. The slowest task (QQP LoRA) takes 20 hours and
a cloud linux machine with
similar, apart from the SF optimiser where the additional pack-propagation
average each complete the quickest task (RTE + Prompt Tuning) takes 0.3 hours. In total 420 GPU hours are run for all optimisation experiments. For evaluation runs, each evaluation is done 100 batches of 160 training samples. For each checkpoint and a choice of damping, the evaluation takes on average 30 minutes. For all the evaluation runs (damping evaluated tasks 3 ckpts 10 damping 150 evaluations,
standard evaluated 15 tasks 7 ckpts 115 evaluated, total 265 evaluation). 133 GPU hours are done. Considering
tuning, and various preliminary runs to make exact EF/EF//F optimisers and the evaluation framework to run properly, in total times of additional compute time required for all experiments.
H.4 Licenses for All Used Assets
The license, citation and link to various asset used in this paper is provided in Table
29

---

Table 4: The license, citation and link to various asset used in this paper.
Asset Name
Citation
URL
License
T5-hase
Model checkpoint
Apache-2.0
ViT-B/16
X
Model checkpoint
Apache-2.1 2.0
GLUE
50
Website
Multiple
CIFARI0/100
Websile
Unknown
Pytorch
Websile
Multiple
H.S
Further Evaluation Plots
Due to space limit and presentation concerns, the evaluation results presented the main text in experiments (EI) and (E3) are only partial. In this section, additional evaluation results presented.
H.S.1 Approximation Quality across Tasks and Training Stages
The same indicator evaluation in Fig. 2 is done for all experimented tasks. full view of the indicator plots are provided in Fig. 6 and Similar trend can be found across tasks.
YscfYsco
Yse/Ysco
Gradient Norm Imbalance
101
10
101
16
10'
104
10"
10
10
107
102
25
50
100
25
50
100
25
50
Epech
Epoedt
Epaact's
Epocth
2510 De
MNLI
MFPC
CN0
OCP
RTF
DIAAR10
Figure 6: Four (log-scaled) ratios computed for checkpoints at various stages of training (sampled at the interval of one epoch) for all LoRA tasks, including T5 7 GLUE tasks and VIT + CIFARIOO 100. The figure drawn in the same fashion as Fig. 2 presentation clarity.
Note that the error bar is not presented to improve
10'
Yir
10
101
Yer/Yoon
101
Gradient Imbalance
102
107
10-1
10
25
50
75
100
25
100
25
50
1.0
100
Epecit
Epoddt
Epacc
RTC
Figure 7: Four (log-scaled) ratios computed for checkpoints various stages of training (sampled the interval of one epoch) for 7 Prompt Tuning tasks for T5 + GLUE. The figure is drawn in the same fashion as Fig. 2 Note that the error bar is not presented to improve presentation clarity.
H.5.2 Impact of Damping Approximation Quality
The same damping analysis in Fig. 3 is applied to several other tasks PSST2+T5+Prompt Tuning, *RPC+TS+Promppt Tuning, CIFARTOO+ ViT RTE+T5#LORA shown in Fig. g respectively). Similar trend can be found across tasks.
30

---

Epoch 1%
Epoch 50%
Epoch 100%
10
10
10
15
10
10
10
10
100
Figure 8: Approximation quality (relative to SGD) of EF, SF and iEF methods w.z.f damping factor at different training stages task SS72+T5+Prompt Tuning. The figure drawn in the same fashion Fig.
Epoch
Epoch
Epoch 100%
EF
SF
10
Figure 9: Approximation quality (relative to SGD) of EF, SF and iEF methods w.t.t damping factor À at different training stages of task MRPC+T5+Prompl Tuning. The figure is drawn in the same fashion as Fig. 3
H.6 Full Optimisation Results
Due to space limit, only partial test performance table (Table is presented for the experiment (E2) in the main text. In this section, the full training, validation and test results for all combinations of structure, tasks and optimisers are reported for the reader's information.
Training curves and validation accuracy curves of different optimisers for the described 15 setups are presented in Fig. [2] and 13 The final training loss for every task, structure and optimiser combination is presented in Table 5 The validation performance for every task, structure and optimiser combination is presented in Table 6 The test performance for all tasks is presented in Table 7
Table 5: Final train loss for all the task, structure and optimiser combinations. The average train loss of the final 100 steps of 3 random seed runs is reported, along with the standard deviation. IEF achieves the lowest final training loss for out of 15 tasks.
CoLA
SST-2
MRPC
QQP
MNLI
QNLI
RTE
CIFAR100
Prompt Tuning
Adafactor
0.07
0.0711.02
0.1620.07
0.02
0.19
0.1040.05
0.2940.08
SGD
0.33
0.04
0.36
0.1540.13
0.31
0.1540.06
0.35
EF
2.28
0.99
2.80
4.2941104
6.11
5.1210.88
1.7940.16
SF
0.1640.10
0.06
0.43
0.1540.02
0.28
0.27
0.36
EE
0.01
0.02
0.04
0.02
0.17
0.09
0.02
LoRA
A
0.10
0.02
0.07
0.07
0.22
0.10
0.02
0.60_n.21
SGD
0.2440.02
0.03
0.12=n.01
0.10+o.05
0.22
0.11
0.1840.07
0.94_n.34
EF
1.92+o.49
0.90
2.541
1.0340.51
3.4240.38
1.3140.80
3.0840.40
3.10_o.11
SF
0.26
0.14
0.35
0.20+a.12
0.24
0.30
0.39
0.63
EF
0.16+0.04
0.02+to.uz
0.06+6.04
0.07
0.3644.05
0.08
0.05
0.59
31

---

Epoch 1%
Epoch 50%
Epoch 100%
IFF
133
1279
100
10
107
102
10
100
12h13
127
10
101
161
10
Figure 10: Approximation quality (relative to SGD) of EF, SF and iEF methods w.E.. damping factor different training stages of task CIFARIOO+ LoT.. The figure is drawn in the same fashion as Fig. 3
Epoch 1%
Epoch 50%
Epoch 100%
SF
IEF
107
10' 10 10
10
10
10'
Figure 11: Approximation quality (relative to SGD) of ER, SF and iEF methods w.r.. damping factor À different training stages of task RTEAA5+LORA. The figure is drawn in the same fashion as Fig. 3
Table 6: Validation metries (multiplied by 100) (on development set) for all the task, structure and optimiser combinations. The average of the highest validation accuracy of 3 random seed runs is reported, along with the standard deviation. Task-specifie metrics are reported in this table. For SST-2, QNLI, RTE and CIFAR100, accuracy is reported. For CoLA, both accuracy and Matthew's s Corr reported. For MRPC and QQP, Fl-score and Accuracy (in order) are reported. For MNLI, average of accuracy for entire development set is reported.
CoLA
SST-2
MRPC
QQP
MNLI
QNLI
RTE
CIFARIO0
Prompt Tuning
82.0
84. 040.3
90.0
Adafactor
94.2=0.25
82.440.25
91.940.00
64.7-0..4
53.8
88.0 08.020.73
87. 20.01
69.140.09
70.0
85.0#4.11
SGD
93.3
74.5
88. 88.72
54.8
+0.1
80.8
80.64s.uu
69.044..1
68.4 68.4+4..01
62.2
EF
90.32g.23
32.9
50.9
55 55.6_1.30
0.5522..58
81.220..11
0.11=0.07
76. 277
90.3 7..3
SF
03.52..s7
77.1
64..2...55
07.2
39.417.71
81.840 65
87 $7.220..0
81.7
86.241.41
90.7 #00002
iEF
94.44
83.4
91.9
74.6+t.55
50.7
89.5+0.40
87. +0.05
LoRA
83. 10..15
88.640.51
90.0=a.16
A
94.9=
83.240.03
92.2+0.05
83.4
93.7
70.75
91.9+t0.26
86. 12..0
81.3440.6
87.3
89.9 89.9=a..o
SGD
95.0+0.15
83.3
92.3
80.9
90.6+1.02
53.6.0.97
90.
86.7=0.8
69.14...0
55.540 28
86.3
EF
91.9.a..77
61.5.10.01
89.4
52.7 02.0=
30.2
10.5
71.440
82.644.32
79.440.49
76.9 16.944..2 28
90. 10.11
SF
94.5520.29
81.940.17
91.820.32
71.8
92.7
48.3
85. 35.2
86.9
83.410.24
88.540
89.9
iEF
94.9
81.24o.u2
92.2+0.11
81.7=u.5a
94.1
59.5
91.844..55
86.640.12
32

---

Table Test performance for all task, structure and optimiser combinations. For all tasks, only one test result is reported for the best validation checkpoint across three random seed runs. Task-specific metrics (all multiplied by 100) on the test set are reported in this table. For SST-2, QNLI, RTE and CIFARION 100, accuracy is reported. For CoLA, Matthew's Corr is reported. For MRPC and QQP, F1-score and Accuracy (in order) are reported. For MNLI, matched accuracy and unmatched Accuracy (in order) reported.
CoLA SST-2 MRPC QQP MNLI QNLI RTE CIFAR100
Prompt Tuning
87.1
71.8
82.9
Adafactor
45.1
94.3
91.5
60.7
82.8
88.8
82.7
78.3
71.3
75.7
SGD
6.4
93.5
87.4
55.3
66.6
88.9
76.5
79.9
0.3
33.4
EF
3.8
90.2
52.4
50.4
66.5
81.6
33.4
79.7
71.5
SF
45.2
93.7
64.1
52.3
67.8
88.5
78.5
88.4
72.0
83.5
iEF
50.9
94.4
91.3
68.2
84.2
89.2
83.4
LoRA
88.6
71.5
83.6
AdamW
52.2
94.5
92.2
71.2
93.9
85.1
88.8
83.1
79.9
71.6
83.5
SGD
47.8
94.0
91.9
70.1
91.3
66.6
88.8
83.8
79.9
65.4
61.4
EF
0.0
92.1
89.4
50.4
31.0
66.5
84.4
62.7
84.3
71.1
82.1
SF
42.2
94.2
91.8
64.9
92.8
75.8
88.4
89.3
71.5
81.1
iEF
51.2
94.4
92.2
69.1
94.3
85.9
88.9
80.8
33

---

SS72
5072 dedin acturacy
5
15
01
1.-
88
1992
0950
colco
st23
Stop
50p
MEAC
SCD
5CD
80-
2
40
500
2
20
20303
50302
10000
20000
2440
10:00
2010
2000
1000
2000
3000
PALL wwdkinn
PALL va Idadin accuncy
ONLITS ring l66
ONJ caldadan aceurary
Adalacoor
SGD
CF
53
70
stãco
stop
550
72
2
10:00
1202 2:302
Training loss and validation accuracy of all the Prompt Tuning tasks (7 GLUE tasks). Validation accuracy is reported the same frequency as is stated by Table For training loss, 100 points are reported across all training stages for every task. Each train loss data point represents the averaged train loss for all train batches between each reported data point. The error bars represent the standard deviation (1 (1-sigma) for 3 random seed runs. The training loss for EF always starts to diverge halfway through training despite the more complicated scheduling, For most tasks, iEF able to reach lower training loss than EF, SF and the well-tuned baseline Adafactor.
Figure 12:
34

---

SS7O
$40
50
60
2-
50
530
2000
15:00
2000 2038
500
1030
15:00
2000
2002
12000
23020
20000
40000
10000
20030
20302
40302
1201 Corinanngg
03
CCT Will CALCE SCCATROY
VIPC bainngg Bas
METCC vill catien SoUrAAy
60
EP
SGO
dhip
Chip
03
640
10-
22000
20000
20000
12022
20082
30000
10302
20000
46dea 53000 stp
33022
15003 20003 stpp
33000 45083
vul cutle
C1140002 vellidion
Adaa
Adtrrw
4.43
550
Adammi
2010
1000
2000
Figure Training loss and validation accuracy of all the LoRA tasks GLUE tasks and CIFAR100). Validation accuracy is reported at the same frequency as is stated by Table For training loss, 100 points are reported across all training stages for every task. Each train loss data point represents the averaged train loss for all train batches between each reported data point. The error bars represent the standard deviation (I-sigma) for random seed runs. The training loss for EF always starts to diverge halfway through training despite the more complicated scheduling. For most tasks, iEF is able to reach a lower training loss than EE, and the well-tuned baseline AdamW.
35

---

H.7 Additional Train-from-Scratee Experiment
All of the experiments presented in Sec. are conducted under PEFT setups. While this allows our experimental results to consider up-to-date model structures and tasks, an additional experiment with larger trainable parameter size (currently less than 1M parameters) and consider non- non-finetuning setup would be beneficial to further validating the statement of this paper. In this section, a train- from-scratch experiment using 10M parameter MLP model on the CIFAR1O dataset is conducted and analysed.
Optimisation Setup The used model structure is a 2-hidden-layer ReLU-activvted MLP model with parameter size of 10,510,346 (~10M), which takes in flattened 3x32x32 image, and has two 2048 hidden layers. This model structure an extension the setups used in (29 28 The model trained for 60 epochs from scratch on the CIFARTI 10 dataset. During optimisation, no weight decay or dropout is applicd. The Adam, SGD, EF, SF and iEF optimisers are used, and for all optimisers, 60 epochs are run with batch size of 64. The learning rate x 10 of Adam is searched from {5 x 10-5, -0-5,, 1 x 10 5 x 10 10-+) J. The learning rate 0.1 of the SGD searched from 0.01, 0.1, 0.5. The learning rate 50 of iEF is searched from 10, 50, 100. The learning rate 0.1 of SF is searched from [0.01, 0.1, 0.5). The learning rate x 10-4 of EF is searched from {1 x 10-5, 5 1 x 10
x 10-3 x 10 1 x 10-1). }. Normalised update with linear scheduler is used for EF and SF in the paper. constant learning rate is used for iEF. A multi-step scheduler (0.1 decay at fixed epoch number 15 is used for Adam and SGD. For each optimiser run, 3 seeds used generate the error-bars.
Experimental Results Following experiment (E2), the training loss curve and validation accuracy curve is plotted in Fig. 14 The validation and test accuracy is reported in Table Following experiment (E3), the effect of damping on the approximation quality across different stages of training is shown in Fig. 15 Note that we did not conduct corresponding experiment for (EI) because we believe most of the relevant information is included in Fig. 15] The experimental results show that the conclusions drawn by the PEFT experiment also hold for large train-from- scratch experiments. The exact iEF method demonstrate comparative/stronge model optimisation performance to Adam/SGD baselines, and it remains be the strongest and most robust method when compared against EF/SF in terms of approximation quality to exact NG updates. Meanwhile, EF shows consistently terrible approximation quality, and struggles optimise the model, when not carefully damped.
Table 8: Validation and Test accuracy of different optimiser runs for MLP+CIFAR10 setup. For each optimiser run, only test accuracy is evaluated for the checkpoint with the best validation accuracy.
iEF
Adam
SGD
SF
EF
Validation Accuracy (%)
58.8
20
56.320.22 56.6
54.820.06 54.344.66
28.2 1.33
Test Accuracy (%)
58.6
54.4
55.2
29.2
36

---

CIFAR10 training loss
CIFAR10 validation accuracy
60
2.2
2.0
50
SGD
SGD
EF
40
EF
1.6
AdamW
AdamW
30
1.4
SF
SF
1.2
20
1.0
0
10000
20000 step
30000
40000
10000
20000 step
30000
40000
Figure 14: Training loss and validation accuracy curves for the MLP + CIFARIO 10 fein-from-seeatch
setup. The style of the figure follows that of Fig. 12 and 13 The optimisation performance follows EF < SGD SF < Adam < iEF, which overall matches the result for the PEFT experiments. Note that, eventually, iEF achieves both the highest validation accuracy and the lowest training loss with constant learning rate, while Adam and SGD require multi-step scheduler to perform well.
Epoch
Epoch 50%
Ecoch 100%
SF
Viysco
Figure 15: Approximation quality (relative to SGD) of EF, SF and iEF methods w.E.f damping factor different training stages of setup task CIFARIO+MLP The visualisation style and the experimental setup follows that of Fig. 3 (E3). This figure demonstrates that the better approximation quality and the robustness damping of iEF also hold for larger mein-from-scratee image classification task different training stages.
37

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: In both the abstract and the (Our Contributions paragraph in) introduction section, we have summarised the scope and the claims of this paper accurately.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: A limitation section is provided in Appendix G which describes the limitation of this work.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiitiinn asymptotic approximations only holding locally). ). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
38

---

Answer: [Yes]
Justification: We believe our theoretical derivations are accurate, and assumptions are stated where necessary, particularly for convergence analysis for which a detailed proof is provided Appendix C
Guidelines:
The answer NA means that the paper does not include theoretical results, All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: Detailed experimental setups are provided in Appendix H.] and Al- gorithms for the proposed empirical evaluation framework and the iEF/EF/SF optimisers are all provided and correctly cross-referenced. Finally, an anonymised codebase (with instructions) is provided in the supplemental material which enables reproducibility of key results in this paper.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility.
39

---

searching are provided in In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: The code reproduce main results of the paper are provided in the supple- mental material with clear instructions. We will make this codebase public on acceptance of this paper.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cr cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ //nips.co... cesipss.c/puullc/guuui httpg/udddee/oeeSuubbbiiinina soioboiiiciioocccccccoooo for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Sec. 7 provides general descriptions of the experimental setup, and further details on data selection, model structures and Appendix H.1 and H.2
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Error bars (I-sigma standard deviation, assuming normally distributed errors) are provided for all experimental results figures in both the main paper and in appendix, apart from for Fig. 6 and where the error bars omitted for clearer presentation. Note
40

---

that the error bars are provided in Fig. in the main text, which includes selected curves in Fig. and 7 All the optimisation runs are done for three random seeds, and the average evaluation metric is reported along with stand deviation. Note that for test results, due to the difficulty of acquiring them (mainly the test result for GL.U tasks), only the test result for the best validation checkpoint is reported (in Table and
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
A discussion compute resources is provided in Appendix H3
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (c.g., preliminary or failed experiments that NeurIPS Code of Ethics tattps://neurigge wwtpccppppcccccccccc..cc.c.cccct http://cccccpppccccccccccaaaeea http://....eppoooo..c.ccccoaaaaa
didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the
Answer: [Yes]
Justification: This paper proposes an improvement to existing optimisation methods, which in general, and indeed, does not deviate from the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
41

---

The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper proposes improvement existing optimisation methods, which should have no societal impacts (in addition to the existing impacts of general neural network optimisers).
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairesss considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We believe paper poses such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
42

---

Answer: [Yes]
Justification: Appendix H.4 provides the related information for all assets used in this paper.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g.. website). the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out to the asset's 's creators.
New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We intend to release the code for the proposed empirical evaluation framework, and the exact iEF/EF/SF optimiser. The code is properly documented, and are included in the codebase for reprehensibility submitted in supplemental material.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/mooel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
This work involves no crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
43

---

Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This work involves crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
44


Reviews:
[{"review_id": "xIUYhjySxl", "reviewer": "Reviewer_Sh4Z", "summary": "Many approaches have been proposed to approximate natural gradient descent, however most of them rely on estimating the fisher matrix with empirical fisher. The estimation is known to have the inversely-scaled projection issue, where the update is inversely proportional to per-sample gradient norm, as such samples that are not well-learnt would have a small update. In addition, as the covariance of the gradient is not invertible, a damping factor is required to ensure invertibility, and this parameter could be hard to tune in practice. To resolve this issue, improved empirical fisher (iEF) is proposed, which multiplies the per-sample gradient by the norm of its likelihood's gradient with respect to the logits, as such all samples would have same scale of updates. The authors then empirically shows that iEF is a better approximation to natural gradient descent (using a novel evaluation metric) compared with standard empirical fisher and shows better performance then AdamW on parameter efficient fine-tuning tasks.", "questions": "- How does the method compare with Gauss-Newton? Can GN be considered as a baseline approach?\n\n- Why does the approximation quality goes worth as optimization proceeds? (first three subfigure in Fig. 2)\n\n- Why is the relationship between approximation quality and damping factor non monotonic? \n\n- How does iEF compare with AdamW in terms of computational cost?\n\n- In the appendix, line 960 says sgd's learning rate is searched between  {0.1, ... ,100}, 100 seems to be a pretty larger number? Is that a typo?\n\n- I wonder if the authors could provide learning rate v.s. metrics plot to better convince readers that the learning rate is well tuned.\n\n- The baseline AdamW uses weight decay but iEF does not incorporate weight decay, it would be nice to see results of AdamW without weight decay.", "limitations": "- The proposed method could potentially be more expensive than standard optimizers as Eq. 8 would require per-sample gradient.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "-The proposed method is well motivated and supported by convergence guarantee.\n\n- The proposed indicator for evaluating natural gradient approximation quality is very interesting and useful.\n\n- The empirical experiments verify the usefulness of the proposed indicator and the proposed iEF method.\n\n- The experiment settings considered are very up-to-date and practical: Parameter efficient fine-tuning for large model.", "weaknesses": "- The evaluation only contains fine-tuning experiments with parameter efficient fine-tuning techniques, it would be nice to have some more train-from-scratch. In addition, the workloads considered are of rather small scale in terms of tunable parameters, e.g. ResNet-18 has 11M parameters, while the largest tasks in the submission, fine-tuning T5 on GLUE, only contains 0.8M parameters.\n\n- The experiments only consider a small number of training iterations (which is common for fine-tuning setting), but it would still be nice to see the behavior of the proposed method in longer training run.\n\n- It would be better if the authors could cite [1] for Fig. 1.\n\n- It would be nice to see experiments for iEF + KFAC (as is discussed in line 722).\n\n[1] Limitations of the Empirical Fisher Approximation for Natural Gradient Descent", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Author Response to Reviewer Sh4Z\nThank you for your review!\n\n>The evaluation only contains fine-tuning experiments with parameter efficient fine-tuning techniques, it would be nice to have some more train-from-scratch...small...tunable parameters...small number of training iterations.\n\nWe agree that a train-from-scratch setup with a large number of training epochs and with a model with a large number of parameters can further support the claims of our paper. We have conducted an experiment for CIFAR10 + large MLP (~10M parameters), which further validates the claims in the main paper. Please refer to ***AE2 of the Global Author Response*** for detailed experiment setup and results.\n\n> It would be better if the authors could cite [1] for Fig. 1.\n\nWe have cited [1] in Appendix B, which is referenced in the caption for Fig. 1. We will add a citation to [1] directly in the caption for Fig. 1 in the final version of the paper.\n\n[1] Frederik Kunstner, Lukas Balles, and Philipp Hennig. (2019). “Limitations of the Empirical Fisher Approximation for Natural Gradient Descent”.\n\n> It would be nice to see experiments for iEF + KFAC (as is discussed in line 722).\n\nWe have conducted a preliminary evaluation (using our empirical evaluation framework) for block-diagonal versions of EF, iEF and SF on a selection of PEFT tasks. We found that KFAC with iEF achieves the most consistently good approximation quality to NG updates as compared to standard KFAC and KFAC with EF. Please refer to ***AE3 of Global Author Response*** for the detailed experiment setup and results.\n\n> How does the method compare with Gauss-Newton? Can GN be considered as a baseline approach?\n\nThe GN algorithm is as expensive to implement as the NGD method, which cannot be easily implemented as a baseline optimiser for large setups. However, it is possible to extend the evaluation framework (by replacing the Fisher matrix $\\mathbf{F}$ with the GN matrix $\\hat{\\mathbf{G}}$ in Eqn (16)) to evaluate the update approximation quality to an exact GN update.\n\n> Why does the approximation quality goes worth as optimization proceeds? (first three subfigure in Fig. 2)\n\nThe datapoints reported in the first 3 subfigures of Fig 2 are relative indicator values w.r.t. SGD, i.e. $\\frac{\\gamma_\\text{update}}{\\gamma_\\text{SGD}}$. Hence, the overall increasing trend only means that the relative improvement of the approximation quality to the NG update w.r.t. SGD diminishes as training progresses, and it does not necessarily mean that the approximation quality becomes worse. The cause requires further investigation, and is likely dependent on the model structure and task of the setup.\n\n> Why is the relationship between approximation quality and damping factor non monotonic?\n\nThe relationship between damping and approximation quality for iEF is overall monotonic, but it is non-monotonic for both SF and EF approximations (see Figs 3/6/7/8/9). Although there is no guarantee that the relationship between damping and approximation quality should be monotonic, the fact that iEF has an overall monotonic relationship while SF and EF do not indicates that iEF is much more well-behaved and less sensitive to damping tuning, which is a practical advantage of iEF.\n\n> How does iEF compare with AdamW in terms of computational cost?...The proposed method could potentially be more expensive than standard optimizers as Eq. 8 would require per-sample gradient.\n\nThe analysis of time and memory complexity of the iEF method is provided in Appendix D.1. The per-sample gradient theoretically can be obtained when computing the batch gradient, and incurs no additional computational cost. The main additional cost comes from the computation of the Gram matrix: $O(M^2P)$, $M$ being the batch size and $P$ being the parameter size, which is relatively small as compared to a back-propagation (assume $M$ is not too large). However, currently our implementation of per-sample gradient is achieved with backward hooks (in Pytorch), which roughly doubles the cost of the standard back-propagation process.\n\nHowever, we would like to emphasize that the exact iEF method implemented in our paper is mainly for theoretical accuracy during experimental comparison. Various mature approximation techniques could be used to accelerate practical iEF-based optimisers (as suggested in Appendix D.2).\n\n> In the appendix, line 960 says sgd's learning rate is searched between {0.1, ... ,100}, 100 seems to be a pretty larger number? Is that a typo? I wonder if the authors could provide learning rate v.s. metrics plot to better convince readers that the learning rate is well tuned.\n\nThe SGD learning rate search range for LoRA + GLUE setups was indeed {0.1, 1, 10, 20, 50, 100} (identical range for PT). Such a large learning rate is searched mainly because in PT setups, which we carried out first, the gradient norm is significantly smaller than for other setups such as LoRA. Hence, a large learning rate is necessary for the model to converge effectively.\n\nWe provide a table of the average validation accuracy (1 seed) vs. SGD learning rate below for the LoRA + GLUE setup to show that our learning rate is well tuned (we also searched an additional 0.01). The validation accruacy is averaged across 5 selected tasks (CoLA, SST-2, MRPC, QQP, RTE).\n\n|lr|Avg Val Acc.|\n|-|-|\n|0.01|80.6|\n|0.1|86.9|\n|1|64.1|\n|10|60.9|\n\n> The baseline AdamW uses weight decay but iEF does not incorporate weight decay, it would be nice to see results of AdamW without weight decay.\n\nWe re-ran the AdamW + LoRA + GLUE experiments without weight decay. The averaged validation accuracy (3 seeds) for 5 selected tasks (CoLA, SST-2, MRPC, QQP, RTE) are as follows:\n\n|Method|Avg Val Acc.|\n|-|-|\n|AdamW|88.0|\n|AdamW w/o wd|87.8|\n|iEF|87.7|\n\nAdamW without weight decay overall shows only slightly worse generalisation, but indeed improves the relative performance of iEF. We are happy to include these results in the final paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "fA2yAl1dcF", "reviewer": "Reviewer_13ZJ", "summary": "The paper analyses the Empirical-Fisher-preconditioned gradient and highlights how its components on the per-sample gradients are biases towards well-trained samples, thus leading to potentially unstable training trajectories. The authors propose to solve this issue by scaling the per-sample components accordingly, which has negligible extra cost.\nTheoretically, they prove convergence guarantees under the full-rank NTK assumption. Empirically, they show that iEF is better aligned with natural gradient than standard EF, and beats some baselines in optimization performance.", "questions": "In line 160 I don't totally get the meaning of \"is now aligned with the convergence level of each sample\", what do you formally mean with the word \"aligned\"? And in which sense does this \"resolve\" the inversely-scaled projection issue?\n\nLines 130-131: \"has full row rank, and both $\\lambda$ and $\\eta$ are infinitesimally small\", aren't this essentially Assumption 5.1 ($\\lambda=0$ and $\\eta\\rightarrow 0$) and Assumption 5.2 (jacobian full-row-rank)?\n\nIs it correct that the reason that limits iEF to scale to big models is the same reason that limits EF (i.e. the matrix inversion part)?", "limitations": "As mentioned before, there are some limitations with classification/regression, which are not well clarified.", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper is very well written and structured. \nNotation and setting are gently introduced. The problem with EF preconditioning is clarified in great extent formally, and also helped with a nice visualization.\n\nThe proposed solution is well supported:\n\n-the negligible extra cost is explained\n\n-theoretical guarantees are carried out, under some (very common in these global convergence results) assumptions\n\n-experiments are done by both measuring alignment (in a clever scalable way) with natural gradient, both", "weaknesses": "Regression or Classification? Section 3 begins saying that the paper focuses on classification, which at first allows the authors to define Fisher matrix discarding integrals in favour of a finite sum notation. Then the visual illustration (Sec 4.2 and App B) is on regression problem where, conveniently, NDG=iEF. It would be more fair to have a toy 2D example where NDG and iEF are not equal. Can you provide it?\nMoreover, Assumptions C.2 and consequently Theorem 5.4 does *not* hold for classification setting (right?). If that's the case you should definitely make it clear.\n\nAnd don't get me wrong, the fact that for scalar-output-regression your proposed iEF is exact natural gradient is great, definitely worth being highlighted. But the way these results are presented is misleading. \n\nTYPOS: \\\n-Line 103 \"Jacobian\" has an extra \"c\" \\\n-Line 128 shouldn't \"loss\" be \"loss change\"? \\\n-Line 153 is \"GDN\" a typo for \"NGD\" or am I missing something? \\\n-Line 270 is \"iEF\" a typo for \"EF\"?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Author Response to Reviewer 13ZJ\nThank you for your review!\n\n>Regression or Classification? Section 3 begins saying that the paper focuses on classification...Then the visual illustration (Sec 4.2 and App B) is on regression problem...It would be more fair to have a toy 2D example where NDG and iEF are not equal...\n\nWe realise a regression visualisation could be confusing as the paper mainly focuses on classification, but we still decided to use the regression setup (Sec 4.2 and App B) in Figure 1 for visualisation for the following reasons:\n1. The least-squares regression problem is commonly used when analysing NGD and EF in the literature [1, 2]. Particularly, our visualisation follows a similar setup to [2], which is an important related work regarding the limitations of EF. Overall, the toy regression example allows us to be consistent with the literature.\n2. The least-squares regression problem have several ***nice properties*** (consider only two datum). There exists ***a unique*** global minimum; the NG update can find the global minimum in one step, and the advantage over all other updates ***is self-evident***; the iEF update and NG update ***has the same form*** (as pointed out in the paper and by the reviewer); the distortion of the EF update ***is extreme***. Note that none of these ***properties*** hold for a classification setup, which may make the visualisation less straightforward to understand.\n\nHowever, as noted by the reviewer, given the scope of this paper, it is important to include a toy 2D visualisation for a classification setup and this is provided in ***Figure 1 of the global response document***. It again demonstrates the distortion effect of EF updates, and the similarity between the iEF and NG updates. Please refer to ***AE1 of Global Author Response*** for details. In the final version of the paper, we will clarify the justifcation of the regression visualisation, and we can include this new classification visualisation if space permits.\n\n[1] Valentin Thomas et al. (2019). “On the interplay between noise and curvature and its effect on optimization and generalization”\n\n[2] Frederik Kunstner, Lukas Balles, and Philipp Hennig. (2019). “Limitations of the Empirical Fisher Approximation for Natural Gradient Descent”.\n\n>Moreover, Assumptions C.2 and consequently Theorem 5.4 does not hold for classification setting (right?). If that's the case you should definitely make it clear.\n\nThe global convergence analysis for classification setup (which is more important for the scope of this paper) is given in Theorem 5.3. We proved Theorem 5.4 mainly to extend the iEF global convergence guarantee to more general setups. The reviewer is correct that Assumption C.2 and Theorem 5.4 does not hold for classification, because the softmax + CE loss function typically used in classification problems is not strongly convex. We will emphasize this point in the final paper.\n\n> Typos...\n\nThanks for pointing out these typos. We will fix them in the final version of the paper.\n\n> In line 160 I don't totally get the meaning of \"is now aligned with the convergence level of each sample\", what do you formally mean with the word \"aligned\"? And in which sense does this \"resolve\" the inversely-scaled projection issue?\n\nWe note that how iEF resolves the inversely-scaled projection issue of EF could be better explained and we provide an alternative clearer explanation here.\n\nThe inversely-scaled projection issue of EF is mainly caused by its per-sample loss reduction $\\Delta \\mathbf{l_\\text{EF}} = -\\eta\\mathbf{1}$ (see equation below line 129), which blindly enforces an equal loss reduction for all training samples without considering their individual level of convergence. This causes EF updates to overly focus on converged samples (with small $||\\nabla_\\theta l_n||$) while ignoring untrained samples (with large $||\\nabla_\\theta l_n||$), as is shown by the projection term $\\kappa_\\text{EF}$ in Eqn (6). To resolve this issue, we improve the per-sample loss reduction behaviour of the EF update to account for the individual convergence level of each sample. The per-sample loss reduction behaviour of iEF is designed to be the same as a GN update: $\\Delta \\mathbf{l_\\text{iEF}} = -\\eta||\\nabla_{z_n}l_n||^2$ as is shown in Eqn (11). This allows iEF updates to be \"curvature-aware\", and focus on reducing the loss of untrained samples (with large $||\\nabla_{z_n}l_n||$) while be conservative to converged samples (with small $||\\nabla_{z_n}l_n||$). Note that $||\\nabla_{z_n}l_n||$ is believed to be a good indicator of the convergence level of a sample because the objective function $l_n(z_n)$ is convex, and $||\\nabla_{z_n}l_n||$ in general becomes smaller as the sample approaches its minimum.\n\nWe feel it would be easier for readers to understand the motivation of iEF if we use Eqn (11) (the per-sample loss reduction) for motivation instead of Eqn (7) (the per-sample projection), and we are happy to make such edits in the final paper.\n\n> Lines 130-131: \"has full row rank, and both $\\lambda$ and $\\eta$ are infinitesimally small\", aren't this essentially Assumption 5.1 and Assumption 5.2?\n\nThe reviewer is correct. We will add a reference to Assumption 5.1/5.2 on line 130-131 in the final paper.\n\n> Is it correct that the reason that limits iEF to scale to big models is the same reason that limits EF (i.e. the matrix inversion part)?\n\nThe reviewer is correct that the practical limitations of exact EF/iEF are identical (given their similar generation process in Algorithm 1/2). However, the main bottleneck of applying iEF/EF to big models is the memory complexity of storing the per-sample gradient $O(MP)$ ($M$ being the batch size and $P$ being the trainable parameter size), instead of the \"matrix inversion\" (for a Gram matrix of size $M\\times M$), which is manageable as long as $M$ is not too large. A detailed discussion is provided in the \"Time and Memory Complexity\" paragraph of Appendix D.1.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "3jhg7klvRx", "reviewer": "Reviewer_4Ck3", "summary": "This paper proposed a new Natural Gradient Descent algorithm called iEF. The authors conduct a theoretical convergence analysis of iEF. The proposed PSMGD method achieves comparable or even superior performance over existing gradient descent methods.", "questions": "1. I think the reason why the authors use Eq. (7) to solve the inversely-scaled projection issue raised in Lines 135-136 is not well explained. Why multiply \"logits-level gradient norm\" can resolve the inversely-scaled projection issue? \n\n2. Though the author says that the proposed scaling vector can be considered as an efficient approximation to the GN algorithm in Section 5.2. This still can not explain why this scaling vector can resolve the inversely-scaled projection issue as the GN algorithm is not proposed for resolving the inversely-scaled projection issue. Additionally, I do not find the definition of the GN matrix and the claim in Lines 175-176 from the reference [26]. Can the authors tell me the detailed location?\n\n3. In Remark 202-204. The authors say \"This means that iEF method does not get stuck in local minima, unlike the gradient descent method.\". I think most gradient descent methods, can achieve the global minima when the target model uses an m-strongly convex objective function.\n\n4. The experimental result is not sufficient. The results for the AdamW and Adafctor methods are not complete. The proposed iEF method achieves comparable performance with AdamW. Some SOTA baselines such as CAME optimizer and Sophia optimizer are missing.", "limitations": "The paper discusses the limitations and there is no societal impact of the work performed.", "rating": 5, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. The paper is fairly easy to read, and the ideas are presented well.\n\n2. The inversely scaled projection issue of EF proposed in this paper is original.\n\n3. The proposed iEF method achieves better performance compared with SGD, EF, and SF methods.\n\n4. The theoretical analysis is comprehensive and the results are easy to understand.", "weaknesses": "1. I think some of the descriptions are not clear enough and difficult to understand\n\n2. The experiment is not sufficient, and the results are not very impressive.\n\nI explain the above weaknesses in the **Questions** part.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Author Response to Reviewer 4Ck3\nThank you for your review!\n\n> I think the reason why the authors use Eq. (7) to solve the inversely-scaled projection issue raised in Lines 135-136 is not well explained...GN algorithm is not proposed for resolving the inversely-scaled projection issue.\n\nWe note that it could be better explained how iEF resolves the inversely-scaled projection issue of EF and we provide an alternative clearer explanation here.\n\nThe inversely-scaled projection issue of EF is mainly caused by its per-sample loss reduction $\\Delta \\mathbf{l_\\text{EF}} = -\\eta\\mathbf{1}$ (see equation below line 129), which enforces an equal loss reduction for all training samples without considering their individual level of convergence. This causes EF updates to overly focus on converged samples (with small $||\\nabla_\\theta l_n||$) while ignoring untrained samples (with large $||\\nabla_\\theta l_n||$), as is shown by the projection term $\\kappa_\\text{EF}$ in Eqn (6). To resolve this issue, we improve the per-sample loss reduction behaviour of the EF update to account for the individual convergence level of each sample. The per-sample loss reduction behaviour of iEF is designed to be the same as a GN update: $\\Delta \\mathbf{l_\\text{iEF}} = -\\eta||\\nabla_{z_n}l_n||^2$ as is shown in Eqn (11). This allows iEF updates to be \"curvature-aware\", and focus on reducing the loss of untrained samples (with large $||\\nabla_{z_n}l_n||$) while be conservative to converged samples (with small $||\\nabla_{z_n}l_n||$). Note that $||\\nabla_{z_n}l_n||$ is believed to be a good indicator of the convergence level of a sample because the objective function $l_n(z_n)$ is convex, and $||\\nabla_{z_n}l_n||$ in general becomes smaller as the sample approaches its minimum.\n\nWe feel it would be easier for readers to understand the motivation of iEF if we use Eqn (11) (the per-sample loss reduction) for motivation instead of Eqn (7) (the per-sample projection), and we are happy to make such edits in the final version of the paper.\n\nRegarding the GN algorithm, the reviewer is correct that it is not proposed to resolve the inversely-scaled projection issue. However, the GN algorithm performs well and is a widely-studied second-order optimiser, particularly for traditional ML setups (and was proposed much earlier (1809) than both NGD (1997) and EF (2007)). The iEF update is designed to match the loss reduction behaviour of the GN algorithm mainly to learn from \"a successful teacher\".\n\n> I do not find the definition of the GN matrix and the claim in Lines 175-176 from the reference [26]. Can the authors tell me the detailed location?\n\nReference [1] below ([26] in main paper) states that the GN algorithm is equivalent to the $L^2$ NGD (which means it searches on the $L^2$ output space, i.e. $z$-space), which is mentioned in Section 2.6 of [1]. The GN matrix was introduced as the $L^2$ information matrix $G^{L^2}(\\theta)$ in section 2.1 of [1] (between Eq. (2.6) and (2.7)).\n\n[1] Levon Nurbekyan, Wanzhou Lei, and Yunan Yang. (2023). “Efficient Natural Gradient Descent Methods for Large-Scale PDE-Based Optimization Problems”\n\n> In Remark 202-204. The authors say \"This means that iEF method does not get stuck in local minima, unlike the gradient descent method.\". I think most gradient descent methods, can achieve the global minima when the target model uses an m-strongly convex objective function.\n\nThe \"m-strongly convex objective function\" in Assumption C.2 means: for the $n$-th sample, the function between the model output $z_n$ and per-sample loss $l_n$ is \"m-strongly convex\". As is stated in lines 652-653, under such an assumption, ***the per-sample loss w.r.t. model parameters can still be arbitrarily non-convex*** (depending on the exact structure of the model, i.e. the function between model parameter $\\theta$ and model output $z_n$). Consequently, gradient descent methods, which operates on the non-convex model parameter space $\\theta$, may not be able to converge to global minima under this assumption.\n\n> The experimental result is not sufficient. The results for the AdamW and Adafctor methods are not complete...Some SOTA baselines such as CAME optimizer and Sophia optimizer are missing.\n\nWe conducted additional baseline experiments (Adafactor, CAME, Sophia for LoRA+GLUE, AdamW for PT+GLUE) for 5 selected GLUE tasks, and the validation performance (3 seeds) is reported in the following tables (following the style of Table 6 in the main paper). The following conclusions can be drawn from these experiments:\n1. AdamW < Adafactor in PT, Adafactor < AdamW in LoRA for 4/5 tasks. That is why these results were left out in the main paper.\n2. In LoRA, CAME > AdamW for 3/5 tasks, Sophia > AdamW for 2/5 tasks, iEF > CAME for 3/5 tasks, iEF > Sophia for 4/5 tasks. The addition of the two new baselines does not change the conclusion of the paper too much, but we are happy to include these new baseline results in the final paper.\n\n**Prompt Tuning**\n\n|Method|CoLA|SST-2|MRPC|QQP|RTE|\n|-|-|-|-|-|-|\n|Adafactor|$82.0\\pm0.44$($53.8\\pm1.01$)|$94.2\\pm0.25$|$84.8\\pm0.35$($88.0\\pm0.73$)|$90.7\\pm0.01$($87.7\\pm0.01$)|$64.7\\pm0.34$|\n|AdamW|$81.7\\pm0.53$($55.7\\pm1.25$)|$94.2\\pm0.07$|$83.1\\pm1.36$($87.8\\pm0.32$)|$89.8\\pm0.27$($86.6\\pm0.32$)|$62.3\\pm4.85$|\n\n**LoRA**\n\n|Method|CoLA|SST-2|MRPC|QQP|RTE|\n|-|-|-|-|-|-|\n|AdamW|$83.1\\pm0.15$($58.7\\pm0.55$)|$94.9\\pm0.07$|$88.6\\pm0.51$($91.9\\pm0.26$)|$90.0\\pm0.16$($86.8\\pm0.06$)|$83.4\\pm1.06$|\n|iEF|$83.4\\pm0.24$($59.5\\pm0.64$)|$94.9\\pm0.21$|$88.5\\pm0.88$($91.8\\pm0.55$)|$89.9\\pm0.99$($86.8\\pm0.12$)|$81.7\\pm0.55$|\n|Adafactor|$82.4\\pm0.22$($57.8\\pm0.52$)|$94.3\\pm0.29$|$86.2\\pm0.99$($90.4\\pm0.57$)|$90.6\\pm0.12$($87.5\\pm0.17$)|$75.6\\pm0.91$|\n|CAME|$83.3\\pm0.25$($59.2\\pm0.75$)|$94.8\\pm0.23$|$89.1\\pm0.79$($92.1\\pm0.63$)|$90.4\\pm0.06$($87.3\\pm0.05$)|$59.3\\pm3.98$|\n|Sophia|$83.2\\pm0.58$($59.2\\pm1.36$)|$94.8\\pm0.23$|$88.4\\pm0.37$($91.8\\pm0.31$)|$90.1\\pm0.16$($86.9\\pm0.19$)|$75.6\\pm0.42$|", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7MyVl4akb0", "reviewer": "Reviewer_Khnn", "summary": "The paper proposes a modification of the empirical Fisher matrix that re-scales\na datum's parameter gradient by its logit gradient. This aims to remove a bias\nin the empirical Fisher, dubbed 'inversely-scaled projection issue', which\nbenefits data points that have already been learned. While the modified\nempirical Fisher does not introduce any significant cost, its approximate\nnatural gradient is shown to be closer to the true natural gradient of the\nempirical Fisher and a Monte-Carlo approximated Fisher, and is more robust to\nthe selection of damping.", "questions": "- Q1: Are there any assumptions on the number of neural network outputs for\n  Theorems 5.3, 5.4? You say they are extensions of the proofs in [48], which I\n  believe are stated for single-output NNs.\n\n- Q2: How does iEF/EF work in settings with sequence-valued predictions per\n  datum and does the computational cost scale in the sequence length?\n\n- Misc: Some typos & editing suggestions\n  - L71: 'has gained' -> 'have gained'\n  - Fig. 1: Please add somewhere in the caption that $N=2$\n  - L153: 'NGD' instead of 'GDN'?\n  - L306: 'suffer' -> 'suffers'", "limitations": "yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- **Clarity & Evaluation:** The text is clearly written, and the proposed\n  modification is theoretically justified. The experiments look thorough to me\n  (error bars, modern fine-tuning applications), are clearly analyzed, and\n  support the paper's main claims.\n\n- **Effectiveness:** The proposed modification does not add significant\n  computational overhead, but is shown to significantly improve the proximity to\n  the true natural gradient. It is easy to integrate into existing approximate\n  natural gradient optimizers and could therefore serve as promising direction\n  for the development of future approximate NGD methods.", "weaknesses": "- **Explanation for better approximation of NG update:** The paper demonstrates\n  empirically that their EF modification leads to pre-conditioned gradients\n  which are closer to the true natural gradient. To me, it is not completely\n  clear how addressing the EF's 'inversely-scaled projection issue' causes this\n  effect. The authors could further strengthen their paper by providing a\n  theoretical argument why removing the empirical Fisher's bias towards learned\n  data points results in pre-conditioned gradients with stronger resemblance to\n  the true natural gradient.\n\n  One way to do this could be by considering the distributions over which the\n  gradient covariances are taken. The empirical Fisher uses the data\n  distribution, and the true Fisher uses the likelihood implied by the model. It\n  might be interesting to look into whether one can make statements how the\n  proposed modification changes the data distribution, and whether it brings it\n  closer to the likelihood used in the true Fisher.\n\n- **Optimizer scalability \\& experimental scope:** The authors focus on\n  evaluating their modification in the 'exact' setting, i.e. without introducing\n  additional structural approximations like block diagonals or Kronecker\n  factorizations. The implementation needs to hold the per-sample gradients in\n  memory, which is costly and renders the optimizer impractical for full\n  training of large architectures. I think this is to some extent okay for the\n  scope of this paper, because it is relatively obvious how one would apply\n  these structural approximations on top of the proposed EF modification.\n  However, the current experiments focus heavily on fine-tuning settings and I\n  wonder if the findings hold for other settings, too. I would be convinced\n  further about the findings if the authors provided an additional experiment\n  for 'traditional' image classification (say CIFAR100 or CIFAR10) with a ResNet\n  (say ~10M parameters).\n\n  It should be possible to scale the implementation to this setup. I believe a\n  good starting point are the hook-based approaches of the BackPACK [1] and ASDL\n  [2] frameworks, in combination with the low-rank tricks described in [3, 4],\n  which instead of storing the per-sample gradients, compute the pre-conditioner\n  matrices from layer inputs and output gradients using less memory.\n\n**References**\n\n[1] Dangel, F., Kunstner, F., & Hennig, P. (2020). BackPACK: Packing more into\n  Backprop. ICLR.\n\n[2] Osawa, K., Ishikawa, S., Yokota, R., Li, S., & Hoefler, T. (2023). ASDL: A\n  unified interface for gradient preconditioning in PyTorch.\n\n[3] Dangel, F., Tatzel, L., & Hennig, P. (2022). ViViT: curvature access through\n  the generalized Gauss-Newton's low-rank structure. TMLR.\n\n[4] Yang, M., Xu, D., Wen, Z., Chen, M., & Xu, P. (2022). Sketch-based empirical\n  natural gradient methods for deep learning. Journal of Scientific Computing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Author Response to Reviewer Khnn\nThank you for your review!\n\n>Explanation for better approximation of NG update...To me, it is not completely clear...why removing the empirical Fisher's bias towards learned data points results in pre-conditioned gradients with stronger resemblance to the true natural gradient... One way to do this could be by considering the distributions over which the gradient covariances are taken...\n\nWe agree that the statistical framework is commonly used to analyse the approximation quality to NG updates. But such a framework cannot be easily applied to analyse iEF because iEF is primarily motivated from an optimisation/geometric perspective. However, it is important future work to find theoretical support for iEF from a statistical standpoint.\n\nAs stated in Sec. 5.2, the iEF update is designed to exactly match the loss reduction behaviour of the GN algorithm, which reduces the loss for each sample according to their logits-level gradient norm. This allows iEF to be \"curvature-aware\", and perform more agressive updates for untrained samples (with large gradient norm) and conservative updates for converged samples (with small gradient norm). This curvature-awareness helps iEF to better approximate second-order methods, including the NGD method. In contrast, due to the inversely-scaled projection issue, EF updates are essentially \"anti-curvature\" and perform agressive updates for converged samples and consevative updates for untrained samples. This clearly makes EF a worse second-order method than iEF. It is worth mentioning that, such curvature-awareness may not hold for SGD updates, which may even increase the loss of some samples (depending on the covariance of the per-sample gradients) in a training batch.\n\n>Optimizer scalability & experimental scope: The authors focus on evaluating their modification in the 'exact' setting...I think this is to some extent okay for the scope of this paper...However...I would be convinced further about the findings if the authors provided an additional experiment for 'traditional' image classification (say CIFAR100 or CIFAR10) with a ResNet (say ~10M parameters)...I believe a good starting point are the hook-based approaches...in combination with the low-rank tricks.\n\nWe note the reviewer's understanding of our \"exact\" experimental setup. Also, the reviewer has provided suggestions regarding scaling up to larger setups. We are already using our implementation of hook-based methods to quickly compute per-sample gradients. However, it should be easier if we use the recommended BACKPACK codebase [1] to extend exact iEF to other model structures. Also, we appreciate the approximation techniques recommended by the reviewer, as making iEF an efficient optimiser through approximation is an important future work. \n\nWe agree that an additional train-from-scratch image classification setup with a larger model would be beneficial to support the claims in the main paper. We have conducted an experiment for CIFAR10 + large MLP (~10M parameters), which further validates the claims in the main paper. Please refer to ***AE2 of the Global Author Response*** for the detailed experiment setup and results. Note that in this setup we did not need to apply any approximations, as we are able to fit the per-sample gradients of each batch into our GPU RAM.\n\n[1] Dangel, F., Kunstner, F., & Hennig, P. (2020). BackPACK: Packing more into Backprop. ICLR.\n\n>Q1: Are there any assumptions on the number of neural network outputs for Theorems 5.3, 5.4?\n\nThere are no assumptions on the number of neural network outputs. This extends the proof in [2] where a regression (scalar-output) model is assumed.\n\n[2] G. Zhang et al (2019). “Fast Convergence of Natural Gradient Descent for Over-Parameterized Neural Networks”.\n\n>Q2: How does iEF/EF work in settings with sequence-valued predictions per datum and does the computational cost scale in the sequence length?\n\nWe focus on classification problems where there is only one output distribution per-datum in the main paper. For sequence-valued predictions, there are multiple output distributions per-datum. Assume teacher-forcing is used for training, where the objective function is cross-entropy and a label is provided for every output time-step (assume $T_o$ output time-steps for each datum). There are two ways of applying EF/iEF to this setup.\n\nIf the output sequence is treated as a single probability distribution, the EF update can be computed according to Eqn (3) (with the single label $y_n$ now replaced with the target output sequence $(y\\_n)\\_1, (y\\_n)\\_2...(y\\_n)\\_{T\\_o}$). Similarly, for iEF, by treating the model output logits as a whole, iEF can still be computed following Eqn (8). Note that now for the iEF scaling factor $\\|\\nabla_{z_n}l_n\\|_2^2$ of the $n$-th datum, output logits $z_n$ becomes the concatenated logits vector for all output time-steps, and the loss $l_n$ becomes the accumulated cross-entropy loss for all output time-steps. In this case, for both EF/iEF, the time complexity is constant per-datum. \n\nAlternatively, every output time-step is treated as an independent classification problem ($T_o$ in total for each datum). Both EF/iEF will now require $T_o$ gradients per-datum (one for each output time-step). In this case, the time complexity becomes $O(T_o)$ per-datum, which scales linearly with sequence length.\n\nThe effectiveness of these methods requires further investigation and is left to future work.\n\n> Editing suggestions...\n\nWe agree with all the editing suggestions by the reviewer, and will fix them in the final version of the paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
# Global Author Response
Thank you all for your positive reviews!

We have attached to this global response a pdf document, which contains information for additional experiments (***AE***) (4 figures with captions) that address concerns regarding our paper. This document is referred to as the "Global Response Document" in our seperate author response to each reviewer. A summary of the contents of this pdf is provided as follows.

### AE1: Logistic Regression Classification
To address the suggestions of reviewer 13ZJ regarding the need for a classification based visualisation for the iEF method (in addition to the least-squares regression visualisation in Figure 1 of the main paper), we have provided a 2D visualisation for a toy logistic regression problem in Figure 1 of the global response document (following the style of Figure 1 in the main paper). Detailed problem setups are provided in the caption, and update generation of SGD/EF/iEF/NGD follows that of Appendix B in the main paper. The visualisation further validates the distortion of EF updates in logistic regression problem, and also demonstrates that iEF indeed resolves the inversely-scaled projection issue and achieves high resemblance to NG updates.
### AE2: Train-from-scratch Experiment
To address the suggestions of reviewer Sh4Z and Khnn regarding the need for an additional experiments on a classical train-from-scratch image classification task with a larger model and more training iterations, we have provided a full set of experimental results for a CIFAR10 + MLP setup (Figure 2, 3 in the global response document, corresponding to E1, E2, E3 in the main paper for PEFT setups). The 3-layer ReLU-activated MLP model has a parameter size of 10,510,346 (~10M), which takes in a flattened 3x32x32 image, and has two 2048 hidden layers (developed based on the setups described in [1, 2]). 
1. An MLP model is used instead of a ResNet model due to the following reasons: **1)** It is straightforward to extend our current per-sample gradient implementation from LoRA setup to MLP model, both of which involve only Linear modules (in Pytorch); **2)** Reviewer Sh4Z and Khnn suggested using a ResNet of ~10M parameters. However, for CIFAR setups, 500 residual blocks are needed to reach this parameter size. While ResNet18 for ImageNet indeed has ~10M parameters, the training set of ImageNet is too large to complete during the limited rebuttal time [3]. Both options are difficult to run given the time constraints; **3)** We believe the current setup is sufficient to provide insight into the behaviours of EF/SF/iEF in a larger train-from-scratch setup.
2. During optimisation, no weight decay or dropout is applied. The Adam, SGD, EF, SF and iEF optimisers are used, and for all optimisers, 60 epochs are run with a batch size of 64. The learning rate 1e-4 of Adam is searched from {5e-5, 1e-4, 5e-4}. The learning rate 0.1 of the SGD is searched from {0.01, 0.1, 0.5}. The learning rate 50 of iEF is searched from {10, 50, 100}. The learning rate 0.1 of SF is searched from {0.01, 0.1, 0.5}. The learning rate 1e-4 of EF is searched from {1e-5, 1e-4, 1e-3, 0.01, 0.1}. Normalised update with a linear scheduler is used for EF and SF as in the paper. A constant learning rate is used for iEF. A multi-step scheduler (0.1 decay at fixed epoch number 15 [3]) is used for Adam and SGD. The training loss and validation accuracy curves are plotted in Fig. 2 of the global response document, error bar computed with 3-seeded runs. The final results of the experiments are as follows:

| Method | Val Acc. | Test Acc. |
| - | - | - |
| iEF     | $58.8\pm0.87$ | $58.6$ |
| Adam | $56.3\pm0.22$ | $56.6$ |
| SGD     | $54.3\pm0.66$ | $54.4$ |
| SF     | $54.8\pm0.08$ | $55.2$ |
| EF     | $28.2\pm1.43$ | $29.2$ |

Overall, we can observe that EF < SF $\approx$ SGD < Adam < iEF in terms of both generalisation and convergence, which is aligned with the claims in the main paper.

3. The approximation quality w.r.t. damping factor result is presented in Fig. 3 of the global response document, which shows consistent results with conclusions drawn in experiment E1, E3 of the main paper. Note that due to space limits, we are unable to provide a plot for experiment E1 (equivalent to Fig. 2 in the main paper)

[1] Behnam Neyshabur, Zhiyuan Li, Srinadh Bhojanapalli, Yann LeCun, Nathan Srebro. (2018). Towards Understanding the Role of Over-Parametrization in Generalization of Neural Networks.

[2] Mahesh Chandra Mukkamala, Matthias Hein. (2017). Variants of RMSProp and Adagrad with Logarithmic Regret Bounds.

[3] Kaiming H, Xiangyu Zhang, Shaoqing Ren, Jian Sun. (2015). Deep Residual Learning for Image Recognition.

### AE3: KFAC + iEF Experiment
As is requested by Reviewer Sh4Z, we have conducted a preliminary evaluation for the concept of combining KFAC with iEF (as discussed in Appendix D.2 of the main paper). The empirical evaluation framework proposed in the main paper is used to evaluate the approximation quality of 3 additional block-diagonal methods: KFAC, eKFAC and ieKFAC. KFAC stands for standard KFAC with SF (with 1 MC sample per-datum). eKFAC stands for KFAC with EF (see Eqn (43)) and ieKFAC stands for KFAC with iEF (see Eqn (44)). All methods use a damping factor of 1e-7 as in experiment E1 of the main paper. The evaluation approximation quality w.r.t. training progress for 3 selected tasks: QNLI+T5+LoRA, RTE+T5+LoRA, MRPC+T5+LoRA are shown in Figure 4 of the global response document. It is demonstrated that ieKFAC achieves the most consistent improvement of the approximation quality to NG updates, as compared to KFAC and eKFAC. This indicates the potential of the developement of ieKFAC in future work.

### Further Additional Experiments
There are other additional experiments that cannot fit into the one-page global response document. We will provided these results in our separate individual author responses.

Meta-review: The reviewers have expressed that the proposed indicator for evaluating natural gradient approximation quality is very interesting and useful. Moreover, the empirical experiments verify the usefulness of the proposed indicator and the proposed iEF method. Besides this, the experiment settings considered are very up-to-date and practical according to the reviewers and the paper is very well written and structured. The proposed solution is also well supported. The reviewers have also highlighted the originality of the proposed method. Furthermore, the theoretical analysis is comprehensive and the results are easy to understand. Given this, I believe this paper will constitute a nice contribution to the conference.
Decision: Accept (poster)