- 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 iterations, . This paper improved these results, showing that after iterations, 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 iterations, is achieved.
- Furthermore, Wu et. al., 2024 showed that , while in Corollary 2.3, this paper shows that , 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 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
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.
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/γ2 step complexity and its minimax optimality.
These works obtain faster rates using time-varying stepsizes:
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/ϵ) to polylogarithmic O(lnp(1/ϵ)) in any dimension, for fixed n, γ 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.
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/2, fix n,γ,r and let ν be the hierarchy exponent in our analysis. Set S=ln(1/λ) and q=maxν,1. For sufficiently small λ>0, with the constant stepsize η=1/(AλSq) for a suitable A=A(n,γ,r)>0, GD from zero initialization reaches a stable phase within O(Sν) steps and achieves regularized optimality gap ϵ∈(0,1] within O(Sq[S+ln(1/ϵ)]) total steps, where the hidden constants depend only on n,γ,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 and Theorem 2.2 gives τ≤C for all sufficiently large η. Thus the complexity is independent of sufficiently small ϵ, as in [3] for d=2, with a weaker dependence on n and γ (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η)minn,d−2) for fixed n,d≥2 and sufficiently small fixed margin. Since reaching L≤1/η puts GD in the stable phase and guarantees monotonicity afterwards, the same lower bound holds for our τ. With η=1/ϵ, it gives a corresponding Ω((ln(1/ϵ))minn,d−2) lower bound on the worst-case number of steps that GD with this stepsize needs to reach loss ϵ.
[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.