Research map / Optimization / Nonconvex and smooth optimization
Gradient Descent Converges Arbitrarily Fast for Logistic Regression via Large and Adaptive Stepsizes
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that gradient descent on separable logistic regression with large, risk-adaptive stepsizes (scaled by base stepsize η) achieves risk exp(-Θ(ηt)) after a margin-dependent burn-in, with matching lower bounds and extensions to general losses and two-layer leaky-ReLU networks.
Problem
Convergence rate of gradient descent for logistic/exponential loss on linearly separable data is limited to exp(-Θ(t)) when adaptive stepsizes are small and the risk decreases monotonically; it is unclear how large stepsizes in the edge-of-stability regime affect rates.
Approach
Use risk-adaptive stepsizes η_t = η/L(w_t) (scaled by a large base η) and a split-optimization comparator argument with convexity of the modified loss ϕ, showing the averaged iterate reaches exp(-Θ(ηt)) after a margin-dependent burn-in, even though risk may be non-monotone.
Key results
- Averaged GD iterate with adaptive stepsize η/L(w_t) achieves L(w̄_t) ≤ exp(-γ²ηt/8) for t ≥ √2/γ² (exp. loss) with arbitrarily large η.
- Adaptive-stepsize GD staying in stable regime has risk lower bound exp(-ct), showing EoS is needed for faster rates.
- Any first-order method requires Ω(γ^{-2/3}) burn-in steps to reach small risk on a constructed dataset.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use adaptive stepsizes with an arbitrarily large base stepsize η | GD for linearly separable logistic regression · Linearly separable logistic regression | risk upper bound: C exp(−γ²ηt) -> exp(−1/8γ²ηt) | Helped |
| Keep adaptive-step GD in the stable regime with monotonically decreasing risk | Adaptive-step GD for logistic regression · Constructed linearly separable logistic regression dataset | risk lower bound: exp (−ct) | Hurt |
| Use adaptive stepsizes with an arbitrarily large base stepsize η | GD for a two-layer leaky-ReLU network · Linearly separable data, two-layer network | minimum risk upper bound: exp (−1/8α²γ²ηt) | Helped |
| Use adaptive stepsizes with an arbitrarily large base stepsize η | GD for classification losses satisfying Assumption 5.1 · Linearly separable classification, general loss | risk upper bound: ℓ (−1/8γ²ηt) | Helped |
| Require monotonically decreasing risk instead of allowing entry into the edge-of-stability regime | Adaptive-step GD for logistic regression · Linearly separable logistic regression | risk convergence rate: exp(−Θ(ηt)) -> exp(−Θ(t)) | Hurt |
| Use an arbitrary first-order method from zero initialization | First-order methods for linearly separable data · Constructed linearly separable dataset | iteration complexity: c2γ−2/3 | Hurt |
Surprising findings
- Risk can be non-monotone under large stepsizes yet convergence becomes arbitrarily fast.
- Adaptive-stepsize GD with exponential loss also converges for arbitrarily large base stepsize, unlike large constant stepsize GD which fails under exponential loss.
Limitations
- Burn-in threshold depends on margin γ; lower bound Ω(γ^{-2/3}) is conjectured not tight (conjectured Ω(γ^{-1}))
- Two-layer network result guarantees only the best iterate over the trajectory, not averaged iterate, since ϕ need not be convex
- Analysis restricted to linearly separable data with positive margin
Experimental setup
Datasets: synthetic linearly separable data
Metrics: empirical risk upper bound convergence rate exp(-Θ(ηt)) iteration lower bound
Baselines: GD with adaptive stepsizes in stable regime (Ji & Telgarsky 2021) GD with large constant stepsize (Wu et al. 2024) Cai et al. 2024 two-layer GD
Builds on: Ji & Telgarsky 2021 primal-dual GD analysis Wu et al. 2024 large constant stepsize GD Cai et al. 2024 two-layer network GD Nacson et al. 2019 Altschuler & Parrilo 2024
Closest papers by meaning
- Large Stepsizes Accelerate Gradient Descent for Regularized Logistic Regression (NeurIPS 2025 · similarity 0.95)
- From Logistic Regression to the Perceptron Algorithm: Exploring Gradient Descent with Large Step Sizes (AAAI 2025 · similarity 0.91)
- Constant Stepsize Local GD for Logistic Regression: Acceleration by Instability (ICML 2025 · similarity 0.90)
- Local Steps Speed Up Local GD for Heterogeneous Distributed Logistic Regression (ICLR 2025 · similarity 0.90)
- Any-stepsize Gradient Descent for Separable Data under Fenchel–Young Losses (NeurIPS 2025 · similarity 0.90)
- Finite-Sample Performance of Gradient Descent in Logistic Regression with Gaussian Design (NeurIPS 2026 · similarity 0.90)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.