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

cs.LG stat.ML Haodong Wen, Kaiyue Wen, Jiaye Teng · Oct 1, 2026

What it does

Why it matters

It proves that the worst-case exact transition time from oscillatory loss to monotone decrease scales as $\Theta((\log \eta)^{\min\{n-2,d-2\}})$ uniformly over dimension $d \ge 2$, disproving a conjecture that stepsize independence holds...

Main concern

Community signal

0 up · 0 down

AI Review AI reviewed

Plain-language introduction

This paper studies gradient descent with a large constant stepsize on linearly separable logistic regression, a canonical model for the Edge of Stability phenomenon. It proves that the worst-case exact transition time from oscillatory loss to monotone decrease scales as $\Theta((\log \eta)^{\min\{n-2,d-2\}})$ uniformly over dimension $d \ge 2$, disproving a conjecture that stepsize independence holds beyond $d=2$. The result translates into substantially stronger finite-horizon optimization guarantees by permitting exponentially larger constant stepsizes than prior $O(\eta)$ transient bounds.

Critical review

Verdict

Bottom line

The paper makes a compelling theoretical contribution: it gives a tight, dimension-uniform characterization of the transition time and shows that stepsize independence is a low-dimensional artifact. The upper and lower bounds match exactly, and the analysis is technically sophisticated. That said, the matching lower bound requires restricting to sufficiently small margins $\gamma \le \gamma_n$, and the worst-case hard instance is allowed to depend on the stepsize $\eta$, which slightly narrows the scope of the tightness claim.

“For every integer n ≥ 2, there exists a constant γ_n ∈ (0,1] such that, for every fixed 0 < γ ≤ γ_n, sup_{D∈D_{n,d}(γ)} σ_η(D) = Θ((log η)^{min{n-2,d-2}}) as η→∞, uniformly over all integers d ≥ 2, where the implicit constants and the threshold on η depend only on n and γ, independent of dimension d.”

Wen, Wen & Teng, Theorem 1 · Section 3.2

“Both the constants and the stepsize threshold depend only on n, γ and are independent of dimension d, while the worst-case dataset may depend on η.”

Wen, Wen & Teng, Theorem 1 · Section 3.2

What holds up

The recursive rank-reduction argument for the upper bound is elegant and provides a clear mechanism for why each additional logarithmic factor arises. The lower-bound construction is particularly inventive: it builds auxiliary logistic dynamics backward and concatenates orbit segments to force repeated sample switching. As the authors note, the key obstacle was that the dominant sample can change repeatedly throughout training, and they address this by recursive projections that reduce the rank of the projected sample vectors, yielding matching upper and lower bounds.

“The key challenge in higher dimensions is that the samples contributing most strongly to the gradient can change repeatedly: a sample with a negligible current contribution can later become significant again, and this can happen repeatedly throughout the training trajectory. Our analysis handles these changes through recursive projections that reduce the rank of the projected sample vectors.”

Wen, Wen & Teng, Sec. 1.1 · Section 1.1

Main concerns

A limitation is that the lower bound only holds for margins below an $n$-dependent threshold $\gamma_n$, whereas the upper bound holds for all fixed $\gamma \le 1$. Consequently, the tight characterization is not universal across all separable datasets, but only for those with sufficiently small margin. Moreover, the uniformity in dimension $d$ is over adversarially chosen, stepsize-dependent datasets, which is a standard but important caveat for worst-case lower bounds. The paper also relies on several citations dated 2025–2026 that cannot be independently verified.

“For every integer n ≥ 2, there exists a constant γ_n ∈ (0, 1] such that, for every fixed 0 < γ ≤ γ_n”

Wen, Wen & Teng, Theorem 1 · Section 3.2

“Both the constants and the stepsize threshold depend only on n, γ and are independent of dimension d, while the worst-case dataset may depend on η.”

Wen, Wen & Teng, Theorem 1 · Section 3.2

Evidence and comparison

The theoretical claims are supported by a clean simulation in Appendix A for $n=d=3$ showing transition times growing linearly with $\log \eta$. Comparisons to prior work are fair and precise: the authors clearly distinguish their exact transition time $\sigma_\eta(D)$ from the threshold time $\tau_\eta(D)$ used by Crawshaw & Liu (2026), and prove that both notions share the same worst-case asymptotic order. They also correctly contextualize their improvement over the $O(\eta)$ bound of Wu et al. (2024), leading to a much stronger last-iterate guarantee of $F(w_T) \le \frac{C}{T}\exp(-aT^{1/k})$.

“Thus, the stepsize independence established by Crawshaw & Liu (2026) is specific to the regime d = 2 rather than a dimension-free phenomenon.”

Wen, Wen & Teng, Sec. 1 · Introduction

“F(w_T) ≤ C/T exp(-a T^{1/k})”

Wen, Wen & Teng, Corollary 3 · Section 3.3

Reproducibility

All experimental details are provided in Appendix A, including explicit Gram matrices, Newton iteration for backward map inversion, and margin verification. However, no code repository or software environment is mentioned, and the lower-bound instance construction involves a delicate backward recurrence and concatenation of orbit segments that would be error-prone to recreate by hand. Full reproducibility would benefit from an open-source release of the simulation and construction scripts. The gradient descent update and loss are standard, so with the explicit dataset formulas an independent implementation is possible but nontrivial.

“We simulate GD from w_0 = 0 with n = d = 3, the smallest sample size and dimension for which the transition bound can grow with η.”

Wen, Wen & Teng, App. A · Appendix A

“Newton iteration starts from v = c p̂_i / K_{jj} and uses the small positive solution for u.”

Wen, Wen & Teng, App. A · Appendix A

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.

Challenge the Review

Pick a starting point or write your own. Challenges run in the background, so you can keep reading while the AI investigates.

Challenges are public to read, but only signed-in members can post them. Your challenge text is stored with your account for moderation, but usernames are not shown in the public thread.

No challenges yet. Disagree with the review? Ask the AI to revisit a specific claim.