Theoretical Characterisation of the Gauss Newton Conditioning in Neural Networks
Authors: Jim Zhao
Sidak Pal Singh
Aurelien Lucchi
Venue: NeurIPS 2024 poster (2024)
Keywords: conditioning
gradient outer product
Gauss-Newton matrix
optimization landscape
Primary area: deep_learning_architectures
TL;DR: We analyze how different architecture choices, such as the depth or width of hidden layers or residual connections affect the conditioning of the

Abstract: The Gauss-Newton (GN) matrix plays an important role in machine learning, most evident in its use as a preconditioning matrix for a wide family of popular adaptive methods to speed up optimization. Besides, it can  also provide key insights into the optimization landscape of neural networks. 
In the context of deep neural networks, understanding the GN matrix involves studying the interaction between different weight matrices as well as the dependencies introduced by the data, thus rendering its analysis challenging.
In this work, we take a first step towards theoretically characterizing the conditioning of the GN matrix in neural networks. We establish tight bounds on the condition number of the GN in deep linear networks of arbitrary depth and width, which we also extend to two-layer ReLU networks.
We expand the analysis to further architectural components, such as residual connections and convolutional layers. 
Finally, we empirically validate the bounds and uncover valuable insights into the influence of the analyzed architectural components.

Theoretical characterisation of the Gauss-Newton conditioning in Neural Networks
Jim Zhao"
Sidak Pal Singh' ETH Zürich, Switzerland sidak. singheif ethz,
University of Basel, Switzerland j jim zhao@unibas. ch
Aurelien Lucchi University of Basel, Switzerland aurelien. lucchi Sunibas. com
Abstract
The Gauss-Newton (GN) matrix plays an important role in machine learning, most evident in its use preconditioning matrix for wide family of popular adaptive methods to speed up optimization. Besides, it can also provide key insights into the optimization landscape neural networks. In the context of deep neural networks, understanding the GN matrix involves studying the interaction between different weight matrices as well as the dependencies introduced by the data, thus rendering its analysis challenging. In this work, we take a first step towards theoretically characterizing the conditioning of the GN matrix neural networks. We establish tight bounds on the condition number of the GN in deep linear networks of arbitrary depth and width, which we also extend to two-layer ReLU networks. We expand the analysis to further architectural components, such as residual connections and convolutional layers. Finally, we empirically validate the bounds and uncover valuable insights into the influence of the analyzed architectural components.
1 Introduction
The curvature is a key geometric property of the loss landscape, which is characterized by the Hessian matrix or approximations such as the Gauss-Newton (GN) matrix, and strongly influences the conver- gence of gradient-bart based optimization methods. In the realm of deep learning, where models often have millions of parameters, understanding the geometry of the optimization landscape is essential to under- standing the effectiveness of training algorithms. The Hessian matrix helps identify the directions in which the loss function changes most rapidly, aiding in the selection of appropriate learning rates and guiding optimization algorithms to navigate the complex, high-dimensional space of parameters. How- ever, in practice, the Hessian is not easily accessible due to the high computational cost and memory re- quirements. Instead, the GN matrix (or its diagonal form) commonly employed in adaptive optimiza- tion methods such as Adam [Kingma and Ba, 2014] with the goal to improve the conditioning of the landscape. Although the Gauss- -ewttn matrix Go is only an approximation to the full Hessian ma- trix, it does seem to capture the curvature of the loss very well given the success of many second-order optimization methods based on approximations of the Gauss-Newton matrix, such as K-FAC [Martens and Grosse, 2020], Shampoo [Gupta et al., 2018] or Sophia [Liu et al., 2023]. Particularly interesting the last method, in which the authors observe that their optimizer based on the Gauss-Newton matrix performs even better than their optimizer based on the full Hessian matrix, implying that the Causs-Newtar matrix is a good preconditioner and captures the curvature of the loss landscape well.
First two authors have equal contribution
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Pruning rale
Figure 1: Training loss (left) and condition ber R. of GN (right) for a ResNet20 trained on sub- set of Cifarl0 (n = 1000) with different proportions of pruned weights. Weights were pruned layerwise by magnitude at initialization.
06
20%
40%
60%
80%
10
Condition minterr R
Thaining loss
300
10
200
10a
10
104
20
10
100
20
80
100
Epochs
Epochs
The prevalence of adaptive optimizers and their success in training neural networks illustrates the ability of the GN matrix capture curvature information similar to that of the Hessian matrix.
Although the non-convexity of neural loss landscapes can be considered as a given, some landscapes be tougher to traverse than others. This can, for instance, arise due to, be amplified by, aspects such as: (i) disparate scales of the input data and intermediate features, (ii) initializing the optimization process degenerate location in the landscape (imagine entire set of neurons being dead), (iii) architectural aspects such as width, depth, normalization layers, etc.
Given the close relation of the GN matrix to the network Jacobian (with respect to the parameters) and hence signal propagation [Lou et al., 2022], its significance also reaches more broadly to problems such model pruning and compression. For instance, it has been extensively observed empirically that training extremely sparse neural networks from scratch poses a significantly greater challenge compared pruning neural networks post-training [Evci et al., 2019]. In an illustrative example shown in Fig. I, we observe that training sparse networks from scratch using stochastic gradient descent results in slowdown of training, which is also reflected in an increase in the condition number of the GN matrix (similar experiments on Vision Transformers and other architectures can be found in Appendix I.1). This underscores the relevance of the conditioning of the GN matrix for understanding the behaviour of gradient-based optimizers and emphasizes the significance of maintaining well-behaved loss landscape of the neural network throughout training.
In fact, many fundamental components of deep learning frameworks, such as skip-connections as well as various normalization techniques [loffe and Szegedy, 2015, Salimans and Kingma, 2016, Ba et al., 2016, Wu and He, 2018, Miyato et al., 2018], have been to some degree designed to mitigate the challenges posed by ill-conditioning in neural network optimization. This line of work continues to expand to this date, seeking out better normalization schemes, optimization maneuvers, and regu- larization strategies [Kang al., 2016, Wan al., 2013] that allow for easier and faster optimization while avoiding directions of pathological curvature. But despite the numerous approaches to redress the poor conditioning of the landscape, understanding the precise factors of ill-conditioning within the network structure, and their relative contributions, has remained largely underdeveloped.
Hence, our aim in this work is to carry out detailed theoretical analysis of how the conditioning of the Gauss-Newton matrix is shaped by constituting structural elements of the network i.c., the hidden-layer width, the depth, and the presence of skip connections, name few. We will shortly formally introduce the would like to provide tight bounds for the condition number of these
matrix and how it connected to the Hessian of the
loss function. Concretely, two terms as a function of the spectra of the various weight matrices and reveal the interplay of the underlying architectural parameters conditioning. Furthermore, aim investigate the impact of both the dataset's structure and the initialization procedure on the conditioning of the loss landscape.
Contributions. Taking inspiration from prior theoretical analyses of deep linear networks, we make first foray into this problem by rigorously investigating and characterizing the condition number of the GN matrix for linear neural networks (the extension to the second term of the Gauss-Newton decomposition is touched upon in the Appendix). Our analysis holds for arbitrary- and unveils the intriguing interaction of the GN matrix with the conditioning of various sets of individual layers and the data-covariance matrix. We also complement our analysis in the linear case by studying the effect of non-linearities, via the Leaky-Rel.U activation, albeit for two-layer networks. Importantly, as consequence of our analysis, show the precise manner in which residual networks
networks

---

