On the Global Convergence  of Training Deep Linear ResNets
Authors: Difan Zou
Philip M. Long
Quanquan Gu
Venue:  (2020)

Abstract: We study the convergence of gradient descent (GD) and stochastic gradient descent (SGD) for training $L$-hidden-layer linear residual networks (ResNets). We prove that for training deep residual networks with certain linear transformations at input and output layers, which are fixed throughout training, both GD and SGD with zero initialization on all hidden weights can converge to the global minimum of the training loss. Moreover, when specializing to appropriate Gaussian random linear transformations, GD and SGD provably optimize wide enough deep linear ResNets. Compared with the global convergence result of GD for training standard deep linear networks \citep{du2019width}, our condition on the neural network width is sharper by a factor of $O(\kappa L)$, where $\kappa$ denotes the condition number of the covariance matrix of the training data. We further propose a modified identity input and output transformations, and show that a $(d+k)$-wide neural network is sufficient to guarantee the global convergence of GD/SGD, where $d,k$ are the input and output dimensions respectively.

Published as a conference paper at ICLR 2020
ON THE GLOBAL CONVERGENCE OF TRAIN- ING DEEP LINEAR RESNETS
Difan Zou
Philip M. Long Google
Department of Computer Science University of California, Los Angeles mnowzouccs ucla. edu
plong@google.com com
Quanquan Gu
Department of Computer Science University of California, Los Angeles qguêce uul eddu
ABSTRACT
We study the convergence of gradient descent (GD) and stochastic gradient de- scent (SGD) for training L-hidden-layer linear residual networks (ResNets). We prove that for training deep residual networks with certain linear transformations at input and output layers, which are fixed throughout training. both GD and SGD with zero initialization on all hidden weights can converge to the global minimum of the training loss. Moreover, when specializing to appropriate Gaussian random linear transformations, GD and SGD provably optimize wide enough deep linear ResNets. Compared with the global convergence result of GD for training stan- dard deep linear networks (Du & Hu, 2019), condition the neural network width is sharper by a factor of O(RL), where x denotes the condition number the covariance matrix of the training data. We further propose modified identity input and output transformations, and show that a (d + -)diide neural network is sufficient guarantee the global convergence of GD/SGD, where d, k are the input and output dimensions respectively.
INTRODUCTION
Despite the remarkable power of deep neural networks (DNNs) trained using stochastic gradient descent (SGD) in many machine learning applications, theoretical understanding of the properties of this algorithm, or even plain gradient descent (GD), remains limited. Many key properties of the learning process for such systems are also present in the idealized case of deep linear networks. For example, (a) the objective function is not convex; (b) errors back back- propagattt,,;; and (c) there is potential for exploding and vanishing gradients. In addition enabling study of systems with these properties in a relatively simple setting, analysis of deep linear networks also facilitates the scientific under- standing of deep learning because using linear networks can control for the effect of architecture choices on the expressiveness of networks (Arora et al., 2018; Du & Hu, 2019). For these reasons, deep linear networks have received extensive attention in recent years.
One important line of theoretical investigation of deep linear networks concerns optimization land- scape analysis (Kawaguchi. 2016; Hardt & Ma, 2016; Freeman & Bruna, 2016; Lu & Kawaguchi, 2017: Yun et al., 2018; Zhou & Liang, 2018), where major findings include that any critical point of deep linear network with square loss function either global minimum or a saddle point, and identifying conditions on the weight matrices that exclude saddle points. Beyond landscape analy- sis, another research direction aims to establish convergence guarantees for optimization algorithms (e.g. GD, SGD) for training deep linear networks. Arora et al. (2018) studied the trajectory of gra- dient flow and showed that depth can help accelerate the optimization of deep linear networks. Ji & Telgarsky (2019); Gunasekar et al. (2018) investigated the implicit bias of GD for training deep linear networks and deep linear convolutional networks respectively. More recently, Bartlett et al. (2019); Arora et al. (2019) (a); Shamir (2018); Du & Hu (2019) analyzed the optimization trajectory of

---

