acceptodds
Under review as a conference paper at ICLR 2027

Improved Convergence of Large Stepsize Gradient Descent for Logistic Regression

Abstract

We study gradient descent (GD) with a large constant stepsize for logistic regression on linearly separable data. Existing analysis shows an accelerated rate of to reach loss with an aggressive stepsize, although the loss may initially oscillate. Tighter control of the oscillatory dynamics has been available only for two-dimensional data. We prove a substantially faster rate in arbitrary dimension: GD with a large stepsize reaches loss within steps, where depends only on the margin and the rank of the data. Our proof improves the bound on the transition time of GD from the oscillatory to the stable phase, after which the loss decreases monotonically. We split the oscillatory phase into recursively nested intervals. The margin and the rank bound the nesting depth, and a counting argument bounds the number of intervals at each depth, together yielding the polylogarithmic step complexity.

Primary area:
optimization
Keywords:
gradient descent, large stepsize, logistic regression

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_Z5E6OpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studied how gradient descent converges when minimizing logistic loss and a large stepsize is used. The existing papers have shown that after O~(1/ϵ)\tilde{O} (1 / \sqrt{\epsilon}) iterations, L(wt)≤ϵL(w^t) \leq \epsilon. This paper improved these results, showing that after O(log⁡p(1/ϵ))O(\log^p (1 / \epsilon)) iterations, L(wt)≤ϵL(w^t) \leq \epsilon is achieved. Tighter results have been shown in Crawshaw & Liu 2026, but they hold only in the two-dimensional case. The results shown in this paper hold for arbitrary dimension.

Critical strengths
  • This paper improves the results shown in Wu et al., 2024, showing that after O(log⁡p(1/ϵ))O(\log^p (1 / \epsilon)) iterations, L(wt)≤ϵL(w^t) \leq \epsilon is achieved.
  • Furthermore, Wu et. al., 2024 showed that L(wT)≤O~(1/T2)L (w^T) \leq \tilde{O} (1 / T^2), while in Corollary 2.3, this paper shows that L(wT)≤O(exp⁡(T)1p)L(w^T) \leq O(\exp (T)^\frac{1}{p}), which is much faster than the results of Wu. et. al., 2024.
Critical weaknesses
  • Several existing papers have already established faster convergence rates for gradient descent on separable logistic regression than We et. al., 2024 [1,2]. In particular, Kale et al. 2026 proved an exponential convergence rate, but this paper is not cited.
  • The result of Wu et al. 2024, showing that gradient descent converges for logistic loss even with large stepsizes, is highly interesting. While extending and improving this line of analysis is mathematically appealing, the overall impact appears limited. Since logistic regression is considerably different from modern neural network models, it remains unclear whether improved theoretical guarantees for logistic regression lead to meaningful insights for more practically relevant learning problems.
  • While Crawshaw & Liu 2026 considered two-dimensional cases, they provided a better bound than this paper, as shown in Table 1. Is it possible to remove log⁡p(1/ϵ)\log^p (1 / \epsilon) as in Crawshaw & Liu 2026? It would be also helpfull to numerically demonstrate that this logarithmic overhead is inevitable.

Reference

[1] Kale et al., Exponential Convergence of (Stochastic) Gradient Descent for Separable Logistic Regression, arXiv 2026.

[2] Zhang et al., Minimax Optimal Convergence of Gradient Descent in Logistic Regression via Large and Adaptive Stepsizes, JMLR 2026.

Questions for authors

See the weakness section.

4 comments

Thank you for your constructive review and helpful feedback. We carefully address your concerns and questions below.

W1. Comparison with [1, 2].

Thank you for pointing out the missing citation to [1], we have added it. [2] is already discussed in our introduction and related work (Sections 1 and 1.1), where we state their 1/γ21/\gamma^2 step complexity and its minimax optimality.

These works obtain faster rates using time-varying stepsizes:

  • [1, Theorem 3.3] use an increasing, margin-dependent stepsize schedule that maintains monotone loss decrease, and give O(ln⁡3(1/ϵ))O(\ln^3(1/\epsilon)) complexity for fixed margin.
  • [2, Theorem 2] adapt the stepsize to the current loss and obtain 1/γ21/\gamma^2 step complexity for an averaged iterate.

Our work focuses on the constant stepsize setup and we do not claim to improve on adaptive or scheduled stepsizes. Our contribution is that with a large constant stepsize, we improve the step complexity from polynomial O~(1/ϵ)\tilde{O}(1/\sqrt{\epsilon}) to polylogarithmic O(ln⁡p(1/ϵ))O(\ln^{p}(1/\epsilon)) in any dimension, for fixed nn, γ\gamma and rank.

W2. Impact beyond logistic regression.

