acceptodds
Under review as a conference paper at ICLR 2027

On The Rate Of Convergence Of GD In Non Linear Neural Networks: An Adversarial Robustness Perspective

Abstract

We study the convergence dynamics of Gradient Descent (GD) in a minimal binary classification setting, consisting of a two-neuron ReLU network and two training instances. We prove that while GD successfully converges to an optimal robustness margin, effectively maximizing the distance between the decision boundary and the training points, this convergence occurs at a prohibitively slow rate, scaling strictly as . To the best of our knowledge, this establishes the first explicit lower bound on the convergence rate of the robustness margin in a non-linear model. Through empirical simulations, we further demonstrate that this inherent failure mode is present beyond our theoretical setting, exhibiting qualitatively similar slow convergence across a range of settings, including different network initializations, the Adam optimizer, and higher-dimensional inputs with wider networks. Our theoretical guarantees are derived via a rigorous analysis of the GD trajectories across the distinct activation patterns of the model. Specifically, we develop tight control over the system's dynamics to bound the trajectory of the decision boundary, overcoming the primary technical challenge introduced by the non-linear nature of the architecture.

Primary area:
learning theory
Keywords:
learning theory, optimization, adversarial robustness, neural networks, two layers neural networks, implicit bias, gradient descent convergence rate

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_HwFSOpenReview ↗
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:

  1. 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 ).
  2. 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
  1. Is there any obstruction with the linear reduction trick?
  2. 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

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+=(1,1,0,0)2,Z−=(0,0,−1,1)2,θ=2(w1,b1,w2,b2)Z_+ = \frac{(1, 1, 0, 0)}{\sqrt{2}}, \quad Z_- = \frac{(0, 0, -1, 1)}{\sqrt{2}}, \quad \boldsymbol{\theta} = \sqrt{2}(w_1, b_1, w_2, b_2) 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 Θ(log⁡t)\Theta(\log t) 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/5b_2^{(t)}-b_1^{(t)}>1/5 for all t≥7/ηt\ge7/\eta, 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-1010 networks on 2020 points in R5\mathbb{R}^5, 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/ln⁡t)\Theta(1/\ln t). 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.

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.

Reviewer_ACeSOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
2
Soundness
3
Read review
Paper summary

This work studies the convergence rate of gradient ascent in the minimal non-linear setting: a two-neuron network ReLU(w1x+b1)−ReLU(w2x+b2)\text{ReLU}(w_1x + b_1) - \text{ReLU}(w_2x+b_2), two training datapoints (x,y)=(−1,−1)(x,y) = (-1,-1) and (1,1)(1,1), and exponential loss. The main theoretical result is that, under initialization assumptions, the convergence rate to the optimal robustness margin is Θ(1/log⁡t)\Theta(1/\log t). The theoretical results are verified by experiments on synthetic data.

Critical strengths
  • The 1/log⁡t1/\log t convergence rate under minimal assumptions looks interesting and is verified by the numerical results.
Critical weaknesses
  • My main concern is the limited novelty and technical contribution of the rate analysis: (i) the first part shows that both neurons specialize each datapoint, and thus the training objective is decomposed into two independent linear problems; and (ii) the second part shows that both linear problems have a Θ(1/log⁡t)\Theta(1/\log t) convergence rate. It seems that a more general scenario of part (i) has already been studied by Phuong and Lampert (2020), and part (ii) follows from standard convergence results of linear models.

[1] Phuong, Mary, and Christoph H. Lampert. "The inductive bias of relu networks on orthogonally separable data." International Conference on Learning Representations. 2020.

Questions for authors
  • Can you provide a more detailed comparison to the previous literature, e.g., Phuong and Lampert (2020)?
  • Can you explain the technical difficulties in relaxing the strong assumptions, e.g., two datapoints?
2 comments

