Fisher-Legendre (FishLeg) optimization of deep neural networks
Authors: Jezabel R Garcia
Federica Freddi
Stathi Fotiadis
Maolin Li
Sattar Vakili
Alberto Bernacchia
Guillaume Hennequin
Venue: ICLR 2023 notable top 25% (2023)
Keywords: Second-order optimization
Natural Gradient
Deep Learning
Meta-learning
Fisher information
Legendre-Fenchel duality

Abstract: Incorporating second-order gradient information (curvature) into optimization can dramatically reduce the number of iterations required to train machine learning models. In natural gradient descent, such information comes from the Fisher information matrix which yields a number of desirable properties. As exact natural gradient updates are intractable for large models, successful methods such as KFAC and sequels approximate the Fisher in a structured form that can easily be inverted. However, this requires model/layer-specific tensor algebra and certain approximations that are often difficult to justify. Here, we use ideas from Legendre-Fenchel duality to learn a direct and efficiently evaluated model for the product of the inverse Fisher with any vector, in an online manner, leading to natural gradient steps that get progressively more accurate over time despite noisy gradients. We prove that the resulting “Fisher-Legendre” (FishLeg) optimizer converges to a (global) minimum of non-convex functions satisfying the PL condition, which applies in particular to deep linear networks. On standard auto-encoder benchmarks, we show empirically that FishLeg outperforms standard first-order optimization methods, and performs on par with or better than other second-order methods, especially when using small batches. Thanks to its generality, we expect our approach to facilitate the handling of a variety  neural network layers in future work.

