PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Haodong Wen, Kaiyue Wen, Jiaye Teng

arXiv:2610.01459v1cs.LGstat.ML

TL;DR

The paper addresses whether the Edge-of-Stability transition time remains independent of stepsize in arbitrary dimensions. It uses recursive rank reduction and matching hard instances to establish a tight worst-case bound that grows polylogarithmically with stepsize when both sample size and dimension exceed two.

  • Problem

    Prior work conjectured that the threshold transition time is bounded independently of stepsize in arbitrary dimensions, while the stepsize dependence matters for finite-horizon optimization.

    Source: §1 · pp. 1–2

  • Method

    The analysis recursively reduces the rank of projected sample vectors, bounds interval counts through multiplicative growth, and controls restarts using a cumulative coefficient budget.

    Source: §1.1 · p. 3, §4.1 · p. 7

  • Results

    Theta((log eta)^min{n-2,d-2}) is the worst-case transition-time order for sufficiently small fixed margin, uniformly over d >= 2.

    Source: §5 · p. 10

  • Takeaways & Limitations

    For n,d >= 3, choosing eta = exp(aT^(1/k)) for sufficiently small a ensures the threshold transition time is at most T/2 for sufficiently large T.

    Source: §1 · p. 2

    The analysis considers binary logistic regression datasets in dimensions d >= 2 with n >= 2 that admit a unit separator at margin gamma.

    Source: §3.1 · p. 5

Abstract

from arXiv · show

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.

1 INTRODUCTION

The paper determines how large-stepsize instability depends on sample size and dimension, disproving the conjecture that transition times remain stepsize-independent in arbitrary dimensions. Its proof combines recursive rank reduction with hard instances that realize successive logarithmic factors.

1 INTRODUCTION

  • Large constant stepsizes can accelerate stable-phase descent, but a longer oscillatory phase can leave fewer iterations for that descent within a fixed budget.Earlier work left open whether its O(η) transition bound was necessary; the d=2 result instead gave a stepsize-independent bound and motivated a dimension-free conjecture.Source: §1 · p. 1
  • Θ((log η)^min{n-2,d-2}) is the worst-case order of the exact transition time as η→∞, uniformly over d≥2 under the stated fixed-small-margin conditions.The bound is independent of η when n=2 or d=2; otherwise it can grow polylogarithmically.Source: §1 · p. 2
  • The threshold-based transition time has the same worst-case order, although the two transition-time notions may differ on an individual dataset.The worst-case dataset may depend on η.Source: §1 · p. 2
  • For n,d≥3, choosing η=exp(aT^(1/k)) ensures the threshold transition occurs by T/2 for sufficiently large T, leaving iterations for stable-phase descent.Here k=min{n−2,d−2} and a>0 is sufficiently small.Source: §1 · p. 2

1.1 TECHNICAL OVERVIEW

  • The analysis handles repeatedly changing influential samples through recursive projections that reduce the rank of projected sample vectors.Each rank reduction contributes at most one logarithmic factor; the lower-bound construction realizes all such factors.Source: §1.1 · p. 3
  • The upper bound retains a separable subset of samples at lower rank and restarts the reduction when a large update occurs or an excluded sample becomes significant again.Only O(1) restarts are needed, and each outer block has O(log η) multiplicative-growth intervals per recursive level.Source: §1.1 · p. 3
  • Hard instances let a nearly negligible sample become influential only after its margin changes through Θ(log η) repetitions, with each additional interacting sample adding a logarithmic factor.A strict loss increase at time Θ((log η)^k) ensures the construction lower-bounds the exact transition time, not merely trajectory length.Source: §1.1 · pp. 3–4

2 RELATED WORK

Earlier analyses established an O(η) transition bound generally and a stepsize-independent bound in dimension two, leaving higher dimensions unresolved. This paper gives a tight worst-case dependence for separable logistic regression and distinguishes its focus from broader EoS and separable-regression work.

