Depth Without the Magic: Inductive Bias of Natural Gradient Descent
Authors: Anna Kerekes
Anna Mészáros
Ferenc Huszár
Venue: ICLR 2022 Submitted (2022)

Abstract: In gradient descent, changing how we parametrize the model can lead to drastically different optimization trajectories, giving rise a surprising range of meaningful inductive biases: identifying sparse classifiers or reconstructing low-rank matrices without explicit regularization. This implicit regularization has been hypothesised to be a contributing factor to good generalization in deep learning. However, natural gradient descent is approximately invariant to reparameterization, it always follows the same trajectory and finds the same optimum. The question naturally arises: What happens if we eliminate the role of parameterization, which solution will be found, what new properties occur?  We characterize the behaviour of natural gradient flow in deep linear networks for separable classification under logistic loss and deep matrix factorization. Some of our findings extend to nonlinear neural networks with sufficient but finite over-parametrization. We demonstrate that there exist learning problems where natural gradient descent fails to generalize, while gradient descent with the right architecture peforms well.

Under review as a conference paper at ICLR 2022
DEPTH WITHOUT THE MAGIC: INDUCTIVE BIAS OF NATURAL GRADIENT DESCENT
Anonymous authors Paper under double-blind review
ABSTRACT
In gradient descent, changing how we parametrize the model can lead to drasti- cally different optimization trajectories, giving rise a surprising range of mean- ingful inductive biases: identifying sparse classifiers reconstructing low-rank matrices without explicit regularization. This implicit regularization has been hy- pothesised to be contributing factor good generalization in deep learning. However, natural gradient descent is approximately invariant to reparameteriza- tion, it always follows the same trajectory and finds the same optimum. The question naturally arises: What happens if we eliminate the role of parameteri- zation, which solution will be found, what new properties occur? We characterize the behaviour of natural gradient flow in deep linear networks for separable clas- sification under logistic loss and deep matrix factorization. Some of our findings extend to nonlinear neural networks with sufficient but finite wver-parametrization We demonstrate that there exist learning problems where natural gradient descent fails generalize, while gradient descent with the right architecture peforms well.
INTRODUCTION
There is plenty of empirical evidence that the choice of network architecture is important determinant of the success of deep learning (He et al, 2013] Vaswani et al. 2017). The empirical observations are now supported by theoretical work into the role that aarameter-to-hypolleee
Mi
H
HININESS MAPRIS
mapping plays in deter- mining inductive biases of gradient-based learning. Unregularized gradient descent can efficiently find low-rank solutions in matrix completion problems Arora al., 2019), sparse solutions in separable classification (Gunasekar et al. 2018) compressed sensing /Vaškevičius et al. 2019). Valle-Pérez al. (2018) studied deep neural networks and found evi- mapping is bi- ased towards simpler functions measured by Kol- mogorov complexity. Taken together, these observa- tions and findings have lead the community to hy- pothesize that
N
Figure 1: Illustration of parametrization
dependence of EGD and independence of NGD. Consider two parameter spaces (Wi, W2) and two optimization trajectories in each: one EGD, one NGD. If map these into the hypothesis space (H) then EGD finds different optima, but NGD finds the same.
dence that the parameter-hypothees
The parameter-to--hypotees mapping influences the inductive biases of gradient-based learning and may play an important role in generalization.
In parallel to improving architectures, considerable research was done to improve optimization al- gorithms for deep learning, with a focus on faster convergence and robustness to hyperparameters. Among the most advanced optimization methods are natural gradient descent (NGD) techniques. An intuitive motivation for NGD is that improves convergence by implicitly lifting the problem from parameter-space, where the loss is non-convex and poorly behaved to the Riemannian manifold
The mapping hetween the parameter space and the of hypotheses as Figure

---

