Mirror Descent-Type Algorithms for the Variational Inequality Problem with Functional Constraints

Mohammad S. Alkousa; Fedor S. Stonyakin; Belal A. Alashqar; Seydamet S. Ablaev

cs.LGFeb 24, 2026

Mirror Descent-Type Algorithms for the Variational Inequality Problem with Functional Constraints

Authors: Mohammad S. Alkousa, Fedor S. Stonyakin, Belal A. Alashqar, Seydamet S. Ablaev

Organizations: Innopolis University, Innopolis, Universitetskaya Str., 1, 420500, Russia. · Moscow Institute of Physics and Technology, 9 Institutsky lane, Dolgoprudny, 141701, Russia. · V. I. Vernadsky Crimean Federal University, 4 Academician Vernadsky Avenue, Simferopol, 295007, Republic of Crimea, Russia.

Abstract

Variational inequalities play a key role in machine learning research, such as generative adversarial networks, reinforcement learning, adversarial training, and generative models. This paper is devoted to the constrained variational inequality problems with functional constraints (inequality-type constraints). We propose some mirror descent-type algorithms that switch between productive and non-productive steps depending on the values of the functional constraints at iterations, with many different step size rules and stopping criteria. We analyze the proposed algorithms and prove their optimal convergence rate to achieve a solution with desired accuracy, for problems with bounded and monotone operators and Lipschitz convex functional constraints. In addition, we propose a modification of the proposed algorithms by considering each functional constraint in the calculation when we have a productive step, as well as the first constraint that violates the feasibility. This modification can save the running time of algorithms when we have many functional constraints. In addition, we provide an analysis of the proposed algorithms for $δ$ -monotone operators, allowing us to apply the proposed algorithms, as a special case, to constrained minimization problems when we do not have access to the exact information about the subgradient of the objective function. Numerical experiments that illustrate the work and performance of the proposed algorithms are also given.

Figures & tables

\text{Stopping criterion 1:}\quad R^{2}\leq\frac{\varepsilon^{2}|I|}{2L_{F}^{2}}+\frac{\varepsilon^{2}|J|}{2M_{g}^{2}}-\frac{\varepsilon D|J|}{M_{g}},

(13)

Algorithm 1 Non-Adaptive Mirror Descent for VIs with functional constraints.

\text{Stopping criterion 1:}\quad R^{2}\leq\frac{\varepsilon^{2}}{2}\sum_{i=0}^{k-1}\frac{1}{M_{i}^{2}}-M_{g}D\varepsilon\sum_{i\in J}\frac{1}{\|\nabla g(x_{i})\|_{*}^{2}},

(15)

Algorithm 2 Adaptive Mirror Descent for VIs with functional constraints.

	$g(x_{k})\leq$	$h_{k}^{F}=$	$h_{k}^{g}=$	Stopping criterion 1	Stopping criterion 2
Algorithm 3	$\varepsilon M_{g}$	$\frac{\varepsilon}{\\|F(x_{k})\\|_{*}^{2}}$	$\frac{\varepsilon}{M_{g}}$	$R^{2}\leq\frac{\varepsilon^{2}}{2}\sum\limits_{i\in I}\frac{1}{\\|F(x_{i})\\|_{*}^{2}}+\frac{\varepsilon^{2}}{2}\|J\|-\varepsilon D\|J\|$	$R^{2}\leq\frac{\varepsilon^{2}}{2}\sum\limits_{i\in I}\frac{1}{\\|F(x_{i})\\|_{*}^{2}}+\frac{\varepsilon^{2}}{2}\|J\|$
Algorithm 4	$\varepsilon$	$\frac{\varepsilon}{\\|F(x_{k})\\|_{*}}$	$\frac{\varepsilon}{\left\\|\nabla g(x_{k})\right\\|_{*}^{2}}$	$R^{2}\leq\frac{\varepsilon^{2}}{2}\|I\|+\left(\frac{\varepsilon^{2}}{2}-\varepsilon M_{g}D\right)\sum\limits_{i\in J}\frac{1}{\\|\nabla g(x_{i})\\|_{*}^{2}}$	$R^{2}\leq\frac{\varepsilon^{2}}{2}\left(\|I\|+\sum\limits_{i\in J}\frac{1}{\\|\nabla g(x_{i})\\|_{*}^{2}}\right)$
Algorithm 5	$\varepsilon M_{g}$	$\frac{\varepsilon}{\left\\|F(x_{k})\right\\|_{*}}$	$\frac{\varepsilon}{M_{g}}$	$R^{2}\leq\frac{\varepsilon^{2}}{2}\left(\|I\|+\|J\|\right)-\varepsilon D\|J\|$	$R^{2}\leq\frac{\varepsilon^{2}}{2}\left(\|I\|+\|J\|\right)$
Algorithm 6	$\varepsilon$	$\frac{\varepsilon}{M_{g}\left\\|F(x_{k})\right\\|_{*}}$	$\frac{\varepsilon}{M_{g}^{2}}$	$R^{2}\leq\frac{\varepsilon^{2}}{2M_{g}^{2}}\left(\|I\|+\|J\|\right)-\frac{\varepsilon D\|J\|}{M_{g}}$	$R^{2}\leq\frac{\varepsilon^{2}}{2M_{g}^{2}}\left(\|I\|+\|J\|\right)$
Algorithm 7	$\varepsilon$	$\theta\left(\sum\limits_{t=0}^{k}M_{t}^{2}\right)^{-1/2}$ , $M_{t}=\\|F(x_{t})\\|_{*}$	$\theta\left(\sum\limits_{t=0}^{k}M_{t}^{2}\right)^{-1/2}$ , $M_{t}=\\|\nabla g(x_{t})\\|_{*}$	$k\geq\frac{2\theta}{\varepsilon}\left(\sum\limits_{t=0}^{k}M_{t}^{2}\right)^{-1/2}+\frac{\|J\|M_{g}D}{\varepsilon}$	$k\geq\frac{2\theta}{\varepsilon}\left(\sum\limits_{t=0}^{k}M_{t}^{2}\right)^{-1/2}$

