🔢 mathematics

State-Dependent Lyapunov Method for Rank-1 Matrix Factorization

This paper introduces a state-dependent Lyapunov framework to analyze gradient descent for rank-1 matrix factorization, demonstrating that parameterized quadratic certificates naturally arise from the dynamics' monotonicity structure to guarantee global convergence or drive trajectories toward a balanced manifold, with numerical evidence suggesting the method's broader applicability.

Original authors: Jaehong Moon

Published 2026-05-01

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Jaehong Moon

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a puzzle where you have to break a complex picture (a large matrix) into two simpler pieces (two smaller matrices) that, when multiplied back together, recreate the original picture. This is called matrix factorization.

The problem is that the landscape of possible solutions is like a vast, hilly terrain with many valleys. You want to find the deepest valley (the perfect solution), but you are navigating this terrain using a specific method called Gradient Descent. Think of Gradient Descent as a hiker who always takes a step downhill in the steepest direction.

Usually, if the hiker takes small, careful steps, they will eventually find the bottom of the valley. But what happens if the hiker takes large, bold steps? They might overshoot the valley, get stuck in a loop, or wander off into a dangerous cliff.

This paper introduces a new way to understand exactly where that hiker can go safely, even when taking big steps. Here is the breakdown using simple analogies:

1. The "Smart Bubble" (The Certificate)

The authors discovered a special tool they call a certificate. Imagine this certificate as a smart, shrinking bubble surrounding the hiker.

How it works: As the hiker moves, this bubble doesn't just sit there; it actively changes shape and shrinks.
The Rule: The hiker is guaranteed to stay inside this bubble. Because the bubble keeps getting smaller and tighter, it forces the hiker to move toward a specific destination.
The "State Parameter": The bubble has a dial on it called $\delta$ (delta). As the hiker moves forward, this dial turns up. The bubble gets tighter and tighter as the dial turns, acting like a guide rail that prevents the hiker from wandering off.

2. Two Different Scenarios

The paper looks at two different ways the hiker behaves depending on how big their steps are:

Scenario A: The "Certified" Zone (Safe Steps)
If the step size is within a certain safe range, the shrinking bubble works perfectly. It proves mathematically that the hiker will reach the global bottom of the valley (the perfect solution). The bubble acts like a funnel, squeezing out all the wrong paths until only the correct one remains.

Scenario B: The "Post-Critical" Zone (Big Steps)
If the hiker takes steps that are too big (but not too big to fall off a cliff), the bubble still works, but the destination changes. Instead of stopping at a single point, the hiker gets pushed onto a special balanced path.

The Metaphor: Imagine the hiker reaches a flat, circular track. They can't stop at a single point, but they start running in a perfect, rhythmic loop (a "period-2 orbit"). They don't crash; they just settle into a stable, predictable dance. The paper shows that even with big steps, the system doesn't go chaotic; it finds this stable loop.

3. Why This Bubble is Special (The "State-Dependent" Trick)

In the past, mathematicians tried to use a fixed map or a fixed bubble to guide the hiker. The authors explain why this fails:

The Problem: The terrain looks different depending on where you are. A map that works for the left side of the valley doesn't work for the right side. A fixed bubble is too rigid; it can't adapt to the hiker's changing location.
The Solution: The authors' bubble is state-dependent. It's like a chameleon bubble. It changes its shape and size based on exactly where the hiker is right now.
The Discovery: They didn't just guess this bubble exists. They built a set of logical rules (axioms) and proved that this specific chameleon bubble is the only one that fits the rules. It wasn't a lucky guess; it was the only mathematical structure that could possibly work.

4. The "Noise" Problem

