Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper studies the convergence rates of gradient descent (GD) on minimizing the training loss $L(W_N \cdots W_1)$ of deep linear networks, where $L(W)$ is the convex training loss function of the corresponding linear model (i.e., the loss when the product $W_N \cdots W_1$ is collapsed into a single matrix $W$). We assume that $L(W)$ is strongly convex and smooth in the subspace spanned by the data points. The paper considers the following three initialization schemes

- Gaussian initialization;
- One peak random orthogonal projections and embeddings initialization (which generalizes the orthogonal initialization proposed by Hu et al. (2020));
- Special balanced initialization (which is a special case of balanced initialization considered in Arora et al. (2018a)).

For these schemes, the paper proves that, for sufficiently wide networks,

1. GD converges linearly, and the convergence rate is of the same order as minimizing $L(W)$ as a function of $W$ (Theorems B.1, B.2, and B.3; Theorems 3.1 and 3.2 in the main text are special cases of these theorems).
2. The trajectory of the product $W_N(t) \cdots W_1(t)$ as we minimize $L(W_N \cdots W_1)$ in fact stays close to the trajectory of the $W(t)$ as we minimize $L(W)$ with an appropriately rescaled learning rate (Theorem 3.3).
strength_and_weaknesses: Convergence of optimization methods on training linear neural networks is an important area as it can provide valuable intuitions for understanding nonlinear networks. The paper generalizes existing results and presents the main results clearly.

The $O(\kappa \log 1/\varepsilon)$ iteration complexity to achieve $\varepsilon$-suboptimality looks indeed sharp because it matches the convergence rate of GD on the convex counterpart. Nevertheless, I should mention that the $O(\kappa \log 1/\varepsilon)$ complexity was also achieved by some previous results such as Du and Hu (2019) and Hu et al. (2020). 

The next main result that the trajectory of the product $W_N(t) \cdots W_1(t)$ closely follows the trajectory of $W(t)$ as we minimize the corresponding convex function $L(W)$ is something that I haven't seen in the literature, unless I missed some existing results. This part is quite intriguing as it establishes that optimizing linear NN follows a similar trajectory as the corresponding convex problem, while the problem itself is nonconvex. This observation can deliver useful insights to the community.

While I like the observation made in Theorem 3.3, for the rest of the main results (Theorems B.1, B.2, and B.3), I got the impression that the contributions made by this paper may be somewhat limited. As pointed out above, for Gaussian and orthogonal initializations, the sharp rate $O(\kappa \log 1/\varepsilon)$ was already achieved by Du and Hu (2019) and Hu et al. (2020). 

A quick perusal of the proof reveals that the paper also builds on the techniques developed by these two existing papers. Remark 5 states that for the case where all hidden layers have the same width, Theorems B.1 and B.2 recover the main results of these papers. The "convergence region" established in Lemma D.1 almost exactly follows the conditions developed in the two papers. Appendix E also seems to follow the flow of the proof in Du and Hu (2019).

These observations make me question if Theorems B.1 and B.2 are merely a technical extension of the existing results on "hidden layers having identical widths" to just "hidden layers with general widths." I know this could be a false impression as I didn't go through the proof carefully; I would be happy if the authors prove me wrong.

Anyway, this concern of novelty makes me hesitate to recommend acceptance at the moment. Importantly, the main text of this paper does not make any precise comparisons against the existing results. Can you elaborate/highlight the technical challenges that had to be overcome in extending the existing results to get Theorems B.1 and B.2? 

clarity,_quality,_novelty_and_reproducibility: The paper is well-written and delivers the main results clearly. I found the paper quite enjoyable to read. 

In terms of novelty, the observation made in Theorem 3.3 (Lemmas D.3–D.5) looks novel to me, but as noted above, the remaining elements of the proof seem to rely upon existing results. 

Some minor issues:
- In Eq (4), the RHS has to have a leading $\frac{\beta}{2}$ factor?
- In Definition 2.1, $n_i I_{n_i}$ -> $n_i I_{n_{i-1}}$ and $n_{j-1} I_{n_{j-1}}$ -> $n_{j-1} I_{n_j}$?
- In the definition of special balanced initialization, there is no mention on how $V_1$ is defined? Also I thought $V_N = U_{N-1}$ should also hold here?
- In the statements of Theorem 3.1 and 3.2, it looks weird that $\delta$ does not show up anywhere in the stated bound.
- In Theorem 3.3, it would be useful to mention that $q \in (0,1)$ for the step size of interest?
- The plots in Figure 1 should better be drawn in "semilogy" style?
summary_of_the_review: I enjoyed reading the paper and I think the results presented in the paper deliver valuable insights. However, at the same time, it may be the case that some of the main theorems rely too heavily on some existing results and hence are of limited novelty. In the rebuttal, it would be very helpful if the authors could clarify the technical barriers that had to be overcome in carrying out the extensions. I would be happy to raise my score if my concerns get resolved.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper provides a convergence analysis of deep linear neural networks with overparameterization. Compared to previous work, this paper deals with different initialization methods, more general loss functions, and varying layer width and obtains sharper convergence rate.
strength_and_weaknesses: Strengths:
1. This paper is well-written and easy to follow. The notations are clear. 
2. This paper is well-motivated and made a solid progress in understanding the gradient decent behavior of deep linear neural networks. It shows that overparameterization leads to depth-independent convergence rate, which is not unique to orthogonal initialization, as long as the initialization falls into the convergence region. 
3. The analysis seems rigorous though I didn't check the proofs thoroughly.

