Abstract
The monotone variational inequality is a central problem in mathematicalprogramming that unifies and generalizes many important settings such as smoothconvex optimization, two-player zero-sum games, convex-concave saddle pointproblems, etc. The extragradient algorithm by Korpelevich [1976] and theoptimistic gradient descent-ascent algorithm by Popov [1980] are arguably thetwo most classical and popular methods for solving monotone variationalinequalities. Despite their long histories, the following major problem remainsopen. What is the last-iterate convergence rate of the extragradient algorithmor the optimistic gradient descent-ascent algorithm for monotone and Lipschitzvariational inequalities with constraints? We resolve this open problem byshowing that both the extragradient algorithm and the optimistic gradientdescent-ascent algorithm have a tight $O\left(\frac{1}{\sqrt{T}}\right)$last-iterate convergence rate for arbitrary convex feasible sets, which matchesthe lower bound by Golowich et al. [2020a,b]. Our rate is measured in terms ofthe standard gap function. At the core of our results lies a non-standardperformance measure -- the tangent residual, which can be viewed as anadaptation of the norm of the operator that takes the local constraints intoaccount. We use the tangent residual (or a slight variation of the tangentresidual) as the the potential function in our analysis of the extragradientalgorithm (or the optimistic gradient descent-ascent algorithm) and prove thatit is non-increasing between two consecutive iterates.