Non-Euclidean Gradient Descent Has Many Edges of Stability

arXiv:2610.15223 · math.OC, cs.LG · Submitted 2026-10-10 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: I'm Tom.

Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.

Tom: Today's paper: "Non-Euclidean Gradient Descent Has Many Edges of Stability".

Jane: The gist The almost-everywhere sharp stability threshold of Euclidean gradient descent characterizes Hilbertian geometry, while non-Hilbertian norms allow for coexisting stable and unstable basins in an intermediate regime.

Tom: First, who's behind it and why it matters.

Title and authors: Tom: So we're looking at this paper today, "Non-Euclidean Gradient Descent Has Many Edges of Stability." The title itself suggests something interesting about how things behave when you move away from the usual Euclidean geometry in optimization.

Jane: Right, it sounds like it’s going to tell us that standard gradient descent isn't as straightforward as we think when we use different kinds of norms for our objectives. It’s about characterizing which norms are actually safe for convergence and where those stability boundaries lie.

Lu: The authors are Peter Zaika and Zakhar Shumaylov from the University of Cambridge, so they’re coming from a strong theoretical background in optimization and geometry, which is exactly what we expect here when we're talking about these deep stability thresholds.

Meng: From an engineering standpoint, I’m curious if this is just theoretical math or if it actually tells us how to deploy something better. Because right now, with all the non-Euclidean stuff they’re mentioning, deploying models reliably is a nightmare.

Lalam: I've seen the literature on stability thresholds before, and this paper seems to be tightening up the connection between the geometry of our optimization problem and whether we can actually get a stable solution out of it.

The paper's summary: Tom: Basically, they start by looking at the known guarantees for non-Euclidean gradient descent, which are weaker than what we see in standard Euclidean settings. They find that convergence holds for every initialization when the step size η is less than two over S, where S is this generalized sharpness measure <ref:2610.15223#pg1,convergence holds for every initialization when>.

Jane: That’s a key point—that threshold two over S—but they immediately highlight that for non-Hilbertian norms, the situation gets much more complicated because you can have coexisting stable and unstable basins in an intermediate regime <ref:2610.15223#pg1>.

Lu: The main contribution they make is showing that Hilbertian norms are actually the only ones where this two over S threshold is almost everywhere sharp for every positive-definite quadratic objective <ref:2610.15223#pg1,for every positive-definite quadratic objective>. That means inner-product norms are precisely the ones where we get that clean, predictable behavior we usually see in Euclidean geometry, as stated in their first result.

Meng: If it's only Hilbertian norms that give us that predictable almost everywhere sharpness, then it puts a serious constraint on the types of optimization problems we should even consider for training large models.

Lalam: The summary points out that for general norms, you have distinct attracting critical directions, and these can have different radial stability thresholds denoted as two over λi <ref:2610.15223#pg1>. So it’s not just one edge anymore; there can be several edges of stability coexisting at the same step size η.

The paper's improvements: Tom: The paper suggests that we need to look beyond just that first threshold, because they show that these different stability thresholds, two over λi, allow for open convergent and divergent basins to coexist at the same step size <ref:2610.15223#pg1>. That’s a big deal for understanding the dynamics.

Jane: Exactly—the coexisting basins mean the set of initializations that converge isn't necessarily nested in a simple way; you can have stable and unstable regions right next to each other depending on which critical direction you start from.

Lu: They also point out how this splitting happens by looking at the projection onto the Euclidean unit sphere, which is determined by Q on the unit sphere. This separates the dynamics into a radial component and a directional component defined by Q, leading to those different thresholds two over λi that we talked about earlier <ref:2610.15223#pg1>.

Meng: For deployment, knowing that there are multiple distinct stability thresholds means we might need more complex step-size scheduling than just picking one fixed value η. We’d have to dynamically adjust based on where the current direction is pointing relative to these various lambda values.

Lalam: They also provide a construction—an exact smooth two-edge example in dimension two—which shows that this splitting property isn't just abstract theory; it’s something concrete and robust, even under small perturbations.

