⚡ electrical engineering

Extragradient methods with complexity guarantees for hierarchical variational inequalities

This paper proposes extragradient methods for solving a general class of hierarchical variational inequality problems in real Hilbert spaces, establishing convergence rates, worst-case iteration complexity, and weak convergence under geometric conditions that improve upon existing state-of-the-art results.

Original authors: Pavel Dvurechensky, Meggie Marschner, Shimrit Shtern, Mathias Staudigl

Published 2026-01-27

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Pavel Dvurechensky, Meggie Marschner, Shimrit Shtern, Mathias Staudigl

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 massive, multi-layered puzzle where the rules of the game change depending on how well you've solved the previous layer. This is the essence of the problem tackled in this paper: Hierarchical Variational Inequalities.

Here is a simple breakdown of what the authors did, using everyday analogies.

The Problem: A Game Within a Game

Think of the problem as a two-story building:

The Ground Floor (Lower Level): This is a crowded room where many people (players) are trying to find a comfortable spot. They are all reacting to each other. If one person moves, everyone else has to adjust. The goal here is to find a "stable state" where no one wants to move anymore. In math terms, this is finding a solution to a complex equilibrium problem.
The Second Floor (Upper Level): Once the people on the ground floor settle down, a new set of rules applies. A manager (or a second group of players) wants to make a decision that is "best" for them, but they can only choose from the stable spots the ground-floor people have already agreed upon.

The Challenge: You can't just solve the top floor first because the top floor depends on the bottom floor. And you can't just solve the bottom floor perfectly and then move up, because the "best" spot on the bottom floor might change slightly once the top floor starts making demands. It's a chicken-and-egg situation.

The Solution: The "Optimistic" Walker

The authors propose a new way to walk through this building to find the perfect spot. They call their method the Optimistic Extragradient Method.

Imagine you are walking through a dark, foggy maze (the mathematical problem).

The Old Way (Standard Extragradient): To take a step, you would peek ahead, take a tentative step, look again, realize you might have peeked wrong, and then take a second, corrected step. This requires you to "look" (calculate) twice for every single step you take. It's safe, but slow and tiring.
The New Way (Optimistic Extragradient): The authors' method is like a confident walker who trusts their momentum. They peek ahead, take a step, and then use the previous look to correct their path immediately. They only need to "look" (calculate) once per step.

Why is this a big deal?
The paper claims that by using this "optimistic" approach, they can solve these complex two-story problems faster and with fewer calculations than previous methods, while still guaranteeing they will eventually find the right answer.

The Guarantees: How Fast Will We Get There?

The authors didn't just say "it works"; they put a stopwatch on it. They proved exactly how fast the solution improves as you take more steps.

Feasibility Gap (Are we on the ground floor?): They measured how close the walker is to the "stable zone" of the lower level. They proved that with every step, the walker gets closer to the ground floor at a predictable speed.
Optimality Gap (Are we on the best spot on the second floor?): They also measured how close the walker is to the ultimate "best" solution.

They found that if the "ground floor" has a specific geometric shape (which they call "weak sharpness"—imagine the floor has a gentle slope leading to a valley rather than being a flat, endless plain), the walker finds the solution even faster.

What Makes This Paper Special?

It's More General: Previous methods only worked if the "rooms" were small and finite (like a small office). This new method works even if the rooms are huge, infinite, or have weird, bumpy walls (non-smooth functions). It handles a much wider variety of real-world problems.
It's Efficient: By cutting the number of "looks" (calculations) in half per step, it saves a massive amount of computing power.
No "Compactness" Assumption: Old methods required the problem to be bounded (like a box). This new method works even if the problem space is unbounded (like an open field), which is a significant mathematical leap.

Real-World Examples Mentioned

The paper doesn't just stay in theory; it shows how this applies to:

Game Theory: Finding the best strategy in a game where players have a hierarchy (e.g., a leader and followers).
Optimization: Solving problems where you want to minimize cost, but your choices are limited by the equilibrium of another system.
Signal Processing & Control: Fixing signals or controlling systems where constraints are nested inside other constraints.

The Bottom Line

This paper introduces a smarter, faster, and more flexible way to solve "nested" decision-making problems. It's like upgrading from a slow, double-checking GPS to a high-speed, single-check navigation system that works even in the most complex, unbounded terrains. The authors proved mathematically that this new system gets you to your destination efficiently, no matter how complicated the map is.

Technical Summary: Extragradient Methods with Complexity Guarantees for Hierarchical Variational Inequalities

