Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper studies the training dynamics of deep linear regression models. Specifically, it explores the effect of depth on the loss landscape of robust deep linear models. The results are mainly in two aspects: First, there is a phase transition in the loss landscape of the robust linear regression problem: when the dimension of the feature is much larger than the number of data samples, there exists a true solution that is not a critical point of the $\ell_1$-loss; otherwise, all true solutions are global minima. Second, sub-gradient methods converge to a global minimum that is close to the true solution, and moreover, depth slows down the training rate but improves the generalization error.
strengths_and_weaknesses: The paper is technically sound. The characterization of the phase transition in the landscape of deep linear models looks interesting, especially as RIP does not work in this case. The technique of the analysis may also be potentially applied to other settings.

I am a bit confused about the main information this paper wants to convey. In my humble opinion, the main information is that: for robust deep linear models, some true solutions may not be obtained by first-order methods, but sub-gradient method obtains a solution that is close enough. This information is not that related to the depth. The information related to depth is: depth flattens the local landscape around the true solution, slows down the training rate and improves the generalization error. The latter two points are obtained by comparing the results of two-layer and (more-than-)three-layer networks, which seems a little strange: it does not claim that adding depth after depth exceeds three still improves the generalization error, so I'm not sure whether depth plays a role here.
questions: 1. It seems that the feasible region of $m$ in Theorem 1 and Theorem 2 intersects. Does that mean that subgradient methods will find a solution that has exactly $O(d)$ loss?

2. Is there any result showing that training rate and generalization error is directly correlated with the depth $N$?

3. In Line 174, it is mentioned that the improvement is significant if $m$ is small. How large is this $m$? It seems that by the assumption in Theorem 3, $m$ is not that small.
limitations: Yes.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies an interesting problem called "grossly corrupted linear model", where the ground truth is a linear model and a portion of output samples corrupted with noises with considerable variances. A diagonal linear network with depth N is used to learn the model, and the authors prove/propose several interesting results:
1) There exist parameters that correspond to the ground truth, but are neither local-min nor global-min.
2) The authors propose a sub-gradient optimization method, termed SubGM, that provably converges to the ground truth solution.
3) The deeper models have relatively better landscape around the ground truth solution. As the depth grows, SubGM indeed is more likely to converge to the ground truth solution.

Empirical results show that SubGM also works well on matrix recovery and Cifa-10 classification (with deep ReLU networks), and phenomenon 3) is also observed in these two problems.

strengths_and_weaknesses: **Strength**: 

The paper is clearly presented. It was believed that for neural networks, the depth increases the expressivity power, while the width helps optimization [1]. If we want to train very deep networks (say, more than 50 layers), certain tricks like skip connections and normalization must be applied. This paper, as far as I am concerned, provides a somewhat surprising insight: depth can also benefit the optimization landscape. With a proper learning algorithm, increasing the depth helps the optimization and the recovery of the ground truth. 

This paper studies the landscape from some novel angles: 
- (a) The solution we want (ground truth) is not necessarily a local-min or a global-min
- (b) Given (a), analyzing the local landscape around the solution we want, instead of the landscape around the global-min, can better help the optimization.

The paper establishes the theories based on the above ideas. It showed that the ground truth of the grossly corrupted linear model may not be the global-min of the optimization problem. Subsequently, it provides a landscape analysis to show that depth "smooths" the landscape around the ground truth solution. Then, it proposes an effective algorithm to recover the ground truth, with a convergence proof for any depth N≥2. Although the theory is not on neural-net settings, the experiments demonstrate that similar results can be observed in matrix recovery and image classification with neural networks.

Overall, this is a nice paper. It clearly sheds light on the optimization study of machine learning.

**Weakness**

The main weakness is that the diagonal linear models are not commonly used in practice. To me, it is a simplification of deep linear neural networks, which in turn is a simplification of fully-connected non-linear DNN. It is not clear whether the main theoretical conclusion (depth flattens the local landscape around the ground truth solution) still holds for practical settings.

