Sharp Convergence Analysis of Gradient Descent for Deep Linear Neural Networks
Authors: Hongru Zhao
Jinchao Xu
Venue: Submitted to ICLR 2023 (2023)
Keywords: deep linear neural networks
non-convex optimization
gradient descent
initialization

Abstract: This paper provides sharp rates of convergence of the gradient descent (GD) method for deep linear neural networks with different random initialization. This study touches upon one major open theoretical problem in machine learning: why deep neural networks trained with GD methods are efficient in many practical applications. While the solution of this problem is still beyond reach for general nonlinear deep neural networks, there have been extensive efforts in the literature in studying relevant questions for deep linear neural networks and there are many interesting results in this research direction. For example, recent results on the loss landscape show that even though the loss function of deep linear neural networks is non-convex, every local minimizer is also a global minimizer. When the GD method is applied to train the deep linear networks, it has been shown in the literature that the convergence behavior of the GD method depends on the initialization. In this paper, we obtain the sharp rate of convergence of GD for deep linear networks, and we show that this rate does not depend on the types of random initialization. Furthermore, we show that the depth of the network does not affect the optimal rate of convergence, provided that the width of each hidden layer is appropriately large. 

Under review as a conference paper at ICLR 2023
SHARP CONVERGENCE ANALYSIS OF GRADIENT DESCENT FOR OVERPARAMETERIZED DEEP LINEAR NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
This paper presents sharp rates of convergence of the gradient descent (GD) method for overparameterized deep linear neural networks with different random initializations. This study touches upon one major open theoretical problem machine learningwhhy deep neural networks trained with GD methods are ef- ficient in many practical applications? While the solution of this problem is still beyond the reach of general nonlinear deep neural networks, extensive efforts have been invested in studying relevant questions for deep linear neural networks, and many interesting results have been reported date. For example, recent results on loss landscape show that even though the loss function of deep linear neural networks is non-convex, every local minimizer is also global minimizer. When the GD method is applied to train deep linear networks. it's convergence behavior depends on the initialization. this study, we obtained sharp rate of convergence of GI for deep linear networks and demonstrated that this rate does not depend on the types of random initialization. Furthermore, here, we show that the depth of the network does not affect the optimal rate of convergence, if the width of each hidden layer is appropriately large. Finally, we explain why the GD for an overparameterized deep linear network automatically avoids bad saddles.
INTRODUCTION
Deep linear neural networks, as a class of toy models, are frequently used understand loss surfaces and gradient-bassee optimization methods related to non-convex problems. Dauphin et al. (2014) and Choromanska et al. 520 explored the loss function of deep nonlinear networks based on random matrix theory (such a spherical spin-glass model). This theory essentially converts the loss surface of deep nonlinear neural networks into that of deep linear neural networks under certain assumptions, some of which are unrealistic. [Choromanska al. (2015b) suggested an open problem to establish connection between the loss function of neural networks and the Hamiltonian of spherical spin-glass models under milder assumptions. Later, Kawaguchi (2016) successfully discarded most of these assumptions by analyzing the loss surface of the deep linear neural networks.
The landscape for deep linear neural network (Kawaguchi) 2016 Kawaguchi & Lu. 2017 Laurent & Brecht 2018) focuses on several properties of the critical points: (i) every local minimum is a global minimum; (ii) every critical point that not a local minimum is saddle point; and (ii) there exists saddle such that all eigenvalues of its Hessian are zeros if the network is deeper than three layers. Thus, for deep linear neural networks, convergence global minimum impeded by the existence of poor saddles.
Lee al. (016) showed that the gradient method almost surely never converges to a strict saddle point, although the time cost can depend exponentially on the dimension (Du et al.) (017). Gra- dient descent (GD) with perturbations (Ge et al., 2015 Jin et al., 2017) can find a local minimizer in polynomial time. Thus, the trajectory approach combined with random initialization algorithm circumvents the obstacle of existence of poor saddles. According to studies on continuous time dynamics of gradient flow (Du et al. 2018 Arora al. 2018b), the balance property of deep linear network is preserved if the initialization is balanced. Arora et al. (2018a) b). Du & Hu (2019), and Hu et al. (000)) successfully proved that GD with its corresponding initialization schemes
random

---

Under review as a conference paper at ICLR 2023
verges to global minimizer of deep linear neural networks with high probability. Furthermore, the rate of convergence is linear, and behaves like GD for a convex problem.
Hu et al. (2000) established that the convergence for Gaussian initialization can be very slow for deep linear neural networks with large depths, unless the width is almost linear. They also showed that orthogonal initialization in deep linear neural networks accelerate the convergence. Thus, the convergence behavior of the GD method, for training deep linear neural networks, crucially networks depends on the initialization.
Recent studies have demonstrated the connection between deep learning and kernel meth- ods (Daniely] [017]] Arora al., 2019a b. Chizat al., 2019 Lee al., 2019, Du al., 2019
Cao & Gul [2019; Woodworth et al. 2020 especially the neural tangent kernel (NTK), introduced by Jacot et al. (2018). For most common neural networks, the NTK becomes constant (Jacot al.)
2018 Liu et al. (0200 and remains so throughout the training in the limit of large layer width. Throughout the training, the neural networks are well described by their first-order Taylor expan- sion around their parameters at the initialization (Lee et al. 2019).
In this paper, we first evaluate the convergence region, i.e. the set of initialization parameters that lead to the linear convergence of GD for deep linear neural networks (see Lemma 4.. or D.Tp. Next, we demonstrate that if the minimum width among all the hidden layers is suffi ciently large, then the random initialization will fall into the convergence region with high probabil- ity (see Theorem 3.1 Theorem B.I] Theorem B.2 and Theorem B.3). Furthermore, the worst-case convergence rate of GD for deep linear neural networks is almost the same as the original convex problem with a corresponding learning rate. We also demonstrate that the GD trajectories for deep linear neural networks are arbitrarily close to those for the convex problem. The precise statement I and Lemma 4.4 (also see Lemma D.5).
is related to remark 3 Theorem 3.2 Corollary
The present study was inspired by recent reported work Du & Hu (209);; Hu et al. (2020), in which the authors carefully constructed the upper and lower bounds of the eigenvalues of the Gram matrix along the GD and established a linear convergence. In this paper, we generalize their re- sults to strongly convex loss functions with layer varying widths and obtain sharper results. We also show that our rate of convergence for GD in deep linear neural networks is sharp in the sense that it matches the worst-case convergence rate for the original convex problem. The trajectories between the GD for deep linear neural networks and the original convex problem (T) can be arbi- trary close. Furthermore, we show that if the width of each hidden layer is appropriately large, then the optimal rate does not depend on the random initialization types and network depth. Lastly, we elucidate the mechanism underlying the observed automatic avoidance of bad saddles by the GD for overparameterizeed deep linear networks.
2 PRELIMINARIES
2.1 PROBLEM SETUP
Let T and y E H"' be an input vector and target vector, respectively. Define { y/ Jm
as training dataset of size m, and let = [21, " [mm] # 0 and Y [1/1, U2. ... ..m]. Denote the weight parameters by W E g
Consider the well-studied convex optimization problem:
L(W)= = 1 m m (WI..)))
minimize W
(I)
The GD for convex problem I with learning rate of 1n. is given by:
W(++ - VL(W 0 ...
(2)
For any matrix A, let Tmar (A) and (min(A) (A) be the largest and smallest singular values of A respectively. Here, we consider two types of matrix norms and one type of semi-norm for A, |||]]| := mmzz(A) || == tr(AAT), and ||A||x == ||Axlles where Px = X(XTx)xx is the orthogonal projection matrix onto the column space of X, and (XTX) X)t f the Moore-Penrose inverse.
2

---

Under review as a conference paper at ICLR 2023
For two real matrices A, B with the same sizes, consider their Frobenius inner product well as their cemi-inner product, (A, B) = (A, B) == tr(A" (A. B)x == (APx. BPx). Here, we list some basic properties for the semi-norm and semi-inner product.
Lemma 2.1. The loss function L(W) defined in 7 satisfies the following properties: for any W.V R"
1.L(W) = L(WP)), (.) VL(WPx) (.),((W), V)F (VL(W), V)x. [VL(W)]lx 5. |.|| I1x = | if and only if X is full row rank. 4. =
The next lemma demonstrates the importance of the semi-norm I1-11x in our analysis.
Lemma 2.2. Assume that 1(:, y) is adl) strongly convex. Then, the following statements hold.
1. If X is not a full row rank matrix, then L(W) is neither strictly convex nor strongly convex with respect to II-
2. L(W) is am)))ms strongly convex with respect to |l-llx- where Amin (Xx*) is the smallest non-zero eigenvalue of XXT.
The proofs of the two aforementioned lemmas are provided in appendix A uct is not specified, then we will consider the semi-inner product.
Hereafter, if inner prod-
Assume that L is ot-ttongly convex (a > 0), and VL B B-pisschitz (with respect to the semi- norm I]-Ilx): ); that means, for any W, V E R
L(W) 2 L(V) (VL(V,, W V)x I V [VL(W)- VL(V)lx (V VLV)I S -
Without loss of generality, we assume that a and are the best constants. Then, Lemma 2.2 implies that 2 o(()Amin(Xxx)) Similarly, we can also show that B < [(])mmu(XXx)) where VI(..)) is Lipshhit and Xmaz (XXT) is the largest eigenvalue of XXT.
Define the effective condition number of the convex function L. by K= R(L) < 0o. K appears naturally in the rate of convergence of the GD. Let W,, be global minimizer of L(W), that is L(W.) = minw L(W). Notice that W. might not be unique, but Px is unique.
The well-known results for the rate of convergence of GD
state are:
7- 3
E(t)
11-1 1
1
E(0), = 1,,,,=1,2... .., as well as,
(3)
K
11. =
a a = E(t) s
B
1 (1
IW(0) - 1. 1= = 1,2," + k)²
4x
(4)
2
(1
where E(t) = (t)( L(W)).
2.2 DEEP LINEAR NETWORK SETUP
Let N - 1 be the number of hidden layers. Assume rank(X) = r. Denote the weight parameters by WR E TR xpt-x_ k 1,2... ,N, with nn Ny: no ntz, where the ni is the width of the k-th layer. Set Remin = min(n1, f2, n1 and Amaz max [n1,
1N For notational convenience, we denote nj = IIggag Tlg and denote W,.: = W- W; for each isisjs S N. Define n. and W; - 1: I (of appropriate dimension) for completeness.
max((n, R22
Considering the implicit regularization W = WN for the convex problem following non-convex optimization problem of deep linear neural networks:
We obtain the
m
minimize Wi..., W.
L(WN.))=
I(W N.I
(5)
Example 2.1. Specifically, if we set the loss to be I(W x4, 9i) | villz then L(W) J X -13 is 20mmn (XX") strongly convex, and VL. is 2dmax (Xx")
Lipscchitz
m
m
m
3

---

Under review as a conference paper at ICLR 2023
Example 2.2. Deep linear neural networks with regularization À [[N W1 can be con- verted into a new optimization problem
minimize WN
L(WN:1) A ||Waalllx
Let (WW L(W) + X I Then, (x(+) is 2A-strongly convex, and VLx()) is B + 2A- Lipschitz.
More generally, if we consider regularization with form R(W) X 9(Wxx) and g(-) is a'- strongly convex, and 3'-Lisschitz, then for the optimization problem
minimize Wh. WN
L(WNa)) + R(WN- ... Wi) =: La(WN ... Wi),
we know that (R(-) is + Ào' -tt-nlyyy convex, and LR is Ai'-Lischhit.
2.3 INITIALIZATION SCHEMES
In previous studies, the following form of deep linear networks was considered, instead of (5
minimize Wh." W.
L(axWNa)) = Σ WaN
(6)
where aN 1/ Vning. -. aN is normalization constant.
By applying GD on (6) where we update W, simultaneously for j. we obtain
+) (t) 77 aN (WN:+1(1)) VL (aN W.) (W)-1n(t)) j= - ,N. (7)
In a recent study, the authors considered GD 7 and adopted a Gaussian initialization (Du & Hu 2019) or scaled orthogonal initialization (Hu et al. 2020) for initializing W,(
In this paper, we consider the following three kinds of random initializations, which generalize their idea.
Gaussian initialization: Let (i( .... WN (0) be the weight matrices at initialization. We as-
sume that all the entries of W 1 j S N are independent Gaussian random variables with mean and unit variance.
Then, aN normalization constant in the sense that for any R", we have
= ||x1
(8)
In fact, all the initializations discussed in this paper satisfy Remark 1. Let Vi(()= = :.. Wi()), for < i < N. Then, GD with a unit variance Gaussian initialization is equivalent to
Vy(t 1) Vg(1)= (VNo+i(0)) VV.. (1)
n
with zero mean and variance 1 Gaussian initialization for V,, 1,... .N.
GD (9) for loss is equivalent to GD for loss o Hereafter, we will only consider GD for deep linear neural network (6).
We consider the so-called one peak random orthogonal projection and embedding initialization, which generalize the idea of orthogonal initialization (Hu et al. 2020)
Orthogonal initialization:
Definition 2.1. An initialization Wx:1 (0) = Wn (O) -- (0) ... (0))) is said to be one peak random orthogonal projection and embedding initialization if there exists 1 < such that nop < ni I n2 S ... < np, Np > np+1 2 Пp42 Z -.-7--1 2 ny, and Wi (O), W2(0), (D).), W (0), W (p))(0),... ...) W nN (0) independent and uniformly dis- tributed over rectangular matrices, which satisfy
N,
(0) nıln, sisp ()) = n + S N.
4

---

Under review as a conference paper at ICLR 2023
Remark 2. In this definition, V (,) < are random embeddings and
W
j S N are random orthogonal projections. Notably, A is random orthogonal projection if and only if A" is random embedding.
Arora et al. (2018a) studied the rate of convergence of GD global optimum for training deep linear neural network for a balanced initialization. Here, we will consider a special case of balanced initialization, which is described follows:
Special balanced initialization: Assume n1 = ... = N- = n. Consider the initialization (0) VnUx (Tny On, ((n VV Wi(0) VnU, [n, O2 (n= V and W;(0)
VnU,LVVV ,2 S S N where UN- UN. V,, V; = 1- S sis N 1 are orthog- onal matrices (random or deterministic), and VN has a uniform distribution over the orthogonal matrices. Notice that only VN is required be random.
A simple estimation of the loss at the initialization is given by the following lemma. Lemma 2.3. If the initialization satisfies 8 for all x, then with probability at least 1 2. we have
r.rank X)
Waa (0)) I.W.) S Bss where Bs
||
5
Note that the bound By can be improved by using a sharp concentration inequality.
MAIN THEOREMS
Assume the thinnest layer either the input layer or the output layer: that is Rymin 2 max(ng: n2 }. and the ratio between the width of any hidden layer is bounded from above, precisely we have Bmas I Co oc. The quantities C2, Cs and Cs are defined in appendix and are dependent on hyperparameters n,, Kc, ó, rank(X), ()), Co, and N.
For notational convenience, denote
{t)) = L(W())) - L(W.), and DLN = WaayWaaaaaaaa L(W.).
Our assumptions and notation are now in place. We state our main theorems in this section.
3.1 LINEAR CONVERGENCE OF DEEP LINEAR NEURAL NETWORKS
In appendix B we present sharp estimate of the linear convergence of GD for deep linear neural networks in Theorem B.T for Gaussian initialization, Theorem B.2 for orthogonal initialization, and Theorem B.3 for a special balanced initialization. In particular, with specific learning rate v BN
Theorem B. and Theorem B.2 yield the following optimum rate of convergence:
Theorem 3.1. Given any ,,5 E (0.)). there exists constant C == C(e), such that if one of the following two overparameterizattion condition holds:
1. 7mmin C C2 .N with the Gaussian initialization,
2. Nmin C Cs with the one peak random orthogonal projection and embedding initialization
and with probability at least - 8, then we have
1-=) (1-1==)
EDIN <
K.
Remark Consider GD 2 with a learning rate of n,
and initialization W(0) axy WN. (0).
The well-known result rate of convergence (3) for GD 2 of convex problem matches the
rates obtained from Theorem B.I and Theorem B.2
Remark 4. Du & Hu 2009 and Hu et al. (2020) showed that the number of iterations required to reach a precision is O log 2) for L loss. We only improved the rate of convergence and generalized their results to any strongly convex loss.
5

