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

Si Yi Meng, Baptiste Goujaud, Antonio Orvieto, Christopher De SaarXiv 2025 · DOI · arXiv

Abstract

While large step sizes in gradient descent (GD) can accelerate convergence in logistic regression, they frequently trigger unstable "cycling" behavior in non-separable datasets. This paper investigates whether normalizing data to the unit sphere—a common heuristic—guarantees global convergence. We show that while this "fix" works in one dimension, it fails in higher dimensions, where complex cycles can emerge even when the step size is below the theoretical local stability threshold.

Introduction

In optimization, larger step sizes generally lead to faster convergence. For logistic regression on linearly separable data, gradient descent is remarkably robust, converging to the maximum-margin solution even with arbitrarily large step sizes. However, real-world data is often non-separable, where classes overlap and a unique, finite optimal solution $w^*$ exists.

Classical theory suggests stability is maintained as long as the step size $\eta$ remains below $2/\lambda$, where $\lambda$ is the largest eigenvalue of the Hessian at the solution. Yet, recent findings indicate that GD can become trapped in "cycles"—oscillating indefinitely—even when $\eta < 2/\lambda$. This paper explores whether the common practice of data normalization (placing all points on the unit sphere) can prevent such instabilities.

Global Convergence in One Dimension

The authors first analyze the 1D case, where data points are restricted to $\{-1, 1\}$. By examining the GD update function $T(w)$, they employ cobweb diagrams to visualize the dynamics of the optimization process.

Cobweb diagram illustrating global convergence in 1D via the update function T(w).

In this 1D setting, the authors prove a "two-step contraction" property: even if a single GD step overshoots the target, the subsequent step is guaranteed to bring the iterate closer to the optimum than its starting point. This ensures that for any step size below the local stability threshold, the algorithm converges globally to $w^*$.

The Failure of Normalization in Higher Dimensions

Surprisingly, the stability guaranteed in 1D does not extend to higher dimensions ($d > 1$). The authors demonstrate this through a constructive "schmearing" technique. They take a known 2D dataset that exhibits cycling behavior and mathematically embed it into a higher-dimensional unit sphere. This process preserves the unstable dynamics of the original 2D base while satisfying the spherical constraint.

To verify these theoretical findings, the authors simulated GD on a constructed dataset in $d=5000$.

Simulation of a period-13 cycle in 5000 dimensions showing the norm of weights, power spectral density (PSD), and individual weight components.

The simulation reveals a clear period-13 cycle, as evidenced by the oscillations in the weight norm $\|w_t\|$ and the distinct peaks in the Power Spectral Density (PSD) plot. This confirms that high-dimensional geometry provides enough "room" for the loss landscape to support stable cycles, even when data is normalized.

Key Insights and Conclusion

The primary takeaway is that data normalization ($\parallel x_i \parallel=1$) is insufficient for ensuring global stability in logistic regression. The gap between local and global stability is significant: a step size can be locally stable (converging if initialized near $w^*$) but globally unstable (trapping distant initializations in cycles).

Future work remains to identify the specific global conditions on a dataset that would guarantee convergence and to explore whether these cycling dynamics explain instabilities observed in training deep learning models with high learning rates.

Summary updated

Abstract

Gradient descent (GD) on logistic regression has many fascinating properties. When the dataset is linearly separable, it is known that the iterates converge in direction to the maximum-margin separator regardless of how large the step size is. In the non-separable case, however, it has been shown that GD can exhibit a cycling behaviour even when the step sizes is still below the stability threshold $2/λ$, where $λ$ is the largest eigenvalue of the Hessian at the solution. This short paper explores whether restricting the data to have equal magnitude is a sufficient condition for global convergence, under any step size below the stability threshold. We prove that this is true in a one dimensional space, but in higher dimensions cycling behaviour can still occur. We hope to inspire further studies on quantifying how common these cycles are in realistic datasets, as well as finding sufficient conditions to guarantee global convergence with large step sizes.
BibTeX
@misc{meng2025gradient,
  author = {Si Yi Meng and Baptiste Goujaud and Antonio Orvieto and Christopher De Sa},
  title = {{Gradient Descent on Logistic Regression: Do Large Step-Sizes Work with Data on the Sphere?}},
  year = {2025},
  eprint = {2507.11228},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2507.11228},
}
Figure