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.
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$.
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