Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper analyzes the global minima of deep linear networks with weight decay. Under the assumption of linear architecture, $l_2$ regularization and population risk, the paper takes advantage of the symmetry and invariance in the network and derives the analytical expression of the minimum points. Depending on the regularization strength, for two-layer networks, zero is either the global minimum or a saddle point; for deeper networks, zero is always a local minimum and can be global (see Figure 1). The paper also tries to connect these theoretical results with some phenomena in deep nonlinear networks.
strengths_and_weaknesses: Strengths:
1. The paper proposes a set of assumptions under which the analytical expression of the minimum points can be derived, and the corresponding properties can be analyzed.
2. I think the most interesting contribution of this paper is to point out that the weight decay, i.e., the $L_2$ regularization, may introduce a local minimum at zero for deep networks. It is not surprising since the regularization term in Eqn (1) is quadratic while $L_0$ has higher order. It is good to formulate the phenomenon as a rigorous theory under the assumptions.
3. The presentation of the paper is pretty good. The settings are clearly stated and the results are supported by rigorous proofs. There are also detailed comments and discussions about the meaning and possible implications of the theoretical results.

Weaknesses:  
My main concern is that the assumptions in this paper may over simplified the problem. The proofs are straightforward (though I believe Theorem 2 is not trivial), and heavily depend on the symmetry (thanks to the assumptions) that does not hold in general cases. If considering weaker assumptions, I guess we may still prove that zero is a local minimum, since the regularization is quadratic and the square loss has higher order, but the quantitative results in this paper may not be extended. Since the implications in Section 5 are all under weaker assumptions, the theoretical results may not support the discussions here strongly enough. In addition, I guess a ResNet architecture may avoid the local minimum at zero since the square loss is not in high order now.
questions: 1. An important result of this paper is that zero is a saddle point (not local minimum) when $D = 1$ if the strength of the signal is more significant. It would be better to mention it in Theorem 1 or its discussion.
2. In Figure 1 Left, the labels of the inequality may need update.
3. In Figure 2 Right, does the linear regression also have l2 regularization?
limitations: Please see the “Weaknesses” Section above.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This work studies the population loss landscape of stochastic (e.g., in the sense of dropout) deep, linear, neural networks under 2-norm weight regularization. The key contribution of this work is the derivation of analytical expressions for the global minima of the aforementioned loss landscape, at least up to a scalar quantity. The implications of this result for training both linear and non-linear neural networks are discussed. In particular, this result illustrates how weight decay and depth can lead to a more challenging optimization problems, as well as the importance of the role of network initialization in avoiding basins of attraction around bad minima.
strengths_and_weaknesses: Originality: this paper continues the line of work analyzing linear neural networks. I am not a specialist concerning the study of linear networks, but the results appear, at least to the best of my knowledge, novel and interesting.

Quality and clarity: on the whole I think the paper is well organized, well written and clear. A few very minor suggestions in regard to the paper's presentation are as follows.

- I think upfront you could state your network architecture/ forward pass function more clearly / in terms of matrix vector product and give the dimensions of each of your parameter matrices.

- Notation wise both scalars and vectors use lower case characters which can be a bit confusing, perhaps using bold lower case characters for vectors might help.

- It might be helpful for the reader to restate statements of lemmas and theorems in the supplementary so they don't have to flick between.

- Line 475 in the supplementary "...we see that the left hand side \textit{is} larger..."


Significance: I think the extent to which understanding linear networks is important for understand nonlinear networks is not entirely clear. I still think it is important that we understand deep linear networks regardless however, and this work seems like a useful contribution.
questions: - Lemma 2 if I have understood correctly, it essentially seems to say the output layer weight vector $U$ is of the form $c\textbf{v}$, where $\textbf{v} \in\{ \pm 1\}^d$ vector, likewise the the rows of $W$ are just signs of the same constant row vector. How does this compare to the case with no noise?

- The networks you discuss have no bias parameters, how straightforward would it be for you to extend these results and techniques to also cover this case?

- The remark after proposition 1 is useful. Can you provide examples of cases where a global minimum doesn't exist when you set a single regularizer weight to 0?
limitations: I think the authors are reasonably upfront about the limitations of their work, although I think they could perhaps add some suggested avenues for future works. I can't envisage how this work might have a negative societal impact.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper provides a closed-form solution (up to some constant) of the global minima of linear neural networks when trained using square loss and strictly positive weight decay. This result can be extended to the case when the neurons are stochastic and independent. The formulas for the global minima are directly or potentially related to the weight decay, depth, stochasticity of neurons, and signal strength from training data. The authors also used the characterizations of global minima to explain multiple phenomena happening in real neural network training, e.g., deeper networks are harder to optimize. This paper also provided variance analysis in the asymptotic limits of network hyperparameters and did small-scale experiments on synthetic data to validate their theoretical results in non-linear networks.
strengths_and_weaknesses: Strengths:

- This paper theoretically gives an analytical formula (up to some constant) for the global minima of linear neural networks trained with weight decay, and this formula works for deep linear networks and could be generalized to independent stochastic neurons. These analytical expressions provide opportunities to study the properties of these global minima of deep linear networks in detail.

- It is an interesting idea to connect the formula of the global minima of neural networks to various common phenomena in this field, e.g., the collapses in deep learning.