Conclusion: Tom: So, to wrap up the main points of "Non-Euclidean Gradient Descent Has Many Edges of Stability," they prove that the almost everywhere sharpness phenomenon is a characterization of Hilbertian geometry, which means it’s only inner product norms that give us that clean threshold behavior.

Jane: And for non-Hilbertian norms, they show we can have these distinct stability thresholds two over λi where stable and unstable basins coexist at the same step size η <ref:2610.15223#pg1>. It means the convergence basin isn't always nested in a simple way anymore.

Lu: The paper solidifies that Hilbertian norms are exactly those where generalized sharpness retains the Euclidean almost everywhere sharpness property for every positive-definite quadratic, which is a structural characterization of inner product geometry.

Meng: From my side, it means if we're dealing with non-Hilbertian objectives in practice, we have to be very careful because a single step size might not guarantee convergence for every initialization across the whole space.

Lalam: The authors also show that the separation between selection and radial thresholds of these nearby critical directions tends to zero as the dimension p goes toward infinity, which is an interesting limit behavior.

Tom: So, we're left with this paper characterizing stability near critical directions and constraining the global convergence basin for every nonzero initialization, proving almost every initialization diverges throughout this interval strictly below two over mu H <ref:2610.15223#pg1>.

Jane: It’s a deep dive into how geometry dictates optimization behavior in a way that goes beyond just picking the right learning rate, showing how non-Euclidean settings allow for more complex dynamics.

Lu: The paper’s characterization of Hilbertian norms is significant because it gives us a clear geometric way to classify these norms based on their stability properties during gradient descent >

Peter Zaika, Zakhar Shumaylov

University of Cambridge

math.OC, cs.LG

Submitted: 2026-10-10

Updated: 2026-10-10

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 82/100

The gist: The gist The almost-everywhere sharp stability threshold of Euclidean gradient descent characterizes Hilbertian geometry, while non-Hilbertian norms allow for coexisting stable and unstable basins in

Key concepts

Hilbertian Geometry
This refers to a specific type of geometry defined by inner products. The paper shows that Euclidean gradient descent's sharp stability threshold is a defining feature of Hilbertian geometry. A norm is Hilbertian if it satisfies certain conditions related to the generalized Rayleigh quotient, which governs how well the norm approximates an inner product.
Generalized Sharpness (S)
This measures how 'sharp' the convergence behavior is for quadratic objectives under gradient descent. In Euclidean settings, this sharpness is almost everywhere stable. The paper uses this concept to distinguish Hilbertian norms from non-Hilbertian ones, showing that only Hilbertian norms maintain this property across all positive-definite quadratic functions.
Splitting of Stability Edges
This phenomenon occurs in non-Hilbertian settings where different critical directions have varying radial stability thresholds. Instead of a single boundary for convergence, distinct edges appear. These different thresholds arise because the dynamics separate into radial and directional components, each governed by different local maxima on the unit sphere.
Coexistence of Basins
This means that stable and unstable regions can exist simultaneously at a specific step size (like 2/SH). This happens when distinct attracting critical directions have different stability thresholds. The paper proves that for certain non-Hilbertian norms, this splitting allows for the coexistence of both convergent and divergent initializations.

Summary

The gist The almost-everywhere sharp stability threshold of Euclidean gradient descent characterizes Hilbertian geometry, while non-Hilbertian norms allow for coexisting stable and unstable basins in an intermediate regime.

Edge of Stability in Non-Euclidean Settings

For quadratic objectives under non-Euclidean gradient descent, the 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/µH<ref:2610.15223#pg5>. The behavior in the intermediate regime 2/S. The paper shows that Hilbertian norms are the only ones for which 2/S is an almost-everywhere sharp threshold for every positive-definite quadratic objective<ref:2610.15223#pg4>.

Characterization of Hilbertian Norms

The first result establishes a structural theorem stating that the almost-everywhere sharpness phenomenon over all quadratic objectives characterizes inner-product geometry<ref:2610.15223#pg5>. A norm is Hilbertian if and only if for every H ≻ 0, the generalized Rayleigh quotient RH(x) has no strict suboptimal local maxima on the unit sphere<ref:2610.15223#pg5>. This means that inner-product norms are exactly the norms for which generalized sharpness retains the Euclidean almost-everywhere sharpness property for every positive-definite quadratic<ref:2610.15223#pg5>. Every nonHilbertian norm admits a quadratic and a step size η > 2/SH for which an open set of initializations still converges<ref:2610.15223#pg5>.

