Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: (a) This belongs to the literature of implicit bias/inductive bias, which has
gained a great deal of attention among theoretical enthusiasts with an
optimization leaning.

(b) The paper is carefully laid out and argued, and is at a nice level
of clarity and precision.

(c) The mathematical argumentation seems to me correct; 
however I haven't checked line-by-line.

(d) The situation being studied is very very special
and doesn't much correspond to the big kahuna
deep learning. Nevertheless the intellectual clarity
of this special case is quite appealing.

(e) The implied conclusion seems rather special
as well. From one viewpoint it says that if you start 
from the get-go with perfect 
separation of a particular strong form,
then the future evolution of the training 
can never spoil things. This is a very weak statement,
but I suppose if we can't get results here in a very special case
that we can understand well, then the 
general situation is truly hopeless.

Specific Comments.

(1) Why is this max-margin if your constraints only consider one class. It seems to be more of a finding a minimum-norm vector aligned with all training data of that class. Its unclear why the concept of separating margins comes in.

(2) “Theory III: Dynamics and Generalization in Deep Networks” by Banburski et al. also considers general deep relu networks and shows that the resulting margins are max-margin—requiring only separability, not orthogonal separability. In addition, that paper uses traditional DE methods rather than relying on lesser-known extremal sector techniques. Can you discuss or highlight why the simpler example in this paper might lead to insights not found in the other paper.

(3) While the paper says that it is not directly applicable to deep nets, it draws motivation from the popularity of that literature. In that spirit, to justify such an evocation, can you show at least one experiment on a non-synthetic dataset such as MNIST/CIFAR/etc (perhaps even simplified with hand-engineered preprocessed features and subsetted to two-classes) that would support the potential connection to deep learning?

(4) Can you provide any evidence why datasets would become orthogonally separated? Is there some feature
engineering procedure that tends to produce orthogonal separation?

(5) In Figure 1, variance is strange: shows one big outlier, but the plotted projection shows two roughly-equal-magitude directions of variation.

(6) It is unclear how Definition 2 relates to strict extremal directions as defined by the sign patterns.

(7) G should be clarified: What G is and what it represents should be explained to make the results more insightful



 16m 50s

Type a message

review_title: Very special case of inductive bias, very well presented.

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper studies the inductive bias of gradient flow for two-layer ReLU networks for classification problems. Under an orthogonally separable data assumption, it is shown that each node of the ReLU network will converge to one of two directions that linearly separate the data. I think the inductive bias of neural network training is a very important research problem and the result of this paper looks interesting. However, I also have the following concerns about this paper. 

Perhaps the most obvious limitation of this paper is that the orthogonally separable data assumption is too strong. Under this assumption, the classification problem can be solved trivially: one can simply randomly pick a training example and use it as the parameters in a linear predictor. It seems to be highly unlikely that this assumption can be satisfied by any challenging real-world problems.

Moreover, the current submission lacks discussion and explanation of their results:

(a) The result of this paper seems to be weaker than the result in Lyu & Li (2020), while also requiring much stronger assumptions than Lyu & Li (2020).  Note that the inductive bias given in Lyu & Li (2020) is in the form of a maximum margin KKT point of the ReLU network (as a *nonlinear* classifier), however, the result in this paper is more related to the maximum margin solution of linear models, which in general may be much worse than the margin achievable by wide neural networks. Therefore I guess the most straightforward question the authors should clarify is whether under their setting w^+ and w^- indeed gives a KKT point of the *nonlinear* maximum margin problem given by Lyu & Li (2020).

(b) To my knowledge most of the inductive bias results for classification problems (cross-entropy/exponential loss) do not rely on specific initialization methods (except certain assumptions to guarantee achieving zero training error) (Soudry et al. (2018), Ji & Telgarsky (2019b), Lyu & Li (2020)). Therefore the authors may consider providing more explanation on why they require the specific initialization.

(c) In Section 6 it is mentioned that Li & Liang (2018) contain the training in the neighborhood of the (relatively large) initialization. While this is to some extent true, I find this comment not very convincing. When studying inductive bias, it is natural to restrict the training to a fixed training dataset, i.e. to treat the online SGD in Li & Liang (2018) as finite sum SGD by considering a uniform data distribution over training samples. In this case, since Li & Liang (2018) considers classification with cross-entropy loss, the weights will eventually go to infinity and therefore will not stay in the neighborhood of initialization forever, as is shown in Lyu & Li (2020). This is also true for other classification results in the lazy training setting including [1,2,3,4]. It seems that a combination of these results mentioned above and the result by Lyu & Li (2020), which has been discussed in Ji & Telgarsky, 2020 and [5], can already imply a much stronger result compared to this paper. 