Published as a conference paper at ICLR 2020
GD for training deep linear networks and proved global convergence rates under certain assumptions on the training data, initialization, and neural network structure.
Inspired by the great empirical success of residual networks (ResNets), Hardt & Ma (2016) con- sidered identity parameterizations in deep linear networks, i.c. parameterizing each layer's 's weight matrix as I + W, which leads to the so-called deep linear ResNets. In particular, Hardt & Ma (2016) established the existence of small norm solutions for deep residual networks with sufficiently large depth L, and proved that there are no critical points other than the global minimum when the maxi- mum spectral norm among all weight matrices is smaller than O)) Motivated by this intriguing finding, Bartlett et al. (2019) studied the convergence rate of GD for training deep linear networks with identity initialization, which is equivalent to zero initialization in deep linear ResNets. They assumed whitened data and showed that GD can converge to the global minimum if (i) the training loss at the initialization is very close to optimal or (ii) the regression matrix T is symmetric and positive definite. (In fact, they proved that, when & is symmetric and has negative eigenvalues, GD for linear ResNets with zero-initialization does not converge.) Arora et al. (2019a) showed that GD converges under substantially weaker conditions, which can be satisfied by random initialization schemes. The convergence theory of stochastic gradient descent for training deep linear ResNets is largely missing, it remains unclear under which conditions SGD can be guaranteed to find the global minimum.
In this paper, we establish the global convergence of both GD and SGD for training deep linear ResNets without any condition on the training data. More specifically, we consider the training of L-hidden-layer deep linear ResNets with fixed linear transformations at input and output layers. We prove that under certain conditions on the input and output linear transformations, GD and SGD can converge to the global minimum of the training loss function. Moreover, when specializing to appro- priate Gaussian random linear transformations, we show that, as long as the neural network is wide enough, both GD and SGD with zero initialization on all hidden weights can find the global mini- mum. There are two main ingredients of our proof: (i) establishing restricted gradient bounds and a smoothness property; and (ii) proving that these properties hold along the optimization trajectory and further lead to global convergence. We point out the second aspect is challenging especially for SGD due to the uncertainty of its optimization trajectory caused by stochastic gradients. We summarize our main contributions as follows:
We prove the global convergence of GD and SGD for training deep linear ResNets. Specifically, we derive a generic condition on the input and output linear transformations, under which both GD and SGD with zero initialization on all hidden weights can find global minima. Based this condition, one can design a variety of input and output transformations for training deep linear ResNets.
When applying appropriate Gaussian random linear transformations, we show that as long as the neural network width satisfies m ((krx"), with high probability, GD can converge to the global minimum up to an e-error within Okx log(1//e)) (o/e) iterations, where k, are the output dimension and the rank of training data matrix X respectively, and k X / (X) denotes the condition number of the covariance matrix of the training data. Compared with previous convergence results for training deep linear networks from Du & Hu (2019), our condition on the neural network width is independent of the neural network depth L, and is strictly better by factor of (Ln).
Using the same Gaussian random linear transformations, also establish the convergence guar- antee of SGD for training deep linear ResNets. We show that if the neural network width satisfies m = (kTr2 log" (L/e) -n²))nn//// , with constant probability, SGD can converge to the global min- imum up to an e-error within ( log(1/e) n/ B) iterations, where n is the training sample size and B is the minibatch size of stochastic gradient. This is the first global convergence rate of SGD for training deep linear networks. Moreover, when the global minimum of the training loss is O we prove that SGD can further achieve linear rate of global convergence, and the condition on the neural network width does not depend on the target error e.
As alluded to above, we analyze networks with d inputs, k outputs, and m > max(d, k} nodes in each hidden layer. Linear transformations that are fixed throughout training map the inputs to the first hidden layer, and the last hidden layer to the outputs. We prove that our bounds hold with high probability when these input and output transformations are randomly generated by Gaussian distributions. If, instead, the input transformation simply copies the inputs onto the first d compo-
2

---

Published as a conference paper at ICLR 2020
nents of the first hidden layer, and the output transformation takes the first k components of the last hidden layer, then our analysis does not provide a guarantee. There is a good reason for this: a slight modification of a lower bound argument from Bartlett et al. (2019) demonstrates that GD may fail to converge in this case. However, we describe a similarly simple, deterministic, choice of input and output transformations such that wide enough networks always converge. The resulting condition on the network width is weaker than that for Gaussian random transformations, and thus improves on the corresponding convergence guarantee for linear networks, which, in addition requiring wider networks, only hold with high probability for random transformations.
1.1 ADDITIONAL RELATED WORK
In addition to what we discussed above, a large bunch of work focusing on the optimization of neural networks with nonlinear activation functions has emerged. We will briefly review them in this subsection.
It is widely believed that the training loss landscape of nonlinear neural networks is highly noncon- vex and nonsmooth (e.g., neural networks with Rel.U/LeakyReL.U activation), thus it fundamen- tally difficult to characterize the optimization trajectory and convergence performance of GD and SGD. Some carly work (Andoni et al., 2014; Daniely, 2017) showed that wide enough (polynomial in sample size n.) neural networks trained by GD/SGD can learn class of continuous functions (e.g., polynomial functions) in polynomial time. However, those works only consider training some of the neural network weights rather than all of them (e.g., the input and output layers) 1. In addition, a series of papers investigated the convergence of gradient descent for training shallow networks (typically 2-layer networks) under certain assumptions on the training data and initialization scheme (Tian, 2017; Du et al., 2018b; Brutzkus et al., 2018; Zhong et al., 2017: Li & Yuan, 2017; Zhang al.. 2018). However. the assumptions made in these works are rather strong and not consistent with practice. For example, Tian (2017), 7); Du et al. (201 8b): Zhong et al. (2017); Li & Yuan (2017); Zhang et al. (2018) assumed that the label of each training data is generated by a teacher network, which has the same architecture as the learned network. Brutzkus et al. (2018) assumed that the training data is linearly separable. Li & Liang (2018) addressed this drawback; they proved that for two-layer ReLU network with cross-entropy loss, long as the neural network is sufficiently wide, under mild assumptions on the training data SGD with commonly-used Gaussian random initialization can achieve nearly zero expected error. Du et al. (2018c) proved the similar results of GD for training two-layer ReLU networks with square loss. Beyond shallow neural networks, Allen-Zhu et al. (2019); Du al. (2019); Zou al. (2019) generalized the global convergence re- sults to multi-layer over wer-parameterized ReLU networks. Chizat et al. (2019) showed that training wver-parametriizee neural networks actually belongs a so-called "lazy training" regime, in which the model behaves like its linearization around the initialization. Furthermore, the parameter scaling more essential than over-paramteen par-paarameriiztionn to make the model learning within the "lazy training" regime. Along this line of research, several follow up works have been conducted. Oymak & Soltanolkotabi (2019); Zou& & Gu (2019); Su & Yang (2019); Kawaguchi & Huang (2019) improved the convergence rate and over-parameeerrizaton condition for both shallow and deep networks. Arora et al. (2019b) showed that training a sufficiently wide deep neural network is almost equivalent to kernel regression using neural tangent kernel (NTK), proposed in Jacot et al. (2018). Allen-Zhu et al. 12019;; Du et al. 2001);; Zhang et al. (2019) proved the global convergence for training deep ReLU ResNets. Frei et al. (2019) proved the convergence of GD for training deep ReLU ResNets under an over-parameterizatton condition that is only logarithmic in the depth of the network, which partially explains why deep residual networks are preferable to fully connected ones. However, all the results in Allen-Zhu et al. (2019); Du et al. (2019); Zhang et al. (2019); Frei et al. (2019) require a very stringent condition on the network width, which typically has a high-degree polynomial de- pendence on the training sample size n. Besides, the results in Allen- ZZu et al. (2019); Zhang et al. (2019) also require that all data points are separated by positive distance and have unit norm, As shown in Du& & Hu (2019) and will be proved in this paper, for deep linear (residual) networks, there is no assumption on the training data, and the condition on the network width is significantly milder, which is independent of the sample size While achieving a stronger result for linear networks than for nonlinear ones is not surprising, we believe that our analysis, conducted in the idealized deep linear case, can provide useful insights to understand optimization in the nonlinear case.
In Daniely (2017), the weight changes in all hidden layers make negligible contribution to the final output, thus can he approximately treated only training the output layer.
3

---

Published as a conference paper at ICLR 2020
Two concurrent works analyze gradient descent applied to deep linear (residual) networks (Hu et al., 2020; Wu et al., 2019). Hu et al. (2020) consider deep linear networks with orthogonal initialization, and Wu et al. (2019) consider zero initialization rest of the layers, which are similar to our setting. However, there are several differences between their work and ours. One major difference is that Hu al. (2020) and Wu et al. (2019) only prove global convergence for GD, but our results cover both GD and SGD. In addition, Hu et al. (2020) focuses on proving the global convergence of GD for sufficiently wide networks, while we provide generic condition on the input and output linear transformations for ensuring global convergence. Wu al. (2019) assumes whitened data and proves a O log(1/c)) bound on the number of iterations required for GD to converge, where we establish ((log(1/e)) bound.
the last layer and identity initialization for the
1.2 NOTATION.
We use lower case, lower case bold face, and upper case bold face letters to denote scalars, vectors and matrices respectively. For positive integer, we denote the set {1...., k) by [k]. Given a vector x, we use | to denote its & norm. We use (H, o²) to denote the Gaussian distribution with mean i and variance o². Given matrix X. we denote [X|| [ and || its Frobenious norm, spectral norm and f, norm (maximum & norm over its columns), respectively. In addition, denote by mmin ()), Tmax (X) and or (X) the smallest, largest and r-th largest singular values of X respectively. For a square matrix A, we denote by (Ain(A) and Amax(A) the smallest and largest eigenvalues of A respectively. For two sequences {ax {au and {bx we say a O(by) if a& & Gbbg for some absolute constant C1, and use ag = (2(bg) if a > C2by for some absolute constant C2. Except the target error use Ō()) and (2(-) hide the logarithmic factors in O(-) and ((.) respectively.
2 PROBLEM SETUP
Model. In this work, we consider deep linear ResNets defined as follows:
fw(x) = B(I B(I+ ...))...1... (I+ Wi)
where x Rd is the input, fw(x) E R* is the corresponding output, A Rmxd B e R denote the weight matrices of input and output layers respectively, and Wi...., W R=*m denote the weight matrices of all hidden layers. The formulation of ResNets our paper is different from that in Hardt & Ma (2016); Bartlett et al. (2019), where the hidden layers have the same width as the input and output layers. In our formulation, we allow the hidden layers to wider by choosing the dimensions of A and B appropriately.
Loss Function. Let (xx, y:)li be the training dataset, X (xI,..., x,) E R be the input data matrix and Y assume the data matrix X is of rank r. where can be smaller than d. Let W (W..... Wr) be the collection of weight matrices of all hidden layers. For an example (x, y), we consider the square loss defined by
.i.....yn) E kxxn be the corresponding output label matrix. We
(: x)
2 f.((((x) yl
Then the training loss over the training dataset takes the following form
L(W)= Σ e(W 1 B +I++ W,)AX YIB.-
Algorithm. Similar Allen-Zhu al. (2019); Zhang et al. (2019), we consider algorithms that only train the weights W for hidden layers while leaving the input and output weights and B unchanged throughout training. For hidden weights, we follow the similar idea in Bartlett et al. (2019) and adopt zero initialization (which is equivalent to identity initialization for standard linear network). We would also like to point out that the initialization, all the hidden layers automatically satisfy the so-called balancedness condition (Arora et al., 2018; 2019a; Du et al., 2018a). The optimization algorithms, including GD and SGD, are summarized in Algorithm I.
Considering whitened data immediately gives 1.
4

---

Published as a conference paper at ICLR 2020
Algorithm (Stochastic) Gradient descent with zero initialization
input: Training data {x, Yi se[]] step size 7), total number of iterations minibatch size B, input and output weight matrices A and B.
2: initialization: For all e [7.] each entry of weight matrix w initialized O.
Gradient Descent
3: for t. 0, ...... T 1 do
4: w/ ( w V wi ((W for all I E [L]
5: end for
6: output: W
Stochastic Gradient Descent
7: to
O,... - T do
8: Uniformly sample a subset B(O) of size from training data without replacement.
9: For all & E [T.], compute the stochastic gradient G(") Eiego Vw, { (
10: For all e [Z]] w((-1) w G
11: end for
12:
output: (W J1-O...
MAIN THEORY
It is clear that the expressive power of deep linear ResNets identical that of simple linear model, which implies that the global minima of deep linear ResNets cannot be smaller than that of linear model. Therefore, our focus show that GD/SGD can converge point W* with
L(W*)
min Oekkxd
- Y
which is exactly the global minimum of the linear regression problem. It what follows, we will show that with appropriate input and output transformations, both GD and SGD can converge to the global minimum.
3.1 CONVERGENCE GUARANTEE OF GRADIENT DESCENT
The following theorem establishes the global convergence GD for training deep linear ResNets. Theorem 3.1. There absolute constants C and C₁ such that, if the input and output weight matrices satisfy
C [|2(L( - L(W*)) 1/2
aA) 2
B
min min
A
B
o2(X)
and the step size satisfies
& C1
L||| 2
B 2 X (VI(W(0) + B|2X1)
then for all iterates of GD in Algorithm 1, it holds that
L(W(0) - L(W*) (1- nLo (A)o (B) (L(W(")) - L(W)).
Remark 3.2. Theorem 3.1 can imply the convergence result in Bartlett et al. (2019). Specifically. in order to turn into the setting considered Bartlett et al. (2019), we choose m = d = k. A I,
I, L(W*) 0 and XXT I. Then it can be easily observed that the condition in Theorem 3.1 becomes L(W(()) L(W*) & C This implies that the global convergence can be established long as L(W(()) L( (W**) is smaller than some constant, which is equivalent to the condition proved in Bartlett et al. (2019).
In general, L( L(W("))- - L(W*) can be large and thus the setting considered in Bartlett et al. (2019) may not be able to guarantee global convergence. Therefore, is natural ask in which setting
5

---

Published as a conference paper at ICLR 2020
the condition A and B in Theorem 3.1 can be satisfied. Here we provide one possible choice which is commonly used in practice (another viable choices can be found in Section 4). We use Gaussian random input and output transformations, i... each entry in A is independently generated from ((, 1/m) and each entry in is generated from (00, 1 1/k).. Based on this choice of transfor- mations, we have the following proposition that characterizes the quantity of the largest and smallest singular values of A and B, and the training loss at the initialization (i.e., L L(W(O) )). The following proposition is proved in Section A.2.
Proposition 3.3. In Algorithm each entry in B is independently generated from N(0, (²). then if m 3 C. + h + log(1/0) for
each entry in A is independently generated from N(O, and
some absolute constant C, with probability at least 6, it holds that
Juin m)) max (A) Oaa/mm, miin (B) (33mm), maxx (B) (Bvm),
and L(W()) & O(a² km log () X| I
Then based on Theorem 3.1 and Proposition 3.3, we provide the following corollary, proved in Section 3.4, which shows that GD is able to achieve global convergence if the neural network is wide enough.
Corollary 3.4. Suppose |||l= x Then using Gaussian random input and output transformations Proposition 3.3 with a 3 1, the neural network width satisfies m (1lmax(krx' (ooikxx/koooo((/// log(n/8), k + d + log(1/5))) then, with probability at least 1 - ō, the output of GD in Algorithm achieves training loss at most L(W*) + within T = Ok Log(1/e)) iterations, where x- (x) denotes the condition number of the covariance matrix of training data.
Remark 3.5. For standard deep linear networks, Du & Hu (2019) proved that GD with Gaussian random initialization can converge to a c-suboptimal global minima within T [2 ([//log(1//)) iterations if the neural network width satisfies deep linear ResNets achieves the same convergence rate as training deep linear networks and linear regression, while the condition on the neural network width is strictly milder than that for training standard deep linear networks by a factor of ((K)). This improvement may in part validate the empirical advantage of deep ResNets.
OLKrrx3 + d). In stark contrast, training
3.2 CONVERGENCE GUARANTEE OF STOCHASTIC GRADIENT DESCENT
The following theorem establishes the global convergence of SGD for training deep linear ResNets. Theorem 3.6. There are absolute constants C, C1 and C2, such for any 0 < 8 & 1/6 and c > 0, the input and output weight matrices satisfy
2 Pin o
B
X| 2 (og(L(((0)/cc)) L(W()).
min
C.
A |
(x²(X)
and the step size and maximum iteration number are
2 min
(A)o min
(B)
(X)
B
77 & C1
min
Ln A
B
3
X
2 L (W") n X log(T/5) log L /
1
((W(O)) -
T C2 n2L min (A) (X) log
then with probability² at least 1/2 (with respect to the random choices of mini batches), SGD in Algorithm can find a network that achieves training loss at most L(W*) +
By combining Theorem 3.6 and Proposition 3.3, we can show that as long as the neural network is wide enough, SGD can achieve global convergence. Specifically, we provide the condition on the neural network width and the iteration complexity of SGD in the following corollary.
Corollary 3.7. Suppose || Y F = O( F). Then using Gaussian random input and output trans- formations in Proposition 3.3 with a = 3 = 1, for sufficiently small e > O, if the neural network width satisfies m (krr 1or (1/e) n2 BB2 + d), with constant probability, SGD in Algorithm can find a point that achieves training loss at most L L(W*) + within T Ö(k² 2e log(1/e).n/BB iterations.
OOne can boost this probability 1 8 by independently running 1og(1/8) copies of SGD in Algorithm

---

Published as a conference paper at ICLR 2020
that compared with the convergence guarantee of GD, the condition on the neural network width for SGD is worse by factor of Ö(n? log"(1/e) (1/e)/ B²) and the iteration complexity is higher by a factor of Ö(ke-1 n/ B). This because for SGD, its trajectory length contains high uncertainty, and thus we need stronger conditions on the neural network in order to fully control it.
From Corollaries 3.7 and 3.4,
We further consider the special case that L(W*) O, which implies that there exists ground truth matrix & such that for each training data point yx) we have y, Lx, In this case, we have the following theorem, which shows that SGD attain linear rate to converge the global minimum.
Theorem 3.8. There absolute constants C, and C1 such that for any 0 < 1, if the input and output weight matrices satisfy
2 mmn
J
B
n x
min
C.
(((w))).
B
(x
and the step size is set
B
(A)
(X)
C
min
min
Lnn
X
log( (T/5)
for some maximum iteration number T, then with probability at least 1 - 6, the following holds for all / & T,
L(W()) & 22(( (1- LLO min (A)o min (X)
Similarly, using Gaussian random transformations in Proposition 3.3, we show that SGD can achieve global convergence for wide enough deep linear ResNets in the following corollary.
Corollary 3.9. Suppose || O F). Then using Gaussian random transformations in 1, for any & Ö( (nl if the neural network width satisfies m śi(krs' n²² 2 + d). with high probability, SGD in Algorithm I can find network that achieves training loss at most within T Ō(5² log(1/e) n²/ BB) iterations.
Proposition 3.3 with
DISCUSSION ON DIFFERENT INPUT AND OUTPUT LINEAR TRANSFORMATIONS
In this section, we will discuss several different choices of linear transformations at input and output layers and their effects the convergence performance. For simplicity, we will only consider the condition for GD.
As stated in Subsection 3.1, GD converges if the input and output weight matrices A and B
2 (A)
(B)
|X|2 (L(W())) - L(W*)) xx(X)
2 C.
(4.1)
A B
Then it is interesting to figure out what kind of choice of and B can satisfy this condition. In Proposition 3.3, we showed that Gaussian random transformations (i.e., each entry of A and B is generated from certain Gaussian distribution) satisfy this condition with high probability, so that GD converges. Here we will discuss the following two other tranffomattooss.
Identity transformations. We first consider the transformations that A = [Laxd, Oax [m=]]] T and B m/k [Tecky (m))-) which equivalent the setting in Bartlett al. (2019) when m d. Then is clear that
Gmin B) -max (B) =VV/// m/k and Tmin (A) = o F (A) 1.
Now let us consider L( L(W())). By our choices of B and and zero initialization on weight matrices in hidden layers, in the that d k. we have
L(W(")) 1
BAX - Y
-
-1 | -YEEX-11? |
1

---

Published as a conference paper at ICLR 2020
We remark that |/ mm/kX - YIl
could be big 1 (m) X / /Y
(for example, when
X and Y are orthogonal). Then plugging these results into (4. 1), the condition on A and B becomes
V mm/k C.
[ (X)
-
C
X
m
X
2k
where the second incquality is due the fact that L(W*) | Then it is clear if |X|r v2/C, the above inequality cannot be satisfied for any choice of m, since will be cancelled out on both sides of the inequality. Therefore, in such cases, our bound does not guarantee that GD achieves global convergence. Thus, it is consistent with the non-convergence results (Bartlett al., 2019). Note that replacing the scaling factor /m/k in the definition B with any other function of d, and would not help.
Modified identity transformations. In fact, we show that a different type of identity transforma-
tions of A and B can satisfy the condition (4.1). Here provide one such example. Assuming m e +-+A. k. we can construct two sets S1, S2 = [m]] satisfying [1 = d, SSy = and S n2 = Ø. Ja. Then we construct matrices A and B as follows:
Let S (ir...., id} and S₂ {úi,... sk.....J.....
1
(i,j) = (1,.5) otherwise
ooo a Bij B
(i.j)= = (i. otherwise
Au
0
where a is a parameter which will be specified later. In this way, can be verified that BA = O, Omin A) maxx (A) 1, and minn max (B) Thus it is clear that the initial training loss satisfies L(W("))= / Then plugging these results into (4.1), the condition A and B can be rewritten as
1 (1X1)/2- L( (X)
a C.
The R.H.S. of the above inequality does not depend ficiently large a to make this inequality hold. Thus, GD can be guaranteed to achieve the global convergence. Moreover, it is worth noting that using modified identity transformation, neural net- work with m = d + lo suffices to guarantee the global convergence of GD. We further remark that similar analysis be extended to SGD.
which implies that we can choose suf-
EXPERIMENTS
In this section, we conduct various experiments to verify our theory on synthetic data, including i) comparison between different input and output transformations and ii) comparison between training deep linear ResNets and standard linear networks.
5.1 DIFFERENT INPUT AND OUTPUT TRANSFORMATIONS
To validate theory, performed simple experiment 10-d synthetic data. Specifically, randomly generate X E IR 110010000 from a standard normal distribution and set Y = - + 0.1 E, where each entry in E is independently generated from standard normal distribution. Consider (0-hidden-layer linear ResNets, we apply three input and output transformations including identity transformations, modified identity transformations and random transfornations. We evaluate the convergence performances for these three choices of transformations and report the results in Figures 1(a)- where we consider two cases m 40 and m 200. It can be clearly observed that gradient descent with identity initialization gets stuck, but gradient descent with modified identity initialization or random initialization converges well. This verifies our theory. can be also observed that modified identity initialization can lead to slightly faster convergence rate as its initial training loss can be smaller. In fact, with identity transformations in this setting, only the first 10 entries of the hidden variables in each layer ever take non-zero value, so that, matter how large m is, effectively, m 10, and the lower bound of Bartlett et al. (2019) applies.
5.2 COMPARISON WITH STANDARD DEEP LINEAR NETWORKS
Then compare the convergence performances with that of training standard deep linear networks. Specifically, we adopt the same training data generated in Section 5.1 and consider training L- hayden-layer neural network with fixed width m. The convergence results are displayed in Figures
8

---

Published as a conference paper at ICLR 2020
Mently Inteliaionn Madled day
Mertit tation
Suncerd Uhear
200
Standrt Unee Lnd
Strcerd (imer Ln20
Sia Slnnerr Uner p+530
Traato
(a) 771 40
(b) 172 200
(c) 17 40
(d) 172 200
Figure 1: (b)-()).onveegenec performances for three input and output transformations 10- hidden-layer linear ResNets. (c)-(d) Comparison between the convergence performances of training deep linear ResNets with zero initialization hidden weights and standard deep linear network with Gaussian random initialization on hidden weights, where the input and output weights are generated by random initialization, and remain fixed throughout the training.
I(c)-1(d), where we consider different choices of L. For training linear ResNets, we found that the convergence performances quite similar for different I., thus we only plot the convergence result for the largest one (e.g.. = 20 for m = 40 and observed that for training standard linear networks, the convergence performance becomes worse as the depth increases. This is consistent with the theory as our condition on the neural network width m Okrrk² (please refer to Corollary 3.4), which has no dependeney in L. while the condition for training standard linear network is m = O(Lkrk²) (Du & Hu, 2019), which is linear in L.
100 for m = 200). However, it can be
6 CONCLUSION
In this paper, proved the global convergence of GD and SGD for training deep linear ResNets with square loss. More specifically, we considered fixed linear transformations at both input and output layers, and proved that under certain conditions the transformations, GD and SGD with zero initialization on all hidden weights can converge to the glohal minimum. In addition, we fur- ther proved that when specializing to appropriate Gaussian random linear transformations, GD and SGD can converge as long as the neural network is wide enough. Compared with the convergence results of GD for training standard deep linear networks, our condition on the neural network width is strictly milder. Our analysis can be generalized to prove similar results for different loss func- tions such as cross-entropy loss, and can potentially provide meaningful insights the convergence analysis of deep non-linear ResNets.
ACKNOWLEDGEMENT
We thank the anonymous reviewers and area chair for their helpful comments. This work was initi- ated when Q Gu and P. Long attended the summer program the Foundations of Deep Learning at the Simons Institute for the Theory of Computing. D. Zou and Q. Gu were sponsored in part by the National Science Foundation CAREER Award I9S-1906169, BIGDATA IIS- 115-995,, and Salesforce Deep Learning Research Award. The views and conclusions contained in this paper are those of the authors and should not be interpreted representing any funding agencies.
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. In International Conference on Machine Learning, pp. 242-252, 2019.
Alexandr Andoni, Rina Panigrahy, Gregory Valiant, and Li Zhang, Learning polynomials with neural networks. International Conference on Machine Learning, pp. 1908-1916, 2014.
Sanjeev Arora, Nadav Cohen, and Elad E Hazan. On the optimization of deep networks: Implicit acceleration by overparameterizaatoo. In 35th International Conference on Machine Learning, ICML 2018, pp. 372-389, 2018.
Sanjeev Arora, Nadav Cohen, Noah Golowich, and Wei Hu. A convergence analysis of gradient de- scent for deep linear neural networks. In International Conference on Learning Representations, 2019a.

---

Published as a conference paper at ICLR 2020
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Ruslan Salakhutdinov, and Ruosong Wang. On ex- act computation with an infinitely wide neural net. In Advances in Neural Information Processing Systems, 2019b.
Peter L Bartlett, David P Helmbold, and Philip M Long. Gradient descent with identity initializa- tion efficiently learns desitive-definit linear transformations by deep residual networks. Neural computation, 31(3):77--50,, 2019.
Alon Brutzkus, Amir Globerson, Eran Malach, and Shai Shalev-Shward SGD lears over- parameterized networks that provably generalize on linearly separable data. In International Conference Learning Representations, 2018.
Lenaic Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable programming. In Advances in Neural Information Processing Systems, 2019.
Amit Daniely. SGD learns the conjugate kernel class the network. In Advances in Neural Infor- mation Processing Systems, pp. 2422-2430, 2017.
Simon Du and Wei Hu. Width provably matters in optimization for deep linear neural networks. In International Conference on Machine Learning, pp. 1655-1664 1664, 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, 2019.
Simon Du, Wei Hu, and Jason D Lee. Algorithmic regularization in learning deep homogeneous models: Layers automatically balanced. In Advances in Neural Information Processing Sys- tems, pp. 384-395, 2018a.
Simon S Du, Jason D Lee, and Yuandong Tian. When is a convolutional filter easy to learn? In International Conference Learning Representations, 2018b.
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. arXiv preprint arXiv: 180000044, 2018c.
Yuguang Fang, Kenneth A Loparo, and Xiangbo Feng. Inequalities for the trace of matrix product. IEEE Transactions Automatic Control, (9(12):2499-2499) 1994.
Daniel C Freeman and Joan Bruna. Topology and geometry of half-rectified network optimization. In International Conference on Learning Representations, 2016.
Spencer Frei, Yuan Cao, and Quanquan Gu. Algorithm-dependen generalization bounds for over- parameterized deep residual networks. In Advances in Neural Information Processing Systems, 2019.
Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nati Srebro. Implicit bias of gradient descent linear convolutional networks. In Advances in Neural Information Processing Systems, pp- 9461-9471, 2018
Moritz Hardt and Tengyu Ma. Identity matters in deep learning. arXiv preprint arXiv:1611.04233 2016.
Wei Hu. Lechao Xiao, and Jeffrey Pennington. Provable benefit of orthogonal initialization in op- timizing deep linear networks. In International Conference on Learning Representations, 2020.
URL URL https: httpppppeeeveeeeeeeeeeeeeeeeeeee net. wettt//frrmiiidde http:/forummiirkggllss//ll
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kemel: Convergence and gen-
eralization in neural networks. Advances in neural information processing systems, pp. 8571- 8580, 2018.
Ziwei Ji and Matus Telgarsky. Gradient descent aligns the layers of deep linear networks. In ICLR, 2019.
Kenji Kawaguchi. Deep learning without poor local minima. In Advances in Neural Information Processing Systems, pp. 586-594, 2016.
10

---

Published as a conference paper at ICLR 2020
Kenji Kawaguchi and Jiaoyang Huang. Gradient descent finds global minima for generalizable deep neural networks practical sizes. arXiv preprint arXiv: 100.:::900.02419, 2019.
Yuanzhi Li and Yingyu Liang. Learning overparameterized neural networks via stochastic gradi- ent descent on structured data. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pp. 8168-8 -1788177, 2018.
Yuanzhi Li and Yang Yuan. Convergence analysis of two-layer neural networks with ReLU acti- vation. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pp. 597-607. Curran Associates Inc., 2017.
Haihao Lu and Kenji Kawaguchi. arXiv:1702.08588, 2017.
Depth creates no bad local minima.
arXiv preprint
Samet Oymak and Mahdi Soltanolkotabi. Towards moderate overparamettrizzatoo:: global conver- gence guarantees for training shallow neural networks. arXiv preprint urXiv: 2019.
Ohad Shamir. Exponential convergence time of gradient descent for one-dimensional deep linear neural networks. arXiv preprint arXiv:1809.08587 2018.
Lili Su and Pengkun Yang. On learning over-parameetriized neural networks: A functional approxi- mation prospective. arXiv preprint arXiv: 10826, 2019.
Yuandong Tian. An analytical formula of population gradient for two-layered ReLU network and its applications in convergence and critical point analysis. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 3400-3413. JMLR. org, 2017.
Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint arXiv:1011.3027, 2010.
Lei Wu, Qingcan Wang, and Chao Ma. Global convergence of gradient descent for deep linear residual networks. arXiv preprini 1rXiv:1911.00645 2019.
Chulhee Yun, Suvrit Sra, and Ali Jadbabaie. Global optimality conditions for deep neural networks. In International Conference on Learning Representations, 2018.
Huishuai Zhang, Da Yu, Wei Chen, and Tie- Liu. Training over over-parameteriveed deep resnet almost easy training a two-layer network. arXiv preprint arXiv: 1903.0700 2019.
Xiao Zhang, Yaodong Yu, Lingxiao Wang, and Quanquan Gu. Learning one-hidden-layer ReLU networks via gradient descent. arXiv preprint 1rXiv:1806.07888 2018.
Kai Zhong, Zhao Song, Prateek Jain, Peter L Bartlett, and Inderjit S Dhillon. Recovery guarantees for one-hidden-layer neural networks. In Proceedings of the 34th International Conference on Machine Learning-Volume Volume 70, pp. 4140-4149 JMLR. org, 2017.
Yi Zhou and Yingbin Liang. Critical points of linear neural networks: Analytical forms and land- scape properties. 2018
Difan Zou and Quanquan Gu. An improved analysis of training over-parameterized deep neural networks. In Advances in Neural Information Processing Systems, 2019.
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Stochastic gradient descent optimizes over-parameterrzeed deep ReLU networks. Machine Learning Journal, 2019.
A PROOF OF MAIN THEOREMS
We first provide the following lemma which proves upper and lower bounds on L(W)] when W is staying inside certain region. Its proof is in Section B.I.
11

---

Published as a conference paper at ICLR 2020
Lemma A.I. For any weight matrices satisfying [a) Will2 & 0.5/L, it holds that,
Vw, (
> o
(A)
o
- -LWW)
V.. < 2c A
B
(L()) L(W*))
VV ((W; y
2e
A
1
B
2 x,
(W; Y.)
In addition, the stochastic gradient G2 in Algorithm satisfies
2en
A
2 B
X
|G
L(W).
B
where the minibatch size.
The gradient lower bound can be also interpreted as the Polyak-Lojasiewicz condition, which is essential the linear convergence rate. The gradient upper bound crucial bound the trajectory length. since this lemma requires that maXte[r]] [Wll 0.5/L.
The following lemma proves the smoothness property of the training loss function L(W) when W staying inside certain region. Its proof is in Section B.2.
Lemma A.2. For any collections of weight matrices, denoted by W { Wi and
W W...... Wi), satisfying maxie[L] [[Wrlr, maxte[]] |Wllr & 0.5/ L. that, it holds that
L(W)- L(W) &
V L(W), W, - Wi>
A| 2 (V (W) 0.5e A
B 2 X
Σ
W
W.l.A
Based on these two lemmas, we are able to complete the proof of all theorems, which are provided as follows.
A.1 PROOF OF THEOREM 3.1
Proof of Theorem 3.1. order to simplify the proof, we use the short-hand notations AA M.d, AB and μB to denote ||A|| 2l. mmnn(A), [B]] and Umin(B) respectively. Specifically, we rewrite the condition on A and B as follows
4v X|2 (L(W(") L I(W*)) 1/2 xx
AAAB
We prove the theorem by induction on the update number s, using the following two-part inductive hypothesis:
(i) maxie[L] W (5) |F & O.5/L.
ii) (WWO)-L(W')) & (11- (- (L(W L(W*))
First, it can be easily verified that this holds for Now, assume that the inductive hypothesis holds for < t.
Induction for Part (i): We first prove that maxte[s] (w(O) P & 0.5/L. By triangle inequality and the update rule of gradient descent, we have
? Vw. (w(
2ee (L(W())) - I(W*))
< 17
nL 113 8/2
< <2enduNe|XX1p (L)) -(W"))) 1/2
e
12

---

Published as a conference paper at ICLR 2020
where the second inequality follows from Lemma A.I, and the third inequality follows from the inductive hypothesis. Since vI- x $ 1 x/2 for any x [0, 1], we further have
W & V2end X (L(W )(W*)) 1/2
2
#=U
X (L(W(O) - I(W*)) 1/2
Under the condition that p B/ (AAAB) 28 X 2 (L(WO) I(W*))"2/O it can be readily verified that // the inductive step, i.e., [LX W & 0.5/T..
& 0.5/L. Since this holds for all ( E [L]. have proved Part (i) of
Induction for Part (fi): Now prove Part (ii) of the inductive step, bounding the improvement in the objective function. Note that we have already shown that W(t) satisfies max(e[1] [w(") [| < 0.5/ thus by Lemma A.2 we have
I(W()) & I(W(1-1)) n Σ Vw L(W(--1))
+ 1 2. (N (eL((((-)) + (x V Vw, ((((
where we use the fact that w w((-l) Ww, L(W())). Note that L L(W()-1)) & L L(W(()) and the step size is set to be
7 = 2LAAdB| X/22 (VeL(W(O) + 0.5e (o
so that we have
L " L(W((-)))
V Lw
2
(L(W(I-D)) - (L(W(--))L(WW)) L(W*)),
where the second inequality is by Lemma A.I. Applying the inductive hypothesis, we get
nL o
L(W(9) L(W*)+ <
(iv((-")--(W""))
nLp 2 (L(W(O)) L(W*)).
(A.1)
which completes the proof of the inductive step of Part (ii). Thus are able to complete the proof.
A.2 PROOF OF PROPOSITION 3.3
Proof of Proposition 3.3. We prove the bounds the singular values and initial training loss sepa- rately.
Bounds the singular values: Specifically, we set the neural network width
m 100 (v (axx k) / log log 12/8))²
By Corollary 5.35 in Vershynin (2010), know that for matrix U diiids (dN > dz) with entries independently generated by standard normal distribution, with probability at least 1 - 2 exp(-tt/22) /2), its singular values satisfy
ddn ddz t t m (U) & max (U) & ddn V +t.
13

---

Published as a conference paper at ICLR 2020
Based on constructions of A and B, we know that each entry of 3/8 B and 1 A follows standard Gaussian distribution. Therefore, set t = 2110g(12/0) and apply union bound, with probability at least 1 5/3, the following holds,
( al a(v - vd 2/ log(
/ogog((// 12/6)) & mmin (A) & max (A) E alym + vd 2 log( (2
8(ym vk- /ogo 12/6)) & min (B) & max BB) & 3 3( + Vh: + 2 log( 12/6));
where we use the facts that minn (sU) min (U) and max (sU) K0 max (U) for any scalar
and matrix U. Then applying our choice of m, we have with probability at least 1 - 8/3.
0.90mmm m & min (A) v max (A) & 1.lay/m and 0.93 m v mmin (B) & T (B) < 1.13mm.
This completes the proof of the bounds on the singular values of and B.
Bounds on the initial training loss: The proof in this part is similar to the proof of Proposition 6.5 in Du & Hu (2019). Since we apply zero initialization on all hidden layers, by Young's inequality, we have the following for any (x,)),
(0) x, = BAx yl3 & BAx + lyy
(A.2)
Since each entry of B is generated from (O, conditioned A, each entry of BAx is dis- tributed according to Mo, Ax| tail bound for x distribution, we have, with probability at least 1 - 8',
| [ follows a X distribution. Applying a standard
BAx 2 < 3h((1 2 (oog(1/88/// 2 log((1/8)) Ax
Note that by our bounds of the singular values, if m > 100 m/xxdd,k k} + 22oog(8/8) 2 have with probability at least 8/3, |A & 1.laymm thus, it follows that with probability at least 1 8' - 8,
BAx 3 & 1.210 3 km + 2- log(1/8) 2 2log(1/8))
Then by union bound, it is evident that with probability 1 - nz' - 8/3,
B
Σ BAx 1.21aa 3m (oVlog(188)) + 2 log(1 I|
Set = 5/(3n), suppose log(1 (1/8)= > we have with probability least -25/3,
L(W())= = BAX - Y < BAX 2
|Y < 6.05a 2mmmmmm km log( (2 + |
This completes the proof of the bounds on the initial training loss.
Applying a union bound on these two parts, we are able to complete the proof.
A.3 PROOF OF COROLLARY 3.4
Proof of Corollary 3.4. Recall the condition Theorem 3.1:
02 min oA)o min B
X (x
C-
-
(A.3)
A 2 B
By Proposition 3.3, we know that, with probability 1- 8. 8.
min (A) min (B) Omm),
A B|2
| (L(W(0)) I(W+)) 1/2 = ( /(v
(VVhmlogin//b + (x
||
(X)
14

---

Published as a conference paper at ICLR 2020
Note that 5 Σ vr 222, thus the condition (A.3) can be satisfied if m 12krk log(n/6) where x = X (X).
Theorem 3.1 implies that L(W(") L(W") & after T O OnLo (A)o iterations. Plugging in the value of 1j. we get
mim (B)o log
min
==0 |A B
2 (VL(W(O) + || Bl2 x min (A)o min (X)
log :)
By Proposition 3.3, we have
|A B
X
kum log 1/ X + |
B
T=0
log
8 min o min (2
| (v am log( n X
ml X 22)
log E
(x)
| (v /rr log(n//) (0((/00)/m) X | + 1x
1
log
x2(X)
0 k: log 1
for = 12kr log(n/6)), completing the proof.
A.4 PROOF OF THEOREM 3.6
Proof of Theorem 3.6. The guarantee is already achieved by W if > ((W(()) - I (W*)) so we may assume without loss of generality that < L(W(())- L(W*).
Similar to the proof of Theorem 3.1, use the short-hand notations AA, MAA, An and μn denote A|2,, Tmin ( (A), [ and minn respectively. Then we rewrite the condition on and B, and
choices of 1 and T as follows
PAPE
v 8e nl X log(L logg(L(W(0)))
2L(W(O)
XAAB
(x)
Bu (
log 2
17 6e Lnd
min
X 22 L(W*)
3n XII log(T/6) log Lo
L(W(O) L(W*)
7
log
C'
where we set é' c/3 for the purpose of the proof.
We first prove the convergence guarantees expectation, and then apply the Markov inequality.
For SGD, our guarantee is not made on the last iterate but the best one. Define e; to be the event that there no & t such that L(W(t)) L(W*) & d. 1 ((,) O, then there an iterate W, with that achieves training loss within e' of optimal.
Similar to the proof of Theorem 3.1, we prove the theorem by induction on the update number 8, using the following inductive hypothesis: either ((E,) 0 or the following three inequalities hold,
(i) max /
//2(
B
(ii) [[( I(W*))] (1- ) (I(W(O)) - I(W*))
(ii) L(WO)) 2L(W
where the expectation in Part (ii) is with respect to all of the random choices of minibatches. Clearly, if 1 (EE) 0, we have already finished the proof since there is iterate that achieves training loss
15

---

Published as a conference paper at ICLR 2020
within c' of optimal. Recalling that < L(W()) L(W"), it is easy to verify that the inductive hypothesis holds when =
For the inductive step, will prove that if the inductive hypothesis holds for < t, then it holds for 8 = t. When ((,-1) = 0, then 1 (ee) is also 0 and we are done. Therefore, the remaining part is to prove the inductive hypothesis for s t under the assumption that 1( implies that (i), (ii) and (iii) hold for all s & t - 1. For Parts (i) and (ii), we will directly prove that the corresponding two inequalities hold. For Part (iii), will prove that either this inequality holds or 1(e)) = 0.
1, which
Induction for Part (i): As we mentioned, this part will be proved under the assumption (()-1) = L. Besides, combining Part (i) for s = t- 1 and our choice of 17 and T implies that maxie[r.] /w((-)) < 0.5/L. L. Then by triangle inequality, we have the following for [ I[.
w ||
1| n 11..
By Lemma A.1, we have
v /eendAAB X|2
|
L(W((-1)
B
Then we have
|W| (Iw((-))
+ n G (1
W F + /2emndAde X||2
L(W(-1)).
(A.4)
By Part (iii) for = =- we know that L(W((-1)) & 21 (W()). Then by Part (i) for - 1, it is evident that
F 2eetmnddd X|12
2L(W
(A.5)
B
This completes the proof of the inductive step of Part (i).
Induction for Part (ii): As we previously mentioned, we will prove this part under the as- I(),1)
sumption 1
1. Thus, as mentioned earlier, the inductive hypothesis implies that
max | ((11))) || & 0.5/L. By Part (i) for 8 = 4, which has been verified in (A.5), it can [ (2) F & L, then we have the following by Lemma A.2.
be proved that max
- L(W())-L(((->) < n
(W., G(!
n" X - (VeL(W(-))) + 0.5eAada Xl22
G (f 12.
(A.6)
By our condition on A and B, it is easy to verify that
2
AadB
dAdB
|
Then by Part (iii) for s 1-1 (A.6) yields
L Σ
L(W()) - L((((-1)) < Σ
( 2
G
(t-1-)
1=1
(A.7)
Taking expectation conditioning 11 gives
[[((W()))(() -
- L(W(I-1) < n Σ Vw, WwW
L
Σ
E G
w((-1)].
(A.8)
16

---

Published as a conference paper at ICLR 2020
Note that, for i sampled uniformly from [l, the expectation B| upper bounded by
G ( w
can be
E||G (1
| w
B||
(1-1)
Vw. (w.L(w((-1)]
|
2 Bl hWtp://WWW..../////------111111-
(A.9)
By Lemma A.I, we have
V (W(()) y.) W( & 2e
E[ x
y:)
W(
2
x
yi)
n
2e 2 2
X 2 L( L(W(1-1)
Plugging the above inequality into (A.9) and (A.8), we get
E (((W)))(( - I(W((111)
Vw, (
2en X
2 ((W(-1)
+ tn LA X2
X
VV. 1
B
Recalling that v) & 1/(6e1,23 23 1), we have
E [[((W()))( -(W-))- L(W((-1))
5n
V Vw.
Vw.L (W(
2e n7 L2
n
X
4
(A.10)
B
By Lemma A.1, we have
Ww, L(W > 21- ( L(W"))
If we set
3 X
< 6E LE 1
(A.11)
X
then (A.10) yields
E ([() ((( - ((W(-1))
5 (X)) (x)
(L(W(LI)) -
3R
n 1 nA
X X 3. DL L(W*)
B
20² L nn
L(W")
(((W(t-))-L(WW) L(W))) +
(A.12)
30
B1²
Define
4L 1 (X)
20,
70
and 71
3e
B
17

---

Published as a conference paper at ICLR 2020
rearranging (A.12) further gives
[[[(W")) L(W*) & (1 770) (L - + +1pm
(A.13)
Therefore, setting the step size as
7 $ '0c
Bug (X)
471
6E G
AB X
X 2,00 L(W*)'
we further have
E|L(W(0) - L( w(( < (1 -1- (1- -L L(W")] n'm
3 4) [L(W(--)) L(WW") L(W")], ]]
(A.14)
where the second inequality is by (A.13) and the last inequality by the fact that we assume (E,,1) 1, which implies that ((W(-1)) (WW) >< d' 3 4/1/%%. Further taking expectation over W((-1), we get
E
- L(W*) <
(1- 3 13 E[ - L(W*)]
$ (1 3 4)) (L( L(W*)),
where the second inequality follows from Part (ii) for = (- 1 and the assumption that 11 (E)) = 1. Plugging the definition of To. we able complete the proof of the inductive step of Part (ii).
Induction for Part (iii): Recalling that for this part, we are going to prove that either L I(W(O) & ( or I((,) = O, which is equivalent to I(W())) I(E)) & 2l(W(O)) since L( L(W(O)) and L(W()) are both positive. We will prove this by martingale inequality. Let F, = o(W(O), ..... w(O) be a o-algebra, and FF = (Filez1 be a filtration. We first prove that E[L(W()) F(-11 & L(W(+-1) I(E;-1). Apparently, this inequality holds when 1() 0 since both sides will be zero. Then if I(É,1) ([([(())//((])) & I(W((1)) since L(W*) is the global minimum. Therefore,
by (A.14) we have
([L(W()) I((,)) W 1(E.1) 1J (LL( 1(E--)
L(W(-1))
Combining these two cases, by Jensen's 's inequality, we further have
B[log (L(W(1) 1( [(E & log (B[L(W(() (()))FF-1)
< log (L(W(-I))((E ((C,-)),
which implies that (log (I(W(1)). 1 ((E))) 120 is super-martingale. Then we will upper bound the log (L(W(L-1)) I(E Clearly this quantity
martingale difference log (L( I(E))
would be zero if (()-1) = 0. Then if (()-)) = 1. by (A.7) we have
T(((()= & ((W((-1))
Vw,
(| || en
2
G 1
By Part (i) for s = 1- 1, Lemma 1. we further have
L(W(O) & 1 L 2c 2n
L
X
L(W(--))
B²
1+ Le X2 X
L(W(-1)).
(A.15)
where the second inequality follows from the choice of n that
B
2en LA
X
Using the fact that 1(C,) & 1 and 1(6,-1) L, we further have
log (L(W(1)) I(E.)) & log (L(WIL-1)). I(E,-1)) +
B
18

---

Published as a conference paper at ICLR 2020
which also holds for the ((,-1) = O. Recall that flog (L(W(O) 1(())) 1:30 is super- martingale, thus by one-side Azuma's inequality, we have with probability at least 8'
log (L(W 1(E)) < log (L(W())) 3enLMx X
2t log(1/0").
B
Setting 8' = 8/T, using the fact that & and leveraging our choice of and we have with probability least 1 ö/T,
10g
VTn 3 2logg
which implies that
L(W(O) I(E,)
exp log (L(W(()) log(2) <2L(W(O).
(A.16)
This completes the proof of the inductive step of Part (iii).
Note that this result holds with probability at least - 6/T. Thus applying union bound over all iterates (W(+) (W(+))ro...... Ir-0....? yields that all induction arguments hold for all t & T with probability at least 1 5.
Moreover, plugging our choice of T and y into Part (ii) gives
E B[I(WW)) - [(W*) E
By Markov inequality, further have with probability least 2/3, it holds that ((W(T) L( ((W*)J-1(C) & 3e' = e. Therefore, by union bound (together with the high probability arguments of 16) and assuming 5 < 1/6, we have with probability least 2/3-0 1/2, one of the iterates of SGD can achieve training loss within e' of optimal. This completes the proof.
A.5 PROOF OF COROLLARY 3.7
Proof of Corollary 3.7. Recall the condition in Theorem 3.6:
( (A)o
min (B)
2
n2| X||2 log( log(L(W(o)) I(W()).
2 C
(A.17)
A
B
Bo?(X)
Then plugging in the results in Proposition 3.3 and the fact that |X|| 2122 we obtain that condition (A.17) can be satisfied if (krr² log" loge(1/c) B/n).
then and use the fact In addition, consider sufficiently small such that e & based on the results in Proposition 3.3. that ||| |||2 have 7 (k:Be/(Lmmmx Then in order to achieve c-suboptimal training loss, the iteration complexity is
L(W(O)
L(W*)) O(x² nn)))
Lo o min min (X) log
This completes the proof.
A.6 PROOF OF THBOREM 3.8
Proof of Theorem 3.8. Similar to the proof of Theorem 3.6, we set the neural network width and step size follows,
Pap dAAB
4v X1|2
V (2L(W())
(x)
log(2) B2 2
L x A X log(T
where Xa, MA. ÅB and μy denote |A] miin (A), BII2 and omin (B) respectively.
Different from the proof of Theorem 3.6, the convergence guarantee established in this regime is made on the last iterate of SGD, rather than the best one. Besides, we will prove the theorem by induction on the update parameter 1, using the following two-part inductive hypothesis:
19

---

Published as a conference paper at ICLR 2020
(i) ma W ( || & 0.5/L
i L(W()) & (L( (1-
Induction for Part (i) We first prove that max | L. By triangle inequality and the update rule of SGD, we have
| |F
E
n GilF
1end X|12
((W()))L((W))
B
ZenndAdB AB 2||2
([(Wr))-((W>))
- L(W*)) 1/2
1-1
Σ
1 1-
2
AA B X (L(W(0)) - L(W*)) 1/2
where the second inequality is by Lemma A.1, the third inequality follows from Part (ii) for all s < t and the fact that (1 - 1/2 x 1 - x/2 for all x e [0. 1]. Then applying our choice of m implies that
[ 0.5/L. L..
Induction for Part (ii) Similar to Part (ii) and (iii) of the induction step in the proof of Theorem 3.6, first prove the convergence in expectation, and then use Azuma's inequality to get the high- probability based results. It can be simply verfied that
PAMB AAdB
2v X
log(L( (())))
(L( 2 2/2c 2e ((W))))
AAAB
(x
|
log(2) 122 p p (
o
36e Ln 2 x1 1 X (T/8)
6e
1
Thus, we can leverage (2. and obtain
B[L(W ( - L(W((-)) 4n
L L(W(L-1)),
30
where we use the fact that L(W*) 0. Then by Jensen's 's inequality, we have
[ 4 of ((( (X)
of I[log ([((()))] log (L(W(I-1)) + log
30
log (L(W(L-1)) |
3e
where the second inequality is by (og(1 + x:) & x. Then similar to the proof of Theorem 3.6, we are going to apply martingale inequality to prove this part. Let F, = of (W))).... W(!) be r-algebra, and IF (Frrs be filtration, the above inequality implies that
T log [F=+)) 4tmLp2p6307t
& log (L(W(t-1)) 4(t 1
3e
30
(A.18)
which implies that ( log (L(W(1)) + (A.15), we can obtain
is super-martingale. Besides, by
log (L(W(O)) < log (L(W(t-1))) + 3en Ln A X2 x
B
which implies that
log (L(W())) + 1
30
< log (L(W(L-1))) + 4(t - 1)mL
4en
3e
B
20

---

Published as a conference paper at ICLR 2020
where again the fact that log( 1 + z) have with probability at least - 8' that
Thus, by the one-sided Azuma's inequality
log (L(W())) & log (L()())) 4tm A
X
X
v 2t log(1/8")
30
B
2 tnL
o
X
96e Bhe"nLn2>
X
A
X
| log(1/0))
$ log ([(W()))
B 2 1
log ([(((O)) AnL121
X
log(2),
where the second inequality follows from the fact that -at + bvb & b2/a, and the last inequality is by choice of y that
log(2) p p (B)
7
96e3 Ln 2 X log(1/8')
Then it clear that with probability at least
L(W()) (T() exp
(A.19)
e
which completes the induction for Part (ii).
Similar to the proof of Theorem 3.6, (A.19) holds with probability at least 1 - 8 for given t. Then set 8' 6/T and apply union bound such that with probability at least 1 5, (A.19) holds for all t < T. This completes the proof.
A.7 PROOF OF COROLLARY 3.9
Proof of Corollary 3.9. Recall the condition Theorem 3.8: C.
2 (A)o min
n ||||22
min
Bx,(X) V VL((O),
(A.20)
2 B
Then plugging the results Proposition 3.3 and the fact that |||F & v|lX| we obtain that condition (A. can be satisfied if Okrr² B/n).
In addition, it can be computed that 17 O (kBB (Lmn? xx({(() based the results in Proposition 3.3. Then in order to achieve e-suboptimal training loss, the iteration complexity is
((W(l))-((W)
T min 2
log
O(*² log(1/e) n²/B²).
Lo
(X)
This completes the proof.
B PROOFS OF TECHNICAL LEMMAS
B. PROOF OF LEMMA A.I
We first note the following useful lemmas.
Lemma B.1 (Claim B.1 in Du & Hu (2019)). Define + argmineertxi OX Y then for any U Rixd it holds that
UX- YI
UX- +x F + +X Y
Lemma B.2 (Theorem in Fang al. (1994)). Let U, Ve Rdxd be two positive definite matrices. then it holds that
Amin (U)TrVV) & Tr(UV) < Amax (U)Tr(V).
The following lemma is proved in Section B.3.
21

---

Published as a conference paper at ICLR 2020
Lemma B.3. Let U Rdx be rank-r matrix. Then for any V R it holds that mina (U) & UV & max m (U).
Proof of Lemma A.I. Proof of gradient lower bound: We first prove the gradient lower bound. Let U= B(I+ Wz)... (I+ W1]A, by Lemma B.1 and the definition of L L(W"), we know that there exist a matrix & e Rexd such that
L(W)- - - x p + L(W*).
(B.1)
Therefore, based on the assumption that max WilF & 0.5/I, we have
1(W) [B + WL) ... (I+ W(+1)] (UX- - [X+ Wi-1)... AX] I/ A
min (II + W.). (I+ Wi+1)) o ((I+ Wi-1) ... (()))))
B (U - +)XX I
O15//)/) 21, | (U X)XX A A
where the last inequality follows from the fact that miiu (I + Wi) > 1 Will 3 1- W
0.5/L. Applying Lemma B.2, we get
[BT(U- - x)XX A
Tr(BBT (U +) T A (U D)
Amin (BB TT(A AXX (U - T) xX
Amin (BB) Amia (A (A A) I(U ((U0-))X3 XX 1E.
Note that X is of r-rank, thus there exists a full-rank matrix X E gddr such that XX XXT.
Thus have
II(U - +) Tr((U- - x)xx (U (U-6) - - ( (U- ( = || Φ) P
(B.2)
Therefore,
- x
1/ |I(U 1 -Tr((U
XX F
X (U-
> Aminn (X X) [|(UU 1 XI
(X) (I((W) - ((W))-(W<+)) I(W*)),
(B.3)
where the inequality follows from Lemma B.2 and the last equality follows from (B.2), (B.1) and the fact that Amin ( TX = (X = (X). Note that we assume d, k & m and d & n. Thus it follows that Amin (BB together, we can obtain
min (B) and Amin (A A) Pain (A). Then putting everything
VV L(W) 2 > 20 min (B) (B)
min (A)
(L(W-L(W*))
Then using the inequality (1 - 0.5/ T,)2-- > e-1, we are able to complete the proof of gradient lower bound.
Proof of gradient upper bound: The gradient upper bound can be proved in a similar way. Specif-
ically, Lemma B.3 implies
w. L(W) = B(I + WL).. (I+ W441) (UX- - 4X+ Wi-1) ... AX| T
2
([I Wt). .. (I+ W 02 max (II WI-1) (I+ Wi))
max
B T x A
max ([I + Wz) ... (I+ Wi+1) max
W ... (I+ Wi))
B 2 A I(U $ xX 12
+ 0
B
A
IUU - + XX 12
22

---

Published as a conference paper at ICLR 2020
where the last inequality is by the assumption that maX WillF < 0.5/L. By (B.3), we have
I(U - (U-
x)xX P
| - xX / )1
Amax XXT): ((U-+)XXX)) 1/2
Max
XxT) ((U-+)X[p
2 (L(W)- L(W*))
where the inequality is by Lemma B.3 and the second equality is by (B.2). Therefore, combining the above results yields
[w, & 20 (B) (B)
max ma) X (1 0.5/L)) L(W-L(W*))
Using the inequality (1 + 0.5/L)2L-2 & (1 + 0.5/ & we are able to complete the proof of gradient upper bound.
Proof of the upper bound of have
; Let U = B(I WL) ... (I Wi)A, we
Vw, x y:) [B[++ W2) ....... .I. W(+1) (Ux, (1) Wi-1) Ax,] W._1)...Ax,]'
Therefore, by Lemma B.3, we have
Vw, ( x 1.) max ((I Wr) (I+ W(+1)) omax (II+ Wi-1) ... (())
B T (Ux; - A T
(1 + 0.5
B A x |Xx: - yill?
< 2e A TAU
B x
1 (:::
where the last inequality is by the fact that (1+ 0.5/L) ce.
Proof of the upper bound stochastic gradient: Define by the set of training data points used to compute the stochastic gradient, then define by X and Y the stacking of {x) and (yr respectively. Let U B(I+ WL) (I+ Wi) A, the minibatch stochastic gradient takes form
G
Σ V W. (W;x,,y)
B
iEB
n B
B Wz) ... (I+ WH+1) (I
(UX- - +II+++ Wi-1)...AX]
Then by Lemma B.3, we have
n²
|Gr|l &
2
max (I+ Wz) - (I+ Wi-1)) ii Wi-1) ... .I Wi))
B
B BUUX- - Y)X A 1
2
(1+ (1+05//))2L-
B A
-UX
JUX YI?
B
en2 B
B
X
-X-YR
Ba
where the second inequality is by the assumptions that maxie[]] WilF & 0.5/L, and the last inequality follows from the the fact that (1 + 0.5/L)2L-2
(1 + 0.5/L)2 L)2L & e. Note that X and Y are constructed by stacking B columns from X and Y respectively, thus we have |X & |X] and JUX- Y & UX YI = 2L(W). Then it follows that
2en²
|G <
1 L(W).
B
This completes the proof of the upper bound of stochastie gradient.
23

---

Published as a conference paper at ICLR 2020
B.2 PROOF OF LEMMA A.2
Proof of Lemma A.2. Let U- B Wt) ..)...(T ".I(I+ W and Ü B(I+ ..) I W
and
-. We have
L(W) L(W)- 1
(IÜX- Y UX- Y11?)
2
(I(U+ AJX YI |XX Yl?.))
2
(IUX- - Y + AX
UX - Y
2
(12UX Y,AX, A
2
(UX- Y, Y. ( U) + - U
(B.4)
We begin by working on the first term. Let V (I+ WL)
(I+ and (I+ WL) ... (I+
W1), that Ú-U U- B(Ū-V)A Breaking down the effect of transforming V (I+
into V
11; - Wj) into the effects of replacing one layer time, we get
[+1 Σ ((a+tw)) (ft++w)) w.)) - -fia+ (Ha.+w)) 0-%
and, for each I, pulling out a common factor (IT) w,)) (T W)) gives
WI) V = Σ I W1) (I+ W(+) (1] Wi-1)...(I. W1)
2 [I+ Wz) ... (I+ W W W ... (1)
V.
II+ W.) ... (I+ W WT
V,
[[+ W (I+ W1) (I .W.1))...(II Wi)
(B.5)
V2
24

---

Published as a conference paper at ICLR 2020
The first term V1 satisfies
(UX- - Y,
UX-YBB Σ
I (I) (I+ -w: + ...
(I+ Wi) (.)) AX
UX BB WL) ... (I+ WH+1) (W: W Wi-1) .II Wi)AX)
TrU Y) B))++ ... (I+ Win)( W/ Wi-1). (I+ + Wi)AX)
Tr([I+ W (I+ W AXXXX Y) B(I W.) ... ......-II (I+ W41) Wi)
(I W.)....T
-UX- ... -X."' W -Wi)
Σ VW,,I(W) Wi Wi),
(B.6)
where the first equality is by the definition of V1. Now we focus the second term V2 of (B.5),
V2 Σ I+ WT) ... (I+ W W,)
Σ [I+ ((+)--))-.. (I+ W. W WI)(I+ W.-1)... (I Wi).
Recalling that |i]r. r. Wile & 0.5/L for all I e [L]. by triangle inequality we have
|V2|= < (1+ 0.5
Σ
Wr WilFF IW, -WalF
1>
I.
< (1+00/
W WillF)
where we use the fact that Σt. :>> 1>s aid & [[ aja, = (E, a1)² holds for all @1,..., 71 3
0. Therefore, the following holds regarding V2:
UXX-YBV,AAR |UX-
Y r BV
22 B 2 A V
Σ W SIW--Wild wile) )²
L
L 2
(B.7)
where the third incquality follows from the fact that (1 + 0.5/L) = (1 + 0.5/L** & Vē. Next,
we are going to upper bound the second term of (B.4): ] - U Note that, since I(Ū
U |B(V V)AX &
v suffices to bound the norm IV
V... By (B.5), we have
V V
Σ I+ WL)... (I+ W1+1) W Wi-1). ...)....++ Wi)
< O1+05/D)
W. Will.
(B.8)
25

---

Published as a conference paper at ICLR 2020
Plugging (B.6), (B.7) and (B.8) into (B.4), we have
L (W) L(W)
-UX-
(UX - Y. B(B + V2)x) (((V-VVAXI
Ww,L(W), W. wi)
A B X (v (W) 0.5e 2 x(22)
Σ Iw WilF)
V w. LWW,(W), w. Wi>
A B X (W) 0.5e A B
X
Σ
W
wills
(B.9)
where the last inequality is by Jesen's inequality. This completes the proof.
B.3 PROOF OF LEMMA B.3
Proof of Lemma B.3. Note that have
UVV Tr(UVV TU(TTUVVT..
By Lemma B.2, it is clear that
Amin (U U)Tr(VVT) & Tr(U (IUTUVVT) Amax (U U'UT)T(VV))
Since U E gdxr is r-rank, thus we have Amin U = min
(U). Then applying the facts that Amax U U) max (U) and Tr(VV = [[ we are able to complete the proof.
26


Reviews:
[{"review_id": "rkgnmE0ptS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the convergence properties of GD and SGD on deep linear resnets. The authors prove that, under certain conditions on the input and output transformations and with zero initialization, GD and SGD converges to global minima. The results derived in this paper show that the condition on the width of a deep linear resnet is less strict (by a factor O(L kappa) where L is the depth and kappa the condition number of the training data) that a network without residual connection. Overall, the paper is well-written and the analysis is fairly standard and easy to follow (I checked most of the theorems except for Lemma A.2 and the results for stochastic gradients). The authors do not clearly contrast their results to prior work (especially Bartlett et al. (2019) and Arora et al. (2019a)) and I’m therefore not convinced the final result brings any new insight. Please address this issue in your rebuttal. I will reconsider my score if the authors can provide a satisfactory answer.\n\nComparison to Du & Hu\nThe authors claim that their bound shows an improvement by a factor of O(kappa L) over the deep linear network (without residual connections) analyzed in Du & Hu.\n1) I don’t think this is explicitly stated in the paper but are the initialization conditions and the assumed distance to the optimum the same in both papers?\n2) These results are obviously worst-case bounds and the analysis used in both papers is different to some extent. Couldn’t you re-derived this result by adapting your own analysis?\n3) Is there any theoretical proof or empirical evidence showing that resnets do indeed scale better w.r.t. to the condition number of the data?\n\nComparison to prior work\nThe authors mention the work of Bartlett et al. (2019) and Arora et al. (2019a) but it is never very clear what the real differences are.\n1) Regarding Bartlett et al. (2019), you say that “Theorem 3.1 can imply the convergence result in Bartlett et al. (2019).”. Does the result of Theorem 3.1 provides a tighter bound in terms of L or kappa (when using the same initialization conditions)? \n2) Arora et al. (2019a): You explain that they showed that “GD converges under substantially weaker conditions”. How much weaker are these conditions? How do they compare to the “modified identity transformation” that allows you to obtain a global convergence rate. How does your final result compare to Arora et al. (2019a)? The analysis of Arora et al. (2019a) requires a balanced-ness condition, is this substituted by a different condition in your analysis?\n3) Finally, Allen-Zhu et al. (2019) already has some results on deep resnets although their analysis is for a heavily over-parametrized regime. Can you still comment on how their results differ from yours?\n\nA & B are fixed matrices initialized from a Gaussian distribution. How essential is this condition? Assuming for simplicity that A and B are square matrices. Can I not set A=B=identity and still satisfy the condition in Theorem 1? The term on the RHS would be 1 so then the initialization would need to scale as a function of the spectrum of the data matrix X.\n\nResNet vs LinearNet\nWhere does your proof break down for a linear net without residual connections, i.e. where does the proof absolutely need the identify matrices. Looking at the proof, it seems to me, one could change the following in order to still obtain a similar result:\n1) If we consider a network B \\prod_l W_l AX, the proof of proposition 3.3 could be unchanged if the W matrices are initialized to identify instead of zero.\n2) The lower bound on \\sigma^2_min(I + \\tau W_l) would instead be replaced by a lower on \\sigma^2_min(W_l)=\\lambda_min(W_l). Is this where  one can see the benefit of having residual connections?\n\nProposition 3.3\nThe bound on the singular values of the matrices A and B is vacuous for square matrices, in which case I believe the theorem does not hold. Can you comment on this?\n\nExtension stochastic setting\nI only skimmed at the proof but the extension looks fairly straightforward. Can you comment on how difficult this derivation is compared to the deterministic setting?\n\nExtensions\nYou claim \"can potentially provide meaningful insights to the convergence analysis of deep non-linear ResNets.\" although this is not obvious as the landscape of such networks can be very different. Can you elaborate?\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "SyluQ28J9S", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\n*Summary* \nThis paper deals with the global convergence of deep linear ResNets. The author show that under some initialization conditions for the first and the last layer (that are not optimized !) GD and SGD does converge to a global minimum of the min squared error. The closed related work seems to be Bartlett et al. 2019 that study the convergence of GD in the case of linear networks.  \n \n*Decision* \nOn issue for Bartlett et al. 2019 was that they required a condition on the initial suboptimality to be small in order to insure convergence. This work shows that in the case of linear ResNets, with a well chosen initialization, a similar condition holds with high probability. \nI think this paper is interesting for the ICLR community and seems to provide good contributions (like for instance the analysis for SGD). However I have some question that I would like the authors to answer.\n*Questions*\n- In Proposition 3.3 you show an upperbound on $\\sigma_{\\min}(B)$ in order to show in Corollary 3.4  that the condition to apply Theorem 3.1 is true. However, it seems to me that you need a lower bound on  $\\sigma_{\\min}(B)$ to prove that (A.3) is true.\n- To what extent the proof of Theorem 3.1 uses the proof technique of Bartlett et al. 2019 ?\n- With you small enough conditions, are you in the lazy regime described by Chizat, Lenaic, Edouard Oyallon, and Francis Bach. \"On Lazy Training in Differentiable Programming.\" (2019). NeurIPS\n- In Theorem 3.1 What is $e$ ?\n- Could you prove the same result as Theorem  3.1 and 3.6 but with an inequality constraint on the step size? It seems very restrictive to me to ask a stepsize to be exactly equal to a quantity. If you cannot relax you equality constraint into an inequality constraint, can you at least show that your result hold for step size in an interval?\n\n\n=== After rebuttal ===\nThank you for this detailed answer. It confirms that this paper is of interest to the ICLR community.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HJg_GdOTKr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors study the convergence of (stochastic) gradient descent in training deep linear residual networks, where linear transformation at input and output layers are fixed and matrices in other layers are trained. They first establish a global convergence of GD/SGD under some conditions on the fixed linear transformations. They they showed that for Gaussian random input and output transformation, global convergence still holds under conditions on the width of networks strictly milder than the literature. Linear convergence rate of SG/SGD are also established.\n\nThe paper is well written. The results seem novel and interesting.\n\nIt would be nice if the authors can give intuition why the input and output layer transformations need to be fixed in the analysis. What if happen if these matrices vary along the optimization process?\n\n----------------------\nAfter rebuttal:\n\nI have read the authors' response. I would like to keep my original score.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper provides further analysis of convergence in deep linear networks. I recommend acceptance. 
Decision: Accept (Poster)