Table 1: The proposed Algorithms 3 – 7. Mirror Descent Algorithms for VIs with functional constraints.

\text{Stopping criterion 1:}\quad R^{2}\leq\frac{\varepsilon^{2}}{2}\sum_{i=0}^{k-1}\frac{1}{M_{i}^{2}}-M_{g}D\varepsilon\sum_{i\in J}\frac{1}{\|\nabla{\color[rgb]{0,0,0}g_{N(i)}}(x_{i})\|_{*}^{2}},

(38)

Algorithm 8 Modification of Algorithm 2 with many functional constraints.

Panel of Figure 1 — Figure 1: The results of Algorithms 1 —7 (with first stopping criterion), for Example 4 with $n=100,m=10$ , $\varepsilon=0.05$ (left), and $\varepsilon=0.01$ (right).

	Alg. 1	Alg. 2	Alg. 3	Alg. 4	Alg. 5	Alg. 6	Alg. 7
	$\varepsilon=0.05$
Iters.	129005	161	80	3542	3360	133169	604
Time	18.717003	0.021646	0.016614	0.748257	0.517956	37.257767	0.161242
Estim.	0.05	0.05	0.05	0.306	0.306	0.0492	0.05
	$\varepsilon=0.01$
Iters.	3232248	2398	712	86713	85600	3336676	3020

Table 2: The results of Algorithms 1 —7 (with first stopping criterion), for Example 4 with

L_{F}\approx 6.125326,M_{g}\approx 6.22351,n=100,m=10

\varepsilon=0.05,0.01

. In this table, Iters. denotes the number of iterations of each algorithm, Time denotes the running time of each algorithm in seconds, and Estim. denotes the theoretical estimate of an achieved solution by each algorithm.

Figure 2: Results of Algorithms 2 —6, for the forsaken game with different initial points, with

\varepsilon=0.001

and by

10^{4}

iterations of each algorithm, except Algorithm 6 with

10^{5}

iterations.

Explore similar work

Improving the Last-Iterate Guarantees of Anytime Algorithms for Stochastic Monotone Variational Inequalities
Sep 14, 2026Jun-Hyun Kim, Ahmet AlacaogluLast-Iterate Convergence Stochastic Approximation
University of British Columbia, Vancouver. · Department of Mathematics, University of British Columbia, Vancouver.
Parameter-Free Non-Ergodic Extragradient Algorithms for Solving Monotone Variational Inequalities
Apr 9, 2026Lingqing Shen, Fatma Kılınç-KarzanLast-Iterate Convergence Gradient Descent
Tepper School of Business, Carnegie Mellon University
Adaptive Delayed-Update Cyclic Algorithm for Variational Inequalities
Mar 31, 2026Yi Wei, Xufeng Cai, Jelena Diakonikolas
Paul G. Allen School of Computer Science and Engineering, University of Washington, Seattle, WA · Department of Computer Sciences, University of Wisconsin–Madison, Madison, WI

Sep 14, 2026J/K move · Enter open · S save

Improving the Last-Iterate Guarantees of Anytime Algorithms for Stochastic Monotone Variational Inequalities

Jun-Hyun Kim, Ahmet Alacaoglu

University of British Columbia, Vancouver. · Department of Mathematics, University of British Columbia, Vancouver.

Last-Iterate Convergence Stochastic Approximation

Open paper AskPDF arXiv

We analyze a stochastic algorithm with Halpern-type anchoring for constrained convex-concave problems and monotone variational inequalities. This single-loop and single-call algorithm uses one unbiased sample of the gradient operator at every iteration, to be applicable to monotone games with noisy feedback. With

t

denoting the iteration counter, we prove an anytime last-iterate convergence rate of

O(t^{-1/4})

for both the gradient-mapping norm and restricted gap, bypassing the

O(t^{-1/5})

constrained-anytime bottleneck in the literature. Specializing then to multi-point oracles, we use variance reduction to achieve the

O(t^{-1/2})

rate with an anytime single-loop algorithm using

2

samples per iteration. Our results allow constrained problems with a potentially unbounded feasible set; as well as a structured class of stochastic oracles whose variance need not be uniformly bounded.

Abstract

Explore similar work

Improving the Last-Iterate Guarantees of Anytime Algorithms for Stochastic Monotone Variational Inequalities

Parameter-Free Non-Ergodic Extragradient Algorithms for Solving Monotone Variational Inequalities

Adaptive Delayed-Update Cyclic Algorithm for Variational Inequalities