Tight Transition Time Bounds for Separable Logistic Regression at the Edge of Stability

arXiv:2610.01459v1 Announce Type: new Abstract: We study logistic regression on linearly separable data under gradient descent with a large constant stepsize eta. Such dynamics may exhibit a characteristic Edge of Stability phenomenon, in which the loss initially oscillates before transitioning to a stable phase of monotone decrease. Existing work provides a tight Theta(1) bound in dimension d=2 as eta o infty and conjectures a bound independent of eta in arbitrary dimensions dgeq 2. In this paper, we disprove this conjecture by showing that, for every fixed sample size ngeq 2 and sufficiently small margin gamma, the worst-case transition time is $Theta!left((logeta)^{min{n-2,d-2}}right) uniformly over dgeq2$. The key challenge in establishing a tight bound is that the sample contributing most strongly to the gradient can change repeatedly across iterations. To address this issue, we control such changes by induction on dimension and sample size, and construct matching hard instances.

Related

• Gradient Descent on Logistic Regression with Non-Separable Data and Large Step Sizes
• The Multiple Timescales of Gradient Descent on the Edge of Stability: A Perturbative Derivation of the Central Flow
• Variational Structure at the Edge of Stability

Source: arXiv cs.LG | 2026-10-02