cs.LGFeb 21, 2026

Exponential Convergence of (Stochastic) Gradient Descent for Separable Logistic Regression

Authors: Sacchit Kale, Piyushi Manupriya, Pierre Marion, Francis Bach, Anant Raj

Organizations: Undergraduate Programme Indian Institute of Science, Bangalore. · Dept. of Computer Science and Automation Indian Institute of Science, Bangalore. · Inria, Ecole Normale Supérieure PSL Research University, Paris, France.

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

Gradient descent and stochastic gradient descent are central to modern machine learning, yet their behavior under large step sizes remains theoretically unclear. Recent work suggests that acceleration often arises near the edge of stability, where optimization trajectories become unstable and difficult to analyze. Existing results for separable logistic regression achieve faster convergence by explicitly leveraging such unstable regimes through constant or adaptive large step sizes. In this paper, we show that instability is not inherent to acceleration. We prove that gradient descent with a simple, non-adaptive increasing step-size schedule achieves exponential convergence for separable logistic regression under a margin condition, while remaining entirely within a stable optimization regime. The resulting method is anytime and does not require prior knowledge of the optimization horizon or target accuracy. We also establish exponential convergence of stochastic gradient descent using a lightweight adaptive step-size rule that avoids line search and specialized procedures, improving upon existing polynomial-rate guarantees. Together, our results demonstrate that carefully structured step-size growth alone suffices to obtain exponential acceleration for both gradient descent and stochastic gradient descent.

Figures & tables

Figure 1: Comparison of our GD ( 6 ) and constant step-size gradient descent for logistic regression on a synthetic linearly separable dataset. The plot shows the evolution of the empirical logistic loss L(wt)\mathcal{L}(\mathbf{w}_{t}) (log scale) as a function of iterations tt .
Figure 2: Dynamics of Gradient descent for logistic regression on a synthetic linearly separable dataset. Left: Evolution of the empirical loss L(wt)\mathcal{L}(\mathbf{w}_{t}) and inverse step size 1/ηt1/\eta_{t} in log scale. Right: Plot of ln⁡(St)\ln(S_{t}) versus t1/3t^{1/3} , validating order of growth of ln⁡(St)\ln(S_{t}) .
Figure 3: Average loss values with SGD ( 10 ) for logistic regression over a synthetically generated 10-dimensional data.
Figure 4: Average loss values with SGD ( 10 ) for logistic regression over an MNIST subset for different pair of labels
More in this topic

Gradient Descent

Gradient descent iteratively updates model parameters to reduce a loss using its slope, with variants for speed, scale, and constraints.

See all 118 papers

Explore similar work

CardsList
Oct 5, 2026

Improved Convergence of Large Stepsize Gradient Descent for Logistic Regression

We study gradient descent (GD) with a large constant stepsize for logistic regression on linearly separable data. Existing analysis shows an accelerated rate of O~(1/ε)\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/εη=1/ε reaches loss εε within O(ln⁡p(1/ε))O(\ln^{p}(1/ε)) steps, where pp 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.

Xiaochuan Gong, Ang Li

University of Maryland, College Park

Logistic RegressionGradient DescentGradient Descent Dynamics
AskPDF
Jun 7, 2024

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

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/λ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/λ1/λ suffices for global convergence. However, for all step sizes between 1/λ1/λ and the critical step size 2/λ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/λ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.

Si Yi Meng, Antonio Orvieto, Daniel Yiming Cao +1

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

Dynamical SystemsLogistic RegressionOptimization Convergence AnalysisGradient DescentGradient Descent Dynamics
AskPDF
May 28, 2026

Convergence of Steepest Descent and Adam under Non-Uniform Smoothness

Recent work has analyzed the convergence of first-order methods under non-uniform smoothness assumptions that better model the loss landscape in machine learning tasks. We generalize this assumption to objectives whose curvature is an affine function of the objective value. This property is satisfied by a broad class of problems, including logistic regression, generalized linear models with a logistic link function, softmax policy gradient in reinforcement learning, and a class of neural networks. Under this assumption and gradient domination conditions, we establish a general convergence rate for the steepest descent method, and deterministic, diagonal variants of RMSProp and Adam. Our results imply that for logistic regression on separable data and the softmax policy gradient objective, sign GD converges linearly and is provably faster than GD. Furthermore, we show that for a class of two-layer neural networks on separable data, RMSProp and Adam can converge at a linear rate with a constant step-size and momentum parameter. Finally, we present a lower bound demonstrating that, under our assumption, RMSProp and Adam are provably faster than AdaGrad, AMSGrad, gradient descent, and heavy-ball momentum.

Sharan Vaswani, Yifan Sun, Reza Babanezhad

1Simon Fraser University · 2Stony Brook University · 3Samsung AI, Montreal.

Optimization Convergence AnalysisGradient DescentNonconvex OptimizationAdaptive Gradient Methods
AskPDF