On the Convergence of Gradient Flow on Multi-layer Linear Models
Authors: Hancheng Min
Rene Vidal
Enrique Mallada
Venue: Submitted to ICLR 2023 (2023)
Keywords: Multi-layer Linear Networks
Non-convex optimization
Gradient Flow
Training invariance

Abstract: In this paper, we analyze the convergence of gradient flow on a multi-layer linear model with a loss function of the form $f(W_1W_2\cdots W_L)$. We show that when $f$ satisfies the gradient dominance property, proper weight initialization leads to exponential convergence of the gradient flow to a global minimum of the loss. Moreover, the convergence rate depends on two trajectory-specific quantities that are controlled by the weight initialization: the \emph{imbalance matrices}, which measure the difference between the weights of adjacent layers, and the least singular value of the \emph{weight product} $W=W_1W_2\cdots W_L$. Our analysis provides improved rate bounds for several multi-layer network models studied in the literature, leading to novel characterizations of the effect of weight imbalance on the rate of convergence. Our results apply to most regression losses and extend to classification ones.

Under review as a conference paper at ICLR 2023
ON THE CONVERGENCE OF GRADIENT FLOW ON MULTI-LAYER LINEAR MODELS
Anonymous authors Paper under double-blind review
ABSTRACT
In this paper, we analyze the convergence of gradient flow on multi-layer linear model with a loss function of the form f(W,W2 WL). We show that when f satisfies the gradient dominance property. proper weight initialization leads to exponential convergence of the gradient flow to a global minimum of the loss. Moreover, the convergence rate depends on two trajectory-speciffe quantities that are controlled by the weight initialization: the imbalance matrices, which measure the difference between the weights of adjacent layers, and the least singular value of the weight product W = W; W W.. Our analysis provides improved rate bounds for several multi-layer network models studied in the literature, leading novel characterizations of the effect of weight imbalance on the rate of convergence. Our results apply to most regression losses and extend to classification ones.
INTRODUCTION
The mysterious ability of gradient-based optimization algorithms to solve the non-convex neural network training problem is one of the many unexplained puzzles behind the success of deep learning in various applications (Krizhevsky al. 2012) Hinton et al.) 2012 Silver et all, (016). A vast body of work has tried to theoretically understand this phenomenon by analyzing either the loss landscape or the dynamics of the training parameters.
The landscape-based analysis is motivated by the empirical observation that deep neural networks used practice often have a benign landscape (Li et al.) 2018a), which can facilitate convergence. Existing theoretical analysis (Lee et al. 2016;; Sun et al. 2in5 et al.) (017)) shows that gradient descent converges when the loss function satisfies the following properties: 1) all of its local minimums are global minima; and 2) every saddle point has a Hessian with at least one strict negative eigenvalue. Prior work suggests that the matrix factorization model (Ge al.] (017). shallow networks (Kawaguchi] (2016), and certain positively homogeneous networks (Haeffele & Vidal 2015 2017) have such a landscape property, but unfortunately condition 2) does not hold for networks with multiple hidden layers (Kawaguchi] 2016). Moreover, the aundsaape-basel amalysis generally fails to provide a good characterization of the convergence rate, except for a local rate around the equilibrium (Lee al. 2016 Ge al. 2017). In fact, during early stages of training, gradient descent could take exponential time to escape some saddle points if not initialized properly (Du et al. (017).
The trajectory-based analyses study the training dynamics of the weights given specific initialization.
For example, the case of small initialization has been studied for various models (Arora et al. 201
Gidel al. 2019 Li al. 2018b Stöger & Soltanolkotabi 2021| Li al. 2021b a). Under this type
of initialization, the trained model is implicitly biased towards low-rank (Arora et al. 2019a Gidel
al. 2019 Li al. 2018b Stöger & Soltanolkotabi] [021 Li al.) 2021b). and sparse (Li et al.
202la models. While the analysis for small initialization gives rich insights on the generalization of neural networks, the number of iterations required for gradient descent to find a good model often increases as the initialization scale decreases. Such dependence proves to be logarithmic on the scale for symmetric matrix factorization model (Li et al., 201 8b Stöger Soltanolkotabii 2021 Li et al. 2021b), but for deep networks, existing analysis at best shows a polynomial dependency (Li et al. 2021a). Therefore, the analysis for small initialization, while insightful in understanding the implicit bias of neural network training, is not suitable for understanding the training efficiency in practice since small initialization rarely implemented due to its slow convergence. Another line of work studies the initialization in the kemel regime, where randomly initialized sufficiently wide neural

---

Under review as a conference paper at ICLR 2023
network can be well approximated by its linearization initialization Jacot et al. (2018); Chizat et al. (2019); Arora et al. (2019b). In this regime, gradient descent enjoys a linear rate of convergence toward the global minimum (Du et al. 2019; Zllen-Zhu et al. 2019 Du & Hu 2019). However, the width requirement in the analysis is often unrealistic, and empirical evidence has shown that practical neural networks generally do not operate in the kernel regime (Chizat et al. 2019).
The study of non-small, non-kernel-regime initialization has been mostly centered around linear models. For matrix factorization models, spectral initialization (Saxe et al.) (2014; Gidel al. 2019 Tarmoun et al. 202T) allows for decoupling the training dynamics into several scalar dynamies. For non-spectral imitialization, the notion of weight imbalance, quantity that depends on the differences between the weights matrices of adjacent layers, is crucial in most analyses. When the initialization is balanced, i.e., when the imbalance matrices are zero, the convergence relies on the initial end-to-end linear model being close to its optimum (Arora et al., 201 8a b). It has been shown that having non-zero imbalance potentially improves the convergence rate (Tarmoun et al. 2021 Min al. 2021), but the analysis only works for two-layer models. For deep linear networks, the effect of weight imbalance on the convergence has been only studied in the case when all imbalance matrices positive semi-definite (Yun et al. 2020), which is often unrealistic in practice. Lastly, most of the aforementioned analyses study the l2 loss for regression tasks, and it remains unknown whether they can be generalized other types of losses commonly used in classification tasks.
This paper aims to provide a general framework for analyzing the convergence of gradient flow on multi-layer linear models. We consider the gradient flow loss function of the form L = f(W, W2 WI), where f satisfies the gradient dominance property. We show that with proper initialization, the loss converges to its global minimum exponentially. More specifically:
Our contribution:
Our analysis shows that the convergence rate depends on two trajectory-specific quantities: 1) the imbulance mutrices, which measure the difference between the weights of adjacent layers, and 2) a lower bound on the least singular values of weight product W = W1 W2 ... WL. The former is time-invariant under gradient flow, thus it is fully determined by the initialization, while the latter can be controlled by initializing the product sufficiently close to its optimum.
Our analysis covers most initialization schemes used in prior work (Saxe et al., 2014 Tarmoun et al. 2021 Arora et al. 201 8a by Min et al., 2021 Yun et al., (020) for both multi-layer linear networks and diagonal linear networks while providing convergence guarantees for a wider range of initializations. Furthermore, our rate bounds characterize the general effect of weight imbalance on convergence.
Our convergence results directly apply to loss functions commonly used in regression tasks, and can be extended to loss functions used in classification tasks with an alternative assumption on f. under which we show ((1/t) convergence of the loss.
For an n matrix A, we let A denote the matrix transpose of A, oz denote its i-th singular value in decreasing order and we conveniently write Jmin (A) = T [n.m] mm, (A) and let
Notations:
ox((A) = if min m). We also let ||Al|2 = o1 (A) and ||A|||= = v tA' A). For square matrix of size we let tr(A) denote its trace and we let diag(a, )= be a diagonal matrix with a; specifying its i-th diagonal entry. For a Hermitian matrix of size n, we let (A) denote its i-th eigenvalue and we write A > 0 (A < 0) when A is positive semi-definite (negative semi-definite. For two square matrices A, B of the same size, we let (A, B)F = tr(A" B). For a scalar-valued or matrix-valued function of time, F(I), we write F, F() or d [L) for its time derivative. Additionally, T6 use 7 denote the identity matrix of order and (n) to denote the set of orthogonal matrices. Lastly, we use FI+ := max(-,0) 0}.
2 OVERVIEW OF THE ANALYSIS
This paper considers the problem of finding matrix W that solves
min f(W), W
(I)
with the following assumption on
2

---

Under review as a conference paper at ICLR 2023
Assumption 1. The function is differentiable and satisfie
A1:
f satisfies the Polyak-Lojasiens Lojasiewicz (PL) condition, i.e. This condition is also known gradient dominance.
IVF 2 x(f(W) - f)),
A2: f is K-smooth, Le., [V Vf(V)ll S K|W Vile. VW,V and is je-trroggyy convex, i.e., f(W) 2
V)
- VW, V.
While classic work (Polykk, 1987) has shown that the gradient descent update on W with proper step size ensures linear rate of convergence of f(W) towards its optimal value f*, the recent surge of research on the convergence and implicit bias of gradient-baset methods for deep neural networks has led to great amount of work on the overparametrized problem:
min & ((Wi)t=)) = (W.W2- WI). (Wi3
where 2 2. Wi E RA RRI-IKA, 1, 1, L. with ho = n, h2 = m and mi, h 2 .h.-1) 1) is necessary ensure that the optimal value
min (n, (n,mm,)) m]. This assumption on of (2) is also f*, and in this case, the product I W, can represent an overparametrized linear network/model (Arora et al. 2018b Tarmoun et al. 2021 Min et al. 2021
2.1
CONVERGENCE VIA GRADIENT DOMINANCE
For problem
2}. consider the gradient flow dynamics on the loss function & ((W))
Wi Ô
ow; ((Wi)f , = 1........
The gradient flow dynamics can be viewed gradient descent with "infinitesimal" step size and convergence results for gradient flow can be used to understand the corresponding gradient descent algorithm with sufficiently small step size (Elkabetz & Cohen 2021). We have the following result regarding the dire-derivative of L under gradient flow (3).
Lemma 1. Under continuous dynamics in (3), have
A -IVV ((WI) l (TeNHL VI(W), V((W)
(4)
where W- -T Wi, and Tiwel is the following positive semi-definite linear operator on Raxm
1++1
T
I.+1
T(mit E
II w
II W.
E
II
W.
II
W;
.. Ln, Im
Such an expression of | has been studied in Arora et al. (0188). and we include proof in Appendix fooo completeness. Our convergence analysis is as follows.
For this overparameterized problem, the minimum - of 2 is fa Then from Lemma and Assumption A1, we have
h (TWIE, V((W), V(W))))(W)
Amiin [[W:)
(min-max theorem (Tecchl 2014))
(5)
(AI) -Amin Damii(Tiiiia
- f*) Amin (T(w))t, )N( - L*).
If can find lower bound > 0 such that Amin Amiin(T (T(w((0)) 2 a, Vt 0. then the following inequality holds on the entire training trajectory di (L - L*) < aay (f. L*). Therefore, by using Grönwall's s inequality (Grönwall 1919). can show that the loss function L converges exponential to its minimum, i.c.,
C(I) - L < exp
(-ont) e L*), ,t 0.
(6)
Note that A2 assumes j-strong convexity, which implies A1 with 7 2p. However, we list A1 and A2 separately since they have different roles in analysis.
3

---

Under review as a conference paper at ICLR 2023
Therefore, to show exponential convergence of the loss, we need to lower bound Amin (T [Witt Most existing work the convergence of gradient flow/descent on linear networks implicitly provides such lower bound, given additional assumptions on the initialization {W] though not presented with such generality. We revisit previous analyses to see how such problem can be solved for two-layer linear networks, then present our new results regarding deep linear networks.
3
LESSONS FROM TWO-LAYER LINEAR MODELS
In this section, we revisit prior work through the lens of our general convergence analysis in Section
2.1 A lower bound Amin (T [[ws(e) can be obtained from the training invariance of the gradient
How. We first consider the following imbalance matrices:
Dj = WT Wi WI+1WTT1 1 1= I,..,, 1.
For such imbalance matrices, we have
Lemma 2. Under the continuous dynamics
we have (1) 0, 0,1=1,
Such invariance of weight imbalance has been studied in most work on linear networks (Arora et al. 2018a| Du al.) 20188 Yun et al. 2020). We include the proof Appendix [oo completeness. Since the imbalance matrices {Di D=) are fixed at its initial value, any point { (t) on the training trajectory must satisfy the imbalance constraints Wi(t)" Wt()) Wi+1 W
Di) ))
1.... -- 1. Previous work has shown that enforcing certain non-zero imbalance at initialization leads to exponential convergence of the loss for two-layer networks (Tarmoun et al.] | |222]] Min et al.)
2021), and for deep networks (Yun al. 2020). Another line of work (Arora al. 2018a b) has
shown that balanced initialization (Dr = 0, Vt) haves exactly Amin (T(w)())))) Lo min (W))). where W (t) nh (t). This suggests that the bound on Ami (T (T we are looking for should potentially depend on both the weight imbalance matrices and weight product matrix.
Indeed, for two-layer models, a re-statemen of the results in (Min et al. 2022) provides lower bound on Amin( (T(wi,wa)) with the knowledge of the imbalance and the product.
Lemma (re-stated from Min et al. 20222) When L = 2, given weights {W1, W23 with imbalance matrix D WT Wi WoW and product W W W2, define
A - A (>i(- (- A -Am (Am (8)
Then for the linear operator T(W..W.) defined in Lemma 7
we have
Amiu Xmin(T (T(W, {
+ V(A ( A + VIA 2 46 (W)
Min et al. (2022) include a detailed discussion on the bound, including tightness. For our purpose, we note the tollowing:
Effect of imbalance: follows from ( that Amia (T(W, w.,) 2 A since miiu (W) 2 0. Therefore, A is always lower bound the convergence rate. This means that, for most initializations, the fact that the imbalance matrices are bounded away from zero (characterized by A > 0) is already sufficient for exponential convergence.
Effect of product: The role of the product in is more nuanced: Assume n = m for simplicity so that o. o,, (WW?) control how much the product affects the convergence. More precisely. the lower bound in (9) is decreasing function of both A and A.. When A, A_ 0. the lower bound reduces to
am (WTW) = o2 muin (W), We see that the non-negative quantities A,, A
A + 2 min (W), showing a joint contribution to convergence from both imbalance and product. However, as A A_ increases, the bound decreases towards A, which means that the effect of
IIn Min et al. 2022). there is no general idea of lower bounding Amin (T(ws but their analyses essentially provide bound.
4

---

Under review as a conference paper at ICLR 2023
imbalance always exists, but the effect of the product diminishes for large A+, A.. We note that A+,4 A_ measure how the eigenvalues of the imbalance matrix are different in magnitude, i.e., how "ill-conditioned" the imbalance matrix is.
Implication on convergence: Note that ② is almost lower bound for Amin (tW,()) ) i
as the imbalance matrix D is time-invariant (so A+; A- A), except the right-hand side of (9) also depends on min ( (t)... If f satisfies A2, then f has a unique minimizer W Moreover, one can show that given a initial product W W(O), W W(!) constrained to lie within a closed ball
[W) W* }- That is, the product ((t) does not get too far away from W during training. We can use this to derive the following lower bound min (W())):
W: ||W- - -
K (I
min (W())) mmin (W")
V
W" |F == margin (See Appendix A
(10)
This margin term being positive guarantees that the closed ball excludes any W with min (W) 0. With this observation, we find a lower bound Amin (tW ,t 2 0 that depends on both the weight imbalance and margin, and the exponential convergence of loss L follows:
Theorem 1. Let D be the imbalance matrix for L 2. The continuous dynamics in 3 satisfy
C(I)- - L-
("), 2
(11)
where
1. I satisfies only AI, then a2 = A;
2. If satisfies both Al and A2, then
022 = + + (A+ + A)2 + 4( On (W*) - /K/p - Wo )²
A_ + A A) + 4( 0m [0m
(W*) (()) - 1= )², (12)
with ((0)= = I Wi( and W equal to the unique optimizer of f-
Please see Appendix FJ for the proof. Theorem I iis new as it generalizes the convergence result in Min et al. (2022) for two-layer linear networks, which only for l2 loss in linear regression. Our result considers general loss function defined by f. inccluding the losses for matrix factorization (Arora ct al. 2a) linear regression (Min et al. (022). and matrix sensing (Arora et al. 2019a). Addition- ally, Arora et al. (2018a) first introduced the notion of margin for in matrix factorization problems (K 1, 1), and we extend to any f that is smooth and strongly convex.
Towards deep models: So far, we revisited prior results two-layer networks, showing how Amin TT... can be lower bounded by weight imbalance and product, from which the convergence result is derived. Can generalize the analysis deep networks? The main challenge is that even computing Amin (T(w)) given the weights (Wi) is complicated: For L = 2, Amin (Tw,.w,) = An (W WT) + Am (W3 W2). but such nice relation does not exist for L > which makes the search for tight lower bound as in (9) potentially difficult. On the other hand, the findings in (9) shed light on what can be potentially shown for the deep layer case:
1. For two-layer networks, we always have the bound Amin (T(w, Z which depends only the imbalance. Can find lower bound on the convergence rate of a deep network that depends only on an imbalance quantity analogous to A? yes, how does such quantity depend network depth?
2. For two-layer networks, the bound reduces to / conditioned" (A+, A_ are small). For deep networks, can we characterize such joint contribution from the imbalance and product. given similar assumption?
+ 4o2 Miin (W) when the imbalance is "welll
We will answer these questions as we present our convergence results for deep networks.
5

---

Under review as a conference paper at ICLR 2023
4 CONVERGENCE RESULTS FOR DEEP LINEAR MODELS
4.1 THREE-LAYER LAYER MODEL
Beyond two-layer models, the convergence analysis for imbalanced networks not in the kernel regime has only been studied for specific initializations (Yun et al. 2020). In this section, we derive a novel rate bound for three-layer models that applies wide range of imbalanced initializations. For ease of presentation, we denote the two imbalance matrices for three-layer models, DI and D2, as
-1 W2W2 WF D21, D2 W2 W2 WyW3" D23.
(13)
Our lower bound on Aunn (T(w, (W)))) comes after few definitions.
Definition 1. Given two real symmetric matrices A, B of order n, we define the non-commutative binary operation Ar as AA, B = diag(mine { (A:(A), (
where 2y(-) +o0,
Definition 2. Given imbalance matrices (D21, D23) E RR x x Bhhxxha, define
D = (mammmmxx (( (D22))))),
Db2 = mmax (), Ac(D2s), 0112 (14)
221 (D,,) tr( An D21),
A 21 tr (r( - tr ((Dra An D21) ?), (15)
2
22 tr (D(b)) tr tr( Am D2s),
A (2) tr tt((D))) tr ((Duz Am D23) 2).
(16)
Theorem 2. When L = 3, given weights ( W2, Wa} with imbulance matrices (D21, D23), then for the lineur operator Wo.W.) defined in Lemma we huve
Amin (T(wi.Ws.ws)
2 24 (2) + + + A21 + 2 24 (2) + A223)
(17)
Proof Sketch. Generally, is difficult to directly work on Amin (T(W,,w..w,) and we use the lower bound Amin (T(wa.s,wwa) 2 A. WWWWWW,?? + An >n W {m) (WT Ws) +
Am (WT W WyWs). We show that given D21. D23, the optimal value of min W2,Wa,Wa
Am WW WWWWW,TWP) An Wm Am (W, W3) Am (WJ W. W2W3))
(18)
W2W7 W W1 D21.
W.W, W2 W3W D23
( + -211 421 A23 + ( + A23), the bound shown in see Appendix for the complete proof and detailed discussion on the proof idea.
A A D23) (
17 Please
L
With the theorem immediately have the following corollary. Corollary 1. When 3, given initialization with imbalance matrices (D21, D2s) and satisfying Al, the continuous dynamics in B satisfy
C(t) L < exp (-ayht) (C(0) L*), Vt 0,
(19)
where 03
(2) + A 221 A23 (4 + A23). (
We make the following remarks regarding the contribution.
Optimal bound via imbalance: First of all, as shown in the proof sketch, our bound should be considered as the best lower bound on Amin (T,w. (t))), one can obtain given knowledge of the imbalance matrices D21 and D23 only. More importantly, this lower bound works for ANY initialization and has the same role as does in two-layer linear networks, i.e., (T7) quantifies the general effect imbalance the convergence. Finding an improved bound that takes the effect of product min (W) into account is an interesting future research direction.
Implication convergence: Corollary 2 shows exponential convergence of the loss C(t) if az 0. While it is challenging to characterize all initialization such that 0g > 0, the case n = m = is rather simpler: In this case, Dh, A1 D21 Da and Dr, A1 Dz3 Dz3- Then we have
Au = tD.)... ) - tr(Da) = > (Ar(D,..) A((Da)) + An, An, (Dz) 2 -An, (Dz),

---

Under review as a conference paper at ICLR 2023
and similarly we have A2s 2 (D2s). Therefore, ag 2 A21 2 (D21 Abg (D2s) when both D21 and D23 have negative cigenvalues, which is easy to satisfy as both D21 and D23 given by the difference between two positive semi-definite matrices. Such observation can be generalized to show that (x > when D21 has at least y2 negative eigenvalues and D2a has at least m negative eigenvalues. Moreover, D21 and D23, please refer to the remark after Theorem 3 in Section 4.2 A better characterization of the initialization that has 0g is an interesting future research topic.
show that Og >> 0 under certain definiteness assumptions on
The way we find the lower bound in (17) is by studying the generalized eigen- value interlacing relation imposed by the imbalance constraints. Specifically, W.W. WT W1 D21 suggests that As+a (W2W2 S (D21) I (,W,,
Technical contribution:
W""). ), vi because W2 D21 is matrix of at most rank-n. We derive, from such interlacing relation, novel eigenvalue bounds (See Lemma F.6) 2 Wi) that depends on eigenvalues of both W.W2 and D21- Then the eigenvalues of W can also be controlled by the fact that W2 must satisfy both imbalance equations in (3). Since imbalance equations like those in (3) appear in deep networks and certain nonlinear networks Du et al. (2018): Le & Jegelka (2022) we believe our mathematical results are potentially useful for understanding those networks.
on A, (W Wi) and X, (W, W
Comparison with prior work: The convergence of multi- linear networks under balanced initialization (D; = 0, Vl) has been studied in Arora et al. 2018a|b) and our result is complementary as we study the effect of non-zero imbalance on the convergence of three-layer networks. Some settings with imbalanced weights have been studied: Yunn et al. (2020) studies special initialization scheme (D; 2 0, = 1, ... L 2. and Dz-1 Z )1a.-1) that forces the partial ordering of the weights, and Wu et al.) (2019) uses similar initialization study the linear residual networks. Our bound works for such initialization and also show such partial ordering is not necessary for convergence.
4.2 DEEP LINEAR MODELS
The lower bound we derived for three-layer networks applies to any initialization. However, the bound a fairly complicated function of all the imbalance matrices that hard to interpret. Searching for such a general bound is even more challenging for models with arbitrary depth (L 2 3). Therefore, our results for deep networks will rely on extra assumptions on the weights that simplify the lower bound to facilite interpretability. Specifically, we consider the following properties of the weights:
Definition 3. set of weights { [Wi)t with imbalance matrices (D; == W W; - W141 W L-1 said to be unimodal with index 1" if there exists some E [T.] such that
D 0, for 1 <<1" and
Dj - 0, for 1 12 r"
1= Am (m(--Dy (-Di), i2!" l" EE (Di), i<'"
We define its cumulative imbalances 1--1 DT= as des
Furthermore. for weights with unimodality index 1*, if additionally, Di = di 1,,,,, ffor
di 120, 0, for I |<F 1" and di S 0, for 1 121",
then those weights are said have homogeneous imbalance.
The unimodality assumption enforces an ordering of the weights w.r.t. the positive semi-definite cone. This is more clear when considering scalar weights {wi )- ,- in which case unimodality requires wf be descending until index 1* and ascending afterward. Under this unimodality assumption, we show that imbalance contributes to the convergence of the loss via a product of cumulative imbalanaces. Furthermore, we also show the combined effects of imbalance and weight product when the imbalance matrices are "well-conditioned" (in this case, homogeneous). More formally, we have: Theorem 3. For weights (wi)/a with unimodality index 1", we have
1-
Amin (TwmiH.)
II d
(20)
1=1
Furthermore, if the weights have homogeneous imbalance, then
1-11
2
L. (21)
Amin (T(wi)inn) 2
II
+ Lo
(L
Wi.
7

---

Under review as a conference paper at ICLR 2023
We make the following remarks:
Connection to results for three-layer: For three-layer networks, we present an optimal bound
Amin Main(Twe Tw,.W,
2 ( 221) + 22 + 2 ( 22)
given knowledge of the imbalance. Interestingly, when comparing it with our bound in 20 we have: {W1. W2, Ws} with unimodality index 1",
Claim. When = 3. for weights
1. 1ft" then 1 (
2
23 I deg and ] 4 A21 A23 0,
2. Ift = 2, then 2 23 = 11 d(s and ( + + ( - 423) 0,
3. If 3, then 1 (A2) 21 2 = -1 de and [ A23)) 221 A23 O.
(2)
We refer the readers to Appendix for for the proof. The claim shows that the bound in (20) is optimal for three-layer unimodal weights as it coincides with the one Theorem 2 We conjecture that (20) is also optimal for multi-layer unimodal weights and leave the proof for future research. Interestingly. while the bound for three-layer models is complicated, the three terms 2 (4 A23), A21.2..
those with unimodality. This hints at potential generalization of Theorem the deep case where the bound should have L terms capturing how close the weights are those with different unimodality (!" 1,... L.). L).
(AA (2) + A seem to roughly capture how close the weights
Effect of imbalance under unimodality:
For simplicity, we assume unimodality index l" = L. The d(i)). as product of cumulative imbalances, generally grows exponentially with the 1-11
bound I1
depth L. Prior work Yun et al. (2020) studies the case D; 2 0,7 1,... L- 2, and Dr.1 2 Alaz-1
in which case II d())= 2 X Our bound II f.-1 d(s) suggests the dependence on L could
be super-exponentiall When (D.) 2 c 0, for 1 = 1,... L.....,---... 1, we have -.--1 d(g) = E'' > 2 - le = ch 1)!, which grows faster in L than X for any A. Therefore, for gradient flow dynamics, the depth L could greatly improve convergence in the presence of weight imbalance. One should note. however, that such analysis can not be directly translated into fast convergence guarantees of gradient descent algorithm as one requires careful tuning of the step size for the discrete weight updates to follow the trajectory of the continuous dynamics (Elkabetz Cohen 2021).
With our bound in Theorem 3 we show convergence of deep linear models under various initialization:
Convergence under unimodality: The following immediately comes from Theorem 3
{O) are unimodal, then the continuous dynamics in Corollary If the initialization weights
3 satisfy
C(t) - L' exp (-annt) - V22,,
(22)
where
1. I satisfies Al only, then ar.
11 L-1 "(y
2. If satisfies both AI, A2, and the weights additionally have homogeneous imbalance, then
L-1
+ (W+) VK/Nl/W()) W- )
II
aL
with (0) = -I' Wi(0) and w equal to the unique optimizer of f.
Spectral initialization under le loss: Suppose
2|ly W and W -i Wi. We write
Ey
the SVD of Y E RAXm as Y P
Q where E O(n), Q E 0(m). 2, ... 1, (0) = V QZ where Li, = 1.. L are diagonal matrices of our choice and 1/1 E Raxhi, 1= 1- 1, L- with V/" In,- It can be shown that (See Appendix D. for details)
0
0
0
Consider the spectral initialization (1 = VE, Wi(0) = VI-
(1(1) (1)V Wi(() Vi_ V I 2, T- (z(() V (23)
8

---

Under review as a conference paper at ICLR 2023
Moreover, only the first diagonal entries of Σς are changing. Let oi,, Osyy denote the i-th diagonal entry of M1, and Ey respectively, then the dynamics of {ou,)f_1 follow the gradient flow on (i(forilla)) 2 diy II oid for i = 1, m, which is exactly a multi-layer model with scalar weights: [ww) |iiy w/ /2, , w = I w/ Therefore, spectral initialization under l2 loss can be decomposed into m deep linear models with scalar weights, whose convergence is shown by Corollary [ Note that networks with scalar weights are always unimodal, because the gradient flow dynamics remain the same under any reordering of the weights, and always have homogeneous imbalance, because the imbalances are scalars. The aforementioned analysis also applies to the linear regression loss f y XWI p provided that (x, Y is co-diagonalizable (Gidel et al. 2019). we refer the readers to Appendix D.I for details.
Diagonal linear networks: Consider f function on R" satisfying A1 and L= f(w, @ wr.. where wy E RD and @ denote the Hadamard (entrywise) product. The gradient flow on & can not be decomposed into several scalar dynamics as in the previous example, but can show that (See Appendix D.2 for details) -= -IV S -miingsisw Amin (T(m.. )) L*), where w1, the i-th entry of wn. Then Theorem gives lower bound on each Amin ( ((.,, Again, here the scalar weights { always have homogeneous imbalance.
Assumptions
Arora et al.
2018a
Yun et al. 2020
Ours
Unimodal
N/A
1-1
I r--1 d(i)
weights
Homogeneous
imbalance
N/A
v M d(i))² + 2-11 (W))²
Balanced
2-2/2 Lo Lo
(W)
N/A
Table 1: Compare our rate bound with prior work on deep networks.
Comparison with prior work: Regarding unimodality, Yun et al. (0020) studies the initialization scheme D, = 0, -,... L and Dz-1 2= AInr.,, which special case (1" L) of ours. The homogeneous imbalance assumption was first introduced in Tarmoun et al. (202I) for two-layer networks, and generalize it to the deep case. We compare, in Table 1 our bound to the existing work (Arora et al. 2018a; Yun et al. 2020) on convergence of deep linear networks outside the kernel regime. Note that Yun et al. (2020) only studies special case of unimodal weights (1" L. with d(s) X 0, Vi). For homogeneous imbalance, Yun et al. (020)) studied spectral initialization and diagonal linear networks, whose initialization necessarily has homogeneous imbalance, but the result does not generalize to the case of matrix weights. Our results for homogeneous imbalance works also for deep networks with matrix weights, and our rate also shown the effect of the product (W), thus covers the balanced initialization (Arora et al. 2018ap as well.
Remark 1. Note that the loss functions used in (uunasekar er al. (2018); Yun et al. (2020) are classification losses, such as the exponential loss, which do not satisfy A1. However, they do satisfy woais--aiaaiiiiiinneeeee allows us show O (t) convergence of the loss function. We refer readers to Section 4.3 for details.
condition [W](W)]l 2 ((( - VW E Ruxx, which
4.3 CONVERGENCE RESULTS FOR CLASSIFICATION TASKS
As discussed in Remark I. the loss functions used in classification tasks generally do not satisfy our assumption A1 for f. Suppose instead we have the following assumption for f.
Assumption 2. f satisfies (AI') ( 2 x(f(W)-)))))))))))))))>> f*), vW E R"
Then we can show O (4) convergence of the loss function, as stated below.
Theorem 4. Given initialization (Wi(0))/ such that Amin (Twi(o)E)) a, Vt 2 0, and
satisfying (A1") 1), then
[()) - L
C(t) - L' (C(0) - L- )ar2t +1
(24)
9

---

Under review as a conference paper at ICLR 2023
We refer readers to Appendix for the proof. The lower bound on Amin ( (WW) can be obtained for different networks by our results in previous sections. The exponential loss satisfies A1' (see Appendix and is studied in Gunasekar et al. (017);; Yun et (2020) for diagonal linear networks.
CONCLUSION AND DISCUSSION
In this paper, we study the convergence of gradient flow on multi-layer linear models with a loss of the form S(W, W2 ..2...W Wr.), where f satisfies the gradient dominance property. We show that with proper initialization, the loss converges to its global minimum exponentially. Moreover, we derive a lower bound on the convergence rate that depends matrices, which measure the difference between the weights of adjacent layers, and the least singular value of the weight product W Wi W2 WL. Our analysis applies various types of multi-layer linear networks, and our assumptions on f are general enough to include loss functions used for both regression and classification tasks. Future directions include extending our results to analyzing gradient descent algorithms as well as to nonlinear networks.
two majectory-specifte quantities: the imbalance
Convergence of gradient descent: Exponential convergence of the gradient flow often suggests linear rate of convergence of gradient descent when the step size is sufficiently small, and Elkabetz Cohen (02T) formally establishe such a relation. Indeed, Arora al. 20)8a) shows linear rate of convergence of gradient descent on multi-layer linear networks under balanced initialization. A natural future direction is to translate the convergence results under imbalanced initialization for gradient flow to the convergence of gradient descent with small step size.
Nonlinear networks: While the crucial ingredient of our analysis, invariance of weight imbalance, no longer holds in the presence of nonlinearities such as ReLU activations, Du et al. (2018) shows the diagonal entries of the imbalance are preserved, and Jegelka (2022) shows a stronger version of such invariance given additional assumptions the training trajectory. Therefore, the weight imbalance could still be used to understand the training of nonlinear networks.
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- paramcterization. In International Conference on Machine Learning, pp. 242-252. PMLR, 2019.
Sanjeev Arora, Nadav Cohen, Noah Golowich, and Wei Hu, A convergence analysis of gradient descent for deep linear neural networks. In International Conference on Learning Representations, 2018a.
Sanjeev Arora, Nadav Cohen, and Elad Hazan. On the optimization of deep networks: Implicit acceleration by overparameterizzaton. In 35th International Conference on Machine Learning, 2018b.
Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep matrix factorization. Advances in Neural Information Processing Systems, 32, 2019a.
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. Advances Neural Information Processing Systems, pp. 8141-8150 2019b.
Lenaic Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable programming. In Advances Neural Information Processing Systems, pp. 2937-2947, 2019.
Simon Du and Wei Hu. Width provably matters in optimization for deep linear neural networks. In International Conference on Machine Learning, pp. 1655-1664, 2019.
Simon S. Du, Chi Jin, Jason D. Lee, Michael Jordan, Barnabás Póczos, and Aarti Singh. Gradient descent can take exponential time to escape saddle points. In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS' 17, pp. 1067-1077. Red Hook, NY, USA, 2017. Curran Associates Inc. ISBN 9781510860964
10

---

Under review as a conference paper at ICLR 2023
Simon S Du, Wei Hu, and Jason D Lee. Algorithmic regularization in learning deep homogeneous models: Layers are automatically balanced. In Advances in Neural Information Processing Systems (NeurIPS), 2018.
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over- parameterized neural networks. In International Conference on Learning Representations//CCRR)) 2019, 2019.
Omer Elkabetz and Nadav Cohen. Continuous vs. discrete optimization of deep neural networks. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021.
Rong Ge, Chi Jin, and Yi Zheng. No spurious local minima in nonconvex low rank problems: A unified geometric analysis. In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 1233 1242. PMLR, 06-11 Aug 2017. URL https://groceeiing/ mlr press/v70/ 0 html
html
Gauthier Gidel, Francis Bach, and Simon Lacoste-Julien. Implicit regularization of discrete gradient dynamics linear neural networks. In Advances in Neural Information Processing Systems, volume 32, pp. 2202-32111 Curran Associates, Inc., 2019.
T. H. Grönwall. Note the derivatives with respect to parameter of the solutions of system of differential equations. Annals of Mathematics, 20(4):292-296, 1919. ISSN 0003486X.
Suriya Gunasckar, Blake Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nathan Srebro. Implicit regularization in matrix factorization. In Proceedings of the 3/st International Conference on Neural Information Processing Systems, pp. 6152-6160) 61600, 2017.
Suriya Gunasekar, Jason D Lee, Daniel Soudry, and Nati Srebro. Implicit bias of gradient de- scent on linear convolutional networks. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianche and R. Garmett (eds.), Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018. URL URL/httpss//porcceedinss neur cc/ pdf
Benjamin D Haeffele and René Vidal. Global optimality in tensor factorization, deep learning, and beyond. arXiv preprint arXiv: 2015.
Benjamin D Haeffele and René Vidal. Global optimality in neural network training. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 7331-7339, 2017.
Geoffrey Hinton, Li Deng, Dong Yu, George E Dahl, Abdel-rahman Mohamed, Navdeep Jaitly, Andrew Senior, Vincent Vanhoucke, Patrick Nguyen, Tara N Sainath, et al. Deep neural networks for acoustic modeling in speech recognition: The shared views of four research groups. IEEE Signal processing magazine, 29(6):82-97, 2012.
Roger A. Homn and Charles Johnson. Matrix Analysis. Cambridge University Press, New York, NY, USA, 2nd edition, 2012.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization neural networks. In Advances in neural information processing systems, pp. 8571-8580, 2018
Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M. Kakade, and Michael I. Jordan. How escape saddle points efficiently. In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning URL httts::
Research, pp. 1724-177 1732. PMLR, 06-11 Aug 2017.
mlr
press/v70/ htm
Kenji Kawaguchi. Deep learning without poor local minima. In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett (eds.), Advances in Neural Information Processing Systems, vol- ume 29. Curran Associates, Inc., 2016. URL

---

Under review as a conference paper at ICLR 2023
Alex Krizhevsky, llya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolu- tional neural networks. In Advances in neural information processing systems, pp. 1097-1105, 2012.
Thien Le and Stefanie Jegelka. Training invariances and the low-rank phenomenon: beyond linear networks. In International Conference on Learning Representations, 2022.
Jason D. Lee, Max Simchowitz, Michael I. Jordan, and Benjamin Recht. Gradient descent only converges to minimizers. In Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir (eds.), 29th Annual Conference on Learning Theory, volume 49 of Proceedings of Machine Learning Research, pp. 1246-1257, Columbia University, New York, New York, USA, 23-26 Jun 2016. PMLR. URL https::/prrcceddiii
ml. www.prpessss.... v49 /wte///e/......./ html
Hao Li, Zheng Xu, Gavin Taylor, Christoph Studer, and Tom Goldstein. Visualizing the loss landscape neural nets, In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018a.
Jannguan Li, Thanh V Nguyen, Chinmay Hegde, and Raymond K. W. Wong. Implicit sparse regularization: The impact of depth and early stopping. In A. Beygelzimer, Y. Dauphin, Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021a. URL //pprr//eeeeeevee.... net/ forum? wwwiidd-MMM- QMBoG0bz1o
Yuanzhi Li, Tengyu Ma, and Hongyang Zhang. Algorithmic regularization in wer-pparamtterized matrix sensing and neural networks with quadratic activations. In Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet (eds.), Proceedings of the 31st Conference On Learning Theory, volume 75 of Proceedings of Machine Learning Research, pp. 2-47. PMLR, 06-09 Jul 2018b. html
URL httptttst///poceeeeee http://ccceeennan...ppeeeee////.
mlr wwtppprrssswwlseeeee
Zhiyuan Li, Yuping Luo, and Kaifeng Lyu. Towards resolving the implicit bias of gradient descent for matrix factorization: Greedy low-rank learning. In International Conference on Learning Representations, 2021b.
Hancheng Min, Salma Tarmoun, René Vidal, and Enrique Mallada. On the explicit role of initializa- tion on the convergence and implicit bias of overparametrized linear networks. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 7760-7768. PMLR, 18-24 Jul 2021.
Hancheng Min, Salma Tarmoun, René Vidal, and Enrique Mallada. Convergence and implicit bias of gradient flow on overparametrized linear networks. arXiv preprint arXiv:2105.06351, 2022.
Boris T. Polyak. Intoduction optimization. New York: Optimization Software, Publications Division, 1987.
Walter Rudin. Principles of mathematical analysis. McGraw-Hill Book Company, Inc., New York-Torontee Tirk-Tornnto-Lnddnn 1953.
Andrew M Saxe, James L Mcclelland, and Surya Ganguli. Exact solutions to the nonlinear dynamics of learning in deep linear neural network. In International Conference on Learning Representations, 2014.
David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schritwieseer, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):484, 2016.
Dominik Stöger and Mahdi Soltanolkotabi. Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstmuction. Advances in Neurul Information Processing Systems, 34, 2021.
Ju Sun, Qing Qu, and John Wright. When are nonconvex problems not scary?, 2015. URL https://arxiis http:///wwxxx..oo///////////////
otg. 06096
12

---

Under review as a conference paper at ICLR 2023
Salma Tarmoun, Guilherme França, Benjamin D Haeffele, and René Vidal. Understanding the dynamics of gradient flow in overparameterized linear models. In Proceedings of the 38th International Conference Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 10153-10161. PMLR, 18-24 Jul 2021.
Gerald Teschl. Mathematical methods in quantum mechanics: With applications to schrödinger operators, second edition. 2014.
Yi Wang and Sainan Zheng. The converse of weyl's eigenvalue inequality. Advances Ap- plied Mathematics, 109:65-73, 2019. ISSN 0196-8858. doi: http:///bi.orr//100006...aam 2019.05.003. URL https: htop::///wwww/// sciencedirect.
com wwweeeettcoc/cccieeeeeeeeeee httm///ccceee/aall/pp..i.
5019688581 9300867
Lei Wu, Qingean Wang, and Chao Ma. Global convergence of gradient descent for deep linear residual networks. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and
R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran As- sociates, Inc., 2019, URLEstps://prcceeddn.s http://pppcceeeinenno..e.......p neurips...... /t.pp///s.///pppe/////////.
Chulhee Yun, Shankar Krishnan, and Hossein Mobahi. unifying view on implicit bias in training linear neural networks. In International Conference on Learning Representations, 2020.
13

---

Under review as a conference paper at ICLR 2023
A CONTROLLING PRODUCT WITH MARGIN
Most our results regarding the lower bound on Amin [(wa)_, are given as a value that depends on I) the imbalance of the weights; 2) the minimum singular value of the product W I The former is time-invariant, thus is determined at initialization. As we discussed Section we require the notion of margin to lower bound mii (W (t)) for the entire training trajectory.
The following Lemma that will be used in subsequent proofs.
Lemma A.1. If f satisfies A2, then the gradient flow dynamics satisfies
K IW(0)) W Ir 000
mmn (W()) 2 miin (W*)
where (t)) = II (i( and W is the unique minimizer of f.
From Polyak 1987). ), we know if f is u-strongly convex, then has unique minimizer W and
Proof.
f(W) f ||
W - 1'
Additionally, if f is K-smooth, then
f(W) - fr $ 2
W - W*1
This suggests that for any 2 O,
K
(
W' 1 2 L(t) L- 2 IW W 1/.
Therefore we have the following
Omin (W)
miiu (W(t) W + W")
(Weyl's inequality (Horn Johnson, 2012 7.3.P16))
2 min (W*)
[(()) W/
M minn (W*)
[ W'|lF
V 2 (C(t) - L*)
(f is j-strongly convex)
W mmin (W*)
V 2 (C(0)) L*)
(C(t) non-decreasing under
2v Omiu (W*)
K
(f is K -moothh)
> Tmin (W*)
V μ
[I - W
Tmin (W*)
V (W()) - W'
Lemma A.I directly suggests
K [()0) WF == margin
Tmin (W)+)) 2
Owin (W*)
V
and the margin is positive when the initial product W(0) is sufficiently close to the optimal W*.
14

---

Under review as a conference paper at ICLR 2023
B CONVERGENCE ANALYSIS FOR CLASSIFICATION LOSSES
In this section, we consider f that satisfies, instead of A1, the following Assumption 3. satisfies (AI") the Lojasiewicz inequality-lke condition
[V 2 (((W) ; vW E -Ruxm.
Theorem 4 (Restated), Given initialization (Wi(0)) such that
Amin T(Wi(0HL) 2 a, W200
and f satisfying (Al') ) then
C(0) - L- C(t) - 6- 1 (C(0) 11 +
Proof. When satisfies (A1'), then (5) becomes
c (TIwi)A Vf(W), VF(W),
< -Amin (TeWOH [VS(W)
(A1') S -Amin (Twwitt.)) (2(((W) f=)²= -Amin (Twwitte) 7p(c 2-
This shows
d (C (C- L*) 2 Amin (Temiste)) 7²2 an2
(C (C- dl
Take integral f di both sides, have for any 2 0,
1
2 2r?
-- rr 0
which is
[(0) - L
C(t) - - (C(0) - L-)
Following similar argument as in Yun et al. (2020), show that exponential loss on linearly separable data satisfies A1'. Claim. Let f(w) Em exp (- (of w)), if there exists E Sn-1 and 0 such that (= 2) 7, 1......,. ,N,
then
[V](w)|| 2 ((w),, Vw E R
Proof. Using the linear separability, we have
[
exp (-ys (xz (xTTw)) w)) youz
inequality)
2,
exp (-y: ( w)) yerr
i=1
2 exp (-y: (o w)) >
=1f(w))2
as desired.
Therefore, convergence results applies to classification tasks with exponential loss.
15

---

Under review as a conference paper at ICLR 2023
C PROOFS IN SECTION 2
First we prove the expression for È in Lemma
Lemma (Restated). Under continuous dynamics in 13 we have
i == = ((Wi)=)) 1
= (T Vf(W), ((W)))f(W)
where W Il Wi, and T(wi) a positive semi-definite linear operator on Ruxx with
Twwi)
Σ
II w
II
W;
E
W
II W;
W. 1, WL+1 Lm
1i=l11
A+/++1
Proof. The gradient flow dynamics
satisfies
d Wi dt aw. ((Wi)E)))
T II,, W;
L+1
VS(W)
II
W;
(C.1)
where W = - W; and Wo = In WL+1 Im.
Therefore
0
L ((Wi)
Wi
OW
dt
1=1
Σ
C ((Wi)+=))
aw;
1-1
L+1
T
T
L+1
II W
VS(W)
W
II
W
VS(W)
II
W
L+1
L+1 II
W
I W
VS(W)
II N11+1
W
W
(.(W))
L+1 II N=H+
L+1
W
W
Vf(W)
W
II W
V.((W)
v=t++
(Twii VS(W), V((W))
Next, we prove that the imbalance matrices are time-invariant
Lemma 2 (Restated). Under continuous dynamics 3 we have Di(t) - 0, 0,1= -1,.,,,-11
Proof. Each imbalance matrix defined as
D: = WT.. W: Wi41WT WT / 1,... 1,, L-11
We only need to check that (WFWi) and # (Wi+iE2)) are identical.
16

---

Under review as a conference paper at ICLR 2023
From the following derivation, for / 1,... L 1,
(w) dt
WFW W.W.
L+1
II W (=111
VH S(W)
II W
Wi W
II W;
VS(W)
II <i=++
L+1
1 II W
T
L+1
II W
f(W)
II We
Vf(W)
II W
d
(W1+1 Wi+1) di
Witi + Wi+1WZ1
T
L-1
(i W.
II W V=l
VS(W)
II W
W W41
πI Wi
J s(w)
v=1+2
1-142
1 II
L+1
L+1
W.
VS(W)
II
W
II W V+=++1
V ((W)
[[
we know (W7 = d (Wi+1 WT+.) therefore Di(t) = 0, 1,,,, ,,
17

---

Under review as a conference paper at ICLR 2023
D LINEAR MODELS RELATED TO SCALAR DYNAMICS
D.1 SPECTRAL INITIALIZATION UNDER lp LOSS
The spectral initialization Saxe et al. 2014); Gidel et al. 2019): Tarmoun al. (2021 considers the following:
Suppose f = 1111Y= - X and we have overparametrized model W = II==1 W,. Additionally, we assume Y E RNNmm X RNx (n 2 m) are co-diagonalizabl, i.e. there exist P E RN** with p P In and Q 0(m), E ((n) such that we can write the SVDs Y, as Y
Σy
0
Q
P
Q and X PL.
Remark 2. In Section 4 we discussed the case f y W which is essentially considering the aforementioned setting with N = n and X = In.
Given any of weights {Wi) such that
WL V Wi = RE, VT" Wi Vi- VVV', 1= 2,..,,,..
where E,, = 1,.... are diagonal matrices and Vi2 Raxki, 1, L 1 with V/ Imn- The gradient flow dynamics requires
W ac
OW,
-Y XWWWEW ...TT
-REXPP (PEy (PExQ-PEXRR 26 ( V2-1EL-1V -.E
L
L
= R
Ex
Σy - Ex II
E1
QQ"
Σ1
VT
1=1
1=2
L
Im
R
Σx
Ey
Ex
II Σ,
II
Σ
VT.
[=1
1=2
which shows that the singular space R, Ví for W1 do not change under the gradient flow, and the singular values of W1 satisfies
L
Tiay - Ti.
0ia
oi.
oid i = 1, 1, m
1=1
and ,,, = 0, = m + 1, ..... n.
Similarly, show that
Im 0
W., = Vi-1 Ex
Ey - Ex
II E,
Σ,
V
2,....
L-
am1
Lm
0
WL = VZ-1
Σx
Ey - Ex II
Σg
Σ
Q.
0
i=1
L
Overall, this suggests that the singular space of {wi) do not change under the gradient flow, and their singular values satisfies, for i = 1, 1,... m,
oi.y dz. II Oik
oi,z II o 1- 1, 1,...
k=1
kzl
Each dynamic equation is equivalent to the one from gradient flow on Le(Hou))))) = Jiyy oi. I' o. Therefore, under spectral initialization, the dynamics of the weights decoupled into at most dynamics diseussed in Section 4.2
18

---

Under review as a conference paper at ICLR 2023
D.2 DIAGONAL LINEAR NETWORKS
The loss function of diagonal linear networks Gunasekar et al. 2017 Yun et al. (2020) is of the form [um .... 2 Wr.), we write
7
(((m))f))) f(wr .... (..) f(w(1) ,.. mm()) f
II
W1,1
wi.
i.. f takes variables w ,.. w(a) and each variable w(() is overparametrried into II W1,6-
Then we can show that
-I
(w) 1
CI? Oc 2
L
iwn,
0,
(1
Owi(i
Owiz
0
(1)
Oww
Owi,
1-1
0ʃ
iro(i)
1
0f 2 Owc(1)
S
T(w,, 15i5n
min
(f satisfies A1) S min Isišn (m
7l f²)=
T(m.i) ) 7(C L*). ---ii Isisn
min
Moreover, the imbalances (4) = wp, w are time-invariant for each 1,... n
( by Lemma Therefore, we can lower bound each T( using the imbalance (d) ]1=1 in Proposition from which one obtain the exponential convergence of L.
[
19

---

Under review as a conference paper at ICLR 2023
E PROOF FOR TWO-LAYER MODEL
Using Lemma we can prove Theorem
Theorem (Restated). Let be the imbalance matrix L 2. The continuous dynamics in satisfy
L(I) - S exx
0,
(E.2)
where
1. f satisfies only A1, then a2 A
2. f satisfies both Al and A2, then
02 = A + (A+ A)2 + A) (K/Hl/(())> - - )
A_ A + + 4 ( - (K/)))////l - (E.3)
with W(0) = II Wi(0) and W equal the unique optimizer of f.
Proof. As shown in 5 in Section 2
We have
d
(C(t) L*) -miin 7(w. L*).
de
Consider any (Wi (t), W2(t)} on the trajectory, we have, by Lemma
Lemina i
Amiu T(W (1,,
(-A- + V (A +) 40 (W()))
- + A 40 (W()))
(-A++ V A AA +
02
2
When / also satisfies A2: we need to prove
on (W(1)) > on (W*) VK/H(((0)) W
(E.4)
(W(I) 2 (W*)
M'
(E.5)
When n = m, both inequalities are equivalent to
mmin (W)))) 2 mmin - (0) W*
which is true by Lemma A.1
When # m, one of the two inequalities become trivial. For example, if n m, then E.4
trivially 0 2 0, and (E.5) is equivalent to
Omin (W(t)) (omin(('))
(K/H(W(O)) W*
which is true by Lemma A.1
20

---

Under review as a conference paper at ICLR 2023
Overall, have
Amin (WW
Lemman
1
2
- + ( 40 (W()))
2
A + (W(1))
1
-A+ + V ( + + +4 4 (wo -w-1s].))
2
A + (A_ - a)2 +4 (om - (K/ - -
0
Either case, we have de (C(t) L*) s -az)(C(t) - ), and by Grönwall's inequality, we have
[(t) - s (cxp(-a2tt)((()) - -)).
21

---

Under review as a conference paper at ICLR 2023
F PROOFS FOR THREE-LAYER MODEL
In
Section F.1 we discuss the proof idea for Theorem then present the proof afterwards. In Section
we show simplified bound when the weights can be ordered w.r.t. positive-emideefiitneess..
F.1 PROOF IDEA
We first discuss the proof idea behind Theorem 2 then provide the complete proof. Consider the case when Rlxhi x ghaxha x |phax1, The quantity we need to lower bound is
m 1, we use the following notations for the weights (wf. W2, wy)
Amin [wo , w W2W2 w1 + w W1 wg w' + wg W2TW W2w3
= [W] w1 11 + || ||03|| + 1|22wall,
where our linear operator
[wu Warws) reduces to a scalar. The remaining thing to do is to find
min wf .22000
[[W w1 112 - ||w || w>ll + ||W2w3|1
(F.6)
s.t.
W₂ W w1 "w D21
W W2 Wzms = D23
i.e, we try to find the best lower bound Amin (wT .2,.w3) given the fact that the weights have to satisfies the imbalance constraints from D21, D23, and Amia some weights ||w]]| Il. ||wa|]| and the "alignment" between weights [[W wi [l. [|2awall-
[w/] Taal Wa.ws) is related to the norm of
The general idea of the proof is to lower bound each term [W] wi || || 1| ||wal12, ||2 individually given the imbalance constraints, then show the existence of some {wo W2, w3} that attains the lower bound simultaneously. The following discussion is most for lower bounding ||wa]|, Il. W will but the same argument holds for lower bounding other quantities.
Understanding what can be chosen to be the spectrum of W2 W (WT W2) is the key to derive an lower bound, and the imbalance constraints implicitly limit such choices. To see this, notice that W? wy wpr D21 suggests an eigenvalue interlacing relation (Horn & Johnson, 2012 Corollary 4.39) between W2w and D21, i.e.
Au (D21) S Aua (W2W3") I A S..
S AD & (WW,)
Therefore, any choice of (X.(W2W? ) must satisfy the interlacing relation with (
Similarly, (WT W2) (W)
hi must satisfy the interlacing relation with {Aa(D Moreover, hg
( ) and {M: W2) Je agree on non-zero eigenvalues. In short, an appropriate choice of the spectrum of W, W2 (W2 W2) needs to respect the interlacing relation with the eigenval- ues of D21 and D23-
The following matrix is defined
Dr, ==
to be the "minimum" choice the spectrum W2W (W? W2) in the sense that any valid choice of (A,(WW?))) Ma must satisfies
>.WWWW?) 2 A,(D),)) Ax(D21) .........h h1
That is, the spectrum of Dr, "lies between" the one of W2W2 and of D21. Now we check the imbalance constraint again W2W:"" -wiwf D21, it shows that: using a rank-one update w wf one obtain the spectrum of D21 starting from the spectrum of W.W2 and more importantly, require the norm ||wa|| II? to be (taking the trace on the imbalance equation)
tr"W - || 2|2 = tr(D)1)
||w 1|2 tr(W tr(WWW?) - tr (r()))
Now since Dr, "lies inbetween", we have | 1|2 = tr(WWW?) - tr(D21)
(changes from X; (W,W") to Ar(D21)
(changes from X₂ \WW,W, to (D(,,,,) )) (changes from >D(,,,, to (e(a))
(changes from X₂ (Di,,, to X: (D2)) tr(D..,) tr(Dz)),
22

---

Under review as a conference paper at ICLR 2023
which is a lower bound on ||w]|? It is exactly the A21 in Theorem 2 takes more complicated form when n >> 1).
A lower bound on [[W] wil oI requires carefully exam the changes from the spectrum of Dr, to the one of D21. If Ab, (D2)) < 0, then "changes from DD( to (D21)) has two parts
1. (changes from Az (D) to (A((P2))L+) through the part where wi is "aligned" with W
2. (changes from 0 to An (D21)) through the part where wi "orthogonal" to W.'.
Only the former contributes to | W1 w1l² hence we need the expression (2)) + A21, which excludes the latter part. Using similar argument we can lower bound ||wa]l? [|Waw3 12 Lastly, the existence of [wi W2, w3 J that attains the lower bound is from the fact that Dr, (Dn,) is valid choice for the spectrum W2W2 WW2)
The complete proof of the Theorem 2 follows the same idea but with generalized notion of eigenvalue interlacing, and some related novel eigenvalue bounds.
F.2 PROOF OF THEBOREM
Theorem Dis the direct consequence of the following two results.
Lemma F.1. Given any set of weights {W1, W2, Wa} E gaxhs Rhxxaa Rhaxm we have (W3 Amin T(W,, 2 >n (W1 W2 W wf) + An (W1 wi) (W (3) + Am (W3 W W2W3).
(Note that Amin T(W,,w WW,WW,, does not have closed-form expression. One can only work with its lower bound A, (W1 W2W'" An (W1W7) Am (WTWs) + Am (WTT.,WWWWW
Theorem F.2. Given imbalance matrices pair (D21, D23) RAixh1 Rhuxha then the optimal value of
(An(WW WT) + Aa (W: )m (WTWs) + Am WFWWWWWW. W2,Wg,W3
min
s.t.
W2W7 - WT W1 = D21
W2 - WoW = =D23 W W.W-
(D21 D23) A + A + 2A21 A23
Ag +
(2)
Combining those two results gets Amin T (w,,,,,W.) 2 AD21 Dzs)/2, stated in Theorem
The Lemma F.I is intuitive and easy to prove:
Proof of Lemmal
F.
Notice that T(W,,WaWW)) is the summation of three positive semi-definite linear
operators on Raxm i.e.
Tww. T12 + T13 + T23
where
TiEE = W WWW WTE, T = W,W EWW Wa. Ta = EW3 W W2W3,
and Xmmin T12 Am (Wa W W.W,).
WWWWWWW3WT Amin Tis (n Ww),s), Amin T23
Therefore, let Emin with || | have
be the eigenmatrix associated with Amin TWW,.WyWa.)
Amin T(W,W,,Ws) (T12, Emin) F + (T1s, Emin) F + (T23, Emin)
(T.). Emin)
2 Amin T12 + Amin T13 + Amin A2inT23-
The rest of this section is dedicated to prove Theorem
We will first state a few Lemmas that will be used in the proof, then show the proof for Theorem F2 and present the long proofs for the auxiliary Lemmas in the end.
23

---

Under review as a conference paper at ICLR 2023
F.3 AUXILIARY LEMMAS
The main ingredient used in proving Theorem F.2 is the notion of r-interlacing relation between the spectrum of two matrices, which is natural generalization of the interlacing relation as seen in classical Cauchy Interlacing Theorem (Horn & Johnson 2012. Theorem 4.3.17).
Definition 4. Given real symmetric matrices A, B of order n, write A ス, Bf
(A) (B) I (x(A), ,ii
where X-(+) = +00. S and 2y(1) -00, n. The case gives the interlacing relation. Claim. We only need to check
(1) 5 S \B & Wi
for showing A c B.
Proof. Any inequality regarding index outside [z] is trivial.
The following Lemma a direct concequence of Weyl's inequality (Horn & Johnson 2012 Theorem 4.3.1) I), and stated as special case of (Horn & Johnson 2012 Corollary 4.3.3)
Lemma F.3. Given real symmetric matrices A, of order n, if A is positive semi remi-definit and rank(A A - B) S then A 2r B
The converse is also true
Lemma F.4. Given real symmetric matrices A, B of order n, if A Z B, then there exists positive semi-definite matrix XXT with rank XXT) S r and a real orthogonal matrix V such that A XX"" VBVT.
Proof. The case r is proved in (Horn & Johnson, 2012 Theorem 4.3.26). The case r > is proved in (Wang & Zheng 2019 Theorem 1.3) by induction.
Specifically for our problem, we also need the following (Dh, and Dns are defined in Section 4
Lemma F.5. Given imbalance matrices pair (D21, D2s) E xhi R we have Di, In D21 and D Zm D23.
In our analysis, the weights Wi, W2, W3 are "constrained" by the imbalance D21, D23. such con- straints leads to some special eigenvalue bounds (The operation Ar was defined in Section 4 Lemma E.6. Given an positive semi- definte matrix of order n, and Z E Rexn with r S n, when
A n = B,
we have
(ZZZ > tr(A) tr(A A, B),
and
2x, 2,AZ7) 2t ir (43) - (rA B)3) + (tr(A)- - Ir(A,, B))²
and this bound is actually tight
Lemma F.7. Given two real symmetric matrices A, B of order n, if A E, B (r S n), then there exist Z pexa and some orthogonal matrix V On),, such that
A- Z
and
( = -r(A Ar B),
2*,(Z) (A2) ((A Ar B)2) + (tr(A) -tr(-trAAA A, B))²
Remark 3. To see how Lemma F.6 is used, let A = W2W? and = W1, B D21, obtain lower bound on X, W that depends on the entire spectrum of W. and Da This bound is strictly better than X, (W2WW 2012). This should not be suprising because we have "more information on W, W and D2i (entire spectrum v.s. certain eigenvalue).
X (Dz1), the from Weyl's inequality (Horn & Johnson
24

---

Under review as a conference paper at ICLR 2023
F.4
PROOF OF THEOREM F.2
With these Lemmas, we are ready to prove Theorem
F.2
Proof of Theorem F.2 The proof is presented in two parts: First, we show (D(2 D23) is lower bound on the optimal value; Then we construct an optimal solution (W1. W2, W33 that attains (D2,, D2s) as the objective value.
Showing A (D21. D2s) is lower bound: Given any feasible triple (W1. W2, Ws), the imbalance equations
W2 W W1 D21
(F.7)
W W2 - W3W, = D23
(F.8)
implies W2W2 In D21 and W W2 Zm D23 by Lemma F.3 These interlacing relation shows
2 2 (D21), M(W W2) AxD2))) Vi,
which is
>(WWW2 = (WW, W2) 2 ( A.(D,,. 20,ii [h1]
(F.9
Now by Lemma F.6. imbalance equation (F.7) suggests
Ww, 2 tr(W, tr(WWW? An D21),
and
2A, (W, WWW
2 tr (WWWZ)) )) tr (WWW) An D21)²) + (tr(W,W3) tr(w An Dz)))²
Notice that
(WWW))) 2 tr(WeW?) tr( An D21)
h1
max(A(WW2W3)- - -
max (a: (D21)n(D22)
tr (D,,) tr (Di, An D21) A21
(F.10)
where the inequality holds because (F.9) and the fact that ReLU function f(x) max(æ, 0} is monotonically non-decreasing function.
Since A21 can be viewed as summation of ReLU outputs, it has to be non-negative, then F.10 also suggests
(tr(WWW2) -trWW An Dz)))² A
(F.11)
Next we have
2A (WWWWW?
(WWWW (3) - (WWWW An D21)2) + (tr(W2W,3) - trW An D21))²
A + tr (WWWW3)2 tr (WWWWT An D21)²)
A3
(WWW? (min(x(WWWW)) det1-n
21
i=1
2 A Σ (Dr,))
A 21
tr (D%,) tr ((Dr, An D21)2) A2 + +
25

---

Under review as a conference paper at ICLR 2023
where the last inequality is because (F.9) and the fact that the function
0.
x x
( = x² - (min(xx
x a²²
x>a
is monotonically non-decreasing on Ryo for any constant a E R.
At this point, we have shown
An (W 2 221 2 WW, Wf) 2 4 + + We can repeat the proof' above with the following replacement
(F.12)
22 + WT, W1 + WT, D21 + D23, Dny + Dn2
and obtain
Am (W3 W3) 2 A
2Am (W 2 43 + A
(F.13)
These inequalities F.12 F.M.F.13 F.13) show that
A' (D2,, D23) = 2 + A2 + 22m1
A
is lower bound on the optimal value of our optimization problem. Now we proceed to show tightness.
Constructing optimal solution:
By Lemma E55 we know Dry In D21, and by Lemma E7 there exists Z E [Ruxhi and orthogonal
Vi E ((h)) such that
Dn. 2 = VVD
(F.14)
and most importantly,
An (Z A2I.
2An Zf) 4 + A2
(F.15)
Similarly, by Lemma Lemma R5 we know Dng Zm D23. and by Lemma E7 there exists Z3
Rixihg and orthogonal V33 E O1h2) such that
D 23 2z = V3D23V3
(F.16)
and most importantly,
Am (ZzZz)
A23
22m
(Zg 23))
- (2)
+ +A
(F.17)
Let
ViT'
D
(ha-(ha-
V3,
h1 2 h
W
D
VT
V22
h12 < h1
( ((1)))2)xh, xh2
where D (max
(max();(Da))))) (Dx A, (D21), 0}) min (in and
WT ZiVi,
= W3=V 2g
we have
WS(WW)) (WT)= = VTT V1 Vf D21 (W;) WT(W3) V2J Dr, 1/3 V3 V/2533-- D23.
and
(WW(())))) x.(ZZ Az1
Am (WW)) Am (Zf A
2A, WW >r 24 - + +
2Am. ((W)) (WG))(() = Am 23 Dr, A - A
Therefore the lower bound A (D21, D2a) is tight.
26

---

Under review as a conference paper at ICLR 2023
F.5 PROOFS FOR AUXILIARY LEMMAS
We finish this section by providing the proofs for auxiliary lemmas we used in the last section.
Proof of Lemma F.5 Since (D21, D2s) is a pair of imbalance matrices, there exists W2W2, such
that
W In D21, W W2 Zm D23.
(F.18)
because at least our weight initialization W1 (0), W2 Ws(0) have to satisfy W2 WT(0) = D21, W2 (0)W2(0) - W (0) = D23- Therefore, for 0 < i h1 -1 n,
Aetn (Di.) maxx(A++) (Dz), Artn (D23) 0} S Aeta (W2W2) S (2(22)) S (Dr.), where the first two inequalities uses (F.18) and the fact that Actn (W,W2) = Aptn (WTW2). Also the last inequality is from the fact that (D,,, = max (A: ( (D2)) 0), Vi E [M1]]
For h 2 i > h1 n. we still have
00 00= = Aetm -ett((nn))) S Ar(D2)) & (Dm,))
Overall, we have
((P2) S (.Ph),
which is exactly Dr. čn D21.
Similarly, for 0 i h2 m.
Am (aa)) = max (m (D21); ), Am (D2s), 03 S Ai+m W2)
W2) S (,23)) S <Di(Dia),
where the first two inequalities uses (1.8) and the fact that Xitm (W2W?) Aitm (W?W2) Also
the last inequality is from the fact that A (n.) = max() A: (D2)) 0), Vi |/2)].
For h2 2 i h22 m, we still have
x = Aitm (aam(Drr)) S ( Ax(2s)) S (D(D)))
Overall, we have
(Dhal S (D23)) S \x(D)a)) Vi,
which is exactly Dng Zm Dzs.
Proof of Lemma F.6 Notice that rank Z) S r, hence we consider the eigendecomposition
zTz Z = Σ A Z)ouT'
where i are unit eigenvectors of TT Z. Then we can write
A X, \2 2oo
Σ
\Z 2uu =B B
We let D A A->, Zyeu?" then by Lemma suggests that Vi,
R3 we know A 11 D. and D 2,-1 B, which
(A) & A,DD S (A4
(F.19)
X I (B) (D))
(F.20)
In particular, we have A₂(D) < (x(A) from F.19) and X₂(D) S Xit1-r from E20 which suggests
A(D) < min (4), A411- (B)) x (A B),
Hence
tr A, B) 2 tr() tr()) X, 21( iT(A) (z
This proves the first inequality.
27

---

Under review as a conference paper at ICLR 2023
For the second the inequality, let be the unit eigenvector associated with (ZAZ"), then (zAZZ" = x² ZAZ" I. Now write
A Zxx z" Z(I xx )z" B.
Let D A Zxr" z then again by Lemma
F33 we have A 21 D. and D Zr-1
Notice that
D = (A - Zax y2
A + (Zxx' T' z² AZxx z Zzx z A.
Taking trace on both side of this equation and using the cyclic property of trace operation lead to
ur(D²) Lr (A²) + ||xl|* 2X, (ZAZ").
(F:21)
We only need to lower bound | tr( D²), for which we write the eigendecomposition D using eigenpairs (():(D), [4))
n D
n-1
Σ A(D)u,nf = Σ A(Duunt An WD)
Then we have
|| | = ir(2xx -2=) = (r(A) ir(
= (r(A) Σ -m.
2 tr(A) Σ Xy(An, -) An
tr()) tI(AA, B) (AA, A)
where the inequality follows similar argument in the previous part of the proof and uses
Ax < min (B1, = (A B).
(F.22)
from the fact that A 1 D. and D ビ B.
Now examine the right-hand side carefully: The first component tr(A) - tr(A B) is non-negative because (A) 2 (A Av B), Vi. The second component (n A, B) - X,, (D) is non-negative as
well by F22 Therefore the right-hand side is non-negative and can take square on both sides of
the inequality, namely.
| 2 (I((A) - (r
B) + (AM -A) An)))
(F:23)
We also have
tr(B²)= Σ +
Σ (A B)
ir ((A B)3) X2 Ar B) + X2()),
(F:24)
The inequality holds because for = 1, n nn11
0 A S (D) AAA,, B).
where the inequality the left is from A 2 D and the inequality the right is due to F222
28

---

Under review as a conference paper at ICLR 2023
With those two inequalities
F.23
F.24
have (For simplicity, denote Aa == An(A B),
Xn (D))
tr - (IT((A) tr(A tr ((A B}9]
2 Xa + xx 22, 2 + 2(hn - ()((t(A)- tr(AA) A B)) + X3 X2
21 -2 2(An - ()((T(()) - tr(AArrAAA) B))
2(An (A)tr(A) tr(A Ar B) Am) 20:
where the last inequality is due to the facts that An 2 A by F22 and
(r( B)
Σ - BJ) + (n)
This shows
Ex || - tr( 2 (tr(A) - trA,,, B))² - tr ((A Ar B)²)
Finally from
F22 we have
2A, (7A = tr ((A))) + || - tr(ß²)
2 tr ((A)²) tr ((A A, B)²) (tr(A) - tr(AA, Ar B))²
To proof Lemma F we need one final lemma
Lemma E.8 Given two real symmetric matrices A, B of order n, for any S n, if Er B, then
A E (A Ar B) and (A A, B) Z1-1 B.
Proof. Denote D == AA B, we show A 21 D and D 2 B. The following statements holds for any index E [n].
First of all, we have
(D)
s (A4),
(F.25)
and
A-1(AA) S (A)) >,()),
(F:26)
where (A) S (B+ is from A 2 B. F:25 F:26 together show A ż D.
Next, notice that
AB) < A (B) ADD)),
(F.27)
where ABB S ((A) is from A > B, and
Aitr- (D) min (A), AB)
(F.28)
F27
F288
together show D - B.
Then we are ready to prove Lemma F.7
Proof of Lemma F.7 Denote = A B. We have shown in Lemma F.8 that A 2 D and
D D B.
With the two interlacing relations, we know there exist x E Raxl X E Rax(r-1) and some orthogonal matrices V1, V22 E O(n) such that
A - xr T = ViDVT, D D-XX" = =VBVV
(F.29)
then let V = V/V22 we have
A I.
VIxX' VV -BVV.
(F.30)
29

---

Under review as a conference paper at ICLR 2023
Notice that
x² xx" + VXXX'V =/x Vix
X2
then with nz Vix E Raxi, we can write
A - z = VV = VVB
remains to show (zZ and 2A, have the exact expressions as stated.
Notice that A xx=" V1 DV"" then have
| tr(xx²) tr(A V2DV7) = -r((A) tr(D).
(F31))
Moreover, taking trace on both sides of (A xx= (VDDV)) yields
tr ((A)2) 2x Ax + |||||| tr(D²),
from which we have
2x Ar tr(A) tr(D²) + ||||| + = tr(A) -t((ttr(())))))))) + (tr(A) tr())²
(F.32)
Finally, notice that the first diagonal entry of
|x|| x
zz = x
(x:
= Vi
VT
X x
is ||=]| we have, by Horn & Johnson 2012
Corollary 4.3.34),
,xZ2²) < ||>||² tr(A) tr(D) = tr(A) tt(A Ar B).
Since we have already shown in Lemma F6 that
Xx 2 tr(A) tr(A A, B),
we must have the exact equality {,(ZZ=) = tr(A) tr(A Ar B).
Similarly, the first diagonal entry of
T XT VT
AZ If AX
ZAZT
A |z
Vix]
XT
A
x² Ax. then we have, by (Horn & Johnson
2012
Corollary 4.3.34),
2X, S 2x Ar tr (A²) tr ((A,, B)²) (tr(A) tr(AA, A, B))²
Again, Lemma F.6 shows the inequality in the opposite direction, hence one must take the equality
24, (ZAZ") TT Ax tr (A²) tr ((A B) + (tr(A) tr(A Ar B))²
30

---

Under review as a conference paper at ICLR 2023
G SIMPLIFICATION OF THE BOUND IN THEOREM 22 UNDER UNIMODALITY ASSUMPTION
Consider weights (W1, 22, Wa} with unimodality index 1", there are three cases:
===1 1: D21 č 0, D23 00
Definiteness of imbalance matrix put rank constraints the weight matrices:
Since W 2 W D2s 3 O, rank(W, S m implies rank D2s) S m. (D23 can only have negative, if non-zero, eigenvalues and any negative eigenvalue is contributed from WgW"")
ran)( & m and D23 3 together implies rank(W? W2) < m (W. W2 having positive invariant subspace with dimension larger than m will give positive eigenvalue D2s), which is equivalent to rank(W,"W)) W2) Σ m.
rank(W22 W2) m forces rank(Dzi m. (D22 can only have positive, if non non-zero, eigenvalues and any positive eigenvalue is contributed from W W2.)
In summary, we have rank D23) S and rank (D21) m, which implies,
- 0, 0,
1 i h2 m +1
2 0, isicm MxD22)
(D2s)
h2 m 1 Sisha h2
= 0, m +siss
We also have
Da diag( (M)(2))), diag >o (D22))
Dns = diag (mx (A(()))))
Then
(x(De1);
1 1sis m 1
Da, An D21 = Dna Drn Am D23 =
0,
m S 1 h2
(nstl-m(Dp2)
i i= h2
hence A21 Agl = 0. and
23
Am (D21) A m (D23)
A 23
(2) (D21) X 1-m (D23)
A 23
+ A (2) 2Am D2)
- Ang+1-mi (D2a)..
23
1* 1==3; 3: D23 2 D21 30 0
Similar to previous cases, (by considering unimodal weights (WT, WT, WF))
23 = A 23 0, A3 + A = 2A, (D2s) (Am (D2s) th (21))
1" 2: D23 3 0, D21 0
D23, D21 being negative semi-definite implies rank(D2)) S n, rank(D23) s m.
In this cases,
Dry =0, Dn2 =0,
and
[0. (D2))
1 hr Drn Am D23
f0, Ahatt-m (D23),
1 15i h2
Dr, D21
{
i= h1
i h2
then
A21 = ->1yt1-n(D21)
Az3 = A 1oo+l-m((D)) (D2a)),,
(2) -22 -1p (D21)
A (2)
1 (D23) = 0.
Therefore
2421 23 2 =2 -Dbsti-n 1-1-+1-1mmmm (D2s)) A3 + A A + +1!21
31

---

Under review as a conference paper at ICLR 2023
H PROOFS FOR DEEP MODELS
We prove Theorem in two parts: First, we prove the lower bound under the unimodality assumption
in Section
H.1
Then show the bound for the weights with homogeneous imbalance in Section
H.1 LOWER BOUND ON Amin(T(ww) UNDER UNIMODALITY
We need the following two Lemmas (proofs in Section H.3
Lemma 4. Given A E Raxh, B E RRxx,, and D = A BB" E Rlxh, Ifrank(A) S and
D = then
1. rank(B) S r, and rank (D) r.
2. There exists Q E IRAxr with Q" Q = 1r such that
AQQ B AB, AQQ" AT AAT, BBQQBBB B.
and (Q DQ) = AxD)), i= ... r.
Lemma S. For W1 Raxhi W2 E Rhixha.... Wi-1 Bp and W. Rhv- xhe such
that
Dj W/W: Wi+W 20,
1= 1=1,...,
we have
4-14-1 (ni)
W.W., ... WT-WWE- W
Then we can prove the following: Theorem H.1. For weighty (Wi) with unimodality index 1*, have
Amin (T(mitia)
day
(H.33)
Proof. Recall that Timik E
T
L+1
T
L+1
Σ
II
w.
W
E
We
II W.
Wo
In.
WL11
Im
I=1
1=1
ki=t+1
For simplicity, define p.s.d. operators
1-1
1-1
T
L+1
T
L+1
TiE =
II
W
I
W
E
II
W
II W,
11=1,...,1
ii=41
Then T(wi).s El=17. Tt.
When 1" L, we have, by Lemma
1-14-
L-1
Amin (Twwit))) Z Amin (TL) = An An WT- WW--WT wF)
Σ An) =
II
de
When 1" 1, we have, again by Lemma 5
L-1L-1
Amin (T(wi)/,)) Amia (Ti) Am AWZ WTW ..,,.. 2
Am (-DL-1)
Am (-Di)
T- d
Am (-Di)
II
1=
-=1
32

---

Under review as a conference paper at ICLR 2023
(To see Lemma applies to the case 1" 1, consider the following
WE W1, ... W , - Wi,".. WT - WE,
and this naturally leads to - Di-t + Dr. The expressions on the right-hand side of the arrow are those appearing in Lemma 5
Now for unimodality index 1 < 1a < I, we have
Amin
(Tw)) 2 Amia (Ti-) A, (W1 Wi--WW--1 ... WT Am (W7. W Wr++1 WL).
Now apply Lemma 5 to both { W1--1, 3i-3 and (WE, W Wi-), we have
1-
An Wi- W7 Wi) 2
An (Di) = II day
(H.34)
and
T-1l T-1
Am Am.. (WE. ... ...W44 Wr+11' (.,)) 2
Am (-DL-1)
1=1
(-Di)
L-1
L-1
II
(-D = II
de
(H.35)
1=1
Combining (H.34) and H.35 have
An Wi- WW--W Wi Wi)dm (WT
Wr) II do
(H.36)
which leads to Amin (Twalt 2
I day- The proof is complete as we have shown Amin (T(m)),)) 2 I day for any unimodality index 1' E [Z].
H.2 LOWER BOUND ON Amin Amin(T(ww) UNDER HOMOGENEOUS IMBALANCE
We need the following Lemma (proof in Section
H.3
Lemma H.2.
Given any set of scalars {wi}t such that d(s == w 2--w w7. 2 20,1= 1,... 1,
we have
L-1
2
ΣI 1=1
2
II d())
+ +(102-2111)
(H.37)
w
1=1
1=1
where II w/.
Then we can prove the following:
Theorem H.3. For weights (Wi) with homogeneous imbalance, we have
4-1 II 1=1
Amiu (T
de
+Loo
W
Wt
(H.38)
Proof. When all imbalance matrices matrices, this is the balanced case (Arora et al. and Amin (Twaatt)) Lo 2-2/L (W). Here we only prove the case when some di + 0.
2018b)
Notice that given the homogeneous imbalance constraint
wi Wi W4 Wfi d,T
33

---

Under review as a conference paper at ICLR 2023
W/', and W4+1 W must be co-diagonalizable: If we have Q² I such that Q is diagonal, then Q" Wi+1 W Q must be diagonal well since Q² W/ WiQ Q" W W Q = dil
WiQ
Moreover, if the diagonal entries of Q WiQ are in decreasing order, then those of Q" Wi+1W44 because the latter is the shifted version of the former by d:.
This suggests that all Wi, I = 1, have the same rank and one has the following decomposition of the weights:
Wi Qi-1E
(H.39)
Here, M1, = 1,... L are diagonal matrix of size k = min m) whose entries are in decreasing order. And Qi E (R/u mmiffn,m) with Qf Q: I. (ho n, hr = m). From such decomposition, we have
W : ... W, = Q0 E2 Qu. Qo
II Σ
Q
(H.40)
thus
Mmin ( (W)
Amin (Et).
(H.41)
Regarding the imbalance, we have
of (WFW,, W441 )i = d,l # - Di+ = di,
(H.42)
which suggests that Now consider the set of scalars
min (2i) Xumn (21+1) = di,! / = -
(H.43)
Ewi 1
Wi Amin (Ei), 1, 1,...
W/ Amiu E(+1), 1,,...
Wz Amiu (E,.).
Then {wilizs satisfy the assumption in Lemma H.2
w w de 2 0,
1,
(H.44)
where d(y is precisely the cumulative imbalance. Then Lemma
H.2 gives (H.41 is also used here)
L-1
2
ΣII
Z
πI de
+
(H.45)
1=l
i=1
Recall that
T E
L+1
T
I.+1
T(m) E
Σ
II w
II ==0
W
W;
II W,
.. In. W Im..
I=1
L
M=l+1
1=/+1
For simplicity, define p.s.d. operators
1-1
L+1
L+1
TE = I[W; W.
I W;
E
II
W
II
W
.1=1....,
Then T(w),, Et= Tt. Notice that the summand
Il wi exactly corresponds to one of Amin (Ti). For example,
Amin(Tr Amiin AminnWF. (W.....W W W2
...W!
WW) Amin
oF
Σ Q
II w
(H.46)
1=2
34

---

Under review as a conference paper at ICLR 2023
More precisely, we have
Amin (T))
II
W <<
iF
Amin (Ti)
II 1
2 1>1 1"
Amin (Ti)
II
w
1=r.
1.
Therefore, we finally have
L Σ
L-1
Amin (TWa)/
Amin (7))
II it!l
II de
+ (Lom (w))² (H.47)
H.3 PROOFS FOR AUXILIARY LEMMAS
Proofs for Lemma
The proof is rather simple when h1 h2 h Notice that
An (WW W2 ... WT.- W WT'
2 Am W.W--WE-.. X, (WWW. Wr-2WW--...WWW
Xn (W -W WWVWW---W2--W-3--..... w??
L-1
II (W,W?)
Then it remains to show that Am. \W:WW??) 2 LL-1 Au (Di) for = =,, 1,,., ,
L--1 1.
Suppose An (WWWW El- ADD for some & [L 11, then we have
An W WWTT-Wx--
WW + DR-1)
M (W, + (D=-1)
(Di) + (Dx-1)
Σ (n.) 1=k-1
1=k
Therefore, we only need to show Xa (W2-IWTT 2 (D then the rest follows by the induction above. Indeed
1.-1) A,, (W W. = X, (W. + D (D
which finishes the proof for the case of n h1 = h22
h
When the above assumptions does not hold, Lemma 4 allows us related the of weights (Wi)/- to the one { {Wi)_ that satisfy the equal dimension assumption. More specifically, apply Lemma using each imbalance constraint
Dj wfw. W W 2 0,
1= 1, Use these Q1 = -,.... L to
to obtain Qi E (R that has the property in Lemma define
Wi = W/,,/Q ,
D. WTW, W W1+1 Wi,, 1.... 1,
35

---

Under review as a conference paper at ICLR 2023
where Qo =1QQ = Now {Wi) satisfies the assumption that h1
h then
L-16-1
WW .. W W
IE (D.)
(H.48)
Using the properties of Q: E RRlixn 1,... 1. we have
W- ...
An. 1.1.a...-W-WW.. W ...WW
and
L-1L-1
1-14
L-1L-1
II (D. IE
(n D(QI)
Σ (nD))
Therefore, H.48
is exactly
WW ... WE-I W..WW...WWWWWW..
W2
(Di)
(H.49)
Proofs for Lemma and Q² ====r. T,-
Since rank(A) E r, A has a compact SVD A PE such that Q E Rhxr
This is exactly Q we are looking for. Let Q1QI = In - -QQ be the projection onto the subspace orthogonal to the columns of Q. Then
D A BBT = QI DQL and Q[ Q1 are two p.s.d. matrices whose sum is zero, which implies
AQ QI Q BB Q 0.
DQ 0 DQ1 0,
QI = B²Q 0.
Q DQ = 0 shows that the nullspace of D has at least dimension i.e., (ank(D) S
Moreover
AQQ" = A(T. -1Q0) AB AQQ" A = A(T, - AAT
BJ QQQT= B (IA-" B
The last equality B Bd TT QQ shows that rank(B) Sr.
Lastly, we have, for i = 1,...,, ,,
AT( DQ) (QQ D) Al4h - -Q (D).
Before proving Lemma H.2 we state Lemma that will be used in the proof.
Lemma H.4. Given positive T4, 1,. n, we have
1/n
24 2
II
Proof. This is from the fact that arithmetic mean of [x:)%_ is greater than the geometric mean of {x,)r
We ready prove Lemma H.2
36

---

Under review as a conference paper at ICLR 2023
Proof of Lemma H.2
We denote
1 Twi)i = Σ
(H.50)
1=1 E7
Notice that ui? = wl + E/= (w] - w2+1) = wo + d(o). Let d()) = 0, we write the expression for
Il
: = II[(u (w2+d()) = r(W (do))ii
1=1 1z6l
1=1 1s
Therefore, when fixing (d(t) M can be viewed function of wf.
{d
When 0: one of wy must be zero, and because w has the least value among all the weights, we
know wf. = 0. Then
L-1
[m)) =(; |=))
do)
Le. we actually have equality when w = O.
When * 0: then 2 + 0 and write
2²
II oi = wi II 1=1
(w) + dry) = p(w (o
1m1
which shows w² is function of w7, when (d 1-1 are fixed. Here to denote w² for simplicity. Moreover, function pt Rzo - R20 has differentiable inverse p long because
dp dw?,
EI
L w + do)
Σ
(Lemma 3
L (p
1/1 >
and inverse function theorem (Rudin 1953) shows the existence of differentiable inverse. Whenever, p- exists, it derivative is
-1
dw? dp
L ΣΣ
(w). + d()
-
=
Now pick any 0 < Po S 2 we have, by Fundamental Theorem of Calculus,
iimi) -2(p (w²) ):);:(d)))) ((T))
(p ( (wi2) d (w7,; H
= ~ (d (())) +
(p-1))) dwf
For the first part, we have
-2 (d)
2 (po) -do))
2 (p (po) d(0)
L-1
ΣI
>
Il II
dis
1= G2
37

---

Under review as a conference paper at ICLR 2023
and for the second part, have
(w²))
d
r
dwz
(po)
(w²))
2T ddw
L
p (po)
(w²)
2T
II
(w + doj)dwu
(po)
i= iigtt j
(w)
L
2T
p
dw
(po)
wf
eight
M6-1)
(w²?)
(Lemma H.4
2T L 1)
P
dwp
(po)
1=1 ا
W wi
(w²))
T/(-11
2TI(L 11
duy
p2l-2
(po)
(w)
2T -1)p' -2//-2/ duw
(po)
2L(L 22 = L2 L2pp 2/12-2///" wo
= =(Lm2-2/1)² -'' 2-2/1.
(dwf, = -dp)
Overall, for any pn S 2 we have
L-1
II
[Ide deo)
+ (Lw
12200-11 2-2/L
i=1
Let Pa -+ 0, we have 72 [T d(s)
(Iw2 i.e.
I dio +(102-2/2)3
22
38


Reviews:
[{"review_id": "_709ZsgyIR", "reviewer": "Reviewer_h9zp", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper extends the interesting results of [1] on the convergence\nof gradient flow for two-layer linear networks to the case of deep\nnetworks, and to a wider variety of loss functions, obtaining\nbounds on the rate of convergence in terms of notions of the\n``imbalance'' of the initialization of the network.  They also extend\nresults from [2] on deep networks to a wider variety of\ninitializations, again exposing a wider variety of effects.\nTheir bounds for three-layer networks are quite general, and they\nprovide bounds for deeper networks whose initializations satisfy\na condition like one used in [2], but more general.\n\n[1] Hancheng Min, Salma Tarmoun, René Vidal, and Enrique\nMallada. Convergence and implicit bias of gradient flow on\noverparametrized linear networks. arXiv preprint arXiv:2105.06351,\n2022.\n\n[2] Yun, Chulhee, Shankar Krishnan, and Hossein Mobahi. \"A unifying\nview on implicit bias in training linear neural networks.\"\nInternational Conference on Learning Representations. 2020.", "summary_of_the_review": "The strength of the main results was unclear to me, and I felt that some claims made in the paper were not justified by the results.", "strength_and_weaknesses": "The way that the PL condition is used to formulate the results is\nunfamiliar to me, and seems nice.\n\nWhere the authors write ``cannot explain well the training efficiency\nin practice'', I don't find this completely convincing, because people\ndon't use extremely small initializations in practice.  Of course it\nis interesting to determine how the convergence time depends on the\nsize of the initialization.\n\nIt is not clear to me how good the lower bound in Theorem 2 is.  It is\nconsistent with my current understanding, such as it is, that the\nbound of Theorem 2 is often zero, which, when true, makes Corollary 1\nvacuous.  It would be helpful to provide some examples of where\nTheorem 2 provides a good bound.\n\nI don't think that some of the claims made in the text after Theorem 2\nare justified by the result.  For example, since Theorem 2 only has a\nlower bound, I don't see that the claim that they ``fully characterize\nthe effect of imbalance on the convergence of three-layer networks''\nis justified.  Also, to show that ``such a partial ordering is not\nnecessary'', you would need to provide an example of where the RHS of\n(17) was positive without such a partial ordering.  Similarly, I don't\nsee that claims made in the intro about characterization are\njustified.\n\nThe condition defined in Definition 3 seems like a \nstrong assumption to me.  For example, it seems like it\nis very unlikely to be satisfied, or even nearly satisfied,\nby a random initialization.  I think that more justification is\nneeded that this is an interesting condition to study.\nAlso, while it is more general than the condition used\nin [2], it seems to make available a similar set of tools.\nIt also reads to me as being crafted to be able to apply\nWeyl's inequality, rather than to capture a useful product\nof natural, and random, initializations.  Roughly speaking,\nit looks to me that unimodality is ``looking under the\nlamppost''.\n\nSome more comparison with prior work would be helpful.  For example, I\nbelieve that the results of this paper are incomparable in strength\nwith the results in [3]-[5], which touch on an overlapping set of\nissues.  I think that the claim that `` the convergence analysis for\nimbalanced networks not in the kernel regime has only been studied for\nspecific initializations'' is not correct, though I do feel that,\ndespite this, the authors' comparison with [2] seems fair overall.\n\nHere are a couple of smaller points.\n\nThe unimodality index is not defined until Definition 3, but is\nused earlier in the proof of Theorem 2 -- the authors should move\nit earlier.\n\nBefore (13), the authors indicate that they are going to define\n$D_1$ and $D_2$, but then they define $D_{21}$ and $D_{23}$.\n\nI will carefully read and consider the authors' reply.\n\n[1] Hancheng Min, Salma Tarmoun, René Vidal, and Enrique\nMallada. Convergence and implicit bias of gradient flow on\noverparametrized linear networks. arXiv preprint arXiv:2105.06351,\n2022.\n\n[2] Yun, Chulhee, Shankar Krishnan, and Hossein Mobahi. \"A unifying\nview on implicit bias in training linear neural networks.\"\nInternational Conference on Learning Representations. 2020.\n\n[3] Jin, Chi, et al. \"How to escape saddle points efficiently.\"\nInternational Conference on Machine Learning. PMLR, 2017.\n\n[4] Hu, Wei, Lechao Xiao, and Jeffrey Pennington. \"Provable Benefit of\nOrthogonal Initialization in Optimizing Deep Linear Networks.\"\nInternational Conference on Learning Representations. 2019.\n\n[5] Zou, Difan, Philip M. Long, and Quanquan Gu. \"On the Global\nConvergence of Training Deep Linear ResNets.\" International Conference\non Learning Representations. 2019.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "LDTYgSKX-cT", "reviewer": "Reviewer_5qgv", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proves the exponential convergence of gradient flow on multi-layer linear models in which the loss function f satisfies the gradient dominance property. It also provides a lower bound on the convergence rate that depends on the imbalance matrices and the least singular value of the weight product. ", "summary_of_the_review": "The paper provides the exponential convergence result for the gradient flow of multi-layer linear networks under a gradient dominance assumption. It applies to a wide range of imbalanced initializations. It is technically correct and the obtained result is new. The novelty of this paper is fair and it builds upon several existing works on overparametrized linear networks. The impact of this work is not clear as it only applies to linear networks.", "strength_and_weaknesses": "Strength:\n1. The paper is well written and clearly motivated.\n2. The obtained convergence result is quite general and can be applied to a wide range of imbalanced initializations.\n\nWeakness:\n1. Limited to linear networks", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "K5yjbcBlp7I", "reviewer": "Reviewer_QQB2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper aims to analyze the convergence of gradient flow of multi-layer linear models. The paper deposit that in general, the convergence rate depends on two trajectory-specific quantities: the imbalance matrices (which measure the difference between the weights of adjacent layers) and on the least singular values of the weight product. The framework of the paper is designed to cover several existing initialization schemes and applies to both regression and classification.", "summary_of_the_review": "The paper addresses a meaningful question. The work obtains several new technical results, and provides some useful insights about the effect of weight imbalance on convergence for deep linear models.\n\nUpdate: The reviewers' discussions come to a general assessments that while the contributions of the manuscripts are significant and somewhat new, most of the technical improvements are marginal with some concerns about the realisticness of some of the assumptions. My final score was adjusted from 8 to 6 to reflect this summary of the discussions. \n", "strength_and_weaknesses": "### Strengths\n\n- The paper is well-written with a sufficient literature review. The main ideas and techniques of the work were developed based on well-founded rationales.\n- The mathematical analyses of the work are rigorous and seem correct. The framework of the paper is general and broadly applicable (covers several existing initialization schemes; general loss functions)\n- The paper obtains several new technical results/improvements\n    - The derived bounds (Theorems 2,3) characterize the general effect of weight imbalance on convergence. Previous works on this aspect focused on two-layer models or when all imbalance matrices are positive semi-definite.\n    - The analysis applies to general loss functions and thus can be used to study classification tasks (Theorem 4). Existing works mostly focused on l2 loss for regression tasks.\n    - Three-layer model: Theorem 2 is stronger than previous work (Yun et. al.(2020)) in that it doesn’t force the partial ordering of the weights for convergence. The paper also proves that the bound in this case is optimal.\n    - Deep linear models:\n        - The bound of Theorem 3 dominates and unifies two existing bounds on deep networks (Arora et. al.(2018a), Yun et. al.(2020)) and characterizes the general effect of weight imbalance on convergence\n        - The unimodality condition seems to be novel and contains that of Yun et. al.(2020) as a special case\n    - Some technical constructions of the proof of Theorem 2 (interlacing of spectra of two matrices whose difference is positive definite and low-rank; explicit construct of the optimal solution to the lower bound) might be of general interest.\n\n### Weaknesses\n\n- None noted", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Reject