We agree that logistic regression is different from modern deep neural networks. There are several reasons why we think the result matters nonetheless.

  • Separable logistic regression is at present the model in which training and dynamics at the edge of stability can be analyzed exactly, which is why [1, 2, 3, 5] all work in it. You find the result of [5] highly interesting, and ours settles the main question that result left open, in the same model and under the same assumptions.
  • The two-phase analysis of [5] has been transferred and extended to two-layer networks [6] and regularized logistic regression [7], all cited in Section 1.1.

We also developed an extension to regularized logistic regression during rebuttal, see details in response to Reviewer EJJj Q1. For Fλ(w)=L(w)+λ∣w∣2/2F_\lambda(\mathbf w)=L(\mathbf w)+\lambda\\|\mathbf w\\|^2/2, fix n,γ,rn,\gamma,r and let ν\nu be the hierarchy exponent in our analysis. Set S=ln⁡(1/λ)S=\ln(1/\lambda) and q=max⁡ν,1q=\max\\{\nu,1\\}. For sufficiently small λ>0\lambda>0, with the constant stepsize η=1/(AλSq)\eta=1/(A\lambda S^q) for a suitable A=A(n,γ,r)>0A=A(n,\gamma,r)>0, GD from zero initialization reaches a stable phase within O(Sν)O(S^\nu) steps and achieves regularized optimality gap ϵ∈(0,1]\epsilon\in(0,1] within O(Sq[S+ln⁡(1/ϵ)])O(S^q[S+\ln(1/\epsilon)]) total steps, where the hidden constants depend only on n,γ,rn,\gamma,r. This demonstrates that the techniques extend to a strongly convex objective with a finite minimizer, and extensions to neural networks require further analysis.

W3. Can the logarithmic factor be removed?

Rank at most two. Then ν=p=0\nu=p=0 and Theorem 2.2 gives τ≤C\tau\leq C for all sufficiently large η\eta. Thus the complexity is independent of sufficiently small ϵ\epsilon, as in [3] for d=2d=2, with a weaker dependence on nn and γ\gamma (see our limitations).

Rank at least three. In higher rank, some logarithmic dependence is necessary for a bound uniform over the data class. The concurrent work of [4], establishes a worst-case phase transition lower bound Ω((ln⁡η)min⁡n,d−2)\Omega((\ln\eta)^{\min\\{n,d\\}-2}) for fixed n,d≥2n,d\ge2 and sufficiently small fixed margin. Since reaching L≤1/ηL\le1/\eta puts GD in the stable phase and guarantees monotonicity afterwards, the same lower bound holds for our τ\tau. With η=1/ϵ\eta=1/\epsilon, it gives a corresponding Ω((ln⁡(1/ϵ))min⁡n,d−2)\Omega((\ln(1/\epsilon))^{\min\\{n,d\\}-2}) lower bound on the worst-case number of steps that GD with this stepsize needs to reach loss ϵ\epsilon.

[1] Kale, Sacchit, et al. "Exponential Convergence of (Stochastic) Gradient Descent for Separable Logistic Regression." arXiv preprint arXiv:2602.18946 (2026).

[2] Zhang, Ruiqi, et al. "Minimax Optimal Convergence of Gradient Descent in Logistic Regression via Large and Adaptive Stepsizes." Journal of Machine Learning Research 27.124 (2026): 1-31.

[3] Michael Crawshaw, and Mingrui Liu. "Tight bounds for logistic regression with large stepsize gradient descent in low dimension." arXiv preprint arXiv:2602.12471 (2026).

[4] Haodong Wen, Kaiyue Wen, and Jiaye Teng. "Tight Transition Time Bounds for Separable Logistic Regression at the Edge of Stability." arXiv preprint arXiv:2610.01459 (2026).

[5] Wu, Jingfeng, et al. "Large stepsize gradient descent for logistic loss: Non-monotonicity of the loss improves optimization efficiency." The Thirty Seventh Annual Conference on Learning Theory. PMLR, 2024.

[6] Cai, Yuhang, et al. "Large stepsize gradient descent for non-homogeneous two-layer networks: Margin improvement and fast optimization." Advances in Neural Information Processing Systems 37 (2024): 71306-71351.

[7] Jingfeng Wu, Pierre Marion, and Peter Bartlett. "Large stepsizes accelerate gradient descent for regularized logistic regression." Advances in Neural Information Processing Systems 38 (2026): 104485-104525.

Dear Reviewer Z5E6,

Thank you for your constructive review and helpful feedback. As the discussion period nears its end, we would like to know whether our rebuttal has addressed your concerns. Please let us know if you have any remaining questions. We would be happy to discuss them further. Thank you again for your time and consideration.

We thank the authors for the rebuttal. I understood that two prior papers I mentioned considered an adaptive stepsize, while this paper considered a constant stepsize. For the logarithmic factor, it may be very helpful to cite [4] and present this discussion in the camera-ready version. Most of my concerns have been addressed. I would like to keep my positive score.

Thank you very much for the discussion. We are glad that our rebuttal has addressed your concerns, and we greatly appreciate your insightful review and constructive feedback, which helped us significantly improve our manuscript.

