# Generalized Mirror Prox for Monotone Variational Inequalities: Universality and Inexact Oracle

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Jun 2018.

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

- [Nest Your Adaptive Algorithm for Parameter-Agnostic Nonconvex Minimax Optimization](https://mlsanity.com/paper/2206.00743/) (2022)
- [First-Order Methods for Convex Optimization](https://mlsanity.com/paper/2101.00935/) (2021)
- [A Fully Parameter-Free Second-Order Algorithm for Convex-Concave Minimax Problems](https://mlsanity.com/paper/2407.03571/) (2024)
- [Distributed Extra-gradient with Optimal Complexity and Communication Guarantees](https://mlsanity.com/paper/2308.09187/) (2023)

## Abstract (arXiv)

We introduce an inexact oracle model for variational inequalities (VI) with monotone operator, propose a numerical method which solves such VI's and analyze its convergence rate. As a particular case, we consider VI's with H"older-continuous operator and show that our algorithm is universal. This means that without knowing the H"older parameter nu and H"older constant Lnu it has the best possible complexity for this class of VI's, namely our algorithm has complexity Oleft( infnu∈[0,1]left(fracLnuvarepsilon right)^frac21+nuR2 right), where R is the size of the feasible set and varepsilon is the desired accuracy of the solution. We also consider the case of VI's with strongly monotone operator and generalize our method for VI's with inexact oracle and our universal method for this class of problems. Finally, we show, how our method can be applied to convex-concave saddle point problems with H"older-continuous partial subgradients.