We thank the reviewer for bringing this paper to our attention. While the paper studies a related phenomenon, its setting and assumptions differ substantially from ours, and its results cannot be directly extended to our setting for the following reasons:

  1. Gradient Flow vs. Gradient Descent. The paper analyzes continuous-time Gradient Flow (GF) dynamics, whereas we study discrete-time Gradient Descent (GD). The distinction is important, as establishing results for GD requires accounting for finite step sizes and the possibility of crossing activation boundaries between consecutive iterations. Indeed, in their Section 3.1, Phuong and Lampert explicitly identify extending their analysis from GF to GD as an open direction for future work. Thus, their results do not directly cover the GD dynamics studied in our work.

  2. Network architecture and bias terms. Their analysis considers networks without biases, whereas our setting includes a bias in the first layer. This difference substantially changes the network's dynamics and the resulting analysis. One might attempt to eliminate the bias by lifting the data to R2\mathbb{R}^2, but the resulting dataset would no longer satisfy their "Support examples span the full space" assumption (which says that the samples of each label must span the space). Therefore, this transformation does not allow their results to be applied to our setting.

  3. Convergence rate analysis. Their work does not establish a convergence rate for the dynamics they study. Moreover, such a rate does not follow directly from standard convergence results for linear models. We provide a more detailed explanation of this distinction in our response to Reviewer HwFS.

Overall, while the two works investigate related phenomena, the differences in optimization dynamics, network architecture, and theoretical objectives make our settings fundamentally different. Thus, the results of Phuong and Lampert do not subsume the contributions of our work.

I thank the authors for the response. I think this paper would benefit from a more detailed discussion of the previous literature. Therefore, I keep my rating and suggest that the authors revise this work and resubmit to another venue.

Reviewer_QnwCOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies how gradient descent approaches adversarially robust solutions in a two-neuron ReLU network trained on two examples. Its main theorem states that the robustness-margin gap decreases at the sharp rate Θ(1/log⁡t)\Theta(1/\log t) for almost every initialization satisfying the small-loss assumption. The proposed explanation links persistent bias imbalance to logarithmic weight growth, while experiments investigate similar behavior under Adam and in wider networks.

Critical strengths
  1. The paper distinguishes eventual convergence to a robust classifier from the computational efficiency of reaching it, highlighting a limitation that asymptotic implicit-bias guarantees alone do not address.

  2. The central result provides matching upper and lower bounds on robustness-margin convergence, rather than merely establishing convergence to a limiting direction, although the proof concerns below require resolution.

  3. The decision-boundary expression clearly connects slow robustness improvement to a generically nonzero limiting bias difference divided by logarithmically growing weights.

  4. Explicit analysis of discrete-time dynamics. The analysis examines neuron specialization, activation-pattern transitions, and exceptional initializations instead of relying exclusively on gradient-flow arguments.

  5. Careful robustness measurement. The wider-network experiments compute decision-boundary distances through activation-region enumeration and constrained optimization, yielding exact margins up to numerical solver tolerance rather than attack-based estimates.

Critical weaknesses
  1. The guarantees concern two one-dimensional examples, two neurons, fixed output weights, and exponential loss. The almost-everywhere result also requires initial loss below 0.50.5, limiting conclusions about general architectures and arbitrary initialization. 6510_On_The_Rate_Of_Convergenc 6510_On_The_Rate_Of_Convergenc

  2. Lemma B.4’s negative-C1C_1 case is false as written. For a0=0,C1=−1,C2=1a_0=0,C_1=-1,C_2=1, the recurrence gives a2=−1−ea_2=-1-e, violating its stated logarithmic lower bound. Downstream uses need checking, although this does not itself disprove the main theorem.

  3. Proposition E.1 substitutes updated parameters into a fixed-activation loss formula, which need not remain valid when a neuron crosses a ReLU boundary. A transition-aware argument is needed to establish the claimed small-loss invariance.

  4. Insufficient justification of finite-time constants. The displayed bounds in Proposition E.4 and Lemma E.2 do not directly yield Theorem 5.2’s stated constant or its 7/η7/\eta starting time. The proof omits the necessary calculation.

  5. The wider-network comparison uses a deliberately margin-matched two-neuron model and demonstrates qualitative trajectory agreement. It does not establish an inverse-logarithmic rate or isolate the same causal mechanism in wider networks or Adam.