We will follow your suggestion and discuss the concurrent work [4] in the final version of our paper. Thank you again for your time and thoughtful comments.

Reviewer_EJJjOpenReview ↗
Rating
3(+2)
Confidence
3
Informativeness
3(+2)
Presentation
2
Soundness
3
Read review
Paper summary

This paper improves the result about large-stepsize SGD in logistic regression. The duration of the EoS phase is shorted from O~(1/ϵ)\tilde O(1/\sqrt{\epsilon}) to O((log⁡ϵ−1)p)O((\log\epsilon^{-1})^p).

Critical strengths
  1. The paper is technically strong: it establishes an improved bound for large-stepsize GD in logistic regression, especially the EoS phase.
Critical weaknesses
  1. I feel that the contribution of the paper is mostly technical, and the paper is a bit lacking in new insights. The insight of [1] is that large stepsize helps GD to converge faster in the stable phase. Although there is an EoS phase, the duration of this phase is controllable. This paper is mainly about the improved bound of the EoS phase, which provides limited new insights compared with [1].
  2. The way that the theoretical results are presented does not really help with understanding. It would be improved if the authors discuss why the proof in [1] is loose, and how the technical lemmas close the gap.
  3. Although the proposed bound has better dependence on ϵ\epsilon, the dependence on the margin γ\gamma is γ−4\gamma^{-4}, compared with γ−2\gamma^{-2} in [1]. A discussion about the tradeoff is expected.

[1] Wu et al. Large Stepsize Gradient Descent for Logistic Loss: Non-Monotonicity of the Loss Improves Optimization Efficiency. 2024.

Questions for authors
  1. Can the regularized logistic regression be analyzed with the proposed techniques?
  2. Can the authors give any intuitions about the appearance of the rank rr in CC?
10 comments

Thank you for your constructive review and helpful feedback. We carefully address your concerns and questions below.

W1. Main insight.

Thank you for recognizing the technical contribution of our improved EoS phase bound. Our main insight is that taking much larger steps need not require a proportionally longer wait for stable convergence. [1] established the benefit of large stepsizes by balancing the length of the EoS and the stable phases, while we show that the phase transition time can be bounded polylogarithmically in stepsize. This allows a more aggressive constant stepsize and improves the step complexity from polynomial to polylogarithmic.

W2. Why the previous proof is loose and how our lemmas close the gap.

[1] compare cumulative progress along a separating direction w∗\mathbf w_* with a bound on the iterate norm. For η≥n\eta\ge n, every step before the loss reaches 1/η1/\eta advances by at least γ/2\gamma/2 in that direction, while their norm bound has a term η/γ\eta/\gamma and grows only logarithmically with steps. Comparing these estimates gives an O(ηγ−2)O(\eta\gamma^{-2}) phase transition for fixed n,γn,\gamma and sufficiently large η\eta. This argument uses only the length of the updates but not their directions.

Our roadmap is to count negative-margin steps separately, and partition the remaining steps into intervals according to changes in average update direction. Writing wt+1−wt=μtvt\mathbf w_{t+1}-\mathbf w_t=\mu_t\mathbf v_t, with vt\mathbf v_t a convex average of signed examples, each lemma has a specific role:

  • Lemma 3.1: On the proof's finite horizon, ∑tμt≤2ηγ−2\sum_t\mu_t\le2\eta\gamma^{-2} implies fewer than 4nγ−24n\gamma^{-2} negative-margin steps. On the remaining steps before phase transition, μt>1/2\mu_t>1/2 and ⟨wt,vt⟩<ln⁡η\langle\mathbf w_t,\mathbf v_t\rangle<\ln\eta provide the local constraints used to improve the linear denpendence on η\eta.
  • Lemma 3.2: Reference directions organize these steps into nested intervals. The root count is independent of η\eta, and child intervals start at geometrically separated cumulative coefficients, allowing only O(ln⁡η)O(\ln\eta) children per parent.
  • Lemma 3.3: Rank and margin bound the number of weakly aligned reference directions, limiting refinement to ν\nu levels.
  • Lemma 3.4: At maximum depth, update directions must align. Between consecutive steps within a terminal interval, 1/(ηL)1/(\eta L) increases by at least θ/4\theta/4, where θ=γ2/h\theta=\gamma^2/h. Thus each terminal interval has at most ⌈4/θ⌉\lceil4/\theta\rceil steps.
  • Lemma 3.5: Counting argument gives a factorial saving. Combining this with the root and interval-length bounds yields τ≤C(6hγ−2ln⁡η)ν/ν!\tau\le C(6h\gamma^{-2}\ln\eta)^\nu/\nu!.

We will add this roadmap to Section 3.

W3. Accuracy-margin tradeoff.