---

Under review as a conference paper at ICLR 2023
3.2 RESULTS OF TRAJECTORIES
Theorem 3.1 and remark 3 establish that the rate of convergence to global optimum for GD to train deep linear neural network is almost the
the trajectories for the GD to train the corresponding convex problem with high probability, if the width is sufficiently large. Moreover, the GD for the fully-connected deep linear neural network 7 and that for GD have almost the same trajectories.
Let ?/1 ,N 2 be an upper bound of the learning rate 1). We can show that the trajectories of GD 7
for deep linear neural network ( with learning rate of 1j < 7h1 are close to those of GD 2 with a learning rate of 7/+
N xy for the corresponding convex problem (1) with high probability, if the width of each hidden layer is sufficiently large. The precise statement is as follows:
Theorem 3.2. Consider the GD for deep linear neural network (7) with a learning rate of 1 < N for aN W (t), 1,,,..., and GD (2) with learning rate of ax n n.for ((t), = 0, 0,
Given 7, 8 E (0, 1), there exists a constant C == C(T, n/1h) such that one of the following three overparameterizatin conditions holds:
Tmmin C C2 N with the Gaussian initialization,
Tmmin 2 C Cs with the one peak random orthogonal projection and embedding initialization,
Temin 2 C. Co with the special balanced initialization,
then with probability least 1 6, we obtain
[aNN N. (1) (()) 11x D(T,9,)) WaN N-I W.ll
(10a)
(D)N(()) - E(t) < 8 ( ((T.2/((T.g.) g(T.qqtt) Ww. W. (10b)
(t) S 33 W (1) w.
(10c)
7 where D(T, q,t) = min { [14 2
with 0 < q < defined in 15k.
Remark 5. To the best of knowledge, this is the first paper that reveals that the trajectory of the overparameterized deep linear neural networks is close to the original convex problem with an ap- propriately rescaled learning rate.
Corollary 1. According to Theorem 3.2 if we set 1 high probability,
2n (a+ the following inequality holds with
4k
+r)
EDNN S $33
1aaN WN:1 (0) W.
(11)
(1 (1+
Notably, the rate of convergence in 477) is better than that in Theorem 3.1 because if K > 1, then we can choose a sufficiently small T such that the following inequality holds:
4x
+
(1 x1+
Theorem 3.1
B.2 indicate that the implicit regularization induced by the GD for convex problem recovers the convex problem itself in terms of optimization, at the cost of lincar convergence only with high probability for random initialization.
Theorem 3.2 Theorem B.1 and Theorem
Remark 6. Recall the constants C2 Cs. and Cg defined in appendix
B The term rank(X) is not -
optimal, since our concentration inequality depends only on the second moment. By using stronger concentration inequalities for our Lemma 2.3] similar to the proof of proposition 6.5 (Du & Hu
be improved to 1 + loo( (og((ank(()) X)) Co is proportional x², which is slightly better than the constant in Du & Hul (2019). which is propor- tional to x. C3 is also slightly better than the constant reported by Hu et al. (2020), since we do not
2019) and Lemma 4.2 Hu al. 2020), the rank(X)
|X| The improvement of the constant is mainly due to the introduction of the [
have the extra term
semi-norm ||=||x-

---

Under review as a conference paper at ICLR 2023
4 INSIGHTS FOR THEOREM 3.2
Initialization and convergence region: Arora et al. (2018a) showed that the initialization is ap- proximately balanced, and the product matrix N:1 (0) very close global minimizer, then the GD linearly converges to the global minimum for the deep linear network without any width re- quirement. However, the convergence region in (Arora et al. 20) is very small, because W (0) needs to be very close to W.. Later, Du & Hu (2019), and Hu et al. (2020) successfully proved that the GD with a Gaussian, or orthogonal initialization linearly converges to global minimizer of the overparameterized deep linear neural network with high probability. They introduced a technique to analyze the trajectories of GD with large widths for any deterministic initialization.
We introduce the following lemma, which describes the linear convergence result for deep linear network with a deterministic initialization.
Lemma 4.1. Under the setting of Lemma D.1 the GD for a deep linear network satisfies
EDIN (1) S (1 - 77)* EDLN(0), 1,,
Our convergence region (see 31 in Lemma D.I and Definition D.1 originates from the analysis of Du Hu (2019), and Hu et al. (2020) and can be view as a neighborhood of the special bal- nN-1- Both Gaussian and orthogonal initialization
anced initialization, if n2 122
approximately balanced.
For l2 loss, without loss of generality, we assume X to be full rank matrix and L(W.) 0 be- cause of the decomposition method in claim B.1 from Du & Hu (011). However, when considering general strongly convex loss, have to confront the low rank X directly in analysis. Thus, Il-llx appears naturally and aids in achieving the sharp rate of convergence in our main theorems. In addition to the technique reported in Du & Hul (2019), and Hu et al. (2020), we also used clas- sical convex optimization techniques (such as inequalities in Lemma C.1 and Lojyakk-ojjsiwwiez inequality (26)) as well as the classical concentration inequalities for beta distribution (such as the Chernoff type bound in Lemma F.3
Why GD trajectories for overparameterized deep linear neural networks with approximate balanced initialization are close to those for convex problems? The underlying mechanism can be understood as follows: Even though recent results of (Ziyin et al.) (022) can describe the exact global minimizer for deep linear network (with regularization term such (2), the evolution of each W, is still difficult to track. Instead, we consider the discrete dynamics for product matrices
(see (1 and 42
ON (N + 11 = ax WN (1) P())VL((N (t) + aay
For their own linear operator Pt, Du & Hu 2019)) showed that Amaz (ma)(Pp) - 0 ( Amar XX X)
X). X) To the best of our knowledge, the present paper is the first and Amin (Pt) 2 (( 2(xN)) Aman X
to proved that for our operator P+t) = aN
N I (also see (44)), where / is the identity operator. E(()
is negligible, which leads to the following result on discrete dynamics (see Lemma D.3
Lemma 4.2. Under the setting of Lemma D.3 we have
N aNWN (1 + 1) aaN N. (VINaawNa(()) + R(1), AN
with |R(OIxx S 1Iax WI
Without the R(t) term, the discrete dynamics is exactly the GD for a convex function. To control the distance between the two trajectories, we introduce the following lemma (also see Lemma D.4
Lemma 4.3. Assume E [0, 1). and consider a discrete dynamical system V(t) such that,
V(L+1) = V(1) n, VL((()) + R((), where [|((()Ix S <T||V(( W.llx-
If < 2/3, then we huve [V(()= W. < (q + 7 (1) Wl1 where is defined in 15
With the help of this lemma, we further obtain the following trajectories comparison lemma (also Lemma D.5). which leads to the main conclusions in Theorem 3.2

---

Under review as a conference paper at ICLR 2023
Lemma 4.4. Under the setting of Lemma
D.3 we have
1 (t) - -W() ((T, IaN - w [EDLN()) E(6) 3 (² V(T.D(TT..))) - p(T, Iaa IaawWw.(0)) w. (12b)
(12a)
(DIN(1) S 331 + [ N:1 (0) W
(12c)
where D(T,q,t) min { [ 2 2 with 0 < q < defined in 15k
Why do bad saddles not affect GD for overparameterized deep linear neural networks? A critical point x² of f is a bad saddle if Amin f(x)) = 0. Kawaguchi (2016) showed that deep linear networks have bad saddles, and thus, in general, vanishing Hessian can hinder the optimization. Theorem 2.3 in Kawaguchi(2016) explains that for all bad saddles satisfy that W WN-12 a non-full rank matrix. Thus, show that the trajectories of GD are away from bad saddle points, it is sufficient to demonstrate that inf, min (W (WN-1-((t) > 0. According to previous studies, there are two main ways to avoid bad saddles for GD train deep linear networks.
On the one hand, following Arora et al. (2018)), it can be showed that if the approximate balanced initialization satisfies [WN:100)
W.llF I Tmin (W.) - c, for some < c J Omnn(..). then mmi (Wen(WNr (..((t)) 2 c through the training as well as (t)l S (4 [W]l 1//N, and [W s
(4 (4]]Wlll))//M I/N, then min m (W)-12(f)) >
dmiin (W. ((). (4I[W-))77
(x]]
On the other hand, if assume that our rescaled and overparameterrize weight initialization falls into convergence region (1.. then we can show that (see BB() in the proof of Lemma D.I
main (W (t:)(t)) amin CoiinWNNua (WN-11(t)]
T min N (12 2 max
Tmax (t) Tmax SeaarrWi1 (W1(t))
Thus, Jmin (nx-1:2)773
Wy-12 01 max ny (V-1) 2 e c1 > 0.
In conclusion, we first made a conjecture that according to Arora et al. (2018)). for non- overparameterized deep linear network, there are no bad saddles satisfying W ( W. < mmin(W.) Thus, W (0) - WI < min (W.) is indeed a convergence region. However, this region in general is very small, and can even be empty if minnW, = 0. For an overparameterizee deep linear network, the GD initialized in the convergence region will force the trajectories away from all the bad saddles.
Why does the width have to be large? We will discuss overparameterizztion phenomena in deep linear networks. For simplicity,
consider special balanced initialization. First, we know that (t) W: = O v (see C(t) through the proof of Lemma D.1), provided r) = h nx and 7
AN
O N
where (0,
An overparameterized deep linear network around the special balanced initialization is full of global minimizers, i.e., the trajectory limit (Wi, W..... W is in the ( neighborhood of the special balanced initialization (O), W2 (O)).. Notably,
N-1
N-1
min (W - (:2) = II
min (W)()) maa (WN-12(0) (0)
II 2=2
man (W5 nN(N 22
j=2
as well as for any (W1, W2 ... WN) in the x neighborhood of any given initialization
(0). (O). (N)))), we have (detailed argument can be found in the proof of B(t) in
Lemma D.I.
N-2
N
O 1
(n & IN n2N-3 )11)
[NN-12 (0) &
Thus in terms of landscape, we have
O mmin (N-1:2)
T Mmin Smin(WN-ww (WN-1-200) (0) WNN-122 1:2 WN WN-1:200)1
Mmin (WN- (:N-1:200) >
> 1- 0 Vn
(13)
mmin (:-):
8

---

Under review as a conference paper at ICLR 2023
which implies that no bad saddle is present in the O neighborhood of the special balanced initialization, if the width n is sufficiently large.
In terms of training, we have (see the proof of Lemma D.I
[w:(tt) -
(100)--;(00)1 (F - N) [W:(0)| n
as well as [[ - (0000--.0011 (olll O( (t) Thus for an overparameterized deep linear network, the GD [|,
with an approximate balanced initialization only trains W, and WN, and the other weight matri- remain almost constant. Here, we provide empirical evidence in appendix G to support the aforementioned argument.
On the other hand, the sharp rate of convergence depends on the trajectory limit, and when the minimum width is sufficiently large, the trajectory limit and the initialization are not far away from each other. For deep linear network with small widths, the result (Ziyin et al. (022) might shed light on convergence analysis, because the exact global minimizer can be described for a deep linear network with L2 regularization.
Numerical Experiments: In appendix H we will discuss some empirical evidence to support the main results shown Section 3 Further, Figure 2 in appendix H show plots of the logarithm of loss as function of number of iterations. When is small, the trajectories of loss for deep linear neural networks do not decrease in some iterations. However, when n is large, the loss trajectories are close to those for the corresponding convex problem.
OVERVIEW OF THE PROOFS OF MAIN THEOREMS AND LEMMAS
In this section, we provide an overview of the proofs for all the theorems obtained in the main results. Since Theorem 3.1 in the main results is a special cases of general theorems with non- optimal learning rates (see Theorem B.T and Theorem B.2), we only need to focus on the proofs of the general theorems (see Theorem B.1 Theorem B.2 Theorem B.3 and Theorem 3.2
We begin with the convergence region of deep linear neural networks, which is basically the set of initializations that lead to the convergence of the GD for deep linear neural networks. The pre- cise definition can be found in appendix D Lemma 4. and Lemma 4.4 (also see Lemma D.1 and Lemma D.5) prove that this convergence region satisfies the following properties: if the initialization falls into the convergence region, then
ii the GD is guaranteed to converge to global minimizer of the deep linear neural networks,
(ii) the worst-case GD rate of convergence for the deep linear neural networks, which is non-convex problem, is almost the same as the corresponding convex problem with a cor- responding learning rate, and,
(iii) the trajectories the GD for the deep linear neural networks are arbitrarily close those for the corresponding convex problem.
More precisely, Lemma (also see Lemma D.I establishes the convergence region for de- terministic initialization, and it demonstrates the first two properties, (i) and (ii). Additionally, in appendix
[ and appendix F we also prove that the spectral properties of the products of random matrices partially reveal that the overparamettrizattoo realized by adding the width of each hidden layer guarantees that the random initialization falls into the convergence region with high probabil- ity. These results provide foundation to establish the main lincar convergence theorem for random initialization (see Theorem B.I B.2 and B.3).
By contrast, Lemma (also see Lemma D.3) shows that if the initialization falls into the con- vergence region, then the update rule for the product weight matrices the GD for deep linear neural networks is more or less given by (2). This result can be used establish both Lemma 4.4 (also see Lemma D.5), and Theorem 3.2], which is precisely property (iii) the convergence region for deterministic and non-deterministic initializations, respectively.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Sanjeev Arora, Nadav Cohen, Noah Golowich, and Wei Hu. A convergence analysis of gradient descent for deep linear neural networks. CoRR, abs/1810.0228/ 2018a.
Sanjeev Arora, Nadav Cohen, and Elad Hazan. On the optimization of deep networks: Implicit acceleration by overparameterization. In International Conference on Machine Learning, pp- 244-253. PMLR, 2018b.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of op- timization and generalization for overparameterized two-layer neural networks. In International Conference on Machine Learning, pp. 322-332. PMLR, 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, 32, 2019b.
Yuan Cao and Quanquan Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. Advances in neural information processing systems, 32, 2019.
Djalil Chafa,, Djalil Chafä, Olivier Guédon, Guillaume Lecue, and Alain Pajor. Singular values of random matrices. Lecture Notes, 2009.
Lénaic Chizat, Edouard Oyallon, and Francis R. Bach. On lazy training in differentiable program- ming. In NeurlPS, 2019.
Anna Choromanska, Mikael Henaff, Michael Mathieu, Gérard Ben Arous, and Yann LeCun. The loss surfaces of multilayer networks. In Artificial intelligence and statistics, pp. 192-204. PMLR, 2015a.
Anna Choromanska, Yann LeCun, and Gérard Ben Arous. Open problem: The landscape of the loss surfaces of multilayer networks. In Conference Learning Theory, pp. 1756-1760. PMLR, 2015b.
Amit Daniely. Sgd learns the conjugate kernel class of the network. Advances in Neural Information Processing Systems, 30, 2017.
Yann N Dauphin, Razvan Pascanu, Caglar Gulcehre, Kyunghyun Cho, Surya Ganguli, and Yoshua Bengio. Identifying and attacking the saddle point problem in high- nigh-dimensional non-convex op- timization. Advances in neural information processing systems, 27, 2014.
Simon Du and Wei Hu. Width provably matters in optimization for deep linear neural networks. In International Conference on Machine Learning, pp. (655-1664, PMLR, 2019.
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In International conference machine learning, pp. 1675- 1685. PMLR, 2019.
Simon S Du, Chi Jin, Jason D Lee, Michael Jordan, Aarti Singh, and Barnabas Poczos. Gradi- descent take exponential time escape saddle points. Advances neural information processing systems, 30, 2017.
Simon S Du, Wei Hu, and Jason D Lee. Algorithmic regularization in learning deep homogeneous models: Layers are automatically balanced. Advances in Neural Information Processing Systems, 31, 2018.
Morris L. Eaton. Group invariance applications in statistics. Regional Conference Series in Proba- bility and Statistics, 1:i-133, 1989. ISSN 19355912.
Sam Elder. Bayesian adaptive data analysis guarantees from subgaussianity. CoRR, abs/ 161 1.00065, 2016.
Rong Ge, Furong Huang, Chi Jin, and Yang Yuan. Escaping from saddle points-online online stochastic gradient for tensor decomposition. In Conference learning theory, pp. 797-842. PMLR, 2015.
10

---

Under review as a conference paper at ICLR 2023
Wei Hu, Lechao Xiao, and Jeffrey Pennington. Provable benefit of orthogonal initialization in opti- mizing deep linear networks. International Conference on Learning Representations, 2020.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and gen- eralization in neural networks. Advances neural information processing systems, 31, 2018.
GJO Jameson. Inequalities for gamma function ratios. The American Mathematical Monthly, 120 (10):936-99)) 940, 2013.
Chi Jin, Rong Ge, Pranecth Netrapalli, Sham M Kakade, and Michael Jordan. How to escape saddle points efficiently. In International Conference on Machine Learning, pp. 1724-1732. PMLR, 2017.
Kenji Kawaguchi. Deep learning without poor local minima. In Advances In Neural Information Processing Systems, pp. 586-594, 2016.
Kenji Kawaguchi and Haihao Lu. Deep creates no bad local minima. arXiv: 1702.08580, 2017.
Thomas Laurent and James Brecht. Deep linear networks with arbitrary loss: All local minima global. International Conference on Machine Learning, pp. 2908-2913, 2018.
Jaehoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve linear models under gradient descent. Advances in neural information processing systems, 32, 2019.
Jason D Lee, Max Simchowitz, Michael Jordan, and Benjamin Recht. Gradient descent only converges minimizers. Conference learning theory, pp. 1246-1257. PMLR, 2016.
Chaoyue Liu, Libin Zhu, and Misha Belkin. the linearity of large non-linear models: when and why the tangent kernel is constant. Advances in Neural Information Processing Systems, 33: 15954-15964, 2020.
Olivier Marchal and Julyan Arbel. On the sub-gaussianity of the beta and dirichlet distributions. Electronic Communications in Probability, 22(none): 14, 2017.
Feng Qi, Bai-Ni Guo, and Chen. The best bounds in bautschi-kershee inequalities. Mathematical Inequalities Applications, pp. 427-436 2006.
Blake Woodworth, Suriya Gunasekar, Jason D Lee, Edward Moroshko, Pedro Savarese, Itay Golan, Daniel Soudry, and Nathan Srebro. Kernel and rich regimes in overparametrized models. In Conference Learning Theory, pp. 3635-3673. PMLR, 2020.
Liu Ziyin, Botao Li, and Xiangming Meng. Exact solutions of deep linear network. arXiv preprint 247777200.04477,.0 2022.

---

Under review as a conference paper at ICLR 2023
A PROOFS OF BASIC PROPERTIES OF THE SEMI-NORM
Proof of Lemma 2.7
The first property is direct consequence of the definition of the projection
matrix Px-
Notice that
(L(W +&W) -LWPP= L(WPx)).
Considering E - 0, the definition of the directional derivative implies
(VL(WP)))x (VL(W), AW) (L((PP)))WWPPP))) X/ VAW E R".x".,
since Px P This completes the proof of the second property.
The third property is derived from the condition: orthogonal projection matrix satisfies Px PX P = P since
(L((). (VL(WP)))x
= (V (VI(WP)) = (VL(W), V)x
If set V LLW... then the fourth property is implied by the third property.
For the last property, first recall that [[[|xx = || WWPxll ll and Px = x(X"x)txT X is of a full row rank matrix if and only if Px is an identity matrix, which completes the proof.
Proof of Lemma 2.2 Because is not full row rank, we know that Px # There exists W such that W(I Px) # O. Applying the first property in Lemma 2.1 we obtain
4 W W = WPx) W( w L(WPx)
1 + L(WPx).
+
provided + WPx
Hence, L is not strictly convex, which implies that L is not strongly convex.
To prove the second property, is sufficient to show that g(W) = L(W) a(U)min (X convex. Obviously.
|W]]
o(W) I(W)- a(l)
W x; villz all) (I - Amin
(14)
L(W)- a(l) Em Wx, voll convex, because I(:38) is strongly convex. The Hessian of
IWX- YIL Xmain (WTW) [WPx 1 has negative eigenvalue; thus the second term in (14 is also convex. This completes the proof.
B EXACT STATEMENTS OF THE MAIN THEOREMS
Definitions of some quantities:
1 (2 n,a))
0 n1 o+
(15)
1 - (2 - 3),
2
< < 8
(a++)
12

---

Under review as a conference paper at ICLR 2023
2 rank(X)
Bg =
-| 11
8
Co
C1 = nNK Bs
+ NIn,,
(170 27)2/10
C2 uNK BBCo + In N,
Co
C nNKk² B8 (170 1113/m6
Co Coli(N)
C NNKK BB (170 11)2/1100
C nNK² BgCo Co In(N),
C. uyK* Bs:
where N denotes the number of distinct elements in the {.1,-.. -NN113 n with c 0.
and
N
2ux 2FN3
Vo
Theorem B.1. Given any e 0, and 0 < <, 1/2, define no NB. and consider the learning rate of Yo- There exists constant C == C(e), such that if
Tynin 2 CC.
(16)
then with probability least 1 8 over the random Gaussian initialization, we have
22 11 (1
EDLN(()
1 4e
70
EDL
K
Theorem B.2. Given any O, and 0 < < 1/2, define no
2ng 2x and consider the learning
rate to be 1l < 7/o. There exists a constant C = (c), such that if
Temin 2 C Cs.
(17)
then with probability at least 1-8 over the random one peak projection and embedding initialization, we have
27 " + EDLN(1) 1 1 -6
EDLN
K
Specially, nn 12 RN-1= min(nN, no), then requirement 17 can be replaced by
Cs.
(18)
Remark Assume W.
Way W and mi
nv -N111
n. Then, for Gaussian initialization, our Theorem B. leads to Theorem 4.1 in Du & Hu (019
Similarly, for orthogonal initialization, our Theorem B. leads Theorem 4.1 of Hu (2020).
Next, we present a version of the theorem related to balanced initialization.
Theorem B.3. Assume n, _... = n = n. Given any c > O, and < < 1/2, define
2n 3N and consider the learning rate as n < TJo There exists a constant C = C(c), such
To0
that as long as
C-Ca.
(19)
then with probability at least 1 - over the special balanced initialization, we have
(1
(D) <
1-
1
70
11a
EDEN (0).
K
13

---

Under review as a conference paper at ICLR 2023
C INEQUALITIES IN CONVEX OPTIMIZATION
Convex optimization has been studied for about a century, Recall the definitions and basic inequali- ties for a-stroogly convex and B-Lipschitz functions.
Definition C.1. A continues differentiable function f is said to be 3 Lipschitz if the gradient f 3- Lipschitz, that is if for all x, y.
[V fz(2)ll - B x|I,
(20)
is said to be a- strongly convex if for all x, y, we have
f(y) 2 f(z) (Vf(z). y 2) lly =1|²
(21)
Proposition C.1. f is a-strongly convex and V B Lipschitz with respect to a (semi- mnrmm then a S 3 and
+ 3
x) VV(x). - x) + 11 x112 f()) - f(x) s (VI()), -)
1y - xx]1
(22)
a3
(Vf(=) Vf()), x - 2
|| - vl
at Vf(x)- - v/())1
(23)
a+
[V/(x) V 2 a -ll,
(24)
f(z) - f(v) & (Vf(z), x
[f(zr) - v-(I
(25)
23
Proof of Proposition
We only prove the last inequality.
Let y (Vf())
fxx)). Since is convex 3 -ippshiit, we have
f(z) - f(x) 2 (Vf(z),z-1)
and
(V/(v), s v) + - 222
((=)-f(>) s
-1=--11
Thus,
- f()) -(0) f(y)
x(v (V/(v), v) +
2 y11
=(Vf(o),x-v) 23 [V(()) vf(1)12
let us first include and prove the following result. Lemma C.2. 1. Assume L is strongly convex, 0. Denote global minimizer of L by W.. Then, for any W.
Before we prove Lemma D.I
I(W.) - T.W) 2 2a
1
|VT(W)
(26)
2. Assume VL is 3 Lipschitz, then
L(W.) - L(W) S 23
1
|VL(())
(27)
Proof of Lemma C.2 1. First, we know that VL(W.) = 0. L a strongly convex, which implies the inequality (22) holds. Thus
L(V) L(W) (VL(W), W)x + IV --1 gVV).
Minimizing both sides in terms of V gives 26).
14

---

Under review as a conference paper at ICLR 2023
Now focus minimizing gVV). Since g(V) C' and the global minimizer exits, we have
Vg(V") VL(W) + a(V* WxPx 0,
where V is global minimizer for g(V). Thus,
g(V) = 2a
[[VL(W)]
(28)
Applying proposition C.1 to a 3 Lipschitz function VL, we obtain
L(W.) - L(W)
1
S(VL(W.), W. W)x 2B
|L(W)- VL(W.)II&
1
23 VL(W)I
D CONVERGENCE REGION
In this section, we evaluate class of the convergence region for deep linear neural networks with a deterministic initialization. Define A|R(x)= AX" (XX")- X AAxx and view A(R(X) linear operator RX)..
Recall the optimization problem
1 m m
minimize
L LW .....WNN: W1. WW
May (ayWNazww)) L(aNWN:))
(29)
and GD
{
W -1 7 aaw, (Wi(t), (l(()),==1......
aL*
(30)
where OL aw, (W1,-* WN) = aN (W
where the normalization factor aN R2
The following theorem generalizes the idea from a recent work DDu & Hu 2019 Hu et al. 2020).
For notational convenience, we denote (t=(t) W,(t)- (t).). L: LaxxWNall VL, L(aN (t)(t)) etc.
Lemma D.1. Assume the initialization simultaneously satisfies the following conditions:
Omox
[NN++1 S 1
WN+++ (0)) 2 e 02/ (NN 1
Gmin
Omax
(W,-1:1 (0)](()) S
(31)
Fmin(W;-1, (W;-1:1 (0)]R(x)) 2 -2/2 (m) (2,
Omin
3:5:((0 (0)]l S (
Lo L(W.) S (,8B=; =:
where 01, C2 M are positive constant and 0 0. Notice that Bo is a proper upper bound for ||a W N: (0) + |W.113
Set the learning rate as 17 p00y B where 0 < < 1. Define 7 2c
[1-E)2nN
Assume that
C(),, 22
Remén
(32)
Then, GD
30 satisfies
T T(W.) < (1-177) (Tn =(,
15

---

Under review as a conference paper at ICLR 2023
Definition D.1. For given e1, C2, Bu O, and 0 0, we define the convergence region Ric1, 12, 8, M, Bo) by the set of initialization that satisfies the inequality system (31).
Remark 8. The condition (31) describes the convergence region for initialization and the condition (2) describes the overparameteriiation for deep linear neural networks. At this time, is not clear how large this convergence region is. Later, we will show that the properly scaled random initialization with some extra mild overparameteriiattion conditions will fall into this convergence region with high probability.
Proof of Lemme D. To prove Lemma D.I it suffices to show that the following three properties hold A(t), B(t). and C(t) for all t = 0, I,
1. A(l):
L. - L(W.) S (1-m)) (Lo (Lo-)(W.)).
2. B()):
mma [W (NN++1(t)) S ( (
min (WN++1(t)) 2 E (nN-
(Wi-1a(t) R(x)) S 50 (
0 maz
(W)=1(())lR(x) 2 (1,
min
[W)l(t)]l S M No Rmin II. n4
3. C()):
2e 223B
(t( W.O0
R
VONY
Using simultaneous induction, the proof of Lemma D.I is divided into the following three claims.
Claim 1. A(0), .(t.......tt............ A((t), ((()) = C(t+ + 1).
Claim 2. C(t) = B(t), if Temin 2 Cle,.gg no 2 nN, where C(c1, C2) is positive constant only depend on C1. 02.
22
Claim 3. A(t), B(() = A(t + 1), if Mmin
C(ci, 02) N2 where C(c1, 02) is
positive constant only depend on c1, C2-
Proof of Claim
As a consequence of Lemma C.2 and Lemma 2.1 and A(s), s S e, we have
[VV((aW>a($s)]f VL. - Vx(W.x)) <28[L, - L(W.)]
(33)
<23 - -7)"* B.
From A(0), A(t), B(0), .(()))....(t)))) Btt), we have for any 0
aL
(s)
San [+)
aw,
2c
[VL(aNWaa
(34)
VuN
2n1
(1)) B.
16

---

Under review as a conference paper at ICLR 2023
Then,
1)
< Σ
|W,(s + 1) - Wi(s)ll
8=0
OL
(s)
OW,
8
F
2c1
/23B
1177))/22
VNN
8=0
2
V
/28B
17/2)
VTN
==0
2c
V23B
R.
v VINY
This proves C(I + 11)
Proof of Claim
Let 6; W:(() W,(0), Si N. Using C(t), we have 16:11 R, sig
N. Set 91 c min e 10./22200 02/22 -0
is suffices to show that
[WN:((t= Wn. (0))l S 1 ... 72 112,1 <isN,
(35)
(Waa (t) - W.. (0))l S /201/2 (n ... -....-nn41-- 14-1) Si
(36)
and
1/2
[1) W j0)(0)|| s M/2 No
,1 ,<isj<<,,
(37)
Amin {-ISKS)
because O min ()+B) > mnin (A) 0 mmaz (B) Umin (A)
B and max (A+ B) S maa (A) +
Oman (3) = ||||| + [ (e.g. see Theorem 1.3 in Chafar et al. (2009))
Case 1. We first prove (37)-
For <i <i<j j S N, we can write Wj.((t) (t) (W, + 5,) ....(O) + 6.).
Expanding the above product, each term has the form:
W))(k++1((0)- dz. W(,, (1t dx._..... .x. W Wik- 1)) (0), where i S K1 <..... < ko Jj j positions at which perturbation terms 8n, are taken out. Notice that the convergence region assumption (3I) implics that for any <iisj < N,
(38)
1/2
[II-1565) ns
(O)] S M/2- N
II iskgj-1
ny - max(m,-..ng)
SM.N.
Tmin
(39)
WLOG, assume M 2 1. If If j 1, then
| JF (0)l = ||||| S M (n//// )/22
Assuming i > 1,j N, and applying inequality (39) well the following inequality
8-1+1 Σ
i 1
x² x²= = (1 3 1 (1 + - 1, Va 2 0,
obtain
[Wy,(() Wo)l
j-it1
- j - i Rd (M NN 1 -//2 -s/2 (n₂-1 nz/ (mim) 1/2
<M . No (n,-11 ... -.n.i..--n//mmi nn////mmm)))) 112 R- M No/ / N 1]
<e M No (n:-1 n.ng/mmmaa" 1/2
17

---

Under review as a conference paper at ICLR 2023
The last line holds due to the following reasons: there exists absolute constant A1, A2 0 such that
(1 + ++) - S A2rN,
a 2 0, N and xN & A1. Since there exists positive constant C(c1, 02), which only depends on ç12 C22 such that when
C2) Bo N NN
Tymin
E²
(40)
we can have
R.M 18-1N81111 TTmin I A1,
well
R M / //mmm))) N 1) A2 M. R. No+1 /Vmmmin E1 = (c1,), (c1,0)) 02)-
Case 2. The proof of 35 is similar. Set j N, we can save the factor M No from previous calculation, which means
(W::(t) W (O)l
N-i+1
Sea/2
Σ
N ii+1
Rd (M n -//2 (n -..11..--)-- 11
8
5ea/2(ni-) ... nN 1) [2 + R M No ((min)
Se0/22 (n,-1 nN nN 12,2) 2,
where the last line is implied by equation (40p.
Case 3. Similarly, we have
|| [Wa((0| - (0)xx))
Se0/2 Σ
(m .. ....nng))) )2/2 R (M - 2/2 (n1
sea/?(m) ... n1)) 1/2 + M No //mmm)) N 1]
( ... .....))) 1/2,5 - N -
This proves B(I).
Proof of Claim 3
GD
implies
(N (1++1 1)
=(Ww(() - -W
OL (1)
OL (Wx-1())""aw>->> (())...(W()))) -Wi())-1 "w, (t)
OL "aWw-
N
-Wwa 11 AN
(Wi-a(()))) + E(t),
where E(t) contains all the high-order terms (those with 17² or higher), We define a linear operator
N
P(O[[A] = axy
WNaH1 WWw.:(((hh
(41)
for any A E R
Now we have
aN W N:1 (t + aNWNa(()
(W. F()
(42)
Easy to check that P(][-)] is sum of positive semidefinite linear operator.
The following proposition describes the eigenvalues of the linear operator P())
18

---

Under review as a conference paper at ICLR 2023
Proposition D.2. Let St, S2 be symmetric matrices. Suppose S UAAU", S2 VAzVT, where U = [u1, U2 ... um]. and V = [U1, 02,-.. Unl are orthogonal matrices, and A1 = (iag(();22: X2. Am) and A2 diag(Hi, M2. (,,) are diagonal matrices. Then, the linear operator I(A) = S1 is orthogonally diagonalizable, and I((As) Aapti Asg.Asg. where dijli represent all the eigenvalues corresponding to their eigenvectors Asj = u,u..
Applying this proposition and the assumption B(t), obtain the upper bound and lower bound for the maximum and minimum eigenvalues of the positive definite operator P(t), respectively.
N
Amaz (P()) ON
maa (t)( oma (W (W:++1())) S 201
AN
and
N
Xmin((())) 2 Φ
Σ 1=1
min (W (W)xx)())) - mi (WNsi+(())
N
202
(43)
uN
In conclusion, we have
N e 201 and Amin (P(t)) 2
N
Amar (P(t)) S
e
202
(44)
TN
(1-5)2nM
With learning rate of 17 11
<<<<< 1, have
230 BN
L++1 L
$ (VL, ( + ax + B
2 [I)P(I/V)] aN E(t))
(VLe, -nP(()((L))))) + 3
2 ""p /100)//111 + F(t)
(45)
S Mmmin (P(1)) 2
> max (P(I))
|V F(1)
<
202 =
N
1 e
40
+ 20a
B N
||VL,1x + F())
nN
2 nN
where
F(I) = (VL,, B())x + 3 -xx -1POOVVL)1
We claim that F(t) is sufficiently small, such that
L1+1 - Le
e 20a N
1
1]
4o +2gg
| + F())
2
30g N
8
(46)
<
T]
1 -
6oi+3e +30g
-
|V
2
2:(1 - 8)
6(e) tcx)
|V
Assuming this claim for the moment, we complete the proof. Combining (26) and (46), we have
L++1- - L, 5 - -6 to2) 2=(1-e)
Le
((W.) L, - |
which implics
T.41 - T(W,) 5 (1-e 6(e tog) 4E(1 (I, - I(W.)),
(47)
K
19

---

Under review as a conference paper at ICLR 2023
that is
L. - L(W.) & (1-e- -ler 1 ))) (Lo -
((W)) = (1 (1- L(W.)). (48)
While estimating F()), we observe that
[F()]
8 (P()) Flx Ilax
VL F(O))x
=: + 12-
From 34
we have
aL
201
2011
(L))xWx:(0)11
=: K.
aw. F
TN
VaN
Expanding the product
WN + 1) = (Wx(t)= 17 OWN (8) (WN-((t) VaWN=N (t) (1)) ... (Wi(t) OLN
OI
OLN
aw, (t)
each term has the form:
aL
0L
0L
A WN.CK.+1) oWk,
(t) W(k, 1): aW
(1)
(1) W (As (1))
Wky
where 1 < ki < K2 < ......., < N.
As direct consequence of inequality BB() and inequality 39 we obtain
1
(M No0
| || S AN V'N
(nk)*
Vumin
Recall that E(t) contains all high-order terms (those with 17 higher) in the expansion of the product. Thus, E(t can be expressed as follows:
N
aL
aL (1) WK (1) W (1))
OL
Σ
Σ
WN:(k. +1) (1) oW
(t)-W(k, (1 1):(ke 111) (1)-1 OW,, k
2=2 1sk t.
. SNNN
Set { min {(e 200
--30z) - - eor) / (c /
Recall the inequality
S (eN)s. Thus, we have
ON |E(()]l x
1
M No
--1
201
(nk)*
VON
Tymin
2=2
1
. N
-1
N Σ [(eNy(KKy)
M No Temin
201
VnN
/mmin
2=2
(49)
1
MeKM NO+1 / Tnmsn 201 (MeKN)
VuN
MeMM No+1/ /
N
<E -11
e
(ILL(a (if neMM CORMMN"T NO+1 / Tmmmn < E))
nN
N
17 nN
Using 33 and the upper bound of n, we know that there exists constant C(ci, c2), such that
Umin C(er, M2 No nN.
20

---

Under review as a conference paper at ICLR 2023
and
2/2M 22 /B vnN
S { v
neKM M NO+1/ //min _
Ammnn
(e,, 02)
2
1 1+
Using
49
we have
N A011
N
S r
''n
1]
VT S (c= - -cc))
17 nN
| l1
(50)
and
1
N2
N22
2 .
60t
11- ア
|
+ 2
1)2
I 11
2
NiN
"Ny
.22
5(c0ri e401)
221
N
Thus, 46 valid. This proves A(I..
As direct consequence of the proof of Lemma D.I. we can obtain the following lemma.
Lemma D.3. Assume all assumptions in Lemma D.I hold. For any T > O. we can choose new constants C1, 02 as well as C = C(er, (2) such that the overpurameterization assumption 32 in
Lemma D. I hold and
|R((]lx I T (laaNWNa(t)) W-
51))
where
N
aN WN + aN
[VL(uNNx(()) + R()..
NN
Proof of Lemma
D.3
Due to 33
(42
449. and lemma C.2
we have
N
|[(t))xx
aN E(t) + +
VL P())V
NN
N
N
Aman (P())()))) |VLillx
$ E(t]ll
+ 17 max
Amaa (P(t))
TNNN
nn
N
<(C' - E max
1,1---2001 -202)) -7
L
NN
2 23/3 L(W.)) (C' E max 201 1, - c 202 }))
2 eb01+
Because I., - I(..) non-increasing and C" is constant that depends only on Cı, C2, we can choose a sufficiently small positive cı, 02 and &, which depends т, such that
|R(OIlx S V23(L. L(W))) S T MalaaWN.. (t) W
3
Lemma D.4. Assume E [0, 1). Consider discrete dynamical system Vt) such that, V(t + 1) V(t) VL(((()) + R((),
where |R(OIxx - W. 1f., < 2/3, we have
[|V(t) W. 1 < (g+ (1 w.ll2,
where q defined in 15
21

---

Under review as a conference paper at ICLR 2023
Proof of Lemma D.4 Set A(t) (tt) - W. and r' ||A(t))lx x- Notice that
A [[++] 1) (1) n. (VL((()) VV.(W)) + R(1),
and
| + x)
? (V)) - VL(W))lI& - (7(() VZ( VL(W.)) + + + (2114(0)) x + 2n,
- VVLV()) + +
By inequality 23
I
|A(1) (A(1, VL((()) VL(W.))x
+ v² (VV(()()) - VL(W.) MI + 11
=(1 + 7+) ||A(t)|I x 2tp, (At),, VL(V(()) vL(W)))
+ v/2 [VV((()) - VL(W.)II
2% ag
5(1 + 7T) (1)II)
a 3 |A(1))
21T
+ 1he a + B
VV(((()) -VL(W))
Case 1: a+g 17+
2
< 2 8-
In this case, we have
a + 1
<(1 + 7T) [1(
2n. aB a+ B
1122
21/
- -
a + 3
aB
21
+ 77) |101) -2n.
|A(1))& +
1/2
a a+ B
+ 3
<1+ 77 (2 - 3)) [t)l
=(g -(0+77 7r) 1A(1))
Case 2: 0 < 77 S 2
a+3
Similarly, we have
IA 1)11& S + 7
71 - on - -na))))))))))))))))))))) -na))) |()) = 77) (+)
In both cases, we have || + 1)1 -
Thus, ||A()) s (q 77)* |1)))
Next, we will show that the trajectories of the GD 30 for deep linear neural networks 22 are close
to those of GD (2) for the corresponding convex problem 1.
Lemma D.5. Consider the GD for the deep linear neural networks
330 with learning rate 1) < m
for aN W (N), = 0, 1, .... and the GD (2) with learning rate Th- nx foror W (t),, 0,
Assume C(cr, 02) exists in Lemma D. for any C1. > O. For any E (), n < mn (m defined in we can choose C1, C2 > and the constant C. C(cr,
(r(rn//m such that inequality holds, given initialization condition (37) and overparameterrizatin condition
Temin 2 2M2 Ba 20 nN-
(52)
22

---

Under review as a conference paper at ICLR 2023
Furthermore, have
|aNWNa (.) - W & ((T,g,1) (aNWW.1(0) - W.llx
(53a)
[DDN(()) - = (d (DTT)D((.g..) 2 D(T. |aa [|aNWN.(0)) w. (53b)
EtLN(() S 33(g + ( W: -
(53c)
where D(T, mmnn
min 1 + 7) with q defined in 15
Proof of Lemma D.5 Using Lemma D.3
we obtain that for any T (0, 1) and 1) ?h, we can
find sufficiently small positive constants c1 Cg. which only depend on т, n//11, and constant
C((1,c2) O (T,n/m) mentioned in Lemma D.3 such that
(1 - 2)2
+32a BN
where 0 << 1, well
V((+1) v(0) (10)~~v((((C))) + R(),,
where V(I) ax- (1), 1/. = _ and | < =- W. I-Ixx
Notice that 0g := 1//111 = कोन and 11/100 e, where 1/0
200 -3 BN
For the right hand side of inequality 32,, we have
C(c1,c))M Bo N29
NN C" ([(T,n/m)M*' Bo
22 NN.
N
8²
6²
To show that inequality (32) is equivalent inequality 52 it suffices show that only depend on T, n/m. Notice that
8 1=1-1/ -1/1000 = Oge 0 +3cz +31c2
and cı, C2 only depend on and n//n, which implies only depend on n/n..
Now, we will prove the three inequalities in (53).
Recall GD for W()). Define (()) = (()) W(I) ax. - W()). Notice that
A(t+ =1+1)==0p) A(t) n, (VL(V()) VL(W(()) + R(t),
and
|A(++ + 1)
< (VV (t)) VL(W(()) VL((()) VL(((()))
+ +11A011 + (2114(0)lx 2n, [V)((()) - (0))(())x+7))
Let 2 [x) + 2n. (VV(V(()) VL(W +
Now, we aim to find an upper bound for 4,
Applying lemma C.2 with the assumption 0 < 7/- nx 17
2 B.
we know that
4 S (61|A(t))) +T') < ((])((t) - W, 1l + [[((t) - w.llx))
(54)
Thus
4 (t()) w.llx (I]V(t) - W.ll (t()) - w-llx) =: Up..
23

---

Under review as a conference paper at ICLR 2023
By inequality 23
|1 + 1)1
|I(())I - (2, -00---V-- vL((()))
+ n VI + UST
||A()))I& - (V W((). VL(V()) - VL(W(())x
+ n. (V(((()) ((00)VVL(WWR VV UUT
aB
< ||A(1)12 - -21-- ++
|A(1)1
+ (112 1/2 a a+
21/-
|VL(V()) (LIV())--(((())))) -VL(W()) + UST.
Case 1: 2
a+. 1/+ < 3.
In this case, we have
| + 1)
aB3
21/
| 21%
||((t)| +
1/2
[VL(((()) VL(W(O)) + UUT
a + B
a ++ B
or3
21/4
< ||A()) 21 a + B
||(())| +
1/2
(PIA(()) + UST
a + B
S (1 - (2 - 3)3 [A(() + UST
=: =:111((01X* + UST
Case 2: O < 7/ S aat..
Similarly, we have
| + 1)1Ix < (1 (2 a)) |AOII - U UUT. (55)
In both cases, we have 0 < q < 1.
First of all, since U. S Up and ||A(0)]lx = O. we obtain that
Vor
+ g¹ (14(0)13 1-9)
UOT
S Uor
14r |V - Wollx.
[|(()) - 1 q
< 1 1-q
1 1
Applying Lemma D.4 for V(t) and (t), we obtain [|V(t) - woll S (1+e)'g [V W-
and [[())) - W. x S q' [|W - W=ll respectively. Thus, (L(W(t)) I(aN WN.a
<(VL(W 4(0)x+ 8
2
<B (W (t) - W-llx ||((t)lx + 3
2 ||A(t)]
14T
7r
<B
+
(
|1 w
q
Generally speaking,
55 implies
4-1
||00) ST
Σ
d -0,
1=0
We have
t-1
|(()) S 14T) > (q + 77) (IV W.ll&
1=0
(1- ++ (1=()T=²)) I1(00) - W.
< =2(
24

---

Under review as a conference paper at ICLR 2023
Thus, have
[aNWNa(()) - - & min
14r
2(9 2(9 + 2 [V - wollx
(1-9"
as well as
(L) ((N)
<3 (1 w.llx |A(01lx + 8 |1(1))
{ 14r 1-q
1 1-9 -- 2(g 2(g+t7)) TT) | - W3ll
14r
2(q + + .0/2 min
By triangle inequality well L(W(()) L(W.) $ 20 [I W. W. we have
[(ayWwa(tt) L(W.)l 38(4 + 7r) [IV - -
Without loss of generality, we replace all 14r and 7r by which completes the proof.
E GAUSSIAN INITIALIZATION FALL INTO THE CONVERGENCE REGION
In this section, first establish some spectral properties of the products of random Gaussian matri- ces. The spectral properties lead to the conclusion: overparameterization guarantees that the random initialization will fall into the convergence region with high probability. Gaussian initialization:
Denote by (0, 1) the standard Gaussian distribution, and X the chi square distribution with degrees of freedom. Let 5u-1 {i TRd;; || =1 be the unit sphere in Red
The scaling factor aN Vainz--n ensures that the networks initialization preserves the norm of every input expectation.
Lemma E.1. For any E IR"", the Gaussian initialization satisfies
E <lax ||
Proof of Lemma E.1 For random matrix A R=:x=; with iid NO0, entries and any vector 0 + v E Rui the distribution of [|Avil is Xn². We rewrite [oll
[ (0)x / || = ZN ... 21,
where Z, i| (0)=11² / (| (0)
Then we know that the distribution of random variable Z1 X², and conditional distribution of random variables Z; (Z, Zi-1) the law of iterated expectations, we have
x (1 < <is N). Thus, Zz, Zn, are independent. By
[[] |-
II n
3=1
Define A Σi= - 1/ng. Now, we introduce a new notation Ω A.
which means that there
exists 0, such that 9 ( 2
Lemma F.2. Consider real random matrix A₁ E R S i i g with iid N 1) entries and any vector ( of E TR.
Define Ai(g) = 1=
-9 and Umin = minisisg n.j Then
P([ A Ag-1 ... 1 // |,012 e ... ny) s exp {
c²
....))
= fi() Ve> 0.
(56)
84
25

---

Under review as a conference paper at ICLR 2023
When 0 33 A1(9) I c/21l 2), we have
P(IA,,A-11* .... 1 / |z1/ <n ......n)))) S exp {
c²
f2(c).
(57)
36 In 2) A (q)
Hence, for any x E -th-1 with probability at least 1 - - we have
e (m .......... 1//2 || ... A1æ812 S s ng ng)
when 0 <2 33n2, A (g) S /2/ (12
Proof of Lemma E.2 For random matrix A, E R with i.id N 1) entries and any vector
1 the random variable |A,,11 is distributed Xm... We rewrite [=0]
x B -m
A 1|a / ||=1| -9 ... Z1,
where Z; 1|A 1 2. We have Z1 x Zel Zil Zi-1) X2, < <issis 9).
Recall the moments of Z Xm
E !
2 m
7
+
A)
VA >
m
l(2
2
Now, we aim find the Chernoff type bound.
Case 1: We define ratio of Gamma function
[(x + X)
R(x, A)
A > 0.
[(x)
In Jameson (2013), we have
R(x, A) S a(x ( 2)ー-1 S (x + 1)* A > 0, 0.
(58)
Fixed > 0, for any >> 0 we have
P(Zg.- ... Z1 > e'm1 ......n.)) nny S P(( ... Z1)² exc (m) ... ......g) n²)
< de >m ....)) ~B1((2, 2
(Markov inequality)
exp(-A(c+ In(1) ... ...,,)))) II
2 R(ng/2, (Law of total expectation)
j=1
<expl-X(c+ Imn+tmmnnnn11 .n)) + 1n +
Aln nj + +))[Cquuullity (58)
9
In(1 + 2n }
=exp 1
nj
j=1
A Eexp(-dc + 212
nj
jml
Define constant (i プ3 ny
1. Set X = "b((g)
c
we obtain (56).
Case 2: Let Mmin min mini nz.
P(Zg- ... Zn < <e- - ... ...) < P((2g ... 21) > c en ... -.gg
s exp( In(n ... m.))))))))))) + qd In +
In R m2 2
1)}
y=1
26

---

Under review as a conference paper at ICLR 2023
Define
9
Π(A) A(e In(n ...))))))) + qA Σ
In Ri Rij
1),
mmnn
< A
2
2
Notice that f(0) = 0. Define digamma function,
d dx
[((x)
(x)) In([
[(x]
Qi et al. 2006) proved the following sharp inequality of digamma function, 1
In(r 2) 1 (xx In( --> - 0,
I
where 7 is the Euler-Mascheroni constant, and e ~ 0.561459. Thus,
(())= c Σ In 1 - +
+
In [ +
1+
> j=1
n2/2
n2/2+ +
1=1
5=1
Since In(1 + x)) is concave, we have
In(1+ 2 E
[-1/2,0].
If Amin I X 5 0, then
=(A)= = 5(0)
(x))dx
S cAt /
1n(1 (1 + I x+2
dr
12/2
j=1 n1 +
j=1
A+ 1/2
= +A Σ
Aln(1 +
+ (nz/2 2 1/2)ln(1
n2/2 1/2 - 1nn(1 +
n²/2
n2/2"
5=1
< cA + Σ
(1 - 1n + nz/2'
1=1
<el 4ln())A 1))1(g).
Assume 0 < c 2l Let A 12 ln and X"
Since Roiin A2(
have
"A,(o))
X" 2 -Rminn /4.
Assume (g(g) 5 c/ (12
Thus
c²
A1(1)
+ 1 < A 36 36
f(x*) < AA, (g)
+ 44m2
(59)
AA
Thus, we obtain (57).
Lemma E.3. There exists a positive constant C(es, 62) which only depends on Cı, C2. such that if
n A & C(c1,02) then for any fixed < iig N, with probability at least exp - A
we have
max (W (N):(0)) < a (n.- -nN
(60)
and
mmin (W::(O)) 2 (n nN -N-1) 1) 1/2.
(61)
Proof of Lemma
E.3
Let A WT WT.40 (0). We know that
T maa (A) ||A||
sup
||Ab|]2
VESaN
27

---

Under review as a conference paper at ICLR 2023
and
miin (A)
inf vES-N-1
||A0112-
we know that with probability at least 1 - exp -2 (1(())) )
Applying lemma E.2
||Au|l2 / /lull22 E p,
where P p= (M;-1'' - 1/22
Set Ø- min [1 e (e
- / + e Take ø-net No for S with size
-
[W&ll < (3/0)"M RN Notice that with this size we can actually cover the unit ball, only the unit sphere.
Nol exp { { (.)(22))
( ) for all u E No simultaneously we have
Thus, with probability at least
||ull2// [|ll12 E //-00/2 e,t Pl.
Fixed E S there exists E No such that ||u - 1112 S Φ. WLOG, we assume S
||u]|2 S 1. We obtain
||lb|l2 & ||luAll + IIA(u w)ll2 c P & ||||.
Taking supereme over ||l|| obtain
mmax (A) ||||| S e02/2
P < P.
For the lower bound, we have
||Auule 2 ||Aull, - ||A(u 0)ll2 2 -2/2 ||u||| 2 @|A >
(1 (1-6)e-o)) 02/2 --000-0000000)
-000
P e =
Taking the infimum over ||:||2 1, we get
o mmin (A) 2)
The conclusions hold with probability at least
1 - exp { -12
A1
1
21 - 1opfnnln(33/45 exp
-Ω
A
1
21 exp
A
since AN S C(cr,02) 02).
Lemma E.4. There exists positive constant C(e1, 02) which only depends C2 such that if rank(X)Ai I C(c),o2), then for any fixed I j < N, with probability at least
1 we have eepp A1
Tmax (W (W S e (n (m. 1/31/2
(62)
and
min (W)z(0)) 2 - ... n2 1/2
(63)
The proof is similar to that of previous lemma. The only difference is that now we consider the Φ net to cover the unit sphere in R(X) RR",, with dim RR" = (Xan((X) where R(X) represents the column space of X.
Proof of Lemma E.4
28

---

Under review as a conference paper at ICLR 2023
Lemma E.S. Set C Mmaz Amin <00, 0 = 1/2. Assume 9(1/A1) 2 A. where 0 < asaa constant and A satisfies
1 S min { (5ln()) (1
A In(C) minn 3mm6610))77]]
8 5J
A In(N2)) k/5.
Given <isj< <,N, N, with probability at least 2e 2e-b/() c--(1/A)) we have
[W}x(00]| S M&VON (m. (n....nj-a nj-1 max
where My a positive constant that only depends on k.
Proof of Lemma
WLOG, assume 7;-1 S n.. Let A ())( From lemma E.2 we know
that fixed U E E with probability at least 1 - ((1/Ai) we have ||ulll2 - 4/3 (. 1/2
Take small constant c ( 2 5lm[6]C Let U1 uni- be an orthonormal basis
N,22
for R Partition the index set (1, , 1 S U2 U... Sp where |Sr| S
|cn;-1/N20 for each 1 S 1 [ /c].
E.3 hence omit some details. For each 1, taking a 1/2- net Ni for the set Vs. = {u - :0 spanfug E Si}}. we can get
The following discussion is similar to the proof of lemmal
Auull2 S ((n)...n)) nny u Vs,,
with probability at least
1- Wile k/Ai 2 -1--pp cxpf-k/AA + (cnn-1NN+1)m0 1) 2 (3k((55)))
since A S 5Tm(6]
h
Therefore, for any e Rm--1, we can write the sum == E, art,, where on and b E Vs,
for each I. We also know that ||u112 E1>1 1ay12. Then we have
|Aull2 S Σ layl ||ulll2 I 4(n; (.0....,))) n22 [N20 /cl Σ lai?2 & (n.....))) (n.,..,,)) 110122-
Thus,
|||| S McVCN" (1. 1/2
Notice that when S A1 31((611(0)/11 S 166 and when C e, we have
In(C))
A IC(C) < min
5ln(511(6)e/k)) k/5 <
(l1(51n()-CC/))
The success probability is at least
1 - [ /cl e
3k/(552))
21 - exp In 5lm(6)
1n(222)) - 35//(51)) -xk//(5)))
k
> - A/(5b1))
since
A < (5 C/k)
and A In( s k/5.
29

---

Under review as a conference paper at ICLR 2023
Proof of Lemma 2.3
Set rank(X), and "1, uy be orthonormal basis of the column
space of X.
Then, Px-
Ei= u
Notice that
||a, WN: (xx
Σ an W. N.1 N. (0)u.112
By assumption, we have
E a W. (0)]
E a W No.ul))
Σ
1=1
The Markov inequality implies
2r
P(la, NN.1 (0)1l 2
S 2
8
Therefore, we can bound the initial loss value as
Lo L(W.) - (VL(W.), aN (0)x W.) + 8
(a. w.llx
8 Max W N:1 (0) ---l
I 3(1laN WN:1 (0)1 + IW+12)
2r + ||..ll
s {
with probability at least 6/2.
Proof of Theorem B.7 The requirement size n2, ,1 N) in 16 ensures that
lemma E.3 E.4 2.3 and hollo
WLOG, we set C1 = c/ 6, C2 = c/3, M = 2M&VCo Bo = Bs, and
[1-112ny then with "C
probability at least
1 1- N- 001/A)) -0/AA) 8/22 1 since A < min
C(c)
In N' (n(1/8)
the random initialization satisfies the initialization assumption assumption 332. By applying Lemma D.I] we complete the proof.
31 and the overparameterrizatio
F ORTHOGONAL INITIALIZATION FALL INTO THE CONVERGENCE REGION
The following are some basic facts for random projection and embedding. Most of the following properties can be found in Eaton 1989). Proposition F.I.
1. A is a random embedding if and only if AT is random projection.
2. If A is a square matrix, then random projection, random embedding and random orthogo- nal matrix are equivalent.
3. The uniform distribution on the group is left and right invariant probability measure: that is, if A a random orthogonal matrix, then A, U, AU are all random orthogonal matrices, where U is non-random orthogonal matrix.
30

---

Under review as a conference paper at ICLR 2023
4. Assume X is q(9 I n) random matrix whose entries are i.i.d. N( 1) random variables. Then A == X(Xxx))111 is random embedding, since A = 1g and the distribution of left invariant, which means that A and U have the same distribution, where U is non-random orthogonal matrix.
5. If A is uniform distribution over orthogonal group of order and A is partitioned as A = (A1, A2). where A1 is n. q and Ag is n x (n - q), then Af and A7 are both random orthogonal matrix.
6. The columns of uniform distribution over the orthogonal group of order n, and
(EI. En)
VEI 3 E
have the same distribution, where f1. En are ii.d. ((, random variables.
7. Assume A Anxp; n2 S p is random orthogonal projection. For any v E -S8-1, |v and E
<)) are both following beta distribution with a n/2, (p n2/2, where f En are i.i.d. N 1) random variables.
Remark 9. There are several ways to construct the random matrix A = (ai5) q S n, which is uniformly distributed over rectangular matrices with AAT = c2.g. > O. Let On be uniformly distributed over a real orthogonal group of order n, and On is partitioned as On = (AT AT)", where A₁ is q x n. Assume X (I1z) and Iaj are independent standard normal random variables. Then, A, cAi, and ((X/2)-11/2 X have the same distribution.
Lemma F.2. For any E 18" the one peak random projection and embedding initiation satisfies
([) ||
Proof. Let D = pp (0)/ / /122..1........ ... up. Then D is an embedding matrix. Thus, ||Da:12 = ||=:1/2-
Let A; = Wi.+1(00) (0)/ 7p 11 where 2 p p+ 1, and Ap -
Set B; Dx 11 ||;-1 Dx P. 1222 p2ppe p 1. Then, B, follows beta distribution B(n, (n:-I m2)/2) given B -:- Bp+1, p + 1. If n1-1, then B, B:- ... Bp+1) 1, a.s.
If B B(a, b), then the expectation is given by the following equation,
EB a b
Thus, by the law of total expectation, we have
NN E Iaa WN. (oa) np
Dr EB Bp+1 |
NN np ||0:12
This completes the proof.
Next, we introduce sub-Gaussian random variables, associated with bounds how random variables deviate their expected value.
Definition F.I. A random variable X with finite mean = EEX is sub-Gaussian if there is a positive number Ø such that:
Elexp(A(X - pd)l s exp (
(1202 for all À E R
(64)
Such constant 2² is called a proxy variance, and we say that X is oussub-Gaussian, and we write X SG((²).
Example F1. Normal distribution N(, 0²) of course is o² sub-Gaussian.
For beta distribution, Elder (016) showed that B(a, b) 4(a0))42 Sub--Guussian and later, Marchal
& Arbel (017)) concluded Ha++611]
Sub-Gaussian
31

---

Under review as a conference paper at ICLR 2023
The Hoeffding bound for random variable X with mean μ and sub-Gaussian parameter is given by.
12
P| p 2 d) & 2 exp
(65)
20
Simply applying the Chernoff bound for (a, b). we obtain the following lemma. Lemma F.3. Assume a random variable B distributed as a beta distribution ( b) with two posi- tive shape parameters and b. Then,
P( B
2 1) S eex (-2(a b)r² 0.
a + b
Hence,
P
B
a
2 21- - -l-exp(-0(d/(a0+ S a a+bb
+b b
where (1(-) only depend on E. For the upper tail, obtain better bound,
IP
z (1+
S exp (xpp-(E=
In(e + 1))a}.
(66)
a a+b)
Proof of Lemma F.3
We only need to prove the third inequality. Assume random variable B B(a, b). Set = a a b, (1 + =) S y < 1, > 0, and r > O.
We are going estimate the Chernoff bound for B, which is
P(B v) S e (rv- =
The moment generating function of B is given by
a(a + 1) (a + k - 1) pn
a(a + 1)................. (a (a+ k 1) rut 0.
Ee" B =1
Σ
k= o( 1) ... (v
1) k!
yk
k!
Recall that the Maclaurin series of (1 - r/v) - over (-r, v). is given by equation
(1 r1-r = 1+ a(a + 1) .... (a k 1) pk
h!
Thus,
-ry -n "e r ry + a (1/ul-r/)).
Set r = u-r-v--ay a/y E (0, We obtain
FBB 2 expt a an((aa(v)))))))))))))))))))))+)) exp--- -
S y <
where g(x) = 1 - x + - = = E (0.1/(1 + t)}. Notice that g(1) = 0 and g((x) =
In(x) over 10, We know that
g(x) 2 g(1/(1+ + t)) = t In + t) i 1+1
t>> O.
Thus,
In(1 = exp (-(1 - In(1 + ())a) y= = (1 +1+)= 11
P(B2 S exp
++1
Set y (1 (1+ 2. We obtain the inequality 66).
Remark 10. is trivial check
[W,:a(0]] (n.441 ... nny) "
[O)l = (m--17; ... [|
[[)))())]| S (M.7441 1/2
1/2
Rmaa
(1,0441 ... "n (ispsssss))))ssssssssss.ss (1,
Remin
32

---

Under review as a conference paper at ICLR 2023
Remark 11. As special case, if n2 NN-1 n, know that [[
(05-174 nN-1)1/2 n (
Lemma FA. Assume up/
& Cp < xc Sel > 0. Let (()) represent the constant
depend only e. If C 2 C(e)nN, then with probability at least 1 - c 00m /Ca)
mmnn N: (0) _ (1 + (ms- UN-1) , ,25isp
minn (W (W): 2 (1 - =)(m -1 2
Similarly, if nN/C 2 ((E)rank(X)) then with probability at least 1 - 10ny-11CC
e
maz [ (0) - (1 (1+ +)) ... p p
miin (Waa (0) (1 (n12
....:............. ..,, p
Proof of Lemma F.4
Let D 2 1/2
N: N:p+1 (0) and
A; (p 1 n2)
1122
p:a (0). Assume Smx-1, Easy that A; is product of random
orthogonal projection and D is a random embedding.
Let e 0, 0)² R There exists orthogonal matrix 7 such that TDe =e1, ||e1|l2 =
[[TDell2 = ||l|| 1.
Since random orthogonal projection are right invariant, we have
P(I1,,Dul12 2 v) = E E
[1IIATTT p)] = [ (T(1Ate)))20)) D)] = P( 2 v).
This proves that ||.4, Dull and ||,e 12 have the same distribution.
Claim: If * 0, then | / / ||01| = [n, ... nn nz.... ..N-.-1 W/2 21/ ||0122 follows
beta distribution B(m-11/2, (n, n2 1)2))
Define B,- = App 1/- B; = A.e1 1 ||A+111 16l 11 1--1111
Then Bp
(np n2 - 2),
B
Bp-1BBp ~ B(np-2/2, (Ap--1 - n2-2)/2).
B. (BI. B.+1) ~ (n, (n.
1)
14+1 = ni. we know that ....... B
1,1,0 1,
If B B(a,b), b), then the moments given by the following equations,
a+1
- a
EB a + and EB atbatb+1
(67)
By the law of total expectation, have
EB,B++1 Bp n--1
np-1
74-1
n4 74+1
np
np
as well as
B(B,BH11 ... **)b Mi 1 2 n. nnnnnn2111-11 1/2+1
n;
14-1/2
12p22 npp22 22+1
n2p/ 1
Notice that all the integer moments of B, B Bp match those of ((m:-1/2, (op-n4-1)/22 We can verify that beta distribution satisfies Carleman's 's condition, which implies that B,B Bp
B(14-1/2 (Ni / 11u122 ~ B(n,-1/2, (n, - 1)2),, which proves the claim.
1221)
Thus, Do
With probability least 1
}. have
<
(1- (1-s)2m1-1 nhp
|A < (1 =)+ -i-1 ||l|l12
np
Using the ø-net net technique, which has been already used to prove lemma
know that
1/2
Omin (AD) 2 (1 =)
14-1
np
and
1/2
74-11
T Omax (max(AD) S (1 +
np
33

---

Under review as a conference paper at ICLR 2023
with probability at least 1 (xp In(3/o(=))) (xpp))))))mpppmmmmmmmmmm n1/Co 2 C(E)nN, for $ i S (n/ 2 (1-eep(((((n))) Hence, with probability at least - e e we have
since
Mmin (W):(00) 2 - (n--1 (M1-1---RN11" 12-11
and
maa (W::(()) (0) - (1 + -N-1)-
The other part of the proof is similar that of lemma E.4 omit it.
Proof of Theorem B.2. Set 0, c1 -/// 02 c/3. In lemma F.4 we can pick a 0, such
that + S e and 1 - 2 e c Set M = 2/Co. 0 = 0, Bo B5. and (1-c)2nx
The requirement size 12, ....... NIN N in make sure that the remark 10 lemma E.4 lemma 2.3 and lemma [.I all hold.
Notice that even though need the conclusions in lemma F.4 hold simultancously for is p,
p + 1 < < N, it suffices to apply lemma F.4 over E 7 and j E J, such that (n;; E /] and
(ngi ]} both have distinct values. Since
T N and [] I N, with probability at least
2Ne R(Hmen/Co)) - 6/2 2 6,
the one peak random orthogonal projection and embedding initialization satisfies the initialization assumption 331 and the overparamettrization assumption (32).
Under the assumption n, n, ny 1, we can use remark replace lemma F44 Thus,
with probability at least - 6/2 2 1 - 31 holds. By applying lemma 2.3 and D.1
we complete
the proof.
L
Proof of Theorem B.3 Let (N(()) = (,,, OJV ...
W.(0) = VnU,TVT S
1, and (0) = V/ Now, we want to verify 31 By simple calculation, we have
marr (W N: (0)) min (W -
mmax (W:-1:1 (0) R(X)) mar (W:-11(0) R(x))
n 11/2 112,
(68)
[[ (0)l = n/: 12212 <i <isj N.
Notice that for any 15 p S m
||aN NN1 (0)z
UNi|ay UN Ln. 0/ "[UNN[L, OV
NN
TN
where x' UN 0J" V x, || l2 = ||'|||--
Since the distribution of UN In,, 0 V right invariant under multiplying orthogonal matrices, we have
0 //2 /|/l2 B( ny
2
Thus,
IaN = =112:112
Applying lemma 2.3 we have
2 ranran((X) + I| 11
Lo (-W.)) 5
8
with probability at least 8/2.
By applying Lemma
D.1 with <>> 0, = c/6, C2 = c/3, 0 = 0, we complete the proof.
L
Proof of Theorem
3.1 Theorem 3.1 is a special case of Theorem B.I and Theorem B.2
Hence, we
omit the proof.
34

---

Under review as a conference paper at ICLR 2023
Proof of Theorem 3.2 In Theorem B.1 B.2 and B.3 proved that for given constant C1 C2 and 0 < 6, < 1/2 as well as a learning rate 7). there exists a constant C' C((1, 02) such that all three kinds of random initializations will fall into the convergence region with probability at least
1 - 6. By applying Lemma 2.3 we complete the proof.
G
TABLES
In this section, we provide some empirical evidences to support the argument expressed in Sec- tion 4 Why do bad saddles affect GD for overparameterized deep linear neural networks? Consider the following procedures for tables of [[W(t))W;(00 eo
[W.00]
a) We consider X IR 12000000 and W, 120x12 and set Y = W.X + where the entries in X and 6 are drawn i.i.d from N(0, 1).
b) We consider the loss function 1 |lal WN.1 -Y
c) For the given deep linear networks, apply the orthogonal initializations, which de- noted as (0),) $ J.JJA
d) We set the learning rate X-
for the deep linear neural networks.
c) We prepare the tables for [W:(0-W.100l
[W.(0)
Let 11 = n2 = ny = 2000, N 4. Assume W. are drawn i.dd from N(0,, 25). We obtain the following table:
i=
i
= 3
= 4
t
0.05161
0.00826
0.00826
0.18464
[ 2
0.08779
0.01389
0.01389
0.31396
[ 3
0.11335
0.01781
0.01779
0.40435
I 4
0.12109
0.01894
0.01889
0.42920
5
0.12527
0.01956
0.01948
0.44282
t = 6
0.12611
0.01967
0.01958
0.44476
0.12755
0.01988
0.01978
0.44955
f = 8
0.12745
0.01986
0.01975
0.44876
t 9
0.12819
0.01997
0.01987
0.45136
t 10
0.12793
0.01992
0.01982
0.45018
Let my = n2 = 10000, N = 2. Assume W. are drawn i.i.d. from N(0, 4). We obtain the following table:
i
2
3
0.02708
0.00153
0.04844
t 0.04319
0.00244
0.07727
3
0.05296
0.00299
0.09474
I 0.05888
0.00333
0.10533
[ 5
0.06248
0.00353
0.11176
t = 0.06468
0.00365
0.11569
t 0.06603
0.00373
0.11811
t = 8
0.06688
0.00377
0.11962
t 9
0.06741
0.00380
0.12057
10
0.06775
0.00382
0.12117
35

---

Under review as a conference paper at ICLR 2023
Let n1 table:
n2
4000, N 2. Assume W. are drawn i.d. from (0, 1).
We obtain the following
3
f 0.01622
0.00290
0.05802
t =
0.02684
0.00480
0.09601
L.
0.03411
0.00609
0.12202
1 =
0.03919
0.00700
0.14018
Ê 0.04280
0.00764
0.15306
t = 6
0.04539
0.00810
0.16232
t 0.04729
0.00844
0.16908
t 8
0.04869
0.00868
0.17408
t
0.04974
0.00887
0.17782
1 10
0.05054
0.00901
0.18066
Let ni table:
n2 8000, N 2. Assume W. are drawn i..dd
from (N, 1).
We obtain the following
i i=
i ==
== 3
t
0.01173
0.00148
0.04195
t = 2
0.01944
0.00246
0.06955
t 0.02470
0.00312
0.08838
1 4
0.02838
0.00358
0.10151
L t 6
0.03098
0.00391
0.11083
0.03287
0,00415
0.11758
t =
0.03426
0.00432
0,12253
t 8
0.03530
0.00445
0.12624
t = 9
0.03608
0.00455
0.12904
1 10
0.03668
0.00463
0.13118
Let n1 = n2 = 12000, N 2. Assume W. are drawn i.idd from NO, 1). We obtain the following table:
i= 1
i=
i= 3
f
0.00965
0.00099
0.03453
t 2
0.01597
0.00164
0.05712
t =
0.02025
0.00208
0.07244
1 4
0.02323
0.00239
0.08310
L = 0.02535
0.00261
0.09069
1 6
0.02690
0.00277
0.09621
t = 7
0.02804
0.00289
0.10029
t 8
0.02890
0.00297
0.10336
t 9
0.02955
0.00304
0.10570
t 0.03006
0.00309
0.10750
Let ni = n2 = 20000, N = 2. Assume W. are drawn i.i.d. table:
from (0, 1). We obtain the following
i 1
i i 2
i= 3
t
0.00713
0.00057
0.02551
t
0.01181
0.00095
0.04225
t = 3
0.01499
0.00121
0.05362
t 0.01720
0.00138
0.06154
L 5
0.01878
0.00151
0.06720
1 = t 7
0.01994
0.00161
0.07132
0.02079
0.00168
0.07438
t =
0.02144
0.00173
0.07668
t 9
0.02193
0.00177
0.07844
t 10
0.02231
0.00179
0.07981
H FIGURES
In this section, we provide some empirical evidences to support the results in Section 4 Numerical Experiments. We will show how the trajectories of the non-convex deep linear neural networks
36

---

Under review as a conference paper at ICLR 2023
related convex optimization problem for GD under different initialization schemes. Consider the following procedures for plots of the logarithm of loss as a function number iterations:
a) We choose X E R 128x 1000 and W, R and set W.X + E, where the entries in X, W. and are drawn i.i.d. from (O, 1).
b) We consider the loss function ] ||ay W NN X -YI
c) For the given linear networks, apply the Gaussian initialization and peak random
orthogonal projection and embedding initialization, which are denoted as W (0) i <
N.
d) For the a (O) (.. (O).
optimization problem
the initialization to be W(O)
N e) We set the learning rates 7) N-||X|| and 17. nw 7 for the deep linear neural networks
and convex problem, respectively.
We draw the loss function through 25 iterations.
37

---

Under review as a conference paper at ICLR 2023
Loss function for deep linear network and convex problem
DLN
Convex
log (Loss)
105
104
10
15
20
25
nepochs
Loss function for deep linear network and convex problem
DLN
Convex
log (Loss)
10
10
20
25
nepochs
Loss function for deep linear network and convex problem
DLN
log (Loss)
10a
104
10
15
20
25
nepochs
Figure 1: Plot of Loss as a function of number of iterations with n1 n2 f1 (Second), 2000 (Third) for Gaussian initialization, respectively.
128 (First), 200
38

---

Under review as a conference paper at ICLR 2023
Loss function for deep linear network and convex problem
DLN
Convex
log (Loss)
10
20
25
nepochs
Loss function for deep linear network and convex problem
DLN
Convex
log (Loss)
105
10
20
25
nepochs
Loss function for deep linear network and convex problem
DLN
log (Loss)
10a
104
10
15
20
25
nepochs
Figure 2: Plot of Loss as a function of number of iterations with n1 (Second), 5000 (Third) for Orthogonal initialization, respectively.
n2 f3
122 (First), 200
39


Reviews:
[{"review_id": "eOK-KscJXz", "reviewer": "Reviewer_utxC", "summary": "", "questions": "", "limitations": "", "rating": 5, "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 provides a sharp analysis for gradient descent on deep linear networks with strongly convex and smooth objectives. Specifically, for various initialization schemes such as Gaussian initialization, orthogonal initialization and balanced initialization, when the width is at least some constant times the depth, it is shown that gradient descent converges linearly to the global optimum. Moreover, it is shown that the trajectories of GD on linear networks and GD on the corresponding linear model stay close.", "summary_of_the_review": "This paper proves linear convergence results of gradient descent on linear networks with strongly convex and smooth objectives.", "strength_and_weaknesses": "I think this paper provides a nice analysis of gradient descent on linear networks with general strongly convex (potentially over a subspace determined by data) and smooth objectives. However, I have major concerns regarding the novelty. The prior work (Du and Hu, 2019) considered gradient descent on linear networks with the squared loss, and proved linear convergence if the width is at least some constant times the depth. Compared with (Du and Hu, 2019), it seems the main innovation of this paper is an extension to general strongly convex and smooth objectives; such an extension is well-known in convex settings, and it is unclear what the main challenges and novelties are. This paper also provides convergence results on trajectories, but these results also seem to follow from strong convexity.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "eEVRt_fcNdw", "reviewer": "Reviewer_76Qn", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the convergence rates of gradient descent (GD) on minimizing the training loss $L(W_N \\cdots W_1)$ of deep linear networks, where $L(W)$ is the convex training loss function of the corresponding linear model (i.e., the loss when the product $W_N \\cdots W_1$ is collapsed into a single matrix $W$). We assume that $L(W)$ is strongly convex and smooth in the subspace spanned by the data points. The paper considers the following three initialization schemes\n\n- Gaussian initialization;\n- One peak random orthogonal projections and embeddings initialization (which generalizes the orthogonal initialization proposed by Hu et al. (2020));\n- Special balanced initialization (which is a special case of balanced initialization considered in Arora et al. (2018a)).\n\nFor these schemes, the paper proves that, for sufficiently wide networks,\n\n1. GD converges linearly, and the convergence rate is of the same order as minimizing $L(W)$ as a function of $W$ (Theorems B.1, B.2, and B.3; Theorems 3.1 and 3.2 in the main text are special cases of these theorems).\n2. The trajectory of the product $W_N(t) \\cdots W_1(t)$ as we minimize $L(W_N \\cdots W_1)$ in fact stays close to the trajectory of the $W(t)$ as we minimize $L(W)$ with an appropriately rescaled learning rate (Theorem 3.3).", "summary_of_the_review": "I enjoyed reading the paper and I think the results presented in the paper deliver valuable insights. However, at the same time, it may be the case that some of the main theorems rely too heavily on some existing results and hence are of limited novelty. In the rebuttal, it would be very helpful if the authors could clarify the technical barriers that had to be overcome in carrying out the extensions. I would be happy to raise my score if my concerns get resolved.", "strength_and_weaknesses": "Convergence of optimization methods on training linear neural networks is an important area as it can provide valuable intuitions for understanding nonlinear networks. The paper generalizes existing results and presents the main results clearly.\n\nThe $O(\\kappa \\log 1/\\varepsilon)$ iteration complexity to achieve $\\varepsilon$-suboptimality looks indeed sharp because it matches the convergence rate of GD on the convex counterpart. Nevertheless, I should mention that the $O(\\kappa \\log 1/\\varepsilon)$ complexity was also achieved by some previous results such as Du and Hu (2019) and Hu et al. (2020). \n\nThe next main result that the trajectory of the product $W_N(t) \\cdots W_1(t)$ closely follows the trajectory of $W(t)$ as we minimize the corresponding convex function $L(W)$ is something that I haven't seen in the literature, unless I missed some existing results. This part is quite intriguing as it establishes that optimizing linear NN follows a similar trajectory as the corresponding convex problem, while the problem itself is nonconvex. This observation can deliver useful insights to the community.\n\nWhile I like the observation made in Theorem 3.3, for the rest of the main results (Theorems B.1, B.2, and B.3), I got the impression that the contributions made by this paper may be somewhat limited. As pointed out above, for Gaussian and orthogonal initializations, the sharp rate $O(\\kappa \\log 1/\\varepsilon)$ was already achieved by Du and Hu (2019) and Hu et al. (2020). \n\nA quick perusal of the proof reveals that the paper also builds on the techniques developed by these two existing papers. Remark 5 states that for the case where all hidden layers have the same width, Theorems B.1 and B.2 recover the main results of these papers. The \"convergence region\" established in Lemma D.1 almost exactly follows the conditions developed in the two papers. Appendix E also seems to follow the flow of the proof in Du and Hu (2019).\n\nThese observations make me question if Theorems B.1 and B.2 are merely a technical extension of the existing results on \"hidden layers having identical widths\" to just \"hidden layers with general widths.\" I know this could be a false impression as I didn't go through the proof carefully; I would be happy if the authors prove me wrong.\n\nAnyway, this concern of novelty makes me hesitate to recommend acceptance at the moment. Importantly, the main text of this paper does not make any precise comparisons against the existing results. Can you elaborate/highlight the technical challenges that had to be overcome in extending the existing results to get Theorems B.1 and B.2? \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "RAUUS7jmqV", "reviewer": "Reviewer_GzdA", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper provides a convergence analysis of deep linear neural networks with overparameterization. Compared to previous work, this paper deals with different initialization methods, more general loss functions, and varying layer width and obtains sharper convergence rate.", "summary_of_the_review": "This paper is a solid theoretical work on the convergence of gradient descent of deep linear neural networks. I recommend acceptance.", "strength_and_weaknesses": "Strengths:\n1. This paper is well-written and easy to follow. The notations are clear. \n2. This paper is well-motivated and made a solid progress in understanding the gradient decent behavior of deep linear neural networks. It shows that overparameterization leads to depth-independent convergence rate, which is not unique to orthogonal initialization, as long as the initialization falls into the convergence region. \n3. The analysis seems rigorous though I didn't check the proofs thoroughly.\n\nWeaknesses:\n1. The convergence analysis is local. From the last condition of eq (29) in Appendix D, it can be seen that the initial objective function cannot be too far from the minimum value.\n2. This is lack of intuitive understanding of the analysis, especially on the convergence region part. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Mpe1bw_aft", "reviewer": "Reviewer_gRRu", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work proves that overparametrized deep linear networks can converge as fast as gradient descent on the equivalent linear regressor", "summary_of_the_review": "I recommend rejecting the current version due to the lack of insight and discussions\n\nHowever, I think the problems can be easily fixed and I would like to change my assessment if the authors make the corresponding improvements", "strength_and_weaknesses": "Strength: (1) the result has some fundamental importance. (2) the result that deeper nets can converge as fast as a convex linear model is both rather surprising and important\n\nI think the main weakness is the lack of insights and discussion. The following problems should be addressed by the authors before publication:\n\n(1) a few overclaims: the analysis only revolves around overparametrized models, thus the title should also include the word \"overparametrization\" \n- for example, the paper did not obtain any result when the width of the model is small, whereas the title seems to suggest that the results apply to both cases\n- the same criticism applies to the abstract\n- the authors need to update both the title and the abstract to be more specific and avoid overclaiming\n\n(2) the minimum width requirement in theorem 3.1 and 3.2 depends on constants $C, C_2, C_5$. These do not affect the convergence rate, but I think it will provide more insight if the authors provide a remark discussing how they depend on the hyperparameters of the problem, such as the depth of the model, the distribution of the data, etc\n\n(3) a crucial distinction that the authors make is that overparametrization is essential for achieving such a good convergence rate; however, this point is way under-discussed. The authors should spend a lot more energy discussing why overparametrization is essential\n- for example, the authors could explain why the results/theoretical techniques cannot be applied to thinner models and then point out or suggest what properties of a thin model prevent it from being efficiently optimized\n\n(4) in the related works, the authors mentioned the previous results that deeper models can have vanishing Hessian that hinders optimization. The authors should then explain why this is not a problem from their theory \n- for example, what properties of an overparametrized model (or what assumptions that the authors made) help escape such saddles\n\n(5) how does the result change if there is a regularization term such as $L_2$? the authors should also discuss this relevant work: https://arxiv.org/abs/2202.04777\n\n(6) does the main result change in a minibatch setting? the authors should suggest some answer\n\n(7) the font size in the figures is too small. The  authors need to update it to match the font size of the main text", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Reject