Year: 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 (Du & Hu, 2019), our condition on the neural network width is sharper by a factor of OpκLq, where κ 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 pd ` kq-wide neural network is sufficient to guarantee the global convergence of GD/SGD, where d, k are the input and output dimensions respectively.

heading: 1 INTRODUCTION
text: 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-propagate; and (c) there is potential for exploding and vanishing gradients. In addition to enabling study of systems with these properties in a relatively simple setting, analysis of deep linear networks also facilitates the scientific understanding 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 landscape 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 a deep linear network with square loss function is either a global minimum or a saddle point, and identifying conditions on the weight matrices that exclude saddle points. Beyond landscape analysis, 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 gradient 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. (2019a); Shamir (2018); Du & Hu (2019) analyzed the optimization trajectory of
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) considered identity parameterizations in deep linear networks, i.e., parameterizing each layer’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 maximum spectral norm among all weight matrices is smaller than Op1{Lq. 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 Φ 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 appropriate 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 minimum. 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 on 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 “ Ωpkrκ2q, with high probability, GD can converge to the global minimum up to an -error within Opκ logp1{ qq iterations, where k, r are the output dimension and the rank of training data matrix X respectively, and κ “ }X}22{σ2rpXq 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 a factor of OpLκq.
• Using the same Gaussian random linear transformations, we also establish the convergence guarantee of SGD for training deep linear ResNets. We show that if the neural network width satisfies m “ rΩ ` krκ2 log2p1{ q ¨n2{B2 ˘
, with constant probability, SGD can converge to the global minimum up to an -error within rO ` κ2 ´1 logp1{ q ¨ 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 0, 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 .
As alluded to above, we analyze networks with d inputs, k outputs, and m ě maxtd, ku 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-
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 to requiring wider networks, only hold with high probability for random transformations.

heading: 1.1 ADDITIONAL RELATED WORK
text: 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 nonconvex and nonsmooth (e.g., neural networks with ReLU/LeakyReLU activation), thus it is fundamentally difficult to characterize the optimization trajectory and convergence performance of GD and SGD. Some early work (Andoni et al., 2014; Daniely, 2017) showed that wide enough (polynomial in sample size n) neural networks trained by GD/SGD can learn a 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 et al., 2018). However, the assumptions made in these works are rather strong and not consistent with practice. For example, Tian (2017); Du et al. (2018b); 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, as 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 et al. (2019); Zou et al. (2019) generalized the global convergence results to multi-layer over-parameterized ReLU networks. Chizat et al. (2019) showed that training over-parameterized neural networks actually belongs to a so-called “lazy training” regime, in which the model behaves like its linearization around the initialization. Furthermore, the parameter scaling is more essential than over-paramterization 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-parameterization 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. (2019); Du et al. (2019); 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-parameterization 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 dependence on the training sample size n. Besides, the results in Allen-Zhu et al. (2019); Zhang et al. (2019) also require that all data points are separated by a 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 n. 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.
1In Daniely (2017), the weight changes in all hidden layers make negligible contribution to the final output, thus can be approximately treated as only training the output layer.
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 on the last layer and identity initialization for the 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 et 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 a generic condition on the input and output linear transformations for ensuring global convergence. Wu et al. (2019) assumes whitened data and proves a OpL3 logp1{ qq bound on the number of iterations required for GD to converge, where we establish a Oplogp1{ qq2 bound.

heading: 1.2 NOTATION.
text: We use lower case, lower case bold face, and upper case bold face letters to denote scalars, vectors and matrices respectively. For a positive integer, we denote the set t1, . . . , ku by rks. Given a vector x, we use }x}2 to denote its `2 norm. We use Npµ, σ2q to denote the Gaussian distribution with mean µ and variance σ2. Given a matrix X, we denote }X}F , }X}2 and }X}2,8 as its Frobenious norm, spectral norm and `2,8 norm (maximum `2 norm over its columns), respectively. In addition, we denote by σminpXq, σmaxpXq and σrpXq the smallest, largest and r-th largest singular values of X respectively. For a square matrix A, we denote by λminpAq and λmaxpAq the smallest and largest eigenvalues of A respectively. For two sequences takukě0 and tbkukě0, we say ak “ Opbkq if ak ď C1bk for some absolute constant C1, and use ak “ Ωpbkq if ak ě C2bk for some absolute constant C2. Except the target error , we use rOp¨q and rΩp¨q to hide the logarithmic factors in Op¨q and Ωp¨q respectively.

heading: 2 PROBLEM SETUP
text: Model. In this work, we consider deep linear ResNets defined as follows: fWpxq “ BpI`WLq . . . pI`W1qAx,
where x P Rd is the input, fWpxq P Rk is the corresponding output, A P Rmˆd,B P Rkˆm denote the weight matrices of input and output layers respectively, and W1, . . . ,WL P Rmˆm denote the weight matrices of all hidden layers. The formulation of ResNets in 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 be wider by choosing the dimensions of A and B appropriately.
Loss Function. Let tpxi,yiqui“1,...,n be the training dataset, X “ px1, . . . ,xnq P Rdˆn be the input data matrix and Y “ py1, . . . ,ynq P Rkˆn be the corresponding output label matrix. We assume the data matrix X is of rank r, where r can be smaller than d. Let W “ tW1, . . . ,WLu be the collection of weight matrices of all hidden layers. For an example px,yq, we consider the square loss defined by
`pW; x,yq “ 1 2 }fWpxq ´ y}22.
Then the training loss over the training dataset takes the following form
LpWq :“ n ÿ
i“1 `pW; xi,yiq “
1 2 }BpI`WLq ¨ ¨ ¨ pI`W1qAX´Y}2F .
Algorithm. Similar to Allen-Zhu et 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 A 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 at 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 1.
2Considering whitened data immediately gives κ “ 1.
Algorithm 1 (Stochastic) Gradient descent with zero initialization 1: input: Training data txi,yiuiPrns, step size η, total number of iterations T , minibatch size B,
input and output weight matrices A and B. 2: initialization: For all l P rLs, each entry of weight matrix Wp0ql is initialized as 0. Gradient Descent 3: for t “ 0, . . . , T ´ 1 do 4: Wpt`1ql “ W ptq l ´ η∇WlLpWptqq for all l P rLs 5: end for 6: output: WpT q Stochastic Gradient Descent 7: for t “ 0, . . . , T ´ 1 do 8: Uniformly sample a subset Bptq of size B from training data without replacement. 9: For all ` P rLs, compute the stochastic gradient Gptql “ n B ř
iPBptq ∇Wl`pWptq; xi,yiq 10: For all l P rLs, Wpt`1ql “ W ptq l ´ ηG ptq l 11: end for 12: output: tWptqut“0,...,T

heading: 3 MAIN THEORY
text: It is clear that the expressive power of deep linear ResNets is identical to 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 is to show that GD/SGD can converge to a point W˚ with
LpW˚q “ min ΘPRkˆd
1 2 }ΘX´Y}2F ,
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.