Comparison with previous works on the transition to stable phase

  • Wu et al. (2024) established an O(η) transition bound and an eO(T^-2) loss rate with η=Θ(T), while Crawshaw & Liu (2026) proved stepsize independence for a threshold transition in d=2.The two results left open whether stepsize independence persisted in higher dimensions.Source: §2 · p. 4
  • The exact transition time can grow as Θ((log η)^min{n−2,d−2}) in higher-dimensional instances, while remaining uniformly bounded when n=2 or d=2.The exact transition time is the earliest time after which loss remains nonincreasing; the threshold-based notion has the same worst-case order under the theorem's assumptions.Source: §2 · p. 4

Related work

  • Unlike studies of EoS mechanisms, adaptive or stochastic training, and broader separable-regression guarantees, this paper studies when separable logistic regression enters permanent monotone loss decrease.The related work includes analyses of local stability and training dynamics, as well as convergence and implicit-bias results.Source: §2 · p. 4

3 MAIN RESULTS

For sufficiently small fixed margin, the worst-case EoS transition time has a tight polylogarithmic dependence on the stepsize, with its exponent controlled by sample size and dimension. The section also gives a matching order for the threshold transition time and derives a finite-horizon optimization guarantee.

3.1 PROBLEM SETUP

  • The setup considers bounded feature vectors with a unit separator of margin at least γ, and gradient descent on empirical logistic loss starts from w0 = 0.The dataset class allows repeated samples, and γ is a lower bound on the separator margin.Source: §3.1 · p. 5

3.2 TIGHT BOUNDS ON THE EOS TRANSITION TIME

  • Θ((log η)^min{n−2,d−2}) is the tight worst-case EoS transition-time order for sufficiently small fixed margin, uniformly over d ≥ 2.The implicit constants and the stepsize threshold depend only on n and γ, not on dimension.Source: §3.2 · p. 5
  • The worst-case time is independent of η when n = 2 or d = 2, and grows with η once both n,d ≥ 3.Each unit increase in min{n,d} permits one additional logarithmic factor; increasing only the larger parameter leaves the exponent unchanged.Source: §3.2 · p. 5

3.3 COROLLARIES

  • The threshold transition time has the same worst-case asymptotic order as the exact transition time, although the two times need not coincide on an individual dataset.The exact time marks when loss remains nonincreasing; the threshold time marks entry into a sufficient low-loss region.Source: §3.3 · p. 6
  • For fixed n,d,γ, the polylogarithmic transition bound supports loss at most ϵ within O((log(1/ϵ))^k) updates as ϵ → 0, with k = min{n−2,d−2}.The stepsize is chosen before the run as a function of horizon T and remains constant throughout optimization.Source: §3.3 · p. 6
  • When k = 0, the threshold transition time remains O_n,γ(1) for sufficiently large η.The same analysis gives F(wT) = O_γ(1/(ηT)) once T exceeds twice the uniform transition bound.Source: §3.3 · p. 6

4 PROOF SKETCH OF THEOREM 1

The proof combines a recursive upper bound based on projected lower-rank dynamics with a matching construction that creates repeated logarithmic trajectory scales. The lower-bound trajectory must also include a late loss increase and be realized by gradient descent initialized at zero.

4.1 UPPER BOUND

  • Before the threshold transition, a global coefficient-mass budget limits restarts to O(1) outer blocks, and recursive rank reduction bounds the length within each block.Within a block, projection retains separable samples of lower rank while discarded samples contribute only a small additive error.Source: §4.1 · pp. 7–8
  • Each recursive rank level partitions the projected trajectory into O(log η) intervals, yielding a polylogarithmic upper bound on the transition time.The recurrence multiplies the lower-rank process length by O(1 + log B) at each level.Source: §4.1 · p. 8

4.2 LOWER BOUND

  • The lower bound starts with two-coordinate dynamics producing a Θ(log X)-length trajectory, then adds coordinates so each level enables logarithmically many repetitions.The recursive construction yields trajectory lengths of order Θ((log B)^k), with one added logarithmic factor per level.Source: §4.2 · pp. 8–9
  • A long trajectory alone does not establish a late transition, so the construction forces a strict loss increase at t = Θ((log B)^k).For k ≥ 2, the scaled loss rises from O(1) to at least order B^1/4 within the final level-k segment.Source: §4.2 · pp. 9–10
  • Setup samples realize the auxiliary initial state after the first update from w0 = 0 while remaining negligible, preserving the late loss increase and a positive margin independent of B.The resulting dataset has bounded sample norms, and its transition time is at least order (log B)^k.Source: §4.2 · p. 10

