Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies the gradient descent for two-layer leaky-ReLU neural networks on binary classification problems with the logistic loss and shows the simplicity bias where the neural network converges to the linear function that maximizes the margin under appropriate assumptions. 
main_review: [Contributions]

The line of research that characterizes the implicit bias of the optimization method is important to explain the generalization capability without explicit regularization, especially for the nonconvex models such as neural networks. In this sense, the paper makes certain contributions summarized below:

- Under linear separable and symmetric assumptions, the study shows that the two-layer leaky-ReLU network with the parameter maximizing the normalized margin takes the linear function.

- The study shows that the gradient flow of the two-layer leaky ReLU converges to the max-margin linear classifier in direction.

Advantages over related studies are that (i) the study shows the convergence to the max-margin linear function rather than KKT-margin direction which yields a somewhat complicated function, and (ii) the study does not require an assumption called Neural Agreement Regime (NAR) which is used to conclude the similar result in [Sarussi et al. (2021)].

[Weaknesses]

I think this study is interesting, but I'm not sure when Assumption 4.6 is satisfied. Since one advantage is the validity of the required assumption, it is better to elaborate on the description of this assumption. Could you explain the situation where this assumption is satisfied? 
I would like to increase the score if the authors well address this concern.

[Questions]

- There is no explanation about the dependency on the constant $c_{ainit}$ which is introduced for the initialization of $a$. I would like to know how this constant will affect the results. The following paper shows that the training dynamics fall into the kernel regime when the initialization scale of $a$ is small depending on the network width, although the problem setting and the way of initialization is different from this submission.

E Weinan, Chao Ma, and Lei Wu. A comparative analysis of optimization and generalization properties of two-layer neural network and random feature models under gradient descent dynamics, 2020.

- I would like to know how important small-scale initialization is. I acknowledge its importance in the context of feature learning. I want to know the importance in the context of the margin. Why does it fail to converge to a linear function when the initialization scale is large?

[Minor comments]

There are some typos in Appendix. For instance, see lines 551, 556, and 561. Moreover in Lemma B.5, $\ell$ should be replaced with $\ell'$

-----
After reading the rebuttal:
The authors have addressed my concern about Assumption 4.6. They well explained the motivation of this assumption and provided an example. Although a given example is rather limited, it is useful in finding a new research direction. I would like to increase the score to 6. I hope some comments on this assumption will be added in the revision.
limitations_and_societal_impact: The authors adequately addressed the limitations and potential negative social impact
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper considers margin maximization and simplicity bias properties of gradient flow on a two-layer leaky-ReLU network with linearly separable data. If the data is also symmetric (i.e., whenever (x,y) is in the dataset, (-x,-y) is also in the dataset), this paper proves that the max-margin network basically represents the max-margin linear classifier. Moreover, while prior results ensure convergence to KKT points which may not give the maximum margin, this paper shows that under a few technical conditions gradient flow can indeed maximize the margin. On the other hand, if the data is not symmetric, this paper provides an example where gradient flow cannot globally maximize the margin. 
main_review: I think this paper provides a few interesting results and techniques:

(1) Theorem 4.2 uses the symmetry condition to ensure the max-margin network is basically the max-margin linear classifier; I think this is interesting, and the proof of Theorem 4.2 is also nice. 

(2) Section 5 gives a multi-phase analysis: in the first phase, even though random initialization is used, as long as the initialization is small enough, this paper shows gradient flow will approximately move the weight vectors on the first layer to two opposite directions. Then in the second phase, the gradient flow dynamic is approximated by a dynamic of two neurons, and finally in the third phase, this paper proves margin maximization. I think this multi-phase analysis is novel and interesting.

(3) The negative result given by Theorem 6.2 is also interesting, confirming that margin maximization may not hold in general.
limitations_and_societal_impact: As mentioned in Section 7, the linear separability assumption is restrictive. However, in my opinion the symmetry condition is more restrictive: under this condition, if the data is not linearly separable, then it cannot be separated by a network either (this can be proved using the proof of Theorem 4.2). Moreover, one common sufficient condition for a positive definite NTK is that no feature vectors are parallel, which do not hold under the symmetry condition. The symmetry condition is also used in phase I of the gradient flow analysis. I think these points should be discussed more clearly in the body.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper studies the implicit bias for finite two layers Leaky ReLU networks. For linearly separable symmetric data, the authors show that the global max-margin direction corresponds to a linear classifier. In addition, under additional regularity conditions and for a sufficiently small initialization scale, the authors show gradient flow achieves the global max-margin. For non-symmetric yet linearly separable data, the authors show that gradient flow can be led to converge to a linear classifier with suboptimal margin by adding 3 data points.
main_review: The paper studies the implicit bias for finite two layers Leaky ReLU networks and logistic loss.

