Understanding Gradient Descent on Edge of Stability in Deep Learning

Sanjeev Arora, Zhiyuan Li, Abhishek Panigrahi

Abstract

Deep learning experiments by Cohen et al. [2021] using deterministic Gradient Descent (GD) revealed an "Edge of Stability" (EoS) phase. In this phase, the learning rate (LR) and sharpness (the largest eigenvalue of the Hessian, $\lambda_1$) no longer behave according to traditional optimization theory. Instead, sharpness stabilizes around $2/\text{LR}$ and the loss oscillates across iterations while maintaining an overall downward trend. This paper provides a mathematical analysis of a new mechanism of implicit regularization in the EoS phase. We demonstrate that GD updates, driven by a non-smooth loss landscape, evolve along a deterministic flow on the manifold of minimum loss. Unlike previous results that rely on infinitesimal updates or gradient noise, this effect is proven for Normalized GD and GD with a square-root loss. Our theoretical results show that this flow provably minimizes $\lambda_1(\nabla^2 L)$, a finding corroborated by experimental studies on MNIST and CIFAR-10.

Introduction: The EoS Phenomenon

In classical optimization theory, the Descent Lemma provides a strict upper bound for the learning rate: to guarantee that the loss decreases at every step, the learning rate ($\eta$) must be less than $2/\lambda$, where $\lambda$ is the sharpness of the landscape. If the learning rate exceeds this threshold, the system is expected to diverge.

However, modern deep learning practice frequently violates this rule. Practitioners observe the Edge of Stability, where sharpness rises during training until it reaches the $2/\eta$ threshold and then hovers just above it. During this phase, the training loss begins to oscillate—increasing and decreasing across individual iterations—yet it continues to trend downward over long timescales. This paper provides the first formal mathematical explanation for why the optimizer remains stable and continues to improve despite these oscillations.

Theoretical Framework and Methodology

The research analyzes two specific mathematical settings that mirror the behavior of deep neural networks:

  1. Normalized Gradient Descent: Where the step size is adaptive based on the gradient magnitude ($\eta_t = \eta / \|\nabla L\|$).
  2. GD on a Square-Root Loss ($\sqrt{L}$): A setting that introduces specific non-smoothness near the manifold of minimum loss.

The authors employ a two-phase analysis to describe the trajectory of the optimizer:

  • Phase I (Convergence to the Manifold): The optimizer tracks standard Gradient Flow until it reaches the proximity of the "manifold of minima" (the set of parameters where loss is zero).
  • Phase II (The EoS Phase): Once near the manifold, the iterates enter the EoS regime. The authors prove that the iterates begin to align with the top eigenvector of the Hessian. This alignment allows for the derivation of a "limiting flow"—a deterministic differential equation that describes how the parameters move along the manifold to find flatter regions (lower sharpness) even while oscillating across it.

Key Insights: Implicit Regularization via Oscillation

The core contribution of this work is the discovery that the "instability" of EoS is a mechanism for implicit regularization.

  • Alignment as a Driver: During EoS, gradient updates are not chaotic; they align almost perfectly with the direction of maximum curvature. This alignment is what allows the optimizer to navigate the manifold effectively.
  • The Necessity of Finite Learning Rates: Most deep learning theory relies on "infinitesimal" learning rates (Gradient Flow). This paper demonstrates that the EoS effect requires a finite, relatively large learning rate to exist. Without the "instability" caused by exceeding the $2/\lambda$ threshold, the optimizer would not be pushed toward flatter minima.
  • Sharpness Reduction: The derived "limiting flow" provably minimizes the largest eigenvalue of the Hessian ($\lambda_1$). This explains why sharpness stops rising and eventually decreases during the EoS phase, leading to models that generalize better.

Empirical Validation

The theoretical results were tested using two primary benchmarks:

  • MNIST: Using a two-layer fully connected network, the researchers verified that the trajectory of actual Gradient Descent matched the predicted "limiting flow" with high precision.
  • CIFAR-10: The authors trained a VGG-16 model. To align the architecture with the smoothness requirements of the theory, they modified the model to use GeLU activations and average pooling instead of ReLU and max pooling.

Experimental results confirmed the "Stableness Bound": in the EoS phase, the average stableness over any two consecutive steps is at least 2, confirming that the loss must oscillate while still decreasing on average.

Limitations and Future Directions

While this paper provides a rigorous foundation for EoS, several areas remain for future exploration:

  • Local vs. Global Analysis: The current analysis is "local," focusing on behavior once the model is near the manifold of minimizers. The transition from early-stage training into EoS requires further study.
  • Standard Loss Functions: While Normalized GD and $\sqrt{L}$ are analyzed, standard GD on a typical loss $L$ is more complex and may require new insights into the specific geometry of deep learning landscapes.
  • Stochasticity: This work focuses on deterministic GD. Extending these proofs to Stochastic Gradient Descent (SGD), where noise interacts with the EoS phase, is a significant open challenge.

Summary updated

Abstract

Deep learning experiments by Cohen et al. [2021] using deterministic Gradient Descent (GD) revealed an Edge of Stability (EoS) phase when learning rate (LR) and sharpness (i.e., the largest eigenvalue of Hessian) no longer behave as in traditional optimization. Sharpness stabilizes around $2/$LR and loss goes up and down across iterations, yet still with an overall downward trend. The current paper mathematically analyzes a new mechanism of implicit regularization in the EoS phase, whereby GD updates due to non-smooth loss landscape turn out to evolve along some deterministic flow on the manifold of minimum loss. This is in contrast to many previous results about implicit bias either relying on infinitesimal updates or noise in gradient. Formally, for any smooth function $L$ with certain regularity condition, this effect is demonstrated for (1) Normalized GD, i.e., GD with a varying LR $\eta_t =\frac{\eta}{|| \nabla L(x(t)) ||}$ and loss $L$; (2) GD with constant LR and loss $\sqrt{L- \min_x L(x)}$. Both provably enter the Edge of Stability, with the associated flow on the manifold minimizing $\lambda_{1}(\nabla^2 L)$. The above theoretical results have been corroborated by an experimental study.
BibTeX
@misc{arora2022understanding,
  author = {Sanjeev Arora and Zhiyuan Li and Abhishek Panigrahi},
  title = {{Understanding Gradient Descent on Edge of Stability in Deep Learning}},
  year = {2022},
  eprint = {2205.09745},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2205.09745},
}
Figure