Summary
In this paper the authors study the implicit bias of two layers neural networks with ReLU activation, in the setting where the data is composed of independant clusters that "dont' overlap" (i.e the probability of having the point of a cluster falling outo the support of another is small, e.g Gaussian of subgaussian). They study both the generalization properties and robustness of the solution obtained by training such network on those data.
They show that if the network suceed to fit the data (i.e the train loss falls below some threshold) and if we follow the gradient flow:
* then the weights converge *in direction*
* the network generalizes well
* however it converges to a non robust solution (if the dimension is high, the number of clusters is small, and the number of points is small too)
* whereas in the same setting robust solutions exist! But they are not "found" by following the gradient flow
* the adversarial attack associated is universal and transferable
Strengths
The paper does a good job at explaining the technical hypothesis, their significance, and the practical consequences.
The "proof idea" sections contain the right level of details to grasp the ideas.
The paper is easy to read despite its technical content.
While I am not familiar with the topic, the literature review seems thorough, in particular the contributions of the paper compared to existing works are clear.
The main conclusion is significant in my opinion: "However, the implicit bias also leads to non-robust solutions (susceptible to small adversarial 2-perturbations), even though robust networks that fit the data exist.", with the additionnal properties that "the adversarial attack associated is universal and transferable".
Definition 4.1 seems to be new, and it is an interesting concept to define robustness.
Weaknesses
The main weakness of the contribution lies in the hypothesis, that are extremely restrictive, and sometimes even more than it seems at first glance.
It is not clear if those hypothesis have a chance to hold on high dimensional image space, and if the main steps of the reasoning can be adapted to this setting, or if this is just specific to this particular setting and problem (see the section "Limitations" below about the setting).
## Thm 4.2
In Thm 4.2 the quantity is $\min{(Q_{+}/k,Q_{-}/k)}\geq c$ can be discussed a bit. In essence, the condition $c^2k=\omega(1)$ (l332) means that the number of clusters should be **big**, especially if a lot of clusters have the same labels (in which case $c\approx 0$). But on the other hand assumption 2.2 (third item) tells that the number of clusters should be small.
Moreover the dimension in which the theorems hold should be high (from what I understand of theorem 3.1), but there shouldn't be too much points per clusters (otherwise $n$ would be too big).
In overall, beyond artificial example 2., is there practical settings that fulfill those hypothesis? I'm scared that the results only apply to a high dimensional setting with very few points per cluster, that are all orthogonal, and that do not overlap.
Questions
## Suggestion
Based on the quality of the literature review, I think a "summary" table that contains a high level description of some significant prior works, with their associated hypothesis and main conclusions, would help to situate the paper better, in the spirit of:
| Paper | Hypothesis on model | Hypothesis on data | Conclusion
| ----------- | ----------- | ----------- | -----------
| Paper 1| two-layers ReLu | none | converges
| Paper 2| homogeneous | almost orthogonal | converges and generalizes
| Our | etc... | clusters | generalizes but not robust
## Question
How much do the results depend on the hypothesis that the activation is a ReLU ? This is part of the requirements of prior work, and clearly the case of $\phi(z)\geq z$ (l236). Do you think that extension to similar shaped activations is straighforward, or very difficult?
Rating
5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
Confidence
2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Limitations
The limitations of the hypothesis are discussed, but this part can be detailed in more depth. I have a few remarks and questions.
l207 : I think the formula can be simplified as
$$k(\max_{i\neq j} |\langle \mu_i,\mu_j\rangle|+C+1)\leq \frac{1}{10}(d - C + 1)$$
where $C$ depends on $d$ and $\sigma$. An interpretation can be given: "The centroids must be almost orthogonal to each other, and there shouldn't be too much of them.". Note sure if $\frac{1}{10}$ plays a special role, or if any other constant small than $1$ could have done the trick in the proofs. It is worth mentioning it, because this condition is hard to interpret.
We see that "it is worth noting that Assumption 2.2 implies that the data is w.h.p. linearly separable" shows that the hypothesis that the clusters are almost orthogonal is quite strong.
What I understand from "Finally, we remark that when k is small, our results may be extended to the case where σ > 1." (l227) hints that what you need is a "almost orthogonal clusters that don't overlap, so they are separable" kind-of hypothesis. I am not sure how much additional insights it brings compared to the work of Vardi, Yehudai, and Shamir [VYS22].
In particular, the upper bound on $n$ in Thm3.1 is quite surprising, fortunately the discussion l265 "It is noteworthy
that all existing non-vacuous generalization bounds for interpolating nonlinear neural networks in the
presence of label noise require n < d [FCB22; Cao+22; XG23; Fre+23a; Kou+23]." helps to understand why this is required.