5 CONCLUSION

The paper establishes tight worst-case transition-time bounds for constant-stepsize gradient descent on separable logistic regression. The duration is stepsize-independent in the two-dimensional or two-sample regimes, but can grow polylogarithmically in higher-dimensional settings.

5 CONCLUSION

  • For sufficiently small fixed margin, the tight worst-case transition-time order is Θ((log η)^min{n−2,d−2}).Stepsize independence holds when n = 2 or d = 2; otherwise the EoS phase can grow polylogarithmically with η.Source: §5 · p. 10
  • Each logarithmic factor corresponds to an additional level of interaction in the dynamics, with rank recursion bounding the levels and the lower-bound construction realizing them.The results characterize how sample size and data dimension govern the duration of large-stepsize instability.Source: §5 · p. 10
  • Whether analogous hierarchical mechanisms govern large-stepsize transitions beyond separable logistic regression remains open.Source: §5 · p. 10

A ILLUSTRATION OF THEORY

The simulations illustrate how transition time and loss behavior can vary under large stepsizes, while related work and preliminaries set the surrounding context.

A ILLUSTRATION OF THEORY

  • The simulations use three separable samples at n = d = 3, the smallest sample size and dimension for which the transition bound can grow with η.Figure 2 uses a symmetric pair construction, and the datasets may vary with η while n, d, and a positive margin lower bound remain fixed.Source: A ILLUSTRATION OF THEORY · pp. 16–17
  • For the symmetric n = d = 3 construction, both transition times grow approximately linearly with log η, and loss can keep increasing after correct classification as two samples alternate in driving updates.Panel (c) shows the samples’ relative update coefficients, and shading marks the stable phase.Source: Figure 2 · p. 16
  • For Figure 2, the first two samples have negative inner product and fixed pair geometry as η varies; only the third sample changes to realize the initial state.The negative inner product means an update along one sample reduces the other sample’s margin.Source: A ILLUSTRATION OF THEORY · p. 16

B ADDITIONAL RELATED WORKS

  • Related work covers acceleration from stepsize schedules or momentum, large stepsizes in related settings, and transition guarantees for other optimization problems.The cited settings include local gradient descent, regularized logistic regression, two-layer networks, and broader classes of classification losses.Source: B ADDITIONAL RELATED WORKS · p. 18

C PRELIMINARIES AND THE MONOTONE REGION

  • The appendix uses B = η/n, natural logarithms, Euclidean vector norms, and induced operator norms for matrices.It also states the sample norm bound and the convention for symmetric matrix inequalities.Source: C PRELIMINARIES AND THE MONOTONE REGION · p. 18

C.1 PROOF OF LEMMA 4

The proof establishes a forward-invariant region in which loss is nonincreasing, then states an upper-bound regime uniform over dimension and admissible datasets.

C.1 PROOF OF LEMMA 4

  • The proof applies the fundamental theorem of calculus twice to log F along a displacement and uses a Hessian bound.The resulting bound makes the loss nonincreasing whenever F(w) ≤ 2/η.Source: §C.1 · pp. 18–19
  • If F(w) ≤ 2/η, the sublevel set is forward invariant and loss remains nonincreasing; consequently, ση(D) ≤ τη(D).The threshold defining τη(D) is 1/(8η), which is below 2/η.Source: §C.1 · p. 19

D UPPER BOUND

  • For each n ≥ 2 and 0 < γ ≤ 1, the upper-bound argument supplies constants Cn,γ and ηn,γ uniformly for d ≥ 2, datasets in Dn,d(γ), and η ≥ ηn,γ.Lemma 4 is used to obtain the upper bound in Theorem 1.Source: D UPPER BOUND · p. 19

