Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper analyzes the setting of shallow and deep linear neural networks under gradient flow and gradient descent and deduces a superpolynomial directional convergence guarantee.
The result is proven under one assumption: spherically symmetric data distribution. Additionally, in the deep linear networks case, it requires a balancedness condition on the initialization.
Among the existing convergence analysis of binary classification on separable data, the current result diverges by examining the dynamics of minimizing the population logit loss (rather than empirical loss) and tests the case of zero margin separable data. It mitigates some assumptions like prior convergence to zero classification error or overparameterization.
The findings are shown empirically by experiments on both benign and real-world datasets and also partially on non-linear fully-connected ReLU networks. 
main_review: 


In my view, the paper addresses a fundamental topic for better understanding the theory behind deep neural networks --- convergence analysis. Even though the setting is rather restrictive, the work takes a step forward in understanding convergence in these kinds of models. Further, it mitigates assumptions of previous works with a similar setup and therefore presents an important contribution in this field. 
However, there are several issues with the current version that in my opinion should be treated prior to publication.

First, regarding the problem setup. The spherically symmetric distribution is quite a restrictive assumption. Together with assuming separability, it is worth supporting both with stronger motivation. For instance, giving examples for real-world problems that satisfy or nearly achieve those assumptions or preprocessing methods that can approximate this form of the data.
Furthermore, analyzing the population loss instead of empirical loss is a bit nonstandard. In my opinion, it requires justification since in real-world problems we usually don't have access to the distribution but to a finite set of samples, which is the case that is usually addressed. 

Regarding the experiments on MNIST and CIFAR, it is mentioned that: "the datasets do not satisfy our data assumption generally". Despite the fact that the reported results do show a positive effect of the acceleration methods. In my view, the theory presented in the paper cannot provide a valid justification for the phenomenon if the data does not of the correct form of the proofs. Therefore, showing it is a bit out of the topic as I see it. Demonstrating these acceleration methods on datasets that do satisfy the data assumption would be better since the presented theory could support its reasoning. 

Overall, the contribution of the paper justifies publication in my opinion. Although I think clarifying the reasoning for the setting and focusing on the direct implications of its results are things that the authors should address prior to publication.

### Post-rebuttal update
After reading the author's response and all other comments, my opinion remained as before. I believe the paper is borderline but tend to accept. In my view, the main drawback is still the limited significance of the results within the setting presented in the paper. Other criteria, however, seem to assess the paper positively, as the technical aspects of the paper and the results are solid. Therefore, I keep my score slightly above the acceptance threshold.
limitations_and_societal_impact: This work mainly focus on the theoretical aspect of deep neural networks. If there are implication that should be addressed I think they only belong to the impact of deep learning in general and not directly to this work.
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: In this paper the authors present a convergence proof of linear neural networks trained with a logit loss. The analysis is based on previous works of Telgarsky, and is only concerned with binary classification of linearly separable points with 0 margin. In addition the authors make the assumption that the data distribution of the points are isotropic namely, spherically symmetric. With this the authors prove a directional convergence result, that states while the parameters magnitude approaches infinity as seen in previous works with separable data and logit losses,  the direction of the parameters converges to the orthogonal vector to the decision hyperplane. The authors present the result for shallow (1 layer) networks as well as deep linear networks. In addition to convergence the authors observe a trend of decreasing and then increasing parameter magnitudes that they also analyze empirically.