We would like to emphasize that our improvement focuses on ϵ\epsilon-dependence for fixed n,γn,\gamma, and we do not claim that our dependence on n,γn,\gamma is optimal. With η=1/ϵ\eta=1/\epsilon and ϵ≤ϵ0\epsilon\le\epsilon_0, our bound is Cln⁡p(1/ϵ)C\ln^p(1/\epsilon), and compared to [1], $ \frac{C\ln^p(1/\epsilon)}{\gamma^{-2}\epsilon^{-1/2}} =C\gamma^2\sqrt\epsilon\ln^p(1/\epsilon) \rightarrow0 $ as ϵ→0\epsilon\to0.

The tradeoff is a larger constant factor, including 1/γ41/\gamma^{4} and nn dependence, and a margin γ\gamma-dependent exponent. When rank does not limit the depth, p∼1/γ2p\sim1/\gamma^{2} as γ→0\gamma\to0 (Proposition A.2). Therefore a small margin delays the improvement to very high accuracy, and our guarantee is not uniformly better over all margins: for fixed ϵ\epsilon it is worse than theirs once γ\gamma is small enough and varies with ϵ\epsilon (e.g., γ=o(ϵ)\gamma=o(\epsilon)), since CC and pp grow as γ→0\gamma\to0 while [1] grows only like 1/γ21/\gamma^{2}. Our statement treats nn and γ\gamma as fixed throughout.

[1] Wu, Jingfeng, et al. "Large stepsize gradient descent for logistic loss: Non-monotonicity of the loss improves optimization efficiency." The Thirty Seventh Annual Conference on Learning Theory. PMLR, 2024.

Q1. Extension to regularized logistic regression.

We extended the analysis to Fλ(w)=L(w)+λ∣w∣2/2F_\lambda(\mathbf w)=L(\mathbf w)+\lambda\\|\mathbf w\\|^2/2, where LL is the empirical logistic loss and λ>0\lambda>0. For bounded, separable data, fix the sample size n≥2n\ge2, margin γ\gamma, and rank rr. Let ν\nu be the hierarchy exponent in our analysis, S=ln⁡(1/λ)S=\ln(1/\lambda), and q=max⁡ν,1q=\max\\{\nu,1\\}. For sufficiently small λ\lambda and a sufficiently large constant A=A(n,γ,r)A=A(n,\gamma,r), GD from zero with constant stepsize η=1/(AλSq)\eta=1/(A\lambda S^q) reaches a stable phase within O(Sν)O(S^\nu) steps, where the hidden constants depend on the geometry. Thereafter, FλF_\lambda decreases monotonically. For 0<ϵ≤10<\epsilon\le1, it achieves Fλ−min⁡Fλ≤ϵF_\lambda-\min F_\lambda\le\epsilon within $ O\left(S^q[S+\ln(1/\epsilon)]\right) $ steps.

Regularization shrinks the iterate toward zero and can increase the logistic loss. We handle the proof in two stages.

  1. Reach small logistic loss. Put a=1−ηλ>0a=1-\eta\lambda>0 and ut=a−twt\mathbf u_t=a^{-t}\mathbf w_t. Then ut+1−ut=−ηa−(t+1)∇L(wt)\mathbf u_{t+1}-\mathbf u_t=-\eta a^{-(t+1)}\nabla L(\mathbf w_t) is again a positive combination of the signed data yixiy_i\mathbf x_i. Over the O(Sν)O(S^\nu) proof horizon, accumulated shrinkage is O(A−1Sν−q)O(A^{-1}S^{\nu-q}), while ηλln⁡η=O(A−1S1−q)\eta\lambda\ln\eta=O(A^{-1}S^{1-q}). Our choice of qq makes both uniformly small for large AA, controlling the rescaling and the extra shrinkage in terminal intervals. With adjusted coefficient and loss estimates, the rank-margin depth and interval count still lead to L≤κ/ηL\le\kappa/\eta, where κ=1/(2e2)\kappa=1/(2e^2).

  2. Convergence. Consider the actual update w+=aw−η∇L(w)\mathbf w^+=a\mathbf w-\eta\nabla L(\mathbf w). In the boundary κ/(2η)≤L(w)≤κ/η\kappa/(2\eta)\le L(\mathbf w)\le\kappa/\eta, controlling both shrinkage and the gradient change between w\mathbf w and awa\mathbf w gives, for our parameter choice,

    \le 2\eta\lambda\ln(4\eta/\kappa)L(\mathbf w) -\frac{\eta\gamma^2}{8}L(\mathbf w)^2 \le0.$$ Thus descent offsets shrinkage near the boundary. Deeper inside, a direct bound on the full update prevents escape. Convexity then keeps each update segment in the same region, where $\\|\nabla^2F_\lambda\\|\le\kappa/\eta+\lambda<1/\eta$. Let $s$ be the entry time and $\Delta_t=F_\lambda(\mathbf w_t)-\min F_\lambda$. Strong convexity gives contraction, and we have \$ \Delta_{s+k}\le(1-\eta\lambda)^k\Delta_s \$ and \$ \Delta_s=O(1/\lambda). \$ Since $(\eta\lambda)^{-1}=AS^q$, these bounds yield the stated complexity, including the additional $S$ term.