[1] Zou, Difan, Yuan Cao, Dongruo Zhou, and Quanquan Gu. "Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks." arXiv preprint arXiv:1811.08888 (2018).

[2] Nitanda, Atsushi, Geoffrey Chinot, and Taiji Suzuki. "Gradient Descent can Learn Less Over-parameterized Two-layer Neural Networks on Classification Problems." arXiv preprint arXiv:1905.09870 (2019).

[3] Cao, Yuan, and Quanquan Gu. "Generalization bounds of stochastic gradient descent for wide and deep neural networks." NeurIPS 2019.

[4] Ji, Ziwei, and Matus Telgarsky. "Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow relu networks." ICLR 2020.

[5] Moroshko, Edward, Suriya Gunasekar, Blake Woodworth, Jason D. Lee, Nathan Srebro, and Daniel Soudry. "Implicit bias in deep linear classification: Initialization scale vs training accuracy." arXiv preprint arXiv:2007.06738 (2020).



review_title: The assumptions may be too strong

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: This paper characterizes the implicit bias of gradient flow of two-layer ReLU networks on orthogonally separable data trained on the logistic loss. The problem of characterizing the implicit bias of gradient descent on neural networks is an important one, and while the authors do make fairly strong assumptions on the data (data corresponding to the different labels lie in separate orthants), the proof is novel, interesting and non-trivial. The proofs are carefully carried out and seemed as far as I could verify.


A few questions:
1. Is it possible to characterize what the outer weights (a's) converge to? If yes, I would suggest that the authors include this either in the main theorem, or as a comment after the theorem.
2. Does a similar result hold if the network also has bias variables? 
3. Can linearly separable data be made into orthogonally separable data (by appropriate pre-processing) and by also training a bias term?
4. How are the lambda_j's chosen in the near zero initialization? The current description of choosing lambda_j on page 2 is quite vague.
5. I would also urge the authors to add the additional assumption about the positive and negative examples spanning the entire space in Section 2 along with the other assumptions. 
review_title: Good paper that studies an important and interesting problem. Provides a clean solution.

final_score: rating: 7: Good paper, accept
review_content: This paper studies the inductive bias of two-layer ReLU networks trained by gradient flow. The main challenge is to analyze the global convergence of the flow dynamics. Under a special assumption that the data are orthogonally separable, the paper shows that the dynamics converges to a unique max-margin solution. I find that the paper is well written, modulo some assumptions on the data that would be better to be made more rigorous. The overall quality is good. The novelty compared to the literature is that this paper provides a global analysis of the non-linear non-smooth dynamics without going into the over-parameterized regime. 

In Theorem 1 of the paper, what does it mean « For almost all such datasets? » What is the probability distribution of (X,y)? Is there any more precision condition on \lambda, which controls the norm of the initial weights? 

In Lemma A.3, what does it mean « genetic position »? I think what is needed is to assume that the probability that all the x_i lie on some hyperplane is close to zero. This assumption is crucial for (43) to hold, therefore I think it should be made more precise. Or to put in a less probabilistic, one may assume that the maximal number of samples {x_i} that lie on some hyperplane is smaller than the dimension of x_i.

For clarity, is the experiment in 5.2 uses the same data (X,y) as in 5.1? 

Some typos or confusions of notations are listed below:
- \ell^+(t) right before (18), is confusing, as \ell^+ is a function of \theta, I would suggest to use L^+(t)  = \ell^+(\theta(t)) 
- Change W+(t) -> W_(t) to (24)
- \ell’_i(t) in (40) and (41) are also confusing, write L_i’(t) = \ell_i’(\theta(t)) ? 
- Change \Sigma[i,j] -> \Sigma[j,i] in (42), (43), etc. 

review_title: I find that the paper is well written, modulo some assumptions on the data that would be better to be made more rigorous. 

Meta-review: The paper shows that under a very restrictive assumption on the data, ReLU networks with one hidden layer and zero bias trained by gradient flow converge two a meaningful predictor provided that the network weights are randomly initialized with sufficiently small variances. While there is some overlap with a paper by Lyu & Li (2020), the paper under review establishes its results for networks with arbitrary widths whereas using the results of Lyu & Li (2020) works, at least so far, only for sufficiently wide networks. The assumption on the data is anything than realistic and actually any "simple, conventional" learning algorithm can easily learn in this regime. Nonetheless, getting meaningful results for neural networks is still a notoriously difficult task and for this reason, the paper deserves publication.   
Decision: Accept (Poster)