An Improved Empirical Fisher Approximation for Natural Gradient Descent

• Approximate NGD preconditions gradients with an approximate Fisher matrix to accelerate training or improve generalisation.Source: §1 · p. 1
• EF is widely used because it reuses readily computed per-sample gradients, but its approximation quality is questionable and existing evaluation methods do not scale to practical large models.The paper proposes a more generally applicable evaluation framework and an improved approximation that remains efficient to implement.Source: §1 · pp. 1–2
• iEF improves approximation to exact Natural Gradient updates over EF and sampled Fisher, is more robust to damping, and as an optimizer shows strong convergence and generalisation.The paper evaluates exact EF and iEF in practical deep-learning setups, including computer vision and large-language-model fine-tuning.Source: §1 · p. 2

• Many approximate empirical NGD methods use EF, including block-diagonal K-FAC variants; treating some Adagrad methods as empirical NGD is questionable because they use the square root of EF.Source: §2 · p. 2
• EF’s limitations have been reviewed and demonstrated, but analyses of exact EF in larger deep-learning setups were lacking, and practical EF optimizers often require sophisticated damping.Source: §2 · p. 2
• Benchmark performance gives limited information about approximation to exact NG updates, while direct comparisons with exact Fisher matrices or NG updates are difficult for commonplace large-scale models.Source: §2 · pp. 2–3

• For softmax classification, the per-sample loss is categorical cross-entropy, and the Jacobian of per-sample losses represents their parameter gradients.Source: §3 · p. 3
• NGD preconditions the accumulated gradient with the inverse Fisher matrix, while SGD uses the accumulated gradient as its update direction.Source: §3 · p. 3
• Sampled Fisher estimates the exact Fisher using Monte Carlo samples, whereas EF uses empirical gradients and is convenient to compute but may approximate the exact Fisher poorly.The stated EF approximation applies when the model is well trained and its observed-label probabilities approach one.Source: §3 · p. 3

4.1 Formal Definition

• The EF update preconditions the accumulated gradient with the inverse of the empirical gradient covariance plus damping.The damping factor facilitates inversion because the gradient covariance cannot be directly inverted for over-parameterised models.Source: §4.1 · p. 3
• EF induces equal loss reduction on every involved sample, while its update projection onto each sample gradient is analyzed to expose the inversely-scaled projection issue.Source: §4.1 · p. 4
• EF’s projection onto each sample gradient is inversely proportional to that sample’s gradient norm, biasing updates toward well-trained samples and tending to increase update norms as training progresses.A smaller per-sample gradient norm generally indicates that the sample is better trained or closer to its minimum.Source: §4.1 · p. 4

4.2 Visual Illustration

• In the two-parameter regression illustration, EF’s update field is distorted and its trajectories are inefficient, whereas iEF and NGD adapt to the problem’s curvature.EF updates are attracted to each sample’s minimum and can have much larger norms when either sample is nearly converged.Source: §4.2 · p. 4, Figure 1 · p. 4

5.1 Update Formulation

• iEF designs per-sample loss reduction to reflect each sample’s convergence level, alleviating EF’s inversely-scaled projection issue.The logit-level gradient norm generally decreases as a sample becomes better trained.Source: §5.1 · p. 5
• iEF achieves consistently better approximation quality to NG updates than EF and sampled Fisher, while remaining robust to damping choices across tasks and training stages.The update can be obtained alongside back-propagation with negligible overhead.Source: §5.1 · p. 5

5.2 Theoretical Connection to Generalised NGD

• iEF’s loss-reduction behavior approximates Gauss-Newton; it is equivalent to Gauss-Newton for supervised regression and to exact NGD for least-squares regression.The scaling choice is motivated by the Gauss-Newton algorithm.Source: §5.2 · p. 5

5.3 Convergence Analysis

• Under the stated assumptions, iEF has sub-linear global convergence for softmax with cross-entropy and linear global convergence for strongly convex objectives.The strongly convex condition is on the objective with respect to model output; the loss landscape with respect to parameters may remain non-convex.Source: §5.3 · pp. 5–6

5.4 Applications of IEF

• For small-parameter models, exact iEF can be used directly as an optimiser and shows competitive convergence and generalisation against well-tuned baselines.These outcomes are evaluated in experiment E2.Source: §5.4 · p. 6
• The iEF matrix has an EF-like form and yields better NG-update approximation than EF and sampled Fisher, without requiring damping tuning.The paper presents iEF as a low-cost Fisher approximation that could improve Fisher-based methods beyond optimisation.Source: §5.4 · p. 6

