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

arXiv:2507.11228 · cs.LG, math.OC · Submitted 2025-07-15 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Hi, I'm Tom.

Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.

Tom: We're looking at the paper: "Gradient Descent on Logistic Regression".

Jane: Here's the gist of the paper. The gist: In one dimension, restricting data to have equal magnitude allows global convergence for all step sizes below the stability threshold up to 2, but in higher dimensions, cycling behavior can still occur even with this restriction Gradient Descent Dynamics on Logistic Regression The paper investigates the convergence properties of Gradient Descent (GD) applied to logistic regression, specifically examining whether restricting the data to have equal magnitude is a sufficient condition for global convergence under any step size below the stability threshold The core problem addressed is whether GD can exhibit cycling behavior in non-separable cases even when the step sizes are below the stability threshold 2/λ, where λ is the largest eigenvalue of the Hessian at the solution Convergence Guarantees and Stability Thresholds Classical convex optimization theory guarantees convergence if η < 2/L where L is the smoothness constant, but for logistic regression, convergence can be faster with larger step sizes when the dataset is linearly separable In the non-separable setting, the necessary condition for convergence is η < 2/λ where λ is the largest eigenvalue of the Hessian at the minimizer, known as the stability threshold The paper explores whether using step sizes of the form η = γ/λ can still guarantee global convergence to w∗ globally using any γ < 2.

Tom: One-Dimensional Case Analysis The authors prove that in one dimension, restricting examples to be on the unit sphere allows for global convergence for all γ < 2 In this one-dimensional setting, with all labels equal to 1 and a ratio c = m/n ≥ 1, the GD update simplifies to T(w) = w − ηL'(w) where L'(w) = σ(w) − c/(c + 1).

Jane: The analysis shows that for γ in (1, 2), the function T has two stationary points on either side of w∗, leading to oscillatory convergence between them.

Tom: Higher-Dimensional Counterexamples The paper demonstrates that this guarantee does not hold for all dimensions d > 1.

Paper summary: Jane: So, what's the big question they tackle? Is it just about whether GD works or how it works when things are tricky?

Tom: They’re specifically asking if restricting all examples to have equal magnitude is a sufficient condition for global convergence under any step size below that stability threshold. The paper explores this idea.

Lu: So, the authors go into one dimension and show that yes, this restriction does guarantee global convergence for all step sizes less than two.

Meng: One dimension sounds nice because it’s simple to analyze, but what about real-world applications where we have many features? That's where I get nervous about these kinds of geometric constraints.

Tom: That’s the key point they make in the higher dimensions section. They construct a counterexample that shows this guarantee doesn't hold for dimensions greater than one, even when the data is similarly restricted to be on a unit sphere.

Jane: So, it turns out that equal magnitude examples aren't enough to prevent cycling when you move into higher dimensions.

Lalam: The paper essentially proves that in higher dimensions, you can still get cycles of period greater than one even with the data being uniformly distributed on the sphere for the population loss.

Conclusion: Tom: So looking at "Gradient Descent on Logistic Regression: Do Large Step-Sizes Work with Data on the Sphere?", it seems like this paper really highlights how sensitive GD dynamics are to dimensionality.

Jane: It’s about that idea that what works in one dimension might not translate when you have more than a few dimensions, even with nice geometric constraints like equal norms.

Lu: The authors show that while one-dimensional space has global convergence for all step sizes less than two under the unit sphere restriction, higher dimensional datasets can still produce cycles.

Meng: For someone shipping models to production, this means we need to be careful about the underlying geometry of our data; a simple constraint on individual examples isn't a guarantee across different dimensions.

Lalam: I think this suggests that if we want global convergence with large step sizes in higher dimensions, the restriction needs to be on the dataset as a whole, not just every single example.

Tom: Right. The implication for us is that relying solely on equal norms might be too optimistic when dealing with complex data structures across multiple features.

Si Yi Meng, Baptiste Goujaud, Antonio Orvieto, Christopher De Sa

Cornell University · INRIA Paris · ELLIS Institute T¨ubingen

cs.LG, math.OC

Submitted: 2025-07-15

Updated: 2026-10-20

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 79/100

The gist: The gist: In one dimension, restricting data to have equal magnitude allows global convergence for all step sizes below the stability threshold up to 2, but in higher dimensions, cycling behavior can

Key concepts