main_review: I find this paper interesting and provides a nice analysis of a new data distribution setting (0-margin separable data). At the same time, some of the assumptions of this work make it too restrictive and similar to previous art. I find the biggest limitation of this work to be the assumption that the data distribution is isotropic and the development of the theory only with respect to a distribution loss. Namely, a spherically symmetric data assumption is very stringent and is very very far from any interesting data manifold of real data. Even for normalized datasets where the covariance is whitened the assumption that the data is spherically symmetric implies that the dataset contains no directionally specific clusters or variation in density which I find to be very far from any real dataset example. Additionally I recommend the authors spend more time to motivate the key discoveries of this work and their importance, as well as tighten up some of the writing as there are many grammatical issues that occasionally obstruct meaning. 
limitations_and_societal_impact: The authors did not fully address the limitation and the implication of their data distribution assumption of spherically symmetric data.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors study the directional convergence of linear and deep linear networks under a specific setting:  data is separable with zero margin and assumed to be spherically symmetric, and the model is trained by gradient flow/descent with the logit loss. In this setting, the authors improve upon previous results by showing fast directional convergence (superpolynomial). Moreover, unlike previous works the authors are able to analyze the directional dynamics along the entire training process without relying on over parametrization or zero error assumption.
main_review: Overall the authors present an interesting analysis of directional convergence in a restricted setting, which improves upon previous work. My main concern is with the highly narrow scope for which the results apply, as the authors themselves have pointed out (i'd like to commend the authors for providing an honest description of the limitations of their work). 
The technical aspect of the derivation rely heavily on the spherically symmetric distribution assumption (assumption 1 in the paper), absent from previous work , rendering the results somewhat incremental (a more complete theoretical handle of convergence in exchange for a more restrictive setting). 

I'd like to add that i am no expert in this particular area, hence i will leave the more in depth technical review for other more qualified reviewers. 

question:

The authors relate assumption 1 to the benefit of data augmentation and preprocessing. Can they elaborate on this given that recent papers (Neha S et al*) have pointed to the adverse effects of data whitening as preprocessing? How is data augmentation related? 

*Neha S. Wadia, Daniel Duckworth, Samuel S. Schoenholz, Ethan Dyer, Jascha Sohl-Dickstein, "Whitening and second order optimization both make information in the dataset
unusable during training, and can reduce or prevent generalization"
limitations_and_societal_impact: They are adressed
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The authors study both shallow and deep linear networks under the assumption of spherically symmetrical input data. They show that gradient descent provides a super-polynomial convergence rate in this setting, which does not rely on any assumptions on the margin of the data or over-parameterization of the network. They provide some experiments demonstrating their results when their assumptions exactly hold, as well as with deep non-linear activation networks where their assumptions no longer hold. 
main_review: Overall, while the theoretical analysis is sound in this work, the impact of the work is unclear to me. In particular, since there are some restrictive data assumptions upon which the analysis relies, it doesn't appear that the analysis is practically useful for anything. That being said, I appreciate the fact that there is no assumption on the margin or overparameterization. 

The purpose of experiments on non-linear networks is not very clear to me. If anything, it demonstrates that the general intuitions on super-polynomial convergence that were derived under different assumptions do not carry over when these assumptions are removed. Therefore there is a question of what practical utility the theory provides to neural networks as they are used in practice.  Furthermore, it is strange to me that only test error is displayed, rather than training error, since the theory makes claims about the convergence of training loss rather than test loss. It would be good for the authors to clarify these experiments a bit more. 

Proposition 1: The loss function L(w) is only convex in the shallow linear network case as discussed in Section 3. In the deep linear network case where w := (W_1, ..., W_n), the loss is not convex with this parameterization (though it is convex in w_e := (W_n...W_1)^T). This should be clarified. 

This is a small thing, but it seems as though most of the claims in Section 4 apply to N > 2 case, while Section 3 applies to N=1 case. However, the N=2 case is not explicitly discussed. For completeness I think the authors should be clear about this specific case. 

There are also grammatical errors scattered throughout the text, which should be corrected. I list some examples below:

Line 31: "However, these work consider" --> "However, these works consider"
Line 233: "The intuitive of a)" --> "The intuition of a)"
Line 235:  "...weight is the multiply of the other..." --> "...weight is the product of the other..."
limitations_and_societal_impact: Yes.
review_title: null

Meta-review: This paper is borderline.  Reviewers generally agreed that the theoretical analysis (main contribution) is technically solid and delivers strong results, but on the other hand is limited to a very restricted setting of spherically symmetric data distributions.  In addition, several reviewers felt that the empirical section on non-linear neural networks is somewhat disconnected from the theory (which applies to linear neural networks), and the value it adds to the paper is limited.  While I share the aforementioned concerns, I believe the state of deep learning theory is such that strong analyses of restricted settings are still of interest, and therefore recommend publication.  I encourage the authors to reconsider the necessity of some of their experiments and defer to the appendix those that do not significantly contribute to the main message of the paper.



Decision: Accept (Poster)