Published as a conference paper at ICLR 2023
FISHER-LEGENDRE (FISHLEG) DEEP NEURAL NETWORKS
OPTIMIZATION OF
Jezabel R Garcia' " Federica Freddi Stathi Fotiadis' Maolin Li', Sattar Vakili', Alberto Bernacchia & Guillaume Hennequin 122,*
MediaTek Research, Camboume Business Park, CB23 6DW, UK first last www.teearcr.eeecc....m..... com
Computational and Biological Learning Lab, Department of Engineering, University of Cambridge, Cambridge CB2 IPZ, UK
g. www.nnnninnnnn cam ac uk
Equal first/senior authors contributions
ABSTRACT
Incorporating second-order gradient information (curvature) into optimization can dramatically reduce the number of iterations required to train machine learning models. In natural gradient descent, such information comes from the Fisher in- formation matrix which yields a number of desirable properties. As exact nat- ural gradient updates are intractable for large models, successful methods such as KFAC and sequels approximate the Fisher structured form that can easily be inverted. However, this requires model/layer-specific tensor algebra and cer- tain approximations that are often difficult to justify. Here, we use ideas from Segendre-Fencher duality to learn direct and efficiently evaluated model for the product the inverse Fisher with any vector, in an online manner, leading to natural gradient steps that get more accurate over time despite noisy gradients. We prove that the resulting "Fisher-Legendde"" (FishL.eg) optimizer converges to a (global) minimum of non-convex functions satisfying the PL condition, which ap- plies in particular to deep linear networks. On standard auto-encoder benchmarks, we show empirically that FishLeg outperforms standard first-order optimization methods, and performs on par with or better than other second-order methods, especially when using small batches. Thanks to its generality, we expect our ap- proach to facilitate the handling of variety neural network layers in future work.
INTRODUCTION & SUMMARY OF CONTRIBUTIONS
The optimization of machine learning models often benefits from the use of second-orde gradient (curvature) information, which can dramatically increase the per-iteration progress on the training loss. However, second-order optimizers for machine learning face number of key challenges:
1. ML models tend have many parameters, such that estimating the curvature along dimen- sions is intractable. There are normally two ways around this: (i) using iterative methods where each iteration only exploits curvature information along a single dimension ("Hessian free" methods; Martens al. (2010). and (ii) developing custom curvature approximations that can be efficiently inverted to obtain parameter updates (Martens & Grosse 2015) Grosse & Martens) Botev
B0teeBotev et 2017 George et al.) 2018, Bahamou et 2022 (Sori al. (2022). The latter yields state-of-the-art performance in the optimization of deep networks (Goldfarb et al. 2020). However, development of structured curvature approximations must be done on case-by-case basis for each architecture (e.g. fully-connected or convolutional layer) and requires mathemati- cal assumptions that are difficult justify.
2. ML datasets tend to be large well, such that the loss, its gradients, and its curvature can be only stochastically estimated from mini-batches While noise can be mitigated by a combination of large mini-batche and momentum, estimating the various components of the curvature ma- trix before inverting (as opposed to estimating the inverse directly) introduces a bias that can potentially be detrimental.

---

Published as a conference paper at ICLR 2023
Here, focus primarily the Fisher information matrix (FIM) notoriously effective source of curvature information for training ML models. For probabilistic models, preconditioning the gradient by the inverse FIM yields so-called natural gradient updates (Amari 1998). We introduce a novel framework for second-order optimization of high-dimensional probabilistic models in the presence of gradient noise. Instead of approximating the FIM in way that easily be inverted (e.g. as in KFAC; Martens & Grosse 2015 and related approaches), we directly parameterize the inverse FIM. We make the following contributions:
We show that the inverse FIM can be computed through the Legendre-Fenchel conjugate of a cross entropy between model distributions.
We provide algorithm (FishLeg) which meta-learns the inverse FIM in online fashion, and we prove convergence of the corresponding parameter updates.
We first study its application to deep linear networks, an example of non-convex and pathologi- cally curved loss functions with Fisher matrix known in closed form (Bernacchia et al. 2018 Huh, 2020), and find that convergence occurs much faster than SGD with momentum or Adam.
We then show that, in standard auto-encoders benchmarks, FishLeg operating a block- diagonal Kronecker parameterization of the inverse Fisher performs similarly to and sometimes outperforms previous approximate natural gradient methods (Goldfarb et al. 22020), whilst be- ing only twice slower than SGD with momentum in wall-clock time per iteration.
Similar to Amortized Proximal Optimization (Bae al. 2022). FishLeg can accommodate arbitrary parameterizations of the inverse Fisher, thus facilitating future applications of the natural gradient to a broad range of network architectures where manually approximating the FIM an easily invertible form is otherwise difficult.
2
BACKGROUND
2.1 FISHER INFORMATION AND THE NATURAL GRADIENT
We consider probabilistic model parameterized by vector 0, which attributes negative log- likelihood f D) = log p ( to any collection D of data points drawn from a data distribution pT This covers a broad range of models, including discriminative models for regression or classification, as well as generative models for density modelling. The goal is to find parameters 0 to approximate the true data distribution p" (D) by the model distribution p(D (*))
The Fisher information matrix (FIM) measures how much information can be obtained about pa- rameters 0 after observing data D under the model p(D (), and captures redundancies between parameters (Rao, 1992). The FIM is defined
I(0)= = ED==p(Do)) (o D) TT
(I)
By this definition, the FIM is positive semi-definite matrix. It can be shown that under certain regularity conditions, and if is twice differentiable w.r.t. O, then the FIM can also be computed as
I(0)= = Ep-r(Dle) (),,D
It is important note that the average is computed over the model distribution p(D)0), not the data distribution p² (D). Averaging Eq. over p p²(D) results in the empirical Fisher matrix (Kunstner
al.) 2019). while averaging Eq. 2 over p² results in the Hessian of the loss. The FIM, the
empirical Fisher and the Hessian are all different and sometimes confused (Thomas et al. 2020
We consider cases in which parameters are obtained by maximum likelihood:
0 arg min L())
(3)
0
where the population loss function is defined
(( Ep-p- E
which is general non-convex, in particular when the model distribution parameterised by deep neural networks. The natural gradient update takes the form
O 0, 1 I(0) -100)((((0) (() with g()) voL(O)
(5)
2

---

Published as a conference paper at ICLR 2023
where 1) is learning rate and g is the gradient of the loss. In practice, the true distribution of data p" (D) is unknown and we have only access to the empirical loss and a stochastic estimate g of the gradient based on finite sample of data D p². Similarly, while the FIM may be sometimes computed exactly (Bernacchia et al., 2018 Huh 2020). in most circumstances it is also estimated from mini-batch D p. To guarantee invertibility of the FIM, small amount of "damping" can be added to it when it is nearly singular. Note that Eq. is identical to gradient descent when the FIM equals the identity matrix. The natural gradient has several nice properties that make an efficient optimizer (Amari 1998), but computing and inverting the FIM is usually costly.
2.2 THE LEGENDRE- CONJUGATE
The Legendre-Fenchel (LF) conjugate is useful tool in optimization theory to map pairs of prob- lems via duality (Boyd & Vandenberghe 2004) and was introduced in the context of mechanics and thermodynamics (Zia et al. 2009). In the following, we deviate from the standard textbook notation to avoid conflicts with the rest of the paper and to facilitate the translation of these classical results to our problem. Consider a twice differentiable function H(5) of a vector 6, generally non-convex and assume minimum of H. exists. The LF conjugate is equal
Ht (u) ming H(6) -
The LF conjugate, also known as the convex conjugate, is defined also for non-differentiable func- tions and always convex. We summarize here two properties of the convex conjugate H* that we use in our derivations (see chapter 3.3 of Boyd & Vandenberghe, 22004 and ZZia et al. 2009 for details):
Property
The gradient of the conjugate is equal to
V.H (u) = u(u) where ō(u) argmin H(0) u.
The minimizer 5(u) also satisfies VoH((())) = u. implying that Vu is (local) inverse func- tion of V.H. The inverse is global when the function H is strictly convex:
VnH (u) (Vo7)) (u).
Property 2
The Hessian matrix of the conjugate is equal to the inverse (if it exists) of the Hessian matrix of H. computed at ô(u):
V2H(( ((3(())(V(H((66m)
3 RELATED WORK
Natural gradient The Hessian of non-convex losses is not positive definite, and second-order
methods such Newton's update typically do not converge to minimum (Dauphin et al.) 2014).
The natural gradient method substitutes the Hessian with the FIM, which is positive (semi definite
Amari 1998). The natural gradient has been applied to deep learning in recent years (Martens)
& Grosse 2015 Bernacchia et al. 2018 Huh 2020 Kerekes et al.] (021), and has been proved approximately equivalent local loss optimization (Benzing 2022 Meulemans et al.) 2020 Amid
ct al. 2022). Previous work on natural gradient approximately estimated and inverted the FIM analytically (Martens & Grosse 2013 Martens et al. 2018). Instead, we use an exact formulation of the inverse FIM as the Hessian of the LF conjugate of the cross entropy, and we provide an algorithm to meta-learn an approximation the inverse FIM during training.
Legendre-Fenchel conjugate For convex losses, Eq. g implies that the parameter update AO -vLl* (0) VgL* (0) converges
minimum in one step (Maddison et al., 2021 Chraibi et al. 2019). However, this update is not practical because finding Z. is at least as hard as finding a minimum of the loss. [Chraibi et al. (2019) propose to learn L by a neural network, and similar "amortized duality" approaches have recently been developed for optimal transport (Nhan Dam et al. 2019 Korotin et al.) 2019 Makkuva et al. 2020; Amos 2022). Maddison et al. (2021) prove that, if surrogate for L. satisfies relative smoothness dual space, then linear convergence rates can be proven for non-Lipschitz or non-strongly convex losses. Here we consider non-convex losses and we use the LF conjugate of the cross entropy for meta-learning the natural gradient update.
3

---

Published as a conference paper at ICLR 2023
Meta-learning optimizers Many standard optimizers have comparable performance when appro- priately tuning a handful of static hyperparameters (Schmidt et al. 2021). Learned optimizers often outperform well-tuned standard ones by tuning larger number of hyperparameters online during training (Chen et al. 2021 Hospedales et al. 2021 Bae et al.) 2022). Different methods for learn-
ing optimizers have been proposed, including hypergradients (Mac et al. 2013 Andrychowicz
it al. 20166] Franceschi et al. 2017 Wiichrossk et al. 2017 Wu et al. 2018 ; Park & Oliva 2019]
Micaelli & Storkey 2021), reinforcement learning (Li & Malik| 2016; Bello al. 2017). evolution
strategies (Metz et al. [2099] Vicol et al. 2021), and implicit gradients (Lorraine et al. 2020 Ra-
jeswaran et al. 2019| Clarke al. 2021). ). our work, hyperparameters do not minimize the loss,
instead they minimize an auxiliary loss designed to learn the natural gradient update.
FISHER-LEGENDRE OPTIMIZATION
4.1 COMPUTATION OF THE NATURAL GRADIENT VIA THE LEGENDRE-
EAGGENDRE-FENCEEL FENCHEL CONJUGATE
We use the properties of the LF conjugate, in partieular Eq. 9 to directly learn the inverse of the (damped) FIM, and use it in the natural gradient update of Eq. 5 This is different from previous work on natural gradient, which aimed at approximating the FIM analytically and then inverting it. We prove the following:
Theorem 1. Assume that the negative log-likelihood {(0, D) log ((lo( is twice differentiable. Let y > be a small damping parameter. Define the regularized cross entropy between p( and p(D 0 +)
(0, 10 + 1101
(10)
and the function
(0, u) = argming H0, 8) _=o Then, the inverse damped Fisher information matrix exists and is equal to
(11)
(I( + + (0,0).
(12)
Proof. Here we provide a sketch of the proof, see Appendix A.2 for the full proof. Lemma proves that the regularized cross-entropy in Eq. 10/has unique minimum at = O, therefore 80, 0) O. The proof continues by expressing the damped FIM as the Hessian of the regularized cross-entropy. which done by reparameterizing Eq. [ Next, we use Eq. 9 to express the inverse damped FIM as the Hessian of the LF conjugate of the regularized cross-entropy (seen as a function of 8). From there, the theorem follows from Eq. 7
To clarify the connection with the LF conjugate, we note that Eq. 1] represents the gradient of the LF conjugate of the regularized cross-entropy, while Eq. 12] is the Hessian of the LF conjugate see Appendix [A.2 for details, and Appendix AA.3 3..33 for an informal mathematical argument that helps
understanding Theorem 1
Our goal is to compute the damped natural gradient update by solving the optimization problem in Eq. [1] and substituting the inverse damped FIM computed by equation 12 into the definition of the natural gradient step in Eq. 5 yielding
0++1 0 -7 5. (0,, ().(
(13)
Importantly, note that Eq. [] does not need to be solved for all possible pairs of 0 and u. Indeed, given the current value of parameters O,, it sufficient to compute 8, (O., u) (i) at small values u, because v, is evaluated at = 0 in Eq. 12 and (ii) along the direction u x g(O)). because vuδ, is multiplied by g(0.) in Eq. 13 such that knowing the slope of 6, (0., u) along any other direction would be irrelevant. Nevertheless, computing Eq. [ for such restricted (0. u) pairs may still not be easier than computing the FIM by standard methods. e.g. by computing Eq. [ and inverting the resulting matrix. In section we therefore propose a practical instantiation of the ideas developed in this section, which yields online algorithm with provable convergence guarantees.
4

---

Published as a conference paper at ICLR 2023
4.2 ONLINE META-LEARNING OF NATURAL GRADIENT UPDATES
In principle, Theorem D provides an exact implementation of natural gradient by solving the op- timization problem in Eq. I1 and then applying the update of Eq. 13 However, this approach is impractical due to the complexity of solving Eq. [T To make it practical, we propose learning an approximation 8, (0, A) of the true 80 u), through a set of auxilliary parameters A. The auxil- iary parameters À are updated online, during optimization, to push 8, towards solution of Eq. 11 but without requiring convergence. This is akin to meta-learning approach whereby only one or few steps are taken towards desired solution for meta- meta-parameters X, which are optimized concur- rently with parameters 0 in an inner loop (Hospedales et al., 2021). Here we choose gradient-based meta-learning updates (Finn et a (0017). but other choices are possible, e.g. implicit differentiation (Lorraine et al. 2020 Rajeswaran et al. 2019) or evolutionary strategies (Metz et al. 2019 &
Sener 2022).
For the auxiliary parameterization, we choose a linear function u,
(0, u, A) = Q(A)u,
(14)
where Q(A) is a positive definite matrix which will thus effectively estimate the inverse damped FIM (see equation [2). Appropriate choices for Q should take into account the architecture of the model, as discussed further below. Although the r.h.s. of Eq. 14 does not depend on 0 explicitly, an implicit dependence will arise from learning the parameters À in way that depends on the momentary model parameters 0. Indeed, for learning X, we perform gradient descent using Adam on the following auxiliary loss A, choice justified by Eq. [T
(, H,, (0, Q(A)u) - uu Q(Au..
(15)
In summary, we alternate between updating À to minimize the auxiliary loss in Eq. 15 and updating according to Eq. 13 to minimize the main loss
Ar+1 A AdamUpdate (VAA, (O., Ar))
(16)
0++1=0, 00 0.- ((A++1)g(0.).
(17)
where a is a learning rate for the auxiliary parameters and e is a small scalar (both are hyperpa- rameters). Note that the auxiliary loss is computed cg(0) because, argued in section 4.1 it is
sufficient to compute 5 at small values of u in the direction of g(O,). In Appendix A.9 provide an analysis of these coupled dynamics in a simple LinerrGauusie model.
We parameterize Q(X) positive definite Kronecker- factored block-diagonal matrix, with block sizes reflecting the layer structure of deep fully-connected neural networks (section AA5)). Although this is similar to parameterizations used in previous studies of natural gradient (Martens & Grosse 2015), we stress that our approach is more flexible since it learns the inverse FIM rather than ap- proximating and inverting the FIM analytically. In fact, we show in the appendix[A.6jthh alternative forms of the matrix Q, different from those used before, may provide better approximation of the inverse FIM (see Fig.
4.3 CONVERGENCE OF ONLINE NATURAL GRADIENT
In this section we prove that the update of Eq. 17 converges to minimum of the loss for the class of PL functions Dollyak-Lojasiwiicce which are generally non-convex. Charles & Papailiopoulos (018) proved that deep linear networks, which are non-convex (Saxe et 2013), are PL almost everywhere. We study deep linear networks empirically in section 5.1 We stress that the goal of this section is to prove convergence, rather than to obtain tight bounds on the convergence rate.
We provide convergence guarantees for both the true gradient g and stochastic gradients g. The- orem [ is special case of Theorem 1 in Radhakrishnan al. (2020), while Theorem is new to our knowledge. In both cases, the crucial assumption is that Q is a positive definite matrix, which holds for our chosen parameterization (see section A.5). For details on definitions and proofs, see appendix [..4]
Theorem 2. Assume the loss function C is E-smooth and p-PL. Let 0 E arg ming L(0). Assume that the eigenvalues of (xxi) are lower- and upper-bounded uniformly in time by Xmii > 0 and
5

---

Published as a conference paper at ICLR 2023
max- respectively. We have the following rate of convergence for optimization using the update rule of Eq. with 17 EAmax
- -(0)) < ((10)(1111111 J.Amiin
(2(0))-
-
(18)
2 Xmxxxx
Theorem 3.
Let the same assumptions in Theorem 2 hold. In addition, assume that E (0)
G We have the following rate for optimization using update rule 17 with np (Ammm((+4I)
- - -(0)) S
A
where A max
2 G 1 1=222 min
.((0)) c(0))
(19)
++1
4.4 DETAILS OF THE ALGORITHM AND FURTHER REMARKS
Here we detail our practical implementation of the online FishLeg algorithm presented in section also summarized in Algorithm Our code available here on GitHub
Auxiliary optimization Since H6 is evaluated on a model-sampled mini-batch, is a noisy quan- tity whose variance depends on the hyperparameter While this variance could be reduced e-g. by using an antithetic estimator (Gao & Sener 2022), we opted instead for analytically taking the small
limit of the auxiliary loss. By Taylor expanding equation 15
(use equations 23
and dropping
terms that are constant in X, we arrive at
A, u. u. A) =u a 1eINNV3, - Q(2)
(20)
The auxiliary update of Eq. thus becomes A1+1 X AdamUpdate (V VV. /gglg/ A.)
where the normalization g i8 important for continuing to learn about curvature even when gra- dients are small. In order avoid differentiating through the Hessian-vector product in Eq. 20 note that the gradient of Ā w.r.t. can be written
VAA(O, = H ()Q()))) u) V Vx(Q)))
(21)
Algorithm[[]] iin the appendix shows how to implement this efficiently using automatic differentiation tools. As side note, Eq. 21 makes clear that Q will get to approximate the inverse I(0) + 7 (which is also the Hessian of the regularized cross-entropy, see equation 24) at least in the relevant subspace occupied by = g/ g/||g| over iterations. Moreover, note that the noise H., simply adds stochasticity to the auxiliary loss but does not bias its gradient w.r.t. A. Finally, Eq. 20 reveals connection with Hessian-free optimization which we discuss Appendix A.8
Damping Practitioners of second-order optimization in deep learning have consistently found critical to apply damping when the FIM becomes near-singular. Although adaptive damping schemes exist and could be incorporated in FishLeg, here we followed Goldfarb et al. (2020) and used static damping; specifically, we used fixed y Eq. TO, treated a tuned hyperparameter.
Momentum We have found useful to use momentum as many other optimizers do (e.g. KFAC, KBFGS). In most of our experiments, implemented momentum g (as per line 16 of Algo- rithm []. For our wall-clock time results (Fig. 3). however, we applied momentum to our natural gradient estimate Q())g instead, in order preserve the low-rank structure of g each layer of the neural network. This enabled us to substantially speed up the computation of Q(A) gg on small mini-batches, but did not affect training and test errors noticeably.
Initialization of À We find useful to initialize À such that Q(Aa) = Tscaa x I, where 7JsGDm
a learning rate that known to give good results with initialization, FishLeg therefore initially behaves like SGDm. Future work could investigate smarter initialization / warm-starting schemes, e.g. starting Q(A) in an Adam- like diagonal approximation of the empirical Fisher.
With such an

---

Published as a conference paper at ICLR 2023
large data regime
small data regime
Application deep lin- ear networks. A deep linear network (20 layers of size 20 each) with Gaus- sian output likelihood is trained on a number of data samples (left: 4000; right: 40) generated by a noisy teacher in the same model class. (A) Loss eval- uated the training (solid) and test- ing set (dashed), as a function of train- ing epoch. The gray line shows the noise floor, i.e. the test loss evaluated the teacher network. Lines show mean across 10 independent experi- ments (teacher, initial conditions, etc), shadings show =1 stdev. (B) Evolu- tion of the auxiliary loss during training (black), with Fisher-matrix-vecton prod- ucts evaluated exactly according to the analytical expression given in (Bernac- chia et al. 2018). To assess how well the auxiliary optimization steps mini- mize the auxiliary loss a moving target when @ changes -, the auxiliary param- eters X are frozen every 500 iterations and subsequently used re-evaluate the auxiliary loss (colored lines). (C) Same as (A), here as function of wall-clock time. Parameters: minibatch size 40, rj 0.04, a = 0.001, 8 0.9, MSGD = 0.002, 7/Adam 0.0002.
Figure 1:
teacher SGDm FishLeg
(colid: train / dashhedd tess)
0
primary
107
105
102
audiloyy
10a
10-1
10-2
100
230
300
100
200
300
training opochs
training epochs (/100)
C
(sali:: train / dasirel: test)
primary
-2
-4
-6
60
120 clock time
[s]
5
EMPIRICAL EVALUATION
5.1 DEEP LINEAR NETWORKS
We first studied FishLeg in the context of deep linear networks, whose loss function is non-convex, pathologically curved, and for which the Fisher matrix is known analytically (Bernacchia et al.) 2018 Huh 2020). The results presented in [ were obtained with a network of 20 (linear) layers of size 20 each. We generated data by instantiating teacher network with random Gaussian weights (0, 1/n) in each layer and predictive density with mean equal to the activation of the last layer and isotropic Gaussian noise with variance of 0.001 Input samples were drawn from a standard normal distribution, and the teacher's predictive distribution was sampled accordingly to obtain output labels. We investigated the behaviour of FishLeg both in the large data regime (4000 training samples) and the small data regime (40 training samples).
In both regimes, FishLeg very rapidly drove the training loss to the minimum set by the noise (ap),
minimum which was attained by neither manually-tuned SGD-m nor Adam (Fig. A).. This is consistent with previous such comparisons in similar settings (Bernacchia al., 2018). the small data regime, Fishleg displays some overfitting but continues to compare favourably against first- order methods on test error. In wall-clock time, FishLeg was about 5 times slower than SGDm per training iteration in this case (Fig. [C), but show that significant speed up can be obtained by updating À every 10 iterations at little performance cost (see Fig. 3
We used this simple experiment to assess the effectiveness of auxiliary loss optimization during the course of training. The lower the auxiliary loss, the closer cross-entropy at g, and therefore the closer Q(A)g is from the natural gradient. We assessed how much progress was made on the auxiliary loss, relative to how would evolve if À was held constant, as 0 is being optimized (Fig. TB). This revealed two distinct phases of learning. At first, O (and
from the Legendre conjugate of the
7

---

Published as a conference paper at ICLR 2023
FACES
CURVES
MIIITT
training loss
10:
101
10
test error
10"2
10"1
10
3x
10"
10-3
40 epochs
60
150
20 epochs
40
epochs
HahLing
KFAC
KB8GS
#MSprop
+
Adam
mom-mmmm
reliablity
8.0
6.
02
63
101
variability
10
10
Figure 2: Comparison between FishLeg and other optimizers standard auto-encoder, bench- marks (batch size 100). Top: Training loss and test eтror as function of training epochs on the 3 datasets, averaged over 10 different seeds. Middle: reliability of Fishleg across runs. For each optimizer and dataset, the fraction of runs (estimated from 10 runs) that converged properly (i.e. where the loss did not run out to 'nan') is shown; error bars show +1 s.e.m. Bottom: variability (standard deviation) of the training loss across runs, averaged over epochs (discarding any epochs where the loss might have exploded). See supplementary Fig. 5 for results on batch size 1000.
therefore the FIM) changes rapidly, but À rapidly adapts to keep the auxiliary loss in check (compare black and dark purple curves) speculate that this mostly reflects adaptation the overall scale of the (inverse) FIM. Later on, as changes less rapidly, À begins to learn the more subtle geometry of the FIM, giving rise rather modest improvements on the auxiliary loss (compare black and lighter purple curves).
5.2 SECOND-ORDER OPTIMIZATION BENCHMARK
We applied FishLeg the auto-eneoders benchmarks previously used compare second-order optimization methods the details of these experiments (model architectures. datasets, etc) can be found in (Goldfarb et al., 2020), and hyperparameters specific to FishLeg are Table [ (Appendix)) To compare Fishl.eg to other optimizers, we used the code provided by Goldfarb et al. which implemented Adam, RMSprop, KFAC and KBFGS.
These autoencoder benchmarks are difficult problems on which the family of second-orded methods has been shown improve substantially over first-order optimizers (e.g. SGDm) and optimizers that exploit second-order information in diagonal form (Adam, R.Sprop).. Yet, no clear differences in performance has emerged within second-order methods. As far as training loss and test errors are concerned, results confirmed this trend: FishLeg performed similarly to KFAC and KBFGS on the FACES and MNIST datasets, although did converge within fewer iterations on the CURVES dataset (Fig. 2 top).
8

---

Published as a conference paper at ICLR 2023
0.032
SGDm KFAC Fishl
Figure 3: Wall-clock time comparisons on MNIST and FACES, with optimiz- ers all implemented in the same way on CPU (Intel Xeon Platinum 8380H @ 2.90GHz) with OpenBLAS compiled for that architecture and with OpenMP (8 threads). Within each dataset, all curves show the same num- ber of epochs to facilitate comparisons of CPU time-per-iteration. In FishLeg, the auxiliary parameters were updated only every 10 iterations, with no notice- able drop in performance but large wall- clock speedup. Similarly, KFAC's pre- conditioning matrices were inverted at each layer every 20 iterations only.
0.016
MNIST
test
0.008
0.004
10
training epochs
wall-clock time [ks]
0.8
FACES
0.4
0.2
0
10
20
30
20
40
training eoochs
wall-clock time [ks]
Interestingly, however, we found Fishl leg to be consistently more robust than other methods, espe- cially when using relatively small batch sizes. In particular, it converged more reliably over repeated runs with different random initializations (Fig. [ middle). This is perhaps due to other methods achieving their best performance in near-critical hyperparameter regime in which optimization tends to fail half of the time (these failed runs are often discarded when averaging). In contrast, FishLeg achieved similar or better performance in more stable hyperparameter regime, and did not fail a single of the 10 runs we performed. Similarly, FishLeg was also more consistent than other methods, i.e. displayed lower variance in training loss across runs (Fig. 2 bottom).
Given the heterogeneity of software systems in which the various methods were implemented (e.g. JAX PyTorch), using a unified CPU-only implementation applied to the FACES and MNIST benchmarks. This en- sured e.g. that the loss and its gradients were computed in exactly the same way across methods. Overall, one iteration of vanilla FishLeg was ~ 5 times slower than one iteration of SGDm. How- ever, we were able to bring this down only twice slower by updating every 10 iterations, which did not significantly affect performance. Combined with FishLeg's faster progress per-iteration, this meant that Fishlegg retained a significant advantage wall-clock time over SGD (Fig similar to KFAC. In practice we think that it might make sense to update À more frequently at the beginning of training, and let these updates become sparser as optimization progresses.
clean wallclock-time comparison between SGDm, KFAC and FishLeg
6 DISCUSSION
We provided general framework for approximating the natural gradient through online meta- learning of the LF conjugate of specific cross-entropy, Our framework is general: different choices can be made for how to meta-learn the LF conjugate (I). parameterize its gradient (Eq. 14] and evaluate/differentiate the auxiliary loss (Eq. 15). Beyond our specific implementation, future work will study alternative choices that may be more efficient. For example, implicit differentiation (Lor- raine et al. 2020 Rajeswaran et al.) 2019). or evolution strategies (Metz et al., 2019[Gao & Senerj 2022) may be used to meta-learn the LF conjugate. The auxiliary loss could also be evaluated with- out taking the small limit but using antithetic estimators to reduce variance (Gao & Sener] 2022)
Alternative parameterizations could be used for or Q. Indeed, preliminary results show that more expressive choices for Q yield better approximations of the inverse FIM (Appendix (A.)).
Previous work on natural gradient aimed at computing and inverting analytically an approximation to the FIM, which was done on a case-by-case basis for dense (Martens Grosse 2015) ) and convo- lutional (Grosse & Martens 2016) layers, and standard recurrent networks (Martens et al. 2018). By parameterizing the inverse FIM directly, our approach allows the user to express their assumptions about the structure of parameter precisions, which is typically easier to reason about than the struc- ture of parameter covariances. We therefore expect that FishLeg will facilitate future applications of natural gradient optimization broader range of network architectures.

---

Published as a conference paper at ICLR 2023
REFERENCES
Shun-ichi Amari. Natural Gradient Works Efficiently in Learning. Neural Computation, 10(2):251-
276, February 1998. ISSN 0899-7667, 1530-888X, doi: 10.1 10.11622889976993000117466 URL http:// www. mi tpress Journalss org/ doi/ /10.
Ehsan Amid, Rohan Anil, and Manfred Warmuth. Locoprop: Enhancing backprop via local loss optimization. In International Conference on Artificial Intelligence and Statistics, pp. 9626-9642.
PMLR, 2022.
Brandon Amos. On amortizing convex conjugates for optimal transport, 2022.
URL https:
22211
Marcin Andrychowicz, Misha Denil, Sergio Gomez, Matthew W Hoffman, David Pfau, Tom Schaul, Brendan Shillingford, and Nando De Freitas. Learning to learn by gradient descent by gradient descent. Advances neural information processing systems, 29, 2016.
Juhan Bae, Paul Vicol, J. HaoChen, and Roger Grosse. Amortized proximal optimization, 2022.
URL http:: /atp:i/aaaivvvva wwwpa/wwwwwi.oaaeeeeeoeeeooeeeee httgg/bb/222000 00089
Achraf Bahamou, Donald Goldfarb, and Yi Ren. An Adaptive Mini-Block Fisher Method for Deep Neural Networks, July 2022. URL arXiv:2202.0411 [cs].
Irwan Bello, Barret Zoph, Vijay Vasudevan, and Quoc V Le. Neural optimizer search with rein- forcement learning. In International Conference on Machine Learning, pp. 459-468. PMIR, 2017.
Frederik Benzing. Gradient Descent Neurons and its Link Approximate Second-order Optimization. In Proceedings of the 39th International Conference on Machine Learning, pp. 1817-1853. PMLR, June 2022. URL lattps://proceediiii benzing22a html
mlr press/v162/
ISSN: 2640-3498.
Alberto Bernacchia, Máté Lengyel, and Guillaume Hennequin. Exact natural gradient in deep linear networks and its application to the nonlinear case. Advances in Neural Information Processing Systems, 31, 2018.
Aleksandar Botev, Hippolyt Ritter, and David Barber: Practical Gauss-Newton optimisation for deep learning. In International Conference Machine Learning, pp. 557-565, 2017.
Stephen P. Boyd and Lieven Vandenberghe. Convex optimization. Cambridge University Press, Cambridge, UK New York, 2004. ISBN 978-0-521-83378-3,
Richard H Byrd, Gillian M Chin, Will Neveitt, and Jorge Nocedal. On the of stochastic Hessian information in optimization methods for machine learning. SIAM Journal on Oplimization, 21 (3):977-995, 2011.
Zachary Charles and Dimitris Papailiopoulos. Stability and Generalization of Learning Algorithms that Converge Global Optima. In Proceedings of the 35th International Conference on Machine Learning. pp. 745-754. PMLR, July 2018. URL httpps://proceet
mlr. ppesss/
html
ISSN: 2640-3498.
Tianlong Chen, Xiaohan Chen. Wuyang Chen, Howard Heaton, Jialin Liu, Zhangyang Wang, and Wotao Yin. Learning to Optimize: A Primer and A Benchmark. arXiv:2 12828 (cs, math, arXiv: 2103.12822
stat], July 2021. URL /etttp//arriiv..e /at.g////b/////.a/////// 12828
Sélim Chraibi, Adil Salim, Samuel Horváth, Filip Hanzely, and Peter Richtárik. Learning to Opti- mize via Dual space Preconditioning. December 2019. URL httpss///cpnnreviee..c
Forum? 2 www.kxxxcc gSYPS
Ross M Clarke, Elre T Oldewage, and José Miguel Hernández-Lobato. Scalable one-pass opti- misation of high-dimensional weight-update hyperparameters by implicit differentiation. arXiv preprint 10 10461, 2021.
10

---

Published as a conference paper at ICLR 2023
Yann N Dauphin, Razvan Pascanu, Caglar Gulcehre, Kyunghyun Cho, Surya Ganguli, and Yoshua Bengio. Identifying and attacking the saddle point problem high-dimensions non-convex op- timization. Advances in neural information processing systems, 27, 2014.
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta- weta-learning for fast adaptation of deep networks. In International conference machine learning, pp. 1 1136.13.. PMLR, 2017.
Luca Franceschi, Michele Donini, Paolo Frasconi, and Massimiliano Pontil. Forward and reverse gradient-based hyperparameter optimization. In International Conference on Machine Learning, pp. 1165-1173. PMLR, 2017.
Katelyn Gao and Ozan Sener. Generalizing Gaussian smoothing for random search. In International Conference on Machine Learning, pp. 7077-7101. PMLR, 2022.
Thomas George, César Laurent, Xavier Bouthillier, Nicolas Ballas, and Pascal Vincent. Fast ap- proximate natural gradient descent in Kronecker factored eigenbasis. Advances in Neural Infor- mation Processing Systems, 31, 2018.
Donald Goldfarb, Yi Ren, and Achraf Bahamou. Practical quasi-newton methods for training deep neural networks. Advances Neural Information Processing Systems, 33:2386 2020.
Roger Grosse and James Martens. A fameccer-facttred approximate Fisher matrix for convolution layers. International Conference on Machine Learning, pp. 573-582. PMLR, 2016.
Timothy Hospedales, Antreas Antoniou, Paul Micaclli, and Amos Storkey. Meta-learning in neural networks: A survey. IEEE transactions pattern analysis and machine intelligence, 44(9): 5149-5169, 2021.
Dongsung Huh. Curvature-corrected learning dynamics in deep neural networks. ICML, pp. 9, 2020.
Anna Kerekes, Anna Mészáros, and Ferene Huszár. Depth Without the Magic: Inductive Bias of Natural Gradient Descent. arXi::211.111522 [cs, stat], November 2021. URL http://
11544 arXiv: 2111.11542.
Alexander Korotin, Vage Egiazarian, Arip Asadulaev, Alexander Safin, and Evgeny Burnaev. Wasserstein-2 generative networks. arXiv, 2019. URL htt/ttttt:///xxiv...t org/
13882]
Frederik Kunstner, Philipp Hennig, and Lukas Balles. Limitations of the empirical fisher approx- imation for natural gradient descent. Advances in neural information processing systems, 32, 2019.
Ke Li and Jitendra Malik. Learning to Optimize. arXiv:1606. 01885 [cs, math, stat], June 2016. URL
http://bs///66..... 01885 arXiv: 1606.01885.
Jonathan Lorraine, Paul Vicol, and David Duvenaud. Optimizing millions of hyperparameters by implicit differentiation. In International Conference Artificial Intelligence and Statistics, pp- 1540-1552. PMLR, 2020.
David JC MacKay, David JC Mac Kay, et al. Information theory, inference and learning algorithums Cambridge university press, 2003.
Dougal Maclaurin, David Duvenaud, and Ryan Adams. Gradient- based hyperparameter optimiza- tion through reversible learning. International conference on machine learning, pp. 2113-2122. PMLR, 2015.
Chris J Maddison, Daniel Paulin, Yee Whye Teh, and Arnaud Doucet. Dual space preconditioning for gradient descent. SIAM Journal on Optimization, 31(1):991-1016, 2021.
Ashok Makkuva, Amirhossein Taghvaci, Sewoong Oh. and Jason Lee. Optimal transport mapping via input convex neural networks. In International Conference on Machine Learning, pp. 6672- 6681, 2020.

---

Published as a conference paper at ICLR 2023
James Martens and Roger Grosse. Optimizing neural networks with Pronecker-factored approxi- mate curvature. In International conference on machine learning, pp. 2408-2417. PMLR, 2015.
James Martens, Jimmy Ba, and Matt Johnson. Kromecker-factored curvature approximations for recurrent neural networks. In International Conference on Learning Representations, 2018.
James Martens et al. Deep learning via Hessian-free optimization. In ICML,, volume 27, pp. 735- 742, 2010.
Luke Metz, Niru Maheswaranathan, Jeremy Nixon, Daniel Freeman, and Jascha Sohl-Dickstein. Understanding and correcting pathologies in the training of learned optimizers. In Proceedings of the 36th International Conference on Machine Learning, pp. 4556-4565. PMLR, May 2019. ISSN: 2640-3498.
URL httt:p::/ppocceee////e wttppppeeeeiiin..........eeeeeee / 9a. html
ml m.t.ggs............... press
Alexander Meulemans, Francesco Carzaniga, Johan Suykens, João Sacramento, and Benjamin Grewe. A theoretical framework for target propagation. Advances in Neural Information Pro-
cessing Systems, 13:22004-20036, 2020.
Paul Micaelli and Amos Storkey, Cradient-based hyperparametter opperpaaraatteroooiiiiiiiiiiiiii optimization over long horizons. Advances in Neural Information Processing Systems, 34:10798-10800 2021.
Quan Hoang Nhan Dam, Trung Le, Tu Dinh Nguyen, Hung Bui, and Dinh Phung. Three-player Wasserstein GAN via amortised duality. In Proc. of the 28th Int. Joint Conf. on Artificial Intelli- gence (ICAI), pp. 1-11, 2019.
Eunbyung Park and Junier B Oliva. Meta-curvature. Advances in Neural Information Processing Systems, 32, 2019.
Adityanarayanan Radhakrishnan, Mikhail Belkin, and Caroline Uhler. Linear convergence of gen- eralized mirror descent with time-dependent mirrors. arXiv preprint 0857440099.05744,00 2020.
Aravind Rajeswaran, Chelsea Finn, Sham M Kakade, and Sergey Levine. Meta-learning with im- plicit gradients. Advances in neural information processing systems, 32, 2019.
C Radhakrishha Rao. Information and the accuracy attainable in the estimation of statistical param- eters. In Breakthroughs in statistics, pp. 235 247.2 Springer, 1992.
Andrew M Saxe, James McClelland, and Surya Ganguli. Exact solutions to the nonlinear dynam- ics of learning in deep linear neural networks. arXiv preprint 1312.6 2013.
Robin M. Schmidt, Frank Schneider, and Philipp Hennig. Descending through a Crowded Valley Benchmarking Deep Learning Optimizers. In Proceedings of the 38th International Conference Machine Learning, pp. 9367-9376 PMLR, July 2021. URL /ttps::/proceeeeee
mlr. www.ppeessssvii /1//s//v333///// sctp:/scciiiooe at 21a html ISSN: 2640-3498.
Saeed Soori, Bugra Can, Baourun Mu, Mert Gürbüübalaban, and Maryam Mehri Dehnavi. TEN-
GraD: Time-Efffiieet Natural Gradient Descent with Exact Fisher-Block Inversion, March 2022.
URL httt::t/tt/piiieee org /tabs///16... 03947 arXiv:2106.03947 [cs].
Valentin Thomas, Fabian Pedregosa, Bart Merriënboer, Pierre-Antoine Manzagol, Yoshua Bengio, and Nicolas Le Roux. On the interplay between noise and curvature and its effect on optimization and generalization. In International Conference on Artificial Intelligence and Statistics, pp. 3503- 3513. PMLR. 2020.
Paul Vicol, Luke Metz, and Jascha Sohl-Dickstein. Unbiased Gradient Estimation in Unrolled Computation Graphs with Persistent Evolution Strategies. In Proceedings of the 38th Interna-
tional Conference on Machine Learning, pp. 10553-10563. PMLR, July 2021. URL https: 77 prpooeedings..r ml
wttp://ggmm......//......... wwt.pppwwww...iicocooo 12a.. html ISSN: 2640-3498.
Olga Wichrowska, Niru Maheswaranathan, Matthew W. Hoffman, Sergio Gómez Colmenarejo, Misha Denil, Nando Freitas, and Jascha Sohl-Dickstein. Learned Optimizers that Scale and Generalize. In International Conference Machine Learning, pp. 3751-3760. PMLR, July 2017. URL http:://ecccceeennn....oopppeeea ISSN: 2640-3498.
mlr. pttpss//ww/wwwcc/ossskkaaa html
12

---

Published as a conference paper at ICLR 2023
Yuhuai Wu, Mengye Ren, Renjie Liao, and Roger Grosse. Understanding Short-Horizon Bias in Stochastic Oettmmitiiinttionnn arXiv:1803.0200 [cs, stat), March 2018. URL http:
/atxii..rrg/ab//1555..0222. 02021
arXiv: 1803.02021.
Royce KP Zia, Edward F Redish, and Susan R McKay. Making sense of the legendre transform. American Journal of Physics, 77(7):614-6221 2009.
13

---

Published as a conference paper at ICLR 2023
A APPENDIX
A.1 ALGORITHM
Algorithm FishLeg algorithm (online setting)
1:
function UPDATE_AUX(O g, A, Adam
2:
b normalize gradient initialize the adjoint of À to prepare for automatic differentiation reverse pass (c.f. line 9). b can exploit fast matrix-vector products without forming Q Hessian-vector product the regularized cross-entropy H (with ö taken off the auto- matic differentiation tape!) evaluated on a mini-batch different from the one used to obtain g-
g 5t g+g//lg
3:
4:
3- --Q()
5:
6:
h - www.s.eeeec..... Ress.vec.prod (fun å - HH00 6), at ô = O, along v =stop-gradient(0))
7:
d h g
8:
log the value of the auxiliary loss A adjoint of À after completion of reverse pass surrogate auxiliary loss d 0
aux_loss + (d - ğ) stop attop-gradient(0
>>
9:
10:
X, Adam_state + Audateep Ax, a, Adam.state)
a is the learning rate
11:
return aux loss, X, Adam.state
12:
13:
t t 0, initialize 0g and X
14: while not converged do
15:
C. g < value and gradient of negative log likelihood evaluated 0, on minibatch
16:
momentum Note: the following step needs not be performed every iteration wall-clock time speedups can be obtained by running this every 10 iterations, though this might depend on the problem.
- + 8)g
18:
aux aux_loss, A1+1, Adam_state +- UPDATE_AUX(0,, g, A, Awwaaaaaatteee.s O.+1 Or (
19:
20:
1+1+1
A.2
PROOF OF THEOREM
We start by stating the following Lemma, which is a modified version of Gibbs' inequality (see e.g.
Chapter 2.6 MacKay et al. 2003)
Lemma 1. For a fixed 0, the regularized cross entropy between p(D 0) and p(D|0 + 6)
(0, 8) LED + 2
(22)
has unique global minimum 8 O.
Proof of Theorem 7 We start by computing the gradient and Hessian of the regularized cross- entropy (0, 6) with respect d, computed at 0.
V8HL 0) ED- 0) Vol(o, D) + -0
(23)
HH,, 0) ED V2C(0,)) + 7I =1= =I= +
(24)
The gradient equal to the expectation of the score function, which is known be equal to zero also implied by Lemma I). The Hessian is equal to the damped FIM, as expressed by equation Note that the damped FIM positive definite and so its inverse exists.
Using property | of the LF conjugate, we express the inverse damped Fisher matrix as the Hessian of the LF conjugate of H.. We denote by H:; (0, u) the LF conjugate (., (,, 8), as a function of its second argument 6. Using the definition of LF conjugate 6 that is equal to
(0, u) = ming (0, 8) u
(25)
We denote by (0, u) the minimizer of this expression, i.e.
5., u) argmin, (4,0,5) uf
(26)
14

---

Published as a conference paper at ICLR 2023
Using the property of LF conjugate, equation 9 have that
(0,, (0,
(27)
Comparing with the expression 24 of the damped FIM, the right hand side of this equation is equal the inverse damped FIM when 5, u) is equal to zero. By Lemma 1 have that (0, and therefore
(I(0) -10-----H,000
(28)
Finally, using the properties of LF conjugate (Eq. 7) we have that (0. (,H; u) and the inverse FIM is equal to
(.. v.,,(0,0).
(29)
A.3 INFORMAL ARGUMENT FOR THEOREM
Theorem suggests that computation of the inverse damped FIM requires computing 8, (0, u) near 0. By Lemma
have that (0, near zero when u is also near zero. Under this assumption, and using equations 23 24 we may approximate the regularized cross entropy H. 5) by second order Taylor expansion in 6:
therefore may hypothesize that 5(0. u) is
-0, T6 (0,0 1 8" (I((O) +1)6 -
(30)
Minimizing this expression with respect to ô results in
( 1) (I(0) +T))
(31)
which implies the statement of the theorem, (I(0) (()=)+ -V
A.4 PROOFS OF CONVERGENCE
Definition (PL Condition). We say that a function satisfies the PL condition with parameter E R if the following holds
|VC(()) -(C(0)- L(0")), 0O
(32)
use the notation p-PL to denote the class of functions satisfying the condition with parameter
This condition implies that every stationary point a global minimum. however does not imply either uniqueness of the global minimum nor convexity.
Definition (Smoothness). We say that a function smooth with parameter following holds
C(0') < ((0) VC(O) +)+ 11 011-21 00
(33)
We use the notation E-smooth to denote the class of smooth functions with parameter &.
Proof of theorem 2
We show that the error at each iteration t + is linearly related to the error at
iteration t.
15

---

Published as a conference paper at ICLR 2023
[(0++1) - ((O.)
s -gg(0,) (O8(0))))(00)) + Sup
2 =000000('(00) (()(0))
(34)
(g.) T "Qg(O.) + {mmax
2 8(0)) (g)
(35)
711 {mmax (g()))
((OO))Qg(OO)) Qg((.)
(36)
77mmn
|g(0.)11
(37)
2
Mplmin
(C(O,) (())))
(38)
2
Huminn
(C(O:) C()*))
(39)
2fAmax
The first line is result of smoothness assumption and the update rule 17 The second line follows from the definition of Amax- The third line is only rearrangement of terms. The fourth line follows from the definition of Amin and the choice of 1) last line follows from replacing the value of [xmax
EAmus" The fifth line holds by PI. condition. The
We thus have
pdmin
- <
(C(0.)- L(())).
2xxmax
Applying this recursive relation over f, starting from C, we arrive at
Jdmin y (C(6,) - (()))) 2εAmax
((0,) - ((0)) = (1
Proof of theorem t as follows.
We show that the error each iteration + 1 is related the iteration
E [C(0.+1) ((
s E -mg((.))@@@l Qg((O)) +
T (g)())))
@(,))
(40)
2
{ max
-gg( Qg((.) TQg(()) E
1 (8) 1
(41)
2
Eni 22
G
|lminl (0.))
(42)
En 22
G2
s (C(mma( (())) +
(43)
2
The first line is a result of smoothness assumption and the update rule 17 The second line follows
from the definition of Amax- The third line follows from the upper bound assumption on the norm of gradient. The fourth line holds by PL condition.
We thus have
C(0 - L(0") < (1 71/AAmin) - C(0") + Enk 22 2 G2
2
16

---

Published as a conference paper at ICLR 2023
Recall the choice of тд uAmiu(t+1) By definition of A, we have [(0,) - L(0)) 1
A when
1+1
t 0. Using induction, we prove the same for L(0++1) L(
2
A
2 max G2
- -0041)-((6))
V (1
(44)
t
(t
+++ 1)
μ 2
min (t + 1)²
A
A
$
(45)
t+1
(t+
1)2
1
A( 1+1
(46)
(t+
11+
A
(47)
2+2
That completes the proof.
A.5 PARAMETERIZATION OF THE MATRIX Q
Consider multi-layer perceptron (MLP) neural network with L layers. The activation at of neuron i at layer is equal to
N N
df =
Σ
W W
for 1 IsiSN, No
(48)
(49)
where layer has N/ neurons and 1..... L. The symbol W denotes the weight matrix from layer - 1 to layer f, and has size N₂ x (N₂-1 + 1). This weight matrix includes bias, by setting the N₂- + activation at each layer equal to one:
NN,+1
(50)
The function can be any nonlinearity such as ReLU or Softmax in case of the last layer. The output of the neural network is defined as the activation in the last layer, a². For convenience of notation, the input to the neural network, denoted by x and of dimension No. is defined as activation at layer 0:
a 3i for sis No No+1
(51)
(52)
We structure the matrix Q as block-diagonal, each block corresponds to one layer and has the same number of rows and columns, equal Ne(Ne-1+1) For layer 1, We parameterize the corresponding block, denoted by Qi as
Q RR T.I..)
(53)
where the matrix Rs has size (N--1 + 1) x (Ne-1 1) while the matrix La has size N₂ No- Both matrices Le, R& are lower triangular. This parameterization ensures that the matrix Q is pos- itive definite. The auxiliary parameters are represented by the matrices Le. Re for all layers l = 1...., L,, for a total of _ Et=, [N&(N, + 1) + (Ne-1 1)(N,-1 + 2)) auxiliary parameters. This number is much smaller than the total number of entries of the matrix Q, which is equal to
EL No(Ne-1+1)
A.6 PRELIMINARY INVESTIGATIONS OF MORE FLEXIBLE APPROXIMATIONS OF THE INVERSE FIM
Directly parameterizing and learning the inverse FIM lends more flexibility than parameterizing and learning the FIM in an casy-to-invert form. We conducted preliminary experiments with alternative parameterizations Q(A) of the inverse FIM (i.e. beyond the one described in Appendix A.5). all constrained to afford fast Q())g products. In particular, experimented with:
17

---

Published as a conference paper at ICLR 2023
simple diagonal matrix Q (constrained to be positive definite), mostly included useful baseline
the block Kronecker used in the paper and described in Appendix A.5 known to perform much
better than diagonal matrix;
modification of the block Kronecker form that introduces full inner and outer diagonal rescal- ing: at each layer l, we took
= = @ (R) A
where Ae and B₁ are two diagonal matrices of the appropriate size. The presence of Be makes this similar to EKFAC (George et al. 2018). but A makes even more general:
a sum of block Kronecker approximations: at each layer l, we took
Q: (R R(D"" (1
R? 00 (T, (1,7)
All these approximations lend themselves to efficient Qg products (e.g. by exploiting standard prop- erties the Kronecker product).
To assess how well these approximations could approximate the inverse FIM at point in op- timization where qual-qualtty curvature information matters, we pre-trained an MLP with layer sizes [784,300 100,30, 100, 300, 784] for 200 iterations on MNIST autoencoding using SGD-with- momentum. The resulting model parameters were subsequently frozen, and the auxiliary loss was minimized convergence (asymptotic value shown here) under each of the four different parame- terizations of (Q(A) described above. We found that diagonal rescaling improved only slightly over the vanilla block Kronecker approximation. However, there was larger improvement going from the block Kronecker approximation to the sum-of-bloce Kronecker approximation indeed, the im- provement on the auxiliary loss was a sizeable fraction of the improvement going from diagonal approximation to single Kronekronee terms. The latter is known to be highly consequential for training, and so we speculate that com-oof-rrnneee approximations might improve natural gradient descent in future work.
sum of block Kron.
block Kron.
block Kron.
diag.
with diag.
auxilarry loss
0.008
-00012
0.006
-0.02
Figure 4: Comparison of various forms of Q(A). See text in Appendix A.6 for details.
A.7 FISHLEG COMPLEXITY
In this section, we provide an analysis of the complexity of FishLeg for a deep fully connected network with L layers of size N each, processing data in mini-batches of size K. We assume that Q has the block-dies diigonal Kronecker form of Eq. [3 The complexity of the forward pass is N2), and with automatic differentiation the backward pass has the same complexity. At each layer, the gradient of the loss w.r.t. the weight matrix has rank puting the Qg product required for the FishLeg update step (Eq. 17) using Kronecker identities has complexity O(LKN' or (LL'3) whichever is smallest. Finally, the inner update step (Eq. 16) is dominated by (i) the Qğ product (line 4 of Algorithm T) and (ii) the Hessian-vector product (line 6) which has the same O OLLK22) complexity as the forward pass. Altogether, FishLeg has complexity O2)
min(N, K), such that com-
In contrast, KFAC has complexity OLL?2 max(K, K, N)), as the 3 cost of inverting the Kronecker factors is unavoidable when the batch size is small.
18

---

Published as a conference paper at ICLR 2023
A.8 FISHLEG AS AMORTIZATION OF CG STEPS IN HESSIAN-FREE OPTIMIZATION
FishLeg can be thought as a way of gradually amortizing the conjugate gradients (CG)-based inner loop in Hessian-free optimization. Looking back Eq. 20 one might wonder: why not directly optimize over the product v = Q()). instead of optimizing over X? Treating v as free parameters, this would entail minimizing fv (I()) 2fv V g, which in fact exactly what Hessian- free optimization does using CG Byrd et al. 2011, Martens et al. 2010; though I is sometimes replaced by the Gauss-Newton approximation to the Hessian). Although each step of CG has a cost comparable to the computation of g. in practice several iterations are required which tends to remove any advantage on wallclock time. By learning Q(A) instead of Q())g. FishLeg learns to amortize those CG steps over progressively growing subspace of noisy gradients.
A.9 ANALYTICAL RESULTS IN SIMPLE LANEAR-GAUSSIA SYSTEM
Here, we provide an analytical derivation of the behaviour of FishLeg in a simple one-layer linear network with Gaussian likelihood, and draw some insights. Consider regression model of the form p(y|=) = N Nyy 8T xr 1), and a teacher in the same model class with 0 = 0. Let the input distribution be x (0, Σ). The log likelihood in the limit of large data batches sampled from the teacher network is given by {(O) 1 00 For analytical convenience, we will work in the
continuous time limit. In this limit, the standard gradient flow is given by
d0 CO
(54)
This flow is easily seen to converge to the correct solution (the teacher parameter O = 0). but to do so slowly along the eigenvectors of Σ associated with small eigenvalues. Indeed, writing 0 Ua where the columns of U are the orthonormal eigenvectors of Σ, Eq. 54 implies (, = where X
the jth eigenvalue of Σ. Thus, when V is poorly conditioned, convergence is very slow in its bottom subspace. The question arises: how well does FishLeg mitigate this problem?
For this simple model, the Fisher matrix is I Σ, and the cross-entropy of Eq. (unreguularii as TTTE..
is not necessary here) is given by H(., 5) 1 E8. To simplify our analytical derivations, instead of using Adam for optimizing the auxiliary loss as we do in our experiments, here we consider simple gradient descent in continuous time:
dQ dt
Σ0
AVQ 0,
(55)
|ΣA|
which is evaluated at u = g/ where و = 00 is the momentary gradient of the primary loss (the model's 's negative log likelihood). Expanding the auxiliary loss of Eq. 20 obtain
dQ
(1o20- - 2
OT
(56)
dt |0
2
Trace ("020- 2) Σ
V
(57)
Letting x = QΣO, and after some algebra, the auxiliary flow of Q in Eq. 57 implics the following flow for 2:
dz = aZ - 2).
(58)
dt
With the same notation, the primary FishLeg flow
d0
Q-0 =
(59)
di
Thus, in this simple One can already see that, assuming separation of timescales with a >>>>>>> 1 such that 0 changes much more slowly than Q (i.e. than 2), then the FishLeg flow becomes d0/dt = -0 which implies exponential decay of the loss irrespective of Σ and indeed, for this model it is exactly natural gradient descent. To drive the point home, we rewrite these coupled ODEs in the orthonormal eigenbasis of = UA which yields
setup, FishLeg boils down to pair of coupled linear ODEs.
d
0
0 -1 -at )
(
0 2
dt
2
=
aA
(60)
19

---

Published as a conference paper at ICLR 2023
where we have defined 0 U0 and Už, and A is diagonal matrix containing the eigenvalues {Ar } of the input covariance. The eigenvalues {5t} of this state matrix are then easily shown to satisfy
aA + Bc) = -3
(61)
assuming the correct ordering of the 3, w.r.t. the X s. For each X as a grows large (i.e. good separation of timescales between 0 and Q), there only two ways for 3, to satisfy Eq. 61 Either 3, remains finite )).)), implying that + 3,) must be O(1aa), which in turn implies 3. + -1. Or 33 grows large and real, in which case (1 Be) must be negative because -3, is, and more specifically 33 must grow as -O(a). These qualitative arguments can be confirmed by writing down the closed-form solution of the quadratic Eq. [1] In summary, with sufficient separation of timescales between the primary and auxiliary parameter updates, FishLeg converges uniformly in all directions in parameter space, with uniform dominant timescale that does not depend the condition number of Σ. This is contrast with standard gradient descent which is slowed down by small negative eigenvalues in the spectrum of Σ.
Note that in the above derivations, the transition from Eq 57 to Eq. 588 made the implicit assumption that Q was unconstrained in particular, it could lose symmetry. In this case, the derivation shows that unless the auxiliary flow is substantially faster than the primary flow, FishLeg can suffer from oscillations/ poor damping especially in the bottom subspace of (c.f. solutions of Eq, [6] for small a). In practice however, one would normally write Q = LL with positivity constraint on the diagonal of L, and formulated the auxiliary flow in terms dL/dtt instead. This would guarantee Q > 0 throughout optimization. Although analytical derivations become more tedious in this case, we speculate based on numerical simulations that this parameterization mitigates the problem of oscillatory optimization dynamics.
20

---

Published as a conference paper at ICLR 2023
FACES
CURVES
MNIST
100
1000
100
1000
100
1000
Damping 7
1.0
le-3
le-2
1.0
3e-1
3e-2
5e-2
5e-2
le-2
le-1
7e-2
5e-2
le-4
lc-4
le-5
5e-4
lc-4
le-4
1lsGDm
1e-2
le-2
3e-2
Te-2
1e-2
1e-3
Table I:
Optimal hyperparameter values for FishLeg, identified as the result of a grid search over the space shown Table 2
These hyperparameters were chosen minimise the training loss.
FACES
CURVES
MNIST
100
1000
100
1000
100
TO00
Damping
1e-2, 1e-1,
1e-3, 1e-2,
le-4, 1e-3,
le-4, 1e-3, le-2, le-1, 1.0
le-4, le-2,
le-4, 1e-2,
1.0, 10, 100
le-1, 1.0,
3e-2, le-2,
le-1, 3e-1,
3e-2, 1.0, 100
10, 100
3e-1, 1.0.
1.0, 100
10
"
le-3, 5e-3, le-2, 5e-2
5e-4, Se-3,
le-3, Se-3,
1e-3, le-2,
le-3, Se-3,
le-3, Se-3,
le-3, le-2, 5e-2
le-2, 5e-2,
2e-2, 5e-2, le-1
le-2, 5e-2,
le-2, 2e-2,
7e-2, le-1,
7e-2, le-1,
5e-2, 7c-2,
2e-1, 5c-1
2e-1,
lc-1, 5c-1
a
5e-5, 8e-5, le-4, 5e-4,
5e-5, Ic-4, 5e-4, le-3,
le-5, 5e-5,
le-5, Ic-4,
Ie-5, 5e-5,
5e-5, Ic-4,
le-4, 5e-4,
5e-4, le-3,
le-4, 5e-4,
5e-4, le-3
le-3, 5e-3
le-2, le-l
le-3, 5e-3
le-2
le-3, 5e-3
Table 2: Entire space of hyperparameters explored to optimize the training loss for each task. All combinations were explored, in a grid fashion, and each combination was run three times with dif- ferent seeds. Finally, the combination of hyperparameters with the lowest training loss was selected.
21

---

Published as a conference paper at ICLR 2023
FACES
CURVES
MNIST
training loss
107
10a
10
10
test error
60-1
10
30-10-1
10"2
10"1
200
300
400
800
100 epochs
300
epochs
epochs
RihLeeg
+
RMSprop
Adam
momentum
relabiitty
$x32
Variability
4x32
2x30
Figure 5: Same as Fig. 2 with a batch size of 1000.
22


Reviews:
[{"review_id": "qZgxu-7RKV", "reviewer": "Reviewer_ACHH", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes an approximation to the natural gradient update by using Legendre-Fenchel duality to estimate the inverse Hessian with the convex conjugate of the entropy, which is summarized in Theorem 1. Section 4.2 goes on to parameterize a model $Q(\\lambda)$ to predict the solution to the conjugate in (11). The method is experimentally evaluated on deep linear networks (Section 5.1) and the auto-encoding benchmarks from Goldfarb et al., 2020.", "summary_of_the_review": "I recommend to accept the paper as it's a reasonable and well-executed contribution. I would be willing to raise my score after a discussion on not having comparisons to other natural gradient methods in some of the experiments.", "strength_and_weaknesses": "Strengths\n+ Using duality to estimate the natural gradient update is an appealing idea and theorem 1 and the proof are great contributions\n+ The results in Section 5.2 on the settings from Goldfarb et al. are convincingly executed and attain especially nice reliability and variability\n\nWeaknesses\n+ The comparisons on the deep linear networks benchmark in Figure 1 and on the wall-clock times in Figure 3 do not consider other natural gradient methods as baselines, only SGD with momentum and Adam\n+ The top part of Figure 2 shows that FishLeg does not significantly improve upon the overall training loss/test error of other methods.\n+ The approximation $Q(\\lambda)$ may not be very accurate, especially at the beginning of training. Can bad approximations to it cause bad updates to be performed? It could be interesting to note that sub-optimal predictions of $Q(\\lambda)$ could be improved by either running more updates to it or having an explicit fine-tuning phase to find a better conjugate.\n+ $Q(\\lambda)$ is the same shape as the inverse Fisher matrix and is thus an extremely high-dimensional prediction problem. The full (or Kronecker-factored) matrix is too memory intensive to compute for large models, so it seems challenging and computationally intensive to predict it for large models.\n+ How strong are the assumptions of Theorem 1?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "etpsvVF46oa", "reviewer": "Reviewer_QPAM", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In this work, the authors propose an approximated natural-gradient descent for NN via the Legendre transformation. \nThe authors show that the proposed methods performs similarly as K-FAC and its variants  in some medium scale problems (FACES and MNIST).", "summary_of_the_review": "The theoretical results are weak.\n* There is an implicit and key assumption in Theorem 1. \n* Theorem 2 and Theorem 3 are weak/standard due to the direct assumptions on Q, which bypasses the convergence analysis of Eq 16.\n\n\nWithout providing additional results, in the current form, the empirical results are also weak.\nI wonder if the one-step Adam update shown in Eq 16 is enough for more challenging problems. \nThe meta-learning approach is very similar to the auto-encoder task considered in the paper. In this case, the one-step Adam update may be good enough.\nMy question is whether the proposed method such as the one-step Adam update works well on other tasks such as CNN.\n\n\n \n\n", "strength_and_weaknesses": "Strength:\n* Re-formulation of natural-gradient descent via the Legendre transformation.\n* Surrogate approximation Q (Sec 4.2) to handle the positive-definite constraint in the Fisher information matrix. \n* Some theoretical results of the proposed method.\n\nWeakness:\n---\n* Theorem 2 and Theorem 3 are weak/standard since the authors make **direct** assumptions of the matrix Q. Note that Q is an approximation of the Fisher information matrix. Thus, the authors implicitly make assumptions about the Fisher information matrix.\nMoreover, the impact of Eq 16 is unknown since the assumptions of the matrix Q bypass the convergence analysis of Eq 16 as shown in the proof of Thm 2 and 3. \n\n---\n* There is an implicit and key assumption in Theorem 1. Without addressing this issue, the theoretical results are pretty useless.\nMy main question is when/why  $- E_{p(\\mathcal{D})}[ \\nabla_\\theta^2 \\log p(\\mathcal{D|\\theta})] $ is positive-definite in NN cases, which often implies the NN is not over-parametrized. If $- E_{p(\\mathcal{D})}[ \\nabla_\\theta^2 \\log p(\\mathcal{D|\\theta})] $ is positive-definite, why is damping needed?  The authors should include a NN example to justify this assumption. \n\nAs mentioned in Eq (8), the H function must be **strictly convex** w.r.t. $\\delta$.\nAs shown in Lemma 1 (in the appendix), the assumption $p(\\mathcal{D} | \\theta) = p(\\mathcal{D} | \\theta+\\delta) $ iff $\\delta=0$, implies that Eq 24 holds. In other words, $- E_{p(\\mathcal{D})}[ \\nabla_\\theta^2 \\log p(\\mathcal{D|\\theta})] $ must be **positive-definite**.  This is a strong assumption for NN problems. \n\nThere are two types of Fisher estimators when it comes to approximating the expectation via (data) samples. \n1. $-E_{p(\\mathcal{D})}[ \\nabla_\\theta^2 \\log p(\\mathcal{D}|\\theta)]$  (As shown in Eq 2, this does not guarantee to be positive semi-definite. This work exploits this result by making this assumption in Thm 1:  $p(\\mathcal{D} | \\theta) = p(\\mathcal{D} | \\theta+\\delta) $ iff $\\delta=0$.  )\n2. $E_{p(\\mathcal{D})}[ \\nabla_\\theta  \\log p(\\mathcal{D}|\\theta)  \\nabla_\\theta^T  \\log p(\\mathcal{D}|\\theta)   ]$  (As shown in Eq 1, this is  always positive semi-definite. This result has been used in many existing methods such as KFAC)\n\n\n---\n* To avoid directly addressing the positive-definite assumption in Thm 1, the authors instead introduce a  positive-definite surrogate matrix Q. \nThis trick turns the one-step NGD into a two-step update (Eq 16-17). \nIn other words, the iteration cost can be higher compared to KFAC.\nThe authors should discuss the additional cost of this extra step. \nFigure 2 should be plotted in terms of the wall clock time instead of the number of epochs.\nSince the authors use a Kronecker structure in Q, a proper baseline in all experiments should be KFAC. Please report the wall clock time instead of the number of epochs. \nThe additional cost could be high if a very deep NN is used.\n\n---\n* Why is the one-step Adam update in Eq 16  good enough to approximate Eq 11? In optimization, we usually have to use a double-loop update (e.g., taking a few Adam steps) since the one-step Adam update is in general not good enough. Does taking a few more Adam steps in Eq 16 improve the performance?   The authors should discuss this point. \n \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "BKSbEeyXcu", "reviewer": "Reviewer_q97H", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a new optimization algorithm for deep neural networks that incorporates aspects of curvature information via meta-learning. In particular, authors model the inverse of the Fisher information matrix that appears in natural gradient descent via a set of additional parameters that are optimized jointly in an online manner. Authors empirically demonstrate that the proposed method outperforms first order optimization methods and is competitive with other higher order methods on an autoencoder benchmark. Authors also provide a proof of convergence for functions that satisfy the PL condition.", "summary_of_the_review": "Authors consider an optimization method inspired by natural gradient descent which is based on meta-learning an inverse of the Fisher information matrix that can be optimized online during training. The paper reads well and is understandable even for someone outside of the optimization algorithms subfield.\n\nTo be more suitable for a larger audience I think the paper would benefit from an additional paragraph discussing how this method could fit into common use cases (i.e. large parameter regimes) and if there are model-specific scaling expectations in terms of runtime (compared to SGDm).", "strength_and_weaknesses": "Strengths:\n* Paper present empirical verifications on model and real benchmarks\n* Proposed method features convergence guarantees\n* Claims are clearly stated and accompanied by proofs\n\nWeaknesses:\n* Wall clock time is not compared directly with other second order approximations (KFAC, etc)\n* Limited guidance provided on the choices of parameterization of the inverse fisher information matrix. (might be common knowledge in the field)\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "8anKelWLeR-", "reviewer": "Reviewer_qrGz", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors propose a general method to approximate natural gradient updates in a deep-learning context. The natural gradient is a way of second-order optimization. They apply the Legendre-Fenchel duality to learn a direct and efficiently evaluated model for the product of the inverse Fisher with any vector. Under some assumptions, they prove that their approximate natural gradient descent can converge to a local minimum including a global minimum. Several numerical experiments are shown to demonstrate the effectiveness of the algorithm. ", "summary_of_the_review": "The paper is written well with clear mathematics and many numerical experiments. However, the authors still require some direct analytical examples in Gaussian distributions to demonstrate their ideas. Much important literature is missed in the context. \n", "strength_and_weaknesses": "Strength: The usage of Legendre and the auxiliary parameters plus meta-learning is an interesting idea. They have the ability to compute the inverse of the Fisher information matrix efficiently. \n\nWeakness: \n\n1. The authors clearly miss many important results on the approximation of the information matrix, using the Legendre duality and auxiliary variable. \n\nAffine Natural Proximal Learning. Wasserstein Proximal of GANs, Wasserstein natural gradient, etc. \n\n2. Does the authors have some analytical examples to demonstrate the effectiveness of algorithms? Some examples in Gaussian distributions could be useful.  ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-25%