6 Empirical Evaluation Framework for Approximate NGD Methods

• The framework evaluates approximate NG updates quantitatively and efficiently in large-scale setups, without constraining model size or structure.It is designed to address the high memory and time costs of traditional evaluation methods.Source: §6 · p. 6

6.1 Efficient Indicator of Approximation Quality

• Smaller γ(∆θ) indicates a better approximation to the exact NG update, and computing the indicator requires an exact-Fisher matrix-vector product that modern auto-grad frameworks can perform efficiently.This supports application to large-scale models.Source: §6.1 · p. 7

6.2 Theoretical Motivation

• An update with smaller γ(∆θ)^2 is a strictly better approximation under the paper’s alternative NGD definition, and 1/2γ(∆θ)^2 quantifies maximum local-quadratic loss reduction for a given direction.The exact NG update minimises γ(∆θ)^2; the linear conjugate gradient algorithm used in Hessian-free is a locally optimal minimiser.Source: §6.2 · p. 7

Experimental setup

• The experiments compare exact EF, iEF, and sampled Fisher methods across 15 setups, including T5 and ViT parameter-efficient fine-tuning tasks.The setups include T5-base with LoRA and Prompt-Tuning on GLUE, and ViT with LoRA on CIFAR100.Source: §7 · p. 7

E1: Approximation Quality to NG Updates

• For most training stages and all setups, iEF improves on SGD updates and outperforms EF and SF in approximation quality.Figure 2 shows the iEF > SF > EF ordering for most training stages; EF and SF surpass iEF only at training’s start.Source: §7 · pp. 7–8, Figure 2 · p. 8
• As training progresses, greater per-sample gradient-norm imbalance correlates with poorer EF and SF approximation, while affecting iEF less.The authors interpret this pattern as evidence that the inversely-scaled projection issue substantially reduces EF and SF approximation quality.Source: §7 · p. 8

E2: Optimisation Performance

• iEF achieves the best generalisation on 10 of 15 tasks, while reaching the lowest final training loss and providing comparable or better performance than tuned baselines.It outperformed Adafactor on 6 of 7 Prompt Tuning tasks; on LoRA tasks, iEF and AdamW each outperformed the other on 4 of 8 tasks.Source: §7 · pp. 7–9

E3: Impact of Damping

• Across tasks and training stages, near-zero damping gives iEF strong approximation quality, while EF and SF require difficult-to-tune damping schedules.EF and SF can improve with well-chosen damping, but their optimal damping changes across tasks and training stages; iEF is comparable to optimally damped SF.Source: §7 · pp. 8–9, Figure 3 · p. 9

8 Conclusions and Future Work

• Experiments support iEF’s convergence and generalisation on most evaluated tasks, its improved approximation quality over EF and SF, and its robustness to damping choices.The authors identify iEF as a possible improvement to Fisher-based methods beyond optimisation.Source: §8 · p. 10

A Relation between iEF, GN and NGD in Different Machine Learning Setups

• For scalar-output regression, iEF is equivalent to Gauss–Newton; for least-squares problems, iEF, Gauss–Newton, and Natural Gradient descent are equivalent.These equivalences are presented for the machine-learning setups discussed in the appendix.Source: A Relation between iEF, GN and NGD in… · p. 15

A.1 Regression Model Problem

• In scalar-output regression, the iEF matrix has the same form as the Gauss–Newton matrix, making the methods equivalent in that setup.The appendix describes regression with a scalar model output and per-sample losses.Source: §A.1 · p. 15

A.2 Least-Squares Problem

• For least-squares problems, the iEF, Gauss–Newton, and Natural Gradient matrices coincide, and their methods produce the same update vector field.The paper reports this shared update vector field in Figure 1.Source: §A.2 · p. 15

B Visualisation for Linear Least-Squares Problem with Two Training Samples

• EF trajectories are distorted by inverse scaling: updates are attracted to better-converged samples and can deviate from both gradient descent and the optimal NG direction.When per-sample gradient norms are imbalanced, EF updates can become nearly parallel to the loss contour and oscillate; the plotted trajectories use updates normalised to 1 × 10−2.Source: B Visualisation for Linear… · p. 16
• In the two-sample least-squares visualisation, NG and iEF have the most efficient trajectories, while EF’s updates grow when either sample is nearly converged.The setup uses two parameters and two training samples; its unique global minimum is θ⋆ = [0, 0]⊤.Source: B Visualisation for Linear… · pp. 15–16
• The toy regression setup makes EF’s distortion especially clear: NG reaches the unique global minimum in one step, and iEF has the same update form as NG.The authors chose this visualisation for its clarity and consistency with prior EF analyses [20] [47].Source: B Visualisation for Linear… · pp. 16–17
• In the logistic-regression visualisation, EF is ill-behaved, whereas NG and iEF move smoothly toward the x = 1 decision boundary.Unlike the regression example, this setup has no global minimum; loss decreases farther toward the bottom-right corner.Source: Figure 4 · p. 17

