Non-Euclidean Gradient Descent Has Many Edges of Stability

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 >