Abstract
We study logistic regression on linearly separable data under gradient descent with a large constant stepsize $η$. 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 $Θ(1)$ bound in dimension $d=2$ as $η\to \infty$ and conjectures a bound independent of $η$ in arbitrary dimensions $d\geq 2$. In this paper, we disprove this conjecture by showing that, for every fixed sample size $n\geq 2$ and sufficiently small margin $γ$, the worst-case transition time is $$Θ\!\left((\logη)^{\min\{n-2,d-2\}}\right)$$ uniformly over $d\geq2$. 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.
Keywords
Subject
Publication details
- Journal
- Not available
- Open access
- Green open access
Cite this article
APA 7
Wen, H., Wen, K., & Teng, J. (2026). Tight Transition Time Bounds for Separable Logistic Regression at the Edge of Stability. https://omanscience.com/en/articles/tight-transition-time-bounds-for-separable-logistic-regression-at-the-edge-of-stability
MLA 9
Wen, Haodong, et al. "Tight Transition Time Bounds for Separable Logistic Regression at the Edge of Stability." https://omanscience.com/en/articles/tight-transition-time-bounds-for-separable-logistic-regression-at-the-edge-of-stability.
Chicago (author–date)
Wen, Haodong, Kaiyue Wen, and Jiaye Teng. 2026. "Tight Transition Time Bounds for Separable Logistic Regression at the Edge of Stability." https://omanscience.com/en/articles/tight-transition-time-bounds-for-separable-logistic-regression-at-the-edge-of-stability.
Harvard
Wen, H., Wen, K. and Teng, J. (2026) 'Tight Transition Time Bounds for Separable Logistic Regression at the Edge of Stability', Available at: https://omanscience.com/en/articles/tight-transition-time-bounds-for-separable-logistic-regression-at-the-edge-of-stability.
Vancouver
Wen H, Wen K, Teng J. Tight Transition Time Bounds for Separable Logistic Regression at the Edge of Stability. https://omanscience.com/en/articles/tight-transition-time-bounds-for-separable-logistic-regression-at-the-edge-of-stability
IEEE
H. Wen, K. Wen, and J. Teng, "Tight Transition Time Bounds for Separable Logistic Regression at the Edge of Stability," https://omanscience.com/en/articles/tight-transition-time-bounds-for-separable-logistic-regression-at-the-edge-of-stability.