Q2. The rank rr dependence.

The constant CC in Eq. (5) is independent of the rank rr, it depends on nn and γ\gamma only. The rank rr enters through ν\nu, pp, and η0\eta_0.

If your question concerns the intuition for the appearance of rank rr, the key insight can be found in the proof of Lemma 3.3, which shows that the weakly aligned reference directions on a hierarchy branch must be linearly independent, so at most rr can occur. This explains why the data rank rr limits the depth. When r≤2r\le2, ν=p=0\nu=p=0.

Many thanks for the rebuttal. I think the authors have made several good points in the rebuttal, but the improvements need to be reflected in a revision of the paper. The authors are expected and allowed to make revisions but they have not done so, and I feel reluctant to increase my rating.

W1. The main insight that larger LR does not necessarily cause longer instability phase is good, but I feel this effect should be justified by experiments. Reviewer w6Bb has raised a similar question in Weakness 4, but the authors do not seem to address this in the rebuttal.

W2. The revision should be applied to the manuscript.

Reviewer_w6BbOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies GD with large constant stepsizes for logistic regression on linearly separable data. Prior work established a convergence complexity of O~(1/ϵ)\widetilde O(1/\sqrt{\epsilon}) in arbitrary dimensions, while stronger results concerning the initial oscillatory phase were restricted to two dimensions.

The authors prove that, with stepsize η=1/ϵ\eta=1/\epsilon, gradient descent reaches loss ϵ\epsilon within O(log⁡p(1/ϵ))O(\log^p(1/\epsilon)) iterations, where pp depends only on the margin and data rank. The central contribution is a polylogarithmic bound on the transition time from the potentially oscillatory phase to the stable phase. The proof introduces a recursive hierarchy of intervals, uses geometric constraints on update directions to bound its depth, and applies a counting argument with factorial savings to control the number of intervals.

Critical strengths
  • The improvement from O~(1/ϵ)\widetilde O(1/\sqrt{\epsilon}) to O(log⁡p(1/ϵ))O(\log^p(1/\epsilon)) represents a meaningful asymptotic advance over prior arbitrary-dimensional guarantees. Indeed extending improved convergence analysis beyond the two-dimensional setting addresses an open question in large-stepsize optimization.

  • The recursive interval decomposition, geometric capacity argument, and factorial improvement in interval counting constitute the main technical contribution and seem to be a novel. It is notable these techniques avoid directly tracking oscillatory trajectories and may prove useful in analyzing other optimization problems with nonmonotonic dynamics.

Critical weaknesses
  • Although the dependence on the target accuracy is polylog, the exponent pp can be large when the margin is small or the data rank is sufficiently high. The prefactor CC and minimum stepsize threshold η0\eta_0 further complicate the interpretation. It is unclear whether the new complexity guarantee improves existing bounds at practically relevant target accuracies, rather than only asymptotically.

  • The paper establishes an improved upper bound but provides no corresponding lower bound in dimensions greater than two. Consequently, it remains unclear whether the polylogarithmic dependence on the stepsize is intrinsic to the dynamics or an artifact of the analysis.

  • Regarding presentation, it would significantly help with readability if a more high level discussion of the significance and purpose of relevant lemmas were provided and proofs moved to the appendix, particularly in the Analysis section because it is currently extremely dense.

  • Additionally, the main ideas of the paper could benefit heavily from empirical results on toy experiments, such as on mnist, cifar, etc. The lack of numerical experiments makes it difficult to assess whether the predicted dependence on the margin, rank, and stepsize reflects observed behavior.

Questions for authors
  • Could the authors provide representative numerical values of pp, CC, and η0\eta_0 for moderate margins and data ranks? In particular, for what ranges of ϵ\epsilon does the new theoretical bound become stronger than the previous bound of Wu et al. (2024)? This would significantly help clarify the quantitative significance of the improvements

  • Is there an example of linearly separable data with rank at least three for which the transition time provably or empirically increases with the stepsize? Such an example would help distinguish whether the dependence on log⁡η\log\eta reflects an intrinsic feature of the higher dimensional optimization dynamics or looseness in the upper bound.

7 comments

Thank you for your constructive review and helpful feedback. We carefully address your concerns and questions below.

W1/Q1. Values of pp, CC, η0\eta_0, and when the bound beats [1].

We emphasize that our main goal is to improve the ϵ\epsilon-dependence for fixed n,γn,\gamma. For these fixed parameters, $ C\ln^p(1/\epsilon)=o(\epsilon^{-1/2}) $ as ϵ→0\epsilon\to0. Thus our guarantee eventually improves over the previous polynomial dependence [1]. This does not necessarily imply a smaller bound at every finite or large accuracy level, since the constant factors and exponents also count.

