Abstract
The dynamical stability of the iterates during training plays a key role in determining the minima obtained by optimization algorithms. For example, stable solutions of gradient descent (GD) correspond to flat minima, which have been associated with favorable features. While prior work often relies on linearization to determine stability, it remains unclear whether linearized dynamics faithfully capture the full nonlinear behavior. Recent work has shown that GD may stably oscillate near a linearly unstable minimum and still converge once the step size decays, indicating that linear analysis can be misleading. In this work, we explicitly study the effect of nonlinear terms. Specifically, we derive an exact criterion for stable oscillations of GD near minima in the multivariate setting. Our condition depends on high-order derivatives, generalizing existing results. Extending the analysis to SGD, we show that nonlinear dynamics can diverge in expectation even if a single batch is unstable. This implies that stability can be dictated by a single batch that oscillates unstably, rather than an average effect, as linear analysis suggests. Finally, we prove that if all batches are linearly stable, the nonlinear dynamics of SGD are stable in expectation.
Introduction: The Limits of Linear Stability
In deep learning, the stability of optimization trajectories is often analyzed by linearizing the loss landscape into a quadratic bowl. However, modern training frequently occurs at the "Edge of Stability" (EoS), where the learning rate exceeds the threshold for local convergence, leading to persistent oscillations. Standard linear theory predicts that such oscillations should result in divergence. In practice, however, Gradient Descent (GD) often exhibits "stable oscillations" that eventually lead to convergence. This paper bridges the gap between theory and practice by investigating how nonlinear terms—specifically 3rd and 4th-order derivatives—influence the stability of these oscillations in both GD and Stochastic Gradient Descent (SGD).
Methods and Framework
The authors employ several mathematical tools to move beyond simple quadratic approximations:
- Bifurcation Theory: The transition from convergence to oscillation is modeled as a "flip bifurcation." Analyzing the normal form of this bifurcation reveals whether oscillations are suppressed (stable) or explosive (unstable).
- Koopman Operator Theory: To handle the stochasticity of SGD, the authors use Koopman theory to map finite-dimensional nonlinear dynamics into an infinite-dimensional linear space, allowing for the analysis of iterate moments (like mean squared error).
The study utilizes synthetic analytic functions, such as univariate polynomials, to provide a proof-of-concept for how higher-order terms alter the stability landscape. These functions allow for explicit calculation of the higher-order derivatives that dictate the system's behavior beyond the Hessian.
Key Insights
The Cubic Correction in GD
Stability in GD is not merely a function of the Hessian's largest eigenvalue. The authors demonstrate that the third derivative (representing landscape asymmetry) can stabilize oscillations. Conversely, the fourth derivative can either stabilize or destabilize the system depending on its sign. This generalizes previous results that focused solely on the sharpest eigen-direction, showing that stability actually depends on an interaction across all eigen-directions.
SGD and the "Weakest Link" Rule
A counter-intuitive finding of this work is that SGD stability is not necessarily determined by average curvature. While linear analysis suggests that low average curvature ensures safety, the authors prove a "worst-case" rule: if even a single mini-batch causes superlinear divergence, the entire SGD process will diverge in expectation. This suggests that a single "unstable" batch can act as a weakest link, overriding the stabilizing effect of other batches.
Key Results
The paper provides several foundational theorems that formalize these nonlinear dynamics:
- Theorem 2 (GD Stability): Establishes the first exact multivariate condition for stable period-2 cycles, correcting previous incomplete hypotheses.
- Theorem 5 & 6 (SGD Dynamics): Proves that linear instability in a single batch leads to divergence in expectation, while linear stability across all batches guarantees the stability of the full nonlinear SGD process.
Limitations and Future Directions
The current analysis assumes "interpolating" minima, where the gradient of every mini-batch vanishes at the solution. While common in over-parameterized models, this does not account for label noise or under-parameterized settings. Furthermore, the focus on isolated minima leaves open the question of how these dynamics behave on the continuous manifolds of solutions often found in deep learning landscapes. Extending these nonlinear dynamics to manifolds is a key direction for future research.
Summary updated