D.1 AN AUXILIARY INTERVAL ESTIMATE

This section develops an auxiliary interval-length estimate with an exponent controlled by sample count and rank, using induction on a projected process over a smaller sample set. It bounds total time by an initial segment and logarithmically many subsequent phases, with constants depending on fixed sample and margin parameters rather than rank or ambient dimension.

D.1 AN AUXILIARY INTERVAL ESTIMATE

  • For sufficiently large B, the interval bound has exponent min{m−1, r−1}, with constants uniform over sample vectors and ambient dimension.The constants depend only on m, µ, c, K, and E.Source: §D.1 · pp. 19–20
  • When the sample span has rank one, the auxiliary estimate gives a constant upper bound, uniformly in B.The proof bounds the first update by a constant and then compares later times directly to control the remaining interval.Source: §D.1 · p. 21
  • For rank at least two, the trajectory reaches separator coordinate A log B within O(log B) update indices, or the interval already has that length bound.Once the coordinate is large, maintaining coefficient mass at least c prevents the trajectory from pointing too closely along the separator.Source: §D.1 · pp. 21–22
  • Within each phase, a nonempty proper subset of samples has sufficiently negative component along a chosen orthogonal direction, and that direction’s coordinate decreases through the phase.The decrease also holds on the last update, even if the endpoint lies beyond the phase’s stopping threshold.Source: §D.1 · pp. 22–24
  • Projecting onto the chosen direction’s orthogonal complement yields an exact logistic process on fewer samples whose rank drops by at least one, enabling induction.The retained samples preserve the separator and the same B; the new process starts at zero and has nondecreasing offsets through the endpoint.Source: §D.1 · pp. 24–25
  • T ≤ C(1 + log B) + C(1 + log B)(1 + log B)^(r−2), with at most C(1 + log B) later phases, each bounded by (27).The initial part before a_t ≥ A log B has length at most C(1 + log B); the inductive step applies for r ≥ 2.Source: §D.1 · p. 26
  • The constants depend only on m, µ, c, K, and E, and are independent of rank and ambient dimension.At most m − 1 sample reductions occur along any recursive sequence, and the margin lower bound remains at least µ.Source: §D.1 · p. 26
  • This completes the precise form of Lemma 6, with its fixed offsets, initialization, coefficient threshold, and error bound specified in (3)–(6).Source: §D.1 · p. 26

D.2 THE ORIGINAL GRADIENT TRAJECTORY

This section bounds the original trajectory’s transition time by reducing data rank within recomputed blocks and summing their lengths, with an exponent controlled by the original rank. It also develops a construction using exact logistic coefficient dynamics and a uniformly controlled local inverse under the stated coordinate conditions.

D.2 THE ORIGINAL GRADIENT TRAJECTORY

  • Only a bounded number of updates have a coefficient at least B/4, and the proof uses one global coefficient-mass budget to count blocks across all intervals.Each interior block endpoint consumes at least ηγ²/8 of that mass.Source: §D.2 · pp. 29, 31
  • When r = 1, the transition occurs by the first update for sufficiently large η.The proof establishes τη ≤ 1 in the rank-one case.Source: §D.2 · p. 29
  • Recomputing a projection at each block start retains a nonempty sample set in rank r−1, allowing the auxiliary estimate to bound each block’s length by C_n,γ(1 + log B)^(r−2).The block-start projection is recomputed so the auxiliary process begins at zero; the final update is included even if it reaches a large coefficient or the transition time.Source: §D.2 · p. 32

E.1 EXACT COEFFICIENT DYNAMICS

  • The exact coefficient update is Φ_B,K(s) = s − K h_B(e^s), and the auxiliary orbits satisfy it without replacing logistic loss by exponential loss.Source: §E.1 · p. 34

E.2 A UNIFORM LOCAL INVERSE

  • For coordinates p_i in (0, δ] ∪ [R, B], Φ_B,K has an L-Lipschitz local inverse on a radius-α ball around Φ_B,K(log p), sending its center to log p.The constants δ, R, α, and L depend only on κ and H, not on how small the coordinates are.Source: §E.2 · p. 34
  • The inverse-Jacobian norm is bounded by a constant depending only on κ and H, including when either coordinate block is empty.Source: §E.2 · p. 35