Splitting of Stability Edges

The second result explains why the single edge splits, showing that distinct attracting critical directions can have different radial stability thresholds<ref:2610.15223#pg6>. The dynamics separate into a radial component and a directional component determined by Q on the Euclidean unit sphere<ref:2610.15223#pg6>. For a general norm, QS d-1 may have several strict local maxima with different critical values, producing several distinct stability thresholds 2/λi<ref:2610.15223#pg6>. This means that 2/SH is the first edge of stability, not necessarily the only edge<ref:2610.15223#pg7>.

Coexistence of Basins

The radial/projective decomposition shows that stable and unstable open basins may coexist at the same step size, meaning that 2/SH is the first edge of stability, not necessarily the only edge<ref:2610.15223#pg7>. Corollary 5 states that for every η > 2/SH, the projective fixed point [u⋆] is locally exponentially attracting<ref:2610.15223#pg7>. Corollary 6 explains exactly how a sharp almost-everywhere edge can fail by showing that suboptimal maxima are stable beyond 2/SH<ref:2610.15223#pg7>.

Robustness and Constructions

The paper provides constructions to demonstrate these properties, including an exact smooth two-edge example in dimension two<ref:2610.15223#pg8>. Proposition 9 shows that for every integer m ≥ 2, there exists a norm on R squared with Φ that is C∞ away from 0, has a positive-definite quadratic objective for which qH has at least m nondegenerate strict local maxima with pairwise distinct critical values<ref:2610.15223#pg8>. Furthermore, the robustness of these edges is shown to be preserved under sufficiently small admissible C2 perturbations<ref:2610.15223#pg9>.

Spectral Limit Behavior

In the spectral limit, as p → ∞ for finite even p-Schatten norms, the separation between the selection and radial thresholds of nearby critical directions tends to zero as p → ∞<ref:2610.15223#pg11>. This suggests that in spectral geometry, where rank is involved, these thresholds converge to 2/λ<ref:2610.15223#pg11>.

Conclusion on Stability

The analysis constrains the convergence basins as η varies but does not imply that the basins themselves are nested<ref:2610.15223#pg9>. The results characterize stability near nondegenerate critical directions and constrain the global convergence basin, but do not classify all projective dynamics in the intermediate regime<ref:2610.15223#pg9>. For every nonzero initialization, almost every initialization diverges throughout this interval strictly below 2/µH<ref:2610.15223#pg9>. This proves the almost-everywhere claim since finitely many lines have Lebesgue measure zero<ref:2610.15223#pg15>. Every minimum ray is invariant and satisfies zt+1 = (1 − ηµH)zt<ref:2610.15223#pg15>. This proves the almost-everywhere claim since finitely many lines have Lebesgue measure zero<ref:2610.15223#pg15>. The paper concludes by showing that the separation between the selection and radial thresholds of these nearby critical directions tends to zero as p → ∞<ref:2610.15223#pg23>.

How it works

: The analysis relies on relating non-Euclidean gradient descent to ordinary Euclidean gradient descent via linear conjugacy<ref:2610.15223#pg5>. This allows for a forward-invariant region of exponentially divergent directions beyond the generalized stability threshold<ref:2610.15223#pg5>.

  1. The first result characterizes Hilbertian norms by showing that the almost-everywhere condition completely characterizes the allowed norms, stating that a norm is Hilbertian if and only if for every H ≻ 0, every η > 2/SH, µRd (Bη) = 0<ref:2610.15223#pg5>.

  2. The second result explains the splitting of edges by showing that QS d-1 may have several strict local maxima with different critical values, producing several distinct stability thresholds 2/λi<ref:2610.15223#pg6>.

  3. Theorem 4 determines the step sizes at which nearby directions are attracted to u, and the rate at which iterates along u grow or decay<ref:2610.15223#pg7>. A nondegenerate global maximum upgrades the divergent line of Islamov et al. [7, Thm. 5.2] to an open divergent cone, while a nondegenerate suboptimal local maximum gives an open convergent cone for step sizes beyond 2/SH<ref:2610.15223#pg7>.

  4. Theorem 7 establishes the invariant divergence region Uη, which is forward-invariant and every nonzero initialization in ConeH(Eη) eventually diverges exponentially<ref:2610.15223#pg9>. This implies that every convergent trajectory must remain in the set where qH ≤ 2/η<ref:2610.15223#pg9>.

  5. The radial stability threshold of an invariant critical line is determined by 2/λ, and when u is a nondegenerate strict local maximum, this threshold lies strictly above its projective selection threshold, so an open attracting cone is radially contracting immediately below 2/λ and radially expanding immediately above it<ref:2610.15223#pg7>.

