arXiv：cs.LG（机器学习，全量分类）· Haodong Wen, Kaiyue Wen, Jiaye Teng·· 14 小时前AI 评分36
线性可分逻辑回归在稳定性边缘的紧致过渡时间界
Tight Transition Time Bounds for Separable Logistic Regression at the Edge of Stability
AI 导读
该论文否证了任意维度 d≥2 下过渡时间与步长 η 无关的猜想，证明对每个固定样本量 n≥2 和足够小的间隔 γ，最坏情况过渡时间为 Θ((log η)^min{n-2,d-2})，且对 d≥2 一致成立。此前仅 d=2 时 η→∞ 有紧致 Θ(1) 界。作者通过对维度和样本量归纳控制梯度贡献最大样本的反复变化，并构造了匹配的困难实例。
正文
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 \to \infty$ and conjectures a bound independent of $\eta$ 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 $\gamma$, the worst-case transition time is $$\Theta\!\left((\log\eta)^{\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.
| Subjects: | Machine Learning (cs.LG); Machine Learning (stat.ML) |
| Cite as: | arXiv:2610.01459 [cs.LG] |
| (or arXiv:2610.01459v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2610.01459 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Jiaye Teng [view email]
[v1]
Thu, 1 Oct 2026 10:54:10 UTC (103 KB)
来源：arXiv：cs.LG（机器学习，全量分类） · arxiv.org