Improved Convergence of Large Stepsize Gradient Descent for Logistic Regression

Xiaochuan Gong; Ang Li

cs.LGOct 5, 2026

Improved Convergence of Large Stepsize Gradient Descent for Logistic Regression

Authors: Xiaochuan Gong, Ang Li

Organizations: University of Maryland, College Park

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 $\widetilde{O}(1/\sqrtε)$ 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 $η=1/ε$ reaches loss $ε$ within $O(\ln^{p}(1/ε))$ steps, where $p$ 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.

Figures & tables

	Complexity	Stepsize	Setting
Wu et al. (2024, Corollary 2)	$\widetilde{O}\big(1/(\gamma^{2}\sqrt{\epsilon})\big)$	$\eta=\Theta(1/\sqrt{\epsilon})$	any $d$
Crawshaw and Liu (2026, Theorem 2.1)	$O\big(n/\gamma+\ln(1/\gamma)/\gamma^{2}\big)$	$\eta\geq\Omega\big(1/(\epsilon(\gamma n+1))\big)$	$d=2$
Corollary 2.3	$O\big(n\gamma^{-4}\ln^{3}(e/\gamma)\ln^{p}(1/\epsilon)\big)$	$\eta=1/\epsilon$	any $d$

Table 1: Step complexity of constant stepsize GD for logistic regression on linearly separable data. Each complexity holds for all sufficiently small

\epsilon

Figure 1: The hierarchy of intervals. (a) The steps in

\mathcal{T}_{+}\setminus\{0\}

are partitioned into root intervals, each carrying one reference direction. An interval carrying

j

reference directions is split into a prefix of at most

R

steps and at most

R

children, and each child inherits the

j

directions and gains one more (Lemma 3.2 ). An interval reached after

\nu

refinements carries

\nu+1

reference directions; it is terminal, is not refined further, and has at most

\lceil 4/\theta\rceil

steps (Lemma 3.4 ). (b) The children of one interval start at coefficients

\sigma_{i}

, measured from the start of the parent, and the points

u_{i}=\ln(\theta\sigma_{i}/(2\Lambda))

are more than

\theta/4

apart, so a sum over the children can be compared with an integral along this axis. Lemma 3.5 applies this at every level of the hierarchy, which yields the factorial saving.

Explore similar work

Gradient Descent on Logistic Regression with Non-Separable Data and Large Step Sizes
Jun 7, 2024Si Yi Meng, Antonio Orvieto, Daniel Yiming Cao +1Step Accuracy Gradient Descent
Department of Computer Science Cornell University Ithaca, NY, USA · ELLIS Institute Tübingen MPI for Intelligent Systems Tübingen AI Center, Germany
Tight Transition Time Bounds for Separable Logistic Regression at the Edge of Stability
Oct 1, 2026Haodong Wen, Kaiyue Wen, Jiaye TengLogistic Regression Optimal Sample Complexity
Stanford University · Shanghai University of Finance and Economics
Finite-Sample Performance of Gradient Descent in Logistic Regression with Gaussian Design
Jun 19, 2026Junren Chen, Arya MazumdarLogistic Regression Finite-Sample
Department of Mathematics, University of Maryland, College Park. · Halıcıoğlu Data Science Institute, UC San Diego.

Jun 7, 2024, cs.LGJ/K move · Enter open · S save

Gradient Descent on Logistic Regression with Non-Separable Data and Large Step Sizes

Si Yi Meng, Antonio Orvieto, Daniel Yiming Cao, Christopher De Sa

Department of Computer Science Cornell University Ithaca, NY, USA · ELLIS Institute Tübingen MPI for Intelligent Systems Tübingen AI Center, Germany

Step Accuracy Gradient Descent Logistic Regression Bifurcation Separability High-Dimensional+1

Open paper AskPDF arXiv

We study gradient descent (GD) dynamics on logistic regression problems with large, constant step sizes. For linearly-separable data, it is known that GD converges to the minimizer with arbitrarily large step sizes, a property which no longer holds when the problem is not separable. In fact, the behaviour can be much more complex -- a sequence of period-doubling bifurcations begins at the critical step size

2/λ

, where

λ

is the largest eigenvalue of the Hessian at the solution. Using a smaller-than-critical step size guarantees convergence if initialized nearby the solution: but does this suffice globally? In one dimension, we show that a step size less than

1/λ

suffices for global convergence. However, for all step sizes between

1/λ

and the critical step size

2/λ

, one can construct a dataset such that GD converges to a stable cycle. In higher dimensions, this is actually possible even for step sizes less than

1/λ

. Our results show that although local convergence is guaranteed for all step sizes less than the critical step size, global convergence is not, and GD may instead converge to a cycle depending on the initialization.

Abstract

Explore similar work

Gradient Descent on Logistic Regression with Non-Separable Data and Large Step Sizes

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

Finite-Sample Performance of Gradient Descent in Logistic Regression with Gaussian Design