with their skip connections or batch normalization can help enable better conditioning of the loss landscape. While our work builds on Singh al. [2021]. our main contribution is the introduction of tight upper hounds for the condition number of the Gauss-Newton (GN) matrix for linear and residual networks of arbitrary depth and width. To the best of our knowledge, this has not been addressed in the literature before. Lastly, given that our bounds are agnostic to the specific values of the parameters in the landscape, we show the phenomenology of conditioning during the training procedure and the corresponding validity of our bounds.
2 Setup and background
Setting. Suppose we are given an i..d. dataset S (1x1,1))..... ....... Yn)). of size |S| n, drawn from unknown distribution px,y, consisting of inputs x E X R and targets y E C R Based on this dataset S, consider we use a neural network to learn the mapping from the inputs to the targets, Fg X + Y, parameterized by 0 e R To this end, we follow the framework of Empirical Risk Minimization [Vapnik, 1991], and optimize a suitable loss function L θ - R. In other words, solve the following optimization problem,
0
= argmin L( = Σ (0; (x.: 2=1
say with a first-order method such as (stochastic) gradient descent and the choices for could be the mean-squared error (MSE), cross-entropy (CE), etc. For simplicity, we will stick to the MSE loss.
Gauss-Newton Matrix. We analyze the properties of the outer gradient product of the loss function, Go. which we call the Gauss-Newton matrix, defined as
Go - VoFo(x,) VoFo(x))VFo(x)) VoFo(x.)
(I)
where, (xFo(x;) E Roxk is the Jacobian of the function with respect the parameters 0, p the number of parameters, k is the number of outputs or targets. This outer product of the gradient is closely related to the Hessian of the loss function via the Gauss-Newton decomposition [Schraudolph, 2002, Sagun et al., 2017, Martens, 2020, Botev, 2020], hence the chosen name, which decomposes the Hessian via the chain rule as sum the following two matrices:
H = Ho + HF 1 n
K
Σ (oLa(xx) & VoFo(x,) T
VF. I (xH)(,,),
c=1
where V2. la E pkxk is the Hessian of the loss with respect to the network function, at the i-th sample. Note that if & is the MSE loss, then Ho = -Go
Remark R1 (Difference between H2 and Go). When considering MSE loss, the difference between the Gauss Newton matrix Go and the Hessian of the loss function Hμ depends on both the residual and the curvature of the network Fo(x). Thus, close convergence when the residual becomes small, the contribution of Hy will also be negligible and Go is essentially equal to H₁. Furthermore, Lee et al. [2019] show that sufficiently wide neural networks of arbitrary depth behave like linear models during training with gradient descent. This implies that the Gauss-Newton matrix a close approximation of the fall Hessian in this regime throughout training.
Condition number and its role in classical optimization. Consider we are given quadratic problem, argmin 2 w Aw, where A > 0 is a symmetric and positive definite matrix. The optimal solution occurs for w = O. When running gradient descent with constant step size 7 >> O. the obtained iterates would be W (I 7Ajwk-1- This yields a convergence rate ||w=-w"|l of [W----w'] S max (11 m)/max [1],/1 17Amin (A))) The best convergence obtained for = (2maxx (A) + Amin Amin(A)) (A))-1 resulting in |w&ll < - l where k(A) = Amaa(() is
Amma(A
called the condition number of the matrix. This ratio which, intuitively. measures how disparate are the largest and smallest curvature directions, an indicator the speed with which gradient descent would converge to the solution. When
co, the progress can be painfully slow, and + indicates all the curvature directions are balanced, and thus the error along some direction does not trail behind the others, hence ensuring fast progress.
3

---

Effect of condition number at initialization on the convergence rate As the condition number a very local property, it in general hard to connect the conditioning at network initialization to a global convergence rate. However, we would like to argue below that an ill- ill-conditioned network initialization will still affect the rate of convergence for gradient descent (GD) the initial phase of training. Let us denote the Lipschitz constant by L and the smoothness constant by p. Furthermore, let the step size be such that 7 S +. We present a modified analysis of GD for strongly convex functions, where we use local constants μu() and L(k) instead of the global smoothness and Lipschitz constant, respectively. Then by the definition a single step of gradient descent and using the strong convexity and smoothness assumption we have:
00++1 - 11 s (1 m - 101
(2)
So by recursively applying (2) and replacing μr by the local smoothness constants (x():):
0 0-1 S II (1- 100)m00)10000000 0 1=0
One can clearly see the effect of (( in the bound, which is even more dominant when μ(() changes slowly. Of course, the effect of (a()) attenuates over time, and that's why we are talking about local effect. However, one should keep in mind that overparametrization leads the parameter to stay closer to initialization (at least in the NTK regime [Lee et al., 2019]).
3 Related work
Since the Gauss-Newwon matrix is intimately related to the Hessian matrix, and the fact that towards the end of training, the Hessian approaches the Gauss-Newton matrix [Singh al., 2021], we carry out a broader discussion of the related work, by including the significance of the Hessian at large.
(i) Generalization-foousse work: There is a rich and growing body of work that points towards the significance of various Hessian- based measures in governing different aspects of optimization and generalization. One popular hypothesis [Hochreiter and Schmidhuber, 1997, Keskar et al., 2016, Dziugaite and Roy, 2017, Chaudhari al., 2019] is that flatter minima generalize better, where the Hessian trace or the spectral norm is used to measure flatness. This hypothesis is not undisputed [Dinh et al., 2017]. and the extent to which this is explanatory of generalization has been put to question recently [Granziol, 2021, Andriushchenko et al., 2023]. Nevertheless, yet another line of work has tried to develop regularization techniques that further encourage reaching a flatter minimum, as shown most prominently in proposing sharpness- aware minimization [Foret et al., 2021].
The relevance of the Hessian matrix for neural networks.
(ii) Understanding Architectural and Training aspects of Neural Networks: Some other work has studied the challenges in large-batch training via the Hessian spectrum in Yao et al. [2018]. Also, the use of large learning rates has been suggested to result in flatter minima via the initial catapult phase [Lewkowyez et al., 2020]. The effect of residual connections and Batch normalization on Hes- sian eigenspectrum were empirically studied in Ghorbani et al. [2019], Yao al. [2020]. which intro- duced PyHessian, framework to compute Hessian information in scalable manner. More recently. the so-called edge of stability [Cohen et al., 2021] phenomenon connects the optimization dynamics of gradient descent with the maximum eigenvalue of the loss Hessian. Very recently, the phenomenon of Deep neural collapse was studied in Beaglehole et al. [2024] via the average gradient outer-produce
(iii) Applications: There has also been a dominant line of work utilizing the Hessian for second-orde -oddr optimization, albeit via varying efficient approximations, most notably via K-FAC [Martens and Grosse, 2020] but also others such as Yao et al. [2021], Liu et al. [2023], Lin et al. [2023]. Given its versatile nature, the Hessian has also been used for model compression through pruning [LeCun et al., 1989 Hassibi et al., 1993, Singh and Alistarh, 2020] as well as quantization [Dong et al., 2019, Frantar et al., 2023], but also in understanding the sensitivity of predictions and the function learned by neural networks via influence functions [Koh and Liang, 2020, Grosse et al., 2023], and countless more.
Theoretical and empirical studies of the Hessian. There have been prior theoretical studies that aim to deliver an understanding of the Hessian spectrum in the asymptotic setting [Pennington and Bahri, 2017, Jacot al., 2019]. but it remains unclear how to extract results for finite-width
For details of the derivation, we refer the reader to Appendix H.1

---

networks as used in practice. Besides, past work has analyzed the rank, empirically [Sagun et al., 2016, 2017] well as theoretically [Singh et al., 2021. 2023]. Further, the layer-wise wise Hessian of network can be roughly approximated by the Kronecker product of two smaller matrices, whose top eigenspace has shown to contain certain similarities with that of the Hessian [Wu et al., 2020]. In different line of work by Liao and Mahoney [2021], the limiting eigenvalue distribution of the Hessian of generalized generalized linear models (G-GLMs) and the behaviour of potentially isolated cigenvalue-eigenveecte pairs is analyzed.
Hessian and landscape conditioning. The stock of empirical repertoire deep learning has been en- riched by successful adaptive optimization methods plus their variants [Kingma and Ba, 2014] as well as various tricks of the trade, such as Batch Normalization [loffe and Szegedy, 2015], Layer Normal- ization [Ba et al., 2016], orthogonal initialization [Saxe et al., 2013, Hu et al., 2020], and the kind, all of which can arguably be said to aid the otherwise ill-conditioning of the landscape. There have also been theoretical works establishing link between the conditioning of the Hessian, at the optimum and the double-descent like generalization behavior of deep networks [Belkin et al., 2019, Singh et al., 2022].
Gawss-Newton matrix and NTK. In the context of over-parametrized networks, Go is for instance connected to the (empirical) Neural Tangent Kernel, which has been the focus of major line of research in the past few years [Jacot et al., 2018, Wang et al., 2022, Yang, 2020] as the NTK presents an interesting limit of infinite-widie networks. As result the asymptotic spectrum and the minimum eigenvalue of the NTK has been studied in [Nguyen et al., 2022, Liu and Hui, 2023], but the implications for width networks remain unclear.
Despite this and the other extensive work discussed above, a detailed theoretical study on the Gauss Newton conditioning of neural networks has been absent. In particular, there has been little work trying to understand the precise sources of ill-conditioning present within deep networks. Therefore, here we try to dissect the nature of conditioning itself, via first principle approach. We hope this will spark further work that aims to precisely get to the source of ill-conditioning in neural networks and, in longer horizon, helps towards designing theoretically-guides initialization strategies or normalization techniques that seek to also ensure better conditioning of the GN matrix.
4 Theoretical characterisation
The main part of this paper will focus on analyzing the conditioning of Go in Eq. (1) as prior work [Ren and Goldfarb, 2019, Schraudolph, 2002] has demonstrated its heightened significance in influencing the optimization process. We will further discuss an extension to Hg in Appendix Tying both bounds together yields a bound on the condition number of the overall loss Hessian in some simple setups.
Pseudo-condition number: Since the GN matrix of deep networks is not necessarily full rank [Sagun et al., 2017, Singh al., 2021], we will analyze the pseudo-condition number defined as the ratio of the maximum eigenvalue over the minimum non-zero eigenvalue. This choice is rationalized by the fact that gradient-based methods will effectively not steer into the GN null space, and we are interested in the conditioning of the space in which optimization actually proceeds. For brevity, we will skip making this distinction between condition number and pseudo-condition number hereafter.
4.1 Spectrum of Gauss-Newtor matrix
We will start with the case of linear activations. In this case a network with L layers can be expressed by (x) - w W x, with V E ga Xa,-1 for é = I,..., L and a k ag d. To facilitate the presentation of the empirical work, we will assume that the widths of all hidden layers the same, i.e. aę for all f I,..., L 1. Also, let denote by Σ Bdxd the empirical input covariance matrix. Furthermore, we introduce the shorthand-notation Whe = W w' for > and k < E, Wh = W ...W!" Then, Singh et al. [2021] show that the GN matrix can be decomposed as Go = U(I @ E where I, is the identity matrix of dimension h and U E Rp is given by: W @ W I @ WL-11)
E xxx!
U = (W2.L @ La
By rewriting U(I @ Σ = U( & EV2 @ E'/JUU,, where E1/2 the unique positive semi-definite square root of Σ and noting that AB and BA have the same non-zero eigenvalues,
5

---

have that the non-zero cigenvalues of Go are the same as those of
Go (Ix @ _ U @ )
(4)
where U E R kd is equal to
U = W
W @ W
(5)
Warm-up: the one-hidden layer case. In the case of one-hidden layer network, Fo(x) = WVx, have that Go WWT + V V To derive an upper bound of the condition number, we will lower bound the smallest eigenvalue Amin and upper bound the largest eigenvalue Amax Go) separately. Using standard perturbation bounds for matrix eigenvalues discussed in Appendix A, we obtain the following upper bound on the condition number:
I
Lemma 1. Let 3. = (W))i(WW//ee (i (W) + o
min (V)). Then the condition number GN for the one-hidden layer network with linear activations with m max k) is upper bounded by
min
0 maxx ( + o mux (V)
k( GG)) S k())
min (W) + o (V) = K ( (Bw xr (W) + (1- - -w)))())))) k()))).
(6)
Proof sketch. Choosing A WWT & E and B I. & Σ1/2V VV and i = j == 1 for the Weyl's inequality, i = = n for the dual Weyl's inequality and using the fact that WWT & and I & / // are positive semidefinite yield the result.
It is important to point out that the convex combination in Eq. (6) is crucial and more naive bound where we take the maximum of both terms is instead too loose, see details in Appendix E. Later on, will observe that the general case with L layers also exhibits comparable structure, wherein the significance of the convex combination becomes even more pronounced in deriving practical bounds.
Remark R2 (Role of the data covariance). Besides the above dependence in terms of the convex combination of the bounds, we also see how the conditioning of the input data affects the conditioning of the GN spectra. This is observed in Figure 19, where the condition number of the GN matrix is calculated on whitened and not whitened data. This observation might also shed light on why data normalization remains a standard choice in deep learning, often complemented by the normalization of intermediate layer activations.
4.2 The general L-layer case
Following our examination of the single-hidden layer case, we now broaden our analysis to include L- layer linear networks. As before, will first derive expression of the GN matrix and subsequently bound the largest and smallest eigenvalue separately to derive a bound on the condition number. Obtaining the GN matrix involves combining (4) and (5), which yields
Go -Ik= & E U(IK & 1
Σ wwL.HWett.. &
E
By repeatedly applying Weyl's incqualities, we obtain an upper bound on the condition number. Lemma 2. Assume that m > max k3 and that a == - (WL:++1). -o (W1:(-1) > 0 YE Then the condition number of the GN matrix of L-layer linear network can be upper-bounder in the following way:
1...., Let yi == 'ES at
n((G)) < <(E) EL_ Tex( (en(WLet1)33
t=
<x(E)
max ISKL
As mentioned earlier. we observe the same convex combination structure which, as we will soon see experimentally, is crucial to obtain bound that works in practice.
Empirical validation. The empirical results in Figure 2a show that the derived bound seems to be tight and predictive of the trend of the condition number of GN at initialization. If the width of the hidden layer is held constant, the condition number grows with quadratic trend. However, the condition number can be controlled if the width scaled proportionally with the depth. This gives another explanation of why in practice the width of the network layers is scaled proportionally with the depth enable faster network training.

---

Wvith: 800
Witth 1400
Width: (2 1)
Width:
200
20
(Go)
opper
2 100
10
2
Depth 2
Degth
2
6
6 Depthi
Depli
G(Go)
opper
(b)
(a)
Figure 2: a) Condition number at initialization under Kaiming normal initialization of GN Ks (o) and first upper bound derived in Lemma 2 and Eq.(7) for whitened MNIST as function of depth L for different hidden layer widths m for Linear Network over initializations. b) Scaling the width of the hidden layer proportionally to the depth leads to slower growth of the condition number (left) or improves the condition number with depth if the scaling factor chosen sufficiently large (right).
Figure 4: Adding skip connections between each layer for a general L-layer linear Neural Network.
x
WI
Wili
Widta:
Wothh: 1400
Furthermore, Figure 3 empirically demonstrates the importance of bounding the condition number as convex combination of the condition number of the weight matrices, as simply taking the maxi- mum makes the bound vacuous. This is due to a "self-balancing" behavior of the individual terms in Lemma 2, which is further elaborated in Appendix E. We show that the difference in magnitude be- tween each condition number is largely driven by their smallest cigenvalue. Thus at the same time, they also have smaller weight in the convex com- bination, making the overall condition number grow slower than the maximum bound would predict.
109
6
Depth I
Depth
apper Iouna
upgan board
Figure 3: Comparison of derived upper bounds in Lemma 2 for the condition number at ini- tialization for whitened MNIST over 20 runs. Note the logarithmic scaling of the y-axis.
4.3 L-layer linear residual networks
Following the examination of linear networks, our focus will now shift to the analysis of linear networks where introduce skip connection with weight between each layer, illustrated in
Figure 4. This results in residual network of the form (x)x = (W(L) + 31)... ... (W(1) + 31)x.. Given the architecture of the residual network, a substantial portion of the analysis conducted in Section 4.2 for the L-layer linear neural network can be repurposed.
The key insight lies in the realization that when the skip connection precisely bypasses one layer, implics a modification of Eq. (5) to U Ele W W (f Ø w
9 - where we define W (W* + 9I) (w' + -1) if I and w = (W 3D) T (w' + SI) if I < 1. I denotes the rectangular identity matrix of appropriate dimensions. Note, that we can apply the upper bounds derived in Lemma analogously to arrive at
x Go)
S R
x2 (W (2 (W S
max K² (W(Litt11 ( (7) ISESL
E=1
where "6
2
and analogously to the I.-layer case of == o2 WL++1) 2 min (Wi--1)
E for L = 1, L.
a
Let us now analyze how skip connections affect the condition number. Denoting the SVD of W U' note that W - +S' and therefore o VWW"+ 3I) = o; (W') + for all singular values of W Incorporating skip connections results in a spectral shift each weight matrix to the positive direction by magnitude of 3. Furthermore, will assume that the left and right
7

---

singular vectors of the layers in-between coincide, that is V - This assumption is fulfilled if the initialization values are sufficiently close zero [Saxe et al., 2013]. Then for each we have
e max w 3)2 (amax (w)) 8)²
x² ( L ) (W
I minn (W:) - 3) (amin (W") + 8)²
max (W:) + , 2
= III 1 mmin (W) +
(8)
omnn (W (W=) for all B > O, we can conclude that the second upper bound in Eq. (7) for residual networks is smaller than the second upper bound for linear networks in Lemma 2. We verify that this observation also holds for the actual condition number and the tight upper bound in Eq. (7)
Since maxx (W") (W*)+8 )+8 mmax (Wa)
be seen in Figure 5. The latter shows that adding skip connections improves the conditioning of the network. Furthermore, Figure 20 in the appendix shows that the condition number is improved more for larger / because this pushes the condition number towards as can be seen from Eq. (8). To conclude, the analysis of the condition number provides a rigorous explanation for the popularity of residual networks compared fully connected networks. This is in line with existing empirical results in the literature [He et al., 2016, Li et al., 2018, Liu et al., 2019].
Remark: extension to convolutional layers. Note that the analysis fully connected layers can also be extended to convolutional layers in a straightforward way by making use of the fact that the convolution operation can be reformulated in the form of matrix-vector product using Toeplitz matrices, as discussed for instance in Singh et al. [2023]. In this case, we can apply the same analysis as for fully connected networks. See Appendix B for more details.
5 Extension to non-linear activations
After the analysis of networks with a linear activation the previous section, we will extend our results to non-linear activation functions that satisfy (2)) (z))) for one-hidden layer networks Fx(x)= = Wo(Vx), Specifically, this extension includes all diece-wise linear activation functions such as ReLU or Leaky ReLU. For this purpose, we first rewrite the network output a super-position
of unit-networks Fa, (x) over the number of hidden neurons yn as
(x
Σ 1=1
Σ (V i=1
(9)
where W.: denotes the i-th column of W and Vi denotes the i-th row of V. Using the following lemma, we can then derive an expression for the Gauss-Newton matrix.
Lemma (Lemma 25 in Singh et al. [2021]) Let (x) (V..o(Vs.x) be a unit-network corresponding to i-th neuron, with the noneiiryyy such that o(2) = (2)22. Let X Ødxx denote the data matrix. Further, let A' E R=x* be defined as (A')s =
= 1,...,n
and zero elsewhere. Then the Jacobian matrix Vo (X) is given (in transposed form) by:
VoFo, (o XA 8 W., V..XA' O 0)
The Jacobian matrix of the full network is simply the sum over all units VoFo(X) En Vale, (X). Now that we have an expression for the Jacobian matrix, we can compute the GN matrix as Go = (X)(X)
Note that the non-zero eigenvalue of Go and Go = Vx) (X) E R Rinkkn are the same, for which we have
Go Σ VF TVF -
V.,
with G = X'X & W. W. +AX A
& I E RAnkkn since the mixed terms VF, V.F (X) with # j are zero due to the block structure of the Jacobian of the unit-networks. Using the mixed product property of the Kronecker product we obtain
Go Σ. m
W. Σm m
A'X V XA' & I..
(10)
8

---

Widti: 800
Width: 1000
Widtl: 1503
Withh: 3100
3000
100
6
4
Depth L
Degtti
Depti Z
Depilh L
type
type
Beslet
(Ga)
BesSet
FCNN
upper honnd
FCNN
opper bonnd
Figure 5: Comparison of condition number of GN x (GG) between Linear Network and Residual Network with 3 = 1 for whitened MNIST (left) and whitened Cifar-10 (right) at initialization using Kaiming normal initialization over three seeds. The upper bounds refer the first upper bound in Lemma 2 and Eq. (7), respectively.
To improve readability, we will write r E A'X V.. hereafter.
Leaky ReLU activation. Let's now consider the case where the non-linear activation is LeakyReL.U(a = maxfox, 2 for some constant a E [0, 1). Typically a is chosen to be close to zero, e.g. a = 0.01. Again, the condition number re( ((Go) can be upper bounded by bounding the extreme eigenvalues independently. By observing that all terms in Eq. (10) are symmetric, again apply the Weyl's and dual Weyl's inequality. However to get a lower bound larger than zero for Amin Go) a different approach is needed as W.. W. is rank-deficient and the same steps to bound smallest eigenvalue would lead to vacuous value of zero. Instead, we will use the following obser- vation that we can bound the extreme eigenvalues of the sum of a Kronecker product of PSD matrices A, B, for ..... m by Amin 1 (A, 3 B₂)) 2 minigism Amin (A,) Amin CE B:).
By first using Weyl's incqualities and subsequently ap- plying the above bound with A; A'X XA' and B, W., we achieve the following bound for the condition number for K6 GGo)
10'
Gra)
upper
Lemma 4. Consider an one-hidden layer network with Leaky-ReLU activation with negative slope [o. 1]. Then the condition number of the GN matrix defined in Equation (10) can be bounded
upper bound
10a
2000
Width m
0 max X o2 (W) + Amax (T)
K2 Go) S
(11)
Figure Condition number of a one-hidden layer Leaky ReLU network with a 0.01 and upper bounds for whitened MNIST over n = 500 data points. The upper bound refers to Eq. (11). Note that the y-axis is log scaled.
a² min (X) mii (W) Amin (T)
The proof can be found in Appendix H. We further empirically validate the tightness of the upper bounds subset of the MNIST dataset (n = 500), where we chose a 0.01, which is the default value in Pytorch [Paszke et al., 2019]. As can be seen in Figure 6, contrary to the linear setting the condition number increases with width. The upper bound also becomes tighter and more predictive with increasing width.
Comparison to linear network. By running the same setup for varying values of E [0, 1] can interpolate between ReLU (a = 0) and linear activation (a = 1) to see how the introduction of the non-linearity affects the conditioning. In Figure 23, which had to be deferred the appendix due to space constraints, we can see how reducing the value of a seems to consistently improve the conditioning of the GN matrix for the me-hidden layer case.

---

6 Conditioning under batch normalization
Based on the observation that conditioning of the input data affects the conditioning of the GN spec- trum, we also tested whether Batch normalization (BN) [Ioffe and Szegedy, 2015], which is a very commonly used normalization scheme, has a similar effect on the condition number. For this, the condi- tion number of the GN matrix was calculated for a one-hidden layer linear network with and without a Batch normalization layer. The experiment was run on downsampled and subsampled version of Cifar- 10. which was converted to grayscale with d = 64 and n 1000. The data was not whitened to see the effect of BN more strongly. As can be seen in Fig- ure 7. we indeed observe a clear improvement of the condition number when Batch normalization layers are added. Also, the trend of improved conditioning with increasing width remains after adding BN.
1000
betchnorm
BN
no BN
800
600
400
80
100 120 140
Width
Figure 7: Comparison of conditioning of the GN matrix for a one-hidden layer linear net- work with and without Batch normalization on downsampled Cifar- 10 data (d = 64, n = 1000) at initialization over 5 runs.
7 Discussion and conclusion
Summary. In this work, we derived new analytical bounds for the condition number of neural networks, showcasing the following key findings: a) The conditioning of the input data has a nearly proportional impact the conditioning of the GN spectra, underscoring the significance of data normalization. Empirical evidence further demonstrates that Batch Normalization similarly enhances the condition number. b) For linear networks, we showed that the condition number grows quadratically with depth for fixed hidden width. Also, widening hidden layers improves conditioning, and scaling the hidden width proportionally with depth can compensate for the growth. e) We showed how adding residual connections improves the condition number, which also explains how they enable the training of very deep networks. d) Preliminary experiments suggest that the ReLU activation seems to improve the conditioning compared to linear networks in the one-hidden layer case.
Interesting use cases of results. Through our analysis, highlighted that the condition number as a tool from classical optimization is also an attractive option to better understand challenges in neural network training with gradient-based methods. Especially, knowing how different architectural choices will affect the optimization landscape provides a more principled way to design the network architecture for practitioners, for instance how to scale the width in relation to the depth of the network. The paper also gives justification of why pruned networks are more difficult to train as they have worse conditioning. Although this is not our focus, is possible that our analysis could inspire better techniques for pruming neural networks.
I. Limitations and future work. We made first step toward understanding the impact of different architectural choices on the conditioning of the optimization landscape. However, there are still many design choices, that have not been covered yet, such as an extension to non-linear networks for arbitrary layers, other architectures, such as transformers, and analytic bounds for normalization schemes, such batch or layer normalization, which we will leave future work. Another limitation of our current work is that the derived upper bounds are agnostic to the training dynamics. Therefore, they cannot distinguish the difference between random initializations and solutions of deep learning models after convergence. Incorporating training dynamics into the upper bounds would allow us to characterize solutions found by different architectures, which is left for future work. Another future direction is to extend the analysis to the Generalized relevant for training with cross-entropy loss.
matrix, which is particularly
Acknowledgements
Aurelien Lucchi acknowledges the financial support of the Swiss National Foundation, SNF grant No 223031. Sidak Pal Singh would like to acknowledge the financial support of Max Planck ETH Center for Learning Systems.
10

---

References
Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
James Martens and Roger Grosse. Optimizing neural networks with krantcder-factored approximate curvature, 2020.
Vineet Gupta, Tomer Koren, and Yoram Singer. Shampoo: Preconditioned stochastic tensor optimiza- tion. In International Conference on Machine Learning, pages 1842-1850. PMLR, 2018.
Hong Liu, Zhiyuan Li, David Hall, Perey Liang, and Tengyu Ma. Sophia: A scalable stochastic second-order optimizer for language model pre-training. 2023.
Yizhang Lou, Chris E Mingard, and Soufiane Hayou. Feature learning and signal propagation in deep neural networks. International Conference on Machine Learning, pages 14248 14282. PMLR, 2022.
Utku Evci, Fabian Pedregosa, Aidan Gomez, and Erich Elsen. The difficulty of training sparse neural networks. arXiv preprini arXiv: 1906. 10732, 2019.
Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International conference on machine learning, pages 448-456. pmir, 2015.
Tim Salimans and Durk Kingma. Weight normalization: A simple reparameterization accelerate training of deep neural networks. Advances in neural information processing systems, 29, 2016.
Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E. Hinton. Layer normalization, 2016.
Yuxin Wu and Kaiming He. Group normalization. In Proceedings of the European conference on computer vision (ECCV), pages 3-19, 2018.
Takeru Miyato, Toshiki Kataoka, Masanori Koyama, and Yuichi Yoshida. Spectral normalization for generative adversarial networks. arXiv preprint arXiv: 2018.
Guoliang Kang. Jun Li, and Dacheng Tao. Shakeout: A new regularized deep neural network training scheme. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30, 2016.
Li Wan, Matthew Zeiler, Sixin Zhang, Yann Le Cun, and Rob Fergus. Regularization of neural networks using dropconnect. In International conference on machine learning, pages PMLR, 2013.
Sidak Pal Singh, Gregor Bachmann, and Thomas Hofmann. Analytic insights into structure and rank of neural network hessian maps. Advances in Neural Information Processing Systems, 34, 2021.
Vladimir Vapnik. Principles of risk minimization for learning theory. Advances in neural information processing systems, 4, 1991.
Nicol N. Schraudolph. Fast curvature matrix-vector products for second-order gradient descent. Neural Computation, 14:1723-1738, 2002.
Levent Sagun, Utku Evci, V Ugur Guney, Yann Dauphin, and Leon Bottou. Empirical analysis of the
hessian of over-parametrized neural networks. arXiv preprint 1706:11006004544 2017.
James Martens. New insights and perspectives on the natural gradient method. Journal of Machine Learning Research, 21(16)):1-76, 2020.
Aleksandar Botev. The Gauss-Newton matrix for Deep Learning models and its applications. PhD) thesis, UCL (University College London), 2020.
Jaehoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. Advances in neural information processing systems, 32, 2019.

