# Gradient Descent on Logistic Regression with Non-Separable Data and Large Step Sizes arXiv: https://arxiv.org/abs/2406.05033 · HTML: https://mlsanity.com/paper/2406.05033/ ## Key facts - Cited by 14 papers in the map (data through 14 Oct 2026). - Builds on 25 of its 40 references that are in the map. - First posted on arXiv 7 Jun 2024. ## Builds on (most cited first, 25 of 25) - [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) - [Handbook of Convergence Theorems for (Stochastic) Gradient Methods](https://mlsanity.com/paper/2301.11235/) (2023) - [Self-Stabilization: The Implicit Bias of Gradient Descent at the Edge of Stability](https://mlsanity.com/paper/2209.15594/) (2022) - [Understanding the unstable convergence of gradient descent](https://mlsanity.com/paper/2204.01050/) (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) - [The Implicit Regularization of Dynamical Stability in Stochastic Gradient Descent](https://mlsanity.com/paper/2305.17490/) (2023) - [Implicit Bias of Gradient Descent for Logistic Regression at the Edge of Stability](https://mlsanity.com/paper/2305.11788/) (2023) - [Large Stepsize Gradient Descent for Logistic Loss: Non-Monotonicity of the Loss Improves Optimization Efficiency](https://mlsanity.com/paper/2402.15926/) (2024) - [Catapults in SGD: spikes in the training loss and their impact on generalization through feature learning](https://mlsanity.com/paper/2306.04815/) (2023) - [Stochasticity of Deterministic Gradient Descent: Large Learning Rate for Multiscale Objective Function](https://mlsanity.com/paper/2002.06189/) (2020) - [Trajectory Alignment: Understanding the Edge of Stability Phenomenon via Bifurcation Theory](https://mlsanity.com/paper/2307.04204/) (2023) - [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) - [Squareplus: A Softplus-Like Algebraic Rectifier](https://mlsanity.com/paper/2112.11687/) (2021) - [Acceleration by Stepsize Hedging I: Multi-Step Descent and the Silver Stepsize Schedule](https://mlsanity.com/paper/2309.07879/) (2023) - [Quadratic models for understanding catapult dynamics of neural networks](https://mlsanity.com/paper/2205.11787/) (2022) - [From Stability to Chaos: Analyzing Gradient Descent Dynamics in Quadratic Regression](https://mlsanity.com/paper/2310.01687/) (2023) - [Directional Smoothness and Gradient Methods: Convergence and Adaptivity](https://mlsanity.com/paper/2403.04081/) (2024) - [Provable Super-Convergence with a Large Cyclical Learning Rate](https://mlsanity.com/paper/2102.10734/) (2021) - [Accelerated Gradient Descent via Long Steps](https://mlsanity.com/paper/2309.09961/) (2023) - [Gradient Descent Converges Linearly for Logistic Regression on Separable Data](https://mlsanity.com/paper/2306.14381/) (2023) - [Dynamical stability and chaos in artificial neural network trajectories along training](https://mlsanity.com/paper/2404.05782/) (2024) ## Built on by (most cited first, 14 of 14) - [The Optimization Landscape of SGD Across the Feature Learning Strength](https://mlsanity.com/paper/2410.04642/) (2024) - [Large Stepsizes Accelerate Gradient Descent for Regularized Logistic Regression](https://mlsanity.com/paper/2506.02336/) (2025) - [Gradient Descent with Large Step Sizes: Chaos and Fractal Convergence Region](https://mlsanity.com/paper/2509.25351/) (2025) - [From Logistic Regression to the Perceptron Algorithm: Exploring Gradient Descent with Large Step Sizes](https://mlsanity.com/paper/2412.08424/) (2024) - [Gradient Descent on Logistic Regression: Do Large Step-Sizes Work with Data on the Sphere?](https://mlsanity.com/paper/2507.11228/) (2025) - [Any-stepsize Gradient Descent for Separable Data under Fenchel-Young Losses](https://mlsanity.com/paper/2502.04889/) (2025) - [Tight Bounds for Logistic Regression with Large Stepsize Gradient Descent in Low Dimension](https://mlsanity.com/paper/2602.12471/) (2026) - [Finite-Sample Performance of Gradient Descent in Logistic Regression with Gaussian Design](https://mlsanity.com/paper/2606.21683/) (2026) - [Towards Understanding Momentum Acceleration in River-Valley Loss Landscape](https://mlsanity.com/paper/2609.30957/) (2026) - [Loss Gap Parity for Fairness in Heterogeneous Federated Learning](https://mlsanity.com/paper/2603.29818/) (2026) - [Non-asymptotic implicit bias of logistic regression at early-stage gradient descent dynamics](https://mlsanity.com/paper/2608.04382/) (2026) - [Tight Transition Time Bounds for Separable Logistic Regression at the Edge of Stability](https://mlsanity.com/paper/2610.01459/) (2026) - [Large Stepsizes Federated Learning on Logistic Regression with Linearly Separable Data: The Case of Heterogeneous Devices](https://mlsanity.com/paper/2610.05915/) (2026) - [Improved Convergence of Large Stepsize Gradient Descent for Logistic Regression](https://mlsanity.com/paper/2610.06675/) (2026) ## Abstract (arXiv) 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/λ, 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/λ suffices for global convergence. However, for all step sizes between 1/λ and the critical step size 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/λ. 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.