Key Findings

: The paper proves that the almost-everywhere sharp stability threshold of Euclidean gradient descent characterizes Hilbertian geometry<ref:2610.15223#pg5>.

  1. Hilbertian characterization Theorem 1 states that a norm is induced by an inner product if and only if for every H ≻ 0, the generalized Rayleigh quotient RH(x) has no strict suboptimal local maxima on the unit sphere<ref:2610.15223#pg5>.

  2. The paper demonstrates that for non-Hilbertian norms, open sets of convergent and divergent initializations can coexist at the same step size due to different radial stability thresholds 2/λi<ref:2610.15223#pg7>.

  3. Theorem 8 shows that when global minima are finite and nondegenerate, there exists an η∗ such that for every η∗ < η < 2/µH, almost every initialization diverges throughout this interval<ref:2610.15223#pg9>.

  4. The construction of an exact smooth two-edge example in dimension two demonstrates the robustness of these splitting properties under perturbations<ref:2610.15223#pg8>.

: The paper proves that the almost-everywhere sharp stability threshold of Euclidean gradient descent characterizes Hilbertian geometry and explores how non-Hilbertian norms allow for coexisting stable and unstable basins<ref:2610.15223#pg5>.

  1. The paper proves that the almost-everywhere sharp stability threshold of Euclidean gradient descent characterizes Hilbertian geometry, which is equivalent to inner-product geometry<ref:2610.15223#pg5>.

  2. The paper shows that in non-Euclidean settings, distinct attracting critical directions can have different radial stability thresholds, producing coexisting convergent and divergent basins<ref:2610.15223#pg7>.

  3. The global analysis constrains the convergence basins as η varies but does not imply that the basins themselves are nested<ref:2610.15223#pg9>.

  4. The paper provides constructions to demonstrate these properties, including an exact smooth two-edge example in dimension two<ref:2610.15223#pg8>.

: The paper proves that the almost-everywhere sharp stability threshold of Euclidean gradient descent characterizes Hilbertian geometry and explores how non-Hilbertian norms allow for coexisting stable and unstable basins<ref:2610.15223#pg5>.

  1. The paper proves that the almost-everywhere sharp stability threshold of Euclidean gradient descent characterizes Hilbertian geometry, which is equivalent to inner-product geometry<ref:2610.15223#pg5>.

Improvements for AI systems

  1. Improve optimization convergence guarantees by identifying Hilbertian norms; A norm is Hilbertian if∥x∥2 = x⊤P x for some P ≻ 0 characterizes norms where generalized sharpness retains the Euclidean almost-everywhere sharpness property for every positive-definite quadratic.

  2. Develop adaptive learning algorithms that can exploit coexisting stable and unstable basins by identifying open convergent and divergent basins to coexist when analyzing non-Hilbertian norms, as shown in Figure 2(b).

  3. Enhance model robustness by utilizing the structural theorem that shows distinct attracting critical directions can have different radial stability thresholds, producing coexisting convergent and divergent basins, allowing the system to distinguish between competing optimization paths.

  4. Design step-size scheduling for non-Euclidean gradient descent that leverages the identified thresholds, ensuring convergence when the next projective iterate exists and divergence when initializations fall into the high-Rayleigh domain Uη.

  5. Implement a mechanism for detecting the edge of stability by monitoring the growth of the top Hessian eigenvalue toward the stability scale 2/η, allowing for dynamic adjustment of learning rates based on this observation.

Related papers