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. In addition, for the first time we establish the global convergence of SGD for training deep linear ResNets and prove a linear convergence rate when the global minimum is $0$. 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κ 2 q, 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} 2 2 {σ 2 r pXq 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 log 2 p1{ q¨n 2 {B 2˘, with constant probability, SGD can converge to the global minimum up to an -error within r O`κ 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 components 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. 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 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 " rI dˆd , 0 dˆpm´dq s J and B " a m{k¨rI kˆk , 0 kˆpm´kq s. which is equivalent to the setting in Bartlett et al. (2019) when m " k " d. Then it is clear that σ min pBq " σ max pBq " a m{k and σ min pAq " σ max pAq " 1. Now let us consider LpW p0q q. By our choices of B and A and zero initialization on weight matrices in hidden layers, in the case that d " k, we have {2 could be as big as F˘( for example, when X and Y are orthogonal). Then plugging these results into (4.1), the condition on A and B becomes where the second inequality is due to the fact that LpW˚q ď }Y} 2 F {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. Gaussian random initialization on hidden weights, where the input and output weights are generated by random initialization, and remain fixed throughout the training. 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 S 1 , S 2 Ă rms satisfying Then we construct matrices A and B as follows: where α is a parameter which will be specified later. In this way, it can be verified that BA " 0, σ min pAq " σ max pAq " 1, and σ min pBq " σ max pBq " α. Thus it is clear that the initial training loss satisfies LpW p0q q " }Y} 2 F {2. Then plugging these results into (4.1), the condition on A and B can be rewritten as 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. 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. when W is staying inside a certain region. Its proof is in Section B.1. Lemma A.1. Let τ " 1{L, then for any weight matrices satisfying max lPrLs }W l } 2 ď 0.5, it holds that, In addition, , the stochastic gradient G l in Algorithm 1 satisfies 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 max lPrLs }W l } ď 0.5. 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. Let τ " 1{L. Then for any two collections of weight matrices, denoted by Based on these two lemmas, we are able to complete the proof of all theorems, which are provided as follows.
Under certain condition on the input and output linear transformations, both GD and SGD can achieve global convergence for training deep linear ResNets. The authors study the convergence of gradient descent in training deep linear residual networks, and establish a global convergence of GD/SGD and linear convergence rates of SG/SGD. Study of convergence properties of GD and SGD on deep linear resnets, and proof that under certain conditions on the input and output transformations and with zero initialization, GD and SGD converges to global minima.