English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

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.

Tight Last-Iterate Convergence of the Extragradient and the Optimistic  Gradient Descent-Ascent Algorithm for Constrained Monotone Variational  Inequalities