Our proof also provides the sharper bound $ C_{\mathrm{sharp}}(\epsilon) =\frac{C}{\nu!} \bigl(6h\gamma^{-2}\ln(1/\epsilon)\bigr)^\nu $ for ϵ≤1/η0\epsilon\le1/\eta_0 at stepsize η=1/ϵ\eta=1/\epsilon (Eq. (27), Proposition B.13), where ν\nu bounds the hierarchy depth. The main theorem absorbs the geometry-dependent coefficient into additional logarithmic powers, giving Cmain(ϵ)=Cln⁡p(1/ϵ)C_{\mathrm{main}}(\epsilon)=C\ln^p(1/\epsilon) with a polynomial prefactor. Retaining that coefficient can sharpen the numerical comparison.

For comparison, we use guarantee established in [1, Corollary 2], where the smallest admissible integer TT satisfies

\qquad T\ge\frac{120\max\\{e,n\\}}{\gamma^2},$$ with their stepsize $\eta=\gamma^2T/120$. The following table uses $n=100$ and our choice of $h=\lceil\ln(16\gamma^{-2})\rceil$. Its last two columns give conservative accuracy cutoffs below which our corresponding sufficient iteration bound is smaller than the above comparator, with both results' applicability conditions satisfied. | $(\gamma,r)$ | $(\nu,p)$ | $C$, approximately | $\eta_0$ | Main bound improves for $\epsilon\le$ | Sharper bound improves for $\epsilon\le$ | |---|---|---:|---:|---:|---:| | $(0.5,2)$ | $(0,0)$ | $7.29\times10^5$ | $63{,}505$ | $10^{-6}$ | $10^{-6}$ | | $(0.5,3)$ | $(1,10)$ | $7.29\times10^5$ | $71{,}896$ | $10^{-44}$ | $10^{-12}$ | | $(0.1,10)$ | $(8,37)$ | $9.47\times10^8$ | $918{,}649$ | $10^{-204}$ | $10^{-94}$ | The table makes the tradeoff explicit that our constants can postpone the improvement to very high accuracy, particularly for small margins and large ranks. Our contribution is that with a large constant stepsize, we improve the step complexity from polynomial $\tilde{O}(1/\sqrt{\epsilon})$ to polylogarithmic $O(\ln^{p}(1/\epsilon))$ in any dimension, for fixed $n$, $\gamma$ and rank $r$. **W2/Q2. Is logarithmic dependence intrinsic?** Yes, some logarithmic dependence is necessary for a bound uniform over higher rank (rank at least three) datasets with sufficiently small fixed margin. The concurrent work of [2], establishes a worst-case phase transition lower bound $\Omega((\ln\eta)^{\min\\{n,d\\}-2})$ for fixed $n,d\ge2$ and sufficiently small fixed margin. Since reaching $L\le1/\eta$ puts GD in the stable phase and guarantees monotonicity afterwards, the same lower bound holds for our $\tau$. With $\eta=1/\epsilon$, it gives a corresponding $\Omega((\ln(1/\epsilon))^{\min\\{n,d\\}-2})$ lower bound on the worst-case number of steps that GD with this stepsize needs to reach loss $\epsilon$. In particular, their construction with $n=d=3$ gives a rank-three family with a positive margin and phase transition time $\Omega(\ln\eta)$. The hard datasets may vary with $\eta$. This is a uniform worst-case statement, not a claim on a fixed dataset. [1] Wu, Jingfeng, et al. "Large stepsize gradient descent for logistic loss: Non-monotonicity of the loss improves optimization efficiency." The Thirty Seventh Annual Conference on Learning Theory. PMLR, 2024. [2] Haodong Wen, Kaiyue Wen, and Jiaye Teng. "Tight Transition Time Bounds for Separable Logistic Regression at the Edge of Stability." arXiv preprint arXiv:2610.01459 (2026).

W3. Presentation of the analysis.

Thank you for this suggestion. We have clarified the existing overview immediately before Section 3.1 by adding explicit lemma references and explaining why the gradient potential argument of [1] yields a bound linear in η\eta. The revised overview reads:

Wu et al. (2024) control cumulative progress along a separating direction through a global bound on the iterate norm. For large η\eta, each step before the loss reaches 1/η1/\eta contributes at least γ/2\gamma/2 in that direction, while their norm bound grows linearly in η/γ\eta/\gamma and only logarithmically in the iteration count. Comparing the accumulated per-step progress with this norm bound yields an O(η/γ2)O(\eta/\gamma^2) transition bound for fixed n,γn,\gamma and sufficiently large η\eta. Rather than averaging gradient potential along the trajectory, our analysis counts steps using update geometry. Steps at which some signed margin is negative are few (Lemma 3.1). Apart from the initial step, the remaining steps are organized into nested intervals (Lemma 3.2; see Figure 1 in Appendix B.2), each carrying reference directions that constrain every update in it. The margin and the rank bound the depth of this hierarchy (Lemma 3.3). At maximum depth, alignment bounds each terminal interval's length independently of η\eta (Lemma 3.4). The cumulative update coefficients at the starts of sibling intervals are separated on a logarithmic scale (Lemma 3.2), which lets us count the intervals at each depth with a factorial saving (Lemma 3.5). Adding up the lengths of the intervals proves the bound (Section 3.4).

