Non-Euclidean Gradient Descent Has Many Edges of Stability
Abstract
Recent observations that deep learning models train at the edge of stability have renewed interest in understanding stability properties of classical optimization algorithms. For quadratic objectives, standard gradient descent has a sharp stability threshold: it converges from every initialization when η<2/L, diverges from almost every initialization when η>2/L, and diverges from every nonzero initialization when η>2/μ. For non-Euclidean gradient descent, the corresponding known guarantees are weaker: convergence holds for every initialization when η<2/S, where S is the generalized sharpness, while every nonzero initialization diverges when η>2/μ. The behavior in the intermediate regime 2/S<η<2/μ is not fully characterized. We show that Hilbertian norms are the only ones for which 2/S is an almost-everywhere sharp threshold for every positive-definite quadratic objective. Using linear conjugacy between non-Euclidean and Euclidean gradient descent, we show that for general norms the intermediate regime can contain arbitrarily many edges of stability associated with distinct attracting directions. We identify a forward-invariant region of exponentially divergent directions beyond the generalized stability threshold. When the directions of minimum curvature are finite and nondegenerate, we prove that, sufficiently close to 2/μ from below, only their invariant directions remain convergent. We give smooth two-dimensional constructions with arbitrarily many distinct thresholds, arbitrarily large relative threshold separation and show these properties to be stable.
Related
- Local Algebraic Stability of Wasserstein Gradient Descent-Ascent and Mean Field Langevin Dynamics without Spectral Gap
- Sharp L2-stability and gradient stability hierarchies of the L2-Poincaré inequalities on Euclidean balls and Gaussian Poincaré inequality
- The Multiple Timescales of Gradient Descent on the Edge of Stability: A Perturbative Derivation of the Central Flow
- Every k-Quasi-Planar Graph Has Linearly Many Edges
- Broximal Gradient Descent: A Projection-Free Sister of Projected Gradient Descent
BibTeX
@misc{zaika2026noneuclidean,
title = {{Non-Euclidean Gradient Descent Has Many Edges of Stability}},
author = {Peter Zaika and Zakhar Shumaylov},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.15223},
eprint = {2610.15223},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.15223},
}
RIS
TY - UNPB
TI - Non-Euclidean Gradient Descent Has Many Edges of Stability
AU - Peter Zaika
AU - Zakhar Shumaylov
PY - 2026
DA - 2026/10/10
PB - arXiv
DO - 10.48550/arxiv.2610.15223
UR - https://arxiv.org/abs/2610.15223
AB - Recent observations that deep learning models train at the edge of stability have renewed interest in understanding stability properties of classical optimization algorithms. For quadratic objectives, standard gradient descent has a sharp stability threshold: it converges from every initialization when η<2/L, diverges from almost every initialization when η>2/L, and diverges from every nonzero initialization when η>2/μ. For non-Euclidean gradient descent, the corresponding known guarantees are weaker: convergence holds for every initialization when η<2/S, where S is the generalized sharpness, while every nonzero initialization diverges when η>2/μ. The behavior in the intermediate regime 2/S<η<2/μ is not fully characterized. We show that Hilbertian norms are the only ones for which 2/S is an almost-everywhere sharp threshold for every positive-definite quadratic objective. Using linear conjugacy between non-Euclidean and Euclidean gradient descent, we show that for general norms the intermediate regime can contain arbitrarily many edges of stability associated with distinct attracting directions. We identify a forward-invariant region of exponentially divergent directions beyond the generalized stability threshold. When the directions of minimum curvature are finite and nondegenerate, we prove that, sufficiently close to 2/μ from below, only their invariant directions remain convergent. We give smooth two-dimensional constructions with arbitrarily many distinct thresholds, arbitrarily large relative threshold separation and show these properties to be stable.
ER -