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 $\eta<2/L$, diverges from almost every initialization when $\eta>2/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 $\eta<2/S$, where $S$ is the generalized sharpness, while every nonzero initialization diverges when $\eta>2/\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.