# On the Convergence Properties of Non-Euclidean Extragradient Methods for Variational Inequalities with Generalized Monotone Operators

arXiv: https://arxiv.org/abs/1311.2776 · HTML: https://mlsanity.com/paper/1311.2776/

## Key facts

- Cited by 29 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Nov 2013.

## Built on by (most cited first, 29 of 29)

- [Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classes](https://mlsanity.com/paper/2102.00135/) (2021)
- [Stochastic first-order methods for average-reward Markov decision processes](https://mlsanity.com/paper/2205.05800/) (2022)
- [Accelerated Single-Call Methods for Constrained Min-Max Optimization](https://mlsanity.com/paper/2210.03096/) (2022)
- [Decentralized Local Stochastic Extra-Gradient for Variational Inequalities](https://mlsanity.com/paper/2106.08315/) (2021)
- [Accelerated Algorithms for Constrained Nonconvex-Nonconcave Min-Max Optimization and Comonotone Inclusion](https://mlsanity.com/paper/2206.05248/) (2022)
- [Distributed Methods with Compressed Communication for Solving Variational Inequalities, with Theoretical Guarantees](https://mlsanity.com/paper/2110.03313/) (2021)
- [On the Convergence of No-Regret Learning Dynamics in Time-Varying Games](https://mlsanity.com/paper/2301.11241/) (2023)
- [Single-Call Stochastic Extragradient Methods for Structured Non-monotone Variational Inequalities: Improved Analysis under Weaker Conditions](https://mlsanity.com/paper/2302.14043/) (2023)
- [Universal Gradient Descent Ascent Method for Nonconvex-Nonconcave Minimax Optimization](https://mlsanity.com/paper/2212.12978/) (2022)
- [Efficient Algorithms for Empirical Group Distributionally Robust Optimization and Beyond](https://mlsanity.com/paper/2403.03562/) (2024)
- [Convergence Rates of Two-Time-Scale Gradient Descent-Ascent Dynamics for Solving Nonconvex Min-Max Problems](https://mlsanity.com/paper/2112.09579/) (2021)
- [A Decentralized Adaptive Momentum Method for Solving a Class of Min-Max Optimization Problems](https://mlsanity.com/paper/2106.06075/) (2021)
- [On the One-sided Convergence of Adam-type Algorithms in Non-convex Non-concave Min-max Optimization](https://mlsanity.com/paper/2109.14213/) (2021)
- [Nonconvex-Nonconcave Min-Max Optimization with a Small Maximization Domain](https://mlsanity.com/paper/2110.03950/) (2021)
- [Tight Analysis of Extra-gradient and Optimistic Gradient Methods For Nonconvex Minimax Problems](https://mlsanity.com/paper/2210.09382/) (2022)
- [Similarity, Compression and Local Steps: Three Pillars of Efficient Communications for Distributed Variational Inequalities](https://mlsanity.com/paper/2302.07615/) (2023)
- [Perseus: A Simple and Optimal High-Order Method for Variational Inequalities](https://mlsanity.com/paper/2205.03202/) (2022)
- [Sublinear Convergence Rates of Extragradient-Type Methods: A Survey on Classical and Recent Developments](https://mlsanity.com/paper/2303.17192/) (2023)
- [Min-Max Optimisation for Nonconvex-Nonconcave Functions Using a Random Zeroth-Order Extragradient Algorithm](https://mlsanity.com/paper/2504.07388/) (2025)
- [Revisiting Inexact Fixed-Point Iterations for Min-Max Problems: Stochasticity and Structured Nonconvexity](https://mlsanity.com/paper/2402.05071/) (2024)
- [Primal Methods for Variational Inequality Problems with Functional Constraints](https://mlsanity.com/paper/2403.12859/) (2024)
- [Multiscale replay: A robust algorithm for stochastic variational inequalities with a Markovian buffer](https://mlsanity.com/paper/2601.01502/) (2026)
- [Semi-Implicit Hybrid Gradient Methods with Application to Adversarial Robustness](https://mlsanity.com/paper/2202.10523/) (2022)
- [Non-KKT Accumulation in Entropic Mirror Descent](https://mlsanity.com/paper/2608.01658/) (2026)
- [Extragradient-Type Methods with O (1/k) Last-Iterate Convergence Rates for Co-Hypomonotone Inclusions](https://mlsanity.com/paper/2302.04099/) (2023)
- [First-order methods for Stochastic Variational Inequality problems with Function Constraints](https://mlsanity.com/paper/2304.04778/) (2023)
- [Non-Convex Sparse Reinforcement Learning via Non-Monotone Inclusions](https://mlsanity.com/paper/2607.04990/) (2026)
- [Establishing Boundary KKT Convergence of Mirror Descent through Reparameterization](https://mlsanity.com/paper/2608.07248/) (2026)
- [Polyak-Type Extragradient Methods for Monotone Root-Finding Problems](https://mlsanity.com/paper/2609.26581/) (2026)

## Abstract (arXiv)

In this paper, we study a class of generalized monotone variational inequality (GMVI) problems whose operators are not necessarily monotone (e.g., pseudo-monotone). We present non-Euclidean extragradient (N-EG) methods for computing approximate strong solutions of these problems, and demonstrate how their iteration complexities depend on the global Lipschitz or H"older continuity properties for their operators and the smoothness properties for the distance generating function used in the N-EG algorithms. We also introduce a variant of this algorithm by incorporating a simple line-search procedure to deal with problems with more general continuous operators. Numerical studies are conducted to illustrate the significant advantages of the developed algorithms over the existing ones for solving large-scale GMVI problems.