Problem Formulation
The paper addresses the problem of solving hierarchical equilibrium problems within a real separable Hilbert space $Z$ . The core objective is to find a solution $z^*$ to a hemi-variational inequality (HVI) defined over the solution set of another HVI. Formally, the problem (P) is to find $z^* \in S_2$ such that:
$\langle F_1(z^*), z - z^* \rangle + \ell_1(z) - \ell_1(z^*) \geq 0 \quad \forall z \in S_2$
where $S_2 = \text{zer}(F_2 + \partial \ell_2)$ is the solution set of the lower-level HVI. Here, $F_1, F_2$ are monotone operators, and $\ell_1, \ell_2$ are proper, convex, and lower-semicontinuous functions.

This formulation unifies several problem classes, including:

Simple bilevel optimization (where $\ell_1, \ell_2$ are smooth or composite).
Nested variational inequalities (where $\ell_1=0$ and $\ell_2$ is an indicator function).
Hierarchical jointly convex generalized Nash equilibrium problems (GNEPs).
Optimal control under VI constraints.

Methodology
The authors propose an Optimistic Extragradient Method (Algorithm 1) based on Tikhonov regularization. Unlike previous approaches that require double operator evaluations per iteration (e.g., standard extragradient), this method utilizes a "past" operator evaluation to reduce computational cost to a single operator evaluation per iteration.

The algorithm constructs a sequence of regularized operators $V_k = F_2 + \sigma_k F_1$ and regularized functions $G_k = \ell_2 + \sigma_k \ell_1$ , where $(\sigma_k)$ is a decreasing regularization sequence converging to zero. The iteration scheme is:

Prediction: $z_{k+1/2} = \text{prox}_{t_k G_k}(z_k - t_k (F_2(z_{k-1/2}) + \sigma_k F_1(z_{k-1/2})))$
Correction: $z_{k+1} = \text{prox}_{t_k G_k}(z_k - t_k (F_2(z_{k+1/2}) + \sigma_k F_1(z_{k+1/2})))$

The analysis relies on specific geometric assumptions:

Weak Sharpness: The lower-level solution set $S_2$ is assumed to satisfy an $(\alpha, \rho)$ -weak sharpness condition, linking the gap function to the distance from the solution set.
Attouch-Czarnecki Condition: A summability condition on the step sizes and regularization parameters is imposed to ensure boundedness of the iterates.
Hierarchical Coherence: A condition ensuring the domain of the upper-level function is contained within the lower-level domain.

Key Contributions

General Problem Formulation: The paper extends existing literature (specifically [1, 57]) by handling general convex composite terms $\ell_1, \ell_2$ in potentially infinite-dimensional Hilbert spaces, rather than restricting to finite dimensions with indicator functions over compact sets.
Algorithmic Efficiency: The proposed method requires only one evaluation of the operators $F_1, F_2$ per iteration, improving upon the double-call extragradient methods used in prior works.
Complexity Guarantees: The authors establish worst-case iteration complexity rates for both the feasibility gap (lower-level) and the optimality gap (hierarchical problem) using suitably constructed ergodic averages.
Removal of Compactness Assumption: Unlike previous complexity analyses that required compact domains, this work derives convergence rates without assuming the domains of the variational inequalities are compact, relying instead on geometric weak sharpness and asymptotic analysis techniques.

Main Results
The paper establishes sublinear convergence rates for the ergodic average $\bar{z}_K$ generated by the algorithm. Assuming a regularization sequence $\sigma_k = O(k^{-\delta})$ with $\delta \in (0,1)$ :

Feasibility Gap: The gap function for the lower-level problem converges at a rate of $O(k^{-\delta})$ .
Optimality Gap: The gap function for the entire hierarchical problem converges at a rate of $O(k^{-(1-\delta)})$ .
Improved Rates: Under the assumption that the upper-level operator $F_1$ is strongly monotone, the paper derives improved rates, showing convergence to a unique solution.
Weak Convergence: Under the geometric weak sharpness condition, the sequence of iterates is shown to converge weakly to a solution in $S_1$ .

Significance and Claims
The authors claim that their results match and improve upon the state of the art in terms of iteration complexity and the generality of the problem formulation. Specifically, the paper:

Extends complexity guarantees from simple bilevel optimization and specific VI cases to a broad class of hierarchical HVI problems in infinite-dimensional spaces.
Demonstrates that the "weak sharpness" condition, previously used primarily in hierarchical optimization, can be effectively translated to the variational setting to establish unified complexity statements.
Provides a methodological framework using non-autonomous evolution equation analysis techniques to handle unbounded domains, a contribution the authors suggest may be useful for other hierarchical equilibrium problems.

The paper concludes by noting that while the current analysis covers deterministic settings, future work could explore stochastic formulations and accelerated methods. Numerical experiments on hierarchical Nash equilibria and constrained min-max problems (including Generalized Absolute Value Equations) are presented to validate the theoretical findings.