Improved Convergence of Large Stepsize Gradient Descent for Logistic Regression

arXiv:2610.06675v1 Announce Type: new Abstract: We study gradient descent (GD) with a large constant stepsize for logistic regression on linearly separable data. Existing analysis shows an accelerated rate of widetilde{O}(1/sqrt{epsilon}) to reach loss epsilon with an aggressive stepsize, although the loss may initially oscillate. Tighter control of the oscillatory dynamics has been available only for two-dimensional data. We prove a substantially faster rate in arbitrary dimension: GD with a large stepsize eta=1/epsilon reaches loss epsilon within O(ln^{p}(1/epsilon)) steps, where p depends only on the margin and the rank of the data. Our proof improves the bound on the transition time of GD from the oscillatory to the stable phase, after which the loss decreases monotonically. We split the oscillatory phase into recursively nested intervals. The margin and the rank bound the nesting depth, and a counting argument bounds the number of intervals at each depth, together yielding the polylogarithmic step complexity.

Related

• Tight Transition Time Bounds for Separable Logistic Regression at the Edge of Stability
• Large Stepsizes Federated Learning on Logistic Regression with Linearly Separable Data: The Case of Heterogeneous Devices
• Gradient Descent on Logistic Regression with Non-Separable Data and Large Step Sizes

Source: arXiv cs.LG | 2026-10-06