# An Approximation-Based Regularized Extra-Gradient Method for Monotone Variational Inequalities

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Oct 2022.

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

- [Second-Order Min-Max Optimization with Lazy Hessians](https://mlsanity.com/paper/2410.09568/) (2024)
- [A Fully Parameter-Free Second-Order Algorithm for Convex-Concave Minimax Problems](https://mlsanity.com/paper/2407.03571/) (2024)
- [Halpern Iteration Achieves tildeO(ε-1/p) pth-Order Oracle Complexity for Monotone Variational Inequalities](https://mlsanity.com/paper/2608.08463/) (2026)
- [Gradient Norm Regularization Second-Order Algorithms for Solving Nonconvex-Strongly Concave Minimax Problems](https://mlsanity.com/paper/2411.15769/) (2024)
- [Solving Convex-Concave Problems with tildeO(ε-4/7) Second-Order Oracle Complexity](https://mlsanity.com/paper/2506.08362/) (2025)
- [Optimal High-Order Methods for Solving Monotone Variational Inequalities](https://mlsanity.com/paper/2609.23557/) (2026)

## Abstract (arXiv)

In this paper, we propose a general extra-gradient scheme for solving monotone variational inequalities (VI), referred to here as Approximation-based Regularized Extra-gradient method (ARE). The first step of ARE solves a VI subproblem with an approximation operator satisfying a pth-order Lipschitz bound with respect to the original mapping, further coupled with the gradient of a (p+1)th-order regularization. The optimal global convergence is guaranteed by including an additional extra-gradient step, while a pth-order superlinear local convergence is shown to hold if the VI is strongly monotone. The proposed ARE is inclusive and general, in the sense that a variety of solution methods can be formulated within this framework as different manifestations of approximations, and their iteration complexities would follow through in a unified fashion. The ARE framework relates to the first-order methods, while opening up possibilities to developing higher-order methods specifically for structured problems that guarantee the optimal iteration complexity bounds.