Under review as a conference paper at ICLR 2022
of hypotheses, where the loss is better behaved. From the perspective of inductive biases, the most interesting aspect of NGD is its approximate invariance to reparametrization.
Natural gradient descent eliminates the effect of parameter- to toappotee-tt--yyoohessss mapping.
These two observations invite questions about the nature of inductive biases in NGD as well as the in generalization. The first, practical, implication is as follows:
role of cewammtttriaaio-ddeeeeeee the parameter-te to-tto--hy to-hypothesis mapping really does play an important role in generalization, then eliminating its influence on the optimization path may be undesirable, and consequently the pursuit of implementing exact NGD in deep architectures may be counterproductive. Secondly, studying the behaviour of NGD in various models and tasks may give of parametrization, and could perhaps offer a way to experimentally or theoretically test hypotheses.
insights about the importance
In this paper we study the inductive bias of natural gradient descent in deep linear models. These models are particularly suited for our analysis because (a) efficient algorithms exist to calculate exact natural gradients which otherwise computationally intractable and (b) the inductive biases of Euclidean gradient descent (EGD) in these models have been thoroughly studied and understood.
We make the following contributions:
In linear classification, we show that NGF is invariant under invertible transformations of data (Theorems 2 and consequence it cannot recover the Lp large margin solutions that EGD tends to converge to.
We further show that (in case of separable classification) when the number of parameters exceeds the number of datapoints, NGF interpolates training labels in a way similar to ordinary least squares or ridgeless regression (Theorems 3
We demonstrate experimentally that there exist learning problems where NGD can not reach good generalization performance, while EGD with the right architecture can succeed. To perform experiments, we extended the work of |Bernacchia et al. (2018) to derive effi- cient and numerically stable algorithms for calculating exact natural gradients in diagonal networks (Gunasekar et al.] 2018) and deep matrix factorization (Arora et al. (019)..
Before stating our main theoretical and experimental results review some relevant background on parametrizaation-deeeedd implicit regularization and natural gradients.
BACKGROUND
2.1 SEPARABLE CLASSIFICATION WITH DEEP LINEAR MODELS
In this article we consider binary classification datasets {(xn,yn);n) 1...., NN separable by homogeneous linear classifier with a positive margin ( e. 3 s.t. ynx,,9" 2 Vn). (We use the notation X = (x1 ... xN) ()))) ). In such situation /3 is not unique and there may be many separating hyperplanes which all achieve training loss it is up to the inductive biases of the learning algo- rithm to select one. [Soudry et al. (2017) studied the dynamics of unregularized Fuclidean gradient descent on logistic loss and found that the iterate (t) converges to the well-known & large margin classifier in direction, that is
lim
(( [8(()] Bi,1
07 where Br, arg min |812 s.t. 3 2
Vn.
BERD
Importantly, Gunasekar al, (0018) later showed that this behaviour changes if the gradient descent is performed on a different parametrization. In this paper we will focus on L-layer linear diagonal networks (Gunasekar et al. 2018), where W1 3 W2 3 ... 2 WL. using @ to denote elemen- twise product. When we adjust parameters Wi...., WL through Euclidean gradient descent, (3())
converges to the lg large margin separator defined as
lim;-+o
(3t) [3()]
Pase where Brion = arg min |in||||| s.t. yx [ Ging!
B 2 1 Vn.
BER
remarkable consequence of this that unregularized gradient descent can find sparse classifiers, without any form of explicit regularization. In fact, this inductive bias is even more sparsity-seeking than the typically used l regularization (see e. g. Kohh et al. 2007]] Tibshirani 1996). Figure illustrates this behaviour in 2D example.
2

---

Under review as a conference paper at ICLR 2022
At direct perametiization, EGD
BiL diagonal network, EGD
C: direct parametiization, NGD
DiL diagonal network, NGD
Implicit regularization of EGD and NGD on logistic loss in separable classification. EGD reaches different optima depending parametrization: fully connected networks reach & large margin (A), while L-layer linear diagonal networks reach the & 1 -large margin solution which favours sparsity (B), while L-layer linear diagonal networks reach the Lg -large m. NGD converges to the same optimum irrespective of the parametrization (C, D).
Figure 2:
2.2 MATRIX COMPLETION VIA DEEP MATRIX FACTORIZATION
cor.8
Nor,
MCD.
The task of matrix completion involves recovering an unknown matrix 3 PxD from randomly cho- sen subset of observed entrie The problem is clearly underdefined: there are infinitely many matrices that match the observed entries. It is common to make addi- tional assumptions about 3 most commonly that that it has low rank, under which it becomes identifiable.
One approach matrix completion under the low-rank assumption is based on explicit regularization (e.g. nu- clear norm) which leads a convex optimization prob- lem. Another common approach is matrix factorization using an underparametrized representation 3 UV where the sizes of U IR PxR and V IR TtX are stricted to ensure Ios rank at most Learning then proceeds by minimizing the non-convex mean-squared reconstruction error in U, V via gradient descent.
Figure 3: Illustration the neural tangent
Remarkably, Gunasekar et al. (2017) showed that the gradient-based matrix factorization method tends in the over- parametrized setting, i.e. when B = Wi W2 where W, and W22 are full square matrices, without any ex- plicit regularization. This was later extended by Arora al. (2019), who studied the deep matrix product parametrization of the form 3 = W W. ... WL. Arora ct al. (2019) ran experiments for different matrix com- pletion tasks varying initialization, depth and number of observations and compared them to minimum nuclear norm solution. When the number of observed entries large gradient descent in deep matrix factorization models tended the minimum nuclear norm solution. However, in the interesting case of fewer observed en- tries, the behaviour was different. Gradient descent pre- ferred solutions with lower effective rank at the expense of higher nuclear norm. From the evolution of the singular values of B they also concluded that the implicit regularization is towards low rank that becomes stronger as depth grows.
kernel in EGF, EGD, NGF and NGD (lefi to right) in matrix factorization models of different depth (top to bottom). The al- gorithms take gradient steps to minimise the squared error on a single observation at the middle of the matrix. Each panel shows how entries of the full 11 x I1 matrix move from random initial state. When > 2, Euclidean gradient meth- ods also move entries where there is no observation enabling implicit regulariza- tion towards low-rank solutions. By trast, and due to invariance, natural gradi- methods move only the single entry to match the observation.
converge low-rank solutions
to simplify presentation assume the matrices are square, but arguments hold more generally.
3

---

Under review as a conference paper at ICLR 2022
2.3 NATURAL GRADIENT DESCENT
In the next section we briefly introduce some notation and key properties of natural gradient descent (NGD, Amari 1997 Pascanu & Bengio 2013). Intuitively, one can think of NGD as a gradient descent method, but not in the Euclidean space (with the Euclidean metric) of parameters, but instead on the Riemannian manifold of probabilistic models the parameters define (equipped with a different metric). More specifically, let's 's say that the parameter of interest is 6, where 0 defines a probabilistic model p(y|>,, x, 0). We assume that we wish to minimize the log loss under this model, i. e. [(0, x. y)
- llg ply) y x, 0) and L()) = Σn 1(0, Xn, Bn). Then, NGD is usually defined as
A(t + 1) (()) - 1 Vo))) where F(0) Ex Ex(Brix (VC()))) [(+)]]
(1)
(2)
is the average Fisher information matrix and is the step size. In the above definition, E is taken over the distribution specified by 0, but distribution with respect which the expectation Ex is calculated can be arbitrarily chosen. In this article we use the empirical distribution of training
data, though other choices are possible (Pascanu Bengio 2013). We will also consider natural gradient flow (NGF) the continuous limit of NGD, analogously defined as
= - (=-F-(0)
We also note, that F(0) is not generally invertible, and indeed it will not be in some of the cases we will consider. Therefore, it is more correct to define NGF as any trajectory O, which satisfies
F(0)Ø
VoL(O).
(4)
The natural gradient direction is thus only unique within the eigenspace of F(0). Of all natural gradient directions, one common choice is to use the Moore-Penrose pseudoinverse of F:
i = F* (O)V
(5)
We have seen how in EGD, different parametrization of the same problem leads to drastically dif- ferent trajectories and optima. However, NGD with infinitesimally small learning rate (i. NGF) always follows the same trajectory in model-space and this finds the same optimum, irrespective of how it is parametrized, provided that the parametrization is smooth and locally invertible. Below we formally state this property AAmai 1997). alongside a short proof for illustration.
Statement (Invariance of NGF under reparametrization).. Let w and 0 be two parameter vectors related by the mapping 0 = P(w) and consider natural gradient flow in w. Assume that (1) the 00 and (2) F(O,) are both full rank for all L. If w. follows natural gradient flow Jacobian J = dw,
starting from Wo then O. = follows NGF, e. it solves O, = F(O.)++ Vo, CX,,(X L(X,0)). 0t).
NATURAL GRADIENTS UNDER LOGISTIC Loss ON SEPARABLE DATA
We have seen in Section 2.1 that when trained separable data with the logistic loss EGD tends to converge to large margin classifiers. To illustrate how NGD differs, we first prove an invariance property which, as we will see, rules out large margin behaviour. We state this property separately when N < D and when N > D in the theorems that follow. We denote the number of data points with N and the number of input features with D.
Theorem 1. Let's assume, that N < D, X is full rank and A is invertible D x D matrix. Let 3, = 3,(X, y) be the trajectory of NGF and B, = -3,XAA .y) (the trajectory of NGF on data XAT). ). Then XB XA B' (with the assumption that (3 and g have equivalent initial conditions).
XAT B and prove that S; =s(.. The full proof Proof sketch. We use the notation s = XB and s'
can be found in Appendix C.I
Theorem 2. Let (X, be the trujectory of NGF and let A be D D invertible transfor- mation.
If N 2 D. X has full rank and we consider NGF on the transformed data XAT, then A ( .y) = (,(X.)) (with the assumption that (3 and 3 have equivalent initial condi- tions).
Remark. When N 2 D and X is full rank, the size of F(B) is X D and its rank is D, therefore the Fisher information matrix of ( is invertible.
4

---

Under review as a conference paper at ICLR 2022
Proof sketch. First let's say B (,(XAT, y) and v" = =3 A. Then prove the following:
Vor Llunf Ax,) = AV oVnn xn) and F( AF(D)A
(6)
Hence we get:
3 3=
and è = =
So if v and B have the same initialization, then 8,- = By. Full proof can be found in Appendix C.2
Conclusion. Let ui (X. denote the trajectory of 3 which is the linear function 3. x evaluated at each of the datapoints Xn. Then uxAAA,, y) 2n y).
Proof.
w.(XAT = XA 3,(XA) y) = (
One special case of this invariance property is invariance to scaling the dimensions of input data (when A is diagonal). Imagine we scale any dimension by a constant a, NGF counteracts it by scaling the corresponding coordinate of by implicit regularization of NGD as minimizing non-data-dependent norms of B. In particular, rules out the bp mrrge-margnnaa behaviour have seen in EGD.
We see now why this rules out characterising
Remark. Let A be D x D invertible transformation and let B yX.y) be the Eg large margin solu- argmin || subject to yr, x, 2 1 Vn. Then the lg large margin classifier does not have the invariance property, namely there exists a dataset (X, y) and transformation A such that T (3 y) # (X) We include a proof by counterexample in Appendix [
tion, i.e. (X.
Having ruled out norm- baandd implicit regularization, it's natural to consider other statistical methods that exhibit invariance under invertible data transformations. One candidate is ridge-less regression or ordinary least squares (OLS), whose parameter given by the formula BOLS = (X x)- y- As it turns out, the connection between NGD in linear regression and the OLS estimate run deeper than sharing this invariance property.
Theorem 3. N < D and X is full rank, if parameters Br of linear model follow natural gradient flow under logistic loss, the logits St X3, follow an asymptotically linear trajectory with direction vector y.
Remark. The Fisher information matrix w.r.t. is F(B) X D(g)X, where D(3) diagonal with positive elements the diagonal. We see, that Fank(F) rank(X) N, so F is singular, thus several NGF paths are possible. When rank(X) = N, B has - N degrees of freedom and we did describe 33 on N dimensions. That's why we consider s instead of B.
This Theorem follows from the more general Theorem 4 which we will state later.
Informally, when we have more parameters than datapoints, NGD discovers a solution that interpo- lates the training labels (encoded as -Is and +1s) perfectly just like ordinary least squares does in this case. Furthermore, one uses the Moore-Penrose pseudoinverse to calculate the descent direction, e.e Eqn. (5), then B, converges in direction to the OLS parameter.
In general cases, OLS interpolation and lutions in classification tasks. While the LM solution is typically a linear combination of small subset of training data (the support vectors), in OLS all datapoints are support vectors. As shown in (Hsu et al. 2020), under some conditions this difference disappears in the highly overparametrised regime- when D N log N. An implication of Theorem 3is is that this phenomenon, known as sup- port vector proliferation, occurs in NGF when D > N. Thus there a regime where NGF and EGF find qualitatively different classifiers, with different generalisation properties (Hsu et al. 2020).
(LM) methods find qualitatively different so-
Theorem provided useful in the context of linear models but it turns out is relatively straightfor- ward to extend this to a result which holds for non-lineat overparametrized models as well.
Theorem 4. Let w E RR, P> N be the parameters of a classifier with logits s(X; w) R
If w, follows natural gradient flow on the logistic loss with labels y and the Jacobian Jj full rank, then S; grows asymptotically linearly with direction vector y.
ds
Ow:
Remark. If our network is linear = X, so Theorem 3 iss special case of Theorem 4 indeed. Proof sketch. The main idea is that, since J is full rank, by parametrization invariance of NGD the trajectory of s is determined by the trajectory of the corresponding B.
$ $= F=)
(8)
5

---

Under review as a conference paper at ICLR 2022
D - 1000 classification,, sparsily s 20
dynamics of logits sylCyt - ptt) Xxyt
learned coel coefTicients P
positive datapoints negative datapoints
EGD
00%
tedt accurscy
00%
EGD,
70%
NSD (p0p.)
60%
0SD, L
050
NGD
D00, L-4
50%
500
1000
1500
2002
2502
time 10 202
2002
number of observations
Index of input feature
Figure 4: NGD and EGD in a 1000 dimensional sparse classification task, where the ground truth classifier has 20 non-zero components. Left: Test accuracy of EGD depends on parametrizaion. When there are there are fewer datapoints than dimensions, EGD with 2 or 3-layer diagonal parametrization can reach up to 90% accuracy. By contrast, when averaging the Fisher infroma- tion on training samples (dotted line) NGD performs at chance level when N < D. It performs worse than EGD even when N 2 D, or when using the population Fisher calculated on much larger set of samples (dashed line). Middle: Under NGD, when N < D, logits of the model grow linearly, proportional to the binary label. Right: Coefficient vector 3 learnt by EGD in different ar- chitectures and NGD when N = 2500: In the 2-layer diagonal network, corresponding to & implicit regularisation, 3 becomes sparse. In the L-layer model, the solution is substantially less sparse, but the overall structure is learnt. NGD fails to learn the sparse structure.
Then we can calculate F F()) which turns out to be diagonal, so we have N independent differential equations. We solve them get the result. The details of the proof can be found in the Appendix C
3.1 EXPERIMENTS
In order to validate and illustrate findings have run two main simulations, with results pre- sented in Figures 2 [4 In both experiments we considered the direct parametrization 3 = w and the diagonal parametrization 3 = wi @ C wr. (Gunasekar al. 2018) for different depth L. In order to run these experiments we needed to implement an efficient algorithm for computing natural gradients these models: naively calculating and then inverting the Fisher information matrix is computationally inefficient and numerically unstable. We therefore developed an algorithm that ex- ploits the structure the Fisher information matrix, extending the work of Bernacchia et al. (2018) for diagonal networks. The details of our algorithms can be found in Appendix B.2
In Experiment we illustrated EGD and NGD in a 2D toy classification dataset. Positive and nega- tive classes were generated such that they are separable by the the axis-aligned separator, but there exists a non-axis-aligned separator with a higher margin. Based on the findings of Gunasekar et al.) (018 expected EGD to find the large margin solution when L is low, and the axis-aligned solu- tion when L is sufficiently large. The results in panels a and b of Figure 2 confirm these predictions. Figure R illustrate the peterriiaatiionnneeeeeeeee of NGD: it converges the same solution irrespective of parametrization. The solution is different from both the EGD solutions.
focused generalization performance. We generated 1000-dimensional dataset with standard Gaussian X, and a sparse ground-truth separator whose first 20 components were 1, the rest were O. Methods with explicit or implicit regularization towards sparse so- lutions should enjoy good generalization even when N < D. Confirming our expectations, we observed that EGD diagonal parametrizations (L 2, L = 3) performed best on this task. The deeper diagonal model (L = 4) was on par with the shallow solution, we expect that our 2 mil- lion EGD steps were simply not long enough for the implicit regularization to kick in (Moroshko et al. 2020). The NGD solution on the other hand completely fails to generalize when N < 1 and does relatively poorly even as N > D. This catastrophic performance is remedied by averaging the Fisher information but even this variant of NGD fails to match the performance of EGD. The middle panel of Figure 4
In Experiment
a larger dataset i. .e. using the population Fisher (Amari et al.) 2020).
validates the predictions of Theorem 4 logits from the model converge to ty. Finally, the right-hand
panels of Figure 4 show that NGD was unable to identify the sparse structure, which the diagonal model infers best, and even the shallow model approximately finds.
6

---

Under review as a conference paper at ICLR 2022
L intoom
effecctivo rank af converg
20-
toxt lozs
EGD Lm1
50
EGD Lm1
22-
nilhomm L-
IN fro
NGD
NGD
EGD
EGD L-3
EGD L-3
3
1500
1250
1500
1750
2000
2250
2500
1002
1200 1650 1000
1600 2000 2200 2010
1000
1250
3500
number of abservations
number of observations
number of abservations
Figure 5: Performance of unregularized EGD and NGD in rank-5 matrix completion tasks using different architectures. Left and Middle: Using deep matrix product parametrizations with L 2 layers, EGD can reach low training error and identify low-rank solutions even when the number of observations small. By contrast, NGD in the same problem works similarly EGD in the naive parametrization and fails to generalize completely. Right: 2 (orange) and 3 (green) layer models were initialized by collapsing randomly initialized deeper models to test the effect of initialization separately from the effect of EGD dynamics. Initialization plays negligible role in the inductive bias of EGD deep matrix factorization.
4 MATRIX COMPLETION WITH NATURAL GRADIENT DESCENT
As we have seen in Section 2.2 EGD in the deep matrix product parametrization 3 W1 ... WL converges to low-rank solutions. However, when L = 1, i.e. when we run EGD directly on 3, the solution we find is trivial: entries of B3 where we have observation will converge to the observed value, while other entries won't move. Due to parameter-inwe invariice,,,,,,,cee,, NGD cannot differentiate be- tween parametrizations of different depth, is natural to expect that it will fail the same way as EGD does when L 1. Let's look at NGD in matrix completion.
In matrix completion we minimize the squared reconstruction error, which corresponds to the log loss in isotropic Gaussian observation model with & as mean. In Gaussian model, the Fisher Information Matrix of / becomes F F(3) = o I, where of is the observation noise. The observation noise o assumed a constant, and is inconsequential here as it cancels with the o² term in the log loss. Consequently, without loss of generality, we can consider F(3) the identity.
Statement. Let's apply NGF for the problem of matrix completion. EGF in the direct parametriza- tion (B = w) is equivalent to NGF under any parametrization 0 for which J = 3ww. is full rank.
09,
The proof of the statement can be found in Appendix E. This implies that NGF will completely fail to generalize, e.e. make an accurate prediction of any unobserved entry of the matrix.
Figure illustrates the key property of the dynamics which allows EGD to generalize in deeper parametrizations.. Each panel shows values of the neural tangent kernel (NTK) (Jacot et al.) 2018). its equivalent object for NGF called the natural NTK (Rudner et al., 2019). or their discretized versions. For matrix factorization the NTK K(0) is a (D x D) x (D x D) tensor which depends on the parameters where j, k. ((0) measures how much the entry Bi, moves in reaction to a negative loss gradient w.r.t. 8g.1- In these visualizations,
set D 11, and we plot the heatmap of ki.5.5,5. We can see that when we parametrize ,3 directly, the NTK is simply the identity, only the entry A5.5 moves. However, when L 2, EGD by moving entries in the fifth row of W1 or in the fifth column of W2. This, in turn, might result in moving Bi,5 or (5,; as well. This explains the cross pattern seen in Figure 3 first panel in the second information flows' from
respond to the gradient signal at As,s
row. This non-identity NTK is what allows generalization to happen observations to unobserved entries of B. However, NGF, the natural NTK remains the identity irrespective of parametrization This is true even in the approximately invariant NGD.
For our Matrix Factorization experiments we had to develope a scalable and numerically stable algorithm for computing the natural gradient. We did this by extending the algorithm of Bernac- chia et al. (2018) matrix factorization. Exploiting the structure of the Jacobian in the deep matrix product parametrization (3 Wi ... W.) we calculate the natural gradient w.r.t. Wi as BT VaLAt, where A, [1--1 W; and B, II W,. We note that A; and
V.,C L
7

---

Under review as a conference paper at ICLR 2022
B, are matrices that readily computed during the forward and backward pass of mover automatic differentiation of the loss. The details of the derivation can be found in Appendix B.4
Using this algorithm, in Figure 5 we experimentally verify that NGD finds trivial optimum in deep matrix product parametrizations of varying depth. We follow the experimental setup of Arora et al. (019)) and reproduce their results for EGD. We performed an extensive grid search of hyper- parameters and found no setting where NGD would achieve non-trivial performance.
SUMMARY AND DISCUSSION
Inductive biases of gradient- based learning are driven large extent by the way we parametrize our hypothesis. Natural gradient descent (NGD), on the other hand, ignores the parametrization and implicitly optimizes over the manifold of hypothesis. This invited the question whether NGD exhibits any of the useful implicit r regularization that EGD has been shown to have. We characterized the behaviour of NGD over logistic loss, and found that in the overparametrized regime, NGD converges the ordinary least squares interpolant of training labels. This is in contrast with the lurgemaarin--yyo behaviour EGD exhibits. In experiments we found that in the models we studied, NGD fails to generalize well as EGD with the right parametrization.
5.1 OTHER RELATED WORK
Approximate NGD algorithms: Since exact NGD is computationally prohibitive, a great deal of research has been devoted to developing approximate NGD algorithms for deep leaning: K-FAC Grosse & Martens (2016): Martens & Grosse (2015) exploits the approximately Kronecker struc- ture of the Fisher information matrix, while, while Bernacchia et al. (2018) start from exact gradient descent in linear neural networks and then apply the formula verbatim to the non-linear case. An- other line of work aims at improving the invariance properties of NGD algorithms bringing them closer to ideal of NGF (Song et al., 2018 Luk & Grosse 2018). Our motivation differs in that are not focused on designing better NGD algorithms, instead we raise the question whether closer ap- proximation of NGF is desirable in the first place. In order to perform experiments that validate our findings we develop efficient exact natural gradient descent algorithms in overparametrized linear models extending the work of Bernacchia et al. 2018).
Convergence Rates for NGD: The main reason for using NGD in deep learning is the intuitive notion it might speed up convergence by virtue of being invariant to parametrization (Amari 1997
Pascanu & Bengio 2013 Martens 2014). This intuition is backed up by theory: AAmari (1998)
quadratic loss; [Bernacchia et al. (2018) proved fast convergence for deep linear models under quadratic loss; more recently, /Zhang et al. (022)) gave a proof of fast convergence which holds for broad class of overparametrized networks and also extends K- FAC; Rudner et al. (2019) analysed NGD in the neural tangent kernel (NTK) regime. Our work differs in that our primary interest is not whether NGD converges fast, but better understand and illustrate possible trade-off's between fast convergence and generalization.
proved fast convergence
Generalization of NGD: Wilson et al. (017)) were the first to propose that faster convergence may come at the cost of diminished generalization performance in deep learning. Much like our Work/onlsson al. (2017) provided illustrative examples where different methods reach qualitatively different solutions. They focused on adaptive learning rate algorithms like Adam, but due to the connections between Adam and the empirical Fisher information, one might speculate that their findings would extend to NGD as well Zhang et al.] (2019) argued against the notion that NGD may not generalize well, and supported their argument with a generalization bound which holds for both NGD and EGD. However, generalization bounds often fail to predict the empirically observed performance of deep learning (Jiang et al. 2019, see e. g.). In a setting most closely resembling our work Amari et al. (2020) studied generalisation of preconditioned GD for minimising squared loss and found that the optimal preconditioner depends on several factors: EGD generalises better for clean labels, but in scenarios like misspecification or when the labels are noisy, NGD may have an advantage. Finally, Waddi et al.] (202I) argued that second order information of the input data- which some second-order optimisation methods can't utilize well, is key to good generalisation in some neural network architectures. This general connection is related to our Theorems and
5.2 Q&A
Q: How about stochastic gradients? Following Gunasekar et al. (2117 7 2018) Arora et al. (011 2019)am we analysed only full-batch gradient descent. This allowed us to prove properties of gradient flow, i. e. in
8