Questions for authors
  1. Can the authors correct the negative-C1C_1 case of Lemma B.4 and provide a transition-aware proof of Proposition E.1, clarifying whether these corrections affect Theorem 5.1?

  2. Can the authors explicitly derive the denominator 25+5log⁡(1+4ηt)25+5\log(1+4\eta t) and the threshold t≥7/ηt\ge7/\eta in Theorem 5.2 from the supporting lemmas?

  3. Does the proposed mechanism persist with non-orthogonal data geometry or trainable output weights, and can controlled experiments distinguish inverse-logarithmic convergence from other slow finite-time behavior?

  4. check weakness too

3 comments

We thank the reviewer for their constructive comments and the concrete counterexample. We address the concerns below.

W1: Scope and initialization. Our theorem concerns almost every parameter configuration in the small-loss regime, rather than a particular initialization scheme. Any training trajectory whose exponential loss tends to zero eventually enters this regime, irrespective of its starting loss. We added this clarification in the beginning of Section 4. Moreover, our wider-network and Adam experiments complement this conditional theorem with evidence of qualitatively slow margin evolution beyond its setting. We also added an experiment in Section 6.3 studying the effects of training both layers, its results suggest even slower margin convergence than with fixed output weights.

W2 / Q1: Lemma B.4. The negative-C1C_1 case is indeed incorrect, but unnecessary for our proofs. Every application uses positive coefficients, after negating the relevant decreasing sequence where appropriate. Restricting the lemma to C1,C2>0C_1,C_2>0 therefore leaves the downstream results, including Theorem 5.1, unchanged.

W3 / Q1: Activation-pattern transitions. We modified the proof of Proposition E.1 to be transition aware. None of the downstream results are affected.

W4 / Q2: Explicit constants. The revised proof supplies the missing calculations. Under Theorem 5.2’s assumptions, Proposition E.4 gives b2(t)−b1(t)>1/5b_2^{(t)}-b_1^{(t)}>1/5 for t≥7/ηt\ge7/\eta, while Lemma E.2 bounds the denominator. Consequently,

x⋆(t)≥1/55+log⁡(1+4ηt)=125+5log⁡(1+4ηt),for all t≥7/η.x^\star(t)\ge \frac{1/5}{5+\log(1+4\eta t)} = \frac{1}{25+5\log(1+4\eta t)}, \qquad \text{for all }t\ge7/\eta.

W5: Interpretation of the experiments. Appendix F.1 explicitly states that the comparison is not intended to identify an exact asymptotic rate for the wider network. Moreover, “collapse” does not mean replacing or simplifying the trained wide network: it continues training unchanged, alongside a separately initialized, margin-matched two-neuron comparator. We clarified this terminology in the revision. Initial margin agreement is imposed; subsequent trajectory agreement is observed. This supports qualitatively slow finite-time margin evolution, but does not establish an inverse-logarithmic rate or isolate the same causal mechanism.

Q3: Data geometry and trainable output weights. Our theoretical inputs are −1-1 and 11, and our wider-network experiments also use nonorthogonal data. These experiments provide evidence of slow margin evolution beyond the two-point setting, while keeping output weights fixed. Extending the analysis to trainable output weights remains open. Our new experiment shows slower finite-time margin convergence when both layers are trained than in the fixed-output model, whose robustness-margin gap provably decays at an inverse-logarithmic rate. While this does not establish the asymptotic rate for joint training, it provides compelling evidence of slow margin convergence beyond our theoretical setting.

Finally, following the reviewer's observations, we have conducted additional checks of the mathematical derivations and are now very confident in their soundness.

Reviewer_QnwCOpenReview ↗

Thanks for the clarification!

Thanks for clarifying and modifying the mathematical errors. I believe the paper has changed a lot, but need to be reviewed afresh. I therefore keeping my current rating and advise authors to correct all the errors, revise and resubmit to a new venue. All the best.

Thank you for your suggestions and for taking the time to review our response. We have already corrected the identified errors in the revised version of the paper uploaded here.

Comments on the paper

1 comment

We would like to thank all the reviewers for their careful reading of our paper and for their valuable feedback. We have uploaded a revised version of the paper, in which the relevant changes are highlighted in red for your convenience. We have also uploaded an updated version of the code, which includes the new experiment involving training both layers. We hope these updates make it easier to follow the revisions and assess our responses to your comments. Thank you again for your time and constructive feedback.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.