Convergence Boundaries for Nonmonotone Variational Inequalities

23 concepts10 papers2 proposals

Min-max optimization and game-theoretic formulations power some of the most critical paradigms in modern artificial intelligence, from training Generative Adversarial Networks (GANs) to multi-agent reinforcement learning. Mathematically, these problems are often framed as Variational Inequalities (VIs), where the goal is to find a point where a multi-dimensional vector field (or operator) $F(x)$ settles into an equilibrium.

When this vector field is monotone—meaning the operators roughly point toward the optimal solution, analogous to convexity in standard optimization—classical algorithms like Extragradient (EG) and Optimistic Gradient Descent-Ascent (OGDA) perform exceptionally well. In fact, Antonakopoulos demonstrated that for monotone Lipschitz VIs, these algorithms can achieve last-iterate convergence rates that are strictly faster than the traditionally accepted $\Omega(1/\sqrt{T})$ worst-case lower bound.

However, real-world applications rarely satisfy this clean geometric assumption. As noted by Sedlmayer et al., operator monotonicity is frequently violated in practical settings like GAN training. In competitive environments like multi-player Markov games, Anagnostides et al. showed that even simple competitive scenarios break classical monotonicity constraints, leaving standard convergence guarantees inapplicable. When monotonicity fails, optimization algorithms frequently get trapped in rotational, non-convergent loops known as limit cycles.

Why Small Step Sizes Can't Save Us: Step-Size Independent Divergence

When an optimization algorithm begins to oscillate or diverge, a standard engineering instinct is to turn down the learning rate (the step size). In traditional minimization, a sufficiently small step size guarantees that you can safely slide down a continuous local gradient.

In non-monotone vector fields, however, this intuition completely breaks down. To understand why, consider the class of hypomonotone VIs, a generalization of monotonicity where the standard contractive condition is relaxed by a linear error term. Alomar and Chavdarova proved a striking negative result: the standard extragradient algorithm can completely diverge when applied to hypomonotone operators, irrespective of the chosen step size.

Monotone Field:                 Hypomonotone Field (Rotational/Divergent):
    ↓   ↓   ↓                       ↖   ↑   ↗
    → [x*] ←                        ← [x*]  →  (Updates spiral outward
    ↑   ↑   ↑                       ↙   ↓   ↘   regardless of step size)

This phenomenon occurs because non-monotonicity allows the vector field to actively twist away from the equilibrium point $x^*$. Shrinking the step size does not alter the geometric direction of the updates; it merely causes the algorithm to trace out this outward-spiraling, divergent trajectory more smoothly and slowly. This "step-size independent divergence" proves that navigating non-monotone landscapes requires fundamental algorithmic modifications rather than simple hyperparameter tuning.

Quantifying the Chaos: The Weak Minty Boundary

To establish convergence guarantees without strict monotonicity, researchers rely on a relaxed condition known as the Weak Minty Variational Inequality (MVI). Instead of requiring the operator to point toward the solution from every point in the space, the Weak MVI assumes that there exists at least one solution $x^*$ where the operator satisfies:

$$\langle F(x), x - x^* \rangle \ge \rho \|F(x)\|^2$$

Here, $\rho$ acts as a non-monotonicity parameter that measures how severely the vector field can push away from the solution.

  • When $\rho = 0$, the condition reduces to the classical Minty property. Under this condition, Nedich demonstrated that the extra-gradient method remains highly resilient and theoretically guarantees convergence to a valid solution given suitable step sizes.
  • When $\rho < 0$, the problem enters the non-monotone regime, allowing the field to point in a deceptive direction.

There is, however, a hard physical limit to how deceptive the field can be before tracking becomes impossible. As analyzed by Pethick et al., the threshold $\rho > -1/L$ (where $L$ is the Lipschitz constant of the operator) represents the fundamental theoretical boundary for convergence within this class of solvers. If a problem's non-monotonicity exceeds this limit ($\rho \le -1/L$), the repulsive forces of the landscape completely overpower the contractive steps of standard gradient methods, rendering convergence mathematically impossible without structural changes to the algorithm.

Pushing the Boundaries: Algorithmic Fixes

To operate safely near this theoretical $-1/L$ boundary without succumbing to divergence, recent literature focuses on expanding how algorithms gather local information and correct for non-monotone drift.

Multi-Step Exploration

Standard extragradient methods use a single "look-ahead" step to calculate a midpoint gradient, using that intermediate information to execute the actual update. Fan et al. demonstrated that expanding this look-ahead phase into a multi-step exploration phase significantly broadens the class of solvable non-monotone problems. By taking multiple exploratory steps to map the local curvature before committing to a trajectory, their method effectively dampens the deceptive rotational forces of the field, pushing the provable convergence boundary for the weak MVI parameter down to approximately $-0.632/L$.

Hybrid Error Correction

Rather than simply looking further ahead, one can explicitly correct for non-monotone drift using geometric projections. Pethick et al. introduced a hybrid algorithm that bridges the gap between extragradient and proximal methods. By utilizing an error-correction step based on halfspace projections, the algorithm dynamically ensures that updates do not get thrown off course by the non-monotone components of the operator. This approach achieves the optimal $O(1/\epsilon)$ convergence rate across the entire feasible weak MVI range ($\rho > -1/L$), removing the computational overhead that plagued prior state-of-the-art methods.

Scaling to Stochastic and Composite Landscapes

For these methods to be useful in large-scale machine learning, they must also accommodate noise and structural constraints:

  • Stochastic Single-Call Methods: Evaluating operators twice per step can be prohibitively expensive. Choudhury et al. analyzed single-call stochastic extragradient methods under the weak MVI framework. They proved that these methods can achieve an $O(1/K)$ convergence rate for non-monotone problems without needing restrictive "bounded variance" assumptions that typically fail in practice.
  • Operator Sliding: When dealing with composite operators (problems split into smooth non-monotone parts and non-smooth parts), Emelyanov et al. developed an "Extragradient Sliding" routine. This mechanism skips redundant evaluations of the complex non-monotone operator, accelerating convergence in practical applications.
  • Data Shuffling: In practice, practitioners process datasets by shuffling rather than random sampling. Medyakov et al. provided new convergence guarantees for shuffling-based extragradient methods, noting that while shuffling is highly effective, explicit variance reduction techniques remain necessary to converge exactly to an optimal equilibrium rather than just a surrounding neighborhood.

Key Foundational Work

On the Hypomonotone Class of Variational Inequalities (2024) — contributed 10 concept elements to this direction.
Non-Monotone Variational Inequalities (2024) — contributed 3 concept elements to this direction.
Weaker MVI Condition: Extragradient Methods with Multi-Step Exploration (2024) — contributed 2 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_step_size_independent_divergence_2a1e551b,
  title = {step-size independent divergence},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/step-size-independent-divergence/rdr_2a1e551bb7ee4e9bbe68109689df6102},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_step_size_independent_divergence_2a1e551b_v1,
  title = {step-size independent divergence},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/step-size-independent-divergence/rdr_2a1e551bb7ee4e9bbe68109689df6102/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake