mlsanityData to 7 Oct 2026

On the Rate of Convergence of GD in Non-linear Neural Networks: An Adversarial Robustness Perspective

arXiv 2603.02095 ↗First posted 2 Mar 2026cs.LG cs.AIcited by 0

Not on the map. Why?

Abstract (arXiv)

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 even under these strong simplifying assumptions, 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 Theta(1/ln(t)). 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 pervasive, exhibiting the exact same tight convergence rate across multiple natural network initializations. 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.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 17 of its 21 references that are in the map. First posted on arXiv 2 Mar 2026.

Builds on

17 of 21 references.

References · 17

  1. 2013Intriguing properties of neural networkscited by 5,114
  2. 2015Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classificationcited by 3,590
  3. 2017Evasion Attacks against Machine Learning at Test Timecited by 686
  4. 2017The Implicit Bias of Gradient Descent on Separable Datacited by 649
  5. 2019Gradient Descent Maximizes the Margin of Homogeneous Neural Networkscited by 308
  6. 2020Directional convergence and alignment in deep learningcited by 172
  7. 2018Convergence of Gradient Descent on Separable Datacited by 108
  8. 2021Gradient Descent on Two-layer Nets: Margin Maximization and Simplicity Biascited by 82
  9. 2018Risk and parameter convergence of logistic regressioncited by 81
  10. 2018Stochastic Gradient Descent on Separable Data: Exact Convergence with a Fixed Learning Ratecited by 63
  11. 2022Implicit Bias in Leaky ReLU Networks Trained on High-Dimensional Datacited by 46
  12. 2021Continuous vs. Discrete Optimization of Deep Neural Networkscited by 34
5 more
  1. 2021Fast Margin Maximization via Dual Accelerationcited by 33
  2. 2023The Double-Edged Sword of Implicit Bias: Generalization vs. Robustness in ReLU Networkscited by 23
  3. 2021Towards Understanding Learning in Neural Networks with Linear Teacherscited by 19
  4. 2023Adversarial Examples Exist in Two-Layer ReLU Networks for Low Dimensional Linear Subspacescited by 8
  5. 2023Achieving Margin Maximization Exponentially Fast via Progressive Norm Rescalingcited by 4

Built on by

Not cited yet.