Convergence Analysis and Trajectory Comparison of Gradient Descent for Overparameterized Deep Linear Networks
Authors: Hongru Zhao
Jinchao Xu
Venue: Accepted by TMLR ()

Abstract: This paper presents a convergence analysis and trajectory comparison of the gradient descent (GD) method for overparameterized deep linear neural networks with different random initializations, demonstrating that the GD trajectory for these networks closely matches that of the corresponding convex optimization problem. 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 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 to 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 a global minimizer. We focus on the trajectory of GD when applied to deep linear networks and demonstrate that, with appropriate initialization and sufficient width of the hidden layers, the GD trajectory closely matches that of the corresponding convex optimization problem. This result holds regardless of the depth of the network, providing insight into the efficiency of GD in the training of deep neural networks. Furthermore, we show that the GD trajectory for an overparameterized deep linear network automatically avoids bad saddle points.

Published in Transactions on Machine Learning Research (07/2024)
Convergence Analysis and Trajectory Comparison of Gradi- ent Descent for Overparameterized Deep Linear Networks
Hongru Zhao School of Statistics University of Minnesola
shao 118mmm...eeem
Jinchao Xu
manchao.r@@kaus..coo www.:kakustttuu.........o.m
Computer, Electrical and Mathematical Science and Engineering Division King Abdullah University of Science and Technology
Reviewed on OpenReview: https: // openreview. net/ pet/ffrmm? id= JG7dddU77UH
Abstract
This paper presents a convergence analysis and trajectory comparison of the gradient descont (GD) method for overparameterized deep linear neural networks with different random ini- tializations, demonstrating that the GD trajectory for these networks closely matches that of the corresponding convex optimization problem. This study touches upon one major open thcoretical problem in machine learning-wi why deep neural networks trained with GD met hods are efficient 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 interest- ing results have been reported to date. For example, recent results on loss landscape show that even though the loss function of deep linear neural networks non-convex, every local minimizer is also global minimizer. We focus on the trajectory of GD when applied to deep linear networks and demonstrate that, with appropriate initialization and sufficient. width of the hidden layers, the GD trajectory closely matches that of the corresponding convex optimization problem. This result holds regardless of the depth of the network, providing insight into the efficiency of GD in the training of deep neural works... Furthermore, we show that the GD trajectory for an overparameterized deep linear network automatically avoids bad saddle points.
1 Introduction
Deep linear neural networks, class of toy models, are frequently used to understand loss surfaces and gradient-based optimization methods related to non-convex problems. [Dauphin et al. (2014) and Choro- manska et al. (2015a) explored the loss function of deep non-linear networks based on random matrix theory (such as 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 un- realistic. Choromanska et al. (2015b) suggested an open problem to establish a conncction 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 lincar 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 is local minimum a saddle point; and (iii) there exists a saddle such that all eigenvalues of its Hessian are zeros the network deeper than three layers. Thus, for deep linear neural networks, convergence global minimum is impeded by the existence of poor saddles.

---

Published in Transactions on Machine Learning Research (07/2024)
Lee et al. (2016) showed that the gradient method almost surely never converges to strict saddle point, although the time cost can depend exponentially on the dimension (Du et al. 2017). Gradient descent. (GD) with perturbations (Ge et al. 2015 Jin et al. 2017p can find a local minimizer in polynomial time. Thus, the trajectory approach combined with random initialization or random algorithm circumvents the obstacle of existence of poor saddles. According to studies on continuous time dynamics of a gradient. flow (Du et al. 2018 Arora et al. 2018b); the balance property of deep linear network is preserved if the initialization is balanced. |rroa et al. (2018a b), Du & Hu (2019), and [u et al. (2020) successfully proved that GD with its corresponding initialization schemes converges global minimizer of deep linear neural networks with high probability. Furthermore, the rate of convergence is linear, and behaves like GD for convex optimization problem.
Hu et al. 2020)) established that the convergence for Gaussian initialization can be very slow for deep linear neural networks with large depths. For efficient convergence of Gaussian networks, the width needs to scale lincarly with the depth. They also showed that orthogonal initialization in doep lincar neural networks accelerate the convergence. Thus, the convergence behavior of the GD method, for training deep linear neural networks, crucially networks depends the initialization.
Recent studies have demonstrated the connection between deep learning and kernel methods (Danicly 2017
Arora et al. 2019a by Chizat et al., 2019 Lee et al.] 2019 Du et al.
2019; Cao & Gu 2019 Wood wort
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 et al.) 2018: Liu et al. 2020 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 expansion around their parameters at the initialization [Lee et al.
2019
In this paper, we first study the convergence region, the set of initializations which lead to the linear convergence of GD for deep linear neural networks (see Lemma 3). Next, we demonstrate that if the minimum width among all hidden layers is sufficiently large, then the random initialization will fall into the convergence region with high probability (see Theorem [ Theorem 4 Theorem 5 and Theorem 6) Furthermore, the worst-case convergence rate of GD for deep linear neural networks is almost the same as the original convex optimization problem with corresponding learning rate. The most significant finding of our work is that the trajectories of gradient descent. for deep linear neural networks are arbitrarily close to those of the corresponding convex optimization problem, establishing strong connection between their optimization dynamics and providing insights into gradient descent behavior in more complex neural networks. The precise statement related to Remark 3 Theorem Lemma and Corollary
1.1 Our contributions
This work is inspired by recent work by Du & Hu (0019 and Hu et al. (2020), who carefully constructed the upper and lower bounds of eigenvalues of the Gram matrix along GD and established linear convergence. this paper, we generalize their results to strongly convex loss functions with layer-varying widths, and obtain sharp results. We show that our rate of convergence for GD in deep lincar neural networks matches the worst-case convergence rale for the original convex optimization problem. Next, we show that the optimal rate depends neither the types of random initialization nor on the depth of the network, provided that the width of each hidden layer is appropriately large.
The most significant contribution of our work is the trajectory comparison result, which demonstrates that the trajectories of gradient descent for deep linear neural networks can be made arbitrarily close to those of the original convex optimization problem []]. To the best of our knowledge, this trajectory comparison result is the first of its kind and has the potential to greatly influence our understanding of optimization in deep learning.
2

---

Published in Transactions on Machine Learning Research (07 (024)
2 Preliminaries
2.1
Problem Setup
Let 2 E Rh= and y E Ry be an input vector and target vector, respectively. Define { y: a training dataset of size m, and let X (2, " Fmm F 0 and Y == [y1, W2,. ". ,um]. Denote the weight parameters by W E g",
=(y,,
Consider the well studied convex optimization problem:
1 Σ (WW,, L(W): ==
minimize W
(1)
where 1(-3y) strongly convex and has a smooth gradient with respect to its first argument uniformly y. The GD for convex optimization problem with learning rate 7 is given by:
- V(V
(2)
For any matrix A, let omnr (A) and mmin (A) be the largest and smallest singular values of A respectively. In this paper, consider two types of matrix norms and one type of semi-norm for A, ||||| := Omaz (A), ||]l tr(AA"), and | ||APx||ps ps where Px X)xxx)xx is the orthogonal pro- jection matrix onto the column space of X, and (X*X)t is the Moore Penrose inverse.
For two real matrices A, B with the same size, we consider their Frobenius inner product as well as their semi-inner product, (A, = (A, B == tr(ATB) and (A, B)x == (APx, BPx)
The following lemma illustrates why semi-norm || crucial our analysis.
Lemma 1 Assume that ((,3) is a(l)-strongll conver. The following statements hold.
1. X is not full row rank, then L(W) is neither strictly convex nor strongly connec with respect to 1l
2. L(W) is am))mmi (XX") strongly conver with respect to Il-llx, where Amin (Xxi(XX)) is the smallest non-zero eigenvalue of XXT.
i
The proof the lemma above can be found in Appendix From now on, if we do not specify the inner product, we will always consider the semi-inncr product.
Assume that atstrongly convex (a > 0), and VL is Lipschhii (with respect semi-norm ll:)))) that means, for any W, V Bay xnz
L(W) 2 L(V) + (VL(V), W V)x || -VIi
VL(WW- VL(VIlx = -LIW) IIW - -VIlx
Without loss of generality, we assume that a and B are the best constants. Then, Lemma I implics a 2 a(l) Amain (xx*) Similarly, we can also show that B < (Xx) where Vi(..) is 8(1) -(1)-(ippe Lipschitz and Amaz (Xx*) is the largest eigenvalue of XXT.
Define the effective condition number of the convex function L by == K(L) = 2 < oc. x appears naturally in the rate of convergence of GD. Let W, be a global minimizer of L(W), that is, L(W.) minw L(W). Notice that W. might not be unique, but W, Px is unique, that is, if W is another global minimizer of I(W), then W. Px W Px (see Lemma 7 for the precise statement).
3

---

Published in Transactions on Machine Learning Research (07/2024)
By applying the well-known results the rate of convergence, specifically Theorem 3.9 from Garrigos & Gower (2023) and Theorem 2.1.15 from Nesterov (0003) for GD we have
1 E(t)
1
7.
- 1 - E(0). t 1.2. ... well as,
(3)
3
2
8 (1 E(1)
4x
T)6 +++ B
(1 + x)2
|W(00) W. 1,2,
(4)
where E(t) = (() - L.W.).
2.2
Deep Linear Network Setup
Let N - be the number of hidden layers. Assume rank(X) = Denote the weight parameters by We E R 1 = 1,2... ............. .N, with nN = ny. Ro = Us where the n& is the width of the k-th layer. Set (m1, 12, ... ,NN-1 and Amar = max (m1 112, ... 1. For notational convenience, we denote Rmin = min (11
Rja = Ikesy Thk and denote Wes = W ... W, for each 1 $ i $ N. Define nı-1:1 = and
W,-1s = I (of appropriate dimension) for completeness.
Consider the implicit regularization on W W for the convex optimization problem the following non-convex optimization problem of deep linear neural networks:
( Thus, we obtain
m Σ m
minimize Wi. WN
I(WN.))
UW N.)
(5)
Example 1 Specifically, if we set the loss to be 1(W Fi, vi) [Wx; v:ll2, then L(W) | X YI is
2Xxi"(XX") strongly conver, and L is 2Amos (Xx") Lipschitz. m
m
Example 2 The deep linear neural networks with regularization W W.Px be converted into optimization problem
minimize L(WN.)) + W Ix Wi.". WN
Let La(W) L(W) + A 3 Then Lx(-) is a + 2X-strongly convex, and Lxx--) is B 2X-Lipschitz.
More general, if we consider regularization with form R(W) = A g(((Px)) g(-) is -tstronyyyy conver, and 8' -iipschhi, then for the optimization problem
minimize WL, WN
L(WNa) + R(WN ... W1) =: LR(WN ... W1),
we know that LR(-) + Aa stroogll convez, and (LR(.) is + AB' -ipsshitt
2.3 Initialization Schemes
In literalure, researchers consider the following form of the deep linear network instead of
minimize L(axWNa) Wi... WW
Max W WNNT%, vi).
(6)
where aN 1/111/2 is normalization constant.
Applying GD on 6 where we update W, simultaneously for j.
W + = Wt(t) - r) aN (WN)++(tt)) VL (aN WNa (W)-na(t)) 1,.,,
(7)
Recent work consider GD
initializing W, with Gaussian initialization
Du & Hu
2019 or scaled
orthogonal initialization Hu al. 2020).
4

---

and the proof of Published in Transactions on Machine Learning Research (07/2024)
In this paper, we consider the following three kinds of random initialization which generalizes their idea.
Gaussian Initialization: Let Wi(0), Wx be the weight matrices at initialization. We assume that all entries of W,, 1 S S N are independent Gaussian random variables with zero mean and unit variance.
Then an normalization constant in the sense that for any x E " we have
E
[1axWx1(0)e133
||0:1
In fact, all initializations we discussed in this paper satisty 8 see Lemma 9. Lemma
14
Theorem G
Remark 1 Let Vi(1) J.. Wi(),, for ISiSM. Then GD with unill variance Gaussian irilialization is equivalent to
+
(VNg+z(tt)) VL (VN.((t) (V)zzatt)))) N2j
(9)
with mean zero and voriance 1 Gaussian initialization for Vi, 1, ,N. The GD 9 for the loss is equivalent to GD 77) for the loss 6 From now on, we will only consider GD for deep linear neural networks
S
Orthogonal Initialization: We consider so-called one peak random orthogonal projections and em- beddings initialization, which generalizes the idea of orthogonal initialization (Hu et al. 2020
Definition 1 A initialization WN. (0) Wy (0) W1 (0) is said to be one peak random orthogonal projections and embeddings initialization if there erists < p N, such that no S 122 S S Rpp np 2 1pt1 2 Bp+2 2 ..- 2 RN and (1),), W2(0), (O))). (0+)(0), W Wp+2(0), W (0) are independent and uniformly distributed over rectangulor matrices which satisfy
WT (0)W:(0)= = 1: sisp. W. W5)0) (0) = n mn-11ng +issjs N.
Remark 2 In this definition,
W.(0), < is are rundom embeddings and ng-1 - p+ SN
random orthogonal projections. Notice that, A is random orthogonal projection if and only if AT is random embedding.
Arora et al. (018aa studied the rate of convergence to global optimum for GD to train deep linear neural network for balanced initialization. Here, we will consider a special case of balanced initialization which is described as follows.
Special Balanced Initialization: Assume ni ... = NN-1 = n. Consider initialization Wx V II Ong (n (n=n,))VV (1) = /nU, [T,,, OR, 0n=x(n==))) and (. = VTUHT, 2 N 1, where UN-1, UN, Vi, V== 2 N - orthogonal matrices (random deterministie), and Vx has uniform distribution over orthogonal matrices. Notice that only Vy is required to be random.
A simple estimation of the loss at the initialization is given by the following lemma.
Lemma 2 Tf the inilialization satisfies for all x, then with probability least 1 6 we have
L(axWx1(0) L(W.) < BBs where B5 = (2
ra)k(X) (2-ramm((x) + || llWal1x)
Note that using sharp concentration inequality, the bound B3 be improved.
5

---

Published in Transactions on Machine Learning Research (07 (07/2024)
3 Main Results
For the rest of this paper, assume the thinnest layer is either the input layer or the output layer, that is, Tomin 2 max nN} and the ratio between the width of any hidden layer is bounded from above, precisely we have Rmoz I Co < oo. Define some quantities as follows:
Amnn
az/ (2 n)aa));
0 < 1/ S a+3
q =
1 (2 11,8);
2 a+3
< 1/4 < 3
(10)
C = nNK² B&Co InN,
C2 = ,NN BsCo + CoIm(N)
(11)
C3 ,u Bs.
where N denotes the number of distinct elements in the set {n1,... .N-11
Here, the quantity & is related to the rate of convergence of gradient descent for strongly convex function I(W). Setting the learning rate f)+ a+B we can rewrite the well-known rate in (4) in terms of g, due to
4x
9 on7, (2 - m/(x)) =1 (1 + x)
The parameter 8 ()) is confidence threshold, such that the conclusions in Theorem 1 (or Theorem 2 hold with probability of at least 1 - 5, given extra incquality constraint between the minimum width of hidden layers, Amin and the depth, N, as quantified by C1, C2, and C3.
For notational convenience, we denote
E(t) L(W(t)) L(W.), and (D) L(aN (t) L(W.).
Our assumptions and notation are now in place. We next state our main theorems in this section.
3.1 Linear Convergence of Deep Linear Neural Networks
In Appendix
B we present an analysis of the linear convergence of GD for deep linear neural networks, in Theorem 4 for Gaussian initialization, Theorem 5 for orthogonal initialization, and Theorem for special balanced initialization, respectively. These results extend the work of Du & Hu (2019). and Hu et al. (0020) which proved similar convergence rates with & loss. In particular, with the special choice learning rate nn AN, our Theorem and Theorem 5 lead us obtain the following optimum convergence rate.
17
7 with learning rate n 2N Given any 6 E ()) and Co E (o), there erists a constant C = C(E), such that if one of the following two overganmmeterization condition holds:
Theorem Consider GD for the deep linear neural networks
1. Tmin 2 C C1 -N with the Gaussian initialization,
Tmmin 2 C C2 with the one peak random orthogonal projections and embeddings initialization,
with probability at least 1 - 8 we have
EDLN( < (1-1111)))) ) 1,,
Remark 3 Consider GD 2 with learning rate n7. 8r and initialization W = ax N. The well-
known result the rafe of convergence 3 for GD of the conver optimization problem i matches the rates in Theorem 1
Remark If we set Co=1 = and consider E loss, then we can recover the main results Du Hu 2019 and Hu et al. (2020), that the number of iterations needed reach precision is O (xlog :) for lo loss. We generalized their results to any strongly conver loss with varying width.