heading: 3.1 CONVERGENCE GUARANTEE OF GRADIENT DESCENT
text: The following theorem establishes the global convergence of GD for training deep linear ResNets. Theorem 3.1. There are absolute constants C and C1 such that, if the input and output weight matrices satisfy
σ2minpAqσ2minpBq }A}2}B}2 ě C }X}2
` LpWp0qq ´ LpW˚q ˘1{2
σ2rpXq and the step size satisfies
η ď C1 ¨ 1
L}A}2}B}2}X}2 ¨ `
a LpWp0qq ` }A}2}B}2}X}2 ˘ ,
then for all iterates of GD in Algorithm 1, it holds that
LpWptqq ´ LpW˚q ď ˆ 1´ ηLσ 2 minpAqσ2minpBqσ2rpXq
e
˙t
¨ ` LpWp0qq ´ LpW˚q ˘ .
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 in Bartlett et al. (2019), we choosem “ d “ k, A “ I,B “ I, LpW˚q “ 0 and XXJ “ I. Then it can be easily observed that the condition in Theorem 3.1 becomes LpWp0qq ´ LpW˚q ď C´2. This implies that the global convergence can be established as long as LpWp0qq ´ LpW˚q is smaller than some constant, which is equivalent to the condition proved in Bartlett et al. (2019).
In general, LpWp0qq ´ LpW˚q can be large and thus the setting considered in Bartlett et al. (2019) may not be able to guarantee global convergence. Therefore, it is natural to ask in which setting
the condition on 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.e., each entry in A is independently generated from Np0, 1{mq and each entry in B is generated from Np0, 1{kq. Based on this choice of transformations, 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., LpWp0qq). The following proposition is proved in Section A.2. Proposition 3.3. In Algorithm 1, if each entry in A is independently generated from Np0, α2q and each entry in B is independently generated from Np0, β2q, then if m ě C ¨ pd` k ` logp1{δqq for some absolute constant C, with probability at least 1´ δ, it holds that σminpAq “ Ωpα ? mq, σmaxpAq “ Opα ? mq, σminpBq “ Ω ` β ? m ˘ , σmaxpBq “ O ` β ? m ˘ ,
and LpWp0qq ď O ` α2β2km logpn{δq}X}2F ` }Y}2F ˘ .
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 }Y}F “ Op}X}F q. Then using Gaussian random input and output transformations in Proposition 3.3 with α “ β “ 1, if the neural network width satisfies m “ Ωpmaxtkrκ2 logpn{δq, k ` d` logp1{δquq then, with probability at least 1´ δ, the output of GD in Algorithm 1 achieves training loss at most LpW˚q ` within T “ O ` κ logp1{ q ˘
iterations, where κ “ }X}22{σ2rpXq 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 -suboptimal global minima within T “ Ωpκ logp1{ qq iterations if the neural network width satisfies m “ OpLkrκ3 ` dq. In stark contrast, training 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 OpLκq. This improvement may in part validate the empirical advantage of deep ResNets.

heading: 3.2 CONVERGENCE GUARANTEE OF STOCHASTIC GRADIENT DESCENT
text: 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 ă δ ď 1{6 and ą 0, if the input and output weight matrices satisfy
σ2minpAqσ2minpBq }A}2}B}2 ě C ¨ n}X}2 ¨ logpLpW p0qq{ q Bσ2rpXq ¨ b LpWp0qq,
and the step size and maximum iteration number are set as
η ď C1 ¨ Bσ2minpAqσ2minpBqσ2rpXq
Ln}A}42}B}42}X}22 ¨min
"
}X}22,8LpW˚q ,
B
n}X}22 ¨ logpT {δq logpLpWp0qq{ q
*
,
T “ C2 ¨ 1
ηLσ2minpAqσ2minpBqσ2rpXq ¨ log
ˆ LpWp0qq ´ LpW˚q ˙
,
then with probability3 at least 1{2 (with respect to the random choices of mini batches), SGD in Algorithm 1 can find a network that achieves training loss at most LpW˚q ` .
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 “ Op}X}F q. Then using Gaussian random input and output transformations in Proposition 3.3 with α “ β “ 1, for sufficiently small ą 0, if the neural network width satisfies m “ rΩ ` krκ2 log2p1{ q ¨n2{B2`d ˘
, with constant probability, SGD in Algorithm 1 can find a point that achieves training loss at most LpW˚q` within T “ rO ` κ2 ´1 logp1{ q ¨n{B ˘ iterations. 3One can boost this probability to 1´ δ by independently running logp1{δq copies of SGD in Algorithm 1.
From Corollaries 3.7 and 3.4, we can see that compared with the convergence guarantee of GD, the condition on the neural network width for SGD is worse by a factor of rOpn2 log2p1{ q{B2q and the iteration complexity is higher by a factor of rOpκ ´1 ¨ n{Bq. This is 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.
We further consider the special case that LpW˚q “ 0, which implies that there exists a ground truth matrix Φ such that for each training data point pxi,yiq we have yi “ Φxi. In this case, we have the following theorem, which shows that SGD can attain a linear rate to converge to the global minimum. Theorem 3.8. There are absolute constants C, and C1 such that for any 0 ă δ ă 1, if the input and output weight matrices satisfy
σ2minpAqσ2minpBq }A}2}B}2 ě C ¨ n}X}2 Bσ2rpXq ¨ b LpWp0qq,
and the step size is set as
η ď C1 ¨ B2σ2minpAqσ2minpBqσ2rpXq
Ln2}A}42}B}42}X}42 ¨ logpT {δq ,
for some maximum iteration number T , then with probability at least 1´ δ, the following holds for all t ď T ,
LpWptqq ď 2LpWp0qq ¨ ˆ 1´ ηLσ 2 minpAqσ2minpBqσ2rpXq
e
˙t
.
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 }Y}F “ Op}X}F q. Then using Gaussian random transformations in Proposition 3.3 with α “ β “ 1, for any ď rO `
B}X}22,8{pn}X}22q ˘
, if the neural network width satisfies m “ rΩ ` krκ2 ¨ n2{B2 ` d ˘
, with high probability, SGD in Algorithm 1 can find a network that achieves training loss at most within T “ rO ` κ2 logp1{ q ¨ n2{B2 ˘ iterations.

heading: 4 DISCUSSION ON DIFFERENT INPUT AND OUTPUT LINEAR TRANSFORMATIONS
text: In this section, we will discuss several different choices of linear transformations at input and output layers and their effects to the convergence performance. For simplicity, we will only consider the condition for GD.
As we stated in Subsection 3.1, GD converges if the input and output weight matrices A and B
σ2minpAqσ2minpBq }A}2}B}2 ě C ¨ }X}2 σ2rpXq ¨ ` LpWp0qq ´ LpW˚q ˘1{2 . (4.1)
Then it is interesting to figure out what kind of choice of A 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 transformations.
Identity transformations. We first consider the transformations that A “ rIdˆd,0dˆpm´dqsJ and B “ a
m{k ¨ rIkˆk,0kˆpm´kqs. which is equivalent to the setting in Bartlett et al. (2019) when m “ k “ d. Then it is clear that
σminpBq “ σmaxpBq “ a m{k and σminpAq “ σmaxpAq “ 1.
Now let us consider LpWp0qq. By our choices of B and A and zero initialization on weight matrices in hidden layers, in the case that d “ k, we have
LpWp0qq “ 1 2 }BAX´Y}2F “ 1 2 › › a m{kX´Y › › 2 F .
We remark that › ›
a
m{kX´Y › ›
2 F {2 could be as big as 12 ` m}X}2F {k ` }Y}2F ˘
(for example, when X and Y are orthogonal). Then plugging these results into (4.1), the condition on A and B becomes
a m{k ě C ¨ }X}2 σ2rpXq ¨ ˆ 1 2 ` m}X}2F {k ` }Y}2F ˘ ´ LpW˚q ˙1{2 ě C ¨ }X}2 σ2rpXq ¨ c m}X}2F 2k ,
where the second inequality is due to the fact that LpW˚q ď }Y}2F {2. Then it is clear if }X}F ě? 2{C, the above inequality cannot be satisfied for any choice of m, since it 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 in (Bartlett et al., 2019). Note that replacing the scaling factor a
m{k in the definition of B with any other function of d, k and m would not help.
Modified identity transformations. In fact, we show that a different type of identity transformations of A and B can satisfy the condition (4.1). Here we provide one such example. Assuming m ě d`k, we can construct two sets S1,S2 Ă rms satisfying |S1| “ d, |S2| “ k and S1XS2 “ H. Let S1 “ ti1, . . . , idu and S2 “ tj1, . . . , jku. Then we construct matrices A and B as follows:
Aij “ " 1 pi, jq “ pij , jq 0 otherwise Bij “ " α pi, jq “ pi, jiq 0 otherwise
where α is a parameter which will be specified later. In this way, it can be verified that BA “ 0, σminpAq “ σmaxpAq “ 1, and σminpBq “ σmaxpBq “ α. Thus it is clear that the initial training loss satisfies LpWp0qq “ }Y}2F {2. Then plugging these results into (4.1), the condition on A and B can be rewritten as
α ě C ¨ }X}2 σ2rpXq ¨ ` }Y}2F {2´ LpW˚q ˘1{2 .
The R.H.S. of the above inequality does not depend on α, which implies that we can choose sufficiently large α 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, a neural network with m “ d ` k suffices to guarantee the global convergence of GD. We further remark that similar analysis can be extended to SGD.

heading: 5 EXPERIMENTS
text: 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.

