Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This work studies the training dynamics of over-parameterized deep linear networks. The authors propose the Principal Components bias (PC-bias) convergence pattern that characterizes the convergence behavior of deep linear networks training, which is supported by theoretical analysis and empirical results. This works also investigates the Learning Order Constancy effect (LOC-effect) and identified the connection between PC-bias and LOC-effect. Empirically, the authors also study several implications of PC-bias, including early stopping, convergence behavior under label noise, and provide interesting observations.
main_review: This paper identifies several interesting phenomenons for deep (non-)linear neural networks, including the effect of whitened data, connections between the PC-bias, LOC-effect, and spectral bias. 
Pros:
1. Theoretically, this paper provides precise characterizations of the training dynamics of deep linear networks in Section 2.
2. Empirically, the authors investigated the proposed PC-bias in several settings as well as its connections to LOC-effect and spectral bias.

Cons:
1. The theoretical and empirical results are somehow limited to simple linear models, and some of the interesting observations have been studied in previous works, for example, [1] studied the dynamics of deep linear network training and found that the 'networks sequentially learn the solutions of a reduced-rank regression with a gradually increasing rank'. 
2. The connection between whitened data, label noise, and convergence speed is interesting, it would be better to precisely characterize this phenomenon in a lemma/theorem by making some reasonable assumptions.

[1]. Implicit Regularization of Discrete Gradient Dynamics in Linear Neural Networks. Gauthier Gidel, Francis Bach, and Simon Lacoste-Julien, NeurIPS 2019.
limitations_and_societal_impact: N.A.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper studies the evolution of a deep over-parametrized linear network under gradient descent.  The main claim of the paper is that the convergence rate of the weights is faster along directions corresponding to the larger principal components of the data, at a rate governed by the singular values. The paper also supports its argument in an extensive experimental study.
main_review: The paper touches on an important question about the inductive bias of neural nets. This problem has paramount importance to the deep learning community. Moreover, the motivation of the results is clearly explained in the paper. 
However, I'm not sure whether the theoretical side is strong enough to justify a new publication. Specifically:

1. Thm 1 is a direct calculation of the update at each iteration, its contribution is limited. Moreover, it seems to me like a minor modification of the update presented in "Width Provably Matters in Optimization for Deep Linear Neural Networks" by Du and Hu

2. Thm 2 (which is the main theoretical claim of the paper) presenters a new result as far as I know. However, I'm not sure about its novelty given the techniques that are used in standard over-parametrized literature (for example "Width Provably Matters in Optimization for Deep Linear Neural Networks" by Du and Hu or "Gradient descent finds global minima of deep neural networks" by Du et al). I'll be happy if the authors can address the novelty of their proof techniques and compare it to standard lazy training technique.

3. I would suggest rearranging section 2.2 to be formulated as formal theorems where the condition and results are rigorously organized. Moreover, separating more accurately between the two phases of learning might add to the paper's contribution.

4. I think it is important to include the results of the nonlinear case (section B.2 in the appendix) in the main paper. Although additional assumptions are required. These results might hint that the phenomena presented in the paper happens also outside the linear network world. 

Regarding the empirical side, I think that the empirical study is impressive and definitely contributes to the paper. My main concern on the empirical side is why are the settings were changed in the empirical part? (specifically the loss and initialization). I suspect that the theory doesn't hold in practice which might weaken the paper. 

To summarize my review, I didn't find major flaws in the paper. In my opinion, each part alone (the empirical and the theoretical) doesn't enough for a new publication. However, since both parts were combined together, I find the total contribution of the paper on the borderline for a top-tier conference. 

limitations_and_societal_impact: None
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper argues for the existence of the so-called “principal component bias” in the learning of deep wide nets, with the main focus on linear networks. This refers to the phenomenon that the learning that is associated with larger PCs of the data is typically faster. The paper does so via a theoretical analysis of the early stage of learning in linear nets and a series of experiments, involving both linear and nonlinear models.
main_review: This is a paper with quite very interesting experiments. Understanding deep nets is difficult, so the ability to have a partial understanding via a simple pattern like PC bias is valuable, even though PC bias does not give the full picture as admitted in the paper. The theoretical analysis is non-rigorous and appears to be the weaker part; it is the series of small but informing experiments that give useful insights. Specifically the paper draws a nice connection between PC bias and common techniques like PC amplification, whitening and random labelling, demonstrating that PC bias can be a useful guide for subsequent studies that involve these techniques.