- This paper is generally well-written and well-structured. The notations used in this paper are mostly well-defined, and the intuitions and implications of the theoretical results are provided in the main text. These make this paper easy to understand.

- The theoretical proofs in this paper appear to be correct, and the related works are adequately cited.

Weaknesses:

- The theoretical results in this paper are all about linear networks, and the relationship between linear networks are non-linear ones seems somewhat unclear, so most of the conclusions in this paper might not translate directly to non-linear settings. This is my major concern about this paper. The authors claimed on Line 16 that the landscapes of linear networks are believed to well approximate that of non-linear ones, but this claim might be vague and need further explanation. The authors also did experiments with a small two-layer non-linear network on synthetic data, but the scale of this experiment is small, so it is unclear whether this result still holds for more general settings. It would be better if the authors could provide more theoretical or empirical evidence connecting the loss landscape of linear neural networks and those of non-linear ones.

- The characterizations of global minima might not be enough to characterize the training of neural networks, which depends on the properties of the entire loss landscape. For instance, it is possible that the weights of neural networks could diverge and it never reaches a minimum, and it is also possible that the weights converge to a bad local minimum or saddle point. It might be better if the authors could (theoretically or empirically) eliminate these possibilities and show that the network weights will always converge to the points that they characterized, i.e., either the global minima or the bad local minimum at 0.

- The proof techniques used in this paper seem to heavily rely on the existence of weight decay at all layers, making it hard to be generalized to other settings. Without weight decay, relationships like equation (13) will break and the characterizations of the local and global minima could become much more complicated.

- Some arguments made in this paper might be somewhat vague. For example, in Line 268, it might be unclear what the authors mean by "cannot learn the data". 

Minor Comments:

- The details of the experiments the authors did to produce Figure 2 are missing. These details (e.g., how the data are generated, and what the hyperparameters are) could be important for interpreting the experimental results.

- The notation "$v$" on the left-hand side of equation (8) seems undefined. Should it be defined as some term in equation (5)?

Typos:

- Line 243, "are global and cannot generalize" -> "are global cannot generalize"
- Line 269, "two-layer net, and the existence" -> "two-layer net, the existence"

-------------------------------------------------
Update after author response:

I have read all other reviews and the authors' responses, and I decided to increase my score by 2. There are two main reasons why I increase my score:
1.  The authors have added empirical evidence (e.g., ResNet on CIFAR) to further relate the loss landscape of linear neural networks to non-linear ones.
2. The proof framework in this paper can be extended to more general settings with similar results, and the authors have provided theoretical results in more general settings, especially when there is no weight decay.
questions: - Could the authors provide more theoretical or empirical evidence connecting the loss landscape of linear networks and those of non-linear ones?

- Is it true that the weights of linear neural networks will almost always converge to the global/local minima characterized by the authors in this paper? Is it possible that the weights of the neural networks could converge to some points that are not captured in this paper, or even diverge?

- Can the proof techniques used in this paper be generalized to other settings? For example, when there are other kinds of regularizations or no regularizations at all.

- (Minor questions) Could the authors address the two questions I mentioned in the "Minor Comments" section above? In other words, could the authors provide the detailed settings of their experiments and the definition of the notation "$v$" in equation (8)?
limitations: The authors stated the assumptions for their theoretical results in the paper and had many discussions about the implications. It might be better if the authors could discuss more explicitly the limitations of this paper in the implication and conclusion sections.

This paper is mostly theoretical and focuses on a fundamental problem in general neural network training, and I do not see any immediate negative societal impact of this work.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies deep linear neural networks with weight decay and stochastic neurons. The authors show that the analytical global minima of square loss can be found for shallow neural networks (thm1) and deep neural networks (thm2). The analysis has some implications on the role of weight decay and the depth of neural networks.
strengths_and_weaknesses: Strengths:

I like the setting in this paper, which is clean and simple but can manifest interesting properties of neural networks. The results are very interesting, especially the part where bad minima emerge with weight decay. 

Weakness:
1) I understand the difficulty of analyzing global minima hence some assumptions are needed, e.g., diagonal A_0 for the exact form of b^* for the shallow neural networks., and single data. But some results are not easy to interpret, e.g., Thm2, Prop 3. Maybe the authors can provide more intuitions.

2) I have a minor concern that in the main contributions, point 4 seems irrelevant to this paper. 

-- What's v in Eq.(8)?

questions: The paper assumes $\mathbb{E}[\epsilon_i] = 1$ and $\mathbb{E}[\epsilon_i\epsilon_j] = \delta_{ij}\sigma^2 +1$ with $\sigma^2>0$. If $\epsilon$ are all 1, which is the case of neural networks with deterministic neurons, then $\sigma^2$ = 0 which does not fit into this regime. Is it correct?
limitations: Yes.
review_title: null

Meta-review: metareview: There is a clear consensus amongst the reviewers that the manuscript advances the theory for linear deep networks to a degree warranting acceptance at NeurIPS.  The authors responded well to the issues raised by the reviewers which results in increased support by the reviewers that the manuscript be accepted.  Inclusion of weight decay, stochasticity, and architectures beyond feed forward networks make this a valuable addition to the theory of linear deep networks.  
confidence: Less certain
Decision: Accept