Tight Last-Iterate Convergence of the Extragradient and the Optimistic Gradient Descent-Ascent Algorithm for Constrained Monotone Variational Inequalities. (arXiv:2204.09228v2 [math.OC] UPDATED)

Web: http://arxiv.org/abs/2204.09228

The monotone variational inequality is a central problem in mathematical
programming that unifies and generalizes many important settings such as smooth
convex optimization, two-player zero-sum games, convex-concave saddle point
problems, etc. The extragradient algorithm by Korpelevich [1976] and the
optimistic gradient descent-ascent algorithm by Popov [1980] are arguably the
two most classical and popular methods for solving monotone variational
inequalities. Despite its long history, the following major problem remains
open. What is the last-iterate convergence rate of the extragradient algorithm …

algorithm arxiv convergence gradient math