E.3 ADDING ONE NEGLIGIBLE COORDINATE

The section gives a way to add one coordinate while keeping a previously constructed orbit nearly unchanged. It first builds an approximate extension and then corrects it backward to obtain an exact orbit of the enlarged system.

E.3 ADDING ONE NEGLIGIBLE COORDINATE

  • Adding one coordinate can preserve a previously constructed orbit up to an exponentially small error under the lemma’s stated conditions.The lemma assumes common positive spectral bounds and that the old orbit’s coordinates remain in the prescribed ranges.Source: §E.3 · pp. 36–38
  • The construction holds the old orbit fixed initially and solves backward for an approximate new coordinate from its prescribed terminal value.At each step it chooses the small solution; the section verifies that this solution exists.Source: §E.3 · pp. 36–37
  • Because the new coordinate exerts a small force on the old ones, the approximate sequence is corrected backward using local inverses.The correction is constructed step by step from the exact terminal point.Source: §E.3 · pp. 37–38
  • After correction, the change in the old total coefficient mass and the new coordinate’s contribution before time T are both exponentially small.The section bounds the old mass by CD and the new contribution by T times the per-step error.Source: §E.3 · p. 38

E.4 AN AUXILIARY ORBIT WITH A LATE LOSS INCREASE

This section constructs exact auxiliary orbits by backward inversion, beginning with two coordinates and recursively adding gate coordinates through repeated episodes with controlled lengths and coefficient mass. The resulting orbits exhibit a strict late loss increase at time Θ((log B)^k) for k ≥ 2, or at the final update with index Θ(log B) for k = 1, while each newly added gate is exponentially small before its final activation.

E.4 AN AUXILIARY ORBIT WITH A LATE LOSS INCREASE

  • For each fixed k ≥ 1, the construction yields an exact orbit of length T = Θ((log B)^k) and total coefficient mass O(B^1/4).It uses a positive definite matrix of size k + 1 with unit diagonal and a compact set of positive starting points.Source: §E.4 · p. 39
  • The two-coordinate inverse alternates the dominant coordinate, and reversing its backward sequence yields an exact forward orbit of length Θ(log X).The backward sequence stops when the dominant value first reaches a fixed scale.Source: §E.4 · p. 40
  • Θ(log E) updates and O(E) total coefficient mass suffice for a three-coordinate gate episode that changes depth by a fixed fraction.The final update has a gate coefficient of order E, while the gate remains exponentially small beforehand.Source: §E.4 · pp. 41, 44
  • Each new coordinate couples only to the previous gate, with couplings fixed independently of B and episode scale to preserve eigenvalue bounds and enable local inverse estimates.The induction also preserves a bounded profile with the backward steps needed later and keeps coordinates either uniformly small or uniformly large.Source: §E.4 · p. 44

Induction construction

  • At level r, the constructed episode has length Θ((log E)^r) and a final gate coefficient Θ(E), while earlier coefficients for the new gate are exponentially small.The old orbit contributes total mass O(E), and the maximum coordinate is O(E).Source: §E.4 · p. 49

Step 4. Concatenating the final level

  • For k ≥ 2, the concatenated orbit has length Θ((log B)^k); for k = 1, the pair construction has length Θ(log B).The level-k episodes are concatenated backward until the gate depth reaches a fixed scale.Source: §E.4 · p. 49

Step 5. A late strict increase

  • At least one update with j ≥ t0 has a strict loss increase, and by (113) this update occurs at time Θ((log B)^k).Source: §E.4 · p. 50

E.5 REALIZATION BY GRADIENT DESCENT FROM THE ORIGIN

The section embeds the auxiliary long orbit into gradient descent initialized at the origin while keeping the added setup samples negligible. The resulting trajectory retains a late strict loss increase, yielding the lower-bound behavior for the actual dynamics.

