Gradient Descent on Logistic Regression: Do Large Step-Sizes Work with Data on the Sphere?

Title:Gradient Descent on Logistic Regression: Do Large Step-Sizes Work with Data on the Sphere?

Abstract:Gradient descent on logistic regression has many fascinating properties not fully captured by classical analyses. For linearly separable data, the iterates converge in direction to the maximum-margin separator regardless of how large the step size is. For non-separable data, however, cycles may occur even for step sizes below the local stability threshold of $2/\lambda^*$, where $\lambda^*$ is the largest eigenvalue of the Hessian at the solution. We ask whether requiring all examples to have equal norm is a sufficient condition for global convergence below this threshold. We prove that this is indeed true in one dimension. In higher dimensions, even equal-norm datasets can produce cycles, although global convergence holds for the population loss when the examples are uniformly distributed on the sphere. Finally, in one dimension, we relax the equal-norm assumption to an annulus condition that ensures global convergence below the stability threshold, suggesting a path towards analogous sufficient conditions in higher dimensions.

Machine Learning (cs.LG); Optimization and Control (math.OC)

arXiv:2507.11228 [cs.LG]

(or arXiv:2507.11228v2 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2507.11228 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.