[1] Sun et. al., The Global Landscape of Neural Networks: An Overview, arXiv:2007.01429.
questions: 1. In the abstract, t would be better to mention that this paper only considers diagonal linear networks. I am not aware of this until I read Section 1.1.
2. The experiments on ReLU networks did not rule out the effect of representation power. In particular, the better performance of deeper models may be (partially) due to the stronger expressivity.
3. I feel "bless of depth" suits the title better. Once N>1, the model is no longer convex, but increasing depth still improves the performance of SubGM.
limitations: The author may want to discuss how to extend the results to realistic neural-net settings. So far the results are limited to diagonal linear models which are not commonly used in practice. I am curious about the main challenge of applying a similar analysis to fully-connected linear networks or a non-linear DNN.
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: The paper discusses the relation between the optimization landscape around the true solution and the depth of deep neural networks. They theoretically prove that a simple sub-gradient method (SubGM) converges to a neighborhood of the balanced true solution whose radius is determined by the depth N of the model via an N-layer linear neural network with noise. They also experimentally verify their conclusion on ResNet of CIFAR-10.

**post-rebuttal**

The rebuttal answers most of my questions and I decide to change my score. But I think the author should claim that the focus on diagonal linear model in the main boy to avoid confusion.
strengths_and_weaknesses: Strengths:
1. Theoretically prove the relation between optimization landscape/generalization error and the depth of the neural network.

Weakness:
1. A little bit curious about the statement "deeper models generalize better" in line 18. In my understanding, the too deep model will cause the problem of overfitting, especially without the residual block. Could the author explain this statement?

2. The structure of the linear neural network seems to be incorrect. The author uses the Hadamard product when defining the N-layer linear neural network. Take 2-layer linear network and $x\in\mathbb{R}^2$ as an example. The output of the network is defined as $y=<w_1⊙w_2 ,x>= w_{11}w_{21}x_1+w_{12}w_{22}x_2$. So here comes the problem: what is the number of neurons in the hidden layer? The structure of the linear model that the proof of the whole paper based on is really strange and I am curious whether the conclusion drawn in the paper is correct.

3. The author only considers the linear network without the activation function. However, the nonlinear activation function is quite important in deep learning to enhance the expression ability of models in more general and sophisticated application scenarios. I am curious does the performance of deep learning models consists with the theory proven on the linear models? The author only provides the generalization error performance on 2-4 layers simple neural network and I don't think it is convincing enough. In appendix B.3, I only find the test and train accuracy of Resnets and do not find the generalization error performance of Resnets. I think the author should do more experimental research.
questions: Same as the Weakness.
limitations: The authors adequately addressed the limitations and potential negative societal impact of their work
review_title: null

final_score: rating: 9: Very Strong Accept: Technically flawless paper with groundbreaking impact on at least one area of AI/ML and excellent impact on multiple areas of AI/ML, with flawless evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper considers the implicit bias of the deep (diag) linear model. The previous analysis need the loss to be a l2 loss. In this paper, the author consider a robust statistic model where l1 loss should be applied. by ananlysising the landscape around the true solution, The author discovered that the true solutions are likely to be non-critical points under the one-layer convex parameterization, but have a good local property when multilayer nonconvex parameterization is applied.
strengths_and_weaknesses: This paper is quite interesting and I strongly recommend to accept. The proof technique is also new to me. The results include converging of the sub-gradient method and long escape time after arrived the balanced solution. 
questions: - The author can provide more proof initution in the main text. In the main text, the convergence result of the population dynamic and how the initialization scaling changes the stability result is missing. (I'm also curious about it)
- Can you compare the results when the network becomes deeper? It's a trade off or deeper is better?
limitations: No
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 the problem of robust and sparse linear regression under an over-parameterized setting. The authors show that this problem does not have a benign landscape. But for any N-layer model with $N \ge 2$, a simple sub-gradient with small initialization will converge to a small neighborhood of a balanced true solution, the algorithm will stay close to the ground truth for a longer time, and depth flattens the optimization landscape around the solution obtained by SubGM.
strengths_and_weaknesses: Strength:

The paper studies an interesting question related to the over-parameterized problem. In particular, the authors show interesting and important findings that deeper models have provably better optimization landscape around the solution trajectory.

Paper is written well.
questions: What is the reference [42] in Appendix A? I think the authors should carefully the references.

Considering the similar setting but noiseless data, what would the results be?
limitations: Yes, the authors have adequately addressed the limitations and potential negative societal impact of their work
review_title: null

Meta-review: metareview: This paper studies a linear network for a regression problem. The main objective is to provide more understanding of the optimization landscape and characterizes the effect of the structure (depth) on the neural network in the oper-parametrized setting. The paper balance and shows both encouraging results but also addresses the weaknesses of the optimization landscape. The paper is concluded with interesting numerical experiments that support the claims in the paper. Let me also highlight that the theoretical analysis includes many novel parts (in the appendix).

confidence: Less certain
Decision: Accept