Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: 
*Summary* 
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.  
 
*Decision* 
On 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. 
I 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.
*Questions*
- 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.
- To what extent the proof of Theorem 3.1 uses the proof technique of Bartlett et al. 2019 ?
- 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
- In Theorem 3.1 What is $e$ ?
- 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?


=== After rebuttal ===
Thank you for this detailed answer. It confirms that this paper is of interest to the ICLR community.

review_title: Official Blind Review #2

final_score: rating: 6: Weak Accept
review_content: 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?

review_title: Official Blind Review #1

final_score: rating: 6: Weak Accept
review_content: 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.

The paper is well written. The results seem novel and interesting.

It 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?

----------------------
After rebuttal:

I have read the authors' response. I would like to keep my original score.
review_title: Official Blind Review #3

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