heading: 5.1 DIFFERENT INPUT AND OUTPUT TRANSFORMATIONS
text: To validate our theory, we performed simple experiment on 10-d synthetic data. Specifically, we randomly generate X P R10ˆ1000 from a standard normal distribution and set Y “ ´X ` 0.1 ¨ E, where each entry in E is independently generated from standard normal distribution. Consider 10-hidden-layer linear ResNets, we apply three input and output transformations including identity transformations, modified identity transformations and random transformations. We evaluate the convergence performances for these three choices of transformations and report the results in Figures 1(a)-1(b), 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. It 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 m hidden variables in each layer ever take a non-zero value, so that, no matter how large m is, effectively, m “ 10, and the lower bound of Bartlett et al. (2019) applies.

heading: 5.2 COMPARISON WITH STANDARD DEEP LINEAR NETWORKS
text: Then we 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 Lhidden-layer neural network with fixed width m. The convergence results are displayed in Figures
1(c)-1(d), where we consider different choices of L. For training linear ResNets, we found that the convergence performances are quite similar for different L, thus we only plot the convergence result for the largest one (e.g., L “ 20 for m “ 40 and L “ 100 for m “ 200). However, it can be 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 is m “ Opkrκ2q (please refer to Corollary 3.4), which has no dependency in L, while the condition for training standard linear network is m “ OpLkrκ3q (Du & Hu, 2019), which is linear in L.

heading: 6 CONCLUSION
text: In this paper, we 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 on the transformations, GD and SGD with zero initialization on all hidden weights can converge to the global minimum. In addition, we further 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 functions such as cross-entropy loss, and can potentially provide meaningful insights to the convergence analysis of deep non-linear ResNets.

heading: ACKNOWLEDGEMENT
text: We thank the anonymous reviewers and area chair for their helpful comments. This work was initiated when Q. Gu and P. Long attended the summer program on 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 IIS-1906169, BIGDATA IIS-1855099, and Salesforce Deep Learning Research Award. The views and conclusions contained in this paper are those of the authors and should not be interpreted as representing any funding agencies.

heading: A PROOF OF MAIN THEOREMS
text: We first provide the following lemma which proves upper and lower bounds on }∇WlLpWq}2F when W is staying inside a certain region. Its proof is in Section B.1.
Lemma A.1. For any weight matrices satisfying maxlPrLs }Wl}2 ď 0.5{L, it holds that,
}∇WlLpWq}2F ě 2
e σ2minpAqσ2minpBqσ2rpXq
` LpWq ´ LpW˚q ˘ ,
}∇WlLpWq}2F ď 2e}A}22}B}22}X}22 ` LpWq ´ LpW˚q ˘
}∇Wl`pW; xi,yiq}2F ď 2e}A}22}B}22}xi}22`pW; xi,yiq. In addition, the stochastic gradient Gl in Algorithm 1 satisfies
}Gl}2F ď 2en2}A}22}B}22}X}22
B2 LpWq,
where B is the minibatch size.
The gradient lower bound can be also interpreted as the Polyak-Łojasiewicz condition, which is essential to the linear convergence rate. The gradient upper bound is crucial to bound the trajectory length, since this lemma requires that maxlPrLs }Wl} ď 0.5{L.
The following lemma proves the smoothness property of the training loss function LpWq when W is staying inside a certain region. Its proof is in Section B.2.
Lemma A.2. For any two collections of weight matrices, denoted by ĂW “ tĂW1, . . . ,ĂWLu and W “ tW1, . . . ,WLu, satisfying maxlPrLs }Wl}F ,maxlPrLs }ĂWl}F ď 0.5{L that, it holds that
LpĂWq ´ LpWq ď L ÿ
l“1 x∇WlLpWq,ĂWl ´Wly
` L}A}2}B}2}X}2 `
a
2eLpWq ` 0.5e}A}2}B}2}X}2 ˘
L ÿ l“1 }ĂWl ´Wl}2F .
Based on these two lemmas, we are able to complete the proof of all theorems, which are provided as follows.

