We thank the reviewer for his insightful feedback. We now answer your different concerns.

It seems to be a well-known opinion [1-3] that the early alignment, learning sparse features, or simplicity bias is a double-edged sword and sometimes leads to overfitting [1] instead of good generalization.

Implicit or simplicity bias can have both positive and negative effects, depending on the data distribution. For instance, Ohad Shamir in The Implicit Bias of Benign Overfitting demonstrates cases where implicit bias can be detrimental to generalization, but also highlights situations where it is beneficial. Whether this bias helps generalization in practice depends heavily on the true data distribution. Our work specifically provides a theoretical explanation for the simplicity biases observed in prior empirical studies on in-context learning and diffusion, where this bias appears to be beneficial. Our conclusions align with these findings.

Comparison with [1]

[1] pursues a very different goal: demonstrating that the Neural Tangent Kernel interpolator can, in certain situations, generalize better than the feature learning regime (the regime considered in our work). Most importantly, in [1], the interpolating solution still generalizes in the feature learning regime, with the generalization error decreasing to 0 as $n\to\infty$, albeit at a slower rate than the NTK interpolator.

In contrast, in our work, interpolators (both NTK and feature learning) have a non-zero generalization error, even as $n\to\infty$. The novelty of our setting in the theoretical literature lies in demonstrating that avoiding interpolation is necessary for good generalization, (with the exception of very unnatural interpolators, such as linear regression with infinitely small interpolating spikes). To our knowledge, similar properties in prior theoretical work have only been explored through early stopping in training, as mentioned in the discussion section.

Comparison with [2]

[2] describes a benign overfitting phenomenon, where parameters converge to an interpolating solution that still generalizes well. They also show that this solution is not robust to small input perturbations. As mentioned in the discussion section, our contribution differs from benign overfitting: in our case, the parameters do not overfit, while any natural interpolating solution fails to generalize. The differing conclusions about interpolating solutions (i.e., whether they generalize or not) stem from the difference in regimes of dimension. Benign overfitting is specific to large-dimensional settings, whereas our setting does not require such assumptions.

Comparison with [3]

In [3], poor generalization is not a result of overfitting, but of how the overfitting occurs (i.e., the implicit or simplicity bias). Notably, [3] identifies a natural interpolating solution that generalizes perfectly. By contrast, in our setup, only highly unnatural interpolators generalize effectively.

The dataset this paper studies seems quite similar to [4]

The work [4] is fundamentally different from ours, both technically and conceptually. They show convergence to a data interpolator, which would result in poor generalization in our setup. In contrast, our key contribution is providing an example of convergence to a non-interpolating solution that generalizes well.

This difference arises because, in [4], a linear estimator overfits the data (e.g., linearly separable data in classification), whereas in our case, overfitting occurs only with more complex solutions.

Moreover, [4] assumes symmetric data, while we only require a symmetric distribution. Although these are equivalent when $n=\infty$, a main technical challenge in our work stems from the fact that optimization trajectories differ significantly when $n$ is finite, particularly since the width $m$ can be much larger than $n$.

The flow of the paper may benefit from a clearer structure

While there is no dedicated related work section, we extensively discuss related works and their connections to our study, particularly in the introduction and discussion sections. We chose this structure to maintain a better flow for the paper. Given the breadth and diversity of the related literature, we preferred to address it directly where it is most relevant, such as in the various paragraphs of the discussion section. If the reviewer feels it is necessary, we can add a related work section in the appendix to summarize these comparisons.

Additionally, in the revised version, we have switched the Discussion and Sketch of Proof sections to further improve clarity.

We thank the reviewer for their interest with our work and the opportunity to clarify these points.

First, we note that as long as the $(x_i)$ are pairwise non-proportional, any dataset $(x_i,y_i)$ can be fitted by a one-hidden-layer network with ReLU activation, even without a bias term. This property follows directly from the positivity of the NTK matrix (see, e.g., [A] Theorem 2 for the general case, and [B] Corollary 3.1 for data restricted to the sphere). Importantly, for ReLU activation, this memorization property does not require bias terms, in contrast to universal approximation.

Second, we agree with the reviewer that, in the limit of infinite samples, the global minimizer of the training loss (which coincides with the test loss) corresponds to the Bayesian estimator, which is linear in our data model. However, the key focus of our work is on the finite-sample regime, which introduces significant challenges and subtleties.

