Extragradient Method: $O(1/K)$ Last-Iterate Convergence for Monotone Variational Inequalities and Connections With Cocoercivity

Abstract

Extragradient method (EG) (Korpelevich, 1976) is one of the most popular methods for solving saddle point and variational inequalities problems (VIP). Despite its long history and significant attention in the optimization community, there remain important open questions about convergence of EG. In this paper, we resolve one of such questions and derive the first last-iterate $O(1/K)$ convergence rate for EG for monotone and Lipschitz VIP without any additional assumptions on the operator unlike the only known result of this type (Golowich et al., 2020) that relies on the Lipschitzness of the Jacobian of the operator. The rate is given in terms of reducing the squared norm of the operator. Moreover, we establish several results on the (non-)cocoercivity of the update operators of EG, Optimistic Gradient Method, and Hamiltonian Gradient Method, when the original operator is monotone and Lipschitz.

AISTATS 2022; 37 pages, 4 figures. Changes in v2: structure was changed, minor typos are fixed, several additional clarifications were added. Code: https://github.com/eduardgorbunov/extragradient_last_iterate_AISTATS_2022

References in corpus (5)

• Stochastic Hamiltonian Gradient Methods for Smooth Games
• Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with $\mathcal{O}(1/k^2)$ Rate on Squared Gradient Norm
• Potential Function-based Framework for Making the Gradients Small in Convex and Min-Max Optimization
• The Last-Iterate Convergence Rate of Optimistic Mirror Descent in Stochastic Variational Inequalities
• Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity

Cited by in corpus (2)

• Stochastic Extragradient: General Analysis and Improved Rates
• Semi-Anchored Multi-Step Gradient Descent Ascent Method for Structured Nonconvex-Nonconcave Composite Minimax Problems