Stability Threshold (2/λ): This is a critical value related to the largest eigenvalue ($\lambda$) of the Hessian matrix at the solution. If step sizes exceed this threshold, gradient descent can become unstable and fail to converge, potentially leading to oscillations or divergence.
Equal Norm Restriction: This condition means every data point in the dataset has the same magnitude (e.g., they all lie on a sphere). The paper tests whether imposing this geometric constraint on the input data is enough, by itself, to ensure that gradient descent always finds the global minimum.
Cycling Behavior: In non-separable problems, gradient descent can sometimes get stuck in a loop where it repeatedly visits different points without ever settling at the true solution. This cycling is a failure mode that occurs even when step sizes are theoretically small enough for convergence.
One-Dimensional Case: When the data exists in only one dimension, the equal-norm restriction is powerful enough to guarantee global convergence for all step sizes below 2. This demonstrates that lower dimensionality simplifies the dynamics significantly compared to higher dimensions.

Summary

The gist: In one dimension, restricting data to have equal magnitude allows global convergence for all step sizes below the stability threshold up to 2, but in higher dimensions, cycling behavior can still occur even with this restriction

Gradient Descent Dynamics on Logistic Regression

The paper investigates the convergence properties of Gradient Descent (GD) applied to logistic regression, specifically examining whether restricting the data to have equal magnitude is a sufficient condition for global convergence under any step size below the stability threshold The core problem addressed is whether GD can exhibit cycling behavior in non-separable cases even when the step sizes are below the stability threshold 2/λ, where λ is the largest eigenvalue of the Hessian at the solution

Convergence Guarantees and Stability Thresholds

Classical convex optimization theory guarantees convergence if η < 2/L where L is the smoothness constant, but for logistic regression, convergence can be faster with larger step sizes when the dataset is linearly separable In the non-separable setting, the necessary condition for convergence is η < 2/λ where λ is the largest eigenvalue of the Hessian at the minimizer, known as the stability threshold The paper explores whether using step sizes of the form η = γ/λ can still guarantee global convergence to w∗ globally using any γ < 2.

One-Dimensional Case Analysis

The authors prove that in one dimension, restricting examples to be on the unit sphere allows for global convergence for all γ < 2 In this one-dimensional setting, with all labels equal to 1 and a ratio c = m/n ≥ 1, the GD update simplifies to T(w) = w − ηL'(w) where L'(w) = σ(w) − c/(c + 1). The analysis shows that for γ in (1, 2), the function T has two stationary points on either side of w∗, leading to oscillatory convergence between them.

Higher-Dimensional Counterexamples

The paper demonstrates that this guarantee does not hold for all dimensions d > 1. Theorem 3 constructs a counterexample in some dimension d > 1 where, for any γ < 2, there exists a GD trajectory under the step size η = γ/λ that converges to a cycle of period k > 1. This is achieved by schmearing a base dataset with equal magnitude onto a high-dimensional unit sphere while preserving the cycle in the 2-dimensional subspace.

Implications and Future Directions

The findings disproved the conjecture that having data on the unit sphere guarantees global convergence for all step sizes below the stability threshold η = γ/λ when d > 1. The authors conclude that if such sufficient conditions exist, they likely need to be restrictions on the dataset as a whole, rather than restrictions on individual examples, because it is the geometry of the dataset that drives the cycling dynamics.

Rate of Convergence

When GD enters an oscillatory neighborhood in one dimension, a two-step contraction is guaranteed. The rate of convergence, when starting from the oscillatory neighborhood, is shown to be linear (in two-steps) once inside the contraction neighborhood. This rate depends on γ as it approaches the bifurcation point where a stable 2-cycle emerges.

The paper's work helps inspire further studies on quantifying how common these cycles are in realistic datasets and finding sufficient conditions to guarantee global convergence with large step sizes. The results suggest that the restriction to equal magnitude is not sufficient for higher dimensions, highlighting the importance of dataset geometry in determining GD behavior.

Improvements for AI systems

Global convergence guarantee for one-dimensional problems with equal magnitude data can be extended to step sizes up to 2/lambda when data is restricted to a unit sphere, enabling faster learning rates in simple models. This allows AI systems trained on one-dimensional feature spaces to use larger steps without risking cycling, improving training speed.
For non-separable problems in higher dimensions, the paper provides a counterexample showing that global convergence is not guaranteed for any step size below the stability threshold when data is restricted to the unit sphere. This highlights the need for more robust initialization strategies or data regularization when dealing with complex, high-dimensional datasets in deep learning.
The analysis of one-step contraction from right to left demonstrates that if iterates cross the solution point in a specific way, they can be pushed back towards it in two steps. This principle can inspire the design of adaptive step size mechanisms that detect crossing behavior and adjust the learning rate accordingly to prevent divergence or cycling during training.
The construction of a high-dimensional counterexample suggests that adding structured noise or specific outliers can induce cyclic behavior even when data is normalized to the unit sphere. AI systems should be designed with inherent robustness against such pathological data structures, perhaps through regularization terms in the loss function or specialized batch sampling techniques to avoid these problematic configurations.