On the Stability Connection Between Discrete-Time Algorithms and Their Resolution ODEs: Applications to Min-Max Optimisation

This paper establishes a rigorous theoretical framework proving that exponential stability in $O(s^r)$-resolution ODEs implies exponential stability in their corresponding discrete-time algorithms under sufficiently small step sizes, and applies this connection to analyze the convergence properties of various min-max optimization methods while relaxing traditional Hessian invariance assumptions.

The Gist

Imagine you are trying to find the perfect spot to set up a campfire on a hillside. You want to be high enough to see the view (maximize) but low enough to stay warm (minimize). This is a Min-Max problem: two competing goals happening at the same time.

In the real world, we don't have a magic map. Instead, we use algorithms (step-by-step rules) to take small steps toward the perfect spot. These algorithms are like a hiker taking discrete steps: step, step, step.

However, analyzing whether these steps will actually lead to the campfire or get the hiker lost in a loop is very hard. It's like trying to predict the exact path of a bouncing ball by looking at every single frame of a video.

This paper introduces a clever trick: Stop looking at the steps; look at the flow.

The Big Idea: The "Smooth River" vs. The "Rocky Path"

The authors propose that instead of analyzing the hiker's jerky, step-by-step movements (the Discrete-Time Algorithm), we should imagine a smooth river flowing down the hill that the hiker is trying to follow (the Continuous-Time ODE).

• The Discrete Algorithm (DTA): This is the hiker taking big, clumsy steps. Sometimes they overshoot, sometimes they wobble. It's hard to predict if they will reach the goal or fall into a pit.
• The Resolution ODE: This is the smooth river. Water flows continuously. It's much easier to study the river's current to see where it naturally goes.

The paper's main discovery is a Stability Bridge. They prove that if the river (the smooth flow) is guaranteed to flow smoothly into the campfire (a stable equilibrium), then the hiker (the algorithm) will also find the campfire, provided the hiker takes small enough steps.

The "Resolution" Concept

The authors use a mathematical tool called an O(sr)-Resolution ODE. Think of this as a "high-definition" map of the river.

• O(1) Resolution: A rough sketch of the river. It tells you the general direction.
• O(s) Resolution: A detailed, GPS-level map that accounts for the hiker's specific stride length. It's more accurate.

The paper proves that if the river on this detailed map flows safely into the goal, the hiker will too.

Applying it to Min-Max Games

The authors tested this "River vs. Hiker" theory on several famous hiking strategies (algorithms) used in AI and economics:

1. Gradient Descent-Ascent (GDA): The basic hiker.
   • Finding: Sometimes this hiker gets stuck in a circle (a limit cycle) and never finds the fire. The "river" analysis shows why: the river itself swirls in a circle under certain conditions.
2. Extragradient (GEG) & Proximal Point (PPM): These are "smart hikers" who peek ahead before stepping.
   • Finding: The river analysis shows these hikers are much better. If they take small steps, the river guides them straight to the saddle point (the perfect campfire spot).
3. Newton Methods: These hikers use a telescope and a compass (second-order information) to know the exact shape of the hill.
   • Finding: They are very robust. Even if the hill is weirdly shaped, the river analysis proves they will find the spot, as long as the map isn't broken.

Why This Matters (The "No-Hessian" Superpower)

Usually, to prove a hiker won't get lost, mathematicians have to check the "Hessian" (a complex measure of how curved the hill is). If the hill is flat or weird at the goal, the old math says, "We can't prove anything!"

The paper's breakthrough: By looking at the smooth river directly using a tool called a Lyapunov function (think of it as a "height gauge" that always goes down as you get closer to the goal), they can prove the hiker will succeed even if the hill is weird or flat at the top. They don't need the Hessian to be perfect.

The Takeaway

This paper gives us a new, powerful lens to study optimization algorithms:

1. Don't just watch the steps. Model the continuous flow the steps are trying to follow.
2. If the flow is stable, the steps are stable. If the smooth river leads to the goal, the hiker will get there too, as long as they don't take giant, reckless leaps.
3. It works for tricky problems. This method works even when the "hill" is weird, helping us design better AI training methods and economic models.

In short: If you want to know if a robot will find its way, don't just watch its feet. Watch the wind blowing it, and if the wind blows it home, the robot will get there too.

Technical Summary

1. Problem Statement

The paper addresses the challenge of analyzing the convergence and stability of discrete-time algorithms (DTAs) used in min-max optimization problems (e.g., $\min_x \max_y f(x,y)$).

• The Difficulty: Direct analysis of discrete-time dynamics is often technically complex, particularly for non-convex–nonconcave problems where algorithms may fail to converge to local saddle points or exhibit spurious attractors (limit cycles).
• The Gap: While continuous-time dynamical systems (ODEs) are generally easier to analyze, there has been a lack of rigorous theoretical frameworks to guarantee that stability properties (specifically exponential stability) derived from a continuous-time approximation (Resolution ODE) strictly transfer back to the original discrete-time algorithm.
• Existing Limitations: Previous methods often rely on linearization around equilibria, requiring the Hessian to be invertible (non-degenerate) and the Jacobian to have no zero eigenvalues. This excludes many practical scenarios involving degenerate saddle points or stability of invariant sets rather than single points.

