Grokking at the Edge of Linear Separability

Thank you for reviewing our paper. We have addressed your main concerns in detail in the global response. Briefly, we have made the following changes to the manuscript: (a) reorganized the paper to enhance clarity, and (b) generalized our analysis beyond the constant-label approach, demonstrating that Grokking persists near the critical point under broader conditions.

Responses to the questions:

1. "It’s unclear how the remaining four points relate to grokking..." We are a bit unsure about the exact concern. All the listed points in the paper are tied directly to mechanisms that enable Grokking in our setup. Our main point is that Grokking is related to criticality, and the remaining points demonstrate why critical behavior comes about in this setting. Explicitly, point 4 discusses "delayed generalization," a concept almost synonymous with Grokking, ubiquitously used in the Grokking literature, for instance in [Humayun et al. 2024, Lee et al. 2024, Liu et al. 2023] and references within.

2. Over-simplicity of the setup due to constant-labeling: As explained in the global response, we have thoroughly addressed this concern by exploring a more generalized setup. However, the setup itself remains quite simple — which we consider to be a strength rather than a weakness. Simplicity is crucial for developing models that are easy to analyze and that highlight the fundamental elements driving phenomena, which is the essence of the scientific process. In our case, the key takeaway from the setup is that Grokking occurs near critical points in the long-time asymptotic dynamics of training (see the global response for more details).

Regarding your comments, it was hard for us to tease out specific improvements that we could apply. If there are particular aspects you found unclear or challenging to understand, we would greatly appreciate a more detailed criticism.

We greatly appreciate the time you took to read our manuscript, we found your suggestions very helpful in improving our manuscript.

1. Your primary concern seems to be the simplicity of the setup. Indeed, our results are based on Soudry et. al., Nacson et. al, and so on, but our main contribution is not exploring the implicit bias of GD in classification, but rather to show that this bias inevitably leads to a critical point, and that this criticality is responsible for grokking, at least in this scenario (but also in other scenarios). In addition, as you rightfully suggested, we have generalized our results such that the data distribution does not need to be Gaussian, and apply also when the labels are not constant - see the global response for more details.

2. Regarding the missing related work (and question 3): Thank you for pointing out these works which we were not aware of. They are now cited in the revised manuscript. Our contribution is quite different than both of these works. Golecha et. al. provide ways to measure and quantify progress during gorkking, but do not discuss criticality as the underlying mechanism, which is the main point of our work. Humayun et. al. is more related, but they discuss adversary examples and the geometry of feature space. Their phase-transition is different than ours since it is a dynamic transition (i.e. a change in the regime of training dynamcis as function of time) and not a static one as in our case (i.e. a discontinuity of the $t\to\infty$ limit of generalization). It is a different class of dynamical phenomena.

3. Regarding other issues (jargon, introduction, and minor concerns): We completely agree. Thanks for pointing these out. We have fixed all these issues in the revised manuscript.

4. Response to questions:

   1. We mean $\lambda \rightarrow 0.5^{-}$. We fixed it throughout the paper, thanks.
   2. Insights for more realistic settings: this is a very important question - we address it in point 2 of the global response.
   3. We answered above.

If you found our answers satisfactory, we would appreciate reconsidering the score. Regardless, we sincerely thank you again for your detailed comments, which were incredibly helpful.

Thanks for your comment. Could you please highlight the revisions in the paper with a different color so that we can easily spot the changes? Otherwise, maybe you can provide a list of revisions as a comment.

Dear Reviewer eABc,

We would like to bring to your attention our latest revised manuscript, where we have changed much of the text in order to improve readability following your latest comments. In particular, we have highlighted in red the newly phrased theorems, definitions and propositions. We have also added the loss function to the introduction.

For all changes, please see the following diff file: https://filebin.net/vu814u4iv7quxmux

We kindly ask that if you have any further questions or issues, please let us know, as we would be happy to make any effort to improve our paper further before the end of the discussion period.

We wish to thank you for your detailed feedback. It seems like your main concern is readability issues with the manuscript. Within the available time-frame, we have made efforts to enhance the quality and presentation of the paper (with plans for further improvements later). Please see the revised manuscript.

Secondly, we have significantly expanded the generality of our model by considering other data-input distribution such as non-isotropic Gaussians and bi-model distributions, as well as non-constant labeling, as detailed in the global response.