C Convergence Analysis

• Under softmax plus cross-entropy, iEF guarantees global sub-linear convergence of each sample’s target probability toward 1, and hence of accumulated loss toward its global minimum.The analysis assumes a full-row-rank per-sample gradient matrix throughout training; the authors characterize this as a mild assumption for practical deep learning.Source: C Convergence Analysis · pp. 17–18

C.1 Global Linear Convergence for Strongly Convex Objective Functions

• For per-sample objectives that are m-strongly convex in model-output space, iEF preconditioned gradient flow is guaranteed to converge globally and linearly to the accumulated-loss minimum.The result relies on a Polyak–Łojasiewicz inequality; the parameter-space loss landscape may still be arbitrarily non-convex.Source: §C.1 · p. 19

D.1 Stochastic IEF/EF Optimiser

• The stochastic exact iEF optimiser computes updates from a mini-batch’s per-sample gradients and logits-gradient norms, but its O(MP) memory cost limits practical use to small trainable models or small batches.For P ≫ M, update time is O(M²P); collecting per-sample gradients requires storage, while logits-gradient retention adds negligible cost in general deep-learning setups.Source: §D.1 · p. 20

D.2.1 Expression of IEF Matrix

• The iEF matrix preconditions updates equivalently to the iEF update, and differs from EF by rescaling each per-sample gradient with the inverse logits-gradient norm.This diagonal scaling is described as straightforward to implement in approximate empirical NGD optimisers.Source: §D.2.1 · p. 21

D.2.2 Improving Empirical K-FAC with IEF

• The iEF rescaling can be incorporated into empirical K-FAC by diagonally rescaling its gradient-factor estimate, with negligible extra computation for the logits-gradient norm vector.The authors present this integration as a starting point for improving other approximate empirical NGD methods.Source: §D.2.2 · p. 21, §D.2 · p. 21
• ieKFAC has approximation quality similar to exact iEF and much better than KFAC and eKFAC in most stages across the three selected PEFT tasks.The comparison uses un-damped updates on QNLI+LoRA, RTE+LoRA, and MRPC+LoRA across training stages.Source: §D.2.2 · p. 21, Figure 5 · p. 22

D.2.3 Improving Empirical WoodFisher Model Compression

• The paper proposes replacing EF with iEF in the recursion-base formulation used by WoodFisher model compression.The supplied passage describes the substitution, but reports no evaluation result for this change.Source: §D.2.3 · p. 22

E Monte-Carlo Sampled Fisher Matrix

• With one Monte Carlo label per training sample, SF is the sampled-Fisher baseline; that estimate is unbiased, but requires an additional back-propagation and is nearly twice as expensive as EF/iEF.One sample is commonly chosen because K samples require K additional back-propagations; the one-sample Fisher has the same maximum rank as EF and iEF.Source: E Monte-Carlo Sampled Fisher Matrix · pp. 22–23
• As training improves, SF may sample empirical per-sample gradients, so inverse scaling is expected to impair its approximation of exact NG updates.The paper notes that the Sec. 4 analysis does not apply directly to SF's different update formulation.Source: E Monte-Carlo Sampled Fisher Matrix · p. 23

F.1 Implementation Details

• The evaluation framework compares update methods by averaging γ indicators across batches and checkpoints; a smaller γ(∆θ)/γ(SGD) ratio indicates better approximation quality than SGD.A ratio consistently above 1 indicates worse approximation quality than SGD and likely poor practical performance.Source: §F.1 · p. 24

F.1.1 Matrix-Vector Product and Algorithm Complexity

• For softmax models with cross-entropy loss, the framework computes exact-Fisher matrix-vector products through the Fisher–GGN equivalence and double differentiation, at cost comparable to standard training.The implementation uses two forward and two backward passes; a lower-cost method from requires customized forward-propagation code.Source: §F.1.1 · pp. 24–25

F.1.2 Comparison to Traditional Evaluation Methods

• The framework avoids explicitly storing and inverting the exact Fisher, whose computation can require C forward/backward passes and whose P × P storage is infeasible for large models.The proposed method is intended to facilitate evaluation in large-scale deep-learning setups, including methods beyond EF, iEF, and SF.Source: §F.1.2 · p. 25

