How fast does large stepsize gradient descent converge for logistic regression?

The paper bounds the unstable phase, not the whole run

The question is how many gradient descent steps are needed to drive the logistic loss below a target ε when the stepsize is deliberately large. The paper answers it for binary logistic regression on linearly separable data, run from initialization w₀ = 0 with a constant stepsize η.

The key object is the phase transition time τ, defined as the first step t at which L(w_t) ≤ 1/η. Before τ the loss may oscillate rather than fall monotonically; from τ onward it decreases monotonically. So the total step count splits into the length of this unstable phase plus the stable phase that follows. The paper's main theorem bounds τ, and it restates the earlier result that the loss decreases monotonically from step τ onwards.

This distinction matters because the two phases are governed by different quantities. The stable-phase rate is inherited from prior work; the new contribution is a much tighter bound on how long the oscillatory phase can last.

Why large stepsizes break the descent lemma

Classical convergence guarantees rest on the descent lemma: if the loss is β-smooth and the stepsize is below 2/β, every step decreases the loss, and rates follow by summing per-step decreases. For this logistic loss β = 1/4, so stepsizes below 8 guarantee monotone decrease.

The paper studies stepsizes far above that threshold, where the loss need not decrease monotonically. This is the regime practitioners call the edge of stability, where sharpness rises to about 2/η and training proceeds exactly where the descent lemma no longer applies. The paper's framing is that acceleration here comes from the dynamics of gradient descent itself, not from a designed stepsize schedule.

Because monotone-decrease arguments are unavailable, the proof cannot simply sum per-step progress. It has to control the oscillatory phase directly, which is what the new counting argument does.

From linear in η to polylogarithmic in η

With stepsize η = 1/ε, the paper proves that loss ε is reached within O(ln^p(1/ε)) steps, where p depends only on the margin γ and the rank r of the data. For fixed problem-dependent parameters, this improves the prior O(1/√ε) step complexity in arbitrary dimension to polylogarithmic in 1/ε.

The improvement is located in the phase transition bound. Earlier analysis bounded the unstable phase linearly in the stepsize, which caps how large a stepsize can be used within a fixed step budget and was conjectured to be improvable. This paper shows the unstable phase ends within O((ln η)^p) steps, provided the stepsize exceeds a threshold η₀.

A separate, elementary case is stated for large margin: when γ ≥ 1/√2 and η ≥ 64n², a single step suffices, so τ ≤ 1. The polylogarithmic bound applies to the regime 0 < γ < 1/√2.

Nested intervals turn oscillation into a counting problem

The proof does not average a potential along the trajectory, and it does not track the oscillation of iterates across the max-margin direction, which is a one-dimensional motion only in the plane. Instead it counts steps.

Steps at which some signed margin is negative are shown to be few. The remaining steps are organized into recursively nested intervals, each carrying reference directions that constrain every update inside it. An interval carrying j reference directions splits into a short prefix and at most R children, where R = 1 + ⌈4Λ/θ⌉ and Λ = ln η; each child inherits the j directions and gains one new one.

Two quantities then control the structure. A geometric capacity lemma shows that at most ν + 2 vectors in the convex hull of the signed examples can have pairwise inner products at most θ, which bounds the nesting depth by the margin and the rank. A counting argument bounds how many intervals sit at each depth: because sibling intervals start at coefficients whose logarithms are more than θ/4 apart, counting them jointly yields a factorial saving, giving D_j(I) ≤ 2(6Λ/θ)^j / j!.

Where the exponent p comes from

The depth ν is defined as max{0, min{r, ⌊γ⁻² + (γ⁻² − 1)/(h − 1)⌋ − 2}}, where h = ⌈ln(16γ⁻²)⌉ and r is the rank of the data. The exponent p equals ν plus a correction term ν ln(18hγ⁻²/ν) / ln(max{2, ν}) when ν ≥ 1, and equals 0 when ν = 0.

The paper explains the trade-off explicitly. The raw bound τ ≤ C(6hγ⁻² ln η)^ν / ν! has the smaller degree ν, but its coefficient can be superpolynomial in 1/γ. The exponent p absorbs that coefficient so the prefactor C stays polynomial in n and 1/γ. In asymptotic terms, C = O(γ⁻⁴ ln(γ⁻²)[n + ln²(γ⁻²)]), the threshold η₀ is Õ(γ⁻² + ln n), and p = O(min{r, γ⁻²} ln(γ⁻²)).

The threshold η₀ is chosen so that η ≥ 4, Λ > 10, 4Λ ≤ ηθ, and CΛ^p is below the finite horizon used in the proof. Notably, the argument never requires Λ ≥ ν, which would have meant an exponential stepsize requirement.

What the result does and does not cover

The guarantee is stated under bounded and separable data: every ‖x_i‖ ≤ 1, labels y_i ∈ {±1}, and a unit vector w* with ⟨y_i x_i, w*⟩ ≥ γ for all i. The rank r is the dimension of the span of the signed examples, at most min{n, d}.

The result is an upper bound on the phase transition time, not a lower bound. The authors state that tightening the constants in their bounds and establishing new lower bounds are left to future work. The bound also concerns the specific setting of constant stepsize, logistic regression, and linearly separable data; the paper contrasts this with stepsize schedules designed for smooth convex objectives whose minimizers are attained.

One further scope note is that the analysis assumes the stepsize is at least η₀, a threshold that grows with 1/γ and with ln n. The polylogarithmic phase transition is a statement about that regime, not about arbitrary stepsizes.

The comparison that matters is against the linear bound

The decision-relevant comparison in this paper is between two bounds on the same quantity, the phase transition time τ. Prior analysis bounded it linearly in the stepsize, which is what capped the usable stepsize under a fixed step budget. This paper bounds it by C(ln η)^p, so the unstable phase grows only polylogarithmically in η.

That change is what makes the aggressive choice η = 1/ε compatible with a polylogarithmic step complexity in 1/ε. The practical reading is conditional: the improvement is largest when the margin γ and rank r keep p small, since p = O(min{r, γ⁻²} ln(γ⁻²)) and the prefactor C scales like γ⁻⁴ ln(γ⁻²) times n plus logarithmic terms. When the margin is large enough that γ ≥ 1/√2 and η ≥ 64n², the unstable phase collapses to at most one step.

The paper also positions itself against the two-dimensional result, which proved the unstable phase ends within a number of steps independent of η but relied on tracking a one-dimensional motion available only in the plane. The contribution here is extending comparable control to arbitrary dimension through the interval hierarchy and the margin-and-rank depth bound.

Sources used in this answer