mlsanityData to 7 Oct 2026

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

arXiv 2110.04261 ↗First posted 8 Oct 2021math.OC cs.LGcited by 39

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 39 papers in the map (data through 7 Oct 2026). Builds on 31 of its 76 references that are in the map. First posted on arXiv 8 Oct 2021.

Builds on

31 of 76 references.

References · 31

  1. 2014Explaining and Harnessing Adversarial Examplescited by 7,287
  2. 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,326
  3. 2016CVXPY: A Python-Embedded Modeling Language for Convex Optimizationcited by 633
  4. 2019A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approachcited by 142
  5. 2018The Mechanics of n-Player Differentiable Gamescited by 118
  6. 2014Analysis and Design of Optimization Algorithms via Integral Quadratic Constraintscited by 105
  7. 2019On the convergence of single-call stochastic extra-gradient methodscited by 88
  8. 2020From Local SGD to Local Fixed-Point Methods for Federated Learningcited by 74
  9. 2021Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with O(1/k2) Rate on Squared Gradient Normcited by 71
  10. 2019Reducing Noise in GAN Training with Variance Reduced Extragradientcited by 61
  11. 2020Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problemscited by 59
  12. 2020Explore Aggressively, Update Conservatively: Stochastic Extragradient Methods with Variable Stepsize Scalingcited by 49
19 more
  1. 2020Tight last-iterate convergence rates for no-regret learning in multi-player gamescited by 47
  2. 2019A Decentralized Parallel Algorithm for Training Generative Adversarial Netscited by 43
  3. 2021Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivitycited by 43
  4. 2019Variance Reduction for Matrix Gamescited by 37
  5. 2015Smooth Strongly Convex Interpolation and Exact Worst-case Performance of First-order Methodscited by 36
  6. 2019Revisiting Stochastic Extragradientcited by 35
  7. 2020Stochastic Hamiltonian Gradient Methods for Smooth Gamescited by 32
  8. 2019Last-iterate convergence rates for min-max optimizationcited by 25
  9. 2021Decentralized Local Stochastic Extra-Gradient for Variational Inequalitiescited by 25
  10. 2014Optimized first-order methods for smooth convex minimizationcited by 18
  11. 2021On the Convergence of Stochastic Extragradient for Bilinear Games using Restarted Iteration Averagingcited by 18
  12. 2019ODE Analysis of Stochastic Gradient Methods with Optimism and Anchoring for Minimax Problemscited by 16
  13. 2018Operator Splitting Performance Estimation: Tight contraction factors and optimal parameter selectioncited by 13
  14. 2019Stochastic first-order methods: non-asymptotic and computer-aided analyses via potential functionscited by 12
  15. 2021The Last-Iterate Convergence Rate of Optimistic Mirror Descent in Stochastic Variational Inequalitiescited by 12
  16. 2016On the worst-case complexity of the gradient method with exact line search for smooth strongly convex functionscited by 9
  17. 2019Scaled Relative Graph: Nonexpansive operators via 2D Euclidean Geometrycited by 5
  18. 2021Potential Function-based Framework for Making the Gradients Small in Convex and Min-Max Optimizationcited by 4
  19. 2019Optimal Nonergodic Sublinear Convergence Rate of Proximal Point Algorithm for Maximal Monotone Inclusion Problemscited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 1; 2022: 10; 2023: 9; 2024: 4; 2025: 7; 2026: 8.

39 papers.