F.2 Hessian-free Implicitly Minimises γ(·) Indicator

• Hessian-free optimization uses linear conjugate gradients with Fisher matrix-vector products, without storing the Fisher, giving memory complexity O(P).The paper interprets this method as locally minimizing a generalized Rayleigh quotient of F and ∇θL(θ)∇θL(θ)⊤, which corresponds to its indicator γ(∆θHF).Source: §F.2 · p. 25

F.2.1 Proof that Linear CG is a Locally Optimal Minimiser for Indicator γ(·)

• Each conjugate-gradient step is shown to reduce γ(x)^2 optimally along its search direction, and γ decreases with iterations as Hessian-free approaches the exact NG update.This supports γ as an indicator of the approximation level of intermediate Hessian-free solutions.Source: §F.2.1 · pp. 25–27

F.3 γ(·) Quantifies Loss Reduction Effectiveness under the Local Quadratic Approximation

• Under the local quadratic approximation with F as curvature, the maximum loss reduction along an update is −1/2γ(∆θ)^2; lower γ therefore corresponds to greater expected reduction.The exact NG update achieves the maximum loss reduction in this account.Source: §F.3 · p. 27

G Limitations

• The study evaluates exact EF, iEF, and SF approximations, not practical structured optimizers such as K-FAC, EK-FAC, or TNT; applying iEF to those methods remains future work.The paper frames those practical optimizers as further structure-aware approximations to EF or SF.Source: G Limitations · p. 27
• Exact EF, iEF, and SF require storing M per-sample gradients, limiting their optimizer use to small trainable models such as PEFT; exact iEF also lacks direct momentum and weight-decay integration.The paper notes that these constraints do not apply to future use of iEF inside practical approximate NGD optimizers.Source: G Limitations · p. 27

H.1 Overall Experimental Setup

• The experiments span seven GLUE tasks with T5-base using Prompt Tuning or LoRA, plus CIFAR100 with ViT and LoRA; the appendix also supplies task-specific training and evaluation details.GLUE test labels are not available directly, so test evaluation uses submissions to the official site.Source: §H.1 · p. 28

H.5 Further Evaluation Plots

• Across tasks and training stages, the indicator plots show similar trends, and the damping analyses report similar trends across the additional tasks examined.The figures cover LoRA and Prompt Tuning settings, including CIFAR100+ViT+LoRA and RTE+T5+LoRA.Source: §H.5.1 · p. 30, §H.5.2 · p. 30, Figure 6 · p. 30

H.6 Full Optimisation Results

• The appendix reports results for all 15 setups, with final training loss, validation metrics, and test performance organized in Tables 5–7.Table 5 averages the final 100 training steps across three seeds; Table 7 reports a single test result for each best-validation checkpoint across three seeds.Source: §H.6 · p. 31, Table 5 · p. 31, Table 6 · p. 32
• iEF achieves the lowest final training loss in 12 of 15 tasks; EF training loss diverges halfway through training, while iEF reaches lower loss than EF, SF, and the tuned baseline on most tasks.The curves cover 7 Prompt Tuning GLUE tasks and 7 LoRA GLUE tasks plus CIFAR100.Source: Table 5 · p. 31, Figure 12 · p. 34, Figure 13 · p. 35

H.7 Additional Train-from-Scratch Experiment

• The experiment addresses the PEFT-only scope of the earlier results by training a 10,510,346-parameter, two-hidden-layer MLP from scratch on CIFAR10 for 60 epochs.The MLP uses ReLU activations and batch size 64; no weight decay or dropout is applied.Source: §H.7 · p. 36
• iEF shows competitive or stronger optimization than Adam and SGD and remains strongest and most robust against EF and SF in approximation quality to exact NG updates.EF has consistently poor approximation quality and struggles to optimize without careful damping.Source: §H.7 · p. 36
• For the 10M-parameter CIFAR10 MLP, iEF eventually reaches the highest validation accuracy and lowest training loss with a constant learning rate, while Adam and SGD require a multi-step scheduler.The reported optimization ranking is EF < SGD ≈ SF < Adam < iEF.Source: §H.7 · p. 36, Figure 14 · p. 37
• The larger train-from-scratch experiment also shows iEF's better approximation quality and damping robustness across training stages.Figure 15 evaluates approximation quality relative to SGD across damping factors for CIFAR10+MLP.Source: §H.7 · p. 36, Figure 15 · p. 37