Classification with Large-Step Gradient Descent: Unifying Self-Stabilization and Convergence Rates

Salma Tarmoun, Lachlan Ewen MacDonald, Konstantinos Emmanouilidis, Ziqing Xu, René VidalarXiv 2026 · arXiv

TL;DR

This paper provides a unified theoretical framework for understanding why Gradient Descent (GD) remains stable and converges quickly even when using very large learning rates—a phenomenon known as the "Edge of Stability." By decomposing optimization dynamics into parallel drift and orthogonal oscillations, the authors derive the first explicit convergence rates for iterates in classification settings (like logistic regression) and reveal how data geometry can induce a persistent "transient implicit bias."

What Problem Does This Paper Address?

In classical optimization, you are taught to keep your learning rate small to ensure the loss decreases monotonically. However, modern deep learning practitioners often use large learning rates that cause the loss to oscillate wildly. Surprisingly, this "unstable" regime often leads to faster convergence and better generalization.

While previous research has explored this "Edge of Stability" (EoS), a gap remained:

  1. Some theories explained the mechanism (self-stabilization) but didn't provide convergence rates.
  2. Others provided rates for specific losses but didn't explain the underlying geometry.
  3. Existing unified theories worked for least squares (where a manifold of exact minimizers exists) but failed for classification (where the loss infimum is at infinity, and parameters grow indefinitely to maximize the margin).

This paper bridges these gaps for "exponential-tail" losses, which are the bread and butter of classification tasks.

Methods

The authors introduce a geometric framework based on subspace decomposition. They split the parameter space into two parts:

  • A Parallel Subspace ($\mathcal{M}$): The direction along which the loss decreases (e.g., the max-margin direction).
  • An Orthogonal Subspace ($U$): The directions where the curvature is high and the iterates oscillate.

They use a second-order Taylor expansion of the gradient to show that these two components form a coupled dynamical system. Crucially, they identify a third-order coupling term that acts as "implicit gradient descent" on the curvature itself. As the model moves forward in the parallel direction, it naturally reduces the sharpness in the orthogonal directions, eventually damping the oscillations.

Table 1: High-level comparison of related theoretical analyses of GD at the edge of stability.

Datasets

The theory is validated using controlled, synthetic experiments that allow for precise measurement of subspaces and curvature:

  • Pair-Symmetric Logistic Regression: A synthetic 3D dataset where data points are reflected across a plane, creating a clear max-margin direction.
  • Multiclass Simplex Models: An extension to multiclass cross-entropy using centered regular simplices.
  • Non-spanning Geometries: Specialized synthetic setups where the support vectors do not span the entire data subspace, used to test the "transient implicit bias" theory.

Key Insights and Ideas

  • The Curvature-Defined Reference Subspace: Since classification has no finite minimizer, the authors replace the "minimizer manifold" used in regression theory with a subspace defined by the Hessian's structure.
  • Self-Stabilization as Feedback: Oscillations in the sharp directions aren't just noise; they actually accelerate progress in the flat direction, which in turn lowers the sharpness. It’s a self-correcting loop.
  • Three-Phase Damping: The stable phase isn't uniform. The authors prove it consists of:
  • Transition Phase: Oscillations stop growing but don't yet shrink.
  • Linear Contraction: Oscillations shrink exponentially.
  • Polynomial Decay: As the model reaches the tail of the loss, the damping slows down to a power-law rate.
  • Transient Implicit Bias: This is perhaps the most striking finding. In certain geometries (where support vectors don't span the full space), large step sizes can amplify specific orthogonal components. These residuals can persist for a long time, meaning the "path" taken by large-step GD leaves a lasting mark on the final model's alignment.
Figure 2: Roadmap of Theorem 1.

Key Results

  • Explicit Iterate Bounds: The authors provide the first explicit bounds for the iterates ($\theta_t$), not just the loss value, for logistic and cross-entropy losses under large-step GD.
  • Verification of EoS Dynamics: Figure 1 (warmup example) and Figure 3 (spanning model) empirically confirm the predicted three-phase decay. In Figure 3, we see the "Stability Product" $\eta \lambda_1$ hover near the stability boundary before decaying.
  • Geometry Matters: In "non-spanning" cases (Figure 4), the authors show that while the model eventually aligns with the max-margin direction, larger step sizes ($\eta$) result in larger persistent residuals in "weak" directions. This proves that the choice of learning rate changes the qualitative solution in finite time.

Limitations and Future Work

  • Symmetry Assumptions: Much of the rigorous verification relies on symmetric data models (e.g., pair-symmetric logistic regression). While the authors provide some evidence for "approximate symmetry" (Appendix F), a general theory for arbitrary asymmetric data remains open.
  • Linear vs. Deep Models: The analysis is focused on linear classification. While the EoS phenomenon is most famous in deep neural networks, extending this specific geometric decomposition to multi-layer non-linear architectures is a significant challenge.
  • Subspace Identification: In practice, identifying the "reference subspace" for a massive ResNet or Transformer is non-trivial. The authors suggest this as a key area for future investigation.

Summary updated

Abstract

Neural networks are often trained with gradient descent (GD) using step sizes that exceed classical stability thresholds, a regime where standard convergence theory no longer applies. Despite exhibiting non-monotonic loss and oscillatory dynamics, this regime frequently leads to faster convergence and better generalization. Existing theoretical perspectives offer complementary but incomplete insights: one identifies a self-stabilization mechanism that drives GD toward flat regions but does not yield convergence rates; another derives rigorous rates for specific losses but does not explain the underlying stabilization mechanism; and a third unifies these views for overparameterized least squares, but relies on the existence of a minimizer manifold, which is absent in classification settings. In this work, we extend this unified geometric perspective to exponential-tail losses, including logistic and cross-entropy losses in separable linear classification, where the loss infimum is not attained at any finite parameter. We identify a curvature-defined reference subspace that replaces the role of the minimizer manifold, yielding a coupled dynamical system in which orthogonal oscillations are damped by parallel progress along directions of decreasing sharpness. Under regularity conditions, which we verify for logistic and multiclass cross-entropy losses on symmetric data models, we derive explicit bounds for the iterates, not just the loss, covering both the unstable and stable regimes, and revealing a three-phase damping structure in the latter. Our analysis further uncovers a transient implicit bias induced by large step sizes: although GD converges asymptotically to the max-margin direction, large steps can leave persistent orthogonal residuals and, in certain geometries, amplify them, affecting finite-time alignment with the max-margin direction.
BibTeX
@misc{tarmoun2026classification,
  author = {Salma Tarmoun and Lachlan Ewen MacDonald and Konstantinos Emmanouilidis and Ziqing Xu and René Vidal},
  title = {{Classification with Large-Step Gradient Descent: Unifying Self-Stabilization and Convergence Rates}},
  year = {2026},
  eprint = {2611.17459},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.17459},
}
Figure