Sort:

  1. 2022A Unified Approach to Reinforcement Learning, Quantal Response Equilibria, and Two-Player Zero-Sum Gamescited by 64
  2. 2022Stochastic Gradient Descent-Ascent: Unified Theory and New Efficient Methodscited by 37
  3. 2021Stochastic Extragradient: General Analysis and Improved Ratescited by 31
  4. 2022Accelerated Single-Call Methods for Constrained Min-Max Optimizationcited by 31
  5. 2022Accelerated Algorithms for Constrained Nonconvex-Nonconcave Min-Max Optimization and Comonotone Inclusioncited by 19
  6. 2022Tight Last-Iterate Convergence of the Extragradient and the Optimistic Gradient Descent-Ascent Algorithm for Constrained Monotone Variational Inequalitiescited by 18
  7. 2024Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimizationcited by 15
  8. 2023Single-Call Stochastic Extragradient Methods for Structured Non-monotone Variational Inequalities: Improved Analysis under Weaker Conditionscited by 14
  9. 2022Clipped Stochastic Methods for Variational Inequalities with Heavy-Tailed Noisecited by 13
  10. 2022PEPit: computer-assisted worst-case analyses of first-order optimization methods in Pythoncited by 10
  11. 2025Negative Stepsizes Make Gradient-Descent-Ascent Convergecited by 9
  12. 2022Tight Analysis of Extra-gradient and Optimistic Gradient Methods For Nonconvex Minimax Problemscited by 7
27 more
  1. 2023Sublinear Convergence Rates of Extragradient-Type Methods: A Survey on Classical and Recent Developmentscited by 5
  2. 2023Last-Iterate Convergence Properties of Regret-Matching Algorithms in Gamescited by 5
  3. 2024Stochastic Extragradient with Random Reshuffling: Improved Convergence for Variational Inequalitiescited by 5
  4. 2025Multiplayer Federated Learning: Reaching Equilibrium with Less Communicationcited by 5
  5. 2023Min-Max Optimization Made Simple: Approximating the Proximal Point Method via Contraction Mapscited by 4
  6. 2023Communication-Efficient Gradient Descent-Accent Methods for Distributed Variational Inequalities: Unified Analysis and Local Updatescited by 4
  7. 2022Solving Constrained Variational Inequalities via a First-order Interior Point-based Methodcited by 3
  8. 2023Stable Nonconvex-Nonconcave Training via Linear Interpolationcited by 3
  9. 2024Primal Methods for Variational Inequality Problems with Functional Constraintscited by 3
  10. 2025Extragradient Method for (L0, L1)-Lipschitz Root-finding Problemscited by 3
  11. 2025Maximum Risk Minimization with Random Forestscited by 3
  12. 2023Demystifying the Myths and Legends of Nonconvex Convergence of SGDcited by 2
  13. 2026Unbiased and Biased Variance-Reduced Forward-Reflected-Backward Splitting Methods for Stochastic Composite Inclusionscited by 2
  14. 2022When is Momentum Extragradient Optimal? A Polynomial-Based Analysiscited by 1
  15. 2023Extragradient Type Methods for Riemannian Variational Inequality Problemscited by 1
  16. 2024Learning Variational Inequalities from Data: Fast Generalization Rates under Strong Monotonicitycited by 1
  17. 2026Parameter-Free Non-Ergodic Extragradient Algorithms for Solving Monotone Variational Inequalitiescited by 1
  18. 2023Extragradient-Type Methods with O (1/k) Last-Iterate Convergence Rates for Co-Hypomonotone Inclusionscited by 0
  19. 2025A regret minimization approach to fixed-point iterationscited by 0
  20. 2025Generative modeling using evolved quantum Boltzmann machinescited by 0
  21. 2025Computing Pure-Strategy Nash Equilibria in a Two-Party Policy Competition: Existence and Algorithmic Approachescited by 0
  22. 2026Shuffling the Data, Stretching the Step-size: Sharper Bias in constant step-size SGDcited by 0
  23. 2026Negative Momentum for Convex-Concave Optimizationcited by 0
  24. 2026A Unifying View of Anchoring via Operator-Side Tikhonov Regularizationcited by 0
  25. 2026Accelerated and Stable Convergence with Anchored Generalized Optimistic Methodcited by 0
  26. 2026On Same-Sample and Independent-Sample Stochastic Extragradient for Monotone Variational Inequalitiescited by 0
  27. 2026Polyak-Type Extragradient Methods for Monotone Root-Finding Problemscited by 0