Non-Euclidean Gradient Descent Has Many Edges of Stability

arXiv:2610.15223v1 Announce Type: cross 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 eta2/L, and diverges from every nonzero initialization when eta>2/mu. For non-Euclidean gradient descent, the corresponding known guarantees are weaker: convergence holds for every initialization when eta2/mu. The behavior in the intermediate regime 2/S<eta<2/mu 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/mu 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.

Source: arXiv cs.LG | 2026-10-14