My main criticism lies in the theoretical part. Certain parts are not rigorous; for example:
- In the use of big O notation, this notation hides a lot of important dependencies on e.g. time, weight magnitude, etc. This has serious implication to Theorem 2; for example, if the conclusion can only hold until time $\sim O(1/m^{99})$, this implies Theorem 2 is not very useful (even though Fig. 1 is).
- The proof of Theorem 5 is actually bad: from line 515 (which is an entry-wise bound as written) to line 516, one requires a certain union bounding over $m^2$ entries, and so the correct probability bound becomes void. This would have been avoided if the metric of interest (denoted by $|\cdot |$ as in the paper) is not entry-wise absolute value, but some appropriate norm.

These can be fixed, though I think this is the less important part of the paper. Moreover previously there have been rigorous theoretical results that convey a certain sense of PC bias, by solving the complete solution of the learning dynamics, in linear networks (e.g. Gidel et al 2020) as well as nonlinear networks (e.g. Nguyen 2021), without the whitened data assumption just like this paper, but of course in tractable theoretical settings. As such, despite the weakness in the theoretical part, I would not say PC bias has no (or unreliable) theoretical basis, and I would rather emphasize on the experimental findings.

While I do not know the experimental literature sufficiently well to judge on novelty, supposing there is no issue with that and unless there are flaws in experimental designs spotted by other reviewers, I think the paper is a worthy contribution to the broader community.

References:

Gidel, Bach, Lacote-Julien, “Implicit regularization of discrete gradient dynamics in linear neural networks”, 2020.

Nguyen, “Analysis of feature learning in weight-tied autoencoders via the mean field lens”, 2021.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: The authors study a principal component bias of deep linear neural networks when trained with gradient descent using a small learning rate. They show that when the network is sufficiently wide, deep linear networks behave like single layer linear networks during the first phase of training, where the rate of convergence is governed by the largest principled components of the data. It is further shown that at later stages of training, under some assumptions, the PC bias remains to some extent.
main_review: My main concern with the paper is that it is overall quite incremental over previous results:
It is known for some time at this point that sufficiently wide networks evolve linearly, where convergence rate is governed by the principled components of the neural tangent kernel (NTK). For deep linear networks, the NTK itself is given by the Gram matrix of the data (\Sigma_xx using the notations in the paper) scaled by the depth L, which is identical to the NTK of a single layer linear networks up to scale. Hence, it is trivial that when the width M is large, the convergence rate in both shallow and deep linear models will exhibit the PC bias as detailed by the authors. In other words, the large width assumption when applied to linear models strips it of all the interesting properties provided by depth and relegates it to a 1 layer linear network. 
For the second phase of training, i find the assumptions made by the authors quite unrealistic. I would argue that in most tasks of interest k/m cannot be considered small. Moreover, the presented results show no explicit dependency on training time, which makes it difficult to understand the regimes in which the results hold. 

In general, i find the PC bias as described in the paper lacking in its ability to explain any interesting phenomena in deep learning since it is inherently present in shallow networks as well.  In addition, it does not trivially apply to deep nonlinear models. Even when only considering linear models, the incremental technical novelty in the paper does not meet the threshold for acceptance in my opinion.

Question:

1) The experimental section includes results on VGG style linear architectures, however the theoretical section does not deal with convolutions. How should the PC bias be interpreted in this case? Shouldnt the gram matrix \Sigma_xx be computed differently for convolutional architectures? 


_____________________Post Rebuttal______________________

I appreciate the authors response to my review. However, my score remains unchanged for the following reasons. In my view the theoretical contribution is a restatement of known results - Theorem 2 discusses leading corrections to the infinite width limit, which have been discussed in numerous papers [1,2], and theorem 1 should be relegated to a proposition. Moreover, the actual claimed theoretical contribution - namely the O(q/m) and O(K/m) corrections, is not formally presented, and seems to be brushed aside due to technical issues (it is not clearly presented in the supplementary either). 
In general i find the empirical section intriguing, however i doubt the claim of the paper carries over to larger datasets, and i feel this should be addressed in future versions of the paper. 

[1] Wide Neural Networks of Any Depth Evolve asLinear Models Under Gradient Descent

[2] Asymptotics of Wide Networks from Feynman Diagrams

limitations_and_societal_impact: I would encourage the author to address the limitation detailed in the review.
review_title: null

Meta-review: Reviews of this paper were mixed. On the upside, several reviewers commended the insightfulness of its empirical investigation.  On the other end, concerns were raised regarding the novelty and significance of its theoretical contribution in light of known results in the ultra width (NTK) regime.  The latter point does not seem to be clearly delineated in the text.  Overall, while this work clearly has potential to be of interest to the community, due to the aforementioned drawback, it currently falls short of the (extremely competitive) NeurIPS acceptance threshold. I encourage the authors to clearly distill the novelty of their theory, reconsider how much weight is allocated to this theory in light of the distilled novelty, modify the text accordingly, and resubmit to a future conference.
Decision: Reject