---

Sepp Hochreiter and Jürgen Schmidhuber. Flat minima. Neural computation, 9(1::1 42, 1997.
Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Peter Tang. On large-batch training for deep learning: Generalization gap and sharp minima. arXiv preprint arXiv:1609.0488 2016.
Gintare Karolina Dziugaite and Daniel M. Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data, 2017.
Pratik Chaudhari, Anna Choromanska, Stefano Soatto, Yann LeCun, Carlo Baldassi, Christian Borgs, Jennifer Chayes, Levent Sagun, and Riccardo Zecchina. Entropy-sgd: Biasing gradient descent into wide valleys. Journal of Statistical Mechanics: Theory and Experiment, 2019(12):12401 2019.
Laurent Dinh, Razvan Pascanu, Samy Bengio, and Yoshua Bengio. Sharp minima can generalize for deep nets. In International Conference on Machine Learning, pages 1019-1028. PMLR, 2017.
Diego Granziol. Flatness is a false friend, 2021. URL http:pp::/poeeeeeere.eeee/oorooa I6- 16-3mg29P6..
Maksym Andriushchenko, Francesco Croce, Maximilian Müller, Matthias Hein, and Nicolas Flam- marion. A modern look at the relationship between sharpness and generalization. arXiv preprint arXiv:2302.07011 2023.
Pierre Foret, Ariel Kleiner, Hossein Mobahi, and Behnam Neyshabur. Sharpness-aware minimization for efficiently improving generalization, 2021.
Zhewei Yao, Amir Gholami, Qi Lei, Kurt Keutzer, and Michael W Mahoney. Hessian-based analysis of large batch training and robustness to adversaries. Advances Neural Information Processing Systems, 31, 2018
Aitor Lewkowycz, Yasaman Bahri, Ethan Dyer, Jascha Sohl-Dickstein, and Guy Gur-Ari. The large learning rate phase of deep learning: the catapult mechanism. arXiv preprint arXiv:2003.022.5. 2020.
Behrooz Ghorbani, Shankar Krishnan, and Ying Xiao. An investigation into neural net optimization via hessian eigenvalue density, 2019.
Zhewei Yao, Amir Gholami, Kurt Keutzer, and Michael W Mahoney. Pyhessian: Neural networks through the lens of the hessian. In 2020 IEEE international conference on big data (Big data), pages 581-590. IEEE, 2020.
Jeremy M Cohen, Simran Kaur, Yuanzhi Li, Zico Kolter, and Ameet Talwalkar. Gradient descent on neural networks typically occurs at the edge of stability. arXiv preprint wrXiv:2103.00063 2021.
Daniel Beaglehole, Peter Súkeník, Marco Mondelli, and Mikhail Belkin. Average gradient outer product as mechanism for deep neural collapse. arXiv preprint arXiv:2402. 13728, 2024.
Zhewei Yao, Amir Gholami, Sheng Shen, Mustafa Mustafa, Kurt Keutzer, and Michael W. Mahoney. Adahessian: An adaptive second order optimizer for machine learning, 2021.
Wu Lin, Felix Dangel, Runa Eschenhagen, Kirill Neklyudov, Agustinus Kristiadi, Richard E Turnne, and Alireza Makhzani. Structured inverse-free natural gradient: Memory-efficien & numerically- stable kfac for large neural nets. arXiv preprint 122.0233.. 2023.
Yann LeCun, John Denker, and Sara Solla. Optimal brain damage. Advances in neural information processing systems, 2, 1989.
Babak Hassibi, David G Stork, and Gregory J Wolff. Optimal brain surgeon and general network pruning. In IEEE international conference on neural networks, pages 293-299, IEEE, 1993.
Sidak Pal Singh and Dan Alistarh. Woodfisher: Efficient second-order approximation for neural network compression. Advances in Neural Information Processing Systems, 33:18098-18109 2020.
12

---

Zhen Dong, Zhewei Yao, Amir Gholami, Michael Mahoney, and Kurt Keutzer. Hawq: Hessian aware quantization of neural networks with mixed preccisoo,, 2019.
Elias Frantar, Sidak Pal Singh, and Dan Alistarh. Optimal brain compression: A framework for accurate post-training quantization and pruning, 2023.
Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions, 2020.
Roger Grosse, Juhan Bae, Cem Anil, Nelson Elhage, Alex Tamkin, Amirhossein Tajdini, Benoit Steiner, Dustin Li, Esin Durmus, Ethan Perez, Evan Hubinger, Kamilé Lukošiūté, Karina Nguyen, Nicholas Joseph, Sam McCandlish, Jared Kaplan, and Samuel R. Bowman. Studying large language model generalization with influence functions, 2023.
Jeffrey Pennington and Yasaman Bahri. Geometry of neural network loss surfaces via random matrix theory. In International conference on machine learning, pages 2798-2888 2806. PMLR, 2017.
Arthur Jacot, Franck Gabriel, and Clément Hongler. The asymptotic spectrum of the hessian of dnn throughout training. arXiv preprint arXiv:1910.02887 2019.
Levent Sagun, Leon Bottou, and Yann LeCun. Eigenvalues of the hessian in deep learning: Singularity and beyond. arXiv preprint arXiv: 1.07476, 2016.
Sidak Pal Singh, Thomas Hofmann, and Bernhard Schölkopf. The hessian perspective into the nature of convolutional neural networks. arXiv preprint arXiv:2305.0080 09088, 2023.
Yikai Wu, Xingyu Zhu, Chenwei Wu, Annie Wang, and Rong Ge. Dissecting hessian: Understanding common structure of hessian in neural networks. arXiv preprint arXiv:2010.04261, 2020.
Zhenyu Liao and Michael W Mahoney. Hessian eigenspectra of more realistic nonlinear models. Advances in Neural Information Processing Systems, 34:201 04-201 17, 2021.
Andrew M Saxe, James L McClelland, and Surya Ganguli. Exact solutions to the nonlinear dynamics of learning in deep linear neural networks. arXiv preprint arXiv: 131..623/, 2013.
Wei Hu, Lechao Xiao, and Jeffrey Pennington. Provable benefit of orthogonal initialization in optimizing deep linear networks. In International Conference on Learning Representations, 2020.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine-learning
practice and the classical birs-variance trade-off. Proceedings of the National Academy of Sciences, 116632):1584--158544 July 2019. ISSN 1091-6490. doi: 10.1073/pnas. 1903070116..
Sidak Pal Singh, Aurelien Lucchi, Thomas Hofmann, and Bernhard Schölkopf. Phenomenology of double descent in finite-width neural networks. In International Conference Learning Representations, 2022.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems, 31, 2018.
Sifan Wang, Xinling Yu, and Paris Perdikaris. When and why pinns fail to train: A neural tangent kernel perspective. Journal of Computational Physics, 449:110768 2022.
Greg Yang. Tensor programs ii: Neural tangent kernel for any architecture. arXiv preprint arXiv:2006. 14548, 2020.
Quynh Nguyen, Marco Mondelli, and Guido Montufar. Tight bounds on the smallest eigenvalue of the neural tangent kernel for deep relu networks, 2022.
Chaoyue Liu and Like Hui. Relu soothes the ntk condition number and accelerates optimization for wide neural networks. arXiv preprint arXiv:2305.0881.1 2023.
Yi Ren and Donald Goldfarb. Efficient subsampled newton and natural gradient methods for training neural networks. arXiv preprint arXiv:1906.0224 02350.000033......... 2019.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEFE conference on computer vision and pattern recognition, pages 770-778, 2016.
13

