Research map / Optimization / Nonconvex and smooth optimization
Large Stepsizes Accelerate Gradient Descent for Regularized Logistic Regression
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 constant-stepsize gradient descent on l2-regularized logistic regression with separable data can exploit large (edge-of-stability) stepsizes to reach Nesterov-like O~(sqrt(kappa)) step complexity, with a matching critical stepsize threshold.
Problem
Gradient descent with a constant stepsize is usually analyzed in the stable regime, giving O(kappa) step complexity for strongly convex problems; it is unclear whether large, nonmonotone (edge-of-stability) stepsizes help for l2-regularized logistic regression, where the minimizer is finite unlike u
Approach
Large constant stepsizes push GD into an edge-of-stability phase that is nonmonotone but then transitions to a stable phase, yielding exponential convergence in O~(1/sqrt(lambda)) steps for small regularization and O~(1/lambda^{2/3}) for general regularization; the largest convergent stepsize is characterized as Theta(1/(lambda ln(1/lambda))).
Key results
- With small regularization (lambda <= gamma^2/(C n ln n)) and stepsize eta ~ 1/sqrt(lambda), GD reaches epsilon error in O(ln(1/eps)/sqrt(lambda)) steps, matching Nesterov's acceleration.
- For general lambda, GD with eta ~ (gamma^2/lambda)^{1/3} reaches epsilon error in O(ln(1/eps)/lambda^{2/3}) steps, improving the stable-regime O(ln(1/eps)/lambda).
- The critical stepsize for local convergence is Theta(1/(lambda ln(1/lambda))), improving the trivial 2/lambda divergence threshold by a log factor.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a large constant stepsize in the EoS regime instead of a stable-regime small stepsize | GD for ℓ2-regularized logistic regression with small regularization · Linearly separable data; λ≲1/n² | steps to ε error: Ocal(ln(1/ε)/λ) -> Ocal(ln(1/ε)/√λ) | Helped |
| Use a large constant stepsize in the EoS regime instead of a stable-regime small stepsize | GD for ℓ2-regularized logistic regression with general regularization · Linearly separable data | steps to ε error: Ocal(ln(1/ε)/λ) -> Ocal(ln(1/ε)/λ^{2/3}) | Helped |
| Use a large stepsize η=Θ((γ²n)^{1/3}) rather than η=1 | GD with λ=1/n · Population risk, separable distribution | steps to population risk Otilde(1/n): Ocal(n ln n) -> Ocal((n/γ)^{2/3}ln n) | Helped |
| Use regularization λ=1/n and a large stepsize rather than unregularized GD with η=Θ(1) | GD · Population risk, separable distribution | steps to population risk Otilde(1/n): Ocal(n) -> Ocal((n/γ)^{2/3}ln n) | Mixed |
| Use Nesterov's momentum instead of large-stepsize GD | GD with λ=1/n · Population risk, separable distribution | steps to population risk Otilde(1/n): Ocal(n^{1/2} ln n ) vs Ocal((n/γ)^{2/3}ln n) | Hurt |
Surprising findings
- With large stepsizes, GD's objective evolves nonmonotonically yet converges faster than in the stable regime.
- Without regularization, a large stepsize does not improve population-risk step complexity over eta=1 in the stated analysis.
Limitations
- Small-regularization acceleration requires lambda <= O(1/(n ln n)), which may be suboptimal under statistical noise.
- Global convergence for finite-dimensional case with stepsizes between 1/sqrt(lambda) and the critical threshold is open (only conjectured or 1-D).
- Population risk analysis relies on best-known upper bounds and may not be sharp for the actual distribution.
Experimental setup
Metrics: step complexity objective gap population risk bound
Baselines: stable-regime gradient descent Nesterov's momentum adaptive gradient descent silver stepsize schedule
Builds on: edge of stability analysis of logistic regression (Wu et al.) split optimization lemma Nesterov momentum
Closest papers by meaning
- Gradient Descent Converges Arbitrarily Fast for Logistic Regression via Large and Adaptive Stepsizes (ICML 2025 · similarity 0.95)
- Constant Stepsize Local GD for Logistic Regression: Acceleration by Instability (ICML 2025 · similarity 0.91)
- Local Steps Speed Up Local GD for Heterogeneous Distributed Logistic Regression (ICLR 2025 · similarity 0.90)
- From Logistic Regression to the Perceptron Algorithm: Exploring Gradient Descent with Large Step Sizes (AAAI 2025 · similarity 0.89)
- Large Stepsize Gradient Descent for Non-Homogeneous Two-Layer Networks: Margin Improvement and Fast Optimization (NeurIPS 2024 · similarity 0.89)
- Any-stepsize Gradient Descent for Separable Data under Fenchel–Young Losses (NeurIPS 2025 · similarity 0.88)
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.