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

We introduce an inexact oracle model for variational inequalities with monotone operators, propose a numerical method that solves such variational inequalities, and analyze its convergence rate. As a particular case, we consider variational inequalities with Holder-continuous operator and show that our algorithm is universal. This means that, without knowing the Holder exponent and Holder constant, the algorithm has the least possible in the worst-case sense complexity for this class of variational inequalities. We also consider the case of variational inequalities with a strongly monotone operator and generalize the algorithm for variational inequalities 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 Holder-continuous partial subgradients.

Automated summary

We introduce an inexact oracle model for variational inequalities with monotone operators, propose a numerical method that solves such variational inequalities, and analyze its convergence rate. We also extend the algorithm to variational inequalities with strongly monotone operators and apply it to convex-concave saddle point problems with Holder-continuous partial subgradients.