Organizations: AMCS, University of Pennsylvania, Philadelphia, PA 19104 · IDEAS, University of Pennsylvania, Philadelphia, PA 19104 · ESE, University of Pennsylvania, Philadelphia, PA 19104 · CIS, University of Pennsylvania, Philadelphia, PA 19104 · Statistics and Data Science, University of Pennsylvania, Philadelphia, PA 19104 · Radiology, University of Pennsylvania, Philadelphia, PA 19104
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.
Figures & tables
Self-stabilization mechanism?
Rates
Loss setting
Reference Geometry
Damian et al. Damian et al. (2023)
✓
✗
Abstract conditions †
Stable Set
Wu et al. Wu et al. (2024) ; Wu et al. (2025)
✗
✓
Logistic-like
Max-margin line
MacDonald et al. MacDonald et al. (2025)
✓
✓
Least squares
Minimizer manifold
This work
✓
✓
Exponential-tail
Curvature-defined subspace
Table 1: High-level comparison of related theoretical analyses of GD at the edge of stability.
Figure 1: GD dynamics illustrating the flat subspace M , orthogonal oscillations, evolution of the loss, and parameter magnitudes.
Category
Assumption
Role
parallel direction geometry
1. Subspace Alignment
Parallel–orthogonal decoupling on M
2. Relative Curvature Comparability
Curvature control in neighborhood of M
3. Loss–Curvature Compatibility
Parallel drift lowers loss and curvature
Decay profile
4. Local Curvature Decay
Local curvature decay rate
5. Exponential Tail
Tail gradient/sharpness profile
Table 2: Summary of the structural assumptions used in the convergence analysis.
Figure 2: Roadmap of Theorem 1 .
Figure 3: Unstable and stable phases in a spanning logistic model
Figure 4: Non-spanning logistic regression at step sizes η/ηc∈{1,1.5,2,2.5,3} , where ηc:=2/λmax(∇2L(θ0)) . (a) Loss. (b) Angle to max-margin line M . (c) Conditioning ratio ρt . (d) Weak component ∣cwk∣ . (e) Strong component ∣csv∣ . (f) Parallel coordinate.
Appendix figures & tables4 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 5: Non-spanning configuration with α2=4 .
Figure 6: Non-spanning configuration with α2=3 .
Figure 7: Non-spanning support geometry produces learning-rate-dependent residuals in pair-symmetric logistic regression ( R3 , T=20,000 steps). (A) Signed-feature schematics. Reflected pairs zi,±=aie1±ui are connected by dashed lines. The slow support group (orange, a=1 ) spans only e2 ; the fast spur group (blue, a=4 ) spans e3 . In the spanning control, an additional slow group (purple) adds support in e3 . Both geometries share the same max-margin line e1 . (B) Final spur residual ∣⟨θT,e3⟩∣ versus learning rate. The non-spanning geometry retains a systematically larger residual, with the gap widening at large η where unstable amplification is strongest. (C) Angle between θT and the max-margin direction. The non-spanning residual translates into a larger finite-time deviation from the asymptotic classifier, confirming that top-eigenvalue stabilization alone does not guarantee uniform contraction of all orthogonal components.
Figure 8: Small asymmetric perturbation of the pair-symmetric logistic model.
Modern deep learning has been shown to operate using learning rates far larger than those justified by classical optimization theory. Most prior analyses of this phenomenon focus on deterministic gradient descent, leaving the stochastic setting largely unexplored. In this work, we provide sharp convergence guarantees for Stochastic Gradient Descent (SGD) applied to the multiclass cross-entropy loss, for both linear classifiers and two-layer neural networks. We show that the stochasticity of SGD may cause the dynamics to alternate between an edge-of-stability regime that is dominated by curvature-driven oscillations, and a stable regime in which the expected loss decreases at a controlled rate. Despite that, we prove that SGD stabilizes the dynamics, ensuring that the iterates return to stability in a fixed number of iterations and allowing convergence in the best-iterate sense even with large learning rates. Experiments validate our theoretical findings and illustrate the benefits of SGD in the large-stepsize regime.
The training of neural networks often entails objective functions that are not globally L-smooth. For these functions, it is both theoretically and practically difficult to reply to the question: what is the largest possible step size that ensures the convergence of gradient descent (GD)? We address this longstanding open question in deep learning by providing a unifying definition of "large" step sizes that requires only local Lipschitz (or even Hölder) continuity of the gradient. We design first-order adaptive methods that provably yield large step sizes and show that they operate at the edge of stability (EoS) right from the start of the training. In particular, the loss decreases nonmonotonically and the product between the step size and sharpness, i.e., the largest eigenvalue of the Hessian, stays above the EoS threshold of 2 throughout training. Using our method, we are also able to minimize the sharpness all the way down to its global minimum. Contrary to expectation, we find that encountering globally-flat regions too early in the training may both slow down convergence and jeopardize the generalization ability of the network. Exploiting a self-stabilization argument, we allow GD to enter slightly sharper valleys and turn unsuccessful training runs into very successful ones.
We study gradient descent (GD) with a large constant stepsize for logistic regression on linearly separable data. Existing analysis shows an accelerated rate of O(1/ε) to reach loss ε with an aggressive stepsize, although the loss may initially oscillate. Tighter control of the oscillatory dynamics has been available only for two-dimensional data. We prove a substantially faster rate in arbitrary dimension: GD with a large stepsize η=1/ε reaches loss ε within O(lnp(1/ε)) steps, where p depends only on the margin and the rank of the data. Our proof improves the bound on the transition time of GD from the oscillatory to the stable phase, after which the loss decreases monotonically. We split the oscillatory phase into recursively nested intervals. The margin and the rank bound the nesting depth, and a counting argument bounds the number of intervals at each depth, together yielding the polylogarithmic step complexity.