---

Published in Transactions on Machine Learning Research (07 2024)
3.2 Trajectory Comparison
Theorem and Remark X establish that the rate of convergence to global oplimum for GD to train deep linear neural networks is almost the same as the trajectories for GD to train the corresponding convex optimization problem with high probability, the width is large enough. Morcover, GD for the fully-connected deep linear neural networks ( and that for GD 2 have almost the same trajectories.
Let 7/
2nx be an upper bound of learning rate 17. We can show that the trajectories of GD for deep 3N
_ linear neural networks (6) with learning rate 77 7 are close to those of GD (2) with learning rate 7/- nx " for the corresponding convex optimization problem (1) with high probability, if the width of cach hidden layer is sulficiently large. The precise statement. is as follows.
Theorem (Trajectory Comparison) Consider GD for the deep linear neural networks 7 with learning rate 7) mn for ay (t), t = o.... and GD ( with learning rate The An for W (()), t 0, 0.1,.... Given 7, E (0, 1) and Co E [1, 00), there erists constant C C(T,n/m) such that if one of the following three overparameterisstion conditions holds:
1. Amin 2 C C N with the Gaussian initialization,
2. Tmmin 2 C C2 with the one peak random orthogonal projections and embeddings initialization,
Timin 2 - C3 with the special balanced initialization,
then with probabilily at least - 5, we have
[a (t) - ((1) D(T,q,t) JaNWN= W.llx (EDLN()) E(1) 3 /D(,ggT) (() Ilav (a. W.
(12a)
(12b)
WN.N EDIN (1) S + W N:1 (0) W.I
(12c)
where D(T,q,t)= min { [يي [ 20 7) with 0 < 9 1 defined in 10
Remark 5 To our knowledge, we are the first who showed that the trajectory of the overparameterized deep linear neural networks is close the original conver optimization problem with appropriately rescaled learning rate.
Corollary 3 Under the selling of Theorem probability,
if we set v
2nN (a+B)N, the following inequalily hold with high
ED 33
(1
(1+ +7) [IaN W-
4k
(13)
We notice that the rate of convergence in 13 matching 4 is better than that in Theorem 7 It is because if K > 1, we can choose sufficiently small, so that the following inequality holds:
4k
x)+
Roughly speaking, Theorem Theorem Theorem together with Theorem 5 illustrate that the GD for convex optimization problem recovers the convex problem itself in terms of optimization, at the cost of lincar convergence only with high probability for random initialization.
Remark 6
In constants C₁ C2, Cs defined in {11), the term rankiX) is not optimal, since our concentration 8 inequality only depends on the second moment. By using stronger concentration inequalities for our Lemma
2 similar to the proof of proposition 6.5 (Du & Hu 2019) and Lemma 4.2 (Hu et al. 2020), the rank(X) can be improved to 1 + log(
log(renk(X)) rank(X)).
The Ci is proportional to x², which is slightly better than the constant in Du 8 Hu (209)) that is proportional
to x3 The C2 is also slightly better than the constant in Hu et al. (2020), since we do not have the extra
term
The improvement of the constant is mainly due to introducing the semi-norm ||

---

Published in Transactions on Machine Learning Research (07 (07/2024)
3.3 Proofs Overview
Now we will give an overview of the proofs for all theorems in the main results. Since Theorem in the main rosults are special cases of general theorems with non-optimal learning rate (sce Theorem 4 and Theorem 5
only need to focus the proofs of the general theorems (sce Theorem 2 Theorem Theorem and
Theorem G
We start with the convergence region of deep linear neural networks. Basically, the convergence region is the set initialization which lead to the convergence of GD for the deep linear neural networks. The precise
definition can be found in the Definition - Temma and Lemma @ prove that this convergence region satisfies the following properties: if the initialization falls into the convergence region, then
(i) GD guaranteed to converge to a global minimizer of the deep linear neural networks,
(ii) the worst-case rale of convergence of GD for the deep linear neural net works, which is a non-convex problem, is almost the same as the corresponding convex optimization problem with a corresponding learning rate, and,
(iii the trajectories of GD for the deep linear neural networks are arbitrarily close to those for the corresponding convex optimization problem.
More precisely, Lemma 3 establishes the convergence region for deterministic initialization and it demon-
strates the first two properties, (i) and (ii). Additionally, in Appendix E and Appendix F we also proved that the spectral properties of products of random matrices partially reveal the mystery of overparameterization that is, overparameteeriation by adding width of each hidden layer guarantees that the random initialization will fall into the convergence region with high probability. These results provide foundation to establish the main linear convergence theorem for random initialization (see Theorem
and 6p.
On the other hand, Lemma ! shows that if the initialization falls into the convergence region, the update rule for the product weight matrices in GD for deep linear neural networks is more or less that given in 2 This result can be used to establish both Theorem 2 and Lemina which precisely the property (iii) of the convergence region for deterministic initialization and non-deterministic initialization, respectively, It worth mentioning that property (iii) of the convergence region cannot be directly obtained from the results of Du & Hu (2019) and Hu et al. (2020). highlighting the contribution of our work in establishing this property.
4 Convergence Analysis and Trajectory Comparison
4.1 Initialization and Convergence Region
Arora et al. (2018a) showed that if the initialization is approximately balanced, and the product matrix (0: is very close to a global minimizer, then GD linearly converges to the global minimum for the deep linear network, without any requirement on the width. However, the convergence region (Arora et al. 2018a) is very small, since (n.1(0) has to be very close W. Later, several papers by Du & Hu (2019), and Hu et al. (2020) successfully proved that GD with Gaussian, or orthogonal initialization linearly converges to global minimizer of the overparameterized deep linear neural networks with high probability. They introduced technique to analyze trajectories of GD with large widths for any deterministic initialization.
We introduce the following lemina which generalizes the idea from recent work (Du & Hu 2019 Hu et al. 2020), describes the linear convergence result for deep linear networks with deterministic initialization.
APx, and view AlR(x) as lincar operator on R(X), the column space of X. For notational convenience, we denote Wsa(!) W,(1) .W,()) L, L(ay W N.a (()), and V L,, = V (a(aaWaaa(() etc.
Define A A|R(x) AXT
8

---

Published in Transactions on Machine Learning Research (07/2024)
Lemma 3 Assume the initialization satisfies the following conditions simaltaneouslyy
maz
[ NW++++000 (0)) S e (
-
min (N:++1(0)) (0)) 2 e (n 1/2 ,5is -1,
manz (0)
(14)
miin
([=1:1(0)R((x)) 2 e -
( (11-1:1) 1225is
[ jax (0)] S M/2 N (T Ti max 1
Lo- L(W.) & 3B. =:
where c1, 02, M are positive constant and 0 2 0. Note that Bo a proper upper bound for ||ax ( + I[
Set the learning rate (1-e)2ng 2011t
where 0 <<< 1. Define y=
soN Assume that
Nn
C(c1, 122
Toiin
6²
22 N20
(15)
Then GD satisfies
L, (W (To -(W.)),
Definition 2 For given 61, 02, M, Bo > 0, and 2 0, we define the converyence region R(c1, C22 M, Bo) by the set of initialization that satisfies the inequality system [T].
Remark 7 Condition
14 describes the convergence region for initialization and the condition 15 de-
scribes the overgarumelerizatoon for deep linear neural networks. At this time, it is not clear how large this convergence region is. Later, will show that the properly scaled random initialization with some eatra mild overgarameleriaation conditions will fall inlo this convergence region with high probabilily.
Our convergence region (see 14 in Lemma 3 and Definition 2 originated from Du & Hu 2019). and Hu ct al. (2220). This convergence region can be view as neighbourhood of special balanced initialization, if 712 11 Both the Gaussian and orthogonal initializations are approximately balanced.
For the & loss, we assume without loss of generality that decomposition method in Claim B.1 from Du Hu (2019). However, when considering the general strongly convex loss, we have to directly confront the low rank in our analysis. Thus, the || appears naturally and helps to achieve the sharp rate of convergence in our main theorems.
full rank and L(W.) = O, due to the
4.2 Dynamic of GD for Overparameteriiee Deep Linear Neural Networks
We will explain why trajectories of GD for overparameterized deep linear neural networks with approximate balanced initialization are close to trajectories for convex problems. Although the recent result (Ziyin et al. 2022 can describe the exact global minimizer for the deep linear network (with regularization term such the evolution of each W, is still hard to track. Instead, we consider the discrete dynamics for product matrices (t)(t):
as Eg)
an WN.i aN wtw.a///w00000o////////////00010
where linear operator
PO[A a
W W (w (xx()))
for any A E N
Du & Hu 2209)) showed for their linear operator P3 that Amaz (P)) S (( Amar (x"X) X) and (nan(()) 2 2 ny Amin (X" X). We prove that for our operator P(t) N (also see (43)), where is the identity nx operator. E(() is negligible, which leads to the following lemma on discrete dynamics.

---

Published in Transactions on Machine Learning Research (07 (224))
4.3 Trajectory Comparison
We can summarize the above result in the following dynamic comparison lemma.
Lemma 4 Assume that all the assumplions in Lemma g hold. For any T > 0, we can choose new constants C1 O2 as well as C == C(e1,c2) such that the overparameteriaation assumption (15) in Lemma 3 hold and
|R(()]lx S
-T &TllawWw.1()) W-
(16)
where
N W N: + - WNW.. - (V(oxwxx1 R(I).
nN
Without the R(t) term, the discrete dynamics is exactly GD 2 for convex function To control the distance between the two trajectories, we introduce the following lemma, which coincided with Theorem 6
in Hacohen & Weinshall (2022).
Next, we introduce the following lemma for convergence analysis for dynamical system V(I (1 v()) 17. VL(((()) R(t), with V(t) (t))), 0, 0,
Lemma 5 Consider discrete dynamical system (tt) such that,
V(++ = v(t) n- V(V(()) + R(0,t20, where [[(()]lx ST ([V(( W.llx. and r E [0, If 1/- S 2//3, we have [V(t)) - W. - ( 7 (V w.
where 0 <<q is defined in 10
Proof of Lemma 5
Set (() (()) W. and r' -|/((( Notice that
( + 1) = A (1) (VL(((() ((..)) + R((),
and
| + 1 3 (L)V(t)) VL(W.)11 - (L(VV)) VL(W)))
+ ||(() + (211 + 2n, [[ - VL((.)Ilx + +T)='
By inequality
28
in Appendix
we have
[ + 1)IR
S | (7()) (L(()))) vL(W)))x
+ (t) VL(W))II + 7r 11
=(1 + 77) [1A()) (A(), VL(V()) VL(W-))x
+ 2 (L)((t) - VL(W.)I
21/- aB a + B ||A(1)1
<(1 + 7T) |1(0))
+ 112 a + 3
2T/
|[V((V()) -VLW)))
Case 1: 2
a+B <. g-
In this case, we have
A + 1 $(1+77) |A 2n, a3
21/
|A(1)) + 1/2 a+D B
[VI(V()) - VL(..)11
a 3
a.
2n-
<(1+77) |A(0)1 - 21I
|A(1 +
1/2 +
18 |IA(0)
+x+
s(1+ 77 - m1) (t))
10

---

Published in Transactions on Machine Learning Research (07/2024)
Case 2: 0 1/ S a+g Similarly, we have
2
[ + 1)llx - 71 a2 n.a))) (.a))) = 77) [|(
In both cases, we have |A(t + 1)IIx S (7+
Thus, |1(()) - (a+ ( 7+) [1
With the help of this lemma, we further obtain the following trajectories comparison lemma, which leads to the main conclusions of Theorem 2 We will show that the trajectories of GD 7 for deep linear neural
networks ( are close to those of GD 2 for the corresponding convex optimization problem Now, we introduce the following technical lemma for trajectory comparison.
Lemma 6 Consider GD for deep linear neural nelworks ? with learning rale < =
2n for N3
@y NNa 0,,, 0, and GD with learning rate 17. ax 7 for =
Assume that C(cr, erists in Lemma 3 for any c1 > 0. For any T E (0,1), and l M we choose C1 O2 > 0 and the constant = c(e, = (T(,,//m), such that inequality [16] holds, given inétialization
condition 14 and overparaameterriationn condition
Remin 2 CM CM No
(17)
Then, we have
[oN W() D(T,q,)) [aaNWNa(0)) W
(18a)
(EDLN()) E(1) 3 (1/2 g( [aaw W.
(18b)
EDLN (t) s 33(g+ +) I| (0) w.
(18c)
where D(r,q,t) min 2(q + 7)(}, with q defined in (10).
The proof of Lemma. 0 requires analyzing the dynamical system A( (1) - n. (VL(V())) - VL(W(())) + R(),
with A()) v(() - W()) and V(I) www The analysis is essentially the same the proof of Lemma
4.4 Random Initialization Fall into the Convergence Region
In Appendices and we establish that when the width of each hidden layer is sufficiently large, both Gaussian and one peak random orthogonal projections and embeddings initializations will fall into the convergence region, as defined in Definition 2 Morcover, our analysis treats the balanced initialization as a specific instance of orthogonal initialization.
To analyze the product of Gaussian random matrices, only requires analyzing the concentration inequality (Lemma 100 for the product of the x distribution random variables, which has already been considered in Du & Hu (2019) To analyze the product of one peak random orthogonal projections and embeddings, it only requires analyzing the concentration incquality (Lemma 16 for the product of the beta distribution,
which has not been considered in Hu et al. (2020).
Given this foundation, and when combined with Lemma and Lemma we can corroborate Theorems
and 5
4.5 Navigating Away from Bad Saddles
A critical point of f is a bad saddle if Amin (V²f(x*)) Kawaguchi (2016) showed that the deep lincar network has bad saddles, thus in general vanishing Hessian can hinder optimization. Now, we are going explain why do bad saddles not affect GD for overparameterized deep línear neural networks.
11

---

Published in Transactions on Machine Learning Research (07/2024)
Theorem 2.3 in Kawaguchi (2016) showed that all bad saddles satisfy that WN-1:2 is a non-full rank ma- trix. Thus, to show that trajectories of GD are away from bad saddle points, it sulfices to show that inf, Tmin Cmin (122)))))))) > O. In literature, there are two main ways to avoid bad saddles for GD to train the deep linear network.
On the one hand, under the setting in Arora et al. (2018b), has been showed that the approximate balanced initialization satisfies ||W N:1 (0) 10--llll W- S main (W.) - c, for some 0 < Omin (W-), then min (Wwa (t)) through the training as well as [[Wi(t)) (4IIW.Ilp)' and [| s (1.1) )/M. Thus,
Omin (Wn:(())
min (WN--1 2
(W]
(4 (4
On the other hand, if we assume our rescaled and overparameterriee weight initialization falls into the convergence region 14). we can show that (see B(t) in the proof of Lemma
mmin (WN:2(t).
Minn ( (WN (N)1aa())]
Tmin (WN-1:2(t) 2 max
Omao (W (t)) Oman (t)
Thus, Omin Wv Ww-12
nW-1 2 e c1- O. For the overparamelerized deep linear 2 - max - ni
(ny-19) 1-)
network, GD initialized in the convergence region will force the trajectories away from all bad saddles.
Numerical Experiments: In Appendix we will discuss some empirical evidence to support the main results shown in Section 3 The figures compare the trajectories of the logarithm of loss for gradient descent in deep linear networks and the corresponding convex optimization problem. The numerical experiments demonstrate that increasing the minimal width of the hidden layers in deep linear networks leads to opti- mization trajectories that closely resemble those of the corresponding convex problem, irrespective of the initialization scheme. This suggests that sufficient network width stabilizes the optimization process, sup- porting the main theoretical results presented in the paper.
5 Conclusion
In this paper, we present comprchensive convergence analysis and trajectory comparison of the gradient descent method for overparameterized deep linear neural networks with different random initializations.
A key contribution of our work is the trajectory comparison between gradient descent for deep linear neural networks and the corresponding convex optimization problem. We showed that, with appropriate initial- ization and sufficient width of the hidden layers, the trajectories of gradient descent for deep linear neural networks closely match those of the convex optimization problem, regardless of the depth of the network. This finding provides valuable insights into the optimization dynamics of deep linear networks and their relation to their convex counterparts.
The convergence analysis and trajectory comparison presented in this paper contribute to the growing body of work understanding the optimization landscape and dynamics of deep neural networks. Our findings the efficiency of gradient descent in the overparameterized regime and the role of initialization in shaping the optimization trajectories provide valuable insights that can potentially extend to more general deep neural network architectures.
There could be debate on whether the techniques and insights for lincar networks can be extended to deep non-linear networks. On the one hand, works by Ding et al.) (2022) and He al. (2020) have indicated that the loss landscapes of non-linear neural networks differ significantly from those of linear networks. Specifically, non-linear networks may contain spurious local minima, while linear networks do not. Hence, the training dynamics of non-lincar networks may be quite different from those of lincar networks. On the other hand, Du et al. (2019) has already demonstrated that gradient descent finds a global minimum in training for sufficienlly wide deep neural networks, including multilayer fully-connected neural networks, ResNet, and convolutional ResNet. In these cases, the lincar rate of convergence in terms of loss has been established for overparameterized neural networks. However, the result of the trajectory comparison has not been established.
12

---

Published in Transactions on Machine Learning Research (07/2024)
Future research directions include exploring the generalization of our findings to nonlinear deep neural net- works and investigating the impact of different optimization algorithms and regularization techniques on the convergence and trajectory properties of deep networks. Furthermore, our work motivates the develop- ment thcoretical frameworks that can provide a more comprehensive understanding of the optimization dynamics of deep neural networks.
References
Sanjeev Arora, Nadav Cohen, Noah Golowich, and Wei Hu. A convergence analysis of gradient descent. for doep lincar neural networks. CoRR, abs/1810.02281, 2018a.
Sanjeev Arora, Nadav Cohen, and Elad Hazan. On the optimization of deep networks: Implicit acceleration by overparameterriztton.. In International Conference Machine Learning, pp. 244 253. PMLR, 2018b.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis optimization and generalization for overparareterizeel 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 infinitoly wide neural net. Advances in Newral 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 Chafai, Djalil Chalä, Olivier Guédon, Guillaume Lecue, and Alain Pajor. Singular values of random matrices. Lecture Notes, 2009.
Lénaïe Chizat, Edouard Oyallon, and Francis R. Bach. On lazy training in differentiable programming. Tn NewrIPS, 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 multilayer networks. In Conference on 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-dimensional non-convex optimization. Advances neural information processing systems, 27, 2014.
Tian Ding, Dawei Li, and Rnoyu Sun. Suboptimal local minima exist for wide neural networks with smooth activations. Mathematics of Operations Research, 47(4))2784 2814, 2022.
Simon Du and Wei Hu. Width provably matters in optimization for deep linear neural networks. In Inter- national Conference on Machine Learning, pp. 1655-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 on machine learning, pp. 1675 1685. PMLR, 2019.
Simon S Du, Chi Jin, Jason D Lee, Michael I Jordan, Aarti Singh, and Barnabas Poczos. Gradient descent can take exponential time to escape saddle points. Advances in neural information processing systems, 30, 2017.
Simon S Du, Wei Hu, and Jason Lee. Algorithmic regularization in learning deep homogencous models: Layers automatically balanced. Advances in Newral Information Processing Systems, 31, 2018.
13

---

Published in Transactions on Machine Learning Research (07/2024)
Morris L. Eaton. Group invariance applications in statistics. Regional Conference Series in Probability and Stalistics, 1:1-133, 1989. ISSN 19355912.
Sam Elder. Bayesian adaptive data analysis guarantees from subgaussianity. CoRR, abs/1611.00065, 2016.
Guillaume Garrigos and Robert M Gower. Handbook of convergence theorems for (stochastic) gradient methods. arXiv preprint ar 0i0: 11235, 2023.
Rong Ge, Furong Huang, Chi Jin, and Yang Yuan. Escaping from saddle points-online online stochastic gradient for tensor decomposition. In Conference on learning theory, pp. 797 842. PMLR, 2015.
Guy Hacohen and Daphna Weinshall. Principal components bias over- over-parameterized linear models, and its manifestation in deep neural networks. The Journal of Machine Learning Research, 23 2022.
Fengxiang He, Bohan Wang, and Dacheng Tao. Piecewise linear activations substantially shape the loss surfaces of neural networks. arXiv preprint arXiv:2003.122: 2020.
Wei Hu, Lechao Xiao, and Jeffrey Pennington. Provable benefit of orthogonal initialization in optimizing deep linear networks. In International Conference on Learning Representations, 2020.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems, 31, 2018.
GJO Jameson. Inequalities for gamma function ratios. The American Mathemalical Monthly, 120(10): 936-994 986-940,22 2013.
Chi Jin, Rong Ge, Praneeth Netrapalli, Sham Kakade, and Michael I Jordan. How 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. arXi:: 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 as linear models under gradient descent. Advances in neural information processing systems, 32, 2019.
Jason D Lee, Max Simchowitz, Michael I Jordan, and Benjamin Recht. Gradient descent only converges to minimizers. In Conference on learning theory, pp. 1246 1257. PMLR, 2016.
Chaoyue Liu, Libin Zhu, and Misha Belkin. On the linearity large non-linear models: when and why the tangent kernel is constant. Advonces in Neural Information Processing Systems, 33:15954 15964, 2020.
Olivier Marchal and Julyan Arbel. On the sub- gabbsaaussa of the beta and dirichlet distributions. Electronic Commanications in Probabilily, 22(none): 14, 2017.
Yurii Nesterov. Introductory lectures on conver optimization: A basic course, volume 87. Springer Science & Business Media, 2003.
Feng Qi, Bai-Ni Guo, and C. Chen. The best bounds in gautschi-kershaw 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. Learning Theory, pp. 3673. PMLR, 2020.
Conference on
Liu Ziyin, Botao Li, and Xiangming Meng. Exact solutions of deep linear network. arXiv preprint orXiv:2202.00/7 2022.
14

---

Published in Transactions on Machine Learning Research (07 (224))
A Proofs of Basic Properties of Semi-norm
Lemma 7 The loss function L(W) defined in i satisfies the following properties: for any W, V E R"
L(W) L(WPX),
2. VL(W) VL(W
(VI.W)))) (VI(W), V)x,
4- [VL()))>=
|| = =| if and only X is full row rank.
If L(W) is a-strongly conver (a > 0) with respect to the semi-norm || then W.Px unique, that is, W another global minimizer of L(W), then W.Px = W'Px.
Proof of Lemma Px.
The first property is direct consequence of the definition of the projection matrix
Notice that
(L(W + =&W) L(W)) (L(WPx + -(WPP))
By letting s + 0, the definition of the directional derivative implies
(VL(W), (VL(WPs) VV AW) VAW E R"*x".
since Px P
This completes the proof of the second property.
The third property is obtained based on the fact that the orthogonal projection matrix satisfies Px = P Px, since
(VL(W) Px, PV (VI(WPs))x (VVW), (VI(W),
Set V = VLWW). Then the fourth property is implied by the third property.
For the fifth property, first recall that ||]]x = [[Pxxll and Px = X(XTx)xx.. is of full row rank if and only if Px is identity matrix, which completes the proof.
To prove the last property, let W' be another global minimizer of L(W).
Since L(W) is strongly convex, have
L(W") L(W.) 2 L(W") (VL(W"), w')x + W - -w.1
(19)
Because T(W.)- I(W"), show that
(V + (1- W 0.
(20)
Applying property 3 and sctting t in 20 incquality
19 implics || Wallx
By the definition of semi-norm || obtain that
|W'Px W, W.Pxlle I|" W.llx
which implics that W'Px W.Px for any global minimizer W Thus, W. Px unique.
15

---

Published in Transactions on Machine Learning Research (07/2024)
Proof of Lemma 1 Because X is not full row rank, we know that I- Px # 0. There exists W such that
W(T - Px) # 0. Applying the first property in Lemma 7 we have
UGW w- + 1 (WPx) - WG L
1 W - L(WPx) - 1 - ((W + + Px),
provided W + WPx.
Hence, not strictly convex, which implics L not strongly convex.
To prove the second property, it suffices to show that g(W) I(W) a(1)Ammn (xx*) | is convex. It is obvious that
g(W) = L(W) al))
a(l) (I - -YIE - Amin ( (x"x) |
Wa, vall2 +
(21)
m
I(W) all) Ei ii=1 [|W vill F| is convex, since 1(:30)) is strongly convex. The Hessian of | - YI Amin (WT W) IWPxxl] pletes the proof.
1 has no negative eigenvalue, thus the second term in 21 is also convex. This
Proof of Lemma 2
Set r rank(X), and u1, be an orthonormal basis of the column space of X.
Then, Px = Ei uau!" Notice that
WN. (0)]lx NN. (0)P Σ a, W (N),,,
By assumption, have
E la,, N:1 WN::(0111 E Σ
a WN. (0),,11 r.
The Markov incquality implics Therefore, we can bound the initial loss value as
2r
F(laa, WN. (0)1l 2
<
8
2
3
Lo L(W.) < (VI(W.), aN WN. - W.) + 1ay W (N) W.1l
IaN W N:1 (0) Wall.
I 3(1laN WN. N.I (0) [
2r
8 + |[W,1 with probability at least 1 - 8/2.
$ B(
B The Exact Statements of the Main Theorems
Other than the quantities in
we define
C4 nNK? Bs (110
-1)2/10"
Co
C5 nNn22 Bs
+ In N,
(22)
[no
-1)2/18
Co
Co = uNn Bs
+ Co In(N,,
(no
2//
where no
2ny No
with c 0. Recall that m
2nx
N3
16

---

Published in Transactions on Machine Learning Research (07 (07/2024)
Theorem Given any 0, and 0 8 1/2, define no N3 and consider the learning rate n nu- There exists a constant C' C(c), such that if
2nz
Mminn C C5.
(23)
then with probability at least å over the random Gaussian initialization, we have
2(1 2) ) DDLN(0).
EDLN(T) & 1 1 1e
n
Thcorem Given any > 0, and 8 1/2, define no There exists a conslant C == C(c), such that if
2 e Be and consider the learning rate n < n/--
Temén C- Cs:
(24)
then with probobility at least 1 - 8 over the random one peak projections and embeddings initialization, we have
1 2
EDIN(() <
1 70
EDLN(O).
Specially, if n1 = 02 =... NN-1 = min(nn,no))) no); then the requirement 24 can be replaced by
C. C.C
(25)
Remark 8 Assume L(ax WN........ W1) llaNWN WiX Y p= and n1 RN-1 Then for
Gaussian initialization, our Theorem 4 leads to Theorem. 4.1 1 in Du & Hu 2019). Similarly, for orthogonal initialization, our Theorem leads to Theorem 4.1 in Hu et al. (220))
Next, we present a version the theorem related to balanced initialization.
Theorem Assume
nN-1 Given any > 0, and 0 < 8 < 1/2, define no consider the learning rale 1l 170- There exists consland C = C(c), such that long
2n
and
n n C2C-Ca
(26)
then with probability at least 8 over special balanced initial, we have
11 (1 2)
EDLN(1) 1 1- 4e
(D)
C Inequalities in Convex Optimization
Convex optimization has been studied for about century. Recall the definitions and basic inequalities for a-strongly convex and B-Lipschitz functions.
Definition 3 A continues differentiable function f said be 3 Lipschitz if the gradient Vf is Lipschilz, that is if for all n,
[V)(() vf(=))| x|1.
f is said a strongly conver if for all x, y, we have
f(y) 2 f(x) + (Vf(x). x) + a 11 - x||
17

---

Published in Transactions on Machine Learning Research (07/2024)
Proposition 1 If is a- strongly conver and f is 3- Lipschitz with respect to mnomm,, then $ B
and
v l =1|² f()) - f(x) - (Vf(z), x) 8
1 x|l
(27)
aB
(V/(x) v/(w), v) a+ 3
|| vl
V - //(i)
(28)
a+
[V/(x) v 2 a - u|l,
(29)
((x) - ((v) & (V/(x), 9) 23
[V V
(30)
Proof of Proposition 1
We only proof the last incquality.
Let = y - (vV(()) -==((V(())
V (x)). Since
convex 3 Lipsssciiz we have
f(=) - f(x) 2 -Vf()),=->)
and
- -()) S (VI()); -)) + _ -
Thus,
- (()) - f(y)
f(x)+
<(V/()),--))+ (V/(y), 1) + -
v11
=(Vf(r), 2B VV(x) Vf(
Before we start to prove Lemma 3 let us first include and prove the following result.
Lemma 8 1. Assume is strongyy convex, a 0. Denote global minimizer of L by W.. Then for any W,
1
L(W.)- - L(W) 2 |VI(W)
(31)
2a
2. Assume VL is B- Lipschitt, then
1
L(W.) - L(W) <
||V((W)
(32)
233
Proof of Lemma g 1. First, know that VL(W.) 0. L is a-strongly convex, which implics the
inequality 27 holds. Thus
L(V) L(W) (VL(W). W)x + ah IV --I g(V).
Minimizing both sides in terms of V gives 31
Now we focus on minimizing g(V). Since g(V) E C² and the global minimizer exits, we have
Vg(V*) VL(W) + W)Px 0,
where 4 is a global minimizer for vV). Thus,
8(V') = 2a
|VV(())
18

---

Published in Transactions on Machine Learning Research (07 (274))
2. Applying proposition to 3- Lipschitz function VL, we obtain
L(W.) L(W)
<(VL(W.), W. - W)x 2B [VL(W) VL(W))
1
23 /L(W)
D Proofs Related to Convergence Region
Proof of Lemma 3 To prove Lemma B(t), and C(t) for all 0,1,
it sulfices to show that the following three properties hold A()),
1. A(t):
L I(W.) S 11-m7 (1- (To-
2. B(t):
maa (W (NN++1(1)) S e (CN
miin (WN++1(tt) e ( (NN- 1
1/2 -
maz (W: R(x)) S E (m-1n1) ,,,
(W(-za(t)|R(x)) 2 e (1-111) 1/,,2is [[ S M N Rmin 11- nh
min
1/2 <isj<<
3. C(t):
20 2BB R
[W((t) W(O0
VONY
Using sinultaneous induction, the proof of Lemina 3 is divided into the following 3 claims.
Claim A())), .... B())) ... BB)) = C(I 1).
Claim C(t) > Bt)), if Amin 2 M(er,e))M2 Bo 228 nN, where C(c1, 02) is a positive constant only depend on C2.
Claim A(I), A(L+ 1), if Umin CB= where C(ci, 62) is posilàve constond only depend C1, C2.
Proof of Claim
As a consequence of Lemma S and Lemma 7 and A(s), S l, we have
[VL(aaWya(d)) (s)(s)) IVL, VL(WPxx))>
<28[L. L(W.)]
(33)
<2B (1 - -m))* B.
From A(O), A(t), B(0), ... B((), we have for any 0 < 1
ØL
ow, (s)
aN [+) (s))l [
2c
[V(awWwa(s))I
(34)
VuN
201
- (1) B.
VAN
19

---

Published in Transactions on Machine Learning Research (07 (07/2024)
Then,
[ + 1) w.(0) - Σ |W:(s 1) Wl
OL
(5)
OW;
F
2
V 28B
- 177)0/22
VTN
8=0
2c1
V 2/B
Σ (1 17/2)²
VTN
8m0
2c
223B
R.
VNNY
This proves C(t + 1).
Proof of Claim 2 Let 6, = W2(1) - W, sis N. Using C(I), we have |6:1|p < R, Si N. Set
61 = 61/ min ea/2
1/2].
It is suffices to show that
[[Nxs(() WN:(()]l - 1,n
(35)
(ta (o)(())))( S
(36)
and
1/2
[[ W (0)l < M/2 No
II Thk
,<isj<<,,
(37)
Tmmin (-1SkS)
because Mmin (A B)= 2 Omin (A) mar B 0 miin (A)
||B|| and mmaz (A + B) < Tmax (A) mmax (B)
||A|]| + |[B]| (e.g. see Theorem 1.3 in Chafai et al. 2009
Case 1. We first prove 377.
For 1 5 < < N, we can write (t,(t) (0) + 5,) (W.(() + 5.).
Expanding the above product, each term has the form:
W W.((++1)(00 oz. W( ...-,....a S2, W W(k-- ())
(38)
where i < ki < ... < k, S j are positions at which perturbation terms or, are laken out. Notice that the convergence region assumptions (14 implies that for any 1 <<isj< N,
1/2
II- 78
1/2
[W)+(00]| S M/2- 9
II K
max(n;,1,
MM No
(39)
Tmmin
WLOG, assume M 2 1. If i 1, then
[0),(00]|=11]] S M No (n;/n/min )2/2
Assume i> 1,j < N, applying inequality 139 as well as the following inequality
1-1+1
Σ
8 x" (1+ - 11, 2 0,
i
20

---

Published in Transactions on Machine Learning Research (07 (2742
obtain that
[Wa(t) (O)I
j-1+1
j j-i+1] 1) 18th [ No)e m (n:-1 ... ny/ /uminm )
s=1
M N (m;-1 . .............. my/nmmn) 112 (12 R- M- No ///mmmm )N 1]
S No (m--1 my/mmmn) 1/2
The last line holds due the following reasons:
there exists absolute constant A1, A2 0 such that
(1 + -) -1 A2xN,
if 2 0, N 2 1, and xN < A1. Since there exists positive constant C(e), which only depends on cı, C2:
such that when
C(),, Bo
Tymin.
220 nn
(40)
g²
we can have as well as
R M. N.M.NO1..
Vurann I A1,
R-+ M. NN /t/////is (mmin) N 1] S A2 M. R. No+1 /umin 61 = (2),
Case 2. The proof of 355 is similar. Set N, save the factor M N from previous calculation, which means
[WN:(tt (N)(
N-#+1
N -i+i1 Σ
Sea/2
R*MM (M n -e/2 (n:
... 12
8
56012(m14
-N- 1/2 R M No Timin) 1]
where the last line is implied by equation 40
Case 3. Similarly, we have
[W)(()) - (x)(0))
Se9/2 R
(M RMM
'N' n (nl ... ......)))))))))))) )
/ ... m2) 1/2 + M No /Tmmm)) 1]
<f ... ...)))) 1/2 " < N 1
This proves B(I).
Proof of Claim
3 The GD
7 implies
(N
(WW(()) 17 aww (6)
aI,
aI, WwN11()-"'8ww (t) (.)).((W())) (wi(t)-) (( aw, (t)
aI,
-WNa(()) -1 -7.aa aN
W W Wo
E(),
21

---

Published in Transactions on Machine Learning Research (07/2024)
where E(t contains all high-order terms (those with 17² higher). Define linear operator
P(tIAA
2 AN WN (0t. (i-
(41)
for any A E R
Now we have
ON WN + = =x>x()))(() n PU]VI((wWxsa()PP) aN E(t).
(42)
Easy to check that P())[-] is a sum of positive semidefinite linear operator.
The following proposition describes the eigenvalues of the linear operator P()H)-
Proposition 2 Let S1, S2 be symmetric matrices. Suppose S UAAU", S2 VAzVT, where U (un, W2, W2,'.", [um]] and V [01, ",.,",,,"" are othogonal malrices, and A = diag(A1, )2, Am)) and A2 diag(u1, M2: -2.-.. .Pa) are diagonal matrices. Then the linear operator L(A) == S,AS, is orthogo- nally diagonalizable, and L(A,)) = Aif where Aifly represent all eigenvalues corresponding to their eigenvectors A.j- = u.uf.
Applying this proposition and the assumption B(t), we obtain the upper bound and lower bound for the maximum and minimum eigenvalues of positive definite operator P(t), respectively,
Amaz (P(t) S x
ma (W, (W))aa()))()) o (WN++1(t)) S
2c
NN
and
N
Amii (P(t)) 2 aN
Σ
0 min (W, (W.11(()) Pmin (W (Ns++((t)
2
N
20z
nN
In conclusion, we have
N
N
Amar P(())
S
c
201 and Amin(P(tt) 2
-202
(43)
NN
nN
With learning rate 7) = 1/2
(1-8)2nX
0< < we have
231 BN
L1+1 - L
+ B
$ (VL, -n((t////) + (VL,)NE(t))
2 -AP())VLI-aaNEEN
LV -1P(O(LL)))) 8
IP00VIIL + F(!)
S Ammin (P(t))
(P(1))
_
2
||L,|| + F(())
N (1 (1-
B
< -
20a
Acr
+22
z"
|| + F().
nN
2
nN
where
F(t) ax 8
B z" - 1P((VVVVL
[nP(()) -x E(t)
We claim that F(t) is small enough, such that
L+11 L
20a N
3 N
1 1 401
|| + F())
1
NN
2 INN
3mg N
B N
(44)
1 - Bol
|V
17
NN
2 NN
2 - E)
6(c) to2)
|V
8
22

---

Published in Transactions on Machine Learning Research (07/2024)
Assuming this claim for the moment, we complete the proof. Combining
331 and 44
have
1141 I S -(-oett 2=(1-E)
#
T(W.) L4 2a
|
which implies
L441 L(W.) (1 -(elto))) (1-c-0(c)t)))) 4E(1 )
(L, - L(W.)),
that is
L I(W.) < (1-e (1-e00(a 6(c tr2) 45 EE) ) (To I(W.)) (1 m7)" (To I(W.)).
Estimate F(!)
Notice that
IF()
$ VL Iaa F())lx + (21dmazl (P | F(t)lx + 1lay F(1)
I + 12.
From 34 we have
AL aw,
20
2011 VL ([((aWNa(t)lll K.
(t)
s
VnN
F
Expanding the product
OI,N WNa(t+1)= (ww((+1)=(WW()-- oWw" (1) (Ww-1(0) - "aWN-1 (1)... ... (Wi()) aw, (t)
OLN
OI,N
each term has the form:
aL A = WNN(k.+1)(0)) oWw." (t) -100 " oWW,..
OL
ØL (1) W (1))
(1) ..... Wk,
where 1 k bo ho N.
As direct consoquence of incquality B(t) and inequality
39 we obtain
M No
| = 1|PXI S aN VuN
201 (nK)*
/Dmin
Recall that E(t) contains all high-order terms (those with x/2 or higher) in the expansion of the product. Thus, E(t) can be expressed as follows:
aL
aL
aL
Σ
(1)()+1)(()) "aw, (1) (W)-WWa,-Deee -1 ow oW 2 1sk Cheem.cksSN
Σ
(I)
(1)
(1)
(k.
W Ws,
23

---

Published in Transactions on Machine Learning Research (07 (07/2024)
Set ç min((e -22 - -e- 22(c0m - /clont , { -
N
Recall the inequality
S (eN).. Thus, have
oN |E(())xx
1
N
N
5-1 M No
201
(1)))*
VON
Viemnn
8=2
1
M NN
M M-NO Tiimi
201
(eN)
V
Ammin
sm2
(45)
1
neKM No-1/ /
22 (neKN)
VON
1- 1-neKM No+11 Tmmin
N
St 1)
to1t1 [VL(aN (if neKM -N++1 /y0t///n /VTminn < E))
NN
N [VL(aNWwa(t)]
- tc
" nn
Using
33
and the upper bound of we know that there exists constant C(c1, e2), such that
Amin 2 C(cr, No
and
2/2M e2420 N VuN
MeKM M NO+1 / Tnmin 5
Vmmin
C"(ci, 62)
2
1 1
Using
45
we have
( N
( N
I 1 E. 40111
||V s (2-0
33-302)
nnxx ny
nn
17
and
I2
3
N2
N2
2
66141
11
VL
8at2
172
| 11
2
n'
n'
N2
6c
640))
-17
VVLIl
N'
Thus, 44 valid.
This proves A(t).
Proof of Lemma
Due to 333
42
43
45
and lemma
we have
N
|R(()]Ix
aN FF(() + n
VI,, ((.)
NN
x
< E(tn) + ty
[Amar( (P(t))
N
N
Aman (Pmn) |VLelx
nn nN
N V
<(C' { max - 1,1 1.1- c -2023)
nN
2 2/2LL L(W.))
(C' -g + max
201 1, 1 c -202])
cbes +301 +300
24

---

Published in Transactions on Machine Learning Research (07 (07/2024)
Due to the fact that L, - L(W)) is non-inereasing in t, and C' is constant only depend c, 02, choose small enough positive eı, 62 and &, which depends on 7, such that
[ T (2 - L(W.)) I (laaNWNa((t) W
3
Proof of Lemma 6 Using Lemma 1 we obtain that for any (0, and < 7/1, can find small
enough positive constant which are only depend on n/m,, and constant C' = C((1, .2) = C² (T,n//) mentioned in Lemma such that
- 81-)2 e +.00 BN
where 0 < 1, as well as
V(t ((t+1) = VL((())))((( R(t,,
where V(t) = a,v (t), 7o
n, and ||((t)lxx ST =T'=+|IV(6 - W-llx
Notice that 6u n/m +āez and n//10= E, where 17o-
2nn +
For the right hand side of inequality 15
we have
C(c1,e2)MP Bo N29 NN
C" C"(r,n/m) Bo N
To show that inequality 15 is equivalent to inequality 17 it suffices show that only depend on n/m/ Notice that
E == 1=1-m/ n/noo =
toe dog +302
and C1, 02 only depend on 7 and n/m, which implies e only depend on T.n/m-
Now, we start to prove the three inequalities in 18
Recall GD for Wt)). Define ((t) (tt) W(t) AN aN WN=(t) (t). Notice that
A(t+1) 1) = - -LW R(t),
and
IA(++ 1)
h (VVL(V (t) - VL(W())) - 2n.(((()) -L(M)))
+ ||(0)) + (211A(0)] + 2n, - vL((()))+))
Let 4, = 2 21) + 27, (t) (LW +T'
Now, we aim find an upper bound for 4. Applying lemma with the assumption 1). nN
N n 2 know that
4 s (61IA(t)l +7) < (t) w.llx + +[[((t) - w.llx).
(46)
Thus
4T's 77 [t w.lly (I]V(t) - w.lly + ([((t) - w-llx) =: Uv..
25

---

Published in Transactions on Machine Learning Research (07 (224))
By incquality 28
IA + 1)I&&
< |I(())) (A()) - VL(W(())
+ V
+UT
= [|A())1 (2n VI((()) - VI(((()))
+ n (V)())))VV(((II)))) UUT
-
aB |A(())
< [|((1 - -21- a B
+ n/ 27-
|VL(V()) - VVL((()) + UST.
a +
Case 1: a+3 < 1/, < 3.
In this case, we have
| 1)
aB
2T-
21% a + B
||((||I +
1/2
IVL(V(()) VL(W()) + UUT
a + 3
a13
21/
< ||(O)| 21% a + B
||A())I + 1/2
(PAAO0 + UST
a + +
S (1 - (2 - 7)3 (1) + UUT
: 9 |1)())I UST
Case 2: <<00<0 7/ S 2
atg-
Similarly, we have
| + 1) < - (2 - a)a)) |4 - UUT (l: U
(47)
In both cases, we have 0 < q < 1.
First of all, since U, S Uo and ||(())lx = O, we obtain that
Uor T-q 1
UoT of (IA1ORR T- - 1-4 1-9
Uor 14r || w.ll
|A(1))
<
<
Applying Lemma
5 for v(t) and W(t,, we obtain [IV(I) w.llx I (1 + +) (IV()) - w.ll and [[W(1) - W.I l3 S 9² [W - W. 12 respectively. Thus,
(((())) I(ax (t))
(VV) & |
2
9
53 (1)) - W.llx ||A(1)lxx
2 [|A(1)1
<3 122 V
14T
+ 7T
|V(00 - WW.1x
1 q
1-9
Generally speaking,
47
implies
|A(1) ST
Σ 1115
==0
26

---

Published in Transactions on Machine Learning Research (07 (274))
We have
|a()))( 14T Σ (q 7-) (1(()) w.ll&
(1-)) II(00) - -wall
$ 22(
Thus, we have
[a) - z min
{
14r
-0,, 2(q + 7+)² [V(0) - w
well
(L) - T(aNWNa
<3 <8|]W()) - wollx |A(t)lxx + 8 ||(())
<B (V
(V min
14r
2(q + 77)) .g//2 min
14r
2(g ++)) |[ w.ll.
1--
1
By triangle inequality as well as I(W(1)) - I(W.) S 4 [V(0) W. 11.1xx we have
I[ay WNa(()) L(W.)I 38(g + 7 [V((0) W.
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, we first establish some spectral properties of the products of random Gaussian matrices. The spectral properties lead to the conclusion that overparameleriiation guarantees that. the random initializa- tion will fall into the convergence region with high probability. Denote by (0, 1) the standard Gaussian distribution, and x the chi square distribution with & degrees of freedom. Let gd-1 = {a Rd || 1} be the unit sphere in Rd
The scaling factor aN Vainz--nn ensures that the networks at initialization preserves the norm of every input in expectation.
Lemma 9 For any R the Gaussian inilialization satisfies
E [laN |==12--
Proof of Lemma
For random matrix E R with i.id N(0, 1) entries and any vector 0 * e E
R the distribution of [LAvII
[ill Xnç- We rewrite
I (0 = ZN ZN- ... Z1,
where Z, W|aa [0)x|] [[)=1a(0)=1??
Then we know that the distribution of random variable Zi 2 and conditional distribution of random variables Z,((Z,,-.,,Zzu ~ x (1 < & N). Thus, Z1, ... Zn, are independent. By law of iterated expectations, we have
E E[I 1| n
27

---

Published in Transactions on Machine Learning Research (07/2024)
Define A1 = -Ei=1 1/nj.
Now, we introduce a new notation ) which means that there exists A: > 0,
such that Ω
1 31
2 A.
q Lemma 10 Consider real random matrix A₁ E R 1=,8"/-1,15 i q with itd ( 1) entries and any vector 0 of IR... Define (1 E}= 1 and nmin = minggjggng ny. Then my
c²
P(1IA ... / e' m.) S exp
=: =:(le),Ve>> 0.
(48)
8A1(g)
When 0 <cs 2, (q) - c/(1 we have
A(I ... 1| /|||| < E (.....n)) mg) S exp 36 (6
= f2(c).
(49)
Hence, for any x E Snh-1 with probubility at least e -(a we have
0\/ (m ............................... n1g - ||Ag ..I.-l S ( (n1...mmp ) ,.)) when << C2 31m,, Ag(2) /2/ (12
Proof of Lemma 10
For random matrix A, E Ru with i.d N(0,, 1) entries and any vector 0 4 v E ||A, is distributed as x We rewrite [|
R the random variable
I| A1 ||0|| Z Zn Zi,
where Z, ||| / Recall the moments of Z X
We have Z1 x². Zí ZZ ... ZZ-1) X2y (1 < i $g).
E EIZA| 2 2 m +
m
KA
r 2
2
Now, we aim to find the Chernoff lype bound. Case 1: We define ratio of Gamma function
R(x,)) T(x + X)
I(x) x 0, 0.
In Jameson 2013
we have
R(x, s( s \) 2 0, O.
(50)
Fixed c <> 0, for any x > 0 we have
P(Zz... Z1 e ...ng)
< P((Zz ... -ziA > exe(m ... -nn)²)
Se se-xe(n ... ..ng) "L[(Z, ... -1
>c(nn
(Markov inequality)
= =exp( (opl->(cs) A(c + In(ni....n.)
... n1)))
II ==1
2d R(n5/2,A)
(Law of total expectation)
9
<exp(-A(e In(n ............ ..)) + 1n +
Σ
Aln n2
+ (Inequally
50
2
j=1
=expl- do
In(1 +
201
21
}
n2j
- <exp( -
do + 21²
/=1 n
28

---

Published in Transactions on Machine Learning Research (07 (07/2024)
Define constant (1 Eÿ= n.. Set X 4Ai(o) we obtain (48p.
Case 2: Let Rmin = Ri--
P(Zg.-. 71 < "n ..
(.)).))))) mz) S P((Zg ... 71) > (mn)).))))) s exp(M<c- (1(l--n(nn ... In(nn....npp ny)) ) + qd 1n Σ
9
In R nj 2)}.
Define
9
S(A) X(e In(n: ..)) + 22ln2+
Σ j=1
In 18( R2j
A)
mon
< X S 0.
2
2
Notice that f(0) 0. Define digamma function,
['(x)
(x) = dz
(T))
T(x)
Qi ct al. 20066 proved the following sharp incquality of digamma function,
In(x } =
1
(xx In( + +
0,
x
x
where y is the Kaseer-Mascheroni constant, and 7 ~ 0.561459. Thus,
f(A)=
Σ
In n2
20
12 +
+
c+
In
1+
Σ
q 1
2
nq/2
n₂/2 +
X
Since In(1 + 2) is concave, we have
In(1 + 2 [-1/2,0].
(--12,000)
If
Dmin
<A < 0, then
1
( f(0) - L (x)ddz
ScA + /
1n(1 + x+ 1/2
Σ
dr
ng/2
n n1/2 +
j=1
A 1/2
= Σ
Aln(1 +
+ (n,/2 12 1/2)lnl
n2/2 + 1/2 - In(1 + n,/2'
ng/2
1=1
S + Σ
(1 - ln + ng//2
1=1
< cA 4lm(2) (g).
Assume 0 0<c5 3l Let A 12 2, and X AAi(a)
Since Dmnn Ai(4) 2 1, we have X 2 -nmin /.
Assume A1(g) < // 21.
Thus
c² f(X) < (g) +4nn
Ai(9) + 7/ S 36 36
e²
AAi(g)
Thus, we obtain
49
Lemma 11 There erists a positive constant C(c1, c2) which only depends on C22 such that if n S C2), then for any fized 1 < <
i N, with probability at least - exp { -
A. we have
1
Tmax ( (w::(0)) _ E (ni-174-.. ... 1) 1/2
and
Mmin (ain((O))) 2 - 11 1//2
29

---

Published in Transactions on Machine Learning Research (07 2024)
Proof of Lemma 11
Let A= (0). We know that
Maa (A)
||A||
sup
||Ab|]2
wES"N
and
Omin (A)
inf vES"N
||All12-
Applying lemma 10. we know that with probability at least 1 - exp {-2 37 }.
|laaal /0lll/////ll2 E 2.
where P = (1;-1 RN -N
Set Φ = min ---e----1- (e - ((e_)_=
Take a genet No for Suw-1 with size ( S (3/6)aM.
Notice that with this size we can actually cover the unit ball, not only the unit sphere.
Thus, with probability at least 1 1 [&& {-2 (2,) } for all No simultaneously we have
||ull / [|ull2 [e-02/2 P.ppP,e p/ Pl. 02/2
Fixed S"x=1, there exists No such that ||u 1112 S Φ. WLOG, we assume 1 - |ullp S We obtain
||lll| S ||lll IIA(u 1)l1 S e p & |A|]
Taking supereme over ||u||| = 1, we obtain
max (A) =|A=] S 2a12 P < P.
For the lower bound, we have
|Aull2 2 ||Aull2 - [|A(u r))l2 2 -cx/2 |||||| -1al| 2 (1 (1- 1)-))--0/+ -0e
P e2
Taking the infimum over || get.
T Omin (A) 2 o2
The conclusions hold with probability at least
- Wolexp { -52
(1
1
21 - exp(nn ln330)) exp -S2
A
21 eepexp exp { {
1
A
since nx S 02)
Lemma 12 There erists a posilive constand C(c1, 02) which only depends on C1,02, such that if rank(X)Ai S C(c1,02), then for any fixed S < N, with probability at least expl St (2)) we have
Fmax (O)) < E (minz .n;)
and
Miin (W)x(0)(R(()) 2 20 .,)))) 1/2
30

---

Published in Transactions on Machine Learning Research (07/2024)
The proof is similar to that of previous lemma. The only difference is that now consider the @-net to cover the unit sphere in R(X) n nu,", with dim R(X) n R rank X), where ((X) represents the column space of X.
Proof of Lemma 12
* 3y Lemma 13 Set C' = Rmax Saeee//mmin Rmmin < 0C, 0 = 1/2. Assume (11/A1) A satisfies
where 0 < k < 1 is constant and
1 S min (lm(6)) (ln(5
A In(C)= S min [ln(6In(()e/A)
A In(228) S k/5.
Given 1 <iij < N, with probability least. 2e -k((5))) = =1 - we have
[W5,(00|| < M&VNN (m-... nnj- max
where Mg is positive constant that only depends on k.
Proof of Lemma 13 WLOG, assume 74-1 < nz. Let A = (): From lemma 10 we know that fixed
V E S with probability at least - e (((//Ai we have ||uull I 4/3(n, (.. my)
Take small constant 5lm(6)))mm-1 2 5lm Let u1 Un.. be an orthonormal basis for R Partition the index set f1,2, Un,_.) = S1 U S2 .... U S/xze/c] where [S|] [en,-1/N20 for each
ky20
< < [N2*/c].
The following discussion is similar to the proof of lemma 11 hence omit some details. For each 1, taking 1/2- net Mg for the set Vs, {o 5mh-1-1;e span(ey; Si]}, get
||Au|l2 S 4(m ... ny) 1/22,00 Vs..
with probability at least
- Wile k/A1 2 21 expf - + (cn-1/N + 1) 21 1 1-11--3k/6a) 3k/((5)))
since A
k:
[ Therefore, for any a E R2 1, we can write it as the sum v= = Σ, ait, where ag E IR and UI E Vs, for each l.
We also know that ||u112 E121ee /arl2. Then we have
|Aull2 S
Σ layl Alulll2 S .......0 ((m..--n))12
[N28 /cl Σ la s (n (n....n,)) ....,,) 11012-
Thus,
|A|| & MN M (n- (n
Notice that when See e, A < 5 5lm(51n(6Gc/A)
S C7()) and when C> e, we have
k
k II((C
A In & min
51n(51n(6)e/k)) k/5 S
CC/k)
The success probability is at least
1 - 22 /cl le" 3k/((5)))
5ln(6) ())
21 exp In
1n((N2)) 1 3k/((51)) -3k/(11)))
k
2 - 2e R/(5511)
since
b A 5 5ln (5 (6)) C/k)
and A In(N29) S k/5.
31

---

Published in Transactions on Machine Learning Research (07/2024)
Proof of Theorem 4
The requirement size {n1, (2, ,NN11, N) in 23 makes sure that lemma
11
12
13
2
and
8
hold.
WLOG, set c/6, C2 c/3, M 2M&VCo, Bu Bs, and
(1-s)2ny <2egN then with probability
least
2 ((1AA)) 6/2 2 8, since A - C(c)
min
In In(1/5)
the random initialization satisfies the initialization assumption 14 and the overparameterizationn assumption
15
Applying Lemma 3 we complete the proof.
F
Orthogonal Initialization Fall into the Convergence Region
There are some basic facts for random projections and embeddings. Most of the following properties can be
found in Eaton (189))
Proposition 3
1. A is random embedding if and only if A is a random projection.
2. If A is square matriz, then random projection, random embedding and random orthogomal matrix are equivalent.
The uniform distribution on the group is a left and right invariant probability measure, that is, if is random orthogonal matriz, then A, A, are all random orthogonal matrie, where is a non-random orthogonal malris.
4- Assume X a Q6g S n) random matric whose entries are i.i.d. (O,, random variahles. Then X(Xxx)-1/2 is random embedding, since A = lg and the distribution of A is lest invariand, which means that A and UA have the same distribution, where U is a non-rundom orthogonal matriz.
5. If A is uniform distribution over orthogonal group of order and A is partitioned as A A2), where A₁ is n and Ag is n x (n q), then AT and A7 are both random orthogonal matriz.
6. The columns of uniform distribution over orthogonal group of order n, and
1.. .Ea)
VEf + E + E
have the same distribution, where E., are ii.dd N(0,1) random voriables.
7. Assume A Auxp: n I p is random orthogonal projection. For any E S ||Aull and 51/15=1150 89) are both following beta distribution with a = n/2, B = (p (pnn)/2 n2) where : Snn are i.i.d. N(0,1) random variables.
E /)
Remark There are several ways to construct random matriz A (aij)qxx: S n, which is uniformly distributed over rectangular matrices with AAT 2² Lgg c > 0. Let O, be uniformly distributed over real orthogonal group of order n, and On is partitioned as On (Af Ab)" where Ai n. Assume X (zig (xa) and Tij independent standard normal random variables. Then A, cA1, and c(XXT)-1/23 have the same distribution.
Lemma 14 For any x E Rn, the one peak random projections and embedding initiation satisfies
Wo (0)
||
32

---

Published in Transactions on Machine Learning Research (07 (224))
Proof of Lemma 14 Let D (0)000mmmmm ng. Then D is embedding matrix. Thus, ||Dx||
|| Let A; = Wip+1(0) (0)/ 7pp+p1 ... 74-1, where i 12 p 1, and Ap =
Set B; ||,,D=|1/ || Dzl D=:1:: i2p+1. Then, B; follows beta distribution B2 (n:-1 mz)/2) given B - Bp+1. 2 p 1. If m then B, .. Bp+1) 1, a.s.
If B ~ B(a,b) then the expectation is given by the following equation,
EB a a+b
Thus, by law of total expectation, we have
nN E Waa IANND EB, BN-1 ... Bp+1 D =
AN np
||0||
np
This completes the proof.
Next, we introduce sub-Gaussias random variables, associated with bounds on how random variables deviate their expected value.
Definition 4 A random variable with finite mean μ = EX sub- Gaussian if there is a positive number a such that:
12202) 2
Elexp(A(X - - S exp
for all X
Such constant o² is called a proxy variance, and say that X is oä-sub-Gaussian and we write X SG(o?).
Example 3 Normal distribulion N(, of course is o² sub- Sab-Ganssian.
For beta distribution, Elder 2016) showed that B(a, b) Maa4442 Sub-Gaussian and later, Marchal & Arbel 2017) concluded K[+b+11) sub Gaussian.
The Hoeffding bound for random variable X with mean j and sub Gaussian parameter o is given by,
12
P|X- - 11 2 f S eexp
vt 2 0.
(51)
26
Simply applying the Chernoff bound for B(a, b), we obtain the following lemma.
Lemma 15 Assume random variable B distributed beta distribution B(a,b) with two positive shape pa- ramelers a and b. Then
PP( B
a b
2 v) S 2exp { 2(a + b)y² J. 0.
Hence,
IP
B
a
< 8 a a
a
2 1 - expl (l-esp(-((ee((tt0))
+ b
where 2(-) only depend
For the upper tail, we can obtain a better bound,
TP
B > (1 (1+6) a a < exp f-p (s--- In(e 1))a).
(52)
We only need to prove the third inequality. Assume random variable B(a, b). Set = +)+ I < 1, 0, and r > 0.
Proof of Lemma 15
We going to estimate the Chernoff bound for B, which is
P(B v) & tro-laee -.0(0)
-r(0)
33

---

Published in Transactions on Machine Learning Research (07 (07/2024)
The moment generating function of B is given by
20 aaa + 1) (a k pk
((a+1)...
1) nk
Ee =1+
0.
o(v + 1) ... (E + k - 1) k!
y
Recall that the Maclaurin series of (1 - rl-r/ over (-U, v), is given by equation
a(a + 1).... ... (a + h - 1) rk
(1 (1-r/0)-"=11
k!
k=1
Thus,
((v) = In 2 + a allnn1n - -r/u).
Set r - a/v E v). We obtain
P(B 2 y) < expp-(1y (vy a a =: exp(-vy g(a/[ev))), (1 t) S <
where g(z) 1 + x x= a/ E (0,1/( 1/ + t)]. Notice that g(1) = 0 and g(xx) In(x) < 0 over
x E (0, 1).
We know that
g(x) 2 g(1((1 + 1) t (1 +t)
1+1 11> O.
Thus,
t In +
exp f-(t In(1 +))a) y== (1 (1+t)= a <1
P(B 2) S exp
uy
t+1
Set (1 + o48
We obtain the inequality 52
043.
Remark 10 It is trivial to check
I[, (0)ll (n.4++1 ... n2) isiiisiss ssp
(O)][ = (ni-174 ... .. 11-1) 1/2, +Isisis
(0)] < (ma7441 -.. (,)
1/2
Amaa
(1o8441 ... nÿ-1 " (1,1) (1
Ammnn
Remark 11 As a special case, n1 n2 (n4-174- -...1n----N.-.. 112-1) (N-i+1)/2
1N-1 n, know that [0)]
Lemma 16 Assume np/ min(n1, nN-1) S Co co. Set 0. Let C(e) represent the constont depend only on e. m/m/Co 2 C(E)nN, then with probabilily al. least - -t(n:/oo)
6 man (w..(0) < (1 5) i
1/2 12 2
(W Omin (W N: (0) 2 (1 - " 12.
1/2
Similarly, if nNN1 2 C(s)rank(X)) then with probability at least 1 - -((NN11/C)
Tmaz (W (0) (x())) < (1 + e) ... (==+
mmin ()) (1 (min......))) (t
34

---

Published in Transactions on Machine Learning Research (07 (07/2024)
1/ Proof of Lemma 16 Let D (NN-1"N-2" //p) N:p++ (0) and
A, = (mp7p-11... ..) 12 pai (0). Assume v E Sm Easy to see that A, is a product of random orthogonal projections and D random emneediing.
Let e1 (1,0,0, ,0)" R"r. There exists orthogonal matrix T such that TDv e1, ||eill2 = || ||e||2 1.
Since random orthogonal projections are right invariant, we have
Delll 2 y) EE E
(1lAAT7)))))))) p)] =E [F(Iia( D)] -Pe(1 2 v)-
This proves that ||,,Del1 and ||A ll2 have the same distribution.
Claim: If v & 0, then ||A, ||u112 = ( ... n.. ... -..-NN11 W
W. 2112 ||el12 follows beta distribu-
tion Bm 2, (Mp - 1)2)
Define B, e 1b2 B, |A,01 12 ||A 12g i -p-1pp-1
Then Bp ~ 1/2 (mp Up 1/2), Bp- Bp B(1p-2 (11p22/2,(pp11111 npp mn-2))22) 2)/2), ... B,I(Bp, BB+1)
Bfn--1/2, (m: - -24-))2)..
If n441 = T4;, we know that (B, BB+1) = a.s. If B(a, b), then the moments are given by the following equations,
a+1 a k
EB
a a+b and EB atba+b+1 a
By law of total expectation, we have
EB,B,+1 Bp
fi-1
pp
fi-1 n2
n. 1,+1
np
as well
B(B,B4+1 ..,B,** 14-1/2 n2 1/2
14-1/2 2 k
Rp/2 mp/2 +
Rp/2+k
Notice that all integer moments of B,B ... Bp match those of B(n;-1/2, (np (Mp-n1;11/22) We can verify that
beta distribution satisfies Carleman's condition, which implies that B, B,B111'. ... Bp ~ B(n;-1 (mp-n;-1)/2
Thus, | ||]| ~ B(n--1/2 (n, - - (2=1))/2) which proves the claim.
With probability at least expl (-(mm(/ we have
(1 - 6) n111 < A1ADr I (1 + E)² 24-
||llll2 =1
np
np
Using the é-net net technique which has already been used to prove lemma
11
we know that
1/2
ni-1
Umin (AD) 2 (1 -5) E)
np
and
1/2
Omar (AD) S (1 +
14--1
Rpp
with probability least 1 exp(nx In ((3/v(e))) -xp(- 2 1- C(e)nN, for 2 p. Hence, with probability at least 1 - - /Co), have
since n₂/Co 2
Tmin (W (0) 2 (1 - 1N2
and
Oman (N. (0) (1 4)+ (m--1 .........---ii 1 1/2
The other part of the proof similar to that of lemma 12 so we omit it.
35

---

Published in Transactions on Machine Learning Research (07 (07/2024)
Proof of Theorem 5 Set 0, e c/6,c2 c/3. In lemma 16
pick
0,
such that
Ite ea/ and 1 - 02/2 Set M 2/Cu, 0 =0 0, Bo B8, and ")
(1-c)2nx
The requirement on size ( 12, 1, N} in (24] make sure that the remark and Jemma 3 all hold.
10 lerma
16 lemma
Notice that even though we need the conclusions in lemma 16 simultancously hold for 2 s i S p. p+15
S N, it suffices apply lemma 16 over E I and j E J, such that {ng E 1} and {ny:j I} both have distinct values. Since [T] N and [ N, with probability at least
1 - 2Ne R(PminnCo)) - 5/2 1-
the one peak random orthogonal projections and embeddings initialization satisfies the initialization assump- tion (14) and the overparamcterization assumption (15). Under assumption n1 112
replace lemma T6 Thus, with probability at least 1 - 6/2 2 1 5, 14 holds. Applying lemma and complete the proof.
nN-1, we can remark 11
Proof of Theorem
Let Wx(() = VnUN VV..
N Wi(0) = VnU, s & N 1,, and
(0) = |nU,
Now, we want to verify (14). By simply calculation, we have
N 1, - man (W:-1:1 R(x)) man (W-1n1 R(x)) 16-12 SisN,
Oman [WN:+11 (0)) = minn (W WN (0)) (n
[ [00] = n1 <issj<ijs4
Notice that for any 1 p
| (0)=12
Uw,
VN
NN
where = UN, V/ 0 ||0||| = |x'|l 11 Since the distribution of UN [n, V is right invariant under multiplying orthogonal matrices, we have
UN| 2 ||x1|/ ~ B Fl n
ny
2
Thus,
[a: -11=11
Applying lemma
2 have
2 (X) + || llw.1lk)
Lo L(W.) $
with probability at least 1 1-8/2. Applying Lemma 3 with > 0, cı c/6. c/3, 0= complete the proof.
Proof of Theorem proof.
Theorem is a special case Theorem and Theorem 5 Hence, we omit the
Proof of Theorem 2 In Theorem 5 and 6 we proved that for given constant C1 > 0 and 0 <
0,0/2 < 1/2 as well as learning rate there exists constant C = (()),02) such that all three kinds of random initializations will fall into the convergence region defined in Section 4.1 with probability at least 1-8.
This implics that with probability at least 8, we obtain complete the proof.
16 by Lemma
Applying Lemma 6
we
36

---

Published in Transactions on Machine Learning Research (07 (07/2024)
G Numerical Experiments
We will discuss some empirical evidence to support the main results in Section We aim to show how the trajectories of the non-convex deep linear neural networks are related to a convex optimization problem for GD under different initialization schemes. Consider the following procedures for plots of the logarithm of loss as a function number of iterations:
a) We choose X E I 128x 1000 and W. E 10x and set Y = =W.X + where the entries in X, W. and e are drawn iid. from 1).
b) We consider the loss function W - YI
c) For the given linear networks, apply the Gaussian initialization and the one peak random or- thogonal projections and embeddings initialization, which are denoted as (O))), 1 S j S N = 3.
d) For the convex optimization problem we set the initialization to be ( aN W (0) Wi (0).
e) We set the learning rate = AN X- and 7- my for the deep linear neural networks and the
convex optimization problem, respectively.
f) We draw the loss function through 25 iterations.
Figure 1 compare the trajectories of the logarithm of loss for gradient descent in deep linear networks and the corresponding convex optimization problem. The left panel shows the comparison with Gaussian initial- ization, while the right panel shows the comparison with orthogonal initialization, both without averaging.
Recall that the main theorems in Section g) require Mmin 2 max (No, nN); and thus, in the simulation, we require min Z 128. Thus, for the top panels, the minimal width of the hidden layers Temin 128 small, and the trajectories of loss for deep linear networks exhibit non-monotonic behavior, with the loss increasing in some iterations. However, this does not contradict the main theorems in Section 3. because the minimal width of the hidden layers is insufficient.
As the minimal width of the hidden layers increases, the trajectories of loss for deep linear networks become increasingly similar to those of the corresponding convex optimization problem. This suggests that increasing the minimal width of the hidden layers helps to stabilize the optimization process and makes more closely resemble the convex counterpart, which is consistent with Theorem
The choice of initialization scheme, whether Gaussian orthogonal, does not significantly impact the overall convergence bchavior and the relationship between the trajectories of deep lincar networks and the convex optimization problem, when the minimal width of the hidden layers large enough.
37

---

Published in Transactions on Machine Learning Research (07 (07/202) /204)
DLN
DLN Convex
log (Loss)
101
log (Loss)
10
10a
10a
10 nepochs
15
20
25
10
15
20
25
nepochs
DLN Convex
DLN
log (Loss)
10a
log (Loss)
100
10a
nepochs
20
25
nepochs
DLN
Convex
DLN Convex
log (Loss)
10a-
log (Loss)
105-
104
10a
nepochs
25
nepochs
Figure Plot of logarithu of loss as a function of number of iterations with n1 n22 -g 128 (Top), 200 (Middle), 2000 (Bottom) for Gaussian initialization (left panel) and ni n2 ny 128 (Top), 200 (Middle), 5000 (Bottom) for Orthogonal initialization (right panel), respectively.
38


Reviews:
[{"review_id": "tP9JF0AJxe", "reviewer": "Reviewer_BJ3T", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strength\n1. **Novel Analysis of GD Trajectory**: It appears that this paper offers the first comprehensive comparison of gradient descent (GD) trajectories in deep linear networks with those of simplified convex problems.\n2. **Rigorous and Clear Proof Framework**: The proof is robust, and the framework is well-structured. It first establishes sufficient conditions for convergence by characterizing the convergence region, then demonstrates how various initializations fall into this region with high probability as network width increases.\n\n## Weakness\nMy main concern is whether the insights and techniques derived in this paper can carry over to deep nonlinear networks. In practice, deep linear networks are rarely used. One major goal of studying deep linear networks is to provide insights for understanding non-linear networks.\n1. **Difference in Landscape**: Recent research demonstrated that the loss landscapes of non-linear networks differ significantly from those of linear networks. For instance, spurious local minima commonly occur in deep non-linear networks [R1, R2], whereas deep linear networks do not exhibit spurious local minima. This discrepancy suggests that the training dynamics of non-linear networks are unlikely to closely resemble those of linear networks.\n2. **Recent advances on NTK**: Recent analyses based on the Neural Tangent Kernel (NTK) have characterized the training dynamics of sufficiently wide non-linear networks. It remains unclear how the analysis of deep linear networks can provide deeper insights into the training dynamics of non-linear networks.\n\n[R1] Tian Ding, Dawei Li, and Ruoyu Sun. \"Suboptimal local minima exist for wide neural networks with smooth activations.\" Mathematics of Operations Research 47.4 (2022): 2784-2814.\n\n[R2] Fengxiang He, Bohan Wang, and Dacheng Tao. \"Piecewise linear activations substantially shape the loss surfaces of neural networks.\" International Conference on Learning Representations. 2019.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents an analysis of gradient descent (GD) in deep linear networks and provides two new theoretical results:\n1. **Convergence of Gradient Descent**: The authors demonstrate that, for deep linear networks with a strongly convex loss function and sufficient width, GD with appropriate initialization converges linearly with high probability. This result extends previous work that primarily focused on $l_2$ loss.\n2. **Trajectory Approximation**: For sufficiently wide deep linear networks, the trajectory of gradient descent closely resembles that of a simplified convex problem.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "No", "audience_explanation": "", "requested_changes": "To enhance the practical impact of the results, the authors may want to justify how the techniques and/or insights can be extended to deep nonlinear networks (not just simply claiming ``can potentially extend to more general deep neural network architectures''.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Tu7tZeByd9", "reviewer": "Reviewer_dezf", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n1. The paper presents a thorough convergence analysis and trajectory comparison of the gradient descent method for overparameterized deep linear neural networks.\n2. The paper highlights the importance of appropriate initialization and sufficient width of hidden layers for achieving close alignment between the trajectories of gradient descent and the convex optimization problem.\n\nWeaknesses: \n1.  The paper primarily focuses on overparameterized deep linear neural networks. While this provides valuable insights into this specific domain, the findings may not directly extend to more general deep neural network architectures.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper contributes to the understanding of the efficiency of gradient descent (GD) in training deep neural networks. It focuses on overparameterized deep linear neural networks and compares the GD trajectory with that of the corresponding convex optimization problem. The results demonstrate a close match between the two trajectories, highlighting the effectiveness of GD in practice. The study addresses a significant theoretical problem in machine learning and sheds light on why GD methods are efficient for practical applications. Additionally, the paper reveals that the GD trajectory for overparameterized deep linear networks avoids bad saddle points, further enhancing its effectiveness.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Is it possible to achieve similar results using stochastic gradient descent (SGD)? What are the main difficulties?\n\n2. What will happen when the width is fixed but the depth of the linear neural network is sufficiently large? Additionally, what happens when both the width and depth of the network vary?\n\n3. The assumption $n_{min} \\ge \\max(n_0, n_N)$ is kind of stringent, leading to results that may not be applicable to high-dimensional data. Any remarks on this limitation?", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "yW1aVsyhx9", "reviewer": "Reviewer_H61G", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Providing a detailed proof sketch and clearly citing the relevant results when establishing theoretical results are among the strengths of the paper. This paper is overall well-written. \n\n-----------------------\n\nWeaknesses: \n\n$l$ is not defined in (1). Do you consider all convex losses or specific loss functions?\n\nThe strong convexity and smoothness assumptions are stated later on page 3. This creates confusion as the reader does not know the problem setup clearly when reading (1). \n\n-----------------------\n\nOne page 3, the authors claimed \"Notice that $W_*$ might not be unique, but $W_* P_X$ is unique.\" This is not really clear. Please provide the proof. \n\n-----------------------\n\nThe claim that GD in (7) is equivalent to that of (9) in Remark 1 is unclear specially since $\\nabla L$ is not necessarily a homogeneous function.\n\n-----------------------\n\nTo help the readers and improve the presentation of the paper, the authors are encouraged to elaborate on the definitions of quantities in Eqs (10) and (11). In particular, what each expression in Eq. (11) means?\n\n-----------------------\n\nThe sufficient overparameterizations in Theorem 1 (both parts 1 and 2) are not clear. The LHS and RHS of the inequalities depend on   $n_{\\min}$. In particular, the RHS depends on $n_{\\min}$ through $C_0$ which is an upper bound on the ratio $\\frac{n_{\\max}}{n_{\\min}}$. \n\nThe same issue holds for Theorem 2.\n\n-----------------------\n\n\nThe term $q+\\tau$  in (12c) can be larger than 1. Then, the exponential growth with $t$ will not support the claim that is stated just above Theorem 2 and introduction regarding the closeness of trajectories.\n\nBased on the arguments in Corollary 3, the authors adjust $\\tau$ as they wish. But then what is the cost of scaling down $\\tau$ in terms of convergence rate and/or the required assumptions?\n\n-----------------------\n\nThe numerical results in Appendix G hold under different learning rates for the deep linear neural networks and convex optimization problem, which are not consistent with theoretical results. It is unclear the role of learning rates on the claims regarding closeness of trajectories.\n\n-----------------------\n\n\n\nThe constant learning rate significantly limits the trajectory of optimization. In practice, time-varying and adaptive  learning rates are quite popular. The reviewer is wondering  why the authors focused only on fixed learning rates for example in all GD updates?\n\n-----------------------\n\nOn page 2: \"unless the width is almost linear.\":  please clarify linear in what in \"unless the width is almost linear\"", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors have analyzed the set of initializations which give rise to linear convergence of gradient descent (GD). Then they obtain the minimum width that is sufficient for GD with random initialization to converge with high probability.\n\nThe authors claim that the most significant contribution and novelty of this work is to obtain trajectory comparison results and show that the trajectories of gradient descent for such networks can be made arbitrarily close to those of the original convex optimization problem.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see weaknesses and address the raised concerns.", "broader_impact_concerns": "This is a theoretical work. There is no such concern.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This is a borderline paper for which the reviewers had negative opinions about its relevance (see my comments in the Audience section). However, the results provide some insights about over-parametrization and the claims are supported by rigorous proofs. Hence, the quality of the paper does not fall below the acceptance bar of TMLR according to [its acceptance criteria](https://jmlr.org/tmlr/acceptance-criteria.html). I (weakly) recommend acceptance.

On the other hand, the contributions of this work may not be sufficient to receive any special _certifications_.
Decision: Accept (poster)