In real-world problems, there is often "noise" (extra data that doesn't belong to the main picture).

The Challenge: Sometimes, the hiker gets distracted by this noise and wanders toward a fake valley that looks good but isn't the real solution.
The Fix: The authors showed that their shrinking bubble is smart enough to ignore the noise. Even if the hiker starts near the noise, the bubble squeezes them back toward the true signal. It proves that for almost every starting point, the hiker will ignore the fake valleys and find the real one.

5. What About the "Edge of Stability"?

There is a phenomenon in machine learning called "Edge of Stability," where algorithms take steps so big they almost lose control but then stabilize in a weird, oscillating pattern.

The Paper's Insight: The authors explain why this happens. When the steps are large, the "chameleon bubble" pushes the hiker onto that balanced track (the loop mentioned in Scenario B). They showed that this isn't a bug; it's a feature of the geometry. The system naturally settles into this rhythmic loop rather than exploding or crashing.

Summary

The paper is like a navigation manual for a hiker in a tricky, non-linear landscape.

It introduces a smart, shrinking bubble that guides the hiker.
It proves this bubble must exist based on the rules of the terrain (it's not a random guess).
It shows that even with large, risky steps, the hiker won't get lost; they will either find the perfect solution or settle into a stable, rhythmic loop.
It explains how to handle noise so the hiker doesn't get distracted by fake paths.

The authors also ran computer experiments to show that this theory works in practice, even in situations they couldn't fully prove with math yet, suggesting this "smart bubble" idea might be useful for many other types of complex problems.

1. Problem Statement

The paper investigates the convergence dynamics of Gradient Descent (GD) applied to the non-convex problem of Rank-1 Matrix Factorization. The objective is to minimize the reconstruction error:
$\min_{A \in \mathbb{R}^{n \times 1}, B \in \mathbb{R}^{m \times 1}} R(A, B) = \frac{1}{2} \|BA^\top - X\|_F^2$
where $X$ is a target matrix.

Key Challenges:

Non-Convexity: The problem has a continuum of global minimizers and a complex landscape.
Discrete Dynamics: While Gradient Flow (continuous time) preserves the "balance" invariant ( $B^\top B - A^\top A$ ), GD in discrete time does not. This makes analyzing convergence, especially with large step sizes (Edge-of-Stability regime), difficult.
Stationary Points: The set of stationary points includes not only global minimizers but also a continuum of non-minimizing saddle points (e.g., where $A=B=0$ but noise components are non-zero). Proving that GD avoids these non-minimizing sets is a major hurdle.

2. Methodology: State-Dependent Lyapunov Framework

The authors propose a novel certificate-based viewpoint rooted in a State-Dependent Lyapunov Framework. Instead of seeking a single fixed Lyapunov function (which is often impossible for non-convex problems with multiple minimizers), they introduce a parameterized family of quadratic certificates.

A. The Certificate Mechanism

The core object is a parameterized quadratic certificate $I(\delta; \cdot)$ , where $\delta$ is a state parameter that evolves along the trajectory.

Form: For scalar factorization, the certificate is defined as:
$I_{sc}(\delta; a, b) = \delta(a^2 + b^2) - \delta^2 ab + \delta^2 - 4$
Shrinking Level Sets: The key property is that for a trajectory starting inside a level set $\{I(\delta; \cdot) \leq 0\}$ , a single GD step with step size $\eta < \delta$ maps the next iterate strictly into the interior of the level set.
Monotone State Parameter: This "inward" movement forces the state parameter $\delta_t$ to increase monotonically ( $\delta_{t+1} > \delta_t$ ). The trajectory is trapped in a nested sequence of shrinking ellipses (level sets) indexed by $\delta_t$ .

B. Theoretical Framework

The paper formalizes this via structural axioms (A1–A7) for a state-dependent Lyapunov function:

Positive Definiteness & Nesting: Level sets shrink as $\delta$ increases.
Monotonicity: The certificate value decreases (or stays non-positive) after a GD step.
Uniqueness: Through local Lagrange analysis at stationary points, the authors prove that under these axioms, the quadratic form $P(\delta)$ is uniquely determined. This explains why the specific algebraic form of the certificate arises naturally from the dynamics rather than being an ad hoc construction.

3. Key Contributions

1. Convergence Proofs for Rank-1 Factorization

The authors prove that for almost every initialization within a "certified region" (defined by $I(\delta_{init}) \leq 0$ ):

Pre-Critical Regime ( $\eta < 1/\sigma$ ): The trajectory converges pointwise to a global minimizer.
- Mechanism: The monotonic increase of $\delta_t$ forces the trajectory to a limit $\delta^*$ . If $\delta^* < 2$ , the remainder terms in the recursion force the residual to zero.
- Handling Continuum: A critical technical contribution is ruling out convergence to the continuum of non-minimizing stationary points. The limiting certificate boundary restricts possible non-minimizing limits to a finite set. Combined with local instability analysis and a compact-covering argument, this excludes non-minimizing limits for almost all initializations.
Post-Critical Regime ( $1/\sigma < \eta < 2/\sigma$ ): The trajectory does not converge to a minimizer but collapses onto a terminal balanced manifold ( $A=B, \text{noise}=0$ ). On this manifold, the dynamics reduce to a 1D map that exhibits an attracting period-2 orbit (Edge-of-Stability phenomenon).

2. Extension to Rank-1 Approximation

The paper analyzes the case where $X = \text{diag}(1, \sigma)$ with $\sigma \in (0, 1)$ .

They derive a two-parameter certificate family $I(\delta, \xi; \cdot)$ to handle signal and noise blocks separately.
They provide numerical evidence suggesting the existence of a continuous admissible branch $\xi(\delta)$ , though a rigorous proof remains open.
Contrast: Unlike factorization, Rank-1 Approximation with large step sizes leads to divergence (norms grow unbounded), highlighting that the Edge-of-Stability behavior is specific to the factorization structure.

3. Generalization to Augmented Losses

The framework is shown to extend to quartic-augmented scalar losses $R(a,b) = \frac{1}{2}(ab-1)^2 + \mu(ab-1)^4$ . Numerical experiments confirm the certificate remains predictive for certain $\mu$ , suggesting the method's robustness beyond the exact quadratic loss.

4. Key Results

Theorem 1 (Scalar/Rank-1 Factorization): For $\eta \in (0, 1/\sigma)$ , if the initialization satisfies the certificate condition, GD converges to a global minimizer for almost every initialization.
Theorem 2 (Post-Critical Behavior): For $\eta \in (1/\sigma, 2/\sigma)$ , certified trajectories converge to the terminal balanced manifold and exhibit period-2 oscillations (Edge-of-Stability).
Theorem 3 (Rank-1 Approximation): Convergence is guaranteed only under stricter conditions involving a threshold $\delta_{th}$ . Crucially, for $\eta > 1$ , the approximation dynamics diverge, unlike the factorization case.
Uniqueness Theorem: The state-dependent quadratic certificate is the unique solution satisfying the structural axioms derived from the monotonicity of the dynamics.

5. Significance and Impact

Beyond Ad Hoc Proofs: The paper moves away from "guessing" Lyapunov functions. It provides a systematic axiomatic derivation showing that the certificate is a structural necessity of the gradient descent dynamics for this class of problems.
Resolving the Continuum Issue: It offers a rigorous mechanism to handle the continuum of non-minimizing stationary points, a common obstacle in low-rank matrix factorization analysis.
Edge-of-Stability (EoS) Explanation: It provides a geometric explanation for EoS phenomena, showing how trajectories are funneled onto a terminal manifold where they settle into stable cycles rather than diverging or converging to a fixed point.
Distinction between Factorization and Approximation: The work highlights a fundamental difference in the stability of GD for matrix factorization (bounded, structured dynamics) versus matrix approximation (potential divergence) when using large step sizes.
Numerical Validation: Extensive experiments validate the theoretical bounds, showing the certificates are tight for small noise and predicting the transition to period-2 orbits and divergence.

In summary, this paper establishes a powerful State-Dependent Lyapunov Method that unifies the analysis of convergence, stability, and Edge-of-Stability phenomena in rank-1 matrix factorization, providing both rigorous proofs and deep geometric insights into the behavior of Gradient Descent.