# Minimax Optimal Convergence of Gradient Descent in Logistic Regression via Large and Adaptive Stepsizes

arXiv: https://arxiv.org/abs/2504.04105 · HTML: https://mlsanity.com/paper/2504.04105/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 39 of its 50 references that are in the map.
- First posted on arXiv 5 Apr 2025.

## Builds on (most cited first, 30 of 39)

- [The Implicit Bias of Gradient Descent on Separable Data](https://mlsanity.com/paper/1710.10345/) (2017)
- [Gradient Descent on Neural Networks Typically Occurs at the Edge of Stability](https://mlsanity.com/paper/2103.00065/) (2021)
- [The large learning rate phase of deep learning: the catapult mechanism](https://mlsanity.com/paper/2003.02218/) (2020)
- [Self-Stabilization: The Implicit Bias of Gradient Descent at the Edge of Stability](https://mlsanity.com/paper/2209.15594/) (2022)
- [Convergence of Gradient Descent on Separable Data](https://mlsanity.com/paper/1803.01905/) (2018)
- [Understanding the unstable convergence of gradient descent](https://mlsanity.com/paper/2204.01050/) (2022)
- [Understanding the Generalization Benefit of Normalization Layers: Sharpness Reduction](https://mlsanity.com/paper/2206.07085/) (2022)
- [Risk and parameter convergence of logistic regression](https://mlsanity.com/paper/1803.07300/) (2018)
- [SGD Learns Over-parameterized Networks that Provably Generalize on Linearly Separable Data](https://mlsanity.com/paper/1710.10174/) (2017)
- [A Walk with SGD](https://mlsanity.com/paper/1802.08770/) (2018)
- [SGD with Large Step Sizes Learns Sparse Features](https://mlsanity.com/paper/2210.05337/) (2022)
- [Analyzing Sharpness along GD Trajectory: Progressive Sharpening and Edge of Stability](https://mlsanity.com/paper/2207.12678/) (2022)
- [Understanding Edge-of-Stability Training Dynamics with a Minimalist Example](https://mlsanity.com/paper/2210.03294/) (2022)
- [Learning threshold neurons via the "edge of stability"](https://mlsanity.com/paper/2212.07469/) (2022)
- [Large Learning Rate Tames Homogeneity: Convergence and Balancing Effect](https://mlsanity.com/paper/2110.03677/) (2021)
- [Beyond the Quadratic Approximation: the Multiscale Structure of Neural Network Loss Landscapes](https://mlsanity.com/paper/2204.11326/) (2022)
- [Implicit Bias of Gradient Descent for Logistic Regression at the Edge of Stability](https://mlsanity.com/paper/2305.11788/) (2023)
- [Beyond the Edge of Stability via Two-step Gradient Updates](https://mlsanity.com/paper/2206.04172/) (2022)
- [(S)GD over Diagonal Linear Networks: Implicit Regularisation, Large Stepsizes and Edge of Stability](https://mlsanity.com/paper/2302.08982/) (2023)
- [Large Stepsize Gradient Descent for Logistic Loss: Non-Monotonicity of the Loss Improves Optimization Efficiency](https://mlsanity.com/paper/2402.15926/) (2024)
- [Fast Margin Maximization via Dual Acceleration](https://mlsanity.com/paper/2107.00595/) (2021)
- [Stochasticity of Deterministic Gradient Descent: Large Learning Rate for Multiscale Objective Function](https://mlsanity.com/paper/2002.06189/) (2020)
- [Good regularity creates large learning rate implicit biases: edge of stability, balancing, and catapult](https://mlsanity.com/paper/2310.17087/) (2023)
- [Gradient Descent Monotonically Decreases the Sharpness of Gradient Flow Solutions in Scalar Networks and Beyond](https://mlsanity.com/paper/2305.13064/) (2023)
- [Provably Faster Gradient Descent via Long Steps](https://mlsanity.com/paper/2307.06324/) (2023)
- [Acceleration by Stepsize Hedging II: Silver Stepsize Schedule for Smooth Convex Optimization](https://mlsanity.com/paper/2309.16530/) (2023)
- [Acceleration by Stepsize Hedging I: Multi-Step Descent and the Silver Stepsize Schedule](https://mlsanity.com/paper/2309.07879/) (2023)
- [From Stability to Chaos: Analyzing Gradient Descent Dynamics in Quadratic Regression](https://mlsanity.com/paper/2310.01687/) (2023)
- [Large Stepsize Gradient Descent for Non-Homogeneous Two-Layer Networks: Margin Improvement and Fast Optimization](https://mlsanity.com/paper/2406.08654/) (2024)
- [Accelerated Objective Gap and Gradient Norm Convergence for Gradient Descent via Long Steps](https://mlsanity.com/paper/2403.14045/) (2024)

## Built on by (most cited first, 7 of 7)

- [Large Stepsizes Accelerate Gradient Descent for Regularized Logistic Regression](https://mlsanity.com/paper/2506.02336/) (2025)
- [Gradient Descent with Provably Tuned Learning-rate Schedules](https://mlsanity.com/paper/2512.05084/) (2025)
- [Product-Stability: Provable Convergence for Gradient Descent on the Edge of Stability](https://mlsanity.com/paper/2604.02653/) (2026)
- [Convergence of Steepest Descent and Adam under Non-Uniform Smoothness](https://mlsanity.com/paper/2605.30648/) (2026)
- [Towards Understanding Momentum Acceleration in River-Valley Loss Landscape](https://mlsanity.com/paper/2609.30957/) (2026)
- [Exponential Convergence of (Stochastic) Gradient Descent for Separable Logistic Regression](https://mlsanity.com/paper/2602.18946/) (2026)
- [Efficient Logistic Regression with Mixture of Sigmoids](https://mlsanity.com/paper/2604.02920/) (2026)

## Abstract (arXiv)

We study textitgradient descent (GD) for logistic regression on linearly separable data with stepsizes that adapt to the current risk, scaled by a constant hyperparameter η. We show that after at most 1/γ2 burn-in steps, GD achieves a risk upper bounded by exp(-Theta(η)), where γ is the margin of the dataset. As η can be arbitrarily large, GD attains an arbitrarily small risk textitimmediately after the burn-in steps, though the risk evolution may be textitnon-monotonic. We further construct hard datasets with margin γ, where any batch (or online) first-order method requires Omega(1/γ2) steps to find a linear separator. Thus, GD with large, adaptive stepsizes is textitminimax optimal among first-order batch methods. Notably, the classical textitPerceptron (Novikoff, 1962), a first-order online method, also achieves a step complexity of 1/γ2, matching GD even in constants. Finally, our GD analysis extends to a broad class of loss functions and certain two-layer networks.