heading: A.1 PROOF OF THEOREM 3.1
text: Proof of Theorem 3.1. In order to simplify the proof, we use the short-hand notations λA, µA, λB and µB to denote }A}2, σminpAq, }B}2 and σminpBq respectively. Specifically, we rewrite the condition on A and B as follows
µ2Aµ 2 B
λAλB ě 4 ? 2e3}X}2 σ2rpXq ¨ ` LpWp0qq ´ LpW˚q ˘1{2 .
We prove the theorem by induction on the update number s, using the following two-part inductive hypothesis:
(i) maxlPrLs }W psq l }F ď 0.5{L,
(ii) LpWpsqq ´ LpW˚q ď ˆ 1´ ηLµ 2 Aµ 2 Bσ 2 rpXq
e
˙s
¨ ` LpWp0qq ´ LpW˚q ˘ .
First, it can be easily verified that this holds for s “ 0. Now, assume that the inductive hypothesis holds for s ă t. Induction for Part (i): We first prove that maxlPrLs }W ptq l }F ď 0.5{L. By triangle inequality and the update rule of gradient descent, we have
}Wptql }F ď t´1 ÿ
s“0 η}∇WlLpWpsqq}F
ď η t´1 ÿ
s“0
? 2eλAλB}X}2 ¨ ` LpWpsqq ´ LpW˚q ˘1{2
ď ? 2eηλAλB}X}2 ¨ ` LpWp0qq ´ LpW˚q ˘1{2 ¨ t´1 ÿ
s“0
ˆ
1´ ηLµ 2 Aµ 2 Bσ 2 rpXq
e
˙s{2
where the second inequality follows from Lemma A.1, and the third inequality follows from the inductive hypothesis. Since ? 1´ x ď 1´ x{2 for any x P r0, 1s, we further have
}Wptql }F ď ? 2eηλAλB}X}2 ¨ ` LpWp0qq ´ LpW˚q ˘1{2 ¨ t´1 ÿ
s“0
ˆ
1´ ηLµ 2 Aµ 2 Bσ 2 rpXq
2e
˙s
ď ?
8e3λAλB}X}2 Lµ2Aµ 2 Bσ 2 rpXq ¨ ` LpWp0qq ´ LpW˚q ˘1{2 .
Under the condition that µ2Aµ 2 B{pλAλBq ě 2 ? 8e3}X}2 ` LpWp0qq ´ LpW˚q ˘1{2{σ2rpXq, it can be readily verified that }Wptql }F ď 0.5{L. Since this holds for all l P rLs, we have proved Part (i) of the inductive step, i.e., maxlPrLs }W ptq l }F ď 0.5{L.
Induction for Part (ii): Now we prove Part (ii) of the inductive step, bounding the improvement in the objective function. Note that we have already shown that Wptq satisfies maxlPrLs }W ptq l }F ď 0.5{L, thus by Lemma A.2 we have
LpWptqq ď LpWpt´1qq ´ η L ÿ
l“1
› ›∇WlLpWpt´1qq › › 2
F
` η2LλAλB}X}2 ¨ `
b
eLpWpt´1qq ` 0.5eλAλB}X}2 ˘ ¨ L ÿ
l“1 }∇WlLpWpt´1qq}2F ,
where we use the fact that Wptql ´ W pt´1q l “ ´η∇WlLpWpl´1qq. Note that LpWpt´1qq ď LpWp0qq and the step size is set to be
η “ 1 2LλAλB}X}2 ¨ ` a eLpWp0qq ` 0.5eλAλB}X}2 ˘˘ ,
so that we have
LpWptqq ´ LpWpt´1qq ď ´η 2
L ÿ
l“1
› ›∇WlLpWpt´1qq › › 2
F
ď ´ηLµ 2 Aµ 2 Bσ 2 rpXq
e
` LpWpt´1qq ´ LpW˚q ˘ ,
where the second inequality is by Lemma A.1. Applying the inductive hypothesis, we get
LpWptqq ´ LpW˚q ď ˆ 1´ ηLµ 2 Aµ 2 Bσ 2 rpXq
e
˙
¨ ` LpWpt´1qq ´ LpW˚q ˘
ď ˆ 1´ ηLµ 2 Aµ 2 Bσ 2 rpXq
e
˙t
¨ ` LpWp0qq ´ LpW˚q ˘ , (A.1)
which completes the proof of the inductive step of Part (ii). Thus we are able to complete the proof.

heading: A.2 PROOF OF PROPOSITION 3.3
text: Proof of Proposition 3.3. We prove the bounds on the singular values and initial training loss separately.
Bounds on the singular values: Specifically, we set the neural network width as
m ě 100 ¨ `
a maxtd, ku ` a 2 logp12{δq ˘2
By Corollary 5.35 in Vershynin (2010), we know that for a matrix U P Rd1ˆd2 (d1 ě d2) with entries independently generated by standard normal distribution, with probability at least 1´ 2 expp´t2{2q, its singular values satisfy
a d1 ´ a d2 ´ t ď σminpUq ď σmaxpUq ď a d1 ` a d2 ` t.
Based on our constructions of A and B, we know that each entry of 1βB and 1 αA follows standard Gaussian distribution. Therefore, set t “ 2 a
logp12{δq and apply union bound, with probability at least 1´ δ{3, the following holds,
α `? m´ ? d´ 2 a logp12{δq ˘ ď σminpAq ď σmaxpAq ď α `? m` ? d` 2 a logp12{δq ˘ β `? m´ ? k ´ 2 a logp12{δq ˘ ď σminpBq ď σmaxpBq ď β `? m` ? k ` 2 a logp12{δq ˘ ,
where we use the facts that σminpκUq “ κσminpUq and σmaxpκUq “ κσmaxpUq for any scalar κ and matrix U. Then applying our choice of m, we have with probability at least 1´ δ{3, 0.9α ? m ď σminpAq ď σmaxpAq ď 1.1α ? m and 0.9β ? m ď σminpBq ď σmaxpBq ď 1.1β ? m.
This completes the proof of the bounds on the singular values of A 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 px,yq,
`pWp0q; x,yq “ 1 2 }BAx´ y}22 ď }BAx}22 ` }y}22. (A.2)
Since each entry of B is generated from N p0, β2q, conditioned on A, each entry of BAx is distributed according to N p0, β2||Ax||22q, so
}BAx}22 }Ax}22β2
follows a χ2k distribution. Applying a standard tail bound for χ2k distribution, we have, with probability at least 1´ δ1,
}BAx}22 }Ax}22 ď β2kp1` 2 a logp1{δ1q{k ` 2 logp1{δ1qq.
Note that by our bounds of the singular values, if m ě 100 ¨ ` a maxtd, ku ` a 2 logp8{δq ˘2
, we have with probability at least 1 ´ δ{3, }A}2 ď 1.1α ? m, thus, it follows that with probability at least 1´ δ1 ´ δ,
}BAx}22 ď 1.21α2β2km “ 1` 2 a logp1{δ1q ` 2 logp1{δ1q ‰ }x}22.
Then by union bound, it is evident that with probability 1´ nδ1 ´ δ{3,
}BAX}2F “ n ÿ
i“1 }BAxi}22 ď 1.21α2β2km
“ 1` 2 a logp1{δ1q ` 2 logp1{δ1q ‰ }X}2F .
Set δ1 “ δ{p3nq, suppose logp1{δ1q ě 1, we have with probability at least 1´ 2δ{3,
LpWp0qq “ 1 2 }BAX´Y}2F ď }BAX}2F ` }Y}2F ď 6.05α2β2km logp2n{δq}X}2F ` }Y}2F .
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.

heading: A.3 PROOF OF COROLLARY 3.4
text: Proof of Corollary 3.4. Recall the condition in Theorem 3.1:
σ2minpAqσ2minpBq }A}2}B}2 ě C ¨ }X}2 σ2rpXq ¨ ` LpWp0qq ´ LpW˚q ˘1{2 . (A.3)
By Proposition 3.3, we know that, with probability 1´ δ,
σ2minpAqσ2minpBq }A}2}B}2 “ Θ ` m ˘ ,
}X}2 σrpXq ¨ ` LpWp0qq ´ LpW˚q ˘1{2 “ O
˜
p a
km logpn{δq ` 1q}X}F }X}2 σrpXq
¸
.
Note that }X}F ď ? r}X}2, thus the condition (A.3) can be satisfied if m “ Ωpkrκ2 logpn{δqq where κ “ }X}22{σ2rpXq.
Theorem 3.1 implies that LpWptqq ´ LpW˚q ď after T “ O ´
1 ηLσ2minpAqσ2minpBqσ2rpXq log 1
¯
iterations. Plugging in the value of η, we get
T “ O ˜ }A}2}B}2}X}2 ¨ ` a LpWp0qq ` }A}2}B}2}X}2 ˘
σ2minpAqσ2minpBqσ2rpXq log
1
¸
.
By Proposition 3.3, we have
T “ O ˜ }A}2}B}2}X}2 ¨ ` a km logpn{δq}X}F ` }A}2}B}2}X}2 ˘
σ2minpAqσ2minpBqσ2rpXq log
1
¸
“ O ˜ }X}2 ¨ ` a km logpn{δq}X}F `m}X}2 ˘
mσ2rpXq log
1
¸
“ O ˜ }X}2 ¨ ` a kr logpn{δq{m}X}2 ` }X}2 ˘
σ2rpXq log
1
¸
“ O ˆ κ log 1 ˙
for m “ Ωpkr logpn{δqq, completing the proof.

heading: A.4 PROOF OF THEOREM 3.6
text: Proof of Theorem 3.6. The guarantee is already achieved by Wp0q if ě LpWp0qq ´ LpW˚q, so we may assume without loss of generality that ă LpWp0qq ´ LpW˚q. Similar to the proof of Theorem 3.1, we use the short-hand notations λA, µA, λB and µB to denote }A}2, σminpAq, }B}2 and σminpBq respectively. Then we rewrite the condition on A and B, and our choices of η and T as follows
µ2Aµ 2 B λAλB ě ? 8e3n}X}2 ¨ logpLpWp0qq{ 1q Bσ2rpXq ¨ b 2LpWp0qq
η ď Bµ 2 Aµ 2 Bσ 2 rpXq
6e3Lnλ4Aλ 4 B}X}22
¨min "
1
}X}22,8LpW˚q , log2p2qB 3n}X}22 ¨ logpT {δq logpLpWp0qq{ 1q * ,
T “ e ηLµ2Aµ 2 Bσ 2 rpXq ¨ log ˆ LpWp0qq ´ LpW˚q 1 ˙ ,
where we set 1 “ {3 for the purpose of the proof. We first prove the convergence guarantees on expectation, and then apply the Markov inequality.
For SGD, our guarantee is not made on the last iterate but the best one. Define Et to be the event that there is no s ď t such that LpWptqq ´ LpW˚q ď 1. If 1pEtq “ 0, then there is an iterate Ws with s ď t that achieves training loss within 1 of optimal. Similar to the proof of Theorem 3.1, we prove the theorem by induction on the update number s, using the following inductive hypothesis: either 1pEsq “ 0 or the following three inequalities hold,
(i) maxlPrLs }W psq l }F ď
? 2esηnλAλB}X}2
B ¨ a 2LpWp0qq¨
(ii) E “` LpWpsqq ´ LpW˚q ˘‰ ď ´ 1´ ηLµ 2 Aµ 2 Bσ 2 rpXq
e
¯s
¨ ` LpWp0qq ´ LpW˚q ˘
(iii) LpWpsqq ď 2LpWp0qq, where the expectation in Part (ii) is with respect to all of the random choices of minibatches. Clearly, if 1pEsq “ 0, we have already finished the proof since there is an iterate that achieves training loss
within 1 of optimal. Recalling that ă LpWp0qq ´ LpW˚q, it is easy to verify that the inductive hypothesis holds when s “ 0. For the inductive step, we will prove that if the inductive hypothesis holds for s ă t, then it holds for s “ t. When 1pEt´1q “ 0, then 1pEtq is also 0 and we are done. Therefore, the remaining part is to prove the inductive hypothesis for s “ t under the assumption that 1pEt´1q “ 1, which 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), we will prove that either this inequality holds or 1pEtq “ 0. Induction for Part (i): As we mentioned, this part will be proved under the assumption 1pEt´1q “ 1. Besides, combining Part (i) for s “ t ´ 1 and our choice of η and T implies that maxlPrLs }W pt´1q l }F ď 0.5{L. Then by triangle inequality, we have the following for }W ptq l }F ,
}Wptql }F ď }W pt´1q l }F ` η}G pt´1q l }F .
By Lemma A.1, we have
}Gpt´1ql }F ď ? 2enλAλB}X}2 B ¨ b LpWpt´1qq.
Then we have }Wptql }F ď ` }Wpt´1ql }F ` η}G pt´1q l }F ˘
ď }Wpt´1ql }F ` ? 2eηnλAλB}X}2 B ¨ b LpWpt´1qq. (A.4)
By Part (iii) for s “ t´ 1, we know that LpWpt´1qq ď 2LpWp0qq. Then by Part (i) for s “ t´ 1, it is evident that
}Wptql }F ď ? 2etηnλAλB}X}2 B ¨ b 2LpWp0qq¨. (A.5)
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 assumption 1pEt´1q “ 1. Thus, as mentioned earlier, the inductive hypothesis implies that maxlPrLs }W pt´1q l }F ď 0.5{L. By Part (i) for s “ t, which has been verified in (A.5), it can be proved that maxlPrLs }W ptq l }F ď 0.5{L, then we have the following by Lemma A.2,
LpWptqq ´ LpWpt´1qq ď ´η L ÿ
l“1
@ ∇WlLpWpt´1qq,G pt´1q l D
` η2LλAλB}X}2 ¨ `
b
eLpWpt´1qq ` 0.5eλAλB}X}2 ˘ ¨ L ÿ
l“1 }Gpt´1ql } 2 F .
(A.6) By our condition on A and B, it is easy to verify that
λAλB ě µ2Aµ 2 B λAλB ě 2
a
2e´1LpWp0qq }X}2 .
Then by Part (iii) for s “ t´ 1 (A.6) yields
LpWptqq ´ LpWpt´1qq ď ´η L ÿ
l“1
@ ∇WlLpWpt´1qq,G pt´1q l D ` eη2Lλ2Aλ2B}X}22 ¨ L ÿ
l“1 }Gpt´1ql } 2 F .
(A.7)
Taking expectation conditioning on Wpt´1q gives
E “ LpWptqq|Wpt´1q ‰ ´ LpWpt´1qq ď ´η L ÿ
l“1
› ›∇WlLpWpt´1qq}2F
` eη2Lλ2Aλ2B}X}22 L ÿ
l“1 E “ }Gpt´1ql } 2 F |Wpt´1q ‰ . (A.8)
Note that, for i sampled uniformly from t1, ..., nu, the expectation Er}Gpt´1ql }2F |Wpt´1qs can be upper bounded by
Er}Gpt´1ql } 2 F |Wpt´1qs “ E “ }Gpt´1ql ´∇WlLpW pt´1qq}2F |Wpt´1q ‰ ` }∇WlLpWpt´1qq}2F
ď n 2
B Er}∇Wl`pWpt´1q; xi,yiq}2F |Wpt´1qs ` }∇WlLpWpt´1qq}2F .
(A.9)
By Lemma A.1, we have
Er}∇Wl`pWpt´1q; xi,yiq}2F |Wpt´1qs ď 2eλ2Aλ2BEr}xi}22`pWpt´1q; xi,yiq|Wpt´1qs
ď 2eλ 2 Aλ 2 B
n
n ÿ i“1 }xi}22`pWpt´1q; xi,yiq
ď 2eλ2Aλ 2 B}X}22,8LpWpt´1qq
n .
Plugging the above inequality into (A.9) and (A.8), we get
E “ LpWptqq|Wpt´1q ‰ ´ LpWpt´1qq
ď ´η L ÿ
l“1
› ›∇WlLpWpt´1qq}2F
` eη2Lλ2Aλ2B}X}22 ¨ L ÿ
l“1
ˆ 2enλ2Aλ 2 B}X}22,8LpWpt´1qq
B ` }∇WlLpWpt´1qq}2F
˙
.
Recalling that η ď 1{p6eLλ2Aλ2B}X}22q, we have
E “ LpWptqq|Wpt´1q ‰ ´ LpWpt´1qq ď ´5η 6
L ÿ
l“1
› ›∇WlLpWpt´1qq}2F
` 2e2η2L2nλ4Aλ 4 B}X}22}X}22,8LpWpt´1qq
B . (A.10)
By Lemma A.1, we have L ÿ
l“1 }∇WlLpWpt´1qq}2F ě 2e´1Lµ2Aµ2Bσ2rpXq ` LpWpt´1qq ´ LpW˚q ˘ .
If we set
η ď Bµ 2 Aµ 2 Bσ 2 rpXq
6e3Lnλ4Aλ 4 B}X}22}X}22,8
, (A.11)
then (A.10) yields
E “ LpWptqq|Wpt´1q ‰ ´ LpWpt´1qq
ď ´5ηLµ 2 Aµ 2 Bσ 2 rpXq
3e
` LpWpt´1qq ´ LpW˚q ˘
` 2e2η2L2nλ4Aλ 4 B}X}22}X}22,8
` LpWpt´1qq ´ LpW˚q ˘
B
` 2e2η2L2nλ4Aλ 4 B}X}22}X}22,8LpW˚q B
ď ´4ηLµ 2 Aµ 2 Bσ 2 rpXq
3e
` LpWpt´1qq ´ LpW˚q ˘ ` 2e2η2L2nλ4Aλ 4 B}X}22}X}22,8LpW˚q BL2 . (A.12)
Define
γ0 “ 4Lµ2Aµ 2 Bσ 2 rpXq
3e , and γ1 “ 2e2η2L2nλ4Aλ 4 B}X}22}X}22,8LpW˚q B ,
rearranging (A.12) further gives
E “ LpWptqq|Wpt´1q ‰ ´ LpW˚q ď p1´ ηγ0q ¨ ` LpWptqq ´ LpW˚q ˘ ` η2γ1. (A.13) Therefore, setting the step size as
η ď γ0 1
4γ1 “ Bµ
2 Aµ 2 Bσ 2 rpXq
6e3Lnλ4Aλ 4 B}X}22}X}22,8
¨ 1
LpW˚q ,
we further have
E “ LpWptqq ´ LpW˚q|Wpt´1q ‰ ď “ p1´ ηγ0q ¨ rLpWpt´1qq ´ LpW˚qs ` η2γ1 ‰
ď p1´ 3ηγ0{4q ¨ rLpWpt´1qq ´ LpW˚qs, (A.14) where the second inequality is by (A.13) and the last inequality is by the fact that we assume 1pEt´1q “ 1, which implies that LpWpt´1qq´LpW˚q ě 1 ě 4γ1η{γ0. Further taking expectation over Wpt´1q, we get
E “ LpWptqq ´ LpW˚q ‰ ď p1´ 3ηγ0{4q ¨ E “ LpWpt´1qq ´ LpW˚q ‰
ď p1´ 3ηγ0{4qt ¨ ` LpWp0qq ´ LpW˚q ˘ ,
where the second inequality follows from Part (ii) for s “ t´ 1 and the assumption that 1pE0q “ 1. Plugging the definition of γ0, we are able to 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 LpWptqq ď 2LpWp0qq or 1pEtq “ 0, which is equivalent to LpWptqq ¨ 1pEtq ď 2LpWp0qq since LpWp0qq and LpWptqq are both positive. We will prove this by martingale inequality. Let Ft “ σtWp0q, ¨ ¨ ¨ ,Wptqu be a σ-algebra, and F “ tFtutě1 be a filtration. We first prove that ErLpWptqq1pEtq|Ft´1s ď LpWpt´1qq1pEt´1q. Apparently, this inequality holds when 1pEt´1q “ 0 since both sides will be zero. Then if 1pEt´1q “ 1, by (A.14) we have ErLpWptqq|Wpt´1qs ď LpWpt´1qq since LpW˚q is the global minimum. Therefore,
ErLpWptqq1pEtq|Ft´1,Wpt´1q,1pEt´1q “ 1s ď ErLpWptqq|Ft´1,1pEt´1q “ 1s ď LpWpt´1qq.
Combining these two cases, by Jensen’s inequality, we further have
E “ log ` LpWptqq1pEtq ˘ |Ft´1 ‰ ď log ` ErLpWptqq1pEtq|Ft´1s ˘
ď log ` LpWpt´1qq1pEt´1q ˘ ,
which implies that tlog ` LpWptqq ¨1pEtq ˘ utě0 is a super-martingale. Then we will upper bound the martingale difference log ` LpWptqq ¨ 1pEtq ˘ ´ log ` LpWpt´1qq ¨ 1pEt´1q ˘
. Clearly this quantity would be zero if 1pEt´1q “ 0. Then if 1pEt´1q “ 1, by (A.7) we have
LpWptqq ď LpWpt´1qq ` η L ÿ
l“1 }∇WlLpWpt´1qq}F }G pt´1q l }F ` eη 2Lλ2Aλ 2 B}X}22
L ÿ l“1 }Gpt´1ql } 2 F .
By Part (i) for s “ t´ 1, Lemma A.1, we further have
LpWptqq ď ˆ 1` 2eηLnλ 2 Aλ 2 B}X}22 B ` 2e 2n2η2L2λ4Aλ 4 B}X}42 B2 ˙ LpWpt´1qq
ď ˆ 1` 3eηnLλ 2 Aλ 2 B}X}22
B
˙
LpWpt´1qq, (A.15)
where the second inequality follows from the choice of η that
η ď B 2enLλ2Aλ 2 B}X}22 .
Using the fact that 1pEtq ď 1 and 1pEt´1q “ 1, we further have
log ` LpWptqq ¨ 1pEtq ˘ ď log ` LpWpt´1qq ¨ 1pEt´1q ˘ ` 3eηLnλ 2 Aλ 2 B}X}22
B ,
which also holds for the case 1pEt´1q “ 0. Recall that tlog ` LpWptqq ¨ 1pEtq ˘ utě0 is a supermartingale, thus by one-side Azuma’s inequality, we have with probability at least 1´ δ1,
log ` LpWptqq ¨ 1pEtq ˘ ď log ` LpWp0qq ˘ ` 3eηLnλ 2 Aλ 2 B}X}22
B ¨ a 2t logp1{δ1q.
Setting δ1 “ δ{T , using the fact that t ď T and leveraging our choice of T and η, we have with probability at least 1´ δ{T ,
? Tη “ logp2qB
3e a 2 logpδ{T qLnλ2Aλ2B}X}22 ,
which implies that
LpWptqq1pEtq ď exp ” log ` LpWp0qq ˘ ` logp2q ı ď 2LpWp0qq. (A.16)
This completes the proof of the inductive step of Part (iii).
Note that this result holds with probability at least 1 ´ δ{T . Thus applying union bound over all iterates tWptqut“0,...,T yields that all induction arguments hold for all t ď T with probability at least 1´ δ. Moreover, plugging our choice of T and η into Part (ii) gives
E “ LpWptqq ´ LpW˚q ‰ ď 1.
By Markov inequality, we further have with probability at least 2{3, it holds that rLpWpT qq ´ LpW˚qs¨1pEtq ď 3 1 “ . Therefore, by union bound (together with the high probability arguments of (A.16)) and assuming δ ă 1{6, we have with probability at least 2{3´δ ě 1{2, one of the iterates of SGD can achieve training loss within 1 of optimal. This completes the proof.

heading: A.5 PROOF OF COROLLARY 3.7
text: Proof of Corollary 3.7. Recall the condition in Theorem 3.6:
σ2minpAqσ2minpBq }A}2}B}2 ě C ¨ n}X}2 ¨ logpLpW p0qq{ q Bσ2rpXq ¨ b LpWp0qq, (A.17)
Then plugging in the results in Proposition 3.3 and the fact that }X}F ď ? r}X}2, we obtain that condition (A.17) can be satisfied if m “ O ` krκ2 log2p1{ q ¨B{n ˘ .
In addition, consider sufficiently small such that ď rO ` B}X}22,8{pn}X}22q ˘
, then and use the fact that }X}2,8 ď }X}2 we have η “ O ` kB {pLmnκ}X}22q ˘
based on the results in Proposition 3.3. Then in order to achieve -suboptimal training loss, the iteration complexity is
T “ e ηLσ2minσ 2 minpBqσ2rpXq log
ˆ LpWp0q ´ LpW˚qq ˙
“ O ` κ2 ´1 logp1{ q ¨ n{B ˘ .
This completes the proof.

heading: A.6 PROOF OF THEOREM 3.8
text: Proof of Theorem 3.8. Similar to the proof of Theorem 3.6, we set the neural network width and step size as follows,
µ2Aµ 2 B
λAλB ě 4 ? 2e3n}X}2 Bσ2rpXq ¨ b 2LpWp0qq
η ď logp2qB 2µ2Aµ 2 BpBqσ2rpXq
54e3Ln2λ4Aλ 4 B}X}42 ¨ logpT {δq
,
where λA, µA, λB and µB denote }A}2, σminpAq, }B}2 and σminpBq 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 t, using the following two-part inductive hypothesis:
(i) maxlPrLs }W ptq l }F ď 0.5{L
(ii) LpWptqq ď 2LpWp0qq ¨ ´ 1´ sηLµ 2 Aµ 2 Bσ 2 rpXq
e
¯s
.
Induction for Part (i) We first prove that maxlPrLs }W ptq l }F ď 0.5{L. By triangle inequality and the update rule of SGD, we have
}Wptql }F ď t´1 ÿ
s“0 η}Gl}F
ď η t´1 ÿ
s“0
? 2enλAλB}X}2
B
` LpWpsqq ´ LpW˚q ˘1{2
ď ?
2eηnλAλB}X}2 B ¨ ` LpWp0qq ´ LpW˚q ˘1{2 ¨
t´1 ÿ
s“0
ˆ
1´ ηLµ 2 Aµ 2 Bσ 2 rpXq
2e
˙s
ď ?
8e3nλAλB}X}2 BLµ2Aµ 2 Bσ 2 rpXq ¨ ` LpWp0qq ´ LpW˚q ˘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 p1´ xq1{2 ď 1´ x{2 for all x P r0, 1s. Then applying our choice of m implies that }Wptql }F ď 0.5{L. Induction for Part (ii) Similar to Part (ii) and (iii) of the induction step in the proof of Theorem 3.6, we first prove the convergence in expectation, and then use Azuma’s inequality to get the highprobability based results. It can be simply verfied that
λAλB ě µ2Aµ 2 B λAλB ě 4
? 2e3n}X}2 ¨ logpLpWp0qq{ q
Bσ2rpXq ¨ b
2LpWp0qq ě 2 a 2e´1LpWp0qq }X}2
η ď logp2qB 2µ2Aµ 2 BpBqσ2rpXq
96e3Ln2λ4Aλ 4 B}X}42 ¨ logpT {δq
ď Bµ 2 Aµ 2 Bσ 2 rpXq
6e3Lnλ4Aλ 4 B}X}22}X}22,8
.
Thus, we can leverage (A.12) and obtain
E “ LpWptqq|Wpt´1q ‰ ´ LpWpt´1qq ď ´4ηLµ 2 Aµ 2 Bσ 2 rpXq
3e LpWpt´1qq,
where we use the fact that LpW˚q “ 0. Then by Jensen’s inequality, we have
E “ log ` LpWptqq ˘ |Wpt´1q ‰ ď log ` LpWpt´1qq ˘ ` log ˆ 1´ 4ηLµ 2 Aµ 2 Bσ 2 rpXq
3e
˙
,
ď log ` LpWpt´1qq ˘ ´ 4ηLµ 2 Aµ 2 Bσ 2 rpXq
3e ,
where the second inequality is by logp1 ` xq ď x. Then similar to the proof of Theorem 3.6, we are going to apply martingale inequality to prove this part. Let Ft “ σtWp0q, ¨ ¨ ¨ ,Wptqu be a σ-algebra, and F “ tFtutě1 be a filtration, the above inequality implies that
E “ log ` LpWptqq ˘ |Ft´1 ‰ ` 4tηLµ 2 Aµ 2 Bσ 2 rpXq
3e ď log
` LpWpt´1qq ˘ ` 4pt´ 1qηLµ 2 Aµ 2 Bσ 2 rpXq
3e ,
(A.18)
which implies that log ` LpWptqq ˘ ` 4tηLµ2Aµ2Bσ2rpXq{p3eq (
is a super-martingale. Besides, by (A.15), we can obtain
log ` LpWptqq ˘ ď log ` LpWpt´1qq ˘ ` 3eηLnλ 2 Aλ 2 B}X}22
B ,
which implies that
log ` LpWptqq ˘ ` 4tηLµ 2 Aµ 2 Bσ 2 rpXq
3e
ď log ` LpWpt´1qq ˘ ` 4pt´ 1qηLµ 2 Aµ 2 Bσ 2 rpXq 3e ` 4eηLnλ 2 Aλ 2 B}X}22 B ,
where we again use the fact that logp1 ` xq ď x. Thus, by the one-sided Azuma’s inequality we have with probability at least 1´ δ1 that
log ` LpWptqq ˘ ď log ` LpWp0qq ˘ ´ 4tηLµ 2 Aµ 2 Bσ 2 rpXq 3e ` 4eηLnλ 2 Aλ 2 B}X}22 B ¨ a 2t logp1{δ1q
ď log ` LpWp0qq ˘ ´ tηLµ 2 Aµ 2 Bσ 2 rpXq e ` 96e 3ηLn2λ4Aλ 4 B}X}42 logp1{δ1q
B2µ2Aµ 2 Bσ 2 rpXq
ď log ` LpWp0qq ˘ ´ tηLµ 2 Aµ 2 Bσ 2 rpXq
e ` logp2q,
where the second inequality follows from the fact that ´at` b ? t ď b2{a, and the last inequality is by our choice of η that
η ď logp2qB 2µ2Aµ 2 BpBqσ2rpXq
96e3Ln2λ4Aλ 4 B}X}42 ¨ logp1{δ1q
.
Then it is clear that with probability at least 1´ δ1,
LpWptqq ď 2LpWp0qq ¨ exp ˆ ´ tηLµ 2 Aµ 2 Bσ 2 rpXq
e
˙
, (A.19)
which completes the induction for Part (ii).
Similar to the proof of Theorem 3.6, (A.19) holds with probability at least 1´ δ1 for a given t. Then we can set δ1 “ δ{T and apply union bound such that with probability at least 1 ´ δ, (A.19) holds for all t ď T . This completes the proof.

heading: A.7 PROOF OF COROLLARY 3.9
text: Proof of Corollary 3.9. Recall the condition in Theorem 3.8:
σ2minpAqσ2minpBq }A}2}B}2 ě C ¨ n}X}2 Bσ2rpXq ¨ b LpWp0qq, (A.20)
Then plugging in the results in Proposition 3.3 and the fact that }X}F ď ? r}X}2, we obtain that condition (A.17) can be satisfied if m “ O ` krκ2 ¨B{n ˘ .
In addition, it can be computed that η “ O ` kB2{pLmn2κ}X}22q ˘
based on the results in Proposition 3.3. Then in order to achieve -suboptimal training loss, the iteration complexity is
T “ e ηLσ2minσ 2 minpBqσ2rpXq log
ˆ LpWp0qq ´ LpW˚q ˙
“ O ` κ2 logp1{ q ¨ n2{B2 ˘ .
This completes the proof.

heading: B PROOFS OF TECHNICAL LEMMAS

heading: B.1 PROOF OF LEMMA A.1
text: We first note the following useful lemmas. Lemma B.1 (Claim B.1 in Du & Hu (2019)). Define Φ “ arg minΘPRkˆd }ΘX ´Y}2F , then for any U P Rkˆd it holds that
}UX´Y}2F “ }UX´ΦX}2F ` }ΦX´Y}2F .
Lemma B.2 (Theorem 1 in Fang et al. (1994)). Let U,V P Rdˆd be two positive definite matrices, then it holds that
λminpUqTrpVq ď TrpUVq ď λmaxpUqTrpVq.
The following lemma is proved in Section B.3.
Lemma B.3. Let U P Rdˆr be a rank-r matrix. Then for any V P Rrˆk, it holds that σminpUq}V}F ď }UV}F ď σmaxpUq}V}F .
Proof of Lemma A.1. Proof of gradient lower bound: We first prove the gradient lower bound. Let U “ BpI`WLq . . . pI`W1qA, by Lemma B.1 and the definition of LpW˚q, we know that there exist a matrix Φ P Rkˆd such that
LpWq “ 1 2 }UX´ΦX}2F ` LpW˚q. (B.1)
Therefore, based on the assumption that maxlPrLs }Wl}F ď 0.5{L, we have
}∇WlLpWq}2F “ › › “ BpI`WLq ¨ ¨ ¨ pI`Wl`1q ‰J` UX´ΦX ˘“ pI`Wl´1q ¨ ¨ ¨AX ‰J› › 2
F
ě σ2minppI`WLq ¨ ¨ ¨ pI`Wl`1qq ¨ σ2min ` pI`Wl´1q ¨ ¨ ¨ pI`W1q ˘
¨ }BJpU´ΦqXXJAJ}2F ě ` 1´ 0.5{L ˘2L´2}BJpU´ΦqXXJAJ}2F ,
where the last inequality follows from the fact that σminpI `Wlq ě 1 ´ }Wl}2 ě 1 ´ }Wl}F ě 1´ 0.5{L. Applying Lemma B.2, we get
}BJpU´ΦqXXJAJ}2F “ Tr ` BBJpU´ΦqXXJAJAXXJpU´ΦqJ ˘
ě λminpBBJq ¨ Tr ` AJAXXJpU´ΦqJpU´ΦqXXJ ˘
ě λminpBBJq ¨ λminpAJAq ¨ }pU´ΦqXXJ}2F .
Note that X is of r-rank, thus there exists a full-rank matrix rX P Rdˆr such that rXrXJ “ XXJ. Thus we have
}pU´ΦqX}2F “ Tr ` pU´ΦqXXJpU´ φqJ ˘ “ Tr ` pU´ΦqrXrXJpU´ φqJ ˘ “ › ›pU´ΦqrX › › 2 F .
(B.2)
Therefore,
}pU´ΦqXXJ}2F “ › ›pU´ΦqrXrXJ › › 2
F
“ Tr ` pU´ΦqrXrXJ rXrXJpU´ΦqJ ˘
ě λminprXJ rXq ¨ }pU´ΦqrX}2F “ 2σ2rpXq ¨ pLpWq ´ LpW˚qq, (B.3)
where the inequality follows from Lemma B.2 and the last equality follows from (B.2), (B.1) and the fact that λminprXJ rXq “ λrpXXJq “ σ2rpXq. Note that we assume d, k ď m and d ď n. Thus it follows that λminpBBJq “ σ2minpBq and λminpAJAq “ σ2minpAq. Then putting everything together, we can obtain
}∇WlLpWq}2F ě 2σ2minpBqσ2minpAqσ2rpXqp1´ 0.5{Lq2L´2 ` LpW ´ LpW˚q ˘ .
Then using the inequality p1 ´ 0.5{Lq2L´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. Specifically, Lemma B.3 implies
}∇WlLpWq}2F “ › › “ BpI`WLq ¨ ¨ ¨ pI`Wl`1q ‰J` UX´ΦX ˘“ pI`Wl´1q ¨ ¨ ¨AX ‰J› › 2
F
ď σ2maxppI`WLq ¨ ¨ ¨ pI`Wl`1qq ¨ σ2max ` pI`Wl´1q ¨ ¨ ¨ pI`W1q ˘
¨ }BJpU´ΦqXXJAJ}2F ď σ2maxppI`WLq ¨ ¨ ¨ pI`Wl`1qq ¨ σ2max ` pI`Wl´1q ¨ ¨ ¨ pI`W1q ˘
¨ }B}22}A}22 ¨ }pU´ΦqXXJ}2F ď p1` 0.5{Lq2L´2}B}22}A}22 ¨ }pU´ΦqXXJ}2F ,
where the last inequality is by the assumption that maxlPrLs }Wl}F ď 0.5{L. By (B.3), we have
}pU´ΦqXXJ}2F “ › ›pU´ΦqpXXJq1{2pXXJq1{2 › › 2
F
ď λmaxpXXJq ¨ }pU´ΦqpXXJq1{2}2F “ λmaxpXXJq ¨ }pU´ΦqX}2F “ 2}X}22 ¨ pLpWq ´ LpW˚qq,
where the inequality is by Lemma B.3 and the second equality is by (B.2). Therefore, combining the above results yields
}∇WlLpWq}2F ď 2σ2maxpBqσ2maxpAq}X}22p1` 0.5{Lq2L´2 ` LpW ´ LpW˚q ˘ .
Using the inequality p1 ` 0.5{Lq2L´2 ď p1 ` 0.5{Lq2L ď e, we are able to complete the proof of gradient upper bound.
Proof of the upper bound of }∇Wl`pW; xi,yiq}2F : Let U “ BpI ` WLq ¨ ¨ ¨ pI ` W1qA, we have
∇Wl`pW; xi,yiq “ “ BpI`WLq ¨ ¨ ¨ pI`Wl`1q ‰JpUxi ´ yiq “ pI`Wl´1q ¨ ¨ ¨Ax̄i ‰J .
Therefore, by Lemma B.3, we have
}∇Wl`pW; xi,yiq}2F ď σ2max ` pI`WLq ¨ pI`Wl`1q ˘ ¨ σ2max ` pI`Wl´1q ¨ ¨ ¨ pI`W1q ˘
¨ }BJpUxi ´ yiqxiAJ}2F ď p1` 0.5{Lq2L´2 ¨ }B}22}A}22}xi}22 ¨ }Uxi ´ yi}2F ď 2e}A}22}B}22}xi}22`pW; xi,yiq,
where the last inequality is by the fact that p1` 0.5{Lq2L´2 ď e. Proof of the upper bound of stochastic gradient: Define by B the set of training data points used to compute the stochastic gradient, then define by X̄ and Ȳ the stacking of txiuiPB and tyiuiPB respectively. Let U “ BpI`WLq ¨ ¨ ¨ pI`W1qA, the minibatch stochastic gradient takes form
Gl “ n
B
ÿ iPB ∇Wl`pW; xi,yiq
“ n B “ BpI`WLq ¨ ¨ ¨ pI`Wl`1q ‰JpUX̄´ Ȳq “ pI`Wl´1q ¨ ¨ ¨AX̄ ‰J .
Then by Lemma B.3, we have
}Gl}2F ď n2
B2 σ2max
` pI`WLq ¨ pI`Wl`1q ˘ ¨ σ2max ` pI`Wl´1q ¨ ¨ ¨ pI`W1q ˘
¨ }BJpUX̄´ ȲqX̄JAJ}2F
ď n 2
B2 ¨ p1` 0.5{Lq2L´2 ¨ }B}22}A}22}X̄}22 ¨ }UX̄´ Ȳ}2F
ď en 2
B2 }B}22}A}22}X̄}22 ¨ }UX̄´ Ȳ}2F .
where the second inequality is by the assumptions that maxlPrLs }Wl}F ď 0.5{L, and the last inequality follows from the the fact that p1 ` 0.5{Lq2L´2 ď p1 ` 0.5{Lq2L ď e. Note that X̄ and Ȳ are constructed by stacking B columns from X and Y respectively, thus we have }X̄}22 ď }X}22 and }UX̄´ Ȳ}2F ď }UX´Y}2F “ 2LpWq. Then it follows that
}Gl}2F ď 2en2
B2 }B}22}A}22}X}22 ¨ LpWq.
This completes the proof of the upper bound of stochastic gradient.

heading: B.2 PROOF OF LEMMA A.2
text: Proof of Lemma A.2. Let U “ BpI`WLq ¨ ¨ ¨ pI`W1qA and rU “ BpI` ĂWLq ¨ ¨ ¨ pI` ĂW1qA and ∆ “ rU´U. We have
LpĂWq ´ LpWq “ 1 2 ` }rUX´Y}2F ´ }UX´Y}2F ˘
“ 1 2 ` }pU`∆qX´Y}2F ´ }UX´Y}2F ˘ “ 1 2 ` }UX´Y `∆X}2F ´ }UX´Y}2F ˘ “ 1 2 ` }2xUX´Y,∆Xy ` }∆X}2F ˘
“ @ UX´Y, ` rU´U ˘ X D ` 1 2 › › ` rU´U ˘ X}2F . (B.4)
We begin by working on the first term. Let V “ pI`WLq ¨ ¨ ¨ pI`W1q and rV “ pI`ĂWLq ¨ ¨ ¨ pI` ĂW1q, so that rU´U “ BprV´VqA. Breaking down the effect of transforming V “ ś1 j“LpI`Wjq into rV “ ś1 j“LpI` ĂWjq into the effects of replacing one layer at a time, we get
rV ´V “ L ÿ
l“1
«˜
l`1 ź j“L pI`Wjq
¸˜
1 ź j“l pI` ĂWjq
¸ ´ ˜ l ź
j“L pI`Wjq
¸˜
1 ź
j“l´1 pI` ĂWjq
¸ff
and, for each l, pulling out a common factor of ´ śl`1 j“LpI`Wjq ¯´ ś1´l j“lpI` ĂWjq ¯ gives
rV ´V “ L ÿ
l“1 pI`WLq ¨ ¨ ¨ pI`Wl`1qpĂWl ´WlqpI` ĂWl´1q ¨ ¨ ¨ pI` ĂW1q
“ L ÿ
l“1 pI`WLq ¨ ¨ ¨ pI`Wl`1qpĂWl ´WlqpI`Wl´1q ¨ ¨ ¨ pI`W1q looooooooooooooooooooooooooooooooooooooooooomooooooooooooooooooooooooooooooooooooooooooon
V1
` L ÿ
l“1 pI`WLq ¨ ¨ ¨ pI`Wl`1qpĂWl ´Wlq looooooooooooooooooooooooomooooooooooooooooooooooooon
V2
¨ “ pI` ĂWl´1q ¨ ¨ ¨ pI` ĂW1q ´ pI`Wl´1q ¨ ¨ ¨ pI`W1q ‰ loooooooooooooooooooooooooooooooooooomoooooooooooooooooooooooooooooooooooon
V2
. (B.5)
The first term V1 satisfies
xUX´Y,BV1AXy
“ C UX´Y,B ˜ L ÿ
l“1 pI`WLq ¨ ¨ ¨ pI`Wl`1qpĂWl ´WlqpI`Wl´1q ¨ ¨ ¨ pI`W1q
¸
AX
G
“ L ÿ
l“1
A UX´Y,BpI`WLq ¨ ¨ ¨ pI`Wl`1qpĂWl ´WlqpI`Wl´1q ¨ ¨ ¨ pI`W1qAX E
“ L ÿ
l“1 TrppUX´YqJBpI`WLq ¨ ¨ ¨ pI`Wl`1qpĂWl ´WlqpI`Wl´1q ¨ ¨ ¨ pI`W1qAXq
“ L ÿ
l“1 TrppI`Wl´1q ¨ ¨ ¨ pI`W1qAXpUX´YqJBpI`WLq ¨ ¨ ¨ pI`Wl`1qpĂWl ´Wlqq
“ L ÿ
l“1
@ rBpI`WLq ¨ ¨ ¨ pI`Wl`1qsJpUX´YqrpI`Wl´1q ¨ ¨ ¨AXsJ,ĂWl ´Wl D
“ L ÿ
l“1 x∇WlLpWq,ĂWl ´Wly, (B.6)
where the first equality is by the definition of V1. Now we focus on the second term V2 of (B.5),
V2 “ L ÿ
l“1 pI`WLq ¨ ¨ ¨ pI`Wl`1qpĂWl ´Wlq
¨ l´1 ÿ
s“1 pI`Wl´1q ¨ ¨ ¨ pI`Ws`1qpĂWs ´WsqpI` ĂWs´1q ¨ ¨ ¨ pI` ĂW1q.
Recalling that }Wl}F , }ĂWl}F ď 0.5{L for all l P rLs, by triangle inequality we have
}V2}F ď p1` 0.5{LqL ¨ ÿ
l,sPrLs : ląs }ĂWl ´Wl}F ¨ }ĂWs ´Ws}F
ď p1` 0.5{LqL ¨ ˆ L ÿ
l“1 }ĂWl ´Wl}F
˙2
,
where we use the fact that ř l,sPrLs : ląs alas ď ř l,sPrLs alas “ ` ř l al ˘2
holds for all a1, . . . , aL ě 0. Therefore, the following holds regarding V2:
xUX´Y,BV2AXy ď }UX´Y}F }BV2AX}F ď a 2LpWq}B}2}A}2}X}2}V2}F
ď ? 2e a LpWq}B}2}A}2}X}2 ˆ L ÿ
l“1 }ĂWl ´Wl}F
˙2
(B.7)
where the third inequality follows from the fact that p1 ` 0.5{LqL “ p1 ` 0.5{LqL ď ? e. Next,
we are going to upper bound the second term of (B.4): 12}prU ´UqX} 2 F . Note that, since }prU ´ UqX}2F “ }BprV ´VqAX}2F ď }A}22}B}22}X}22}rV ´V}2F , it suffices to bound the norm }rV ´ V}F . By (B.5), we have
}rV ´V}F “ › › ›
›
L ÿ l“1 pI`WLq ¨ ¨ ¨ pI`Wl`1qpĂWl ´WlqpI` ĂWl´1q ¨ ¨ ¨ pI` ĂW1q › › › › F
ď p1` 0.5{LqL L ÿ
l“1 }ĂWl ´Wl}F . (B.8)
Plugging (B.6), (B.7) and (B.8) into (B.4), we have
LpĂWq ´ LpWq
“ @ UX´Y,BpV1 `V2qX D ` 1 2 › ›B ` rV ´V ˘ AX}2F
ď L ÿ
l“1 x∇WlLpWq,ĂWl ´Wly
` }A}2}B}2}X}2 `
a
2eLpWq ` 0.5e}A}2}B}2}X}2 ˘
˜
L ÿ l“1 }ĂWl ´Wl}F
¸2
ď L ÿ
l“1 x∇WlLpWq,ĂWl ´Wly
` L}A}2}B}2}X}2 `
a
2eLpWq ` 0.5e}A}2}B}2}X}2 ˘
L ÿ l“1 }ĂWl ´Wl}2F , (B.9)
where the last inequality is by Jesen’s inequality. This completes the proof.

heading: B.3 PROOF OF LEMMA B.3
text: Proof of Lemma B.3. Note that we have
}UV}2F “ TrpUVVJUJq “ TrpUJUVVJq.
By Lemma B.2, it is clear that
λminpUJUqTrpVVJq ď TrpUJUVVJq ď λmaxpUJUqTrpVVJq.
Since U P Rdˆr is of r-rank, thus we have λminpUJUq “ σ2minpUq. Then applying the facts that λmaxpUJUq “ σ2maxpUq and TrpVVJq “ }V}2F , we are able to complete the proof.

Review summaries:
This 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.  

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.