- Rating
- 1
- Confidence
- 4
- Informativeness
- 1
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
The paper studies implicit bias of GD in one-hidden layer ReLU neural networks with width 2. The paper gives a two-sample example with which GD iterates achieve exponentially slow convergence of the robustness margin (Theorem 5.1). This is done by first showing that neurons "specializes" eventually, which means that activation pattern gets frozen after sufficiently large GD iterations. Specialization reduces GD iterates to a tractable form (eq-9) - (eq-12). Using this tractable form, the authors analyze the dynamics and thereby showing that the robustness margin (eq-14) converges exponentially slow.
Critical strengths
The paper gives an explicit example of exponentially slow convergence of GD toward the robustness margin for one-hidden layer ReLU neural network with width 2.
Critical weaknesses
Although their exact slow convergence result may have not appeared in the literature, it is not surprising and does not seem novel enough for acceptance for two reasons:
- If my understanding is correct, after specialization is established, i.e. (eq-9) - (eq-12) are established, we can view the GD iterates as that of binary linear classification. This is the same trick used in the proof of directional convergence two-layer neural networks in Hashimoto 2026 (https://arxiv.org/abs/2505.16204) and formalized as Corollary 8 of Soudry et al. 2018 (https://arxiv.org/pdf/1710.10345). In fact, once specialization is established, their Theorem 5 should follow relatively easily from Theorem 3 of Soudry et al. with a bit of elementary computation. Thus, the linear trick should allow them to simplify their proof significantly (Appendix E ).
- Given the linear trick, their slow convergence result is not surprising. For binary linear classification, the slow convergence is already established by Soudry et al. and Nacson et al. 2019 (https://arxiv.org/abs/1803.01905), i.e. For homogeneous linear classifiers under Euclidean adversarial perturbations, the robustness margin is same as normalized margin and Theorem 4, Nacson et al. gives the same convergence rate. Although the robustness margin in this paper is not identical to the normalized margin of the transformed linear classifier, the convergence rate seems to follow from the classical result in linear classification. Therefore, I am not convinced that the paper establishes a sufficiently new phenomenon beyond the existing linear classification literature.
Questions for authors
- Is there any obstruction with the linear reduction trick?
- Can you show that the exponentially slow convergence is a more general phenomenon rather than just giving an example for width 2 one-hidden layer networks?
5 comments
Thank you for your response. I would first like to clarify that I did not claim that your result follows from Nacson et al. (2019). I cited Nacson et al. only to point out that logarithmically slow convergence of the robustness margin is already known in linear classification. My argument that your asymptotic result follows from existing theory concerns Soudry et al. (2018), together with elementary calculations.
Once the GD dynamics reach the specialized regime of Assumption D.1, Equations (9)–(12) are exactly GD updates for a linearly separable classifier in a transformed four-dimensional feature space. This type of reduction is already covered by Corollary 8 of Soudry et al. (2018). Their Theorem 3 gives
\qquad \theta^\star=(1/2,1/2,-1/2,1/2).$$ Consequently, $$w_1^{(t)}-w_2^{(t)}\sim\log t.$$ The numerator of Equation (14) also appears straightforward to handle. Using your notation in Appendix B, $v_1=w_1^{(t)}-b_1^{(t)}$ and $u_2=w_2^{(t)}+b_2^{(t)}$ are invariants of the GD dynamics after specialization. Moreover, $u_1^{(t)}=w_1^{(t)}+b_1^{(t)}$ and $-v_2^{(t)}=b_2^{(t)}-w_2^{(t)}$ satisfy identical scalar recurrences of the form $$a_{t+1}=a_t+\eta e^{-a_t}.$$ Setting $A_t=e^{a_t}$, the recurrence implies $A_{t+1}-A_t\to\eta$, and hence $a_t=\log(\eta t)+o(1)$, independently of the initialization. It follows that $u_1^{(t)}+v_2^{(t)}\to0$, and therefore $$b_2^{(t)}-b_1^{(t)} \longrightarrow\frac{v_1+u_2}{2}.$$ The required nonvanishing argument is not difficult once the Jacobian non-singularlity is established, which is not so difficult to check. Therefore, using Equation (14), $$\gamma^\star-\gamma(\theta^{(t)}) =|x^\star(t)| \sim\frac{|v_1+u_2|}{2\log t},$$ which establishes the matching asymptotic rate in Theorem 5.1. It may be the matter of positioning. Slow convergence is known for linear classifier as I pointed out already. So, given the reduction trick, showing slow convergence itself does not appear to be novel enough. Showing that slow convergence holds for "almost all intialization" sounds good but it is limited to the particular two samples. What I asked in my second question is exactly this. If you proved slow convergence for more general data and networks, it would have made a difference.Thank you for clarifying the connection to Soudry et al. and providing the simpler asymptotic argument. We agree that, once specialization is established, your calculation recovers the matching asymptotic rate. We appreciate this perspective and estimate that incorporating it could shorten our proof by approximately 2–3 pages, while retaining the arguments needed for our finite-time guarantees.
The distinction we would emphasize is between analyzing the dynamics after specialization and establishing that the original nonlinear dynamics reach and remain in that regime. Corollary 8 of Soudry et al. assumes that the activation pattern eventually becomes fixed; it does not establish this property for our network. Our analysis proves, under the theorem’s assumptions, that the neurons reach the required specialized configuration and that subsequent updates preserve it. These conclusions require controlling the preceding activation-pattern transitions and are not replaced by the proposed post-specialization calculation. Thus, the connection to linear theory explains the eventual rate, but its applicability to the original nonlinear trajectory is itself part of the result. Establishing that specialization occurs and persists is not immediate, and we therefore believe that the availability of a linear description afterward does not, by itself, make the robustness conclusion unsurprising.
Our contribution also includes explicit finite-time guarantees: Theorem 5.2 provides a concrete lower bound on the robustness-margin gap, with specified constants and a validity threshold. These guarantees are not supplied by the asymptotic reduction alone. We will clarify this division between the nonlinear dynamics, the asymptotic calculation, and the quantitative bounds.
We also understand that your question about broader settings concerns theoretical generalization, rather than additional empirical evidence. Our experiments support the relevance of the phenomenon beyond the analyzed model, but do not establish such a generalization. Even in this minimal setting, establishing specialization and controlling activation-pattern transitions already require an involved analysis. Extending these arguments and the resulting robustness guarantees to broader data and networks appears challenging and remains an open problem that we do not currently know how to resolve.
We thank the reviewer for suggesting this connection. The linear reduction offers a potential alternative approach, but recovering the same guarantees requires addressing several remaining steps:
Relating the margins. As the reviewer notes, the margin studied by Nacson et al. differs from our input-space robustness margin. It remains to justify that bounds transfer between these quantities without losing sharpness. Moreover, the unit-normalized linear problem obtained after specialization: Z+=2(1,1,0,0),Z−=2(0,0,−1,1),θ=2(w1,b1,w2,b2) falls into the case explicitly excluded in their footnote 3: the leading-order term underlying their generic lower-bound analysis vanishes. That argument therefore does not directly yield a nontrivial lower bound in this case and requires separate treatment. These distinctions are essential because our result establishes matching upper and lower bounds for the original robustness-margin gap, which the linear reduction alone does not guarantee.
Ruling out cancellation. Lemma D.7 and the proof of Proposition D.6 establish that the bias difference approaches a nonzero limit and eventually has a fixed sign, under the proposition’s assumptions. Merely showing that both biases grow as Θ(logt) would not exclude cancellation of their difference, which yields perfect robustness. Controlling this difference is essential to our lower bound and required substantial effort. Nacson et al.’s generic nonvanishing argument concerns a different quantity and excludes the symmetric lifted dataset arising from the proposed reduction. Thus, this reduction does not directly supply the bias-difference control required here.
Obtaining explicit finite-time guarantees. The relevant asymptotic results do not provide an explicit validity threshold for our robustness-margin lower bound. Recovering Theorem 5.2 requires uniform finite-time control of the bias difference, not merely its limiting value or the growth of the individual parameters. The newly added Proposition E.4 establishes b2(t)−b1(t)>1/5 for all t≥7/η, while Lemma E.2 bounds the denominator. Together, these yield our explicit margin bound. An alternative derivation would need to supply comparable quantitative estimates; they do not follow by simply substituting constants into the stated asymptotic rate.
Our analysis addresses these steps directly. The proposed reduction may offer an alternative route, but its remaining gaps are potentially significant: they concern establishing the matching lower bound and explicit finite-time guarantees, which are central to our contribution. Until these steps are supplied, the reduction alone does not demonstrate that our results follow routinely from existing linear theory.
Regarding broader settings: Our experiments already examine width-10 networks on 20 points in R5, under GD and Adam. We also added an experiment in Section 6.3 showing slower finite-time margin convergence when both layers are trained than in the fixed-output model, whose robustness-margin gap provably decays at the inverse-logarithmic rate Θ(1/lnt). These experiments provide evidence of qualitatively slow margin evolution beyond the theoretical setting, though not a proof of the same asymptotic rate. Extending the theoretical guarantees remains an open direction.