Weaknesses:
1. The convergence analysis is local. From the last condition of eq (29) in Appendix D, it can be seen that the initial objective function cannot be too far from the minimum value.
2. This is lack of intuitive understanding of the analysis, especially on the convergence region part. 

clarity,_quality,_novelty_and_reproducibility: All good.
summary_of_the_review: This paper is a solid theoretical work on the convergence of gradient descent of deep linear neural networks. I recommend acceptance.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper provides a sharp analysis for gradient descent on deep linear networks with strongly convex and smooth objectives. Specifically, for various initialization schemes such as Gaussian initialization, orthogonal initialization and balanced initialization, when the width is at least some constant times the depth, it is shown that gradient descent converges linearly to the global optimum. Moreover, it is shown that the trajectories of GD on linear networks and GD on the corresponding linear model stay close.
strength_and_weaknesses: I think this paper provides a nice analysis of gradient descent on linear networks with general strongly convex (potentially over a subspace determined by data) and smooth objectives. However, I have major concerns regarding the novelty. The prior work (Du and Hu, 2019) considered gradient descent on linear networks with the squared loss, and proved linear convergence if the width is at least some constant times the depth. Compared with (Du and Hu, 2019), it seems the main innovation of this paper is an extension to general strongly convex and smooth objectives; such an extension is well-known in convex settings, and it is unclear what the main challenges and novelties are. This paper also provides convergence results on trajectories, but these results also seem to follow from strong convexity.
clarity,_quality,_novelty_and_reproducibility: The paper is well-written, but I have concerns about the novelty as described above.
summary_of_the_review: This paper proves linear convergence results of gradient descent on linear networks with strongly convex and smooth objectives.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This work proves that overparametrized deep linear networks can converge as fast as gradient descent on the equivalent linear regressor
strength_and_weaknesses: Strength: (1) the result has some fundamental importance. (2) the result that deeper nets can converge as fast as a convex linear model is both rather surprising and important

I think the main weakness is the lack of insights and discussion. The following problems should be addressed by the authors before publication:

(1) a few overclaims: the analysis only revolves around overparametrized models, thus the title should also include the word "overparametrization" 
- for example, the paper did not obtain any result when the width of the model is small, whereas the title seems to suggest that the results apply to both cases
- the same criticism applies to the abstract
- the authors need to update both the title and the abstract to be more specific and avoid overclaiming

(2) the minimum width requirement in theorem 3.1 and 3.2 depends on constants $C, C_2, C_5$. These do not affect the convergence rate, but I think it will provide more insight if the authors provide a remark discussing how they depend on the hyperparameters of the problem, such as the depth of the model, the distribution of the data, etc

(3) a crucial distinction that the authors make is that overparametrization is essential for achieving such a good convergence rate; however, this point is way under-discussed. The authors should spend a lot more energy discussing why overparametrization is essential
- for example, the authors could explain why the results/theoretical techniques cannot be applied to thinner models and then point out or suggest what properties of a thin model prevent it from being efficiently optimized

(4) in the related works, the authors mentioned the previous results that deeper models can have vanishing Hessian that hinders optimization. The authors should then explain why this is not a problem from their theory 
- for example, what properties of an overparametrized model (or what assumptions that the authors made) help escape such saddles

(5) how does the result change if there is a regularization term such as $L_2$? the authors should also discuss this relevant work: https://arxiv.org/abs/2202.04777

(6) does the main result change in a minibatch setting? the authors should suggest some answer

(7) the font size in the figures is too small. The  authors need to update it to match the font size of the main text
clarity,_quality,_novelty_and_reproducibility: Both clarity and novelty are good
summary_of_the_review: I recommend rejecting the current version due to the lack of insight and discussions

However, I think the problems can be easily fixed and I would like to change my assessment if the authors make the corresponding improvements
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The authors obtain new bounds on the rate of convergence of gradient descent applied to deep linear networks.  The bounds hold for more general loss functions than earlier bounds.  The authors also describe general conditions on the initialization that lead to convergence, and show that some initialization schemes are likely to satisfy these conditions.

The consensus view was that this analysis was too technically incremental for publication in ICLR.  The bounds were also formulated in a way that made it difficult to understand what exactly was proved.

justification_for_why_not_higher_score: Despite the fact that it received scores straddling the accept-reject boundary, including one quite high score, this was not viewed as a borderline case because the two reviewers with the most relevant expertise recommended rejection, including the only reviewer who expressed a confidence of 4.   I (the meta-reviewer) also went over the paper in some detail, and agreed with the rejection recommendations.

justification_for_why_not_lower_score: N/A
Decision: Reject