We also plan to shorten the refinement and counting proofs in the main text, retaining their full appendix proofs, and move Figure 1 from Appendix B.2 to Section 3.2 beside the hierarchy construction. We will finalize these layout changes in the revised manuscript subject to the page limit.

[1] Wu, Jingfeng, et al. "Large stepsize gradient descent for logistic loss: Non-monotonicity of the loss improves optimization efficiency." The Thirty Seventh Annual Conference on Learning Theory. PMLR, 2024.

W4. Experiments on MNIST

The experiment you ask for is the one that motivated this paper. [1, figure 1] ran GD on MNIST images of 0 and 8 and conjectured that their transition bound can be improved. [2, Figure 1(a)] observed on 256 MNIST images with stepsizes 16 to 512 that the transition time does not increase with the stepsize, and conjectured a stepsize-independent bound in every dimension, which by the lower bound of [3] cannot hold uniformly over datasets. We ran the experiments and added the results to the revised paper as Appendix C (new text in blue), with Figure 2 and Table 2.

Setup. We consider the eight pairs of digits in the table below. For each pair we draw three subsets of the MNIST training set uniformly at random, each with 128 images per digit, so that n=256n=256, 24 datasets in all. The features xi\mathbf x_i are the pixel intensities of an image together with a constant coordinate, rescaled by a common factor so that ∣xi∣≤1\\|\mathbf x_i\\|\le1, and the labels yi∈{±1}y_i\in\{\pm1\} indicate the digit. Every subset is linearly separable with rank r=256r=256. We run GD on the logistic loss from w0=0\mathbf w_0=\mathbf 0 with a constant stepsize η\eta. For a target loss ϵ\epsilon we compare η=1/ϵ\eta=1/\epsilon as in Corollary 2.3, η=ϵ−1/2\eta=\epsilon^{-1/2}, which is the choice η=Θ(1/ϵ)\eta=\Theta(1/\sqrt\epsilon) of Wu et al. (2024) with the constant set to one, and η=4\eta=4, for which the loss decreases monotonically since η<8\eta<8.

Loss (Figure 2(a,b)). Large stepsizes raise the loss sharply in the first steps (up to 3.7⋅1043.7\cdot10^4 at η=106\eta=10^6 on 4 vs 9) and still reach a small loss faster. On 4 vs 9 the loss is below 1/η1/\eta after 676, 144, 71 and 45 steps at η=102,103,104,106\eta=10^2,10^3,10^4,10^6. It does not increase after τ\tau, as Theorem 2.2(ii) states.

Phase transition time (Table 2, Figure 2(c)). Medians over the three subsets of each pair.

pairτ\tau at η=102\eta=10^210410^410610^610810^8 to 101210^{12}steps to ϵ=10−4\epsilon=10^{-4} with η=102\eta=10^2steps to ϵ=10−6\epsilon=10^{-6} with η=103\eta=10^3
0 vs 1378885,33421,088
0 vs 811917111114,451147,018
1 vs 711210101014,531141,038
2 vs 720615131322,257220,546
3 vs 568949414175,111515,488
3 vs 856747444360,078375,707
5 vs 869151475273,100505,808
4 vs 91,261645958132,333>106>10^6

The transition time shows no growth with the stepsize. In each of the 24 datasets it peaks near η=102\eta=10^2 and takes the same value at η=108\eta=10^8, 101010^{10} and 101210^{12}.

Steps to a target loss (Table 2, Figure 2(d)). As τ\tau is the number of steps to reach loss 1/η1/\eta, the columns 10410^4 and 10610^6 are the steps to ϵ=10−4\epsilon=10^{-4} and 10−610^{-6} with η=1/ϵ\eta=1/\epsilon, 5 to 81 steps over the 24 datasets. With η=ϵ−1/2\eta=\epsilon^{-1/2} (last two columns), GD needs 444 to 2169 times as many steps at 10−410^{-4} and at least 1600 times as many at 10−610^{-6}. With η=4\eta=4 it reaches 10−610^{-6} within 10610^6 steps on none.

Stepsize, margin and rank. Our main insight is that taking much larger steps need not require a proportionally longer wait for stable convergence. The transition time is bounded polylogarithmically in η\eta (Theorem 2.2), which permits the stepsize η=1/ϵ\eta=1/\epsilon and improves the step complexity from polynomial to polylogarithmic in 1/ϵ1/\epsilon (Corollary 2.3). This dependence on η\eta and ϵ\epsilon is the contribution of the paper and what the experiments above address. The margin and the rank enter Theorem 2.2 through CC and pp, which bound the worst dataset with a given margin and rank. They are not predictions for a given dataset, and we do not claim that they are optimal (see limitations in Section 2).

[1] Wu, Jingfeng, et al. "Large stepsize gradient descent for logistic loss: Non-monotonicity of the loss improves optimization efficiency." The Thirty Seventh Annual Conference on Learning Theory. PMLR, 2024.