---

Hao Li, Zheng Xu, Gavin Taylor, Christoph Studer, and Tom Goldstein. Visualizing the loss landscape of neural nets. Advances neural information processing systems, 31, 2018.
Tianyi Liu, Minshuo Chen, Mo Zhou, Simon S Du, Enlu Zhou, and Tuo Zhao. Towards understanding the importance of shorteut connections in residual networks. Advances in neural information processing systems, 32, 2019.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32, 2019.
Hermann Weyl. Das asymptotische verteilungsgesetz der eigenwerte linearer partieller differentialgle- ichungen (mit einer anwendung auf die theorie der hohlraumstrahlung), Mathematische Annalen, 71(4):441 479, 1912.
Alex Krizhevsky, Geoffrey Hinton, al. Learning multiple layers of features from tiny images. 2009.
Roman Vershynin, Introduction to the non-asymptotic analysis of random matrices. arXiv preprint arXiv:1011.3027, 2010.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. In Proceedings of the IEEE international conference on computer vision, pages 1026-1034, 2015.
Jack W Silverstein. The smallest eigenvalue of large dimensional wishart matrix. The Annals of Probability, pages 3364-1366 1985.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(1)):228--2324, 1998.
14

---

A Standard pertubation bounds for matrix eigenvalues
A.1 Weyl's inequality and dual Weyl's inequality
In this section, we first briefly review the Weyl's incquality and its dual form. We then demonstrate how these inequalities can used to bound the extreme eigenvalues and thus the condition number of the sum of two Hermitian matrices A, B by the extreme eigenvalues of A and B.
Lemma 5. Weyl [1912] Let A, B E R be two Hermitian matrices, and let X .... An. denote the ordered eigenvalues, then the Weyl's inequality and dual Weyl's 's inequality state that
(A) + (B), ú,j 1, n. A + B) S (A) + A (B), i,j 1. A (A
(Weyl)
(Dual Weyl)
In the following, we derive an upper and lower bound the condition number of a symmetric matrix A, for which we have
Amax (axxx(A)) (A)l
<(A)
AAmin (A)l
Recall that given a Hermitian n X n matrix A, we can diagonalize it by the spectral theorem. We obtain the following sequence of real eigenvalues
(A) 2 (2) ... (A).
We will make use of the Weyl's inequality and the dual Weyl's inequality to bound the eigenvalues of the sum of two Hermitian matrices A B.
From Lemma 5, we obtain the following inequalities: From Weyl's inequality we have
(A + B) (1 + (B) An A + B) S (A) + (B), for SiiS S.Ss
From the dual Weyl's inequality we have
(A + B) 2 An- (A) + (B), for 0 Siinn
Am (A + B) 2 An (A) + A, (B).
Hence, we can find a lower and upper bound for the condition number of + B
maxos/5n-1 (A) + A1+, (B) in (A) A1+ (B))]
Amax(()= + Amax B
S <(A + B)
<
(12)
Amin (A) + Amin (B)
A.2 Further bounds for extreme eigenvalues for positive semidefinite matrices
For square matrices A E IRPXP, B [2*4, denote by A Ap the eigenvalues of A and by Mi...., My the eigenvalues of B listed by multiplicity. Then the eigenspectrum of A @ B E RPPXp4 consists of the eigenvalues
App i= i =
Note that if A, B additionally positive semidefinite (PSD), we have the following equality for the largest and smallest eigenvalues of A & B
Xmax (A X B Amax (A) Amax (B)
(13)
Amin
A
B
Amiin (A)Amin (B).
(14)
Furthermore, it follows from the sub-multpplicativity of the matrix norm that for square, PSD matrices A, B of same dimensions it holds that
Amax (AB) < Amax (A) Amax (B)
Amin (AB) > Amia (A) Amin (B).
15

---

B Extension of analysis to convolutional layers
The analysis fully connected layers be extended convolutional layers in straight forward way, by using the fact that the convolution operation can be reformulated in the form of a matrix- vector product using Toeplitz matrices, as discussed for instance in Singh al. [2023]. This would mean that we can apply the same analysis as for fully connected networks. For completeness we will discuss how below how the convolution operation further details, the readers is referred to Singh et al. [2023].
be rewritten as a matrix-vector product. For
Consider convolution operation W of input E' with m filters of size k S d. which organized in the matrix W E m For simplicity a stride of 1 and zero padding is assumed. Let - E R denote the vector formed by considering the indices j to & 1 of the original vector R.. In this case, the convolution operation can be written
I X1s)
(Wi xa-k+1dd)
(Dmx(d-+t1)
W =
(W me; X1:k)
W me. Xd
where Wi, denotes the i-th row of W.
Let us further introduce Toeplitz matrices W. m u-r for each filter with T == toep( Wi., E R odd=x+ such that,
Wil
W ak
0
T.
W
Wik ik
0
Wa
W
Finally, by stacking the Toeplitz matrices a row-wise fashion, that is
TW
TW
pmmld-+11xdd
Ww. m.
we see that the matrix multiplication of T with an input x gives the same result as vectorizing the convolution operation row-wise, i.e.
vec, (W + x) T x.
For linear network with L hidden layers, each of which is a convolutional kerne,, the network function can be formally represented as
Fo(x) = W(L+1) * W(L) *.... (1 xx
(15)
where the parameters of each hidden layer é are denoted by VX(e) E R is the number of output channels, m the number input channels, and ke the kernel size. As we assumed x to be one-dimeni, we have mo = 1.
Similar single convolutional operation, the output of single convolutional layer can be expressed via Toeplitz matrices. The Toeplitz matrix associated with the b-th convolutional layer Wi() can be expressed by
wif T
(imy-1))
T(0
E B mmedexme-dde
myle (le
wile T (meime-ll 13
where v)(e) (3.f)*
k refers the ji, fibre of y)( and WWO Rdexde- to itsassociated Toeplitz matrix. Now, the network function can be equivalently written as Fo(x) T ((+1))((1)) ...
tocp(W (.) (1.)).) de-1)
(16)
16

---

MNIST whitened, n=1000, linear CNN
Kernel size
Kernel
Kernel 11
10
type
K(Ga)
K(Go)
upper bound
10a
2
3
4
5
5
2
Number of filters
Number filters
Number filters
Figure 8: Experiments the condition number of the Gauss Newton matrix at initialization for linear two-layer CNN at initialization on a random subsample of n=1000 of MNIST, whitened, with varying kernel size and number of filters. We the condition number (in analogy to depth in MLPs) and the kernel size improves conditioning (in analogy width in MLPs).
trend where the number of filters increases
We further provide experiments on linear CNNs in Figure initialization showcasing that we can observe similar trends where the number of filters increases the condition number of the Gauss Newton matrix (in analogy to depth in MLPs) and the kernel size improves conditioning (in analogy to width in MLPs).
C Sensitivity of condition number on choice of smallest eigenvalue
This work considers the pseudo condition number of some matrix A E R=**, which is the ratio Amar(A) (A)
of the largest eigenvalue over the smallest non-zero eigenvalue Auz.inn (A) If A is of full rank, the pseudo condition number is equivalent to the condition number. However, if A is rank deficient, has to be typically estimated numerically if the rank is not known analytically. Based on the numerical estimation of the matrix rank, the smallest eigenvalue chosen accordingly and the pseudo condition number is calculated.
In this section we evaluate the sensitivity of choice of the smallest eigenvalue on the resulting pseudo condition number. This is illustrated in the example of a 1-hidden layer network with ReLU activation function and a hidden width m 20 at initialization and after 100 epochs of training. The details of this experimental setup are further specified in Appendix I.2.
In Figure 9 we can see that depending on the eigenvalue distribution, the condition number can be quite robust (Epoch=O), but also very sensitive (Epoch=100) to the numerical matrix rank estimation.
Orderrd spectram by magnitude
Sensitivity of matrix rank estimetion r
Condition number K
Epoch=0
10a
10
Epoch= 100
10-8
Aus
10
10
Epoch=00
Epoch=100 100
10-21
10
Ansmmis
2000
4000
6000
8000
10000
dc(G)
sk/G)
rk(G)
+k(G)
Figure 9: The spectrum of the GN matrix ordered by magnitude at initialization and after 100 epochs. The star marks the smallest non-zero eigenvalue, which is determined by the computed matrix rank (left). Sensitivity of condition number as function of the matrix rank (right).
17

---

D Evolution of the condition number during training
We conducted experiment to track the condition number and evaluate how tight the upper bound is throughout training. For this we trained a 3-layer linear network with a hidden width of m 500 with three different seeds for 5000 epochs with SGD with a mini-batch size of 256 and a constant learning rate of 0.2 on subset of Cifar- 10 (n 1000) [Krizhevsky et al., 2009], which has been images and whitened. The network was trained on a single NVIDIA GeForce RTX 3090 GPU and took around 5 minutes per run. The condition number was computed the explicit formula Lemma on CPU and took around minutes. The condition number and the upper bound shown in Figure 10 together with the training loss. We make the following two observations: The condition number takes values in the range of 6 to 12 throughout training, which corresponds to maximal change of around 50% of the condition number initialization. This indicates that the condition number at initialization can be indicative how the conditioning is along the optimization trajectory. 2. The upper bound remains tight throughout training, which highlights that it can provide reliable information about the condition number the Gauss-Newton matrix throughout training.
downsampled to 3 x
0.10
12
lype
x(Go) upper bound
Condition number
Training loss
0.09
10
0.08
0.07
2000
2000
4000
epoch
epoch
Figure 10: Training loss (left) and corresponding evolution of the condition number throughout training for three seeds. The shaded area the figures corresponds to one standard deviation from the mean.
18

---

E Understanding the difference between the convex combination bound and the maximum Bound
In Lemma we have seen that the upper bound of the condition number can be expressed in terms of a convex combination of the condition number of the weight matrices. this section, will elucidate the "self-balancing" behavior of the individual terms in Lemma 2. For completeness, let us restate Lemma 2 here again:
Lemma 2. Assume that >> max (d, k) and that a == o (WLtt+1) o (WI--1) > 0 or 1...., L. Let "ie == Ei= can be upper-bounded the following way:
max(d,
Then the condition number of the GN matrix of a L-layer linear network
N0 GG)) S <<()) E Tek (WwttWt))) ) <x(2) ISESL
max ((W
By looking at the individual values of x² WL+++1 and oin (WL++1) and similarly x²2 (W(W ( and (wi:: (WI:f-1) over l I..... L for networks increasing depth L, we can see the 'self- balancing' behavior in Figure 11 for downsampled MNIST (d 196) over 10 runs and neurons per hidden layer. Note that this behavior is also consistent for different widths m, input dimension d, and output dimension k. By first looking at the first row, observe that x² (W1:(1) (top left) dominates the product of each term Lemma and follows an exponential growth rule in (note the log scale of the y-axis). By looking the second row, the smallest singular value of x² (W1+-1) (bottom left) is decreasing exponentially, leading to the saaf-bblancing' behavior of the condition number. The same observation also holds for W1.++1 but since the number of weight matrices decreases with f this leads to mirrored plot. The "self- 'self-balancing" behavior can be seen below Figure for ease of reading, where the individual terms of Lemma plotted with and without the weighting factor Ye-
300
that the same time,
6 X 10P
L
10
L
X 10
10
2.0
3 x 10P
4.0
5.0
4.0
2 x 10P
8.0
10P
0
8
2
65
8
E
109
109
10
1.0
min (W/t-1))
2.0
10
1.0
6 10
10
2.0
8.0
10-1
4 x 10
10
2.
8
Figure 11: Condition number and smallest eigenvalue of W1:e-1 (first column) and W L:6+1 (second column) for downsampled MNIST 196) for three seeds. Shaded area corresponds to one standard deviation. Note that the y-axis is log-scaled at the different limits for each subplot.
19

---

109
1
L
104
10
20
2.0
6.0
6.0
104
10"
4
0
2
6
Figure 12: Condition number of weight matrices with and without weighting factor Ye for downsam- pled MNIST (d 196) for three seeds, which highlights the 'self feffbbalacingg effect of the weight condition number. Note that the y-axis is log-scaled and both plots have different limits. Shaded area corresponds to standard deviation.
Conditioning of functional Hessian for one-hidden layer network
Consider the case of a one-hidden layer linear network Fx(x) WVx, with x E Rd W E Rx and V E Rm and some corresponding label y E R Under the assumption the MSE loss, the functional Hessian is then given as:
O Kemx kmm.
28 2
I
HE
(17)
Ω
& Im
dm
where Ω x ] E Rxd the residual-input covariance matrix, with 6x.y == F (x)
being the residual. Since would like to estimate the spectrum of Hp, let suppose that it has eigenvector v
a x b
Assuming that À is the corresponding eigenvalue, we have the following
eigenproblem:
Hp ( =
(Pcod) a
& b c
Let's start with the guess that b = d, then we obtain the following equations:
Aa = Sc and Ac = Ω a.
Solving this gives:
Ω 1cc= X and 22 a x2a.
Hence, and c are simply the cigenvectors of ΩN and Ω respectively. Both these matrices have the same non-zero cigenvalues, and the resulting eigenvalues for the functional Hessian nothing but the square root corresponding eigenvalues
the matrix Ω S2 with both positive and negative signs. About b d: We still have degree of freedom left in choosing them. Any m-orthogonal vectors with unit norm would satisfy the above equation and, for simplicity, we can just pick the canonical basis vectors in m
Teacher-Student setting Let us now further assume Teacher-student setting, i.e. y Zx for some (WV Z] (WV Z)Σ.
Z E Rixd In this case note that Ω = E[WVVx y)x
Now recall the definition of the condition number xl (HF)
H
H and using the observation
20

---

from above we have that
H Fl max Hp) max (WV- -)
S max
WV 2) -mmax ()
H p 1lll min (Hp) min (WV- Z)Σ)
2 min
WV Z) Amin E).
Therefore we have
K <(HF) S <WWV -Z) x(().
(18)
Similar to bounding the condition number of the GN matrix, we can also clearly see a dependency on the conditioning of the input covariance.
G Concrete bounds at initialization for one-hidden layer linear network
G.1
Non-asymptotic bound
Based on the upper bound in Eq. (6) derived for the one-hidden layer linear network, we can look at how this bound behaves concretely at initialization. If we assume the entries of W and V to be i.id. Gaussian entries, then WWT and V will be Wishart matrices, for which asymptotically the distribution of the smallest and largest eigenvalues are known. Also there known non-asymptotic bounds to bound the maximum and minimum singular value of a Gaussian matrix:
Lemma 6 (Corollary 5.35 in Vershynin [2010]). Let A be an N x n matrix whose entries are independent standard normal random variables (0, 1). Then for every t 2 0, with probability at least 1 exp((= ) one has
V min (A) S max (A) S N Vn+
(19)
Using the Lemma above and union bound, we can also derive non-asymptotic bound for the condition number of the GN matrix under the assumption that we have a wide layer m > max(d, k)::
Lemma 7. Assume that 2 max(d, k) and that the entries of V E R.xdd W E kx are initialized Gaussian ii.dd with Viz (O, dt) and Wi, ~N(0, then with probability least
1 - 8exp(- L the condition number of the GN matrix x k(Go) is upper bounded by
r6 (G) Amax (Go) S x2
(0 ( Vb +)² (. vd VV t)3)
Amin (Go)
(o (1 Vk 1)² + ( vd t)2)
Proof. Assume that V E Raxdd W E R are initialized Gaussian i.i.d. with Vij ~ ~((,o and Wij ~ NN o.), then the bounds in Lemma are scaled with dy and ow respectively:
aolvm- Vd 1) < mmin (V) S mmax (V) S a. a.(ym + vd+1)
Tu (vm Vk t) S mmin (W) S max (W) S ow +k+
Further noting that
Amnn (VT T V) = o (V), Amaxe (VTV = 0 - (V) Amin WWW = 2 (W) Amax (WWT) 2 max (W),
get the following non-asymptotic upper respectively lower bounds for the extreme eigenvalues with probability at least 2 exp((-5p = each:
Aunin V V) 2 v.m Vd t)3 Amax. (V V) s o.(mm Vd t)²
Amin WW ) 2 0 (vm VTe t)2
Amaix (WT)) & di vi + t)²
Using union bound, get the upper bound for the condition number of the GN matrix.
21

---

Based on the bound derived above, we can understand how the condition number behaves under initialization schemes used in practice. Consider the setting of a wide hidden layer m > max (d, k}. in which the input dimension is much larger than the output dimension, i.e. d > k. This is for instance the case for image classification, where the number of image pixels typically much larger than the number of image classes. A popular initialization scheme is the one proposed in He et al. [2015], commonly known as the Kaiming/Hc initialization, which corresponds to o o = in our case. Hence, under the assumption of m >> d, we will have of
> of and therefore
(o V +f vd+
x(Go) S xx(>)
(20)
(o vk t/2 o Vd t)3)
(Vm + vd
(Vm t)? k
(21)
G.2 Asymptotic bound
To complement the analysis, we can also derive an asymptotic bound for the condition number when d, k, m go to infinity together.
For this, will use result from Silverstein [1985], in which it is shown that the smallest eigenvalue of the matrix M,- = UU, where U, E R=** composed of i.i.d. AN(0, 1) random variables, converges to (1 /y)² as + oc, while - E (0, 1) as - oc. This corresponds to the case in which the hidden layer is larger than the input and output dimensions, that is 2 max(d, k))
Similarly it can be shown that Amax + (1 + v0)² for all 0 for + 20.
Using this result we can bound the extreme eigenvalues of WWT and V V at initialization. Assuming that the entries of W and V are entry-wise independent normally distributed Waj we get for
(00, ) Vi ~ NN0,, (for instance o 1 of d for d, ls m + 0o:
2
Amin (Wi )- = 0z m Amin
1 U UT Um
k,m
o m
1
h
m
m
m
2
Amax WWT) o2 m Amin
1 Un UT
k.m-+00
00 m
1
V
k
m
m
Amin (VVT)= = m Aminn
1 Um UT
d,m d.m-000
0. m
1 1
d
2
Amax VVT)= = = 0g. m Amax
1 L Um
d.
0 m
1+
Thus, in the asymptotic case in which the hidden layer is wide m max(d, k), we can derive the following upper bound for the condition number:
2
1
k m
o
1 + V
k(Go) S C d.k.m-
m
k{E)
(22)
2
+
o
1
v
m
m
Again, if m >> maxfd, k} we also have in the asymptotic limit that K( (Go)) x k()).
22

