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.
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.
Comparison to Du & Hu
The 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.
1) 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?
2) 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?
3) 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?
Comparison to prior work
The 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.
1) 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)? 
2) 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?
3) 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?
A & 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.
ResNet vs LinearNet
Where 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:
1) 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.
2) 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?
Proposition 3.3
The 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?
Extension stochastic setting
I 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?
Extensions
You 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?