mlsanityData to 7 Oct 2026

Sublinear Convergence Rates of Extragradient-Type Methods: A Survey on Classical and Recent Developments

arXiv 2303.17192 ↗First posted 30 Mar 2023math.OC stat.MLcited by 5

Not on the map. Why?

Abstract (arXiv)

The extragradient (EG), introduced by G. M. Korpelevich in 1976, is a well-known method to approximate solutions of saddle-point problems and their extensions such as variational inequalities and monotone inclusions. Over the years, numerous variants of EG have been proposed and studied in the literature. Recently, these methods have gained popularity due to new applications in machine learning and robust optimization. In this work, we survey the latest developments in the EG method and its variants for approximating solutions of nonlinear equations and inclusions, with a focus on the monotonicity and co-hypomonotonicity settings. We provide a unified convergence analysis for different classes of algorithms, with an emphasis on sublinear best-iterate and last-iterate convergence rates. We also discuss recent accelerated variants of EG based on both Halpern fixed-point iteration and Nesterov's accelerated techniques. Our approach uses simple arguments and basic mathematical tools to make the proofs as elementary as possible, while maintaining generality to cover a broad range of problems.

Key facts. Cited by 5 papers in the map (data through 7 Oct 2026). Builds on 58 of its 141 references that are in the map. First posted on arXiv 30 Mar 2023.

Builds on

58 of 141 references.

References · 58

  1. 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,326
  2. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  3. 2017Training GANs with Optimismcited by 217
  4. 2015A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insightscited by 203
  5. 2020Large-Scale Methods for Distributionally Robust Optimizationcited by 179
  6. 2018A Variational Inequality Perspective on Generative Adversarial Networkscited by 144
  7. 2019A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approachcited by 142
  8. 2018Optimistic mirror descent in saddle-point problems: Going the extra (gradient) milecited by 132
  9. 2020Near-Optimal Algorithms for Minimax Optimizationcited by 119
  10. 2016A Variational Perspective on Accelerated Methods in Optimizationcited by 108
  11. 2020A Survey on Generative Adversarial Networks: Variants, Applications, and Trainingcited by 97
  12. 2020Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimizationcited by 94
38 more
  1. 2019On the convergence of single-call stochastic extra-gradient methodscited by 88
  2. 2021Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with O(1/k2) Rate on Squared Gradient Normcited by 71
  3. 2018Understanding the Acceleration Phenomenon via High-Resolution Differential Equationscited by 68
  4. 2021Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Gamescited by 66
  5. 2021Fast Extra Gradient Methods for Smooth Structured Nonconvex-Nonconcave Minimax Problemscited by 61
  6. 2020Halpern Iteration for Near-Optimal and Parameter-Free Monotone Inclusion and Strong Solutions to Variational Inequalitiescited by 60
  7. 2020Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problemscited by 59
  8. 2016Tight Complexity Bounds for Optimizing Composite Objectivescited by 47
  9. 2021Stochastic Variance Reduction for Variational Inequality Methodscited by 46
  10. 2021Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivitycited by 43
  11. 2021Extragradient Method: O(1/K) Last-Iterate Convergence for Monotone Variational Inequalities and Connections With Cocoercivitycited by 39
  12. 2018Golden Ratio Algorithms for Variational Inequalitiescited by 38
  13. 2018A Forward-Backward Splitting Method for Monotone Inclusions Without Cocoercivitycited by 35
  14. 2015A Three-Operator Splitting Scheme and its Optimization Applicationscited by 34
  15. 2017Extragradient method with variance reduction for stochastic variational inequalitiescited by 33
  16. 2022Accelerated Single-Call Methods for Constrained Min-Max Optimizationcited by 31
  17. 2014Accelerated Schemes For A Class of Variational Inequalitiescited by 30
  18. 2013On the Convergence Properties of Non-Euclidean Extragradient Methods for Variational Inequalities with Generalized Monotone Operatorscited by 29
  19. 2015Projected Reflected Gradient Methods for Monotone Variational Inequalitiescited by 27
  20. 2019Generalized monotone operators and their averaged resolventscited by 27
  21. 2022Solving Nonconvex-Nonconcave Min-Max Problems exhibiting Weak Minty Solutionscited by 27
  22. 2022Exact Optimal Accelerated Complexity for Fixed-Point Iterationscited by 23
  23. 2015ARock: an Algorithmic Framework for Asynchronous Parallel Coordinate Updatescited by 21
  24. 2023Solving stochastic weak Minty variational inequalities without increasing batch sizecited by 21
  25. 2023Escaping limit cycles: Global convergence for constrained nonconvex-nonconcave minimax problemscited by 21
  26. 2021Halpern-Type Accelerated and Splitting Algorithms For Monotone Inclusionscited by 20
  27. 2013Optimal Primal-Dual Methods for a Class of Saddle Point Problemscited by 19
  28. 2014Optimal stochastic extragradient schemes for pseudomonotone stochastic variational inequality problems and their variantscited by 19
  29. 2022Accelerated Algorithms for Constrained Nonconvex-Nonconcave Min-Max Optimization and Comonotone Inclusioncited by 19
  30. 2022From Halpern's Fixed-Point Iterations to Nesterov's Accelerated Interpretations for Root-Finding Problemscited by 18
  31. 2022Tight Last-Iterate Convergence of the Extragradient and the Optimistic Gradient Descent-Ascent Algorithm for Constrained Monotone Variational Inequalitiescited by 18
  32. 2022Branch-and-Bound Performance Estimation Programming: A Unified Methodology for Constructing Optimal Optimization Methodscited by 16
  33. 2022Convergence of Proximal Point and Extragradient-Based Methods Beyond Monotonicity: the Case of Negative Comonotonicitycited by 16
  34. 2015The rate of convergence of Nesterov's accelerated forward-backward method is actually faster than 1/k2cited by 15
  35. 2022Beyond the Golden Ratio for Variational Inequality Algorithmscited by 12
  36. 2022Fast Optimistic Gradient Descent Ascent (OGDA) method in continuous and discrete timecited by 10
  37. 2022From the Ravine method to the Nesterov method and vice versa: a dynamical system perspectivecited by 9
  38. 2015A Smooth Primal-Dual Optimization Framework for Nonsmooth Composite Convex Minimizationcited by 8

50 most cited of 58 All 58 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 1; 2024: 2; 2025: 0; 2026: 2.

5 papers.

  1. 2023Variance Reduced Halpern Iteration for Finite-Sum Monotone Inclusionscited by 10
  2. 2024Revisiting Inexact Fixed-Point Iterations for Min-Max Problems: Stochasticity and Structured Nonconvexitycited by 4
  3. 2024Revisiting Extragradient-Type Methods -- Part 1: Generalizations and Sublinear Convergence Ratescited by 2
  4. 2026Parameter-Free Non-Ergodic Extragradient Algorithms for Solving Monotone Variational Inequalitiescited by 1
  5. 2026RAMPAGE: RAndomized Mid-Point for debiAsed Gradient Extrapolationcited by 0