---

Under review as a conference paper at ICLR 2022
the limit of infinitesimally small learning rates, which is not meaningful limit in SGD. This line of work demonstrates that useful inductive biases exist in gradient- gradient-based learning even in the absence of gradient noise. Indeed, recent empirical evidence suggests that stochasticity may not be necessary for good generalization in deep networks (see e. g. Cieiping et al., 2021). In practice, we expect the question of generalization to be complex, with multiple factors like stochasticity or parametrization- dependence playing a role, We propose that analysing NGD is useful tool in understanding this complex interplay, as acts as a form of ablation by eliminating parametrizatioo--deeedeee
Q: Does this mean NGD does not generalize well?? Not necessarily. We show that there are cases where it does not, but it is possible that in other situations the inductive biases of NGD are more helpful than those of EGD + parametrization, especially when trained on large data. Intuitively, our theorems suggest that NGD may be too efficient at minimising the training loss at the cost of poorer generalisation. However, in our experiments we saw that averaging the Fisher information matrix over test data may remedy this, which would be in line with the practical recommendation of Pascanu & Bengio 2013). Empirical evidence for generalization in exact NGD is sparse due to the computational cost. Some works report good test performance using approximate methods (Grosse & Martenn 2016 Bernacchia et al. 2018 small models (Pascanu & Bengio 2013), but since the focus in these works was on demonstrating the usefulness of new methods, it is questionable how thorough these comparisons were. Zhang et al. (2019); Amari et al. (2020) studied generalisation of natural gradient methods theoretically in limited settings and provided some empirical evidence to support their claims. A systematic empirical investigation similar to (Wilson et al., 2017) may be more informative on this question.
Q: Does initialization play role? Changing the parametrization may influence generalisation in at least three ways: (1) initialization, (2) training dynamics, and (3) constraining the hypothesis space. As weights are often initialized from a parameter- independent distribution, these may give rise to a non-trivial and parameter-dependen initial distribution in hypothesis-space. [aale- Pérez et al. (2018) argued that in deep networks, this manifests as form of simplicity bias. In our models, initialisation has a simlicity bias, too: if matrices WI...., WE are drawn from an isotropic Gaussian, their product &3 will be effectively low-rank with an increasing probability as L increases. By replacing EGD by NGD, we only eliminate the influence of parametrization on training dynamics, but the effects of initialization remain. It is therefore important to disentangle relative importance of initialisation (I), and parameter parameter-dependent dynamics (2). To this end, we designed a set of additional experiments, where we controlled the effect of initialization separately from the effects through dynamics. We initialised deep matrix factorisation models by drawing each component matrix W, as a product of independent Gaussian matrices, then ran EGD. Thus, we were able create models behaving like L 6 layer model at initialization but L 2 layer model during training. We found that the effect of initialization on generalization performance was negligible compared to the effects of training dynamics (Figure [e.. at least in deep linear models. We further note that initialization plays a very important role in the limit of infinitely wide networks, too, where initialization scale determines whether the network behaves like a linear kernel machine, or more like the behaviour we describe in finite networks here (Woodworth et al.) 2020).
Q: What if you calculate Fisher information on test data? Pascanu & Bengio 2013) noted that in deep learning, averaging the Fisher information over test data, rather than training data seemingly improves performance. In our theorems and experiments we assume averaging over the training data, sometimes referred to the sample Fisher information (sce e.g. Ammai al. 2020) this makes our proofs tractable. In our high-dimensional sparse classivication experiment in Figure tested the performance of NGD when the Fisher information is averaged over large number of samples, called the population Fisher, and we found that generalisation performance improved, but still did not match that of EGD, especially when sparsity-inducing diagonal parametrisations are used.
Q: What about other forms of natural gradients? ? In addition to the Fisher-Rao natural gradients that we consider here, there are other forms of natural gradients, such as those based on the Wasserstein metric (Li & Montular 2018 Arbel et al. 2019). When considering this broader family of natural gradient descent, it is natural to ask if the choice of metric may give rise to different inductive biases in NGD similarly to how different parametrizations effect EGD differently. We think this is a fertile area for future research.

---

Under review as a conference paper at ICLR 2022
REPRODUCIBILITY STATEMENT
Python code to reproduce our results (including all Figures except Figure 1 can be found in the following (anonymized) git repository which contains unit tests and documentation:
https://anonymous 4open. science/rr/eepllnett 2F10
REFERENCES
Shun-ichi Amari. Neural learning in structured parameter spaces- natural riemannian gradient. In M. C. Mozer, M. Jordan, and Petsche (eds.), Advances in Neural Information Processing Sys- tems, volume 9. MIT Press, 1997. URL htttpss: neur www.ips..or cc cc/paper///ppc 1996/F11e oag.aaac..........2222222222..5.
332
Shun-ichi Amari Natural gradient works efficiently in learning. Neural Computation, 10:251-276.
1998. ISSN 7667, doi: 10.11162009997666933000000000000
URL / miit.
edu edt/neco/artiie http:///w.cccce.e....//////////1
Shun-ichi Amari, Jimmy Ba, Roger Grosse, Xuechen Li, Atsushi Nitanda, Taiji Suzuki, Denny Wu,
and Ji Xu. When does preconditioning help hurt generalization? 6 2020. URL https:
1073224
Michael Arbel, Arthur Gretton, Wuchen Li, and Guido Montufar. Kemeliied wasserstein natural gradient. 10 2019.
Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep matrix factorization. Advances in Neural Information Processing Systems, 32, 5 2019. URL http:
//arxiv..rq/abb//100000 100.9005...33333 13655
Alberto Bernacchia. Máté Lengyel, and Guillaume Hennequin. Exact natural gradient in deep linear networks and its application the nonlinear case. Advances in Neural Information Processing Systems. 31, 2018. 8. URL https: http::::////oooopoeo/oeo neurips cc pcc/paaper/2018/haeee 7FC18eb7b30 T c18a 93 Abst html
Donald W. Fausett and Charles T. Fulton. Large Least Squares Problems Involving Kronecker Products. SIAM Journal on Matrix Analysis and Applications, 15(1), 1994. ISSN 0895-4798.
doi: 10. 10.11377/0895479991222222
Jonas Geiping. Micah Goldblum, Phillip E. Pope, Michael Moeller, and Tom Goldstein. Stochas- tic training is not necessary for generalization. 2021. URL aattps://arxte org/obg........................e
2109. 14119v1
Roger Grosse and James Martens. A tronecker-factoree approximate fisher matrix for convolution layers. 33rd International Conference on Machine Learning, ICML. 2016, 27851-87, 2 2016.
URL https: /tas:///axivv http:/og/g/aaaaoeoe.eeee 01407v2
Suriya Gunasekar, Blake Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nathan Sre- bro. Implicit regularization matrix factorization. Advances in Neural Information Process- ing Systems, 2011--eceember::12--61111 5 2017. htt.tttss///aii..rrrtt org. Daaxxiv.org/abb///0000 09280v1
Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Implicit bias of gradient descent on linear convolutional networks. Advances Neural Information Processing Systems, 2018- December:9461-9477 6 2018.
org absa 00468
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 7---Deemmeer:70-777... 12 2015. URL htllhttt///// /
03385v1
Daniel Hsu, Vidya Muthukumar, and Ji Xu. On the proliferation of support vectors high dimen- sions. 9 2020. URL htttpss//arxx..oorr///////////0 10t.//
10

---

Under review as a conference paper at ICLR 2022
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernl:: Convergence and generalization in neural networks. Advances in Neural Information Processing Systems, 2018- December.8571-8590, 6 2018.
07572v44
Yiding Jiang, Behnam Neyshabur, Hossein Mobahi, Dilip Krishnan, and Samy Bengio. Fantas- tic generalization measures and where find them. In International Conference on Learning Representations, 2019.
Kwangmoo Koh, Seung-Jean Kim, Stephen Boyd, and Yi Lin. An interior-point method for large- scale I-regularized logistic regression. Journal of Machine Learning Research, 8:1519-1555, 2007.
Wuchen Li and Guido Montufar. Natural gradient via optimal transpor Information Geometry, 1: 181-214, 3 2018.
Kevin Luk and Roger Grosse. A coordinate-free construction of scalable natural gradient. 2018. URL http::ttsssst http://xxxvvvorr.. /aos//188... 10340v1
James Martens. New insights and perspectives on the natural gradient method. Journal of Machine Learning Research, 21:1-76, 12 2014.
James Martens and Roger Grosse. Optimizing neural networks with kronecker-factored approximate curvature. 32nd International Conference on Machine Learning, ICML 2015, 3:2398-2407,, 2015. URL http://///araii.ooo/aaaaa///////
Edward Moroshko, Suriya Gunasekar, Blake Woodworth, Jason D. Lee, Nathan Srebro, and Daniel Soudry. Implicit bias in deep linear classification:: Initialization scale training ac- curacy. Advances in Neural Information Processing Systems, Decembre,, 2020. URL
fttps://arxiv/ org. http://bs/2000.ooo 200.///20070063
Razvan Pascanu and Yoshua Bengio. Revisiting natural gradient for deep networks. 1st International Conference Learning Representations, ICLR 2013 Workshop Track Proceedings, 1 2013.
URL httpps://a.x...or/////////// http:/bs////0 3584v
Tim GJ Rudner, Florian Wenzel, Yee Whye Teh, and Yarin Gal. The natural neural tangent kernel: Neural network training dynamics under natural gradient descent. In 4th workshop on Bayesian Deep Learning (NeurIPS 2019), 2019.
Yang Song, Jiaming Song, and Stefano Ermon. Accelerating natural gradient with higher-order invariance. 35th International Conference on Machine Learning. ICML 2018, 11:7491-7514, 2018. URL htttht:tp//aaaet www.:/wwwwwogg....eooere h.0../////..ssss////rrrrrrrrrr/.
01273v2
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The implicit bias of gradient descent on separable data. 6th International Conference on Learn- ing Representations, ICLR 2018 Conference Track Proceedings, 19:1-57, 10 2017. URL httpp:://rxxv..co 10100////////011000000 1010..035511
Robert Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Sta- tistical Society: Series B (Methodological). 58:267-288, 1996. ISSN 2517-6161. doi: 011111022517-61111199.11111 dol/Eb11/10.111//251177
URL fttts:///on1 http:///onnneeebbrr..eoeo 1996. tbw2080.22...
com/
Guillermo Valle-Pérez, Chico Q. Camargo, and Ard A. Louis. Deep learning generalizes because the parameter-function map is biased towards simple functions. 7th International Conference on Learning Representations, ICLR 2019, 5 2018. http:httts//axxii wwaxxii.rrg//o.. abs/1805.
0B522v5
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in Neural Informa- tion Processing Systems, D999 6009,, 2017. URL https: //arx/aa.vvv.////a////a/.aaaaaaa .wr.i..r.r//////oo...o../ abs/ 0o0/ 03762v5
11

---

Under review as a conference paper at ICLR 2022
Tomas Vaškevičius, Varun Kanade, and Patrick Rebeschini. Implicit regularization for optimal sparse recovery. Advances in Neural Information Processing Systems, 32. 9 2019. URL
https::/aaxiiv http://awwvvvvooaa/////aaa
05122v1
Neha S Wadia, Daniel Duckworth, Samuel S Schoenholz, Ethan Dyer, and Jascha Sohl-Dickstein. Whitening and second order optimization both make information in the dataset unusable during training, and can reduce or prevent generalization. 2021.
Ashia C. Wilson, Rebecca Roelofs, Mitchell Stern, Nathan Srebro, and Benjamin Recht. The marginal value of adaptive gradient methods in machine learning. Advances in Neural Informa- tion Processing Systems, 2017-December:41499 449-4199, 2017. URL https:: beetps://arxiv.ort
abs/ / 1705. 08292v2
Blake Woodworth, Suriya Gunasekar, Jason D Lee, Edward Moroshko, Pedro Savarese, Daniel Soudry, Nathan Srebro, Jacob Abernethy, and Shivani Agarwal. Kernll and rich regimes in overparametrized models. volume 125, pp. 3635-3673. PMLR, 2020. URL https:
//proceedings.uo mlr.. httpeeeeesrnn.......pesss///ss/s wwwpssswelea.. http:///w/1////oooooohh22222 http://owtottt2aaaaccoo
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64:107- 115, 3 2021. ISSN 15577317. doi: 10. 10.1145/3446776. URL httthttps//dd....
orgo doi/
abs /0s/10.00 15.111353346672
Guodong Zhang, James Martens, and Roger Grosse. Fast convergence of natural gradient descent for overparameterized neural networks. Advances in Neural Information Processing Systems, 32, 2019. ISSN 10495258. URL httph:::///// atw.v.riiivv//.i/// org/
http://wwwww....aaa////aaaaaaa/a 111.11991...121222 10961v2
A USEFUL LEMMAS
We will need the following lemma in the proof of Theorem 1,4.
Lemma 1. If we solve a separable classification problem with natrual gradient flow with separator and outpul s, then the gradient and the Fisher information matrix are the following (in case of linear network this means X3): [vC(s)); = - 9i(1 - ((ys8))
(9)
[F())]iss = (s.) (bsi)
(10)
Proof. First note that s(u) Ite- and c5( (b-u)) = 11-((1)
e- Ite-v.
Oc
0 N
[+L(())]
log(1 (unnn)
1 e yi(1 d(v1):))
(11)
ds:
as:
nml
Using Equation
we get the following:
[F(s) Ey V V. [(s)]]k = VT (1 (1,
[y - 2
if i=
Ey [1: d(vs::) [M) o(y,,))) if itj
(12)
(1s))(1-6(ss))) Eg. (1,)) 1y, (y) ((,))) if i
if i=j
Now we get the following:
-1, ((s:)(( ((ss)) (1 (1-)))(1)((s))) 0
(13)
Hence we get:
[F(s)] (c) ((s))).
(14)
12

---

Under review as a conference paper at ICLR 2022
The next lemma is essential in all computation connected to matrix completion with matrix factor- ization.
Lemma 2. If we assume that the product matrix B comes from Gaussian distribution with fixed TnI standard deviation and P mean, then the Fisher information matrix of the product matrix in matrix factorization is F(3) = oz
Proof. Because of the assumption:
p - ((X))N(X),,,n)))
(15)
where 0 the parameters the model (1, on).
1
(x-p)2
(X 11)
(X
(1)
Vo logr(X10) Vo log
(log(
On 2m 2m
On PaV28 2x
20
2
(16)
therefore we can compute the Fisher
(X-1) 1) 1) T
F( F Ex=p(x10)
[Vo logr(X [ogr(X10)] Exxp(X10)
0
0
(17)
B EXACT NATURAL GRADIENTS IN LINEAR MODELS
B.1 SIMPLE LINEAR MODEL LOGISTIC LOSS
To obtain the natural gradient gC with respect to B, we have to solve the following linear system:
P(3)V&LC VVa,,
(18)
where F(3) is the Fisher information matrix and V,C is the (Euclidean) gradient. Under the logistic loss the Fisher information matrix becomes
F(B) X diag(o(X()) o d(xX3)
(19)
where & is the logistic sigmoid which is applied elementwise vector arguments and @ denotes elementwise product. The gradient the logistic loss as follows:
VgL = (y C X) (1-(v X)
(20)
Mathematically, we could use these expressions and solve the linear system Equation 18) however, this would be potentially numerically unstable for reasons outlined below. Let's introduce the nota- tion X y O X and u X simplify the formulæ. Due to symmetry, the Fisher information all occurrences of can be replaced by X. This gives rise the following expressions for the Fisher information matrix:
F(B) X diaglø(u) @ ((-u)
(21)
and the gradient:
v
(22)
As the classifier gets better, components of increase and diverges to +oo. As consequence both F(3) and V.L are expected to become small, from the term o(-u). This could lead to issues with numerical stability. To solve this, we rewrite both using following identity:
1 Φ(-u) 1t er 1te =6"((u)
eu
(23)
obtaining:
F(3) Umaa XT -otagle-utune 2 (u))
(24)
v - Umaz -ut d(u),
(25)
where Umax is the largest entry of u. We have thus isolated the term responsible for poor numerical performance into a multiplicative term Mmus which simply leave out when solving the lin- even as u increases, provided that the difference
ear system. The remaining terms are between elements of is not too large.
13

---

Under review as a conference paper at ICLR 2022
B.2 DIAGONAL LINEAR NETWORK UNDER LOGISTIC LOSs
In diagonal linear network we express 3 = W1 O ...00 OW. Here we will discuss how we compute
the natural gradient with respect to W1.
We now solve the following (underdetermined) system of linear equations, which we write using using Einstein summation notation:
F(B). Vw,, VB,C,
(26)
ag
where J3,1K dwi, is the Jacobian of the mapping from w to B. In this specific parametrization, most entries of J is non-zero. Let's denote the product of the first | - 1 weight vectors as ai and the weight vectors as by we can have:
product of the last L
B. W1,1
Wi. Wi+15" . WL ar, Wi,
(27)
b
Thus, the Jacobian becomes:
bi,
if if i +
Jaik
(28)
Substituting this back, we have solve the following system of equations:
F(B)iJJJLA & wi L = Va,L FI V w1. = VpCC. C.
(29)
(30)
(31)
To ensure numerical stability, use the same trick as in B.2
Since the above system of equations is underdetermined, we could choose different solutions. In our experiments used the pytorch... 1 linalg. 1st least squares solver which finds the solution with the lowest l norm.
B.3 SEPARABLE CLASSIFICATION
First note that in our model (vn E
... 11,
o(s) Ite T
plyn = 1 [|, (3) 1 e
=6(-Bn yn -- Bax
(32)
plyn - -1|xn, (3) 1 UxxT 1 6(-ynx 3)
So the loss function is (Vn E (1,2,...N})
((ynx = log(1 + e 3nx
(33)
and
N
((B) = Σ log(1 + - -bxx
(34)
Until now this did not depend on the parametrization. Now look at the parametrizations we used in our article. If we use fully connected network the gradient is the following:
N
Un X vn
VAL(3)
V log(1 +e - -VxxT
1 + e vnx B
(35)
N
N
Σ
Yn Xn
Bnx, (1 - 6(ynx,T1 B)).
+
e ev,xx00
7=
14

---

Under review as a conference paper at ICLR 2022
The Fisher information matrix is the following:
F(3)
Ex xx 1
N
-1
N
R=1
(1 - -
(1 -1-,
o( o(-x,11))3)
N n=1
(36)
x
(dxx 3) xxx) (1 (1
x
o( B) -1 xx, 3))
If we use diagonal network 3 W1 ④ W2 :
WL-1 & Wr. where
[w]
W2 w
The gradient is the following:
VaC = VW
(37)
where J (the Jacobian) is the following
09 Ow
(38)
iww
where
0
03, a[wnlj
N II
Eú.j
[we]s
(39)
8wn.
k= 1,
The Fisher information matrix is the following:
F(w)= = F(B)J
(40)
B.4 MATRIX FACTORIZATION
Before we compute the natural gradient of matrix factorization let us introduce some notations:
B = W.W, Wz, as before and
0 = vec(B),
(41)
W vec(W, W1, W....,, WL),
(42)
where vec vectorizes the matrices to obtain a column vector. is a reparametrization of w, so With this notation, let's compute the natural gradient with respect the
0 P(w) and let J 30 parametrization w. 8w
V.C = FV (1 = J-
(43)
We use the assumption that J is full rank and because of F(0) = / is invertible (J F(0))J)-
J -1((()) -J--. Thus, the natural gradient simplifies
(44)
and multiplying by J we obtain
= VoL.
(45)
We can consider the Jacobian like L consecutive matrices
= [J1J2... ... Jr]
(46)
where J;
Svec w and note that VoL = werl V BL) and V. = veel we. L)). Rewrite
a0
equation 45
Juec V Ww
w. L) W...
(47)
15

---

Under review as a conference paper at ICLR 2022
If solve the following equation for i 1,... L, then the concatenation of vectors vecl V W; C)
will solve equation 47 as well.
Jevedl Fuee(VW. Ww T,
1 vecl (v.L)
(48)
Let A, = WiW,, wi- and B; W W WL and using @ notation for the Kronecker product and utilize the property vec(ABC) (C
A))ec(XX) we get
(vec( @vec(A,W;B.) a(BTT @ A,) B, @ A. J (Vi) Dvec(W.)
(49)
@vec(W.)
thus need solve
(B. & (w, = L veeceVB VBL)
(50)
for vee( V w: L). One do this by exploiting properties of the Kronecker product and using Moore- Penrose pseudo-inverses as follows:
vee V W. = 1 (B. @ (e)))c(( =
1 (B,
(51)
We note that when A, and B, are near full-rank, using the pseudoinverses may not be numerically stable. Fausett Fulton 1994) instead proposed a solution based on QR decomposition, and even discussed approach which extends to the rank deficient case. In practice we found that this was not necessary for ours experiments. As a result, our implementation we use the formula 1 B VaCAt to update the factor matrices with the natural gradient.
C PROOF THEOREMS
C.I PROOF OF THEOREM 1
Statement. Let's assume, that N < D. is full rank and A an invertible x matrix. Let 3, y. be the trajectory of NGF and Br (XAA yy) (the trajectory of NGF on data XA ). Then X3 3'
Proof. Let XB and s' 3'. The gradient and the Fisher information matrix are the following (the calculation can be found in Lemma D
[+[(s)) (1 (yns.)
(52)
[F(s))i, ( ((s:))
The exact same can be said about s', so and s' are the solutions of the same differential equations, so if we use the same initialization s, st
C.2 PROOF THEOREM 2
Statement. Let B,(X, be the trajectory of NGF and let A be D x D invertible transforma- tion. If 2 D, X has full rank and we consider NGF on the transformed data X then A ( .y) (X.
Proof. Let B' be the trajectory of NGF on the transformed data:
3- (XAA ,y).
(53)
To run NGF on 3' we need its Fisher information matrix. Note that the Fisher information matrix of linear models with logistic-loss is
F(B) x diag(o(XX)) ((-X,))x.
(54)
by Appendix B.1 Note that this case the rank of the Fisher information matrix is D, so it is invertible. Same true for B'. Let's compute the Fisher information matrix of G
N
F(3)
Σ D=1
Egg. Axx,
(yyn Axa V Axn)l
(55)
N
16

---

Under review as a conference paper at ICLR 2022
First, specify Vg. EyvnB" Axn) and use the notation 2e = A.
E Axn) - J E(yn Xn)
(56)
where == 0v ag"
Dv:
0 82 Fr A,
J.J =
(57)
033 0ß²
Therefore J AT JJ and
Fyllyn3' Ax,) = AV Xm)
(58)
We now can continue the computation of the Fisher:
NV
F(Ø')
E M.l, LAx,, [AV T Elyno0 Xn)V VTT llyn0" A
N
1=
(59)
A
Eynix V.= .. u xn) V xn)I)AT AF(e)AT.
Cyynv
N
Note, that the Fisher of v must be invertible as well from the previous Equation. Let's see the NGF on B':
V XA v) = - )AF(()) V V (ynB" Axn) =
(60)
N
F() A A
V Vol(nn 2n) = -F())(((---)0)))) F(o))'V
x=1
We also have the following (by the Chain Rule):
b= J AT
(61)
Now from Equation (60) and 66
we get:
= F(v)
(62)
This is the same differential equation as the one 3 is solution of. So if they are initialized the same way U. = (,) so B, = v2= = A 3'.
C.3 PROOF OF THEOREM 4
Statement, IfN < and is the separator. Let s be the output. Let the Jacobi matrix from ,3 to S be J de J J is full rank s is asymptotically linear with direction vector y.
23.
Proof. First let's note that by the invariance property of NGF the trajectory of is defined by the trajectory of B.
3=-F-(ssVVL(s
(63)
Let's assume is 1-dimensional. In this case X1 and y be used since have only one data point. To solve equation (63) we need the gradient and the Fisher information matrix which are the following (the calculation can be found in the Appendix B.2)
v.L(s) yy(1 (1- Φ(ys))
(64)
The Fisher information matrix:
F(s) ((s)(1 o(s))
(65)
Then Equation (63 can be written as:
$ y(1 d(ys))
(66)
((s) - o(s))
17

---

Under review as a conference paper at ICLR 2022
Now rescale our data points s.t. 2
so $
and y -y 1. Hence we get:
0s
(67)
dt
(())
Which can be solved and the solution
log(1 e²)
= log(e - 1)
(68)
By equation (68 we get the asymptotic behaviour
$ lim
log(e'+c -
lim
(69)
l+c
el
lim (-000 et+c -
lim
(70)
10x 1 - e (t+c)
(From (69) to (70) we use L'Hopital Rule).
Hence proved Theorem 4 for N = 1. Now let's assume, that N > 1. Now we write down the gradient again:
[ -1 o(yss))
(71)
And the Fisher information matrix:
[F(s)) (s) o(s.))
(72)
So now we substitute in Equation (1) and Equation 722 to Equation = Vi as we did in the previous case. Hence we get the following:
We can rescale, so
(1=))(-=(aa)))
(($1))
05
+ (1 (32))
0
2(52))
((8)))
(( X1 (xx))
(b(N)
(73)
Hence we got N independent differential equations which are exactly the same in the N case. So in each dimension š is asymptotically t + e for some c. Hence å z t1 + c, where R P a constant. So s Rs ly + Ca. where C2 R is a constant.
D COUNTEREXAMPLE FOR THE INVARIANCE OF lg LARGE MARGIN SOLUTION
The counterexample is the following:
(-1 2) 2). y = and = (2 -3)
Then (r(X,)) y) = argmin||B]]2 subject to 23, 3,3, 2 1, therefore 3² (-)) Further-
more AT .y) = arggminnl3]] subject to -4,3 2/3 2 1, therefore 3² (XAT, .)) = 0
but (XA .y) =
= (x(
E PROOF OF THE STATEMENT ABOUT THE PARAMETRIZATION INVARIANCE OF NGF
Statement.
Let w and be two parameter vectors related by the mapping 0 = P(w) and consider
natural gradient flow w. Assume that (1) the Jacobian J 80 and (2) F(0.) are both full rank Dw.
for all t. If w. follows natural gradient flow starting from wo then 6 = P (w.) follows NGF, i. e. solves 6, = -((+)) (ex,()))))
18

---

Under review as a conference paper at ICLR 2022
Proof. We use that F(w) = F(O) which follows from the definition of FF:
F(w) =
ExIVx Ex)
The invariance statement follows:
0 =
= = -F L,X,
JJ+ = V -F(O)) -((() Vo,
F PROOF OF THE STATEMENT ABOUT NGD IN MATRIX COMPLETION
Statement. Let's apply NGF for the problem of matrix completion. EGF the direct parametriza- tion (B w) equivalent to NGF under any parametrization for which J Ow. full rank. 89,
Proof. First let's consider parametrization 0 s.t. the direct parametrization 3 w (= P(0)) and Sw is full rank. Then by the invariance property Og is the solution of the NGF with the 0Ø
arbitrary parametrization, then w, P(O,) is the solution of:
w - V-Vw(((
Which agrees with the EGF with direct parametrization.
G INVARIANCE PROPERTY OLS
We show the same transformation invariance property for OLS that showed in Theorem 2 for NGF. Again, we split the problem into two cases: D and 2 D. Note that for the problem X y the Ordinary least squares solution is B (X X) X y if the columns of X is linearly independent.
Statement. Let N < D, A is an invertible x D matrix. If B the solution of the Ordenary least squares problem for the matrix X and (3' for XAT, then X XATB.
Proof. Immediately follows from the definition of the problems: X = y and XA B' = =y= y-
Statement. Let N 2 D, X has full rank and is an invertible x D matrix. If B is the solution of the OLS problem for the matrix X and B for XA then A B' B.
Proof.
A 3 4
H SUPPLEMENTARY FIGURES
19

---

Under review as a conference paper at ICLR 2022
D 50 classification, sparsity s =
100%
90%
test accuracy
80%
EGD, L =1
70%
NGD
EGD, =
60%
EGD, = 3
EGD,L=4
50%
0
200
400
600
800
1000
number of observations
Figure 6: During peer review, reviewers requested lower dimensional variant of the experiment reported in Figure 4 Instead of 1000 dimensions, in this experiment we used D 50, and instead of = 20 non-zero components, the real / had 5 5 non-zero entries. The experimental setup and hyperparameters were otherwise not changed from Figure The 5-layer diagonal network performs poorly, which is likely result of sensitivity hyperparameters,, we expect that with additional fine- tuning of the hyperparameters for this experiment, L = 4 would do at least as well as the shallow == model.
20


Reviews:
[{"review_id": "tpMRszNsFwb", "reviewer": "Reviewer_gWo5", "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": "## Strenghts\n\n - The background is clearly explain. The illustrative figures, and the toy experiments are well designed.\n - The theorems are simple, yet as far as I know novel, and not trivial. The simple conclusions of these theorems provide useful insights into the inductive biases of natural gradient algorithms.\n\n## Weaknesses\n\n - It is not clear from the text what is N and D in the beginning of section 3\n -  For theorem 1 to hold true, I think that $\\beta_t$ and $\\beta'_t$ also must start from the same initial conditions (it is not specified in the theorem statement)\n - I found some parts to be not very clear: between theorem 3 and 4 there is a discussion that starts with \"OLS works very differently from large-margin methods\" and end with \"when $D>N \\log N$ they end up finding the same solution\".\n - section 4, paragraph 1: why is it a bad thing that \"other entries won't move\" ?\n\nAnd on a different subject, I would have appreciated an experiment on an actual dataset/architecture to illustrate the consequence of your theorems in actual deep nets.\n\n## Typos\n\n - section 3: conclusion missing $_t$ in $\\beta_t$\n - \"perfectly)\" (second to last paragraph end of page 5)\n - page 6 \"to unobserved entries\"\n - \"develope\"\n\n## Other related works that could have been discussed\n\n- https://arxiv.org/abs/2006.10732\n- https://arxiv.org/abs/2008.07545", "summary_of_the_paper": "This paper studies the inductive bias of natural gradient flow in deep linear networks and in matrix factorization. They show that the solution to the empirical risk minimization problem using NGF is invariant to pixel permutation, and conclude that the desirable property of Euclidean gradient descent under logistic loss of finding the minimum l2 norm solution does not hold (theorem 1&2).\n\nThey also contribute an efficient NGD algorithm for deep diagonal linear networks.", "summary_of_the_review": "Overall this is an interesting discussion of the different inductive biases of EGD and NGF.", "strength_and_weaknesses": "", "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": "gSSj9GbYxZ", "reviewer": "Reviewer_VPSX", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Strengths:**\n- I think studying NGD as \"a form of ablation by eliminating parametrization-dependence\" is a very clever way to better understand the complex interaction of the learning rule (and hyperparameters) and the parametrization of the model when it comes to explaining generalization performance in modern deep networks.\n- The entire paper was very well organized, writing was clear and the proofs and theorem statements were well written and explained.\n- I thought the background on the interaction of parameterization and EGD in separable classification and matrix completion was very well done.\n\n**Weaknesses:**\n - The major weakness of this work is that while I think studying NGD (either theoretically or empirically) as a means of understanding the role of parametrization in generalization is very original, in the two settings studied (linearity separable classification and matrix factorization) the parameter-to-hypothesis mapping is already well understood.  I was hoping to see how this \"ablation\" technique could be applied to settings where there wasn't already a good understanding of the role of parametrization to provide *new* insights.  Clearly stating what new insights can be gained from this perspective or considering a not well studied setting (empirically or theoretically) would be helpful.\n - If the contributions of section 3 are to provide new, useful insight into the inductive bias of NGD, then I think this could be emphasized and discussed more.  What do these simplified settings imply for understanding NGD in a general setting?  I think you could expand here on the question in section 5, \"Q: Does this mean NGD does not generalize well?\".\n - You mention multiple times how you extend the work of Bernacchia et al. (2018) to develop \"an algorithm that exploits the structure in the Fisher information matrix...for diagonal networks\", but left all detail of this work in the Appendix.  Without diving into the details, its hard to understand what you did to extend their work.  This is one of your major contributions and certainly essential to your experimental section, so I would discuss this in much more detail in the body.\n\n**Minor comments:**\n- In the emphasized block, \"influences the inductive biases of gradient-base learning\", do you mean \"gradient-based\"?\n- The end of this sentence is confusing: \"...matrix factorization models tended to the minimum nuclear norm solution, but for fewer observed entries, which is the interesting case, this was not the case.\" Did you forget a word or meant to delete something?\n- In the proof of \"Invariance of NGF under reparametrization\" you write $\\mathcal{P}(\\dot{w}_t)$ but I think you mean $\\dot{\\theta}_t$?  Correct me if I am wrong but in general these should only be the same if $\\mathcal{P}$ is linear.\n- In theorem 4 you write \"the Jacobi matrix\", do you mean \"Jacobian\"?\n- Consider the relatively recent work \"Kernel and Rich Regimes in Overparametrized Models\" when discussing the role of initialization, parametrization and implicit biases.", "summary_of_the_paper": "This paper studies the role of parameterization in determining inductive biases and influencing generalization in deep learning by studying natural gradient descent.  As the authors review, natural gradient descent is invariant to reparameterization.  This implies that the trajectory of NGD is in some sense ablating the role of parameterization allowing the authors to (1) determine the importance of parameterization with gradient descent in generalization, and (2) study the inductive biases unique to NGD.  The authors consider two settings both theoretically and empirically: separable classification with deep linear models and matrix completion via deep matrix factorization.", "summary_of_the_review": "In summary, I think this work is very well written, clear, and addresses an important question (how to understand the role of parameterization in generalization) through an original lens, the study of natural gradient descent/flow.  However, the authors did not convince me that this perspective could lead to new insights that were not already well known.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "Ojd9zo7Pz6P", "reviewer": "Reviewer_CBDn", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper provides some interesting analyses on natural gradient descent in training deep linear models. The observation that natural gradient flow is invariant to reparameterization looks particularly insightful. Experient results are also provided to back up the theories. \n\nHowever, I also find several limitations of the paper:\n\n- The presentation of the paper is not clear. For example, the studies in this paper are focused on binary classification with logistic loss. However, Section 2.2 and Section 4 discussed matrix factorization, which, if my understanding is correct, is a regression-type problem. Therefore, it is not clear how the analyses in this paper can be applied to matrix factorization problems. Moreover, the remark below Theorem 3 is not consistent with the introduction around equation (5). \n\n- The results of this paper are not very comprehensive. Theorems 3 and 4 seem to be much weaker compared with the inductive bias results for Euclidean gradient flow. Moreover, the claim that there exist learning problems where natural gradient descent perform much worse than Euclidean gradient descent is only demonstrated experimentally.\n", "summary_of_the_paper": "This paper studies the inductive bias of natural gradient flow. The authors highlight the invariance property of natural gradient flow under reparameterization, and study the training dynamics of natural gradient flow under different problem settings for deep linear models. ", "summary_of_the_review": "For the reasons listed in the previous section, I think this paper is at the borderline, and I currently tend to recommend rejection. ", "strength_and_weaknesses": "", "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": "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": "NfA2ui4zEh", "reviewer": "Reviewer_74k1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "## Strengths \nThis paper in general is well-written and easy to read.  This paper is a findings paper.  \n\n## Weaknesses \nThere are some issues that could weaken the arguments made in this paper.\n\n### 1. Invariance of NGD\nThe statement in Sec 2.3 assumes the Fisher information matrix (FIM) is non-singular (full-rank).\nThe authors should clarify whether the FIMs considered in the Experiments in Sec 3.1 and Sec 4 are indeed non-singular.\nIf the pseudoinverse is indeed employed, the authors should also show that the invariance of NGD or NGF also holds in singular cases.\n\n### 2. Theorem 4\nIn Theorem 4, the authors assume that the Jacobian matrix is full-rank. \nThe authors should give an example of a 2-layer (linear) NN to illustrate how this assumption is satisfied. I also wonder why the FIM is non-singular in this case since Eq 9 implies that the FIM is invertible.\n\n\n### 3. Meaning of D\nDoes D mean the number of input features? If so, I wonder whether the authors consider the most common cases when the number of input features (D) << the number of (training) data points (N) << the number of NN parameters. \nThis question is closely related to pointer 4.\nI think all experiments considered should report these three numbers.  \n\n### 4. Empirical FIM approximations\nIn Eq 2, the exact FIM is computed under the expectation w.r.t. x.  In this work, the FIM is computed over a set of training data, which is known as an empirical approximation in statistics. If the number of data points << the number of input features, the empirical approximation of the FIM could be bad (see [1]).\nIn experiment 2, the authors show that NGD could perform poorly. The authors should report the number of parameters used in this experiment. \nAccording to the caption of Figure 4, the number of training data points is 2500 and the number of input features is 1000.  I do not think the empirical approximation of the FIM over 2500 training data points is good enough since the FIM should be at least a 1000-by-1000 matrix.\nI would like to see the performance of NGD when the number of input features is changed from 1000 to 50. For the sparse classification task, the authors may set the first 5 components to be 1 instead of the first 20 components.\n\n\n### 5. Practical NGD with damping (ridge regression)\nIn practice, I do not think the pseudoinverse is used due to the high computational cost.\nIt will be great if the authors can comment on cases when damping is used. Does damping introduce extra inductive bias of NGD? \n\n### 6. Initialization does play a role\nNGD is a discretization of NGF. Solving NGF is an initial value problem (IVP) in this setting. \nThus, initialization should play a role such as pre-training. The statement about initialization should be more carefully stated.\n \n\n\n ## References\n [1] Kunstner, Frederik, Philipp Hennig, and Lukas Balles. \"Limitations of the empirical Fisher approximation for natural gradient descent.\" Advances in Neural Information Processing Systems 32 (2019): 4156-4167.\n\n  \n", "summary_of_the_paper": "In this work, the authors study the inductive bias of natural gradient descent in some simple and ideal settings. \nThe authors argue that the invariance of NGD could lead to a worse generation error compared to standard gradient descent (EGD) in some settings.\n ", "summary_of_the_review": "This paper in general is well-written and easy to read.  Some arguments made in this work seem to be reasonable. However, there are issues that weaken the arguments. Please address the issues in the main review. I am happy to give a higher rating.\n", "strength_and_weaknesses": "", "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": "Not applicable"}, "extra_text": {}}, {"review_id": "2u8YavtMlNy", "reviewer": "Reviewer_2Yhk", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "The main subject of the paper is to utilize properties in NGD and study the inductive bias of NGD. However, either current reviewer or the authors are misunderstanding what the “reparametrization invariance” properties of NGD means. In general, the descriptions in section 2.3 where the NGD is described looks okay. The authors even say that \n\n“NGD with infinitesimally small learning rate (i. e. NGF) always follows the same trajectory in model-space and this finds the same optimum, irrespective of how it is parametrized, provided that the parametrization is _smooth_ and _locally invertible_.”\n\nHowever, as far as I can tell, the authors study parameterization changes that’s not considered reparameterization. For example, in Section 3, the authors consider $\\beta= w$ vs $\\beta = w_1 \\odot \\cdots \\odot w_L$, the parameter space dimension changes from $D$ to $L \\times D$ which to me is not considered reparameterization with guaranteed optimization equivalence under NGD. Similarly in matrix completion Section 4, parameterizing $\\beta$  (with dimension $D \\times D$) with different depth of matrices $W_i$ (dimension $L \\times D \\times D$) to me is just a completely different model architecture rather than a reparameterization.  To me, what others are saying is similar to  ResNet-50, ResNet-101 or VisionTransformer to solve ImageNet classification problems are “different parameterization” in reality are just different architectures. \n\nWithout the justification of connecting optimization of different architectures, I don’t quite understand the point of the analysis. There’s a chance that the reviewer is totally missing the point but to say the least, the main point, if it exists, doesn’t come across properly given that NGD doesn’t say anything about optimization of different architectures. \n\nTo delve into this issue in more detail, for example in Figure 5 / Section 4, where the authors identify a problem where NGD doesn’t generalize but GD does well with L=2, L=3. I do wonder what the author is actually showing is that L=1 is a bad way (in an obvious way) to solve matrix completion problems. Can authors confirm the NGD was also run on L=2, L=3 cases and obtain non-generalization behavior?\n\nThe reviewer does recognize in Figure 2 that C, D leads to the same solution which is interesting and would like to have better understanding given that NGD doesn’t guarantee the same optimization for different architectures. \n\n\nNit:\n- NGF is used without introduction: since the paper mainly focuses on NGF, one should introduce and define early in the introduction. \n- p3 Figure 3 description needs more explanation, without reading section 4, it’s hard to tell what the figure is showing. At least describe that they are components of a natural NTK. \n- p5 (X, y) -> $(X, y)$ (put in the math-form)\n- p8  “from observations too unobserved entries” -> “from observations to unobserved entries” \n- p8 “ichi Amari”: remove “ichi”\n- p14 “Until know this” -> “Until now this”\n\n-----------------------------------------------------\nPost-rebuttal: Thank you for the detailed explanation on validity of reparametrization invariance and verifying NGD in deep MF models. I agree that deep linear models the paper study is somewhat special. Also intermediate layer width (e.g. extreme bottleneck width) could break local invertible map, although the paper simplifies the analysis to equal large hidden layer widths. It would be probably worth pointing out and explaining how reparametrization invariance can be applied to models under study. Also the author should justify full rank of FIM. \n\nI've raised my score and lowered my confidence based on the discussion. \n", "summary_of_the_paper": "The paper studies inductive bias of natural gradient descent (NGD) in deep linear networks. Utilizing _reparameterization invariance_ properties of NGD, the authors attempt to eliminate the role of parameterization and isolate the effect of solution found by gradient descent.  The paper studies gradient flow dynamics for 1) separable classification under logistic loss and 2) deep matrix factorization. One of the contributions stated is identifying learning problems where NGD fails to generalize while GD with the right architecture performs well. ", "summary_of_the_review": "While studying inductive bias of gradient descent optimization and their role to generalization property is an important subject and natural gradient descent provides an interesting tool to investigate and isolate certain optimization artifacts, I believe the current paper’s direction of analyzing these may be flawed. Without proper justification of their methodology, the reviewer suggest that the paper shouldn’t be accepted to ICLR.", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: *Summary:* Study inductive bias of natural gradient flow. 

*Strengths:* 
- Some reviewers found the invariance to reparametrization insightful, a good way to better understand the interaction of the learning rule and parametrization. 
- Experiments support the theory.   

*Weaknesses:* 
- Unclear takeaway message. 
- Comparison with Euclidean case not comprehensive. 
- Insufficient distinction between reparametrization (invertible) and different parametrization. No experiments on actual dataset/architecture.
- Some reviewers found the the cases considered in the paper are already well understood. 

*Discussion:* 

2Yhk found that although the author responses and other reviews clarified some of their concerns, particularly about reparametrization conditions, the result provided in the paper is not strong enough and could be further clarified. The authors found that this reviewer might have misunderstood the paper. Following the discussion period, the reviewer raised his/her score and lowered his/her confidence. In response to CBDn the authors added demonstration of NGD being worse than EGD on matrix completion. In one of the responses, the authors summarize their contribution as: ''replacing EGD with NGD … disturbs the second mechanism [dynamics and GD trajectories]''. I find the question really is what kind of quantitative conclusions can be made. gWo5 pointed out important related work that was not discussed in the initial submission. Authors added discussion. VPSX misses applications to less well understood settings. Authors however only offer to keep this in mind for future work. VPSX also asks to emphasize the insights into the inductive bias of NGD. Authors added some discussion, however mostly pertaining previous works and not specific enough in my opinion. 

*Conclusion:* 

One reviewer found this work marginally above the acceptance threshold and four other reviewers found that it does not reach the bar for acceptance. I find the topic worthwhile and that it deserves a thorough investigation. However, I concur with the reviewers that some concepts require a clearer presentation and that it would be desirable to see more general results and more comprehensive discussions. Several suggestions were made by the reviewers and acknowledged by the authors, but many of these were left for future work. In summary, I think that the article makes a good start but needs more work. Therefore I am recommending a rejection at this time. I encourage the authors to revise and resubmit.
Decision: Reject