[2] Michael Crawshaw, and Mingrui Liu. "Tight bounds for logistic regression with large stepsize gradient descent in low dimension." arXiv preprint arXiv:2602.12471 (2026).

[3] Haodong Wen, Kaiyue Wen, and Jiaye Teng. "Tight Transition Time Bounds for Separable Logistic Regression at the Edge of Stability." arXiv preprint arXiv:2610.01459 (2026).

Comments on the paper

1 comment
AuthorsOpenReview ↗

General response to all reviewers

We thank all reviewers for their careful reading and constructive comments. We have uploaded a revised manuscript, in which all changes are marked in blue. Below we summarize the main points addressed during the rebuttal and refer to the individual responses and to the revised text.

1. Main insight and scope (Reviewer EJJj, W1; Reviewer Z5E6, W1 and W2). Our main insight is that taking much larger steps need not require a proportionally longer wait for stable convergence. [1] balance the lengths of the unstable and the stable phase, whereas we bound the transition time polylogarithmically in the stepsize η\eta. This allows the larger constant stepsize η=1/ϵ\eta=1/\epsilon and improves the step complexity from O~(1/ϵ)\widetilde O(1/\sqrt\epsilon) to O(ln⁡p(1/ϵ))O(\ln^{p}(1/\epsilon)) in arbitrary dimension. The insight is now stated in the introduction (page 2, lines 85–86). Our results are for a constant stepsize, and we do not claim to improve on adaptive or scheduled stepsizes such as those of [2, 3]. The latter work is now cited in Section 1.1 (page 2, line 107).

2. Experiments (Reviewer w6Bb, W4; second response to Reviewer EJJj, W1). The new Appendix C (pages 30 to 31, lines 1566–1635, with Figure 2 and Table 2) reports experiments on MNIST with constant stepsizes. With a large stepsize the loss can increase sharply during the first steps, but a small loss is reached much faster. For large stepsizes, the phase transition time does not grow with the stepsize. As a result, GD with the stepsize η=1/ϵ\eta=1/\epsilon reaches a target loss ϵ\epsilon in far fewer steps than with smaller stepsizes. The details are in W4 of our response to Reviewer w6Bb.

3. Constants, margin and rank (Reviewer w6Bb, W1 and Q1; Reviewer EJJj, W3 and Q2). Our improvement focuses on the dependence on ϵ\epsilon (equivalently on η\eta) for fixed nn, γ\gamma and rank. The constants CC and pp bound the worst dataset with a given margin and rank, and we do not claim that they are optimal. Our response to Reviewer w6Bb (W1 and Q1) gives the values of pp, CC and η0\eta_0 for representative parameters and the accuracy from which our bound is below that of [1]. Our response to Reviewer EJJj discusses the tradeoff between accuracy and margin (W3) and how the rank appears (Q2).

4. Necessity of the logarithmic dependence (Reviewer w6Bb, W2 and Q2; Reviewer Z5E6, W3). For data of rank at most two our bound does not depend on η\eta. For rank at least three, some logarithmic dependence is necessary for a bound that is uniform over datasets, by the lower bound in the concurrent work of [4].

5. Presentation of the proof (Reviewer w6Bb, W3; Reviewer EJJj, W2). The opening of Section 3 (pages 5 to 6, lines 262–273) now explains why the argument of Wu et al. (2024) yields a bound linear in η\eta and states the role of each of Lemmas 3.1 to 3.5 in our analysis.

6. Beyond logistic regression (Reviewer EJJj, Q1; Reviewer Z5E6, W2). Our analysis extends to regularized logistic regression, where it gives a polylogarithmic dependence on 1/λ1/\lambda. The statement and the idea of the proof are in our response to Reviewer EJJj (Q1). We are currently working on the full proof of this extension despite the limited time of the rebuttal phase.

In summary, the revised text is in the introduction (page 2, lines 85–86), in Section 1.1 (page 2, line 107), in Section 3 (pages 5-6, lines 262–273), and in the new Appendix C (pages 30-31).

[1] Wu, Jingfeng, et al. "Large stepsize gradient descent for logistic loss: Non-monotonicity of the loss improves optimization efficiency." The Thirty Seventh Annual Conference on Learning Theory. PMLR, 2024.

[2] Zhang, Ruiqi, et al. "Minimax Optimal Convergence of Gradient Descent in Logistic Regression via Large and Adaptive Stepsizes." Journal of Machine Learning Research 27.124 (2026): 1-31.

[3] Kale, Sacchit, et al. "Exponential Convergence of (Stochastic) Gradient Descent for Separable Logistic Regression." arXiv preprint arXiv:2602.18946 (2026).

[4] Haodong Wen, Kaiyue Wen, and Jiaye Teng. "Tight Transition Time Bounds for Separable Logistic Regression at the Edge of Stability." arXiv preprint arXiv:2610.01459 (2026).

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.