Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper studies the low-rank phenomena in the context of *non*linear neural networks. In this work, the authors prove, via a tree network transformation of their initial network, that there exists some matrix invariance across consecutive layers  (thm 1). Their assumptions are relatively mild (except maybe Assumption 1 that I discuss in my main review)

They then leverage that invariance results in order to show a low-rank phenomenon (thm 2) for a wide range of neural networks with positively-1-homogeneous activation functions.

main_review: ## Strengths
The theoretical result seems significant and to the interest of the community
The technical lemmas (Lemma 2,3,4) are well explained. Overall the paper is well written in my opinion. 
## Weaknesses
I think this paper would benefit from a more detailed discussion of the interpretation of Theorem 2. (see my questions) 

## Questions:
- Corollary 1: Aren’t the fact that the weight vectors do converge in direction to a limiting direction with non 0 entries implied by Assumption 1?
- I would love to see more comments and discussion around Theorem 2: To what extent (13) shows a low-rank phenomenon? What are the impact of $V_c(j)$ and $N_r(j)$ on your bound (it seems that they hurt the bound)? What is the interpretation of (14) and (15)?
- In (15) why can we look at the inner product between $v_{j+1}$ and $u_j$ (can't they have different dimensions)? What is the interpretation of this result?
- “In fact, the following assumption, shown in the literature, is sufficient” What do you mean by shown in the literature? Empirically shown? Do you have a citation for that?
- Assumption 2 implies Assumption 1 only for $t \geq t_0$. What happens if the sign for $w(t)$ changes a finite number of times and is eventually constant? Could you prove a similar result as Thm 2?

## Minor remarks
- ReLU and Relu are inconsistent across the text
- End of Page 4 ‘This assumption is realistic…’ I guess you are talking about assumption 1. Maybe, there is a missing sentence. 
- Btw Equation 4 and 5 $OUT_v$. Also $u$ is not quantified for equation 5. 
- Pae 9 “Phenonmenon”. 
- Equation 3, Aren’t $e \in p$ missing in the index of the sum? Also, $f$ is missing in the index of the product. 

summary_of_the_review: The theoretical result shown is very relevant to the community and is proved under relatively weak assumptions. 
I strongly recommend accepting this paper.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper shows under certain assumptions, there exist invariants in DNNs with ReLU (or leaky ReLU and identity) activations - similar to the invariants observed in linear networks. To show this invariance a decomposition of the DNN as the composition of a multilinear function and a network with {+1,-1} weights. Using these invariants they show that for linearly separable data, the absolute value of the weight matrices converge to rank one matrices (assuming directional convergence).
main_review: This paper gives a nice overview of the techniques used and improves on them in comparison to previous work. The sketch of proofs are quite detailed. This a quite dense paper, with many definitions (for all architectures studied) but I found it clear and well written.

Some of the assumption are quite strong, such as the sign remaining fixed and the alignment to parameters with no zero weight, but at least the authors take the time to discuss these assumptions.

The final result (the convergence to a rank one solution) is new for the deep non-linear case.
summary_of_the_review: The article proves a new result on the convergence to a rank one solution, in some quite specific setting and under some strong assumption. The techniques used are improvements over previous techniques, they are well presented and could be of independent interest.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper extends several technical results: (1) the decomposition lemma that applies to any feedforward networks; (2) the training invariance lemma, both for vertices and layers, that applies to various network structures; (3) the low-rank phenomenon for non-linear, non-homogeneous networks.
main_review: This paper has several strengths: (1) The decomposition of any feedforward network into a tree network and a path enumeration mapping. This lemma is interesting and may be useful in future works. (2) Based on certain assumptions, the training invariance lemma, and the low-rank phenomenon can be extended to non-linear networks, which can be viewed as a great contribution. (3) The paper is well written and easy to follow.

Weakness: 

(1) My main concern is that Assumption 1 and Assumption 2 are restrictive and even a bit unrealistic for some architectures. Assumption 2 seems to require the weights to go to infinity. This only happens in classification tasks, and only makes sense for homogeneous networks. For a non-homogeneous network architecture, scaling up each entry of the weight can in fact drastically change the correctness of the prediction. For example, the weights of a ResNet cannot enjoy a directional convergence since scaling up will alter the sign of the output. While the authors admit this and argue '...is widely used in practice:  most practical stopping criteria based on parameter convergence imply at least directional convergence', I do wish to see some citations to support this claim.

(2) Assumption 1 certainly cannot happen for any $t>0$. It definitely can hold for those $t$ in the late phase of training. Therefore, it would be better to instead state $t>T$ for some $T$, which is a more realistic assumption. Again I am very willing to change my mind if I see any empirical evidence supporting Assumption 1($\forall t>0$).

(3) Along with the last concern, another concern is that Assumption 1 gives an impression that the key difficulties are assumed away. The invariance lemma is proved for various architectures, but almost none of those architectures can be expected to satisfy Assumption 1 for any $t>0$. If Assumption 1 is modified so that $t>T$, then the results become less impressive since the results probably only hold for the late training phase.
summary_of_the_review: A very interesting paper that has certain technical contributions. The assumptions may be a bit unrealistic, but the technical results can be applied in the future. I recommend acceptance and am willing to raise scores given that my concerns are adequately addressed.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper studies the invariance in training nonlinear networks under gradient flow or differential inclusion. It is shown that, for various network architectures, there are time-invariant quantities related to networks weights, if the trajectory is in the sign-stable regime (the sign of the weights does not change). This sign-stable regime invariance suggests the weight matrices are necessarily low-rank, provided that they diverge to infinity along some non-degenerate directions. 
main_review: ************************************************************************************
Update: Thanks to the author for the response. I think now the paper is clear, and I have raised my score. 
************************************************************************************

This paper is mostly well written. In my opinion, the training invariance is very relevant in theoretically understanding the deep neural networks and the results presented in this paper are novel and interesting.

However, I have questions about some statements in the paper. I hope the author can clarify the following:
1. The author stated, after Theorem 1, "The first point of Theorem 1 admits an extremely simple proof for the linear fully-connected network case in Arora et al. (2018) (Theorem 1) but has not been generalized to other architectures." I don't see why this is true: In Theorem 1, if I understand the notation correctly, equation 6. shows the invariance of $|W_1(t)|^T|W_1(t)|-|W_2(t)||W_2(t)|^T$, where $|W_1(t)|$ is the entry-wise absolute value of $W_1(t)$. However, Arora et al. (2018) show the invariance of $W_1(t)^TW_1(t)-W_2(t)W_2(t)^T$, when using linear activation. The two matrices shown to be invariant are different.
2. In the proof of Lemma 6, the non-absolute version of the invariance $W_1(t)^TW_1(t)-W_2(t)W_2(t)^T$ is used, I understand that Lemma 6 is true for linear networks because that matrix is invariant, but then Lemma 6 would not hold for nonlinear networks since now the matrix invariance has entry-wise absolute value?

Overall, I hope the author can precisely define what is the matrix invariance for nonlinear networks, and how such invariance is used to prove Theorem 2.

Minor comment: In equation (14), the inequality should only hold when taking the limit?
summary_of_the_review: Strength: Well written; Novel and significant results

Weakness: Some statements might be wrong; Some proof needs clarification
review_title: null

Meta-review: *Summary:* Low-rank bias in nonlinear architectures. 

*Strengths:*  
- Significant theoretical contribution. 
- Well written; detailed sketch of proofs. 

*Weaknesses:* 
- More intuitions desired. 
- Restrictive assumptions. 

*Discussion:* 

Authors made efforts to improve the discussion in response to 6P7z. Authors agree with eeoo about Assumption 2 being relatively restrictive but point out that main results do not need it. They discuss Assumption 1 and revised it formulation. Reviewer eeoo was satisfied with this. Following the discussion udhX raised their score (after authors acknowledged an early problems and improved them) and found the paper well written with novel and significant results. 

*Conclusion:* 

Three reviewers consider this a good paper that should be accepted. A fourth reviewer rated it marginally above the acceptance threshold but following the discussion period explicitly recommended acceptance. I find the topic interesting, timely, relevant. In view of unanimously favorable feedback from four reviewers I am recommending accept.
Decision: Accept (Poster)