In this regime, the reviewer’s reasoning does not fully apply because the asymptotic cross terms cannot be neglected when both the sample size $n$ and the network width $m$ are large.

To summarize, the reviewer states that ERM corresponds to linear regression when $n$ is large. While this is true in certain cases, it does not hold when the network width $m$ remains significantly larger than $n$, as interpolation is still possible in this regime. Importantly, the convergence to linear regression in our analysis comes from an optimization problem rather than a representation limitation. This distinction is discussed in the paragraph “Absence of Interpolation.”

We hope this clarification resolves any misunderstandings.

Best regards, the authors

References

[A] Carvalho, L., Costa, J. L., Mourão, J., & Oliveira, G. (2024). The Positivity of the Neural Tangent Kernel.

[B] Montanari, A., & Zhong, Y. (2022). The interpolation phase transition in neural networks: Memorization and generalization under lazy training.

We thank the reviewer for his insightful feedback. We now answer your different concerns.

W1 Gap to practical setting

We agree that it is not immediately clear whether the considered setting reflects the behavior of more complex architectures encountered in practice. This challenge is common in the theoretical Deep Learning literature, where analyses are typically conducted on simplified models, though they might still provide insights into more complex settings. Notably, the study of Gradient Flow is widely used in the literature as it serves as a first-order approximation of SGD under small learning rates. As mentioned in the experimental details (Appendix A.1), our experiments are run with SGD and a general default initialization scheme. In the revised version, we have added additional experiments with GeLU activations in Appendix A.3 (and will add Adam+GeLU once we run these experiments). We prefer Adam rather than AdamW to follow the experimental setup of Raventos et al. (2024) and because our focus is on implicit regularization, thus avoiding explicit regularization techniques.

The experiments for GeLU (and preliminary observations for Adam) yield similar observations as in our original setup.

W2 notations

We chose to avoid using bold characters for vectors, as we found that incorporating them made the notation cumbersome, given the constant presence of vectors in our equations.

$\mathfrak{D}_n$ is defined as a function of two separate arguments $(w,\theta)$. This definition is intentional, as $\mathfrak{D}_n$ is continuous only in its second argument $\theta$, but not in $w$, even though $w_i(t)$ is included in $\theta(t)$. Note that in L177 (L187 in revised version), $w$ represents an arbitrary vector whereas $w_i(t)$ and $\theta(t)$ specifically refer to the network parameters.Thus, Definition 1 is mathematically rigorous and states static properties of $\mathfrak{D}_n$, as a function of two arguments.

Q1: Could you elaborate on the optimization threshold's dependency on the network's width m

As mentioned in the experimental details, the experiments are run with $m=10\ 000$ (this is now clarified in the main text). The optimization threshold in Theorem 2 is independent of the width $m$ (see L 403 in revised version). The strength of our result lies in the fact that it holds for arbitrarily large m, where interpolation remains possible even for very large n.

The only dependency of Theorem 2 with $m$ is through the probability of the result holding, which is of order $1-O(2^{-m})$. It is because we need at initialization that at least one neuron satisfies $a_j>0$ and at least one satisfies $a_j<0$.

Q2: definition 1 is not self contained

Thanks for this suggestion, we modified the definition to “a vector is said extremal with respect to G_n”. $\mathfrak{D}_n(\cdot,\mathbf{0})$ corresponds to the sub-gradient of $G_n$ in the new version. Extremal vectors correspond to the KKT points of the maximization/minimization problems of $G_n$ on the unit sphere in $\mathbb{R}^d$.

Dear Reviewer afoB,

As the discussion period is ending soon, we wanted to check if you have any additional questions about our paper.

Best regards,

The authors

We thank the reviewer for his insightful feedback. We now answer your different concerns.

the sample complexity bounds appear loose relative to empirical evidence

The theoretical analysis of this (seemingly simple) setting reveals quite intricate, and clearly leads to some looseness in the provided bounds. Yet, our empirical observations confirmed a similar dependency of the sample complexity bound wrt the dimension d. We added preliminary experiments with dimensions 10 in the revised version confirming that trend. A more polished version of these experiments, as well as results for d=20 will be included in future version. Note that these experiments require significant computational resources (see our response to reviewer EBuW).

the sections are somewhat disjointed due to the way discussions are interleaved with results

Thank you for the suggestion. In the revised version, we added further intuition and explanations about the early alignment phase in Section 2 and reordered Sections 4.1 and 4.2 to improve clarity.

