Tight Transition Time Bounds for Separable Logistic Regression at the Edge of Stability
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 η→ ∞ and conjectures a bound independent of η in arbitrary dimensions d≥ 2. In this paper, we disprove this conjecture by showing that, for every fixed sample size n≥ 2 and sufficiently small margin γ, the worst-case transition time is Θ ((logη)min{n−2,d−2}) uniformly over d≥2. 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
- Large Stepsizes Federated Learning on Logistic Regression with Linearly Separable Data: The Case of Heterogeneous Devices
- Deterministic Bounds on Accuracy and Stability of Metric-Space Regression and Classification
- Data generation for the logistic regression model under controlled conditions
- A penalized logistic generalized regression estimator
- Logistic Gaussian process density regression: a generalized Bayesian approach
BibTeX
@misc{wen2026tight,
title = {{Tight Transition Time Bounds for Separable Logistic Regression at the Edge of Stability}},
author = {Haodong Wen and Kaiyue Wen and Jiaye Teng},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.01459},
eprint = {2610.01459},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.01459},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Tight Transition Time Bounds for Separable Logistic Regression at the Edge of Stability
AU - Haodong Wen
AU - Kaiyue Wen
AU - Jiaye Teng
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2610.01459
UR - https://arxiv.org/abs/2610.01459
AB - 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 η→ ∞ and conjectures a bound independent of η in arbitrary dimensions d≥ 2. In this paper, we disprove this conjecture by showing that, for every fixed sample size n≥ 2 and sufficiently small margin γ, the worst-case transition time is Θ ((logη)^min{n−2,d−2}) uniformly over d≥2. 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.
ER -