---

H Proofs
Lemma 1. Let Bu o (W)/(o min (W) + min (V)). Then the condition number of GN for the
one-hidden layer network with linear activations with m > max{d, k) is upper bounded by
o (W) + o (V)
R ((GG))= S ((E)
R x<E) (Bw k: ()2 -1- Bw) (1-33) (6)
min (W) o2 min (V)
Proof.
Note that we have by the Weyl's in dual Weyl's inequality that
Amax Go) Amax WWWT
@ E+L
E
V
VE V < Amax (WW)
X Σ) + Amax (I ② E VVV/2 V
Amin (o) Amin A (WWT& T @ E 1 VE 2 Amia (WW] T
2 Σ) + Amin (I & E V
Then note that WW & E and I & V V are positive semidefinite and using the equality for the extreme eigenvalues of Kronecker products in Eq. (13), we have the bound
Amax WW Σ) + Amax [I & E /E Amax (WW] Mmmx (E) + Amax 11/2 VE
Amin (WWT Σ Amin (I, E // Amin (WW)) ) ()) + Amin
(2 VΣ
Using the submultiplicativity of the matrix norm we get the upper bound
Amax (BxT))WT)))) Amax (VTV) mmaa (WWT) + Amin AainnVTV (VTV)
K( Go) S R E
Finally, by noting that we have >; (WWT)= (W) and \;(V V) = (V for i E (min, max because we have m > max(d, k} yields the result.
Lemma 4. Consider one-hidden layer network with Leaky-ReLU activation with negative slope E [0, 1). Then the condition number of the GN matrix defined in Equation (10) can be bounded as:
02 max (X) 02 max (W) + Amax (T)
K: x(Go)=
(11)
a² o2 min (X) (W) + Amiu (T)
Proof. As before we will bound the condition number by separately bounding the extreme eigenvalues first.
First, recall the expression of the GN matrix as
Go Σ A'x W. Σ A'X V & I
and note that we can apply the Weyl's and dual Weyl's inequality because (A X XA WT.) and
V TV,
XA') @ I are symmetric, yielding the following bounds:
Amin Go) Z Aminn
Σ (A'X
XA') x(AxXXxa))
@ (W.. WT,))
+ Amin
Σ VV. &
Amax (Go) S Amax
Σ (A'X XA') @ (W..W..))
+ Amax
Σ V XA') 2 I
Then we can bound the first term by using the fact that for the sum of a Kronecker product of PSD matrices A,, B, for i = 1,..., have Amia (Em (A, @ B,)) 2 minigism Amin (A,)
Auin
(E m B;) to get
m
m
Amin
Σ (A'XT @ (W.,WT,))
> Amin (A'XTXXX XA))
Σ
W. W.T
> a² Amin (X X) X)mmin (WWT)
(23)
a² 2 (X)02 min (W)
(24)
23

---

by noting that A' only contains or -a on its diagonals in case of Leaky-ReLU activation and W. W WW Analogously, have
e (W.. S mmax((X) (X)o max (W).
Xmax
This yields the first upper bound.
To get the second upper bound, we need to further bound the second term. For this, note that
Amnin Eax S(A.VV.VVV V.. v..'A 8 I
Amin
V
V V. XA
m
2 2 Amin
Σ
X [ v)
a Amin
X
V
Amin
(
(25)
Analogously have
Amax E V., XA') @ LI Amax (VVVVX)
(26)
which gives the second upper bound.
H.1 Further details on the effect of condition number at initialization on convergence rate
We present here further details of the modified analysis of GD for strongly convex functions to study the effect of the condition number initialization on the convergence rate, where use local constants μkk) and L(k) instead the global smoothness and Lipschitz constant, respectively. Let denote the Lipschitz constant and let the smoothness constant be denoted by μ. Furthermore, let the step size be such that 77 I 7,- Then by the definition of gradient descent we get
|
1-112-
0c
0" V 10x)
0
1-112 2m f (0%) (0: 0¹) I (02)
Strong convexity
(1 nk41| | 0₂ 0- 2m (s(x)) - f(0)) + v (Ox) [|2
Smoothhess
I (1- (1-7 10 11 2m - f(0))) 2nf(0) f(0)))
= (1 m) - 112 27p - mn (0)
- f(0))
Since we assumed that T s t. the last term is negative. Therefore:
0 - 11 s (1 Tk - 1
(27)
So by recursively applying (27) and replacing ya by the local smoothness constants μ(k):
k-1
0 - 1
II 1=0
mi(i))] 11
(28)
One can see the effect of (x(0) the bound, which is even more dominant when p(k) changes slowly. Of course, the effect of (00) attenuates over time, and that's 's why we are talking about a local effect.
24

---

I Further experimental results
L1 Further experiments on pruning networks at initialization
We repeated the experiments of pruning the weights at initialization for different architectures, includ- ing a small Vision Transformer (Figure 13), a ResNet20 (Figure 14), ResNet32 (Figure 15), VGG5Net* (Figure 16) and Feed-forward network (Figure 17). The default initialization from PyTorch [Paszke et al., 2019] was used. In all setups, the weights were pruned layer-wise by mag- nitude and trained on subset of Cifar-10 of n 1000 images. The ViT was trained with AdamW with a learning rate of le and weight decay le 1e- The ResNer20, ResNet32 and VGGnet were trained with SGD with momentum 0.9 and weight decay of 10-1 and learning rate of 0. with step decay to 0.01 after 91 epochs for ResNet20 and ResNet32 and after 100 epochs for the VGGnet, The Feed-forward network was trained with SGD with constant learning rate of 0.01. All networks were trained with a mini-batch size of 64, the ResNet20, ResNet32 and the Feed-forward network were trained on a single NVIDIA GeForce RTX 3090 GPU and the ViT on single GPU NVIDIA GeForce RTX 4090. The training time was around hour for each setup. The computation of the condition number was run in parallel on GPU and took around 8 hours for each pruning rate of each network.
1.2 Effect of width conditioning and convergence speed
For one-hidden layer feed-forward network with ReLU activation, we empirically examined the effect of the hidden width on both the conditioning and the convergence speed when trained on subset of MNIST (n = 1000). The networks were trained with SGD with fixed learning rate, which was chosen via grid-search, on a single NVIDIA GeForce RTX 3090 GPU, The learning rate was 0.3 for the networks with width 15 and 20 and 0.5 for all the remaining networks. The networks were initialized via the Xavier normal initialization in PyTorch [Paszke et al., 2019]. The training time took less than one hour for all networks. The computation of the condition number was performed in parallel for each width and took around hours in the largest setting. Figure shows the trend that a larger width improves both the conditioning and the convergence speed. Additionally, the condition number is also more stable throughout training for larger widths.
I.3 Additional experiments on the effect of residual connections
As we have seen previously in Figure 3, the upper bound as a linear combination in Lemma is crucial to get a tight bound on the condition number. Additionally, as illustrated in Figure 19,
the ViT was based on Code taken from https://gi ht/ggtthub... waauu..coomeeee tintn/ vision- trwntrranns-ee ormer- from- scratch/tree/main which was published under the MIT license. "The implementation of the ResNet20, ResNet32 and VGG5 was based on Code taken from https: :// github.commjee com/ www.e//jjeeeeeo/eeeetettt
'The implementation
The author granted explicit permission to use the code.
Prining rate
0%
20%
40%
60%
80%
90%
10
Training loss
10P
Condition mumber
10
10a0
109
108
10a
10-1
100 Epochs
150
200
50
100
150
200
Epochs
Figure 13: Training loss (left) and condition number (right) for different amounts of pruning at initialization for a Vision Transformer for three seeds. The shaded area in the figures corresponds to one standard deviation from the mean.
25

---

Pruning rate
20%
40%
60%
10
Training lnss
30
Coudition mumber
10
20
10a
10
104
20
40
80
100
20
40
60
100
Epochs
Epochs
Figure 14: Training loss (left) and condition number (right) for different amounts of pruning initialization for a ResNet20.
Pruming rate
0%
20%
40%
60%
80%
40
Condition number x
1045
Traiiing loss
30
10
20
109
10
108
20
60
100
Epochs
Epochs
Figure 15: Training loss (left) and condition number (right) for different amounts of pruning at initialization for ResNet32.
Pruming rate
0%
20%
40%
60%
80%
40
Condition mumber K
10a
Training loss
30
10a
20
107
10
10a
50
100
150
50
100
150
Epochs
Epochs
Figure 16: Training loss (left) and condition number (right) for different amounts of pruning at initialization for a VGG5.
26

---

Pruning rate
0%
20%
10%
60%
80%
10a
10
Condition mumber
Thaining loss
6 10
10-1
4
50
100
150
200
50
100
150
200
Epochs
Epochs
Figure 17: Training loss (left) and condition number (right) for different amounts of pruning at initialization for a feed-forward network.
Width
100
150
200
1042
10
Condition nimber
Thaining loss
10.00
10-2
108
10-3
10
100
200
400
Epocks
Epochs
Figure 18: Training loss (left) and condition number (right) for different widths of one-hidden layer Feed-forward network trained on subset of MNIST (n 1000).
whitening the data is essential to improve the conditioning. Therefore, not otherwise specified, MNIST LeCun et al. [1998] and Cifar-10 10 Krizhevsky et al. [2009] will refer to whitened data and we refer Lemma or its equivalent in Eq. (7) for residual networks the "upper bound". The shaded area in the figures corresponds to one standard deviation from the mean. If not other specified via the Kaiming normal initialization in PyTorch was used.
As one can see from (8), the condition number for each term in the sum of the first upper bound in (8) improves when increases. This can be seen by the fact that the ratio will be dominated by and will go to for 3 + oo. This is also what we observe empirically in Figure 20 and Figure 22, where the condition number is smaller for 3 1 compared the other two settings, where B < J 1.
for deeper networks with
In Figure 23 the condition number of the GN matrix for one-hidden layer network with Leaky- ReLU activation is plotted for different values of a, where corresponds ReLU and corresponds to linear activation. We can see how ReLU activation improves the conditioning in the one-hidden layer setting.
The condition number was computed on CPU via the explicit formulas given in Lemma 2 and Eq. (7) and took approximately a few hours per experiment.
1.4 Further details on experiments compute resources
The total compute for experiments conducted amounts to approximately less than 100 hours. The main bottleneck is the computation of the condition number, which can be potentially further sped up by making full use of parallel computations on all available GPUs. The full research project required more compute than the experiments reported in the paper due to preliminary experiments.
27

---

whitened: K(2 1.0, not whitened: x(E) 3.0le
normalization
whitened not whitened
10
2
8
Depth L
Figure 19: Comparison the condition number for a Linear Network with hidden width m = 3100 with and without whitening Cifar-10 10 at initialization over three runs. Note, that the y-axis is displayed in log scale.
MNIST
Width: 800
Wiltil: 1000
Widta:: 1200
Width: 1000
Depth
Dopth L
Depli
Depti L
type
x(GO)
L/VE 1/E
Eppet bound
Figure 20: Condition number of outer- outer-product Hessian k( ((o)) and upper bound of a Residual Network for different values of 3 as function of depth for whitened MNIST at initialization over 20 runs.
Nevertheless, the total compute of the full research project amounts time of similar order of magnitude.
L..1 Computational complexity of computing condition number of Gauss-Newton matrix
In order to compute the condition number need to compute the eigenspectrum of the GN matrix Go. which has dimension p X p, where p the number of parameters or of the matrix Go. which has dimensions kd x kd, where d and k are the input, respectively output dimension of the network. The time complexity of calculating the eigenvalue decomposition has cubic complexity. That in order to compute the condition number, we have computational complexity of O (minnpp kd))).
28

---

Cifar-10
Wiith 1500
Width
Widtin: 3100
Walth 3400
Dopth 2
2
Depth T.
Depth
Deptis F.
network
type
RosNet
((Go)
FCNN
bound
Comparison of condition number of outer-produc, Hessian K kGo)) between Linear Network and Residual Network for whitened Cifar-10 at initialization over three runs.
Figure 21:
Cifar-10
Width: 1500
Width 1800
Widtis: 3100
Width: 3400
0
2
2
Dopth
Depth &
Depta L
Depti L
type
#(Gg)
1/VE
upper bound
1/L
Figure 22: Condition number of outer-product Hessian xs (Go)) and upper bounds for Residual Network with different values of /3 at initialization over three runs for Cifar-10.
10a
6 x 102
CK
0.0
X 102
0.1
0.3
3 x 10
0.5
1.0
1000
2000
3000
4000
5000
Width
Figure 23: Condition number of a one-hidden layer Leaky-ReLU network for different values of for whitened MNIST over 500 data points, where 0 corresponds ReLU and corresponds to a linear activation. Note that the y-axis is log-scaled.
29

