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 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.
Abstract (translated)
我们在一个最小的二元分类设置中研究梯度下降（GD）的收敛动力学，该设置由一个具有两个训练实例的两神经元ReLU网络组成。我们证明，在这些强烈的简化假设下，即使如此，GD仍然成功地以最优鲁棒性边界收敛，并有效最大化决策边界与训练点之间的距离。然而，这种收敛是以极其缓慢的速度发生的，其速度严格遵循$\Theta(1/\ln(t))$的规模。据我们所知，这是首次在非线性模型中明确建立的关于鲁棒性边界的收敛速率下限。 通过经验模拟，我们进一步展示了这一内在失败模式具有普遍性，在多个自然网络初始化的情况下表现出完全相同的严格的收敛速度。我们的理论保证是通过对GD轨迹进行严格分析而得出的，特别是对于模型的不同激活模式。具体而言，我们开发了对系统动力学的有效控制以限制决策边界的轨迹变化，克服了由架构非线性本质引入的主要技术挑战。 这段文字描述了一个关于梯度下降在特定神经网络结构上收敛速率的研究结果，并强调了该研究的重要性和新发现的理论基础。
URL
https://arxiv.org/abs/2603.02095