E.5 REALIZATION BY GRADIENT DESCENT FROM THE ORIGIN

  • An extra direction lets the first update from w0 = 0 place the auxiliary coordinates exactly at the required initial state.At the origin, every logistic coefficient equals B/2.Source: §E.5 · pp. 50, 52
  • The construction realizes the auxiliary orbit with a margin bounded independently of B, the number of copied setup samples, and ambient dimension.The actual data are formed from the auxiliary vectors and a shared additional vector, with zero coordinates appended if needed.Source: §E.5 · pp. 50–52
  • The realized trajectory has length Θ((log B)^k); when k = 1, its true gradient descent loss has a strict increase at an index of order log B.Source: §E.5 · pp. 51, 54
  • The copied setup samples remain negligible, and the auxiliary-orbit error stays below one over the orbit.The error estimate supports transferring the auxiliary orbit’s late loss increase to the true gradient descent trajectory.Source: §E.5 · pp. 52, 54

E.6 COMPLETION OF THE LOWER BOUND

The lower-bound construction covers both positive and zero logarithmic exponents. For fixed sample size, finitely many parameter choices allow the construction and its stepsize thresholds to be made uniform over dimensions.

E.6 COMPLETION OF THE LOWER BOUND

  • When k = 0, meaning n = 2 or d = 2, the proof uses a constant lower bound from a two-dimensional separated dataset and an increasing first update.The separator has margin g_n.Source: §E.6 · pp. 54–55
  • For k ≥ 1, the construction has a positive margin independent of B, the copied setup-sample count, and ambient dimension.For fixed n, only k = 0, 1, …, n − 2 can occur, so the finitely many stepsize thresholds can be maximized.Source: §E.6 · p. 55
  • After taking the maximum of finitely many stepsize thresholds, the lower-bound construction applies uniformly over every d ≥ 2.The construction for margin γ_n also supplies the lower bound for γ because D_n,d(γ_n) is contained in D_n,d(γ).Source: §E.6 · p. 55

F PROOF OF THEOREM 1

The proof combines a uniform lower construction with an upper bound from Appendix D to establish Theorem 1. Its constants and stepsize threshold do not depend on dimension.

F PROOF OF THEOREM 1

  • The lower construction and the Appendix D upper bound match in order, proving Theorem 1 uniformly over d ≥ 2.The upper bound for the threshold transition time also bounds the exact transition time because σ_η(D) ≤ τ_η(D).Source: F PROOF OF THEOREM 1 · p. 55
  • The implicit constants and the stepsize threshold depend only on n and γ, not on d.The lower construction is stated uniformly for all d ≥ 2.Source: F PROOF OF THEOREM 1 · p. 55

G.1 PROOF OF COROLLARY 2

The proof of Corollary 2 combines a pointwise comparison of the exact and threshold transition times with a matching lower bound. The Corollary 3 proof derives a decay estimate after the threshold and chooses a stepsize depending on the horizon.

G.1 PROOF OF COROLLARY 2

  • Lemma 4 gives ση(D) ≤ τη(D) for each dataset, which the proof combines with (2) to bound the transition time.Source: §G.1 · p. 55
  • Theorem 1 supplies the matching lower bound, and both constants and the common stepsize threshold are independent of d.This completes the dimension-uniform bound in Corollary 2.Source: §G.1 · p. 55

G.2 PROOF OF COROLLARY 3

  • After F(w_t) ≤ 1/(8η), the proof bounds per-example terms and uses a gradient lower bound to derive reciprocal-loss decay.It uses ℓ_i,t and q_i,t definitions, the inequality 1 − exp(−x) ≥ x/2 for 0 ≤ x ≤ 1, and sums the resulting estimate over updates.Source: §G.2 · p. 56
  • Corollary 3 uses C = 128/(15γ^2), with a, C, and T0 depending only on n and γ.For n ≥ 3, the proof chooses η = exp(aT^(1/k)) for 1 ≤ k ≤ n − 2 after setting a threshold η0.Source: §G.2 · p. 56

Related papers

Loading 2610.01459v1…