---

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

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: All assumptions are stated at the beginning of the paper and formal proofs of Lemmas and Theorems are provided in the Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: For the main experimental results, all information needed, such as the network architecture, the initialization scheme, and the optimizer with its hyperparameters are specified. Additionally, the dataset as well as the preprocessing steps were specified.
Guidelines:
The answer NA means that the paper does include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to model. In general. releasing code and data often one good way to accomplish this, but reproducibilityy can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open- open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibiliity In the case of closed-source models, it may be that access to the model is limited in
31

---

some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: Code to run the experiments is provided in the supplementary material together with instructions how to reproduce the results.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm co/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to reproduce the results. See the NeurlPS code and data submission guidelines (https: httpe//ooSSuuumiiiiieiie
//nips.co wttpccccpppcccccctcocccccccccccc
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: For each experimental setting, the architectural setup, initialization scheme and the optimizer together with its hyperparameters were specified. Since our work only evaluated the training setting, data split was not necessary.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: For the experiments that support the main claims of the paper 1-sigma error bars are shown as shaded area. Figure 2a, Figure 2b, and Figure were calculated over seeds and Figure 3 over 20 seeds.
Guidelines:
32

---

The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: For each experiment the (approximate) compute and whether CPU or GPU were used were specified. Additionally a brief subsection provided Appendix I.4 to discuss the total estimated compute.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't It make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: /neuriss....///
Answer:
[Yes]
Justification:
The paper conforms in every aspect with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
33

---

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

---

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

---

Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
36


Reviews:
[{"review_id": "WF0EzUKfTp", "reviewer": "Reviewer_NTTB", "summary": "This paper is dedicated to the theoretical characterization of the condition number of the Gauss-Newton (GN) matrix in neural networks. By studying deep linear networks and two-layer nonlinear networks, the authors establish tight bounds on the GN matrix's condition number and extend this analysis to architectures incorporating residual connections and convolutional layers. The methodology is rigorous, and the experimental validation is thorough, making significant contributions to understanding optimization processes in deep learning.", "questions": "1. Can this paper be extended to study the effect of network initialization on convergence rate?\n\n2. Is it more appropriate to adjust the experiment on the effect of condition number and convergence rate in this paper to study different initializations or study the depth of the current network? They are more likely to keep the minimum loss close to each other, and make more use of the analysis of convergence rate.", "limitations": "As stated in the weaknesses.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper deeply studies the properties of Gauss-Newton matrices, especially in terms of condition numbers in deep linear networks and two-layer two-layer nonlinear networks (Leaky ReLU activation), and provides rigorous theoretical derivation and proof.\n\n2. This paper experimentally shows that the width and depth of the network, when the parameters are initialized with a certain distribution, have a strong correlation with the condition number.", "weaknesses": "1.The discussion in this paper on the relationship between the Gauss-Newton matrix condition number and the convergence rate of network optimization could be richer.\n\n2.Convergence Rate Analysis in Figure 17: The network's optimal solution and the corresponding minimum loss differ under various settings, making it difficult to analyze the convergence rate from the loss changes. For instance, at epoch 300, the network with a width of 15 may have nearly converged, while the network with a width of 200 still shows a significant downward trend. Thus, it is hard to draw conclusions about the convergence speed. \n\n3.The caption of Figure 9 does not match the subfigures.\n\n4.Figures 12-16 are not referenced or analyzed in the paper.\n\n5.This paper lacks exploration of more general networks and recent network structures.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Weakness 1**:\n> Convergence Rate Analysis in Figure 17: The network's optimal solution and the corresponding minimum loss differ under various settings, making it difficult to analyze the convergence rate from the loss changes. [...] Thus, it is hard to draw conclusions about the convergence speed.\n\n**Answer**:\nThank you for pointing this out. \n- To investigate this further, we have rerun the same experiment for 2000 epochs. The result can be found in Figure 2 of the attached PDF. \n- As the Reviewer pointed out, we indeed observe that the two networks with the smallest width converge to a suboptimal loss. Nevertheless, we *still observe the **connection** between a **smaller condition number** and a **faster convergence rate** for the remaining four networks*.\n\n**Weakness 2**:\n> The discussion in this paper on the relationship between the Gauss-Newton matrix condition number and the convergence rate of network optimization could be richer.\n\n**Answer**:\nThank you for this comment. \n- As discussed above, we have **rerun one experiment** to investigate the connection between the convergence rate and the Gauss-Newton matrix condition number more closely. \n- Moreover, we discuss below as an *Answer* to your **Question 1** how our work can be extended to study the **effect of the condition number at initialization on the convergence rate**. We hope that these additional discussions have enriched the discussion on the relationship between the condition number of the GN matrix and the convergence rate of network optimization.\n\n**Weakness 3**:\n> The caption of Figure 9 does not match the subfigures.\n\nThank you for pointing this out. We have corrected the caption now.\n\n**Weakness 4**:\n> Figures 12-16 are not referenced or analyzed in the paper.\n\nThank you for this comment. We have now added the reference to Figures 12-16 in appendix I.1. All experiments, except the VGG experiment, showcase that there is indeed a connection between the condition number of the network and the convergence speed during training.\n\n**Weakness 5**:\n> This paper lacks exploration of more general networks and recent network structures.\n\n**Answer**:\nIt would indeed be interesting to extend our analysis to other architectures, such as CNNs or Transformers. \n- **Straight forward extension to CNN.** We would like to note that our results can already be directly extended to CNNs by making use of the fact that the convolution operation can be reformulated in the form of a matrix-vector product using Toeplitz matrices, in which case we can apply the same analysis as for fully connected networks, which we also mention in a remark in line 266 and further elaborate in Appendix B. Previous work, such as Pinson et al. [2023] or Singh et al. [2022] have also studied properties of linear CNNs, such as its rank, making it an interesting object of study. \n- **Empirical results on CNN.** We addtionally provide empirical results for the condition number of the GN matrix of linear CNNs at initialization in Figure 1 of the attached PDF of the general response, where we examine the effect of kernel size and number of filters on the condition number of the GN matrix. \n- **MLPs in Transformers suggest potential transferability of some theoretical results.** The theoretical analysis of the condition number in Transformers would indeed be very intriguing, although we are currently unable to derive bounds for this setting. We would like to mention that previous work. Nevertheless, we would like to point out that MLPs make up a large part of standard transformer architectures and thus we expect that some theoretical results will also carry over to the Transformer setting.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "S3cElS6Ucy", "reviewer": "Reviewer_oXX9", "summary": "This paper characterizes the conditioning of Gauss-Newton (GN) matrix. The contribution of this paper is clear and straightforward: for deep linear networks, it establishes a bound on the condition number of GN matrix, which is further extended to 2-layer ReLU networks. These bounds could be useful in certain scenarios. Numerical experiments are conducted to support the theoretical claims.", "questions": "Could the authors give some implications of the proposed bounds and how we can better use it in practice?", "limitations": "The authors addressed their limitations in Section 7. In addition, in my view, the bounds fail to capture the distinctions between the solutions of deep learning models and random parameters such as the initialization, which limits its significance.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. This paper is clearly written and well-organized. The motivation of conducting the proposed research is clearly demonstrated in the introduction, i.e., why it is interesting to study the condition number of GN matrix for certain types of simplified deep neural networks. The main results and empirical results are also clearly presented.\n2. Numerical experiments verify that the bounds are tight under conditions imposed by the authors.", "weaknesses": "1. My major concern is about the implications of the derived bounds. Specifically, I note that training/learning such as gradient descent learning dynamics, which is crucial in practice, is not involved in deriving the bound. Thus it is hard to see the implication of these derived bounds since they are the same for both before and after training of the model parameters, i.e., it provides no information about the effects of training and fails to characterize the properties of solutions of deep learning models in a specific task. This might even lead the bounds to be meaningless in certain scenarios. For example, in Lemma 1, let $k = 1$, then according to [1],  after enough iterations of gradient descent, the largest singular value $\\sigma_{\\max} \\to \\infty$ (as there is no formal definition of $\\sigma_{\\max}$ in Lemma 1 I assume that my understanding of its definition is correct) while $\\sigma_{\\min} \\to 0$ for both $W$ and $V$, thus the bound blows up and becomes meaningless.\n\n2. I find the introduction part of this paper a bit verbose, e.g., it spends about 4 pages (almost half of the main body) to discuss existing results and related works before presenting details of main results (starting from Lemma 1). I think it would be better to emphasize more about the technical contributions of the current work, which is not clear to me since it seems that many important steps have already been solved by previous works, e.g., Eq. (2), (3), and Lemma 3.\n\n**Reference**\n\n[1]  Ji and Telgarsky. Gradient descent aligns the layers of deep linear networks.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Weakness 1**:\n> My major concern is about the implications of the derived bounds. Specifically, I note that training/learning such as gradient descent learning dynamics [...] is not involved in deriving the bound. Thus it is hard to see the implication of these derived bounds since they are the same for both before and after training of the model parameters [...]. This might even lead the bounds to be meaningless in certain scenarios. For example, in Lemma 1, let 𝑘=1, then according to [1], after enough iterations of gradient descent, the largest singular value 𝜎max→∞ [...] while 𝜎min→0 for both 𝑊 and 𝑉, thus the bound blows up and becomes meaningless.\n[1] Ji and Telgarsky. Gradient descent aligns the layers of deep linear networks.\n\n**Answer**:\nThank you for raising your concerns about the implications of the derived bounds, which we would like to answer in two parts:\n\n1. **Upper bound remains tight throughout training.** As you correctly pointed out, the bounds are indeed agnostic to the learning dynamics. And it is of course conceivable to find a parametrization of the weight matrices for which the upper bounds become vacuous. However, our empirical results in **Figure 9** in **Appendix D** of the main paper show that the upper bound actually remains tight throughout training, and is thus predictable of the Gauss-Newton condition number throughout training.\n2. **Reference [1] considers extreme case of linearly separable data.** We have checked reference [1] closely after your comment and would like to note that [1] consider an extreme case, in which they assume that the data is linearly separable, which is of course generally never the case. However, this assumption is essential for the authors in [1] to show the asymptotic weight matrix alignment. \n\nTherefore, we would like to argue that our bounds are indeed useful and relevant in practical settings, as has been illustrated in the point above.\n\n**Weakness 2**:\n> I find the introduction part of this paper a bit verbose, e.g., it spends about 4 pages (almost half of the main body) to discuss existing results and related works before presenting details of main results (starting from Lemma 1). I think it would be better to emphasize more about the technical contributions of the current work, which is not clear to me since it seems that many important steps have already been solved by previous works, e.g., Eq. (2), (3), and Lemma 3.\n\n\n**Answer**:\nOur intention was to provide a comprehensive background and context to ensure that readers with varying levels of familiarity with the topic could fully understand the significance of our contributions. However, your point is well-taken and we will modify the text according to your comment. Thank you for pointing this out.\n\n**Question 1**:\n> Could the authors give some implications of the proposed bounds and how we can better use it in practice?\n\n**Answer**:\nThis is a very good question indeed. \n- There are several implications regarding the choice of architecture that are discussed in the paper (for instance the way to scale the width in relation to the depth, and the importance of using normalization layers). The paper also gives a justification of why pruned networks are more difficult to train as they have worse condition number. Although this is not our focus, it is possible that our analysis could inspire better techniques for pruning neural networks.\n- Finally, we also want to mention potential applications in architectural search that is often performed at initialization due to the prohibitive cost of training. [Mellor et al., 2021, Yu et al., 2019, Elsken et al., 2019].\n\n**Limitations 1**:\n> The authors addressed their limitations in Section 7. In addition, in my view, the bounds fail to capture the distinctions between the solutions of deep learning models and random parameters such as the initialization, which limits its significance.\n\n**Answer**:\nThank you for this comment. We will add this limitation to our discussion in section 7.\n\nWe kindly request the reviewer to let us know if there are any remaining\nquestions they may have. If they find that their queries have been sufficiently addressed, we would greatly appreciate it if they could reconsider their evaluation of our paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "w7bmPb0vZt", "reviewer": "Reviewer_6bdM", "summary": "This paper examines the condition number of the Gauss-Newton matrix [1] in neural networks. It shows that normalization techniques, such as Batch Normalization [2], initial normalization, skip connections [3], and appropriate layer dimensions, reduce the condition number and therefore enhance the training stability. The objective is to provide insights into the training of deep neural networks by characterizing a new, tight upper bound for the condition number of the Gauss-Newton matrix. The paper primarily focuses on linear neural networks and shallow non-linear neural networks.\n\n[1] SCHRAUDOLPH, Nicol N. Fast curvature matrix-vector products for second-order gradient descent. Neural computation, 2002, vol. 14, no 7, p. 1723-1738.\n[2] IOFFE, Sergey et SZEGEDY, Christian. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In : International conference on machine learning. pmlr, 2015. p. 448-456.\n[3] HE, Kaiming, ZHANG, Xiangyu, REN, Shaoqing, et al. Deep residual learning for image recognition. In : Proceedings of the IEEE conference on computer vision and pattern recognition. 2016. p. 770-778.", "questions": "1. Could you clarify the statement on line 31: “imagine an entire set of neurons being dead”? What implications does this scenario have for your study?\n2. How good is the approximation of the Gauss Newton matrix $\\mathbf{G}_O$ without considering the term $\\mathbf{H}_F$?\n3. Can you also conduct experiments on more challenging datasets like ImageNet [7] or TinyImageNet [8]?\n4. Can you develop more about the time and space complexity of the computation of the condition number?\n5. Can you explain and rephrase the lines 719 and 720 with the associated Figures 19 and 21?\n6. Why did you compute the condition number on CPU rather than on GPUs (line 725)?\n7. Can you also explore the relation between te condition number and the batch size?\n\n[7] DENG, Jia, DONG, Wei, SOCHER, Richard, et al. Imagenet: A large-scale hierarchical image database. In : 2009 IEEE conference on computer vision and pattern recognition. Ieee, 2009. p. 248-255.\n[8] Le, Ya and Xuan S. Yang. “Tiny ImageNet Visual Recognition Challenge.” (2015).", "limitations": "The limitations of the work are well addressed by the authors. I do not believe this work has any particular negative social impact.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "This paper provides new theoretical insight into the training dynamics of Deep Neural Networks (DNNs) by examining the conditioning number of the Gauss-Newton Matrix. The experimental results are robust and shed light on often obscure aspects of DNN optimization, such as the impacts of normalization, layer size, residual connections, and ReLU activation function. Meanwhile, the way the authors interpret the experimental results seems reasonable. Importantly, the paper also clearly outlines its limitations in the conclusion.", "weaknesses": "The paper is difficult to read and follow due to several typos and unclear ideas. The main contribution is not significant and heavily relies on Singh's work [4]. The authors discuss the K-FAC method [5], which uses the EFIM and not the Hessian, even though it can be an approximation in certain cases where the model's likelihood is in the exponential family [6]. The paper only addresses the Gauss-Newton matrix and not the Generalized Gauss-Newton matrix [6], which could be more relevant, especially when using a cross-entropy loss function instead of MSE. Additionally, the references are outdated (e.g., line 49 and most of the related work), and there are typographical errors, such as \"generalized\" being repeated on line 140 and \"collapse\" being misspelled on line 124. There is also a lack of references related to the Gauss-Newton matrix, Kronecker properties PyTorch library, etc...\n\n[4] SINGH, Sidak Pal, BACHMANN, Gregor, et HOFMANN, Thomas. Analytic insights into structure and rank of neural network hessian maps. Advances in Neural Information Processing Systems, 2021, vol. 34, p. 23914-23927.\n[5] MARTENS, James et GROSSE, Roger. Optimizing neural networks with kronecker-factored approximate curvature. In : International conference on machine learning. PMLR, 2015. p. 2408-2417.\n[6] MARTENS, James. New insights and perspectives on the natural gradient method. Journal of Machine Learning Research, 2020, vol. 21, no 146, p. 1-76.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Weakness 1**:\n> The paper is difficult to read and follow due to several typos and unclear ideas. The main contribution is not significant and heavily relies on Singh's work [4].\n\n**Answer**:\nWe understand the concern of the reviewer regarding the potential overlap with Singh et al. [2021].\n- We would like to clarify that while our work builds on Singh et al. [2021], our **main contribution** is the introduction of **tight upper bounds for the condition number of the Gauss-Newton (GN) matrix** for linear and residual networks of arbitrary depth and width. To the best of our knowledge, this has **not been addressed before in the literature**.\n- More specifically, Singh et al. [2021] derived expressions for the Hessian which we use in our analysis. Therefore, there is an **entirely different focus and a thematic difference** between our current work and the previous work in Singh et al. [2021]. However, obtaining bounds on the GN matrix based on these expressions is not an easy task. We demonstrated that naive bounds are vacuous, while we presented experimental evidence demonstrating that the theoretical bounds are predictive in practice. We would be grateful if the reviewer could elaborate on what ideas are not clear in the paper, we would be happy to provide further details.\n\n**Weakness 2**:\n> The paper only addresses the Gauss-Newton matrix and not the Generalized Gauss-Newton matrix [6], which could be more relevant, especially when using a cross-entropy loss function instead of MSE. \n\n**Answer**:\nThank you for this insight regarding the Generalized Gauss-Newton matrix.\n- Our current work focuses on the Gauss-Newton matrix to build a solid foundational understanding of its properties, which we believe is important before extending our analysis to more complex scenarios.\n- While we recognize the relevance of the Generalized Gauss-Newton matrix, particularly for cross-entropy loss, addressing this is currently beyond the scope of our work. We believe that this is a key direction for future research and will add this to the discussion on limitations and future work in the final version of the paper.\n- Despite this, our **findings on the Gauss-Newton matrix already provide important insights** into the *initialization and training dynamics of neural networks using MSE loss*, which are valuable in their own right.\n\n**Weakness 3**\n> Additionally, the references are outdated (e.g., line 49 and most of the related work). There is also a lack of references related to the Gauss-Newton matrix, Kronecker properties PyTorch library, etc\n\n**Answer**:\nThank you for this comment. We apologize for the outdated references. We have now updated our references to cover more recent and additional relevant works, particularly on the Gauss-Newton matrix, normalization techniques, and Kronecker properties. This also includes replacing the outdated references with new ones.\n\n**Weakness 4**:\n> [...] and there are typographical errors, such as \"generalized\" being repeated on line 140 and \"collapse\" being misspelled on line 124.\n\n**Answer**:\nWe apologize for the issues regarding the readability and typographical errors in the initial submission.\n- We would like to point out however that it is in fact not a typographical error, as Liao and Mahoney [2021] indeed analyze a generalization of the family of generalized linear models, which they called generalized generalized linear models (G-GLM).\n- We have also thoroughly revised our work to correct all typos and improve the clarity and have also rephrased sections, such as lines 140, for better comprehension.\n\n**Question 1**:\n> Could you clarify the statement on line 31: “imagine an entire set of neurons being dead”? What implications does this scenario have for your study?\n\n**Answer**:\nThe statement on line 31 refers to the phenomenon where neurons become inactive (that is, produce zero output) due to poor initializations or training dynamics. This will have a direct effect on the eigenspectrum of the GN matrix, which we will illustrate on a simple example.\nConsider a 2-layer linear network $F_{\\theta}(\\mathbf{x}) = \\mathbf{W} \\mathbf{V} \\mathbf{x}$, where one neuron in the hidden layer is dead, that is output only zeros. Then this is equivalent to the row corresponding to the neuron of the matrix $\\mathbf{W}$ to be a zero vector. This directly implies that the rank of $\\mathbf{W}$ is reduced by one or that there is another zero eigenvalue in the eigenspectrum. This in turn increases the value of the pseudo condition number $\\kappa(\\mathbf{W})$ that appears in the upper bound in Eq. (4).\n\n**Question 2**:\n> How good is the approximation of the Gauss Newton matrix 𝐺𝑂 without considering the term 𝐻𝐹?\n\n**Answer**:\nThank you for this question.\n- The difference between the Gauss Newton matrix $\\mathbf{G}_O$ and the Hessian of the loss function $\\mathbf{H}_L$ depends on both the residual and the curvature of the network $F\\_{\\boldsymbol{\\theta}}(\\mathbf{x})$. Thus, close to convergence when the residual becomes small, the contribution of $\\mathbf{H}_F$ will also be negligible and $\\mathbf{G}_O$ is essentially equal to $\\mathbf{H}_L$.\n- Furthermore, Lee et al. [2019] show that sufficiently wide neural networks of arbitrary depth behave like linear models during training with gradient descent. This implies that the Gauss-newton matrix is a close approximation of the full Hessian in this regime throughout training.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "94VvatKohL", "reviewer": "Reviewer_ewWf", "summary": "The authors derived upper bounds for the condition number of the outer product of the jacobian of the neural network output (the Gauss Newton matrix) in the case of deep linear networks, and non-linear networks with a single hidden layer with piecewise-linear activation functions. They empirically evaluate these bounds using MNIST (with the exception of one plot in the main text that used CIFAR-10) and find their bounds reflect the general trend of the empirical condition number as depth (or in some cases width) are varied. The work is motivated by highlighting the importance of Hessian information in the optimisation of neural networks.", "questions": "- To be clear, on line 82 where we refer to \"outer gradient product of the loss function\", this is actually the outer gradient product of the network function and has no dependence on the loss function, right?\n- Suggestion: In the equation below line 182 (which should probably be numbered) some extra brackets and the use of \\cdots rather than \\dots would make this expression clearer to read.", "limitations": "The authors briefly discuss some future directions their work could be taken in, but do not seriously critique the work they present here.", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The empirical evaluations show that the bounds are actually quite informative, following the general behaviour of the condition number and in some cases being quite tight as well. They point out that if they replace the convex combination in their bound(s) with a maximum, the bound becomes much looser and does not show any behaviour following trends.\n- The understanding of neural network loss landscapes and how best to optimise them is still in its relative infancy, so works like this can be valuable.\n- Extensive proofs and extra plots are provided in the appendices", "weaknesses": "- ~~The paper generally uses the same dataset (MNIST) for almost all the plots, so it's hard to tell if these good behaviour of their bounds hold on other, potentially harder to optimise, problems such as CIFAR-10.~~ **It was pointed out in the rebuttal that CIFAR-10 was included in the appendix.**\n- The precise motivation of studying the Gauss Newton is slightly weak. It's not clear to me that these results actually tell us anything substantial about optimising the neural network.\n- The authors were not able to extend their bound to the deep non-linear network case.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Weakness 1**:\n> The paper generally uses the same dataset (MNIST) for almost all the plots, so it's hard to tell if these good behaviour of their bounds hold on other, potentially harder to optimise, problems such as CIFAR-10.\n\n**Answer**:\nThank you for this comment. Please note that we do have experiments using Cifar-10 in the Appendix (see for instance Figure 20 and 21), which showcase that our bounds are also tight in this case. Does this address your comment?\n\n**Weakness 2**:\nThe precise motivation of studying the Gauss Newton is slightly weak. It's not clear to me that these results actually tell us anything substantial about optimising the neural network.\n\n**Answer**:\nThank you for this comment. We would like to answer your comment in two parts:\n- **Preconditioning methods based on GN matrix are successful.** Although the Gauss-Newton matrix $\\mathbf{G}_O$ is only an approximation to the full Hessian matrix, it does seem to capture the curvature of the loss very well given the success of many second-order optimization methods based on approximations of the Gauss-Newton matrix, such as K-FAC [Martens and Grosse, 2020], Shampoo [Gupta et al., 2018] or Sophia [Liu et al., 2023]. \n- **GN matrix performs better than Hessian as preconditioner in Sophia algorithm.** Particularly interesting is the last method, in which the authors observe that their optimizer based on the Gauss-Newton matrix performs even better than their optimizer based on the full Hessian matrix, implying that the Gauss-Newton matrix is a good preconditioner and captures the curvature of the loss landscape well. \n- As the condition number characterizes the convergence rates of gradient-based methods at least locally, we would like to argue that our results do help in understanding the optimization process of neural networks with gradient-based methods better.\n<!-- Furthermore, we would like to highlight the close connection of the GN matrix to the Neural Tangent Kernel (NTK) and the Jacobian. Therefore, we believe that a better understanding of the GN matrix can also help to provide valuable insights into related objects.  -->\n\n**Weakness 3**\nThe authors were not able to extend their bound to the deep non-linear network case.\n\n**Answer**:\nWe are indeed not yet able to extend our bounds to deep non-linear networks, which is something that we also mention in the limitation section. Yet we believe that our theoretical bounds on deep linear and residual networks already provide valuable insights on how different choices in the network architecture can affect the condition number of the Gauss-Newton matrix.\n\n**Question 1**:\nTo be clear, on line 82 where we refer to \"outer gradient product of the loss function\", this is actually the outer gradient product of the network function and has no dependence on the loss function, right?\n\n**Answer**:\nThank you for this question. Yes, you are right, the Gauss-Newton matrix is defined in Eq.(1) (same as defined in prior work discussed above) and it has no dependence on the loss function. As elaborated in lines 84-90, this is precisely the outer product Hessian $\\mathbf{H}_O$ when the loss function is the MSE loss, which is what we are considering for most part of the work.\n\n**Question 2**:\nSuggestion: In the equation below line 182 (which should probably be numbered) some extra brackets and the use of $\\cdots$ rather than $\\dots$ would make this expression clearer to read.\n\n**Answer**:\nThank you for this suggestion! We will improve the display of the equation to make it more readable.\n\nWe kindly request the reviewer to let us know if there are any remaining\nquestions they may have. If they find that their queries have been sufficiently addressed, we would greatly appreciate it if they could reconsider their evaluation of our paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
Dear Reviewers,

we would like to thank you for the time that you have committed to reviewing our work and for the questions and comments, which have helped to enhance our work considerably. 

We are pleased to report that we were able to address almost all of your comments and questions (except one question which we hope **Reviewer NTTB** can clarify), which we summarize below:

1. - As suggested by **Reviewer NTTB** we have extended our discussion on the relationship between the Gauss-Newton matrix condition number and the convergence rate of network optimization, which we substantiate with an experiment that we discuss below in more detail.
    - Additionally, we have conducted another experiment on linear CNNs, which highlights the empirical applicability of our bounds in the CNN setting.
2. As requested by **Reviewer oXX9** we have elaborated the practical relevance of our derived bounds, which can be seen in Figure 9 in appendix D of our main paper, and further discussed how these bounds can be better used in practice.
3. As requested by **Reviewer 6bdM** we have highlighted the novelty of our contribution and clarified questions regarding the actual computation of the condition number (e.g. CPU vs. GPU, computational complexity). 
4. As requested by **Reviewer ewWf**, we provide further motivation for studying the Gauss-Newton matrix and its relevance for understanding the optimization process of neural networks.
5. We clarified some formulations, corrected some minor typos, and promised to update parts of our references.

We believe that our revision highlights the novelty of our contribution, and that the additional experiments, which we provide, support our claim. We are looking forward to the Author-Reviewer discussion period. 
In the meantime, we kindly ask you to re-evaluate our paper and consider raising your scores and confidence in your assessments. 

Best regards,

The Authors


### Further experiments
- **Experiments on CNNs.** As requested by **Reviewer NTTB** we conducted additional experiments on the condition number of the Gauss-Newton matrix of linear CNNs at initialization, which can be found in Figure 1 of the attached PDF. We examine the effect of kernel size and number of filters on the condition number of the GN matrix. We observe a trend, where the number of filters increases the condition number (in analogy to depth in MLPs) and the kernel size improves conditioning (in analogy to width in MLPs). This highlights the empirical applicability of our bounds in the CNN setting.
- **Connection between condition number of GN matrix and convergence speed.** As has also been requested by **Reviewer NTTB** we have rerun an experiment, which evaluates the convergence speed of a 2-layer ReLU network with varying width, for more epochs. The result can be found in Figure 2 of the attached PDF. Although the two networks with small widths converge to a suboptimal minimum and should be discarded from the discussion on convergence speed, we can still observe the connection between a smaller condition number and a faster convergence rate for the remaining four networks.

Meta-review: This paper provides a theoretical characterization of the condition number of the Gauss-Newton (GN) matrix in neural networks, establishing tight bounds for linear networks and extending the analysis to some non-linear, residual, and convolutional architectures. This paper provides interesting analysis and will benefit the community, and therefore I recommend acceptance.
Decision: Accept (poster)