2. Methodology

The authors propose a rigorous framework connecting DTAs to their $O(s^r)$-resolution ODEs (continuous-time flows that approximate the discrete updates with error $O(s^r)$).

A. Theoretical Foundation: Stability Transfer

The core theoretical contribution is establishing a "stability-transfer principle" based on Lyapunov methods:

1. Closeness Assumption (Assumption 2.4): The paper assumes the discrete update $z_{k+1} = w_s(z_k)$ and the continuous flow $Z(t)$ satisfy a one-step consistency condition: $|Z(s; z_0) - z_1(z_0)| \le O(s^r)$ for $r \ge 2$.
2. Lyapunov Approach: Instead of linearizing the system (which requires non-degenerate Jacobians), the authors use converse Lyapunov theorems.
   • They show that if a continuous-time system has a locally exponentially stable equilibrium (or compact invariant set) with a Lyapunov function $V$, the same function (or a perturbed version) can prove exponential stability for the discrete-time system, provided the step size $s$ is sufficiently small.
3. Main Theorems:
   • Theorem 2.5: If a common equilibrium is exponentially stable for the continuous-time system, it is exponentially stable for the discrete-time system for small $s$.
   • Theorem 2.8: This result is extended to compact invariant sets, proving that asymptotic stability of a set in continuous time implies asymptotic stability of the set in discrete time.

B. Application to Min-Max Algorithms

The framework is applied to derive and analyze the $O(1)$-resolution (leading order) and $O(s)$-resolution (first-order correction) ODEs for several prominent algorithms:

• Two-Timescale Gradient Descent-Ascent (TT-GDA)
• Generalised Extragradient (GEG)
• Two-Timescale Proximal Point (TT-PPM)
• Damped Newton (DN)
• Regularised Damped Newton (RDN)
• Jacobian Method (JM)

The authors construct these ODEs using the recursive formulas from [26] (Theorem 3.2) and analyze the eigenvalues of the Jacobian of the resulting ODEs at saddle points.

3. Key Contributions

1. Rigorous Stability Bridge: The paper provides the first rigorous proof that exponential stability of a common equilibrium in an $O(s^r)$-resolution ODE implies exponential stability in the corresponding DTA, without requiring the step size to approach zero for the existence of stability (only for the magnitude of the region of attraction).
2. Relaxation of Hessian Invertibility: By analyzing the resolution ODEs directly via Lyapunov functions, the framework bypasses the standard assumption that the Hessian must be invertible at saddle points. This allows for the analysis of degenerate saddle points and stability of sets (e.g., a ball of saddle points).
3. Algorithm-Specific Analysis:
   • GEG, TT-PPM, DN, RDN: The authors prove that under proper hyperparameter selection, the set of saddle points is a subset of the exponentially stable equilibria for these algorithms.
   • TT-GDA & JM: The analysis highlights inherent limitations. For TT-GDA, saddle points are only stable if the eigenvalues of the Hessian are not purely imaginary. For the Jacobian Method, the authors show it can diverge even for strongly convex-strongly concave problems if eigenvalues are purely imaginary.
4. Handling Degenerate Cases: The paper demonstrates the framework's utility on functions with rank-deficient Hessians (e.g., $f(x,y) = x^2 - y^4$), showing convergence to saddle points where traditional linearization-based methods fail.

4. Key Results

• Stability Transfer: If an equilibrium is exponentially stable for the $O(s)$-resolution ODE, it is exponentially stable for the DTA for sufficiently small step sizes $s$.
• Algorithm Performance Summary:
  • GEG, TT-PPM, DN, RDN: Successfully converge to saddle points (saddle points are a subset of stable equilibria) under mild conditions.
  • TT-GDA: Fails to guarantee convergence to saddle points if the Hessian has purely imaginary eigenvalues (a common issue in bilinear problems).
  • Jacobian Method: Proven to have restrictive limitations; it may diverge for standard convex-concave problems.
• Set Stability: The framework successfully proves that algorithms converge to a compact set of saddle points (e.g., a ball of saddle points) even when individual points are not isolated or the Hessian is singular.

5. Significance

• Theoretical Insight: The work resolves a long-standing implicit assumption in optimization literature: that stability in continuous-time approximations automatically implies stability in discrete-time. The authors provide the necessary conditions and proofs for this transfer.
• Practical Tool: It offers a systematic methodology for algorithm designers. Instead of struggling with complex discrete-time Lyapunov analysis, one can derive the resolution ODE, analyze its stability (which is often more intuitive), and rigorously conclude the stability of the discrete algorithm.
• Broader Applicability: By removing the requirement for Hessian invertibility, the results apply to a wider class of non-convex–nonconcave problems, including those with degenerate saddle points, which are prevalent in modern machine learning (e.g., GANs, adversarial training).
• Future Direction: The authors suggest using this framework in reverse: designing a continuous-time flow with desired properties and deriving a corresponding discrete-time algorithm that inherits those stability guarantees.

In summary, this paper establishes a robust theoretical foundation for using continuous-time ODEs to analyze and certify the convergence of discrete-time min-max optimization algorithms, significantly broadening the scope of problems where convergence to saddle points can be guaranteed.