Regarding weaknesses 2 and 3: you are correct, thank you for highlighting these weaknesses to us, as they are easily resolved. We have emphasized both points. The "constant label" point appears in the abstract and explicitly in the model setup, and the difference between "our" separability and "Soudry/Telgarsky" separability is discussed in Line 195.

Regarding the questions:

1,2,3, and 5 - Fixed. Thank you.

4 - Regarding the non-asymptotic version of Wendel's theorem: In Appendix A we provide both the original result of Wendel for finite $N,d$ result (Eq. (17)), which is the CDF of a binomial distribution, and its limiting behavior in the limit $N,d\to\infty$, which is a step function.

6 - Thank you for raising this important point which requires clarification. The main idea that we want to communicate is that Grokking in both scenarios is related to the fact that the model parameters are in the vicinity of a critical point. In that sense $\lambda$ and $\alpha$ are related as they are the so called "order parameters" that determine criticality. However, there isn't a direct mapping between them, as the two settings likely correspond to a different universality class, see also point 2 in the global response above.

If you found our answers satisfactory, we would appreciate reconsidering the score. Regardless, thanks again for the great feedback.

We thank you for your detailed review, and appreciate the positive feedback. Regarding the weaknesses:

1. We have added to the manuscript an appendix on discriminative labeling and more general input data distributions, please see the global response for more details.
2. That's a very good question, we answer it in detail in point 2 of the global response.

Answers to questions:

Q1a. Random labels pose a conceptual problem, since in that case the population distribution is undefined. Could you please clarify? In the revised manuscript (appendix H) we provide experiments with binary datasets and show that our results hold qualitatively when the dataset is highly imbalanced. Q1b. This is a good point. We note, though, that the Gaussianity of the data in this manuscript only serves as a distribution that achieves almost-separable data in some parameter regime. If the dataset is on the verge of separability, we predict that the norm of the over-fitting solution will diverge regardless of the data distribution.

Q2. "double descent" can be used to describe at least two different phenomena: (a) a non-monotonic dependence of the generalization loss on training time (e.g. in Davies et. al. 2024) and (b) a non-monotonic dependence of the asymptotic generalization performance on model complexity (e.g. Schaeffer et. al. ICLR 2024). Our model deals with double-descent of type (a) but not of type (b). Interestingly, both types of double descent are related to critical behavior -- Schaeffer et. al. demonstrate explicitly that the non-monotonicity in the generalization performance is due to an "interpolation threshold" which is a critical point (we alluded to that in lines 55 and 121). Our manuscript, in accord with Davies et. al., show that type (a) is also related.

Q3. Your description is correct. The idea was that the only thing that matters to the dynamics is the distance of the origin from the convex-hull of the dataset (the margin), and in the Gaussian model this is just a function of $\lambda$ in the limit $N,d\to\infty$. Therefore, we replaced the dataset by a simpler dataset consisting of two points only, but with the same dependence of the margin on $\lambda$. We have clarified this in the revised text.

Dear reviewers,

We would like to thank you again for engaging with us. We believe your constructive comments have greatly improved our paper. Having addressed most of your concerns, it seems that the only common issue that remains is the writing and presentation of the paper. We have thoroughly edited the paper to address these concerns, and we believe that the presentation and readability are now significantly improved thanks to your criticism. The changes include:

1.⁠ ⁠Formalizing all claims as numbered propositions, as suggested (marked in red in the updated pdf).

2.⁠ ⁠Adding a roadmap at the beginning, as suggested.

3.⁠ ⁠Reorganizing the paper to highlight the main ideas more clearly, making it more accessible to the reader. We have moved some of the discussion regarding the toy model to the appendix and emphasized in the introduction and discussion the main takeaway - that Grokking in this setting results from near-critical behavior, and that this applies also to several other occurrences of grokking in the literature.

4.⁠ ⁠Addressing additional small issues related to jargon and providing further clarification on points raised by the reviewers. We have highlighted some of the key changes in red, while the rest of the changes are spread throughout the paper.

A diff pdf file (from the initial version) is attached here: https://filebin.net/vu814u4iv7quxmux

We hope that the new revision resolves any remaining concerns regarding the presentation. There is not much time left, but if you have any more requests please let us know and we will try our best to address them.