We note that providing more detailed insights into the early alignment phase requires substantial space and has already been addressed in prior works (e.g., Maennel et al., 2018 and Boursier and Flammarion, 2024). Instead, we decided to focus on our own original contributions, including only the tools and understanding of the early alignment phase necessary for our analysis.

figure 1 could include some information about the distance between neuron weights

In the appendix of the revised version, we have included histograms of the mean cosine similarity with the OLS estimator at the end of training for different values of n. These results confirm the predictions of Theorem 2.

Could the authors empirically or theoretically discuss if sample complexity influences when this early training phase occurs?

This training phase occurs in a general setting, provided the initialization scale is sufficiently small. After concentration, the sample complexity $n$ has little impact, as the early-phase dynamics are primarily driven by the expected value $G(w)$. Indeed, the dynamics of this phase depend only on the function $G_n$​, meaning that the sample complexity $n$ influences the dynamics only through its effect on the geometry of $G_n$​. The goal of Section 3 is to study this influence of $n$ on the shape of the function $G_n$​ (or equivalently, the vectors $D_n$​). In the general setting of Section 3, the initialization scale threshold is independent of $n$ for large enough $n$, as $D_n​(w)$ concentrates towards $D(w)$.

Ethical concerns about similarity with Boursier and Flammarion (2024) in section 2

Our work builds on the results of Boursier and Flammarion (2024) and the goal of section 2 is precisely to summarize these results as the starting point of our analysis. To avoid any additional confusion, we follow the same notations (hence the similarity in Section 2.1) and definitions. We now explicitly state at the beginning of section 2 that we introduce here the results of Boursier and Flammarion (2024). However, the main explanatory paragraphs in Section 2.3 (early alignment and its implications) are novel.

We thank the reviewer for their useful feedback.

Now we answered the different concerns of Reviewer uxcs, we would be happy to answer any remaining concern on your side if there is any.

We thank the reviewer for his positive and insightful feedback. Additionally, we thank you for all the suggestions of rewriting that have been incorporated in the revised version. We now answer your different concerns.

gap between theoretical setting and empirically observed phenomena

The exact reason for the observed phenomena in practice remains unclear. It could stem from the stability issue raised by Qiao et al., the problem of convergence toward local minima, a combination of these factors, or even more complex considerations arising from more complex data structures. The goal of our work is to propose a plausible theoretical explanation for the observations in ICL and diffusion models. Validating whether any of these factors fully explain the empirical observations would require extensive experiments, which we leave for future work. Notably, we could consider the ICL experiment of Raventos et al. (2024) with significantly smaller learning rates.

Conjecture of effective width in the orthogonal training data setting

In the work of Boursier et al., the effective width is only 2 at the end of training. However, achieving this minimal width requires a significantly overparameterized network, with roughly $m\gtrsim 2^n$. This overparameterization is necessary to ensure that, at initialization, there exists at least one neuron $w_i$ positively correlated with all data points $x_k$ such that $y_k>0$, and similarly, another neuron $w_j$ positively correlated with all negative-labeled data points.

Studying their orthogonal data setting under mild overparameterization (eg $m=poly(n)$) remains an open problem, as the initialization condition would no longer hold in such cases. Consequently, multiple neurons would be required to fit all positive labels (and similarly for negative ones). Preliminary investigations suggest that this scenario would lead to an effective width that increases with $n$. However, determining the exact dependency on $n$ would require further analysis.

How essential is the ReLU activation

Homogeneous activations (e.g., ReLU or leaky ReLU) are crucial to the analysis of the early alignment phase and, more generally, to many analyses that allow an arbitrarily large or infinite width. While our work could be directly extended to any leaky ReLU activation, we focused on ReLU for the sake of clarity

When considering more general activations (e.g. differentiable ones), the early alignment phase still happens (see Kumar and Haupt 2024), yet it does not break omnidirectionality of the neurons as $m\to\infty$. In consequence, infinitely large networks with differentiable activations should still interpolate at the end of training (see Chizat and Bach 2018). Nevertheless, achieving this interpolation in practice often requires very large $m$ in practice, as interpolation of the data seems even harder to reach with GeLU activations as suggested in our new experiments.

How much compute was needed

The experiments were run on a personal computer (MacBook pro) and required approximately 100 hours of compute. This relatively long time is specifically due to the fact that we considered largely overparametrized networks and long training times, to ensure that convergence of the parameters was reached. The precision about the required compute has been added in the revised version of the paper.