# Gradient Descent Converges Linearly for Logistic Regression on Separable Data

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 22 references that are in the map.
- First posted on arXiv 26 Jun 2023.

## Builds on (most cited first, 12 of 12)

- [The Implicit Bias of Gradient Descent on Separable Data](https://mlsanity.com/paper/1710.10345/) (2017)
- [Convergence of Gradient Descent on Separable Data](https://mlsanity.com/paper/1803.01905/) (2018)
- [Risk and parameter convergence of logistic regression](https://mlsanity.com/paper/1803.07300/) (2018)
- [On Iterative Hard Thresholding Methods for High-dimensional M-Estimation](https://mlsanity.com/paper/1410.5137/) (2014)
- [Margins, Shrinkage, and Boosting](https://mlsanity.com/paper/1303.4172/) (2013)
- [Acceleration with a Ball Optimization Oracle](https://mlsanity.com/paper/2003.08078/) (2020)
- [Global linear convergence of Newton's method without strong-convexity or Lipschitz gradients](https://mlsanity.com/paper/1806.00413/) (2018)
- [Sparse Convex Optimization via Adaptively Regularized Hard Thresholding](https://mlsanity.com/paper/2006.14571/) (2020)
- [Matrix Scaling and Balancing via Box Constrained Newton's Method and Interior Point Methods](https://mlsanity.com/paper/1704.02310/) (2017)
- [Iterative Hard Thresholding with Adaptive Regularization: Sparser Solutions Without Sacrificing Runtime](https://mlsanity.com/paper/2204.08274/) (2022)
- [Condition Number Analysis of Logistic Regression, and its Implications for Standard First-Order Solution Methods](https://mlsanity.com/paper/1810.08727/) (2018)
- [Unifying Width-Reduced Methods for Quasi-Self-Concordant Optimization](https://mlsanity.com/paper/2107.02432/) (2021)

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

- [Gradient Descent on Logistic Regression with Non-Separable Data and Large Step Sizes](https://mlsanity.com/paper/2406.05033/) (2024)
- [Armijo Line-search Can Make (Stochastic) Gradient Descent Provably Faster](https://mlsanity.com/paper/2503.00229/) (2025)
- [Gradient-Normalized Smoothness for Optimization with Approximate Hessians](https://mlsanity.com/paper/2506.13710/) (2025)
- [AutoSGD: Automatic Learning Rate Selection for Stochastic Gradient Descent](https://mlsanity.com/paper/2505.21651/) (2025)
- [Adaptively Point-weighting Curriculum Learning](https://mlsanity.com/paper/2505.01665/) (2025)
- [Finite-Sample Performance of Gradient Descent in Logistic Regression with Gaussian Design](https://mlsanity.com/paper/2606.21683/) (2026)
- [Exponential Convergence of (Stochastic) Gradient Descent for Separable Logistic Regression](https://mlsanity.com/paper/2602.18946/) (2026)

## Abstract (arXiv)

We show that running gradient descent with variable learning rate guarantees loss f(x) ≤ 1.1 · f(x^*) + ε for the logistic regression objective, where the error ε decays exponentially with the number of iterations and polynomially with the magnitude of the entries of an arbitrary fixed solution x^*. This is in contrast to the common intuition that the absence of strong convexity precludes linear convergence of first-order methods, and highlights the importance of variable learning rates for gradient descent. We also apply our ideas to sparse logistic regression, where they lead to an exponential improvement of the sparsity-error tradeoff.