The paper main contributions are:
- For linearly separable *symmetric* datasets, the authors show that the global max-margin separator is linear.
- Moreover, the authors show that in this setting and under additional regularity conditions and sufficiently small initialization scale, gradient flow converges to a global max-margin *linear* classifier. 
In particular, the authors note that previous works only showed convergence to a KKT-margin direction which in general may be non-linear.
- These results connect current implicit bias max-margin results with simplicity bias works.
- However, for non-symmetric yet linearly separable data, the authors show that gradient flow can be led to converge to a linear classifier with suboptimal margin by adding 3 data points.

My main questions\concerns:
- How small should the initialization scale be for the result stated in theorem 4.3 to hold?
The authors mention that small initialization is needed to avoid the NTK regime and yet, to get a better sense of the results, it’s important to understand if they only hold for infinitesimal initialization or does they also hold for intermediate initialization scales (where the training accuracy might also have some effect, e.g. [1]).
Some experimental results on a synthetic dataset that demonstrate the paper’s main findings might help clarify this point.
- Symmetric dataset: The authors justified the symmetric dataset assumption by mentioning that this assumption can be easily satisfied with data augmentation. They also give a negative result for what happens when the dataset is not symmetric. However, since the mentioned data augmentation is not common practice, I worry that the symmetry assumption is too restrictive and weakens the paper’s positive results.

Clarity/writing: 
In general, the paper is well written, and I did not see any critical issues. Two suggestions that I think can improve the clarity:
- The o-minimal structure should be briefly explained\given some intuition.
- Some explanation should be given for why assumption A.5 is necessary.

Minor comments:
- Line 31: nature-->natural
- Equation between lines 159 and 160: ‘.’-->’,’
- Line 344: corollary general theorem--> corollary of the general theorem

Citations:

[1] E. Moroshko, S. Gunasekar, B. Woodworth, J. D. Lee, N. Srebro, D. Soudry, "Implicit Bias in Deep Linear Classification: Initialization Scale vs Training Accuracy", NeurIPS 2020.

---

Update: Thank you for your response and for explaining the assumption.

limitations_and_societal_impact: The authors mentioned and justified most of the limitations of their results. However, some of the limitations should be more thoroughly discussed, as mentioned in the main review.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proves that gradient descent may converge to the “max-margin” linear solution that attains the global optimum of the loss on finite two-layer Leaky ReLU nets trained on linearly separable and symmetric data. 

The contribution of this paper is mainly reflected in the strict assumption of data distribution (linearly separable and symmetric data). It is proved that GD has good convergence property in relatively simple nonconvex optimization problems (finite two-layer Leaky ReLU nets), and tends to get relatively “simple” solutions (the model complexity of “max-margin” linear solution is low, and it is resistant to overfitting risk).

main_review: Originality: This paper studies the properties of the convergence solution of GD under the specific data distribution and simplified network model, which is not a new problem. The originality of this paper is mainly reflected in the new assumption of data distribution (linearly separable and symmetric data), which leads to stronger conclusions than previous work (from KKT margin direction to global Max margin direction).

Quality & Clarity: This paper is theoretical research, and the process of proof is rigorous. In writing, the main results and the secondary lemmas are properly arranged and expressed clearly. Although there are some types in the appendix, it does not affect the understanding.

In the appendix, line 551 and line 560  have the missing references.

Significance: It is difficult to extend the assumptions to the deep neural network structure. Its significance only lies in helping us understand some simple structures in DNNs. Considering that the assumptions of the model and data distribution in this paper are not difficult to be realized through experiments, I hope that the authors can verify their theoretical results through experimental design by synthesizing the dataset.

If the author can provide some experimental results to verify the theoretical conclusion, I would be willing to raise the score to 7-8.

limitations_and_societal_impact: In this paper, some non-symmetric results are given in the appendix.

Theoretical research has no social impact.
review_title: null

Meta-review: This paper refines the implicit bias story for two-layer networks, analyzing settings where it is guaranteed to prefer certain simple linear solutions.  While the reviewers had some concerns, overall reviews and discussion were positive.  I urge the authors to carefully address reviewer comments during their final revisions.
Decision: Accept (Poster)